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 $\{\operatorname{det} A: A \in \mathcal{M}\}$.
Here $\operatorname{det} A$ denotes the determinant of the matrix $A$.
Let $D$ be the set of possible determinants. We claim that
$$
D=\left\{0, \pm 2^{0}, \pm 2^{1}, \pm 2^{2}, \pm 2^{3}, \ldots, \pm 2^{673}\right\}
$$
so the number of possibilities is $2 \times 674+1=1349$.
To prove this we may argue as follows. First note that the determinant is clearly an integer and if $d \in D$, then by exchanging any two rows we have $-d \in D$. So take such a $2021 \times 2021$ matrix and let us consider the absolute value of its determinant.

If there is a row with zero $1 \mathrm{~s}$, then the determinant is 0 . Otherwise, successively remove rows with one 1 , along with the column containing that 1 . By Laplace expansion, we obtain a matrix with the same determinant, up to sign. It is possible that we end up with a $1 \times 1$ matrix whose determinant is 0 or 1 . Otherwise, we have a matrix that has two $1 \mathrm{~s}$ in each row.

Now interpret each column of the resulting matrix as a vertex of a graph and each row as an edge between the vertices whose corresponding columns contain 1s. The graph cannot have loops, but can have multiple edges. If there is an isolated vertex in this graph, then the matrix has a column of 0 s and hence the determinant is 0 . Otherwise, remove all degree 1 vertices and their adjacent edges. This corresponds to applying Laplace expansion down a column with one 1 and produces a matrix with the same determinant, up to sign.

The resulting graph has $n$ vertices and $n$ edges for $n \leq 2021$, without any degree 0 or degree 1 vertices. Since the sum of the degrees is twice the number of edges, it must be the case that every vertex has degree 2. Therefore the graph is a disjoint union of cycles. This means that the rows and columns of the corresponding matrix can be permuted to give a block diagonal structure, with each block corresponding to a component of the graph. We may do this in such a way that each block is a matrix $J_{m}$ for some integer $m \geq 2$, where the $(i, i)$ and $(i, i+1)$ entries are 1 (with indices taken modulo $m$ ) and the remaining entries are 0 .

The determinant of $J_{m}$ is 0 for $m$ even, since the sum of the even rows is equal to the sum of the odd rows. The determinant of $J_{m}$ is 2 for $m$ odd, by Laplace expansion down
the first column. The two minors involved in this Laplace expansion are upper triangular matrices with 1 s along the diagonal, and $m$ being odd ensures that they contribute with the same sign.

It follows that the absolute value of the determinant is 0 if the graph contains any even cycles, and otherwise it is 2 to the power of the number of cycles in the graph. Odd cycles must have length at least 3 , so since $2021=3 \times 673+2$ there can be at most 673 of them. For $0 \leq k \leq 673$ we may obtain a matrix with determinant $2^{k}$ by taking $k$ blocks equal to $J_{3}$ and placing $1 \mathrm{~s}$ in the remaining diagonal entries, and this completes the proof.