You are here
HomeSmith normal form
Primary tabs
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 nonzero 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 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 $\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 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},\ldots,j_{r}$ where $r\leq\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\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 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 $\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 nonzero 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 invertible, 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.
Mathematics Subject Classification
13F10 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections