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.

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

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 $S A T$ 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
Canonical name	SmithNormalForm
Date of creation	2013-03-22 13:52:08
Last modified on	2013-03-22 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