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:

The determinants of u and v have absolute value 1:

Each entry on the diagonal of r divides the successor:

Confirm the decomposition:

Scope  (12)

Basic Uses (8)

Find the Smith decomposition of an integer square matrix:

Format the result:

Smith decomposition of a singular matrix:

The number of nonzero rows in r is equal to the rank of m:

Smith decomposition for a rectangular matrix:

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

Use SmithDecomposition with a rational matrix:

Smith decomposition for a Gaussian integer matrix:

Smith decomposition for a Gaussian rational matrix:

Smith decomposition works only with rational matrices:

The Smith decomposition for a large, integer matrix is computed efficiently:

Special Matrices (4)

Find the Smith decomposition for sparse matrices:

Smith decompositions of structured matrices:

Smith decomposition of an IdentityMatrix consists of three identity matrices:

Smith decomposition of HilbertMatrix:

Applications  (4)

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:

The Smith decomposition gives a canonical representation for finitely generated Abelian groups. Consider the quotient group of integer 2vectors modulo the relations and . That is to say, consider two points in the plane equivalent if they differ by integer multiples of the vectors and . Compute the Smith decomposition of the matrix whose rows are the :

From it can be seen that the structure of the group is , or simply as is the trivial group:

Hence, every point on the plane is equivalent to one of the nine points . Consider the point . To find the canonical representative of , rotate into the diagonal basis using on the right and compute the modulus with respect to the diagonal entries of :

The point is equivalent to , so it should map to the same canonical representative, and it does:

Thus, every integer point in the plane can be reduced to a canonical representative. Conversely, the matrix TemplateBox[{v}, Inverse] can be viewed as mapping the canonical basis to the starting basis. As the lattice generated by and is simply the set of all points equivalent to the origin, rotating that lattice by TemplateBox[{v}, Inverse] will produce the same lattice as generated by and :

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  (9)

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:

The and matrices always have integer values, irrespective of whether the input is integer or rational:

This extends to the real and imaginary parts of the result if the input matrix is complex:

Each diagonal entry in divides its successor:

The matrix has integer values if the input matrix is integer:

If the input matrix has noninteger rational elements, so will the matrix:

For a real-valued input, the diagonal entries of the matrix are non-negative:

For complex-valued input, the real and imaginary parts of the entries are non-negative:

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

The first use of HermiteDecomposition gives and an upper-triangular matrix:

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

Wolfram Research (2015), SmithDecomposition, Wolfram Language function, https://reference.wolfram.com/language/ref/SmithDecomposition.html.

Text

Wolfram Research (2015), SmithDecomposition, Wolfram Language function, https://reference.wolfram.com/language/ref/SmithDecomposition.html.

CMS

Wolfram Language. 2015. "SmithDecomposition." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/SmithDecomposition.html.

APA

Wolfram Language. (2015). SmithDecomposition. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/SmithDecomposition.html

BibTeX

@misc{reference.wolfram_2022_smithdecomposition, author="Wolfram Research", title="{SmithDecomposition}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/SmithDecomposition.html}", note=[Accessed: 28-November-2022 ]}

BibLaTeX

@online{reference.wolfram_2022_smithdecomposition, organization={Wolfram Research}, title={SmithDecomposition}, year={2015}, url={https://reference.wolfram.com/language/ref/SmithDecomposition.html}, note=[Accessed: 28-November-2022 ]}