Smith normal form
This topic gives a version of the Gauss elimination algorithm for a commutative^{} principal ideal domain^{} which is usually described only for a field.
Let $A\ne 0$ be a $m\times n$matrix with entries from a commutative principal ideal domain $R$. For $a\in R\setminus \{0\}$ $\delta (a)$ denotes the number of prime factors^{} of $a$. Start with $t=1$ and choose ${j}_{t}$ to be the smallest column index of $A$ with a nonzero entry.
 (I)

If ${a}_{t,{j}_{t}}=0$ and ${a}_{k,{j}_{t}}\ne 0$, exchange rows 1 and $k$.
 (II)

If there is an entry at position $(k,{j}_{t})$ such that ${a}_{t,{j}_{t}}\nmid {a}_{k,{j}_{t}}$, then set $\beta =\mathrm{gcd}({a}_{t,{j}_{t}},{a}_{k,{j}_{t}})$ and choose $\sigma ,\tau \in R$ such that
$$\sigma \cdot {a}_{t,{j}_{t}}\tau \cdot {a}_{k,{j}_{t}}=\beta .$$ By leftmultiplication with an appropriate matrix it can be achieved that row 1 of the matrix product^{} is the sum of row 1 multiplied by $\sigma $ and row $k$ multiplied by $(\tau )$. Then we get $\beta $ at position $(t,{j}_{t})$, where $$. Repeating these steps one obtains a matrix having an entry at position $(t,{j}_{t})$ that divides all entries in column ${j}_{t}$.
 (III)

Finally, adding appropriate multiples^{} of row $t$, it can be achieved that all entries in column ${j}_{t}$ except for that at position $(t,{j}_{t})$ are zero. This can be achieved by leftmultiplication with an appropriate matrix.
Applying the steps described above to the remaining nonzero columns of the resulting matrix (if any), we get an $m\times n$matrix with column indices ${j}_{1},\mathrm{\dots},{j}_{r}$ where $r\le \mathrm{min}(m,n)$, each of which satisfies the following:

1.
the entry at position $(l,{j}_{l})$ is nonzero;

2.
all entries below and above position $(l,{j}_{l})$ as well as entries left of $(l,{j}_{l})$ are zero.
Furthermore, all rows below the $r$th row are zero.
Now we can reorder the columns of this matrix so that elements on positions $(i,i)$ for $1\le i\le r$ are nonzero and $\delta ({a}_{i,i})\le \delta ({a}_{i+1,i+1})$ for $$; and all columns right of the $r$th column (if present) are zero. For short set ${\alpha}_{i}$ for the element at position $(i,i)$. $\delta $ has nonnegative integer values; so $\delta ({\alpha}_{1})=0$ is equivalent^{} to ${\alpha}_{1}$ being a unit of $R$. $\delta ({\alpha}_{i})=\delta ({\alpha}_{i+1})$ can either happen if ${\alpha}_{i}$ and ${\alpha}_{i+1}$ differ by a unit factor, or if they are relatively prime. In the latter case one can add column $i+1$ to column $i$ (which doesn’t change ${\alpha}_{i})$ and then apply appropriate row manipulations to get ${\alpha}_{i}=1$. And for $$ and ${\alpha}_{i}\nmid {\alpha}_{i+1}$ one can apply step (II) after adding column $i+1$ to column $i$. This diminishes the minimum $\delta $values for nonzero entries of the matrix, and by reordering columns etc. we end up with a matrix whose diagonal elements ${\alpha}_{i}$ satisfy $$.
Since all row and column manipulations involved in the process are , this shows that there exist invertible^{} $m\times m$ and $n\times n$matrices $S,T$ so that $SAT$ is
$$\left[\begin{array}{cccc}\hfill {\alpha}_{1}\hfill & \hfill 0\hfill & \hfill \mathrm{\dots}\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill {\alpha}_{2}\hfill & \hfill \mathrm{\dots}\hfill & \hfill 0\hfill \\ \hfill \mathrm{\vdots}\hfill & \hfill \mathrm{\vdots}\hfill & \hfill \mathrm{\ddots}\hfill & \hfill \mathrm{\vdots}\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill \mathrm{\dots}\hfill & \hfill {\alpha}_{r}\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill \mathrm{\dots}\hfill & \hfill 0\hfill \\ \hfill \mathrm{\vdots}\hfill & \hfill \mathrm{\vdots}\hfill & \hfill \mathrm{\dots}\hfill & \hfill \mathrm{\vdots}\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill \mathrm{\dots}\hfill & \hfill 0\hfill \end{array}\right].$$ 
This is the Smith normal form of the matrix. The elements ${\alpha}_{i}$ are unique up to associates^{} and are called elementary divisors.
Title  Smith normal form 

Canonical name  SmithNormalForm 
Date of creation  20130322 13:52:08 
Last modified on  20130322 13:52:08 
Owner  Mathprof (13753) 
Last modified by  Mathprof (13753) 
Numerical id  21 
Author  Mathprof (13753) 
Entry type  Topic 
Classification  msc 13F10 
Defines  elementary divisor 