Notes - Rings and Modules HT24, Smith normal form


Flashcards

Can you state the “Smith normal form” theorem?


Suppose:

  • $R$ is a Euclidean domain
  • $A \in \text{Mat} _ {n,m}(R)$

Then:

  • $A \sim D _ k$, where $k = \min(n, m)$ and
\[D_k = \begin{bmatrix} d_1 & 0 & \cdots & 0 & \cdots & 0 \\\\ 0 & d_2 & \ddots & \vdots & \cdots & 0 \\\\ \vdots & \ddots & \ddots & 0 & \cdots & 0 \\\\ 0 & \cdots & 0 & d_k & \cdots & 0 \\\\ \vdots & \vdots & \vdots & \vdots & \cdots & 0 \\\\ 0 & 0 & \cdots & 0 & \cdots & 0 \end{bmatrix}\]
  • and $d _ i \mid d _ {i + 1}$ for all $i$.

($A \sim D _ k$ means they are equivalent in the sense that $D _ k = PAQ$ where $P \in \text{Mat} _ {n, n}(R)$ and $Q \in \text{Mat} _ {m, m}(R)$).

Quickly prove the “Smith normal form” theorem, i.e. that if

  • $R$ is a Euclidean domain
  • $A \in \text{Mat} _ {n,m}(R)$

then

  • $A \sim D _ k$, where $k = \min(n, m)$ and
\[D = \begin{bmatrix} d_1 & 0 & \cdots & 0 & \cdots & 0 \\\\ 0 & d_2 & \ddots & \vdots & \cdots & 0 \\\\ \vdots & \ddots & \ddots & 0 & \cdots & 0 \\\\ 0 & \cdots & 0 & d_k & \cdots & 0 \\\\ \vdots & \vdots & \vdots & \vdots & \cdots & 0 \\\\ 0 & 0 & \cdots & 0 & \cdots & 0 \end{bmatrix}\]
  • and $d _ i \mid d _ {i + 1}$ for all $i$.

We aim to prove the statement that given $A$ we can find a square matrix equivalent to $A$ which is of the form

\[B = \begin{bmatrix} b_{11} & 0 & \cdots & 0 \\\\ 0 & b_{22} & \cdots & b_{2m} \\\\ \vdots & \vdots & \ddots & \vdots \\\\ 0 & b_{n2} & \cdots & b_{nm} \end{bmatrix}\]

where $b _ {11}$ divides all the entries $b _ {ij}$ in the matrix. If we prove this, then the overall result follows as we can use induction on the size of the matrix by working with the submatrix $\hat B$, where we divide through the submatrix by $b _ {11}$.

To prove this lemma, we use induction on the “norm” of the matrix, which we define as

\[N(A) := \min_{a_{ij} \ne 0} N(a_{ij})\]

(where using a norm function on the entries is justified since $R$ is a Euclidean domain). By using column and row swaps, we may assume that initially (call this LEAD).

\[N(A) = N(a_{11})\]

The steps to then reduce into the $B$ form are as follows:

  • REDUCE: If any $a _ {i1}$ or $a _ {1j}$ is not divisible by $a _ {11}$, say $a _ {i1}$, then we can apply the division algorithm to get $a _ {i1} = q _ {i1}a _ {11} + r _ {i1}$ and then subtracting $q _ {i1}$ lots of row $1$ from row $i$, we get a new entry with a smaller norm than $a _ {11}$, so we are done by induction.
  • CLEAR: If all the $a _ {i1}$s and $a _ {1j}$s are divisible by $a _ {11}$, then we can subtract multiples of the first row / column to clear the entries in the first row and column.
  • DIVIDE: Now we have transformed $A$ into a matrix similar to the required form, but we might have some entry not divisible by $a _ {11}$. We can add the row corresponding to this entry to row $1$, and then we are in step $1$ again (since we can now reduce this top entry to one with a smaller norm than $a _ {11}$, and apply the inductive hypothesis).

LEAD, REDUCE, CLEAR, DIVIDE.




Related posts