08 - Smith Normal Form

Smith Normal Form

Let $R$ be a Euclidean Domain
Let $A\in {\mathrm{Mat}}_{n,m}(R)$ be a matrix then

$A$ is ERC Equivalent (and hence equivalent) to diagonal matrix $D$ where if $k=\min \{m,n\}$ then

$$D=\left(\begin{array}{cccc}{d}_1& 0& \cdots & 0\\ 0& d_2& \ddots & 0\\ ⋮& \ddots & \ddots & 0\\ 0& \cdots & 0& d_k\\ ⋮& ⋮& & ⋮\\ 0& 0& \cdots & 0\end{array}\right)$$

where each successive $d_i$ divides the next

Sequence of elements $(d_1,d_2,\cdots ,d_k)$ is unique up to units

Proof

Claim that using row and column operations matrix is equivalent to $A$ in form

$$B=\left(\begin{array}{cccc}{b}_{11}& 0& \cdots & 0\\ 0& b_{22}& \cdots & b_{2m}\\ ⋮& ⋮& \ddots & ⋮\\ 0& b_{n2}& \cdots & b_{nm}\end{array}\right)$$

where $b_{11}$ divides all entries $b_{ij}$ in matrix

Factoring out $b_{11}$ from each entry then apply induction on $n$ to submatrix

$$B^{\prime }={\left(\frac{b_{ij}}{b_{11}}\right)}_{i,j\ge 2}$$

to get result

To prove claim, use induction on $N(A)=\min \{N(a_{ij}):1\le i\le n,1\le j\le m\}$

1. If any$a_{i1}$ or $a_{1j}$ are not divisible by $a_{11}$ then

$$a_{i1}=q_{i1}{a}_{11}+r_{i1}$$

So take $q_{i1}$ times row $1$ from row $i$ to get new matrix $A^{\prime }$ with entry $r_{i1}$ and

$$N(A_1)\le N(r_{i1})<N(a_{11})=n(A)$$

Hence done by induction

2. If all $a_{i1}$ and $a_{1j}$ s are divisible by $a_{11}$ then
   Subtract appropriate multiplies of first row from other rows to get matrix $A_2$
   So all entries in first column below $a_{11}$ equal zero
   Similarly using column operations then
   Get $A_3$ with all entries on first row after $a_{11}$ equal zero

3. Hence $A_3$ has required except possibly having entry not divisible by $a_{11}$
   Otherwise let $(A_3)=(a_{ij}^3)$
   If $a_{ij}^3$ is not divisible by $a_{11}$ then add row $i$ of $A_3$ to row $1$ to get matrix $A_4$
   Hence at situation of step $1$ and done by induction