Integer Matrix Normal Forms
The Smith Normal Form Algorithm
The Smith normal form, its computation by alternating row and column reduction, and the invariant factors it exposes.
Engineering / MathematicsInteger Matrix Normal Forms2 min readKV-MATH-0540
Where the Hermite normal form describes how a submodule sits inside an ambient module, the Smith normal form forgets the embedding and exposes the isomorphism class of the quotient.
Definition
A matrix is in Smith normal form when it is diagonal and each diagonal entry divides the next. The diagonal entries are the invariant factors and are uniquely determined by the matrix.
Computation
Smith normal form
- Find a small pivotMove the entry of smallest absolute value to the corner.
- Clear the row and columnReduce all other entries in the first row and column using the pivot.
- Handle non-divisibilityIf some remaining entry is not divisible by the pivot, add its row to the first and repeat — the pivot strictly decreases, guaranteeing termination.
- RecurseApply the same procedure to the remaining submatrix.
- Enforce divisibilityAdjust adjacent diagonal pairs so each divides the next.
Reading the structure
If a subgroup of a free abelian group of rank n is presented by a matrix whose Smith normal form has invariant factors, the quotient group decomposes accordingly.
| Feature of the form | Meaning for the quotient |
|---|---|
| Number of non-zero diagonal entries | Rank of the subgroup |
| Entries equal to one | Contribute nothing; discard |
| Entries greater than one | The cyclic factors |
| Zero columns | Free part of the quotient |
| Product of non-zero entries | Order of the torsion subgroup |
Cost and growth
Practical note
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.4.4. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.