15
$\begingroup$

Let $A = [a_{ij}]_{n\times n}$ be a Hermitian matrix, such that $|a_{ij}| =1$ for $i \neq j$, and $a_{ii} = 0$ for each $i$. I am interested in a tight lower bound of $\|A\|_*:=\sum_{i=1}^n |\lambda_i(A)|$, where $\lambda_i(A)$'s are eigenvalues of $A$.

Note that, by minimizing $\sum_{i=1}^n |\lambda_i|$ over two constraints $\sum_{i=1}^n \lambda_i = 0$ and $\sum_{i=1}^n \lambda_i^2= n(n-1)$, one can obtain $\sqrt{2n(n-1)}$ as a lower bound. But it seems that isn't tight.

On the other hand, if $A := J - I$ (all ones matrix minus identity), then $\sum_i |\lambda_i(A)| = 2(n-1)$.

Is it true that $2(n-1)$ is actually a lower bound (for large enough matrices, say $n \geq 10$) ?

Remarks:

  • As Alex's answer below, the minimum of trace norm of such matrices may be less than $2(n-1)$, even for arbitrarily large matrices.

  • But, as a comment of @fedja, the minimum is $(2+o(1))n$ as $n\to\infty$.

Added:

  • In the particular case, when $a_{ij}=±1$, the lower bound holds. See this answer below, for an overview of the proof.
