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](https://mathoverflow.net/questions/303091/l1-norm-of-littlewood-polynomials-on-the-unit-circle)).   

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