Working on a problem in combinatorics I come up with the following inequality on matrix norms, which I checked it also numerically:

Let $A=(a_{ij})$ be a real symmetric $n\times n$ matrix with trace equal to zero. If $\lambda_1,\dots,\lambda_n$ be all of eigenvalues of $A$, then $$\sum_i |\lambda_i|\geq \frac{1}{n-1} \sum_{i\neq j} \big\vert a_{ij}-\frac{a_{ii}+a_{jj}}{2}\big\vert.$$

I have a very long combinatorial proof for this inequality, but I'm curious if there is a more straightforward proof. Thanks!

  • 1
    $\begingroup$ Wlog we may suppose that $a_{ij}=x_i x_j-y_i y_j$ for two orthogonal unit vectors $x, y$. $\endgroup$ Dec 19 '18 at 21:10
  • $\begingroup$ @FedorPetrov Yes.And the whole fight is for $-1$ in $n-1$; if we had the factor $1/n$ instead, the estimate would be trivial. $\endgroup$
    – fedja
    Dec 19 '18 at 21:57
  • 2
    $\begingroup$ For what it's worth, here is an equivalent reformulation. Let $G=(V,E)$ be a finite graph. Define $\Lambda(G)$ to be the largest constant $\lambda$ such that $\sum_{(i,j)\in E}(x_i-x_j)^2\ge\lambda \sum_{i\in V}x_i^2$ for all real $x_i$ with $\sum_{i\in V}x_i=0$. We want to show that $\Lambda(G)+\Lambda(G^c)\ge 1$ where $G^c$ is the complement of $G$. $\endgroup$
    – fedja
    Dec 21 '18 at 2:36
  • 2
    $\begingroup$ @fedja: Your equivalent reformulation is actually the source of the question asked by Mostafa. I and Mostafa have an almost long proof for it and we will submit a primary version of the proof on Arxiv, as soon as possible. We are curious to know is there any more straightforward proof based on the reformulation stated in OP? Thanks a lot. $\endgroup$
    – Mahdi
    Dec 21 '18 at 12:42
  • 3
    $\begingroup$ @fedja: A solution for your equivalent reformulation is here, arxiv.org/pdf/1901.02047. I'm sorry for the delay in sharing the solution. It is pleasant if you tell us your constructive advice about the solution. I have learned a lot from you in MO. Merry Christmas, Dear Fedja. $\endgroup$
    – Mahdi
    Jan 9 '19 at 3:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.