# An inequality for matrix norms

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!

• Wlog we may suppose that $a_{ij}=x_i x_j-y_i y_j$ for two orthogonal unit vectors $x, y$. Dec 19 '18 at 21:10
• @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. Dec 19 '18 at 21:57
• 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$. Dec 21 '18 at 2:36
• @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. Dec 21 '18 at 12:42
• @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. Jan 9 '19 at 3:09