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(n2)$ and will it be possible to prove by any means?
$\begingroup$
$\endgroup$
4

$\begingroup$ Can you please briefly indicate where the conjectured bound $2n(n2)$ came from? $\endgroup$– Christian RemlingJan 3, 2023 at 5:04

$\begingroup$ @Christian $n\ge 3$ $\endgroup$– shahulhameedJan 3, 2023 at 12:10

1$\begingroup$ @Christian The upper bound is obtained for the $n \times n$ matrices $A'$ and $B'$ where the nondiagonal entries are all one in the former and $1$ for the latter. $\endgroup$– shahulhameedJan 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(n2)$. It is plausible that that case is easier to prove. $\endgroup$– Brendan McKayJan 4, 2023 at 7:11
Add a comment

1 Answer
$\begingroup$
$\endgroup$
6
A bound seems $4n(n1)$, attained for $A=JI$ 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(n1)$$ 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)^22\sum\limits_{i=1}^n\lambda_i(A)\lambda_i(B)\le 4n(n1)$$ by CauchySchwarz. Edit.

1$\begingroup$ This is a correct proof of the bound $4n(n1)$ but it is not attained by $A=JI, B=A$. You need to sort the eigenvalues separately for $A$ and $B$. For $A$ it is $n1,1,\ldots,1$ and for $B$ it is $1,\ldots,1,(n1)$. This gives $2n(n2)$ as OP said. $\endgroup$ Jan 4, 2023 at 6:27

$\begingroup$ @Brendan Mckay Yes, I strongly feel that $2n(n2)$ is a tight bound which is attained for the matrices $A=JI$ 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 $n1$, 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