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
- 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.