# Sum of the absolute eigenvalues of A>=B

Kindly help me to prove/disprove the following statement.
Let $A$ be a symmetric matrix of order $n \times n$ with all the diagonal entry equal to $0$, and other non-diagonal entry equal to $k$ (where $k$ is a fixed positive integer). Similarly,
Let $B$ be a symmetric matrix of order $n \times n$ with every diagonal entry equal to $0$, and each non-diagonal entry equal to some $\ell$ with $1\leq \ell \leq k<n$.

For example:$A= \begin{pmatrix} \begin{array}{cccc} 0 & 3 & 3 & 3 \\ 3 & 0 & 3 & 3 \\ 3 & 3 & 0 & 3 \\ 3 & 3 & 3 & 0 \\ \end{array}\end{pmatrix}$, $B=\begin{pmatrix} \begin{array}{cccc} 0 & 3 & 1 & 2 \\ 3 & 0 & 2 & 3 \\ 1 & 2 & 0 & 1 \\ 2 & 3 & 1 & 0 \\ \end{array} \end{pmatrix}$.
Prove/disprove the following statement:

Suppose $\lambda_1, \lambda_2, ..., \lambda_n$ are eigenvalues of $A$ and $\mu_1, \mu_2, ..., \mu_n$ are eigenvalues of $B$. Then $$\sum_{i=1}^{n}{|\lambda_i|}\geq \sum_{i=1}^{n}{|\mu_i|}.$$
Note that $A$ and $B$ are the distance matrices of some vertices(diameteral) of $G_1$ and $G_2$ respectively.

• Do you have ample numerical evidence that this property holds? – Federico Poloni Dec 5 '15 at 11:27
• when you say other non-diagonal entry equal to $\ell$'', you mean that $\ell$ may depend on the entry? Else I do not understand your example. – Fedor Petrov Dec 5 '15 at 12:48

In particular, we have $A=kee^T-kI$, so that $\lambda(A)=((n-1)k,-k,\ldots,-k)$, so that $\|A\|_* = 2(n-1)k$.
Now generate a random matrix $B$ such that $B_{ii}=0$, $B_{ij}=B_{ji}$ and $B_{ij} \le A_{ij}$ for every entry. It does not matter that the entries of $B$ are integers or not (to have a "clean" example, I round the entries below to ensure that $B$ is integral). In particular, try the following Matlab code:
n=63;k=3;B=ceil(k*rand(n));B=B-diag(diag(B));B=round((B+B')/2);sum(svd(B))-2*(n-1)*k

Quite easily one obtains $\|B\|_* > \|A\|_* = 2(n-1)k=372$.
Other choices of $n$ and $k$ can give you smaller explicit examples if you wish to find (e.g., $n=23, k=2$ also worked after some attempts).