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 be a -matrix with entries from a commutative principal ideal
domain . For denotes the number of
prime factors of . Start with and choose to be the smallest
column index of with a non-zero entry.
- (I)
-
If and , exchange rows 1 and .
- (II)
-
If there is an entry at position such that , then set and choose such that
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 and row multiplied by . Then we get at position , where . Repeating these steps one obtains a matrix having an entry at position that divides all entries in column .
- (III)
-
Finally, adding appropriate multiples
of row , it can be achieved that all entries in column except for that at position 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 -matrix with column indices where , each of which satisfies the following:
-
1.
the entry at position is non-zero;
-
2.
all entries below and above position as well as entries left of are zero.
Furthermore, all rows below the -th row are zero.
Now we can re-order the columns of this matrix so that elements on positions
for are nonzero and for ; and all columns right of the -th
column (if present) are zero. For short set for the element at
position . has non-negative integer values; so
is equivalent to being a unit of .
can either happen if and
differ by a unit factor, or if they are relatively prime. In the
latter case one can add column to column (which doesn’t change
and then apply appropriate row manipulations to get .
And for and one can apply step (II) after adding column to column .
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
satisfy .
Since all row and column manipulations involved in the process are ,
this shows that there exist invertible and -matrices
so that is
This is the Smith normal form of the matrix. The elements 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 |