any positive power of a matrix all of whose submatrices have odd determinant satisfies the same property Below is a question and solution that I'm trying to understand. My questions are shown below (under "let $\pi(i)$ be the $i$th number on the list).


Firstly, if $A$ is upper triangular with $1$'s on the diagonal, then any submatrix $(a_{ij})_{i,j\in S}$ has the same form because for any entry $a_{ij}$ for $j > i$, the entry will be zero in the submatrix as it was zero in $A$.


Permuting the columns and rows of $A$ by $\pi$ corresponds to permuting the rows and columns of the submatrices and thus doesn't affect their determinants (i.e. if rows $i$ and $j$ in $A$ are swapped, then any submatrices with entries in those rows has those rows swapped and likewise for swapping columns).


Here's my attempt at further justifying the claim that "in the expression of $\det(M)$ as a sum of signed products of entries of $M$, each corresponding to a permutation of $S$, there will be exactly two nonzero terms":

Suppose we have a permutation of entries of $M$ so that the corresponding signed product is nonzero.
If the permutation only has trivial cycles, it is the identity permutation. So there is at least one nontrivial cycle.Since k was minimal, the nontrivial cycle must have length k. Now we consider several possibilities when the k-cycle $C$ is not equal to $(i_1i_2\cdots i_k)$:
Case 1: $i_k$ maps to $i_a$ for some $a > 1$. Then $(i_ai_{a+1}\cdots i_k i_a)$ is a strictly shorter cycle.
Case 2: There exists $j < k$ so that $i_j$ does not map to $i_{j+1}$. This case seems significantly harder to deal with, so I was wondering if I could get some hints at least?

I think that the explicit procedure for constructing $\pi$ should also require that at each subsequent stage, list one element all of whose predecessors have already been listed.


Finally, how can one use $\pi$ to get the desired upper triangular form? Can someone explain with a formal proof (or at least some ideas) of why "using $\pi$" as such works?

 A: 
This case seems significantly harder to deal with, so I was wondering if I could get some hints at least?

Well, the hint is that it is not significantly harder; it is the same case, really. The $i_1,\ldots,i_k$ are "all the same" from the point of view of the original cycle, so if some argument works for $i_k$ then it should work for any $i_j$.

I think that the explicit procedure for constructing $\pi$ should also require that at each subsequent stage, list one element all of whose predecessors have already been listed.

This seems equivalent to the procedure written in the original text.

Finally, how can one use $\pi$ to get the desired upper triangular form? Can someone explain with a formal proof (or at least some ideas) of why "using $\pi$" as such works?

If $a_{ij} = 1$, then by the definition of $\pi$ we have $\pi(i) \leq \pi(j)$. This means that after permuting the columns and rows according to $\pi$, $a_{\pi(i)\pi(j)}$ will be on or above the main diagonal of the matrix. Since this is true for any $i,j$ with $a_{ij} = 1$, the resulting matrix is upper triangular.
Formally, let $\sigma$ denote the inverse of $\pi$. Then our new matrix will be $B = (b_{ij})_{ij}$, where $b_{ij} = a_{\sigma(i)\sigma(j)}$. The condition on $\pi$ can be equivalently stated as "if $a_{\sigma(i)\sigma(j)} = 1$, then $i \leq j$". Taking the contrapositive, we get "if $i > j$, then $a_{\sigma(i)\sigma(j)} = 0$".
But this is the same as saying that $B$ is upper triangular.
