Can a 0-1 matrix square to the matrix with all ones?

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Can a 0-1 matrix square to the matrix with all ones?

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: IMC 2024, Problem 3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

9044 posts

#1 h Aug 7, 2024, 12:41 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pi_quadrat_sechstel

603 posts

pi_quadrat_sechstel

#2 h Aug 7, 2024, 1:08 PM

Y by

Tintarn wrote:

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

$A^2$ has $n-1$ times the eigenvalue 0 and the eigenvalue $n$ . So the charaterisric polynomial of $A$ must be $X^{n-1}(X\pm\sqrt{n})$ . This is only for $n=m^2$ an integer polynomial.

Let $0\leq k\leq n-1$ and let $M_k$ be the $m\times m$ -matrix with entries $(m_k)_{ij}=\begin{cases}1&i\equiv j+l\pmod{m}\\0&\mathrm{else}\end{cases}$ . We can choose $A$ as the block-matrix $A=\begin{pmatrix}M_0&M_0&M_0&\cdots&M_0\\ M_1&M_1&M_1&\cdots&M_1\\ M_2&M_2&M_2&\cdots&M_2\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ M_{m-1}&M_{m-1}&M_{m-1}&\cdots&M_{m-1}\end{pmatrix}$ .

This post has been edited 2 times. Last edited by pi_quadrat_sechstel, Aug 7, 2024, 2:08 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

9044 posts

#3 h Aug 7, 2024, 1:26 PM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

51 posts

#5 h Apr 23, 2025, 9:30 AM

Y by

A totally different proof

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3598 posts

#6 h Apr 23, 2025, 5:47 PM

Y by

The only difficulty is to find a matrix for each admissible value of $m^2$ .
Using the form found by @pi_quadrat_sechst, that follows is a simple solution:
let $Z=[0,\cdots,0]^T,V=[1,\cdots,1]^T\in \{0,1\}^m$ ; then put
$M_0=[V,Z,\cdots,Z],M_1=[Z,V,Z,\cdots,Z],....,M_{m-1}=[Z,\cdots,Z,V]$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a