# 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\neq 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 non-zero entry.

(I)

If $a_{t,j_{t}}=0$ and $a_{k,j_{t}}\neq 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\left(a_{t,j_{t}},a_{k,j_{t}}\right)$ 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 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 $\delta(\beta)<\delta(a_{t,j_{t}})$. 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 left-multiplication with an appropriate matrix.

Applying the steps described above to the remaining non-zero columns of the resulting matrix (if any), we get an $m\times n$-matrix with column indices $j_{1},\ldots,j_{r}$ where $r\leq\min(m,n)$, each of which satisfies the following:

1. 1.

the entry at position $(l,j_{l})$ is non-zero;

2. 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\leq i\leq r$ are nonzero and $\delta(a_{i,i})\leq\delta(a_{i+1,i+1})$ for $1\leq i; 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 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 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 $\delta(\alpha_{i})<\delta(\alpha_{i+1})$ 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 $\alpha_{i}\mid\alpha_{i+1}\;\forall\;1\leq i.

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{matrix}\alpha_{1}&0&\ldots&0\\ 0&\alpha_{2}&\ldots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\ldots&\alpha_{r}\\ 0&0&\ldots&0\\ \vdots&\vdots&\ldots&\vdots\\ 0&0&\ldots&0\end{matrix}\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 SmithNormalForm 2013-03-22 13:52:08 2013-03-22 13:52:08 Mathprof (13753) Mathprof (13753) 21 Mathprof (13753) Topic msc 13F10 elementary divisor