# Is this lower bound for a norm of some complex matrices true?

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

• In the particular case, when $a_{ij}=±1$, the lower bound holds. See this answer below, for an overview of the proof.
• @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. – Yemon Choi Jun 9 '18 at 16:15
• @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). – Christian Remling Jun 9 '18 at 16:17
• 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$). – Yemon Choi Jun 10 '18 at 20:04
• Another cheap observation is that the minimum is $(2+o(1))n$ as $n\to\infty$, so the conjecture is quite plausible. – fedja Jun 10 '18 at 20:23
• 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 – Terry Tao Jun 13 '18 at 19:04

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.

• 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$? – Yemon Choi Jun 14 '18 at 6:25
• @ 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$. – Alex Gavrilov Jun 14 '18 at 8:13
• 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. – Mahdi Jun 14 '18 at 9:09
• I agree. But this would be a question from number theory, which I do not know much of. – Alex Gavrilov Jun 14 '18 at 9:11
• @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? – Yemon Choi Jun 14 '18 at 13:04


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}$$

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