Putnam 2021, Problem B-5

Say that an $n$-by-$n$ matrix $A = (a_{ij})_{1 \leq i,j \leq n}$ with integer entries is very odd if, for every nonempty subset $S$ of $\{1,2,\ldots,n\}$, the $|S|$-by-$|S|$ submatrix $(a_{ij})_{i,j \in S}$ has odd determinant. Prove that if $A$ is very odd, then $A^k$ is very odd for every $k \geq 1$.

Solution:
For convenience, throughout we work with matrices over the field of 2 elements. In this language, if there exists a permutation matrix $P$ such that $P^{-1}AP$ is unipotent (i.e., has 1s on the main diagonal and 0s below it), then $A$ is very odd: any principal submatrix of $A$ is conjugate to a principal submatrix of $P^{-1}AP$, which is again unipotent and in particular nonsingular. We will solve the problem by showing that conversely, for any very odd matrix $A$, there exists a permutation matrix $P$ such that $P^{-1}AP$ is unipotent. Since the latter condition is preserved by taking powers, this will prove the desired result.

To begin, we may take $S = \{i\}$ to see that $a_{ii} = 1$. We next form a (loopless) directed graph on the vertex set $\{1, \ldots, n\}$ with an edge from $i$ to $j$ whenever $a_{ij} = 1$, and claim that this graph has no cycles. To see this, suppose the contrary, choose a cycle of minimal length $m \geq 2$, and let $i_1, \ldots, i_m$ be the vertices in order. The minimality of the cycle implies that
$$a_{i_ji_k} = \begin{cases} 1 & \text{if } k-j \equiv 0 \text{ or } 1 \pmod{m} \\ 0 & \text{otherwise.} \end{cases}$$

The submatrix corresponding to $S = \{i_1, \ldots, i_m\}$ has row sum 0 and hence is singular, a contradiction.

We now proceed by induction on $n$. Since the directed graph has no cycles, there must be some vertex which is not the starting point of any edge (e.g., the endpoint of any path of maximal length). We may conjugate by a permutation matrix so that this vertex becomes 1. We now apply the induction hypothesis to the submatrix corresponding to $S = \{2, \ldots, n\}$ to conclude.

**Remark.** A directed graph without cycles, as in our solution, is commonly called a DAG (directed acyclic graph). It is a standard fact that a directed graph is a TAG if and only if there is a linear ordering of its vertices consistent with all edge directions. See for example https://en.wikipedia.org/wiki/Directed_acyclic_graph.