$\endgroup$
  • $\begingroup$ @ChristianRemling Thanks - I deleted my misguided comment, of course in my approach I was ignoring the diagonal terms which give an $O(n)$ "correction" to my estimate of the trace norm. $\endgroup$ – Yemon Choi Jun 9 '18 at 16:15
  • $\begingroup$ @YemonChoi: But the idea may have been spot on, I'm also curious now what happens for random $\pm 1$'s (or complex $a_{jk}$'s with random phase). $\endgroup$ – Christian Remling Jun 9 '18 at 16:17
  • 1
    $\begingroup$ If we can show that every matrix $A$ of the form you describe satisfies $\inf\{ \Vert A-D\Vert_{\rm op} : D \hbox{ is diagonal} \} \leq n/2$ then the answer to your question is positive. In particular, we win if the spectrum of $A$ is supported in an interval of length $\leq n$. But I haven't managed to prove this (although it does hold for $A=J-I$). $\endgroup$ – Yemon Choi Jun 10 '18 at 20:04
  • 2
    $\begingroup$ Another cheap observation is that the minimum is $(2+o(1))n$ as $n\to\infty$, so the conjecture is quite plausible. $\endgroup$ – fedja Jun 10 '18 at 20:23
  • 2
    $\begingroup$ If one restricts attention to circulant matrices then the problem begins to closely resemble the Littlewood problem, see e.g. arxiv.org/abs/math/0601565 $\endgroup$ – Terry Tao Jun 13 '18 at 19:04
5
$\begingroup$

No, it is not; in fact, $2(n-1)$ is a local maximum.

Let $B$ be a Hermitian matrix such that $|B_{ij}|=1$ and $B_{ii}=1$. We denote its eigenvalues by $\mu$ (not to confuse them with eigenvalues of $A$). It is easy to see that always $\mu\le n$: if $(x_1,\dots,x_n)$ is an eigenvector and $|x_i|=\max_j|x_j|$ then $$|\mu x_i|=\left|\sum_j B_{ij}x_j\right|\le \sum_j |x_j|\le n|x_i|.$$

If $A=B-I$ then $$\sum_i |\lambda_i|=\sum_i |\mu_i-1|.$$ In the case $B=J$ we have $\mu_1=n$ and $\mu_i=0,2\le i\le n$, hence $$\sum_i |\lambda_i|=2(n-1).$$ If $B$ is not much different from $J$ then we still have one large eigenvalue $\mu_1$ and plenty of small ones, $\mu_i<1,2\le i\le n$. In this more general case $$\sum_i |\lambda_i|=\mu_1-1+\sum_{i=2}^n(1-\mu_i)=2(\mu_1-1)\le 2(n-1).$$ Naturally, even in a vicinity of $J$ it won't always be an equality.

$\endgroup$
  • $\begingroup$ Regarding the updated version: for $n=2$ all matrices $A$ of the required form have eigenvalues $\pm 1$, so they all have trace norm $2$. Can you show an explicit example for $n=3$ with trace norm strictly less than $4$? $\endgroup$ – Yemon Choi Jun 14 '18 at 6:25
  • $\begingroup$ @ Yemon Choi: If $\mu=n$ then all $x_i$ must have the same absolute value. Then we may modify $B$ taking the conjugate of it by a diagonal unitary matrix and turning the eigenvector into $(1,1,\dots,1)$. It follows that $B$ in this case must be conjugate to $J$. $\endgroup$ – Alex Gavrilov Jun 14 '18 at 8:13
  • $\begingroup$ Actually, this is a complete answer to my question. But the problem still is open, when the phase of $a_{ij}$s are chosen from a finite discrete set containing zero (In particular, when $a_{ij} = \pm 1$). That cases may be related to the Littlewood problem when $A$ is a circulant matrix, according to the comment of Tao above. $\endgroup$ – Mahdi Jun 14 '18 at 9:09
  • $\begingroup$ I agree. But this would be a question from number theory, which I do not know much of. $\endgroup$ – Alex Gavrilov Jun 14 '18 at 9:11
  • $\begingroup$ @AlexGavrilov Thank you for the explanation of this case, but this doesn't seem to answer my question. You say that $2(n-1)$ is a local maximum but don't give examples where inequality is strict, and my point was that for $n=2$ inequality can't be strict. So what are some explicit numbers for $n=3$ (or $n=4,\dots$) where inequality is strict? $\endgroup$ – Yemon Choi Jun 14 '18 at 13:04
3
$\begingroup$

This is merely to expand on one of my comments above. $\newcommand{\Tr}{{\rm Tr}}$ $\newcommand{\snorm}[2]{\Vert#2\Vert_{(#1)}}$

We recall that for any complex $n\times n$ matrix $X$, the trace norm of $X$ is equal to $\sup\{ | \Tr(XY^*) | \}$ where the supremum is taken over all $n\times n$ complex matrices $Y$ satisfying $\snorm{\infty}{Y}\leq 1$. Here $\snorm{\infty}{\cdot}$ denotes the operator norm, a.k.a. the largest singular value.

Now suppose $A$ has all diagonal entries equal to zero, and let $D$ be any diagonal matrix. Then

$$ \Tr(A (A+D)^*) = \sum_{j,k} A_{jk}\overline{(A_{jk}+D_{jk})} = \sum_{j\neq k} |A_{jk}|^2 = \snorm{2}{A}^2 $$

where $\snorm{2}{\cdot}$ denotes the Hilbert-Schmidt norm, a.k.a. the Frobenius norm.

Consequently $\snorm{2}{A}^2 \leq \snorm{1}{A} \inf_D \snorm{\infty}{A+D}$. If we impose the further constraint that $|A_{jk}|=1$ for all $j\neq k$ then the LHS of this inequality is equal to $n^2-n$, and so

$$ \snorm{1}{A} \geq n(n-1) \cdot\left( \inf_D \snorm{\infty}{A+D} \right)^{-1} $$

$\endgroup$
2
$\begingroup$

In the special case $a_{ij} = \pm 1$, $2(n-1)$ is a lower bound, for every $n>0$.

As a comment by T. Tao above, the problem resembles the sharp Littlewood conjecture on the minimum of the $L^{1}$-norm of polynomials (on the unit circle in the complex plane) whose absolute values of coefficients are equal to $1$. In the special class of polynomials with $\pm 1$ coefficients, Klemes proved the sharp Littlewood conjecture (see here).

The proof of Klemes gives us the following equality, for an $n\times m$ matrix $A$ with singular values $\sigma_1,\ldots,\sigma_{r}$ and for $ 0 \leq p \leq 2 $: \begin{equation*} \sum \limits_{i=1}^{r} \vert \sigma_{i} \vert^p= C_p \int_{0}^{\infty} \log \left(1+\sum \limits_{k=1}^{r} S_{k}(A^*A) t^{k} \right)t^{-\frac p2 -1}dt, \end{equation*} where $S_k(A^*A)$ stand for the sum of the determinat of $k\times k$ principle submatrices of $A^*A$ and $C_p$ is a constant depenting on $p$.

When $A$ is Hermitian, singular values are equal to eigenvalues and by obtaining a "good" lower bound for $S_{k}(A^2)$, when $A$ is a matrix of the form described in the question, we can establish the lower bound in the special case $a_{ij} = \pm 1$.

$\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.