Smith normal form

This topic gives a version of the Gauss elimination algorithm for a commutativePlanetmathPlanetmathPlanetmath principal ideal domainMathworldPlanetmath which is usually described only for a field.

Let A0 be a m×n-matrix with entries from a commutative principal ideal domain R. For aR{0} δ(a) denotes the number of prime factorsMathworldPlanetmathPlanetmath of a. Start with t=1 and choose jt to be the smallest column index of A with a non-zero entry.


If at,jt=0 and ak,jt0, exchange rows 1 and k.


If there is an entry at position (k,jt) such that at,jtak,jt, then set β=gcd(at,jt,ak,jt) and choose σ,τR such that


By left-multiplication with an appropriate matrix it can be achieved that row 1 of the matrix productMathworldPlanetmath is the sum of row 1 multiplied by σ and row k multiplied by (-τ). Then we get β at position (t,jt), where δ(β)<δ(at,jt). Repeating these steps one obtains a matrix having an entry at position (t,jt) that divides all entries in column jt.


Finally, adding appropriate multiplesMathworldPlanetmathPlanetmath of row t, it can be achieved that all entries in column jt except for that at position (t,jt) 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×n-matrix with column indices j1,,jr where rmin(m,n), each of which satisfies the following:

  1. 1.

    the entry at position (l,jl) is non-zero;

  2. 2.

    all entries below and above position (l,jl) as well as entries left of (l,jl) 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 1ir are nonzero and δ(ai,i)δ(ai+1,i+1) for 1i<r; and all columns right of the r-th column (if present) are zero. For short set αi for the element at position (i,i). δ has non-negative integer values; so δ(α1)=0 is equivalentPlanetmathPlanetmath to α1 being a unit of R. δ(αi)=δ(αi+1) can either happen if αi and α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 αi) and then apply appropriate row manipulations to get αi=1. And for δ(αi)<δ(αi+1) and αiαi+1 one can apply step (II) after adding column i+1 to column i. This diminishes the minimum δ-values for non-zero entries of the matrix, and by reordering columns etc. we end up with a matrix whose diagonal elements αi satisfy αiαi+1 1i<r.

Since all row and column manipulations involved in the process are , this shows that there exist invertiblePlanetmathPlanetmathPlanetmath m×m and n×n-matrices S,T so that SAT is


This is the Smith normal form of the matrix. The elements αi are unique up to associatesMathworldPlanetmath 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