Find the maximum number of 1s in matrix $A$ such that $A^2=0$ and elements of $A$ are either $0$ or $1$ Let $A$ be a square matrix(n by n) that consists of $1$s and $0$s. Find the maximum number of $1$s the matrix A can have if $A^2=0$.
Attempt
My only observation is that if $A_{ij}=1$, $j^{th}$ row and $i^{th}$ column cannot have any element other than $0$.
Also, I can prove that $rank(A)\le n/2$
 A: To get a lower bound of $\left\lfloor \frac{n}{2} \right\rfloor \left\lceil \frac{n}{2} \right\rceil$, let $A$ be the adjacency matrix of a directed complete bipartite graph with left nodes $\left\{1,\dots,\left\lfloor \frac{n}{2} \right\rfloor\right\}$, right nodes $\left\{\left\lfloor \frac{n}{2} \right\rfloor+1,\dots,n\right\}$, and all arcs going from left to right.  The condition $A^2=0$ corresponds to the nonexistence of a directed path of length 2.
To see that this is also an upper bound, partition the node set $N=\{1,\dots,n\}$ into four disjoint sets:
\begin{align}
N_1 &= \text{nodes with at least one outgoing arc and no incoming arcs} \\
N_2 &= \text{nodes with at least one incoming arc and no outgoing arcs} \\
N_3 &= \text{nodes with at least one outgoing arc and at least one incoming arc} \\
N_4 &= \text{nodes with no outgoing or incoming arcs}
\end{align}
Now $A^2=0$ implies $N_3=\emptyset$.  Also, $N_4=\emptyset$ because otherwise we could increase the number of arcs by adding arcs from $N_4$ to $N_2$.  Hence $|N_1|+|N_2|=n$, and we can achieve $|N_1||N_2|=|N_1|(n-|N_1|)$ arcs by including all possible arcs from $N_1$ to $N_2$.  It is well known that $|N_1|=\lfloor n/2\rfloor$ maximizes this product, or you can prove it directly by showing that any other partition of $n$ into $n_1+n_2$ with $n_1 \le n_2$ can be improved.
