Matrix inequality involving the sum of elements 
Let $M$ a $n \times n$ matrix that has all elements either $1$ or
$-1$. Prove that the sum of the elements of $M^2$ is at least
$\dfrac{n(5-6n)}{3}$.

My trial: I will denote the trace of a matrix by $\text{Tr }(...)$. Let $U$ the $n\times n$ matrix that has all the elements $1$. Then the sum of the elements of $M^2$ is $\text{Tr }(UM^2)$. I also thought it would work if we let $M=[b_{ij}]_{1\leq i,j\leq n }$ where $|b_{ij}|=1$. Then, by considering $L_i$ the sum of all the elements of the line $i$ of $M$ and $C_i$ the same but for columns, then the inequality becomes
$$L_1C_1+\dots+L_nC_n\geq\frac{n(5-6n)}{3}.$$
It is also clear that $L_1+\dots+L_n=C_1+\dots+C_n$.
Please help me find a proof to this! Thank you in advance!
 A: The assertion is wrong. Let $M$ be a matrix where the upper right triangular block, including the diagonal itself, has elements $+1$, and the  lower left triangular block has elements $-1$. Then, as introduced by OP,  we consider row sums and column sums. The $k$th row has sum  $L_k = n+2-2\cdot k$, the $k$th column has sum  $C_k = -n+2\cdot k$. This gives
$$
L_1C_1+\dots+L_nC_n = \sum_{k=1}^n (n+2-2\cdot k)(-n+2\cdot k) = \frac{n (4 - n^2)}{3}
$$
Now we see that for $n\ge 6$ we have $\frac{n(5-6n)}{3} - \frac{n (4 - n^2)}{3} > 0 $, so indeed for  $n\ge 6$ the sum of all elements of $M^2$ in this case becomes smaller than the claimed $\frac{n(5-6n)}{3}$. $\qquad \Box$

It is hypothesized that for the presented triangular matrix structure, indeed the sum of elements of $M^2$ is smallest amongst all matrix realisations. Computer simulations for the first $n$ confirm this, note that there are $2^{n^2}$ many realisations of the matrix $M$.
More importantly, there is a "greedy" argument which supports this hypothesis. We want to minimize the sum $L_1C_1+\dots+L_nC_n$. Proceed iteratively. Start with the first term  $L_1C_1$. This becomes minimal if  $L_1$ is maximally positive and $C_1$ is maximally negative (or the other way around). This is achieved if the first row is all positive, and if the first column is all negative. The latter is not possible, since the first row and the first column have the element $M_{1,1}$ in common, hence the best choice is to have all further elements of the first column negative. Changing the sign of $M_{1,1}$ makes no difference.
Now proceed with the second term
$L_2C_2$. The same arguments hold, however $M_{2,1}$ and $M_{1,2}$ are already set in the first step. Let the rest of the second row/column be positive / negative. The first two terms together then give $n\cdot(2-n) + (n-2)\cdot(4-n) = -2(n-2)^2$. Now consider changing the sign and let $M_{1,2} = -1$. The first two terms together then give $(n-2)\cdot(2-n) + (n-2)\cdot(2-n) = -2(n-2)^2$. So indeed nothing changes.
This can be continued with change of  sign of $M_{1,2}$, or with both of $M_{1,2}$ and  $M_{2,1}$, with no effect. Hence minimality is preserved. Further, continue in the same vein with each further term in $L_3C_3 \cdots L_nC_n$. Once completed, this gives exactly the proposed matrix structure (and equivalent ones, applying  sign changes which are ineffective for the minimality of the sum).
