Possible values of determinant of 0-1 matrices

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

Possible values of determinant of 0-1 matrices

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2021 Simon Marais, A3

The post below has been deleted. Click to close.

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

mathematics2004

82 posts

mathematics2004

#1 h Nov 2, 2021, 4:38 PM • 1 Y

Y by Tip_pay

Let $\mathcal{M}$ be the set of all $2021 \times 2021$ matrices with at most two entries in each row equal to $1$ and all other entries equal to $0$ .
Determine the size of the set $\{ \det A : A \in M \}$ .
Here $\det A$ denotes the determinant of the matrix $A$ .

Z K Y

The post below has been deleted. Click to close.

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

62 posts

#2 h Nov 9, 2021, 4:50 PM • 1 Y

Y by loup blanc

We introduce some more notations.
Let $\mathcal M_n$ be the set of all $n \times n$ matrices with at most two entries in each row equal to $1$ and all other entries equal to $0$ .
Let $D_n$ be the set $\{\det A: A \in \mathcal M_n\}$ .
Thus the problem asks for the size of $D_{2021}$ .
It is easy to see that $D_1 = \{0, 1\}$ and $D_2 = \{0, 1, -1\}$ .
Also for $n \geq 2$ , it is clear that $x \in D_n \iff -x \in D_n$ for any $x$ , by exchanging any two rows of a matrix.

For any $A \in \mathcal M_{n - 1}$ , the matrix $\begin{pmatrix}1 & \\ & A\end{pmatrix}$ belongs to $\mathcal M_n$ and has the same determinant as $A$ . This shows that $D_{n - 1} \subseteq D_n$ .

Let $A$ be a matrix in $\mathcal M_n$ such that $\det A \in D_n \setminus D_{n - 1}$ .
If there is one row of $A$ with no $1$ , then the determinant is $0$ , which is already in $D_{n - 1}$ , contradicting our assumption.
If there is one row of $A$ with only one $1$ , then removing the row and column containing that $1$ from $A$ will give a matrix in $\mathcal M_{n - 1}$ , which has the same determinant as $A$ . This means that $\det A$ belongs to $D_{n - 1}$ , contradicting our assumption.
It follows that each row of $A$ contains exactly two $1$ 's.

Similarly, if there is one column of $A$ with no $1$ or only one $1$ , then $\det A$ belongs to $D_{n - 1}$ , which is impossible.
As the total number of $1$ 's is equal to $2n$ , each column of $A$ also contains exactly two $1$ 's.

Moreover, we know that no two rows of $A$ are identical, otherwise the determinant would be zero.
Thus we have a simple graph, whose vertices are the columns of $A$ , and each row defines an edge connecting the two columns on which this row has a $1$ .
We have seen that each vertex of this graph has degree $2$ . Thus the graph is a disjoint union of several circles.
This means that, up to permutation of rows and columns, the matrix $A$ can be written as a block diagonal matrix, whose diagonal blocks are all of the form $\begin{pmatrix}1 & 1 & & \\& 1 & 1 & \\ & & \ddots & \ddots & \\ & & & 1 & 1\\1& & & & 1\end{pmatrix}.$ Note that each block has size at least $3 \times 3$ .
It is easy to see that for a block of size $k$ , the determinant of the block is $(-1)^k + 1$ , which is $0$ or $2$ according to whether $k$ is even or odd.
Thus all blocks are of odd size. That is, we can write $n = k_1 + \cdots + k_r$ with all $k_i \geq 3$ odd, and the determinant of $A$ is, up to sign, equal to $2^r$ .

We summerize the above discussion as follows: for $n \geq 2$ , we have $D_n = \{0, \pm 1\} \cup \bigcup_{m = 3}^n \{\pm 2^r: m = k_1 + \cdots + k_r, k_i \geq 3, 2\nmid k_i\}.$ From here, it is easy to see that $D_{2021} = \{0\} \cup \{\pm 2^r: 0 \leq r \leq 673\}$ .

Z K Y

The post below has been deleted. Click to close.

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

stanislavssss2025

1 post

stanislavssss2025

#3 h Nov 20, 2024, 2:39 PM

Y by

I believe, you are wrong. 2021 is divided into blocks of size at least 3. If one of the blocks is of even parity, the whole thing is zero. Thus consider when all k are odd. But then, it is not true that number of blocks can be any value from 0 to 673.

It can't be any even value, as then we have even number of odd blocks = 2021, which can't be true. However, we can show that any odd number of blocks can be achieved. Indeed, substract 1 from the length of each block. Now they are all even, and all >= 2. And 2021 turns into 2021-odd = even number. And it is obvious, that we can achieve any even number as a sum of even numbers >= 2 (Just take all 2's and one number of what's left). Thus, the correct answer is 0 and +- 2^(2r+1), where r goes from 0 to (673-1)/2 = 336.

Z K Y

The post below has been deleted. Click to close.

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

62 posts

#4 h May 27, 2025, 7:40 PM

Y by

stanislavssss2025 wrote:

I believe, you are wrong.

Note that $D_n$ also contains $D_{n - 1}$ . The division into blocks is only relevant for those in $D_n \backslash D_{n - 1}$ .

Z K Y

The post below has been deleted. Click to close.

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

3616 posts

#5 h May 30, 2025, 1:56 PM

Y by

The key of the Isolemma's proof is "We have seen that each vertex of this graph has degree $2$ . Thus the graph is a disjoint union of several circles."
cf here
https://math.stackexchange.com/questions/3749686/let-g-be-a-graph-such-that-all-its-vertices-have-degree-2-prove-that-g-is-a
In fact, the elements of ${D_n}^{+}=\{x\in D_n;x\geq 2\}$ are generated by the block diagonal matrices containing some of the following matrices on its diagonal:
$I_k$ , $I_l+P_l$ -where $l\geq 3$ and $P_l$ is the matrix of the cycle $(1,l,l-1,\cdots,2,1)$ - .
For example, if $n=11$ :
$I_3+P_3,I_8$ gives $2$
$I_3+P_3,I_3+P_3,I_5$ gives $4$
$I_3+P_3,I_3+P_3,I_3+P_3,I_2$ gives $8$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a