The Smith normal form (SNF) of an m \times n matrix A over a principal ideal domain R (such as the integers \mathbb{Z}) is a diagonal matrix D = \operatorname{diag}(d_1, d_2, \dots, d_r, 0, \dots, 0), where r \leq \min(m,n), each d_i is a non-zero element of R, and d_i divides d_{i+1} for $1 \leq i < r, obtained via D = P A Q for invertible matrices P \in \operatorname{GL}_m(R) and Q \in \operatorname{GL}_n(R).[1][2][3]
This form is unique up to multiplication of the diagonal entries by units of R, with the diagonal elements d_i known as the invariant factors of A, which fully characterize the cokernel of the linear map defined by A as a finitely generated torsion module \bigoplus_{i=1}^r R/(d_i).[1][3] The existence and uniqueness were first established by Henry John Stephen Smith in 1861 for matrices over \mathbb{Z}, later generalized to principal ideal domains.[4][1]
Computing the SNF involves applying elementary row and column operations over R—swapping rows/columns, multiplying by units, and adding multiples of one to another—analogous to Gaussian elimination but preserving the ring structure, often using the Euclidean algorithm to ensure the divisibility condition.[3][2] The invariant factors satisfy that the product d_1 d_2 \cdots d_k equals the greatest common divisor of all k \times k minors of A, for each k.[1]
Beyond linear algebra, the SNF has applications in number theory for solving systems of linear Diophantine equations, in algebraic topology for classifying finitely generated abelian groups, and in combinatorics for analyzing the critical groups of graphs and the structure of integer matrices in enumerative problems.[1][5]
Prerequisites
Principal ideal domains
A principal ideal domain (PID) is defined as an integral domain R in which every ideal is principal, that is, generated by a single element a \in R such that the ideal consists of all multiples \{ra : r \in R\}.[6] This property ensures that the ring has a highly structured lattice of ideals, simplifying many algebraic constructions.[7]
Prominent examples of PIDs include the ring of integers \mathbb{Z}, where every ideal is of the form n\mathbb{Z} for some nonnegative integer n, and polynomial rings k over a field k, whose ideals are generated by single polynomials.[6] Another class consists of discrete valuation rings (DVRs), which are local PIDs with exactly one nonzero prime ideal and arise as valuation rings associated to discrete valuations on fields.[8]
PIDs possess several fundamental properties that underpin their utility in algebra. Every PID is a unique factorization domain (UFD), meaning every nonzero nonunit element factors uniquely into irreducibles up to units and order.[9] In a PID, any two elements a, b generate a principal ideal (a, b) = (d), where d is a greatest common divisor of a and b, and Bézout's identity holds: d = as + bt for some s, t \in R.[6] This enables the computation of GCDs, often via the Euclidean algorithm when the PID admits a suitable Euclidean function, as in \mathbb{Z} or k.[10] Units in a PID are precisely the elements whose principal ideals equal the entire ring R, and two elements are associates if one is the product of the other by a unit, leading to \langle a \rangle = \langle ua \rangle for any unit u.[6]
A cornerstone result is the structure theorem for modules over PIDs, which asserts that every finitely generated module over a PID decomposes uniquely (up to isomorphism) as a direct sum of a free module and a torsion module, providing the foundational decomposition for more advanced classifications.[11]
Finitely generated modules
A module M over a ring R is finitely generated if there exists a finite set \{x_1, \dots, x_n\} \subseteq M such that every element of M can be expressed as an R-linear combination of these generators.[12]
When R is a principal ideal domain (PID), the structure theorem provides a complete classification of finitely generated modules. Specifically, every such module M decomposes uniquely (up to isomorphism) as M \cong R^r \oplus \bigoplus_{i=1}^k R/(d_i), where r \geq 0 is the free rank, k \geq 0 is the torsion rank, each d_i \in R is a non-zero non-unit element, and the d_i satisfy d_1 \mid d_2 \mid \cdots \mid d_k up to units (associates). For the special case R = \mathbb{Z}, this becomes \mathbb{Z}^r \oplus \bigoplus_{i=1}^k \mathbb{Z}/d_i \mathbb{Z} with positive integers d_i > 1.[13] This decomposition separates M into a free part isomorphic to R^r and a torsion part consisting of cyclic modules, with the successive divisibility condition ensuring uniqueness of the invariant factors d_i.[13]
Finitely generated modules over a PID can be presented using matrices. Given a presentation with n generators and m relations, the module is the cokernel of a homomorphism \phi: R^n \to R^m defined by an m \times n matrix A \in M_{m \times n}(R), so M \cong R^m / \operatorname{im} \phi, where the columns of A encode the relations among the generators.[14] Two such presentation matrices A and B yield isomorphic modules if there exist invertible matrices P \in \operatorname{GL}_m(R) and Q \in \operatorname{GL}_n(R) such that P A Q = B, reflecting a change of basis in the domain and codomain.[15]
This matrix presentation framework motivates the study of normal forms, as they standardize the relation matrix to directly reveal module invariants such as the free rank r and torsion coefficients d_i, facilitating the computation and comparison of module structures without resolving the full isomorphism.[16]
Definition and properties
Let R be a principal ideal domain and A \in M_{m \times n}(R) an m \times n matrix over R. The Smith normal form theorem states that there exist invertible matrices P \in \mathrm{GL}_m(R) and Q \in \mathrm{GL}_n(R) such that PAQ = D, where D is a diagonal matrix with diagonal entries d_1, d_2, \dots, d_s, 0, \dots, 0 (with s \leq \min(m,n)), satisfying d_i \mid d_{i+1} for all i = 1, \dots, s-1 and d_i \neq 0 for i = 1, \dots, s.[17][18]
This form is achieved through a sequence of elementary row and column operations over R, which generate the equivalence relation: (i) interchanging two rows (or columns), (ii) multiplying a row (or column) by a unit of R, and (iii) adding an R-multiple of one row (or column) to another.[18] These operations correspond to left- or right-multiplication by elementary matrices, which are invertible over R.[18]
The nonzero diagonal entries d_1, \dots, d_s determine the structure, with s equal to the rank of A over the fraction field of R; units among the d_i can be normalized to 1 (the identity element in R, e.g., 1 in \mathbb{Z}). The non-unit nonzero entries are the invariant factors of A, unique up to multiplication by units in R.[17][18]
Uniqueness follows from the determinantal ideals of A: for each k = 1, \dots, \min(m,n), the k-th determinantal ideal I_k(A) is the ideal generated by all k \times k minors of A. In the Smith normal form D, I_k(D) = (d_1 d_2 \cdots d_k) for k \leq s and I_k(D) = (0) for k > s; since equivalence preserves these ideals, the product of the first k (nonzero) diagonal entries generates I_k(A), determining each d_k up to units as the generator of I_k(A) : I_{k-1}(A) (with I_0(A) = R).[18][19]
Invariant factors and uniqueness
The invariant factors of a matrix A over a principal ideal domain R are the non-unit nonzero diagonal entries d_1, d_2, \dots, d_t in its Smith normal form, normalized such that d_i \mid d_{i+1} for i = 1, \dots, t-1; here t is the number of such factors. The full diagonal has s nonzero entries where s = \rank(A) (over the fraction field of R) and s \geq t, with the additional s - t entries being units (normalized to 1). Beyond the s nonzero entries, the remaining diagonal positions up to \min(m,n) are 0.[1]
These factors capture the torsion part of the cokernel of the map A: R^n \to R^m, specifically \coker(A) \cong \bigoplus_{i=1}^s R/(d_i) \oplus R^{m-s} \cong \bigoplus_{i=1}^t R/(d_i) \oplus R^{m-s}, since R/(u) = 0 for any unit u \in R; the free part has rank m - s, while the 0 entries contribute free summands and unit entries contribute trivial summands.[1][20]
The sequence of invariant factors (d_1, \dots, d_t) is unique up to multiplication by units in R, regardless of the choice of invertible matrices P and Q such that P A Q = \operatorname{diag}(d_1, \dots, d_s, 0, \dots, 0).[21] This uniqueness follows from the invariance of the Fitting ideals under elementary row and column operations. The k-th Fitting ideal \operatorname{Fit}_k(A) is the ideal generated by all k \times k minors of A; for the diagonal form D, \operatorname{Fit}_k(D) is generated by the product d_1 d_2 \cdots d_k, and since equivalent matrices share the same Fitting ideals, the products determine the d_i uniquely up to units.[21]
An alternative approach to uniqueness uses the annihilator ideals of the exterior powers of the module. The elementary operations preserve the annihilators \operatorname{Ann}_R(\wedge^k M) for the finitely generated module M = \operatorname{coker}(A), and these annihilators determine the invariant factors via their structure as principal ideals in the PID, ensuring the canonical form is independent of the decomposition.[1]
The invariant factors are connected to the elementary divisors, which provide a primary decomposition of the torsion module. Each d_i factors uniquely (up to units) as a product of prime powers p_j^{e_{i,j}} in R, and the elementary divisors are the collection of these p_j^{e_{i,j}} across all i, leading to the torsion decomposition \bigoplus_{i=1}^t R/(d_i) \cong \bigoplus_p \bigoplus_{j} R/(p^{e_j}) where the exponents for each prime p are non-decreasing; however, the Smith normal form emphasizes the invariant factor presentation over this primary one.[1]
Computation
Algorithm overview
The Smith normal form of an m \times n matrix A over a principal ideal domain R can be computed constructively using a series of elementary row and column operations, which correspond to left and right multiplications by invertible matrices over R.[21] The overall strategy involves iteratively diagonalizing the matrix in a block-wise manner, starting from the top-left entry and proceeding to subsequent positions along the diagonal, mimicking the Euclidean algorithm to reduce off-diagonal entries to zero while leveraging the greatest common divisor properties inherent to PIDs.[22] This process transforms A into a diagonal matrix D such that D = PAQ for some invertible P and Q over R, with the diagonal entries satisfying the divisibility condition.[23]
Key operations in the algorithm include swapping rows or columns to position a suitable pivot, adding integer multiples of one row (or column) to another to eliminate entries, and scaling rows or columns by units in [R](/page/R) to normalize pivots.[21] These operations preserve the equivalence class of the matrix and exploit the fact that in a PID, any two elements have a greatest common divisor that generates their ideal, allowing systematic reduction.[22]
The algorithm terminates because each iteration either zeros out off-diagonal entries in the current block or advances to the next diagonal position, with the well-ordering principle of R ensuring that the "size" of non-pivot entries decreases in a well-founded order.[23] Specifically, the process stabilizes when the matrix becomes fully diagonal, as the sequence of principal ideals generated by the diagonal entries becomes stationary.[23]
A high-level pseudocode outline for the algorithm proceeds as follows:
for i from 1 to min(m, n) do
Find a non-zero entry in the i-th row and column submatrix as pivot
Swap rows/columns to bring pivot to position (i, i)
Eliminate off-diagonal entries in row i and column i using additions of multiples
Normalize the pivot if necessary
end for
for i from 1 to min(m, n) do
Find a non-zero entry in the i-th row and column submatrix as pivot
Swap rows/columns to bring pivot to position (i, i)
Eliminate off-diagonal entries in row i and column i using additions of multiples
Normalize the pivot if necessary
end for
This loop continues until the matrix is diagonal.[21]
To achieve the standard Smith normal form, after diagonalization, the algorithm ensures the diagonal entries d_1, d_2, \dots, d_r (with r the rank) satisfy d_i \mid d_{i+1} for all i, by propagating divisors backward through additional row and column operations if the initial diagonal does not meet this condition.[22] For detailed procedural steps, including pivot selection, refer to the subsequent section.[21]
Detailed steps
The computation of the Smith normal form of an integer matrix proceeds through an iterative process that transforms the matrix using elementary row and column operations while preserving equivalence over the integers. The algorithm operates on the current leading submatrix, starting with the full matrix, and focuses on establishing a pivot at the (1,1) position that satisfies specific divisibility conditions before eliminating off-diagonal entries and recursing on the remaining block.[24][3]
In the first step, pivot selection involves identifying the nonzero entry of minimal absolute value within the current submatrix and permuting rows and columns to position it at the (1,1) entry, denoted as a_{11}. This choice minimizes the pivot size to facilitate subsequent reductions, as the absolute value serves as the size function \sigma in the Euclidean domain of integers. Permutations are achieved via swapping rows or columns, which are unimodular operations.[24][3]
The second step, pivot improvement, applies a variant of the Euclidean algorithm to ensure that a_{11} becomes the greatest common divisor (GCD) of all entries in its row and column, thereby eliminating larger entries that are not multiples. For an entry a_{i1} in the first column with i > 1, if a_{11} does not divide a_{i1}, add the i-th column to the first column (or a multiple thereof) to introduce a smaller remainder into the first row; repeat permutations and reductions as needed until a_{11} divides every entry in the first row and column. Similarly, process the first row entries a_{1j} for j > 1. This process iteratively reduces the pivot until it achieves the GCD property.[24][3]
Once the pivot divides all relevant entries, the third step performs off-diagonal elimination to clear the rest of the first row and column. For an entry a_{i1} in the first column (i > 1), let g = \gcd(a_{11}, a_{i1}); since the improvement step ensures g = a_{11}, subtract (a_{i1} / a_{11}) times the first row from the i-th row, which is an integer multiple. The updated entry becomes:
a_{i1}' = a_{i1} - \frac{a_{i1}}{a_{11}} \cdot a_{11} = 0.
Analogously, for an entry a_{1j} in the first row (j > 1), subtract (a_{1j} / a_{11}) times the first column from the j-th column to zero it out. These operations do not affect the pivot or introduce smaller entries elsewhere in the submatrix. The process then recurses on the remaining principal submatrix excluding the first row and column.[24][3]
After the matrix is fully diagonalized through recursion, a final adjustment ensures the diagonal entries d_1, d_2, \dots, d_k satisfy the divisibility condition d_i \mid d_{i+1} for all i. If a violation occurs, such as d_i not dividing d_{i+1}, swap the i-th and (i+1)-th rows (and columns if necessary), then recompute the local GCD and elimination in that block to resolve the issue. This step may require iterating back through affected pivots but terminates due to the non-increasing nature of the entries.[24][3]
Illustrative example
Consider the integer matrix A = \begin{pmatrix} 2 & 1 \\ 1 & 3 \end{pmatrix}. To compute its Smith normal form, begin by swapping the rows to position the smallest absolute value entry as the pivot: \begin{pmatrix} 1 & 3 \\ 2 & 1 \end{pmatrix}. Next, eliminate the entry below the pivot by subtracting 2 times the first row from the second row: \begin{pmatrix} 1 & 3 \\ 0 & -5 \end{pmatrix}. Then, eliminate the entry to the right of the pivot by subtracting 3 times the first column from the second column (after multiplying the second row by -1 to make the pivot positive, yielding \begin{pmatrix} 1 & 3 \\ 0 & 5 \end{pmatrix} intermediately): \begin{pmatrix} 1 & 0 \\ 0 & 5 \end{pmatrix}. The resulting diagonal matrix is the Smith normal form, with invariant factors 1 and 5.[24]
Now consider another example, the diagonal matrix A = \begin{pmatrix} 2 & 0 \\ 0 & 3 \end{pmatrix}. Although already diagonal, the entries do not satisfy the divisibility condition since 2 does not divide 3. To proceed, apply column operations using Bézout coefficients, as \gcd(2,3)=1 and $2(-1) + 3(1) = 1: replace the first column with -1 times the first column plus 1 times the second column, yielding \begin{pmatrix} -2 & 0 \\ 3 & 3 \end{pmatrix}. Multiply the first column by -1: \begin{pmatrix} 2 & 0 \\ -3 & 3 \end{pmatrix}. Swap rows and multiply the new first row by -1: \begin{pmatrix} 3 & -3 \\ 2 & 0 \end{pmatrix}. Subtract 1 times the second row from the first row: \begin{pmatrix} 1 & -3 \\ 2 & 0 \end{pmatrix}. Subtract 2 times the first row from the second row: \begin{pmatrix} 1 & -3 \\ 0 & 6 \end{pmatrix}. Finally, add 3 times the first column to the second column: \begin{pmatrix} 1 & 0 \\ 0 & 6 \end{pmatrix}. This is the Smith normal form, with invariant factors 1 and 6. The cokernel of the linear map defined by A is isomorphic to \mathbb{Z}/6\mathbb{Z}.[24][25]
Analysis
Computational complexity
The computation of the Smith normal form of an m \times n integer matrix with entries bounded by B in absolute value begins with naive algorithms that perform repeated row and column operations involving greatest common divisor (GCD) computations to eliminate off-diagonal entries. These methods, akin to extended Gaussian elimination over the integers, incur a time complexity of O(m n (m + n) \log B) bit operations, primarily due to the iterative GCD steps and the logarithmic cost of each Euclidean algorithm invocation on growing intermediate values.[26]
Improved deterministic algorithms achieve polynomial time in the matrix dimensions and the bit length \log B. The seminal work of Kannan and Bachem (1979) introduced the first such polynomial-time algorithm, running in O((m n)^3 (\log (m n) + \log B)^3) arithmetic operations, with corresponding bit complexity accounting for integer multiplications.[27] Subsequent refinements, such as those by Chou and Collins (1982) and further optimizations in the 1980s, reduced the bit complexity to O(s^5 M(s^2)) for square matrices of size s = \min(m,n), where M(t) denotes the cost of multiplying two t \times t integer matrices, leveraging faster matrix multiplication techniques.[28]
Computing the Smith normal form over \mathbb{Z} presents significant challenges due to bit growth in intermediate entries, which can reach exponential sizes without careful control, potentially leading to worst-case exponential time if modular reductions are not employed. Modern variants mitigate this by incorporating fast Euclidean algorithms like the half-GCD method, achieving near-optimal bit complexities such as \tilde{O}(n^\omega (\log n + \log B)^{O(1)}) for n \times n matrices, where \omega < 2.373 is the matrix multiplication exponent.[29]
In practice, computer algebra systems like Magma and Sage implement hybrid approaches using p-adic expansions or modular arithmetic over prime powers, combined via the Chinese Remainder Theorem, to handle large matrices efficiently while avoiding excessive bit growth; for instance, these methods enable computation of the Smith normal form for matrices up to 1000 × 1000 in reasonable time on modern hardware.[30][31]
Theoretical lower bounds establish that any algorithm must require at least \Omega(m n) bit operations to read the input, but more substantively, \Omega((m n)^2) due to the need to evaluate or implicitly compute GCDs of minors up to size \min(m,n), as the invariant factors depend on these determinants.[28]
The Smith normal form was introduced by Henry John Stephen Smith in 1861 in his paper on systems of linear indeterminate equations and congruences, where it provided a canonical diagonal representation for integer matrices under equivalence transformations. This development paralleled the work of Charles Hermite, who around the same period established the Hermite normal form as an upper triangular canonical form for integer matrices using only row operations, serving as a one-sided analog to the two-sided Smith form. Over principal ideal domains, the Smith normal form generalizes such structures, but its form varies with the ring; for example, over fields (which are PIDs), it reduces to the rank-nullity theorem's diagonal form, consisting of 1's along the diagonal up to the matrix rank and 0's thereafter, which is equivalent to the reduced row echelon form under row and column operations.[32]
In contrast to similarity transformations, which conjugate a matrix via P^{-1} A P to study endomorphisms, the Smith normal form relies on equivalence transformations P A Q = D with invertible P and Q, capturing module structure rather than operator similarity.[18] Over fields, these notions align for diagonalizable matrices, where both yield a diagonal canonical form with eigenvalues on the diagonal, but the Smith approach emphasizes the invariant factors derived from equivalence.[33]
The Smith normal form connects to other canonical forms for matrices over fields through the characteristic matrix xI - A; its diagonal entries give the invariant factors of the characteristic polynomial, directly determining the rational canonical form of A, which decomposes the space into cyclic subspaces.[34] This relates to the Jordan canonical form, a refinement over algebraically closed fields, where the invariant factors capture the semisimple (diagonalizable) part via products of elementary divisors, while the Jordan form specifies the block structure from those divisors, encoding nilpotent components and generalized eigenspaces.[34]
Over more general rings, such as Euclidean domains beyond fields, the Hermite normal form acts as a partial analog to the Smith form, producing an upper triangular matrix with non-negative entries below the diagonal being zero and diagonal entries satisfying divisibility conditions, achievable via row operations alone without full two-sided equivalence.[35] This one-sided nature makes it computationally complementary, often used as an intermediate step toward the Smith form.[35]
Applications
Systems of linear Diophantine equations
The Smith normal form provides a systematic method for determining the solvability and parametrizing the integer solutions to systems of linear Diophantine equations of the form A \mathbf{x} = \mathbf{b}, where A is an m \times n integer matrix, \mathbf{x} \in \mathbb{Z}^n, and \mathbf{b} \in \mathbb{Z}^m.[36] This approach generalizes to equations over any principal ideal domain (PID) R, where solutions are sought in R^n.[37]
To solve the system, first compute the Smith normal form of A, which yields unimodular matrices P \in \mathrm{GL}_m(\mathbb{Z}) and Q \in \mathrm{GL}_n(\mathbb{Z}) such that P A Q = D, where D = \mathrm{diag}(d_1, \dots, d_r, 0, \dots, 0) with r = \mathrm{rank}(A), d_i dividing d_{i+1} for i = 1, \dots, r-1, and each d_i a non-zero element of the PID.[36] Substituting \mathbf{y} = Q^{-1} \mathbf{x} (noting Q^{-1} is also unimodular) transforms the equation to D \mathbf{y} = P \mathbf{b}. Let \mathbf{c} = P \mathbf{b}. The transformed system decouples into r independent equations d_i y_i = c_i for i = 1, \dots, r, and y_i = 0 for i = r+1, \dots, m (if m > n, consistency requires c_i = 0 for those indices).[37]
Solutions exist if and only if d_i divides c_i in the PID for each i = 1, \dots, r (and c_i = 0 for i > r if applicable).[36] If solvable, a particular solution is given by y_i = c_i / d_i for i = 1, \dots, r and y_i = 0 for i = r+1, \dots, n, with the corresponding \mathbf{x}^{(0)} = Q \mathbf{y}^{(0)}. The general solution is then \mathbf{x} = \mathbf{x}^{(0)} + Q \mathbf{k}, where \mathbf{k} spans the kernel of D, consisting of vectors with arbitrary entries in the last n - r coordinates and zeros elsewhere; this yields a free module of rank n - r over the PID.[37]
For inhomogeneous systems (where \mathbf{b} \neq \mathbf{0}), the diagonal entries d_i directly impose the consistency conditions via the divisibility requirements on c_i, ensuring the transformed right-hand side aligns with the structure of D.[36]
For example, consider A = \begin{pmatrix} 2 & 3 \\ 4 & 6 \end{pmatrix} (rank 2), whose SNF is D = \begin{pmatrix} 1 & 0 \\ 0 & 6 \end{pmatrix} (after suitable P and Q), and take \mathbf{b} = \begin{pmatrix} 5 \\ 12 \end{pmatrix}. Then \mathbf{c} = P \mathbf{b}; assuming the transformation aligns such that the conditions hold (1 divides the first component of \mathbf{c}, 6 divides the second), a particular solution exists, and since rank 2 and n=2, the kernel is trivial, yielding a unique solution. For a rank-deficient case, say n=3 with third column zero (rank 2), solutions are parametrized by one free integer parameter.[37]
Classification of abelian groups
The classification of finitely generated abelian groups relies on viewing them as finitely generated modules over the principal ideal domain \mathbb{Z}. The structure theorem for such modules asserts that every finitely generated abelian group G is isomorphic to \mathbb{Z}^r \oplus \bigoplus_{i=1}^t \mathbb{Z}/d_i\mathbb{Z}, where r \geq 0 is the rank (the dimension of the free part), the d_i > 1 are positive integers satisfying d_i \mid d_{i+1} for each i, and t is the torsion rank.[38] This decomposition, known as the invariant factor form, provides a canonical presentation of G up to isomorphism.[1]
To obtain this decomposition from a finite presentation of G, consider G \cong \mathbb{Z}^n / \operatorname{im}(A), where A is an m \times n integer matrix encoding the relations among the n generators. The Smith normal form of A, computed via elementary row and column operations over \mathbb{Z}, yields a diagonal matrix \operatorname{diag}(s_1, s_2, \dots, s_k, 0, \dots, 0) with k = \operatorname{[rank](/page/Rank)}(A) and s_i \mid s_{i+1} for i = 1, \dots, k. The nonzero s_i (with s_i > 1 or adjusted to 1 if necessary) directly give the invariant factors d_i = s_i, while the number of zero diagonal entries determines the free rank r = n - k. Thus, G \cong \bigoplus_{i=1}^k \mathbb{Z}/s_i\mathbb{Z} \oplus \mathbb{Z}^r.[38][1]
An alternative canonical form is the elementary divisor decomposition, where the torsion part \bigoplus_{i=1}^t \mathbb{Z}/d_i\mathbb{Z} is further decomposed into primary components: G \cong \mathbb{Z}^r \oplus \bigoplus_p \bigoplus_{j} \mathbb{Z}/p^{e_{p,j}}\mathbb{Z}, with the sums over primes p and exponents e_{p,j} \geq 1. Each invariant factor d_i factors as a product of prime powers, and the elementary divisors are these prime power factors collected across all d_i with nondecreasing exponents for each prime. For instance, \mathbb{Z}/12\mathbb{Z} \cong \mathbb{Z}/4\mathbb{Z} \oplus \mathbb{Z}/3\mathbb{Z}, since $12 = 4 \times 3.[1] Both forms are unique up to isomorphism, with the invariant factors determining the elementary divisors via prime factorization and the converse by successively multiplying the highest powers across primes to form each d_i. An algorithm to convert between them involves factoring the d_i into primes and regrouping the powers: start with the elementary divisors sorted by prime and exponent, then form d_t as the product of the highest power for each prime, d_{t-1} from the next highest, and so on, ensuring divisibility.[1]
The uniqueness follows from the fact that the invariant factors (or elementary divisors) are determined by the successive gcds of the minors of A, which are preserved under the equivalence to Smith normal form. For example, consider the abelian group presented by generators x, y, z and relations $2x = 0, $3y = 0. The relation matrix is \begin{pmatrix} 2 & 0 & 0 \\ 0 & 3 & 0 \end{pmatrix}, whose Smith normal form is \operatorname{diag}(1, 6, 0). Thus, the group is isomorphic to \mathbb{Z}/1\mathbb{Z} \oplus \mathbb{Z}/6\mathbb{Z} \oplus \mathbb{Z} \cong \mathbb{Z} \oplus \mathbb{Z}/6\mathbb{Z}. In elementary divisor form, this is \mathbb{Z} \oplus \mathbb{Z}/2\mathbb{Z} \oplus \mathbb{Z}/3\mathbb{Z}.[1]
Other applications
Beyond solving Diophantine equations and classifying abelian groups, the Smith normal form finds use in algebraic topology for computing homology groups of spaces, which are finitely generated abelian groups. In combinatorics, it analyzes the critical group (or Laplacian integer kernel) of graphs, where the SNF of the Laplacian matrix yields the group's structure, aiding in enumerative combinatorics and chip-firing games. It also appears in number-theoretic problems involving integer matrices, such as in invariant theory and modular forms.[1][5]