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

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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