0
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ Looks like oeis.org/A002620 $\endgroup$
    – RobPratt
    Oct 16 '20 at 1:16
  • 1
    $\begingroup$ 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$. $\endgroup$ Oct 16 '20 at 1:30
  • $\begingroup$ Sorry you're right. It is not 4. It is n/2. $\endgroup$
    – arke
    Oct 16 '20 at 3:44
2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ This is not just a lower bound; you have solved the problem. $\endgroup$ Oct 16 '20 at 2:12
  • $\begingroup$ I had only proved the lower bound, but now I added a proof of the upper bound. $\endgroup$
    – RobPratt
    Oct 16 '20 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.