The Smith normal form is a diagonal form of a matrix over a principal ideal domain, obtained by invertible row and column transformations, whose nonzero diagonal entries form a divisibility chain. These entries classify the matrix up to changes of bases in its domain and codomain. Over the integers, they can be chosen positive, making the form unique. The construction is a central tool in the classification of finitely generated abelian groups, the study of modules, and the exact solution of integer linear systems.
Definition and existence
Let be a principal ideal domain, and let . There exist invertible matrices
such that
where is the rectangular diagonal matrix
and
Here, “rectangular diagonal” means that every entry outside positions , for , is zero. The integer is the rank of , calculated over the field of fractions of .
The elements are called the invariant factors of . They are unique up to multiplication by units of . Thus the diagonal matrix becomes unique once a convention for choosing representatives of associated elements has been fixed:
- Over , the nonzero diagonal entries are chosen positive.
- Over , the ring of polynomials over a field , they are chosen monic.
The transformation matrices and are generally not unique.
For integer matrices, invertibility over is equivalent to having determinant or . Such matrices are called unimodular matrices. Requiring integer inverses is essential: arbitrary rational changes of bases would erase the divisibility information that the Smith form preserves.
Matrix equivalence and changes of bases
Two matrices and over are equivalent if
for invertible and over . The Smith normal form completely classifies this equivalence relation: two matrices of the same dimensions are equivalent exactly when their invariant factors agree up to units.
This is different from matrix similarity, which has the form . Similarity describes one endomorphism under a change of basis, whereas matrix equivalence allows independent changes of bases in the source and target.
If represents a homomorphism
then its Smith form expresses that map in suitable bases as
It therefore isolates the nonzero components of the map while recording their divisibility properties.
Determinantal divisors and uniqueness
The invariant factors can be characterized without explicitly finding and .
Set . For , let be a greatest common divisor of all minors of . These elements are called the determinantal divisors. Over a general principal ideal domain, each is defined up to a unit.
They satisfy
up to multiplication by a unit. Consequently,
with compatible choices of representatives.
The underlying reason is that invertible row and column operations preserve the ideal generated by the minors. For a Smith diagonal matrix, the divisibility chain makes this ideal precisely
This also proves uniqueness of the invariant factors up to units.
For a nonsingular integer matrix,
The determinant gives only the product of the invariant factors; smaller minors distinguish matrices with the same determinant.
Examples
Consider
Subtracting three times the first row from the second gives
Subtracting twice the first column from the second, then changing the sign of the second row, gives
Since , this is the Smith normal form.
The determinantal-divisor calculation yields the same result:
Hence and .
A diagonal matrix need not already be in Smith normal form. For example,
fails the divisibility condition. Its invariant factors are
so its Smith form is .
Construction and algorithms
Over the integers, Smith reduction uses elementary operations:
- interchange two rows or two columns;
- multiply a row or column by ;
- add an integer multiple of one row or column to another.
Over a general principal ideal domain, multiplication by any unit is allowed, and invertible transformations built from Bézout identities provide gcd reductions.
Over a Euclidean domain, the procedure resembles the Euclidean algorithm:
- Move a nonzero entry to the upper-left position.
- Use division and row or column operations to reduce the pivot until it divides all entries in its row and column.
- Clear the remainder of that row and column.
- If the pivot does not divide an entry of the remaining block, use that entry to obtain a new pivot associated to a proper divisor of the old one.
- Once the pivot divides the entire remaining block, repeat on that block.
The fourth step is necessary. Clearing a row and column alone produces a diagonal decomposition, but does not ensure the required divisibility chain.
The existence theorem holds over every principal ideal domain, not only Euclidean domains. Its abstract proof uses Bézout identities and the ascending chain condition on ideals rather than relying on a Euclidean division function. Effective computation additionally requires suitable algorithms for the underlying ring.
For integer matrices, naive implementations can create very large intermediate coefficients. More advanced methods use modular computations, coefficient control, and reconstruction. Computing only the invariant factors may be substantially cheaper than also computing the full transformation matrices. This distinction matters for large sparse matrices, whose transformations can become dense.
Modules and finitely generated abelian groups
The most important interpretation of Smith normal form concerns the module presented by a matrix. Regard the columns of as relations among generators. The resulting module is the cokernel
Smith reduction gives an isomorphism
Here denotes a direct sum, and a unit invariant factor contributes a zero module.
This yields the structure theorem for finitely generated modules over a principal ideal domain. In particular, every finitely generated abelian group has a decomposition
where
The integer and the listed invariant factors are uniquely determined.
For the matrix in the first example,
Factoring the invariant factors into powers of primes produces the elementary-divisor decomposition. The conversion between these decompositions uses the Chinese remainder theorem.
Applications
Integer linear equations
For a system of linear equations
suppose . Set
The system becomes . It has an integer solution exactly when
When these conditions hold, the first coordinates of are fixed and the remaining coordinates are arbitrary integers. Smith form thus provides both solvability criteria for linear Diophantine equations and a parametrization of their solutions.
Lattices and subgroup index
If has full rank, its columns generate a finite-index subgroup of . The index is
The individual invariant factors describe the quotient group more precisely than its order alone.
Algebraic topology
In algebraic topology, boundary maps of finite chain complexes are represented by integer matrices. Smith reduction helps compute integral homology groups, including their free ranks and torsion factors.
For
the two maps must be handled compatibly. When explicit bases or generators are required, changes of basis used for one boundary map must be propagated to the adjacent map; their separate diagonal forms do not by themselves specify those generators.
Polynomial matrices and linear operators
Over , Smith form classifies finitely presented modules over a polynomial ring in one variable. Applying it to
for a square matrix yields polynomial invariant factors that determine the rational canonical form of . This connects Smith reduction with the classification of linear operators without requiring the characteristic polynomial to split over .
Scope and distinctions
Smith normal form is an exact algebraic construction, unlike the singular value decomposition, which uses orthogonal or unitary transformations and measures real or complex magnitudes. Smith invariant factors instead encode divisibility in the coefficient ring.
Over a field, every nonzero element is a unit, so Smith form reduces to a diagonal matrix with ones and all remaining entries zero. Its finer information appears over rings such as and .
The theorem does not extend unchanged to arbitrary rings. Even over an integral domain, not every matrix admits a Smith form. For instance, over , the row matrix
cannot be equivalent to a diagonal row matrix: its entries generate the nonprincipal ideal , whereas the entries of a diagonal row matrix generate a principal ideal.
History
The form is named after Henry John Stephen Smith, who introduced the integer-matrix version in 1861 in work on systems of linear indeterminate equations and congruences. Its later formulation over principal ideal domains made it a standard bridge between matrix computations and the structure theory of modules.