Suppose $A$ and $B$ are two symmetric real $\{0,1,-1\}$ matrices of order $n$ with diagonal elements as zeros (therefore the traces are zeros) and eigenvalues $\lambda_1\ge \lambda_2\ge \dotsb \ge \lambda_n$ and $\mu_1\ge \mu_2\ge \dotsb \ge \mu_n$ respectively, then can we find upper bound for the sum $S(A,B)=\sum\limits_{i=1}^n(\lambda_i-\mu_i)^2$ in terms of $n$? Will the upper bound be $2n(n-2)$ and will it be possible to prove by any means?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Can you please briefly indicate where the conjectured bound $2n(n-2)$ came from? $\endgroup$– Christian RemlingCommented Jan 3, 2023 at 5:04
-
$\begingroup$ @Christian $n\ge 3$ $\endgroup$– shahulhameedCommented Jan 3, 2023 at 12:10
-
1$\begingroup$ @Christian The upper bound is obtained for the $n \times n$ matrices $A'$ and $B'$ where the non-diagonal entries are all one in the former and $-1$ for the latter. $\endgroup$– shahulhameedCommented Jan 3, 2023 at 12:22
-
$\begingroup$ Note that $\varLambda A\varLambda$ has the same eigenvalues as $A$ if $\varLambda$ is a $\pm1$ diagonal matrix, so the optimum is not unique. I did some simulations for the case $B=-A$, $3\le n\le 10$ and didn't find anything bigger than $2n(n-2)$. It is plausible that that case is easier to prove. $\endgroup$– Brendan McKayCommented Jan 4, 2023 at 7:11
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
A bound seems $4n(n-1)$, attained for $A=J-I$ and $B=-A$ (as in the comment) -edit- if we allow any ordering of the eigenvalues. First $$\sum_{i=1}^n\lambda_i(A)^2=\text{Tr}(A^2)=\sum_{i,j}|a_{i,j}|^2\le n(n-1)$$ since $A$ is symmetric with a zero diagonal and entries $a_{i,j}$ in $\{0,-1,1\}$ ; $$\sum\limits_{i=1}^n(\lambda_i(A)-\lambda_i(B))^2=\sum\limits_{i=1}^n\lambda_i(A)^2+\sum\limits_{i=1}^n\lambda_i(B)^2-2\sum\limits_{i=1}^n\lambda_i(A)\lambda_i(B)\le 4n(n-1)$$ by Cauchy-Schwarz. Edit.
-
1$\begingroup$ This is a correct proof of the bound $4n(n-1)$ but it is not attained by $A=J-I, B=-A$. You need to sort the eigenvalues separately for $A$ and $B$. For $A$ it is $n-1,-1,\ldots,-1$ and for $B$ it is $1,\ldots,1,-(n-1)$. This gives $2n(n-2)$ as OP said. $\endgroup$ Commented Jan 4, 2023 at 6:27
-
$\begingroup$ @Brendan Mckay Yes, I strongly feel that $2n(n-2)$ is a tight bound which is attained for the matrices $A=J-I$ and $B=-A$. The question is whether we can prove it by some means; I hope matrix norms would help us by intuition $\endgroup$ Commented Jan 4, 2023 at 7:32
-
$\begingroup$ @Toni Mhax If we can prove that maximum eigenvalue of these matrices have least upper bound 1, then I have the proof for the bound. Can anybody help me $\endgroup$ Commented Jan 5, 2023 at 9:19
-
1$\begingroup$ @shahulhameed The eigenvalues can range from $-n+1$ to $n-1$, including 0. $\endgroup$ Commented Jan 5, 2023 at 10:14
-
1$\begingroup$ Except for $B=0$, yes. Say $B$ is a counterexample and replace it by $-B$ if necessary so that $\lambda_1$ has the greatest absolute value. For integer $k$, the trace of $B^{2k}$ is $\sum_i{\lambda_i^{2k}}$. If all the eigenvalues are less than 1 in absolute value, and not all zero, this expression will be strictly between 0 and 1 for large enough $k$. But the trace of $B^{2k}$ is an integer, so there is no such $B$. $\endgroup$ Commented Jan 6, 2023 at 0:56