Smith normal form


Smith normal form

The Smith normal form is a normal form that can be defined for any matrix (not necessarily square) with entries in a principal ideal domain (PID). The Smith normal form of a matrix is diagonal, and can be obtained from the original matrix by multiplying on the left and right by invertible square matrices. In particular, the integers are a PID, so one can always calculate the Smith normal form of an integer matrix. The Smith normal form is very useful for working with finitely generated modules over a PID, and in particular for deducing the structure of a quotient of a free module.

Let "A" be a nonzero "m"×"n" matrix over a principal ideal domain "R", and for "a" in "R" {0}, write δ("a") for the number of prime factors of "a" (these exist and are unique since any PID is also a unique factorization domain). In particular, "R" is also a Bézout domain, so it is a gcd domain and the gcd of any two elements satisfies a Bézout's identity.

Algorithm

Our goal will be to find invertible square matrices "S" and "T" such that the product "S A T" is diagonal. This is the hardest part of the algorithm and once we have achieved diagonality it becomes relatively easy to put the matrix in Smith normal form. (Note that invertibility of a matrix with entries in "R" is the same as saying that its determinant is a unit.) Phrased more abstractly, the goal is to show that, thinking of "A" as a map from R^n (the free "R"-module of rank "n") onto R^m (the free "R"-module of rank "m"), there are isomorphisms S:R^m o R^m and T:R^n o R^n such that S circ A circ T has the simple form of a diagonal matrix. The matrices "S" and "T" will be found by repeatedly applying elementary transformations that replace a row (column) with a linear combination of itself and another row (column).

Set "t" = 1 and choose "j""t" to be the smallest column index of "A" with a non-zero entry. One can repeatedly apply the following to put a matrix into Smith normal form.

Case I

If a_{t,j_t}=0 and a_{k,j_t} eq 0, exchange rows t and "k".

Case II

If there is an entry at position ("k","j""t") such that a_{t,j_t} mid a_{k,j_t}, then, letting eta =gcdleft(a_{t,j_t}, a_{k,j_t} ight), we know by the Bézout property that there exist σ, τ in "R" such that

:sigmacdot a_{t,j_t}- au cdot a_{k,j_t}=eta.

By left-multiplication with an appropriate matrix "L" it can be achieved that row "t" of the matrix product is the sum of row "t" multiplied by σ and row "k" multiplied by -τ. (If σ and τ satisfy the above equation, they must be relatively prime; so there exist α and γ such that

:sigmacdot alpha+ au cdot gamma=1,

or in other words, the determinant of the matrix

:egin{pmatrix}sigma & - au \gamma & alpha \end{pmatrix}

equals one. "L" can be obtained by fitting this matrix into the diagonal of the identity matrix at the appropriate positions, depending on the value of "t" and "k". That "L" has determinant one guarantees that "L" is invertible over "R".) After left-multiplying by "L" we get β at position ("t","j""t"), where delta(eta) < delta(a_{t,j_t}) and β divides a_{t,j_t}. Repeating these steps, one ends up with a matrix having an entry at position ("t","j""t") that divides all entries in column "j""t".

Case 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. However, to make the matrix fully diagonal we need to eliminate nonzero entries on the row of position ("t","j""t") as well. This can be achieved by repeating the steps in Case II for columns instead of rows, and using multiplication on the right. In general this will result in the zero entries from the prior application of Case II becoming nonzero again.

However, notice that the ideals generated by the elements at position ("t","j""t") form an ascending chain, because entries from a later step always divide entries from a previous step. Therefore, since "R" is a Noetherian ring (it is a PID), the ideals eventually become stationary and do not change. This means that at some stage after Case II has been applied, the entry at ("t","j""t") will divide all nonzero row or column entries before applying any more steps in Case II. Then we can eliminate entries in the row or column with nonzero entries while preserving the zeros in the already-zero row or column. At this point, only the block of "A" to the lower right of ("t","j""t") needs to be diagonalized, and the algorithm can be applied recursively, treating this block as a separate matrix.

Results

Applying the steps described above to the remaining non-zero columns of the resulting matrix (if any), we get an m imes n-matrix with column indices j_1, ldots, j_r where r le min(m,n), each of which satisfies the following:

* the entry at position (l,j_l) is non-zero;
* 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.

This is a version of the Gauss algorithm for principal ideal domains which is usually described only for commutative fields.

