7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you have ample numerical evidence that this property holds? $\endgroup$ – Federico Poloni Dec 5 '15 at 11:27
  • $\begingroup$ 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. $\endgroup$ – Fedor Petrov Dec 5 '15 at 12:48
10
$\begingroup$

The claim is false.

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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