International Mathematics Competition
for University Students
2024

IMC2024: Day 1, Problem 3

Problem 3. For which positive integers \(\displaystyle n\) does there exist an \(\displaystyle n\times n\) matrix \(\displaystyle A\) whose entries are all in \(\displaystyle \{0,1\}\), such that \(\displaystyle A^2\) is the matrix of all ones?

Alex Avdiushenko, Neapolis University Paphos, Cyprus

Solution. Answer: Such a matrix \(\displaystyle A\) exists if and only if \(\displaystyle n\) is a complete square.

Let \(\displaystyle J_n\) be the \(\displaystyle n\times n\) matrix with all ones, so \(\displaystyle A^2=J_n\). Consider the equality

\(\displaystyle A^3 = AJ_n = J_nA. \)

In the matrix \(\displaystyle AJ_n\), all columns are equal to the sum of colums in \(\displaystyle A\), that is, the \(\displaystyle (i,j)\)th entry in \(\displaystyle AJ_n\) is the number of ones in the \(\displaystyle i\)th row of \(\displaystyle A\). Similarly, the \(\displaystyle (i,j)\)th entry in \(\displaystyle J_nA\) is the number of ones in the \(\displaystyle j\)th column of \(\displaystyle A\). These numbers must be equal, so \(\displaystyle A\) contains the same number of ones in every row and column. Let this common number be \(\displaystyle k\); then \(\displaystyle AJ_n=J_nA=kJ_n\).

Now from

\(\displaystyle nJ_n = J_n^2 = (A^2)^2 = A(AJ_n) = A(kJ_n) = k(AJ_n)=k^2J_n \)

we can read \(\displaystyle n=k^2\), so \(\displaystyle n\) must be a complete square.

It remains to show an example for a matrix \(\displaystyle A\) of order \(\displaystyle n=k^2\). For \(\displaystyle l=0,1,\ldots,k-1\), let \(\displaystyle B_l\) be the \(\displaystyle k\times k\) matrix whose \(\displaystyle (i,j)\)th entry is \(\displaystyle 1\) if \(\displaystyle j-i\equiv l\pmod{k}\) and \(\displaystyle 0\) otherwise, i.e., \(\displaystyle B_l\) can be obtained from the identity matrix by cyclically shifting the colums \(\displaystyle l\) times, and let

\(\displaystyle A = \begin{pmatrix} B_0 & B_1 & B_2 & \ldots & B_{k-1} \\ B_0 & B_1 & B_2 & \ldots & B_{k-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ B_0 & B_1 & B_2 & \ldots & B_{k-1} \\ \end{pmatrix}; \)

Due to \(\displaystyle B_lB_m=B_{l+m}\), this matrix satisfies \(\displaystyle A^2=J_{k^2}\).