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$.
Problem
Source: 2021 Simon Marais, A3
Tags: matrix, determinant, linear algebra
09.11.2021 19:50
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\}$.
20.11.2024 17:39
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.