## A fact about the invariant factors of a matrix

Let $A$ be an $n \times n$ matrix over a field $F$.

Let $1 \leq k \leq n$, and let $s,t : k \rightarrow n$ be injective, monotone functions. (That is, $1 < s_1 < s_2 < \ldots < s_k < n$.) The $(s,t)$-minor of $A$, denoted $(A)_{s,t}$, is the $k \times k$ matrix whose $(i,j)$ entry is the $(s_i,t_j)$ entry of $A$. We will call such $s$ and $t$ crunchy.

Let $d_k(xI-A)$ be the unique monic generator in $F[x]$ of the ideal $H_k(xI-A) = (\mathsf{det}\ (xI-A)_{s,t} \ |\ s,t\ \mathrm{crunchy\ on}\ k)$.

Now suppose $S$ is the Smith normal form of $xI-A$, and that the diagonal entries of $S$ are $D_i$. Prove that $D_i = d_i/d_{i-1}$, taking $d_0 = 1$.

(Setting $d_0 = 1$ is in fact the proper thing to do. Think of a matrix as a function from $n^2$ to $F$; then if $n = 0$, this function is empty. Now $S_0 = 1$, and in the formula $\mathsf{det}\ A = \sum_{\sigma \in S_0} \varepsilon(\sigma) \prod_{i=1}^0 a_{\sigma(i),i}$, the empty product is 1, and we have one summand. So the ideal in $F[x]$ is $(1)$.)

[I consulted these notes by Gregg Musiker for this problem.]

We begin by arguing that $d_k(A) = d_k(EA)$, where $E$ is an elementary matrix. (We discussed elementary matrices previously.) Recall that left multiplication by an elementary matrix corresponds to one of the three elementary row operations. Let $s$ and $t$ be crunchy, and let $S = \mathsf{im}\ s$ and $T = \mathsf{im}\ t$.

Suppose $E$ interchanges rows $i$ and $j$.

1. If $i,j \notin S$, then $(EA)_{s,t} = (A)_{s,t}$, and so $\mathsf{det}\ (EA)_{s,t} = \mathsf{det}\ (A)_{s,t}$.
2. If $i,j \in S$, then $(EA)_{s,t}$ is obtained from $(A)_{s,t}$ by interchanging rows $s^{-1}(i)$ and $s^{-1}(j)$. So we have $(EA)_{s,t} = E^\prime (A)_{s,t}$ for some row-swapping elementary matrix $E^\prime$, and thus $\mathsf{det}\ (EA)_{s,t} = -\mathsf{det}\ \mathsf{det}\ (A)_{s,t}$.
3. Suppose $i \in S$ and $j \notin S$. Now let $s^\prime$ be the (unique) crunchy function whose image is $S$ with $i$ replaced by $j$. Now $(EA)_{s,t}$ is obtained from $(A)_{s^\prime,t}$ by swapping some rows. So $(EA)_{s,t} = E^\prime(A)_{s^\prime,t}$, where $E^\prime$ is some product of row-swapping elementary matrices, and we have $\mathsf{det}\ (EA)_{s,t} = (-1)^p \mathsf{det}\ (A)_{s^\prime,t}$ for some $p$.

Thus we have $H_k(A) = H_k(EA)$, and so $d_k(A) = d_k(EA)$.

Now suppose $E$ multiplies row $i$ by a field element $\alpha$.

1. If $i \notin S$, then $(EA)_{s,t} = (A)_{s,t}$, and so $\mathsf{det}\ (EA)_{s,t} = \mathsf{det}\ (A)_{s,t}$.
2. If $i \in S$, then $(EA)_{s,t}$ is obtained from $(A)_{s,t}$ by multiplying row $s^{-1}(i)$ by $\alpha$. So we have $\mathsf{det}\ (EA)_{s,t} = \alpha \mathsf{det}\ (A)_{s,t}$.

Thus we have $H_k(A) = H_k(EA)$, and so $d_k(A) = d_k(EA)$.

Finally, suppose $E$ adds $\alpha$ times row $j$ to row $i$.

1. If $i \notin S$, then $(EA)_{s,t} = (A)_{s,t}$, and so $\mathsf{det}\ (EA)_{s,t} = \mathsf{det}\ (A)_{s,t}$.
2. If $i \in S$ and $j \in S$, then $(EA)_{s,t}$ is obtained from $(A)_{s,t}$ by adding a multiple of row $s^{-1}(j)$ to row $s^{-1}(i)$. So $(EA)_{s,t} = E^\prime(A)_{s,t}$ for some row-adding elementary matrix $E^\prime$, and we have $\mathsf{det}\ (EA)_{s,t} = \mathsf{det}\ (A)_{s,t}$.
3. Suppose $i \in S$ and $j \notin S$. Now $(EA)_{s,t}$ is obtained from $(A)_{s,t}$ by adding some unrelated row vector to row $s^{-1}(i)$. In particular, we have $\mathsf{det}\ (EA)_{s,t} = \sum_{\sigma \in S_k} \varepsilon(\sigma) \prod_{\ell=1}^k (a_{s(\ell), \sigma^{-1}(s(\ell))} + \delta_{i,s(\ell)} \alpha a_{j,\sigma^{-1}(s(\ell)})$ $= \mathsf{det}\ (A)_{s,t} + \mathsf{det}\ (E^\prime A)_{s,t}$, where $E^\prime$ is a product of two elementary matrices; one which swaps rows $i$ and $j$, and one which multiplies the (new) $i$th row by $\alpha$. We’ve already seen that $\mathsf{det}\ (E^\prime A)_{s,t}$ is a unit multiple of $\mathsf{det}\ (A)_{s,t}$.

Thus we have $H_k(A) = H_k(EA)$, and so $d_k(A) = d_k(EA)$.

So for any elementary matrix $E$, $d_k(EA) = d_k(A)$. Now note that $(A)_{s,t}^\mathsf{T} = (A^\mathsf{T})_{t,s}$, so that $d_k(A^\mathsf{T}) = d_k(A)$. So we also have $d_k(AE) = d_k(A)$ for elementary matrices $E$.

By Theorem 21 in D&F, we have $P(xI-A)Q = S$ in Smith Normal Form, where $P$ and $Q$ are products of elementary matrices. In particular, $d_k(xI-A) = d_k(S)$.

Now we claim that $d_k(S)/d_{k-1}(S) = D_k(S)$.

Claim: If $t \neq s$, then $\mathsf{det}\ (S)_{s,t} = 0$. To see this, Note that if we remove some row from a diagonal matrix, then the result has a zero column. Unless we also remove the corresponding column, the determinant is 0.

Now suppose $s$ is crunchy on $k$. By the divisibility condition on the diagonal entries of $S$, we have $S_{i,i} | S_{s(i),s(i)}$ for all $i$. In particular, the determinant of the $k \times k$ minor with $s(i) = i$ for $1 \leq i \leq k$ divides the determinant of every other $k \times k$ minor. So $d_k(S) = \prod_{i=1}^k D_i(S)$, and $d_k/d_{k-1} = D_k$ follows.