SmithDecomposition

SmithDecomposition[m]

gives the Smith normal form decomposition of an integer matrix m.

Details

  • The result is given in the form {u,r,v}, where u and v are unimodular matrices, r is a diagonal matrix with each diagonal entry dividing the next one, and u.m.vr.
  • The unimodular matrices u and v are integer matrices with Abs[Det[u]]1, and their inverses are also integer matrices.

Examples

open allclose all

Basic Examples  (1)

Decompose m into unimodular matrices u and v and a diagonal matrix r:

Each entry on the diagonal of r divides the successor:

The matrices u and v are unimodular, i.e. determinants are units:

Scope  (5)

An integer matrix:

The matrix r is integral and diagonal:

The u and v are integer, unimodular, and diagonalize m:

A Gaussian integer matrix:

The matrix r is Gaussian integral and diagonal:

The u and v are Gaussian integral unimodular and diagonalize m:

A rational matrix:

The matrix r is rational and diagonal:

Multiplying r with the LCM of denominators of m gives integers:

The u and v are integer, unimodular, and diagonalize m:

A Gaussian rational matrix:

The matrix r is Gaussian rational and diagonal:

u and v are Gaussian integral, unimodular, and diagonalize m:

SmithDecomposition works with non-square matrices:

The square matrices u and v bring m into diagonal rectangular form:

Applications  (3)

The Smith decomposition can be used to solve linear equations over the integers. Consider with and as follows:

As m=(TemplateBox[{u}, Inverse].r.TemplateBox[{v}, Inverse]), the equation m.x=(TemplateBox[{u}, Inverse].r.TemplateBox[{v}, Inverse]).x=b implies x=v.TemplateBox[{r}, Inverse].u.b:

Compare with the solution from Solve:

For an invertible , a solution exists if and only if the above process produces an integer result:

Use SmithDecomposition to compute the extended GCD of two integers and :

Let be the column matrix with entries and :

The Smith decomposition gives , with the unique positive , unimodular matrix:

Hence First[u].mFirst[r]:

But as the first row of is the and the left-hand side of the equation is , the foregoing equation is Bézout's identity. This means the extended GCD is:

Compare to ExtendedGCD:

Use SmithDecomposition to compute the right-extended GCDs of two matrices and :

Let be the matrix formed from the rows of and :

The matrix in the Smith decomposition will be a matrix:

Let and be the top-left and top-right quarters of :

The matrix and thus the matrix r.TemplateBox[{v}, Inverse] are, like , matrices:

Let denote the top half of r.TemplateBox[{v}, Inverse]:

The matrices m_a=a.TemplateBox[{g}, Inverse] and m_b=b.TemplateBox[{g}, Inverse] have integer entries:

Hence is a right divisor of both and :

Since the determinants of , , and obey gcd(TemplateBox[{a}, Det],TemplateBox[{b}, Det])=TemplateBox[{g}, Det], is in fact a right GCD:

Moreover, the first three rows of the Smith decomposition give Bézout's identity :

Hence, the extended right GCD is as follows:

Properties & Relations  (6)

The matrix in the decomposition is a square matrix, where is the number of rows of :

The matrix in the decomposition is a square matrix, where is the number of columns of :

The matrix in the decomposition is a diagonal, rectangular matrix of the same dimensions as :

The matrices and each have determinants of magnitude 1:

Each diagonal entry in divides its successor:

The Smith decomposition can often be found by two iterations of the Hermite decomposition:

The first use of HermiteDecomposition gives and an upper triangle matrix:

Applying HermiteDecomposition to the Transpose of the triangle matrix gives and :

Introduced in 2015
 (10.2)