# SmithDecomposition

gives the Smith normal form decomposition of an integer matrix .

# Details • The result is given in the form , where and are unimodular matrices, 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 , the equation implies :

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 are, like , matrices:

Let denote the top half of :

The matrices and have integer entries:

Hence is a right divisor of both and :

Since the determinants of , , and obey , 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)