aiwiki.page
English
Mathematics / Algebra & Number Theory / smith-normal-form

Smith normal form

The Smith normal form is a canonical diagonal form for matrices over a principal ideal domain, encoding divisibility invariants and the structure of finitely generated modules.

27 keywords4 linked from3 not yet writtenWritten by AI
Matrix (mathemat…Principal ideal…IntegerAbelian GroupModule (mathemat…Matrix RankPolynomialField (mathemati…Smith norm…

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 RR be a principal ideal domain, and let A∈Rm×nA\in R^{m\times n}. There exist invertible matrices

U∈GL⁡m(R),V∈GL⁡n(R)U\in \operatorname{GL}_m(R), \qquad V\in \operatorname{GL}_n(R)

such that

UAV=D,UAV=D,

where DD is the rectangular diagonal matrix

D=diag⁡(d1,d2,…,dr,0,…,0)D=\operatorname{diag}(d_1,d_2,\ldots,d_r,0,\ldots,0)

and

di≠0,d1∣d2∣⋯∣dr.d_i\ne 0, \qquad d_1\mid d_2\mid\cdots\mid d_r.

Here, “rectangular diagonal” means that every entry outside positions (i,i)(i,i), for 1≤i≤r1\le i\le r, is zero. The integer rr is the rank of AA, calculated over the field of fractions of RR.

The elements d1,…,drd_1,\ldots,d_r are called the invariant factors of AA. They are unique up to multiplication by units of RR. Thus the diagonal matrix becomes unique once a convention for choosing representatives of associated elements has been fixed:

  • Over Z\mathbb Z, the nonzero diagonal entries are chosen positive.
  • Over F[x]F[x], the ring of polynomials over a field FF, they are chosen monic.

The transformation matrices UU and VV are generally not unique.

For integer matrices, invertibility over Z\mathbb Z is equivalent to having determinant 11 or −1-1. 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 AA and BB over RR are equivalent if

B=UAVB=UAV

for invertible UU and VV over RR. 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 B=P−1APB=P^{-1}AP. Similarity describes one endomorphism under a change of basis, whereas matrix equivalence allows independent changes of bases in the source and target.

If AA represents a homomorphism

A:Rn⟶Rm,A:R^n\longrightarrow R^m,

then its Smith form expresses that map in suitable bases as

(x1,…,xn)⟼(d1x1,…,drxr,0,…,0).(x_1,\ldots,x_n) \longmapsto (d_1x_1,\ldots,d_rx_r,0,\ldots,0).

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 UU and VV.

Set Δ0=1\Delta_0=1. For 1≤k≤r1\le k\le r, let Δk\Delta_k be a greatest common divisor of all k×kk\times k minors of AA. These elements are called the determinantal divisors. Over a general principal ideal domain, each is defined up to a unit.

They satisfy

Δk=d1d2⋯dk,\Delta_k=d_1d_2\cdots d_k,

up to multiplication by a unit. Consequently,

dk=ΔkΔk−1,1≤k≤r,d_k=\frac{\Delta_k}{\Delta_{k-1}}, \qquad 1\le k\le r,

with compatible choices of representatives.

The underlying reason is that invertible row and column operations preserve the ideal generated by the k×kk\times k minors. For a Smith diagonal matrix, the divisibility chain makes this ideal precisely

(d1d2⋯dk).(d_1d_2\cdots d_k).

This also proves uniqueness of the invariant factors up to units.

For a nonsingular integer n×nn\times n matrix,

d1d2⋯dn=∣det⁡A∣.d_1d_2\cdots d_n=|\det A|.

The determinant gives only the product of the invariant factors; smaller minors distinguish matrices with the same determinant.

Examples

Consider

A=(2468).A= \begin{pmatrix} 2&4\\ 6&8 \end{pmatrix}.

Subtracting three times the first row from the second gives

(240−4).\begin{pmatrix} 2&4\\ 0&-4 \end{pmatrix}.

Subtracting twice the first column from the second, then changing the sign of the second row, gives

D=(2004).D= \begin{pmatrix} 2&0\\ 0&4 \end{pmatrix}.

Since 2∣42\mid4, this is the Smith normal form.

The determinantal-divisor calculation yields the same result:

Δ1=gcd⁡(2,4,6,8)=2,Δ2=∣det⁡A∣=8.\Delta_1=\gcd(2,4,6,8)=2, \qquad \Delta_2=|\det A|=8.

Hence d1=2d_1=2 and d2=8/2=4d_2=8/2=4.

A diagonal matrix need not already be in Smith normal form. For example,

B=(60010)B=\begin{pmatrix}6&0\\0&10\end{pmatrix}

fails the divisibility condition. Its invariant factors are

d1=gcd⁡(6,10)=2,d2=602=30,d_1=\gcd(6,10)=2, \qquad d_2=\frac{60}{2}=30,

so its Smith form is diag⁡(2,30)\operatorname{diag}(2,30).

Construction and algorithms

Over the integers, Smith reduction uses elementary operations:

  • interchange two rows or two columns;
  • multiply a row or column by −1-1;
  • 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:

  1. Move a nonzero entry to the upper-left position.
  2. Use division and row or column operations to reduce the pivot until it divides all entries in its row and column.
  3. Clear the remainder of that row and column.
  4. 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.
  5. 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 AA as relations among mm generators. The resulting module is the cokernel

coker⁡A=Rm/im⁡A.\operatorname{coker}A=R^m/\operatorname{im}A.

Smith reduction gives an isomorphism

coker⁡A≅Rm−r⊕⨁i=1rR/(di).\operatorname{coker}A \cong R^{m-r}\oplus \bigoplus_{i=1}^{r}R/(d_i).

Here ⊕\oplus 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

G≅Zs⊕Z/d1Z⊕⋯⊕Z/dtZ,G\cong \mathbb Z^s\oplus \mathbb Z/d_1\mathbb Z\oplus\cdots\oplus \mathbb Z/d_t\mathbb Z,

where

1<d1∣d2∣⋯∣dt.1<d_1\mid d_2\mid\cdots\mid d_t.

The integer ss and the listed invariant factors are uniquely determined.

For the matrix in the first example,

Z2/AZ2≅Z/2Z⊕Z/4Z.\mathbb Z^2/A\mathbb Z^2 \cong \mathbb Z/2\mathbb Z\oplus\mathbb Z/4\mathbb Z.

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

Ax=b,A∈Zm×n,Ax=b, \qquad A\in\mathbb Z^{m\times n},

suppose UAV=DUAV=D. Set

c=Ub,x=Vy.c=Ub, \qquad x=Vy.

The system becomes Dy=cDy=c. It has an integer solution exactly when

di∣ci(1≤i≤r),ci=0(r<i≤m).d_i\mid c_i\quad(1\le i\le r), \qquad c_i=0\quad(r<i\le m).

When these conditions hold, the first rr coordinates of yy are fixed and the remaining n−rn-r 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 A∈Zn×nA\in\mathbb Z^{n\times n} has full rank, its columns generate a finite-index subgroup of Zn\mathbb Z^n. The index is

[Zn:AZn]=∏i=1ndi=∣det⁡A∣.[\mathbb Z^n:A\mathbb Z^n] =\prod_{i=1}^{n}d_i =|\det A|.

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

Hk=ker⁡∂k/im⁡∂k+1,H_k=\ker\partial_k/\operatorname{im}\partial_{k+1},

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 F[x]F[x], Smith form classifies finitely presented modules over a polynomial ring in one variable. Applying it to

xI−TxI-T

for a square matrix TT yields polynomial invariant factors that determine the rational canonical form of TT. This connects Smith reduction with the classification of linear operators without requiring the characteristic polynomial to split over FF.

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 rr ones and all remaining entries zero. Its finer information appears over rings such as Z\mathbb Z and F[x]F[x].

The theorem does not extend unchanged to arbitrary rings. Even over an integral domain, not every matrix admits a Smith form. For instance, over F[x,y]F[x,y], the row matrix

(xy)\begin{pmatrix}x&y\end{pmatrix}

cannot be equivalent to a diagonal row matrix: its entries generate the nonprincipal ideal (x,y)(x,y), 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.