16
$\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!

Improve this question
$\endgroup$
9
  • 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
    Commented Dec 19, 2018 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
    Commented Dec 19, 2018 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
    Commented Dec 21, 2018 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 - Free Palestine
    Commented Dec 21, 2018 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 - Free Palestine
    Commented Jan 9, 2019 at 3:09

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .