Let $\mathcal{O}$ be the set of $n\times n$ matrices with integer entries so that for every nonempty subset $S$ of $\{1,2,\cdots, n\}$, the $|S|$ by $|S|$ submatrix $(a_{ij})_{i,j \in S}$ has odd determinant. Prove that if $A\in\mathcal{O}$, then for every $b\ge 1, A^b \in \mathcal{O}$.
I know it suffices to work with matrices over the field of two elements since only parity matters for the determinant.
Why is it true that if there exists a permutation matrix $P$ so that $P^{-1} AP$ is unipotent (i.e. has 1s on the main diagonal and 0s below it), then $A\in\mathcal{O}$?
Is it true that any principal submatrix of $A$ is conjugate to a principal submatrix of $P^{-1} AP$ and if so, why?
Since $P^{-1} AP$ is unipotent implies that $(P^{-1} AP)^k$ is unipotent, it suffices to show that for any element $A$ of $\mathcal{O}$, there exists a permutation matrix $P$ so that $P^{-1} AP$ is unipotent.
Let the $(i,j)$th element of $A$ be $a_{ij}$. To show that such a permutation matrix exists, let $S = \{i\}$ to see that $a_{ii}=1$. Form a directed graph on the vertex set $\{1,\cdots, n\}$ with an edge from $i$ to $j$ whenever $a_{ij} = 1$ and claim the graph has no cycles. This can be seen because if there was a cycle $i_1, i_2,\cdots, i_c$ of minimal length, then $a_{i_j i_k} = \begin{cases}1,&\text{ if $k-j\equiv 0,1 \mod c$ }\\ 0,&\text{ otherwise}\end{cases}$ (if $a_{i_j i_k} = 1$ and $k-j\not\equiv 0, 1\mod m$, then we can assume WLOG that $j < k$ and delete the edges in between $i_j$ and $i_k$, which yields a contradiction as there must be at least one edge between $i_j$ and $i_k$). But then note that the row sum of the submatrix corresponding to $S=\{i_1,\cdots, i_m\}$ is $0$ (in the field of 2 elements, $0$ and $1$), which contradicts the fact that $S$ must be nonzero by hypothesis.
We proceed by induction on $n$ where the base case $n=1$ follows from above. Since the directed graph has no cycles, there must be some vertex $i$ that is not the starting point of any edge (i.e. has outdegree zero), and this can be proven using the Pigeonhole principle and the finiteness of the directed graph.
By the inductive hypothesis, there exists a permutation matrix $P$ so that the submatrix $A'$ corresponding to $S=\{1,\cdots, n\}\backslash \{i\}$ satisfies that $P^{-1}A'P$ is unipotent. But how can I obtain a permutation matrix $P_2$ from this one that makes $P_2^{-1} AP_2$ unipotent? I know that by the definition of the directed graph, since vertex $i$ has outdegree zero, there is no entry $a_{ji}$ equal to $1$.