IMC 2024 · Day 1 · P3

Hint: Let $J$ be the $n \times n$ matrix with all ones. Consider $A^3 = AJ = JA$.

Answer: Such a matrix $A$ exists if and only if $n$ is a complete square.

Let $J_n$ be the $n \times n$ matrix with all ones, so $A^2 = J_n$. Consider the equality $$A^3 = A J_n = J_n A.$$ In the matrix $A J_n$, all columns are equal to the sum of colums in $A$, that is, the $(i,j)$th entry in $A J_n$ is the number of ones in the $i$th row of $A$. Similarly, the $(i,j)$th entry in $J_n A$ is the number of ones in the $j$th column of $A$. These numbers must be equal, so $A$ contains the same number of ones in every row and every column. Let this common number be $k$; then $A J_n = J_n A = k J_n$.

Now from $$n J_n = J_n^2 = (A^2)^2 = A (A J_n) = A (k J_n) = k (A J_n) = k^2 J_n$$ we can read $n = k^2$, so $n$ must be a complete square.

It remains to show an example for a matrix $A$ of order $n = k^2$. For $l = 0, 1, \dots, k-1$, let $B_l$ be the $k \times k$ matrix whose $(i,j)$th entry is 1 if $j - i \equiv l \pmod k$ and 0 otherwise, i.e., $B_l$ can be obtained from the identity matrix by cyclically shifting the colums $l$ times, and let $$A = \begin{pmatrix} B_0 & B_1 & B_2 & \dots & B_{k-1} \\ B_0 & B_1 & B_2 & \dots & B_{k-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ B_0 & B_1 & B_2 & \dots & B_{k-1} \end{pmatrix};$$ The $(i,j)$th block in $A^2$ is $$\begin{pmatrix} B_0 & B_1 & \dots & B_{k-1} \end{pmatrix} \begin{pmatrix} B_{j-1} \\ \vdots \\ B_{j-1} \end{pmatrix} = (B_0 + B_1 + \dots + B_{k-1}) B_{j-1} = J_k B_{j-1} = J_k,$$ so this matrix indeed satisfies $A^2 = J_{k^2}$.