snf

Smith normal form (SNF) is a canonical diagonal form for integer matrices that can be obtained through unimodular transformations. For an m-by-n integer matrix A, there exist unimodular matrices U (m-by-m) and V (n-by-n) with determinant ±1 such that UAV = D, where D is diagonal with entries d1, d2, ..., dr, followed by zeros. The diagonal entries satisfy d1 divides d2 divides ... divides dr, and r is the rank of A. The nonzero diagonal entries are called the invariant factors of A.

The SNF is unique up to multiplication of the diagonal entries by units in the integers (typically the signs), and one can choose all di to be nonnegative. The Smith normal form generalizes the notion of diagonalization to integer matrices and provides a complete set of invariants for the integer linear transformation represented by A.

In a broader algebraic sense, SNF is tied to the structure theorem for finitely generated modules over a principal ideal domain. For the map defined by A between free modules, the cokernel Z^m / Im(A) decomposes as a direct sum of cyclic groups: Z/d1Z ⊕ Z/d2Z ⊕ ... ⊕ Z/drZ ⊕ Z^{m-n-r}, where the last term accounts for free components. In particular, SNF gives a concrete description of the abelian group structure associated with A.

Computationally, SNF is obtained via a sequence of elementary row and column operations corresponding to unimodular transformations, often using the extended Euclidean algorithm. Several polynomial-time algorithms exist for computing SNF, making it a standard tool in integer linear algebra, number theory, and module theory. SNF also facilitates solving systems of linear Diophantine equations and understanding module classifications.