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


*

*In the particular case, when $a_{ij}=±1$, the lower bound holds. See this answer below, for an overview of the proof.

 A: 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.
A: 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} $$
A: 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$. 
