3
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Can you please briefly indicate where the conjectured bound $2n(n-2)$ came from? $\endgroup$ Jan 3, 2023 at 5:04
  • $\begingroup$ @Christian $n\ge 3$ $\endgroup$ 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$ 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$ Jan 4, 2023 at 7:11

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
6
  • 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$ 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$ 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$ Jan 5, 2023 at 9:19
  • 1
    $\begingroup$ @shahulhameed The eigenvalues can range from $-n+1$ to $n-1$, including 0. $\endgroup$ 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$ Jan 6, 2023 at 0:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.