Maximum Ones in a Nilpotent Binary Matrix

Worked Solution

How to Think About It: The condition $A^2 = 0$ is a constraint on *paths*, not just on rank. Read $A$ as the adjacency matrix of a directed graph on $n$ vertices: $A_{ik} = 1$ means there is an edge $i \to k$. The $(i,j)$ entry of $A^2$ counts directed paths $i \to k \to j$ of length two. Because every entry of $A$ is $0$ or $1$ -- so the products $A_{ik}A_{kj}$ are nonnegative and *cannot cancel* -- $A^2 = 0$ is equivalent to the purely combinatorial statement: there is no directed path of length two anywhere in the graph. The whole problem reduces to: how many edges can a directed graph on $n$ vertices have if it contains no path of length two? That count is the number of $1$s.

Quick Estimate: "No length-two path" means no vertex can be both the head of some edge and the tail of some edge -- otherwise those two edges would chain into a length-two path. So the vertices that *emit* edges and the vertices that *receive* edges form two disjoint groups. If $a$ vertices emit and $b$ vertices receive (with $a + b \le n$), the most edges you can have is the complete bipartite $a \times b$ block, $a\cdot b$ edges. Maximizing $a\cdot b$ subject to $a + b \le n$ gives $a = \lfloor n/2 \rfloor$, $b = \lceil n/2 \rceil$, so the answer should be $\lfloor n/2 \rfloor \lceil n/2 \rceil = \lfloor n^2/4 \rfloor$. For $n = 6$: $9$. For $n = 7$: $12$.

Approach: Translate $A^2 = 0$ into "no length-two directed path," prove that this forces the emitting and receiving vertex sets to be disjoint (yielding the upper bound $\lfloor n^2/4\rfloor$ by AM-GM), then exhibit a construction that attains it.

Formal Solution:

*Step 1 -- Reformulate the constraint combinatorially.* For any $i, j$, $$\bigl(A^2\bigr)_{ij} = \sum_{k=1}^{n} A_{ik} A_{kj}.$$ Every term $A_{ik}A_{kj}$ is $0$ or $1$, so the sum is zero iff every term is zero, i.e. for all $i,j,k$ it is never the case that $A_{ik} = 1$ and $A_{kj} = 1$. Equivalently: there is no index $k$ that is simultaneously the head of some edge ($A_{ik}=1$ for some $i$) and the tail of some edge ($A_{kj}=1$ for some $j$). (Beware the trap of arguing only through $\mathrm{rank}(A)$: it is true that $\mathrm{Col}(A)\subseteq\mathrm{Null}(A)$ forces $\mathrm{rank}(A)\le\lfloor n/2\rfloor$, but rank alone does not bound the number of $1$s -- a single rank-$1$ all-ones $2\times 3$ off-diagonal block already has $6$ ones, far more than its rank. The sharp constraint is the path/disjointness condition below, not the rank.)

*Step 2 -- The emitting and receiving sets are disjoint.* Define $$S = \{\,k : \text{row } k \text{ is nonzero}\,\} = \{k : \exists\, j,\ A_{kj} = 1\} \quad(\text{vertices that emit an edge}),$$ $$T = \{\,k : \text{column } k \text{ is nonzero}\,\} = \{k : \exists\, i,\ A_{ik} = 1\} \quad(\text{vertices that receive an edge}).$$ If some $k \in S \cap T$, then there exist $i$ with $A_{ik}=1$ and $j$ with $A_{kj}=1$, giving the term $A_{ik}A_{kj}=1$ in $(A^2)_{ij}$ -- contradicting $A^2=0$. Hence $$S \cap T = \varnothing, \qquad\text{so}\qquad |S| + |T| \le n.$$

*Step 3 -- Upper bound on the number of $1$s.* Every $1$ of $A$ sits in some row $k\in S$ (its row is nonzero) and some column $\ell\in T$ (its column is nonzero); that is, all $1$s lie inside the $S\times T$ submatrix, which has exactly $|S|\,|T|$ entries. Therefore $$\#\{1\text{s in }A\} \;\le\; |S|\,|T| \;\le\; \left(\frac{|S|+|T|}{2}\right)^{2} \le \left(\frac{n}{2}\right)^2,$$ by AM-GM. Since the count is an integer and $|S|+|T|\le n$, the maximum of $|S|\,|T|$ over integers with $|S|+|T|\le n$ is attained at $|S|=\lfloor n/2\rfloor,\ |T|=\lceil n/2\rceil$, giving $$\#\{1\text{s}\} \;\le\; \left\lfloor \frac{n}{2} \right\rfloor \left\lceil \frac{n}{2} \right\rceil = \left\lfloor \frac{n^2}{4} \right\rfloor.$$

*Step 4 -- Matching construction.* Let $m = \lfloor n/2 \rfloor$. Define the $n \times n$ matrix $$A = \begin{pmatrix} 0 & J \\ 0 & 0 \end{pmatrix},$$ where $J$ is the $m \times (n - m)$ all-ones matrix and the zero blocks have the appropriate sizes. Then:

• $A$ has entries in $\{0,1\}$ and exactly $m(n - m) = \lfloor n^2/4 \rfloor$ ones.
• $A^2 = 0$: the only nonzero block is the top-right $J$, and multiplying it by the corresponding (bottom) rows of $A$, which are all zero, gives $J\cdot 0 = 0$; all other block products vanish. (Combinatorially: $S = \{1,\dots,m\}$ emit only into $T = \{m+1,\dots,n\}$, and the vertices in $T$ emit nothing, so no edge can be continued -- no length-two path exists.)

Thus the bound is tight. For $n = 6$, $m = 3$: a $3\times 3$ all-ones block in the top-right corner gives $9$ ones with $A^2 = 0$.

Answer: The maximum number of $1$s is $\lfloor n^2 / 4 \rfloor$, achieved by an all-ones $\lfloor n/2\rfloor \times \lceil n/2\rceil$ block placed off-diagonal (emitting rows mapping into disjoint receiving columns) in an otherwise zero matrix. For $n=6$ this maximum is $\lfloor 36/4\rfloor = 9$.