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

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.


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


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