Now we can re-order the columns of this matrix so that elements on positions (i,i) for 1 le ile r are nonzero and delta(a_{ii}) le delta(a_{i+1,i+1}) for 1 le 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 relative 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) and alpha_i midalpha_{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 le i < r.

Since all row and column manipulations involved in the process are invertible, this shows that there exist invertible m imes m and n imes n-matrices "S, T" so that the product "S A T" is

:egin{pmatrix}alpha_1 & 0 & 0 & & cdots & & 0 \0 & alpha_2 & 0 & & cdots & & 0 \0 & 0 & ddots & & & & 0\vdots & & & alpha_r & & & vdots \ & & & & 0 & & \ & & & & & ddots & \0 & & & cdots & & & 0end{pmatrix}.

This is the Smith normal form of the matrix. The elements alpha_i are unique up to associatedness and are called the elementary divisors, invariants, or invariant factors.

Applications

The Smith normal form is useful for computing the homology of a chain complex when the chain modules of the chain complex are finitely generated. For instance, in topology, it can be used to compute the homology of a simplicial complex or CW complex over the integers, because the boundary maps in such a complex are just integer matrices. It can also be used to prove the well known structure theorem for finitely generated modules over a principal ideal domain.

Example

As an example, we will find the Smith normal form of the following matrix over the integers.

:egin{pmatrix}2 & 4 & 4 \-6 & 6 & 12 \10 & -4 & -16end{pmatrix}

The following matrices are the intermediate steps as the algorithm is applied to the above matrix.

: oegin{pmatrix}2 & 0 & 0 \-6 & 18 & 24 \10 & -24& -36end{pmatrix} oegin{pmatrix}2 & 0 & 0 \0 & 18 & 24 \0 & -24& -36end{pmatrix}

: oegin{pmatrix}2 & 0 & 0 \0 & 18 & 24 \0 & -6 & -12end{pmatrix} oegin{pmatrix}2 & 0 & 0 \0 & 6 & 12 \0 & 18 & 24end{pmatrix}

: oegin{pmatrix}2 & 0 & 0 \0 & 6 & 12 \0 & 0 & -12end{pmatrix} oegin{pmatrix}2 & 0 & 0 \0 & 6 & 0 \0 & 0 & 12end{pmatrix}

So the Smith normal form is

:egin{pmatrix}2 & 0 & 0 \0 & 6 & 0 \0 & 0 & 12end{pmatrix}

and the elementary divisors are 2, 6 and 12.

Similarity

The Smith normal form can be used to determine whether or not matrices with entries over a common field are similar. Specifically two matrices "A" and "B" are similar if and only if the characteristic matrices xI-A mbox{ and } xI-B have the same Smith normal form.

For example, with:egin{align}A & {} =egin{bmatrix} 1 & 2 \ 0 & 1 end{bmatrix}, & & mbox{SNF}(xI-A) =egin{bmatrix} 1 & 0 \ 0 & (x-1)^2end{bmatrix} \B & {} =egin{bmatrix} 3 & -4 \ 1 & -1 end{bmatrix}, & & mbox{SNF}(xI-B) =egin{bmatrix} 1 & 0 \ 0 & (x-1)^2end{bmatrix} \C & {} =egin{bmatrix} 1 & 0 \ 1 & 2 end{bmatrix}, & & mbox{SNF}(xI-C) =egin{bmatrix} 1 & 0 \ 0 & (x-1)(x-2)end{bmatrix}end{align}

"A" and "B" are similar because the Smith normal form of their characteristic matrices match, but are not similar to "C" because the Smith normal form of the characteristic matrices do not match.

See also

* Canonical form
* Henry John Stephen Smith (1826 &ndash; 1883), whose name is attached to the Smith normal form

External links

* Thomas Heye's GFDL [http://planetmath.org/?method=l2h&from=objects&name=GausssAlgorithmForPrincipalIdealDomains&op=getobj Smith normal form article at PlanetMath]
* GFDL [http://planetmath.org/encyclopedia/ExampleOfSmithNormalForm.html Example of Smith normal form at PlanetMath]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Normal-gamma distribution — Normal gamma parameters: location (real) (real) (real) (real) support …   Wikipedia

  • Normal distribution — This article is about the univariate normal distribution. For normally distributed vectors, see Multivariate normal distribution. Probability density function The red line is the standard normal distribution Cumulative distribution function …   Wikipedia

  • Normal School for Colored Girls — Miner Normal School U.S. National Register of Historic Places …   Wikipedia

  • Canonical form — Generally, in mathematics, a canonical form (often called normal form or standard form) of an object is a standard way of presenting that object. Canonical form can also mean a differential form that is defined in a natural (canonical) way; see… …   Wikipedia

  • Henry John Stephen Smith — Infobox Scientist name = Henry John Stephen Smith box width = image width = caption = birth date = birth date|1826|11|02 birth place = Dublin, Ireland death date = death date and age|1883|02|09|1826|11|02 death place = Oxford, Oxfordshire,… …   Wikipedia

  • Agent Smith — The Matrix character Movie poster for The Matrix Revolutions, featuring some of the numerous copies of Smith. First appearance …   Wikipedia

  • Multivariate normal distribution — MVN redirects here. For the airport with that IATA code, see Mount Vernon Airport. Probability density function Many samples from a multivariate (bivariate) Gaussian distribution centered at (1,3) with a standard deviation of 3 in roughly the… …   Wikipedia

  • Mecca Normal — Mecca Normal, photo by Jean Smith Formed by Jean Smith and David Lester in 1984, Mecca Normal is a two piece indie rock band from Vancouver, Canada. Smith writes lyrics and sings in a style that is often confrontational and laced with feminist… …   Wikipedia

  • Gordon A. Smith — Gordon Appelbe Smith, born June 18, 1919 (1919 06 18) (age 92) in East Brighton, England, is a Canadian painter, printmaker, sculptor, and teacher living in West Vancouver, British Columbia. Smith taught with contemporaries Alistair Bell,… …   Wikipedia

  • Joseph Smith, Jr. — Joseph Smith, Jr. (December 23, 1805 – June 27, 1844) was the founder of the Latter Day Saint movement, also known as Mormonism, and an important religious and political figure in the United States during the 1830s and 1840s. In 1827, Smith began …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.