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 idealdomain $R$. For $a\in R\setminus \{0\}$ $\delta (a)$ denotes the number ofprime factors of $a$. Start with $t=1$ and choose $j_t$ to be the smallestcolumn index of $A$ with a non-zero 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 =\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 left-multiplication with an appropriate matrix it can be achieved that row 1of 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 allentries in column $j_t$ except for that at position $(t,j_t)$ are zero. This canbe achieved by left-multiplication with an appropriate matrix.

Applying the steps described above to the remaining non-zero columns of theresulting matrix (if any), we get an $m\times n$-matrix with column indices$j_1,\mathrm{\dots },j_r$ where $r\le \min (m,n)$, each of which satisfies thefollowing:

1. the entry at position $(l,j_l)$ is non-zero;

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 re-order 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$-thcolumn (if present) are zero. For short set ${\alpha }_i$ for the element atposition $(i,i)$. $\delta$ has non-negative 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 thelatter 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 non-zero 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

This is the Smith normal form of the matrix. The elements ${\alpha }_i$ are unique up to associates and are calledelementary divisors.