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

• Looks like oeis.org/A002620 Oct 16 '20 at 1:16
• It is not generally true that $\operatorname{rank}(A) \leq 4$ unless we have some restriction on $n$ that you're not telling us about. For example, the $(2k) \times (2k)$ matrix $$A = \pmatrix{0 & I_k\\0 & 0}$$ has rank $k$ and satisfies $A^2 = 0$. Oct 16 '20 at 1:30
• Sorry you're right. It is not 4. It is n/2.
– arke
Oct 16 '20 at 3:44

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.