15
$\begingroup$

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!

$\endgroup$
  • 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$ – Fedor Petrov 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
  • 1
    $\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
  • 1
    $\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 at 3:09

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.