HermiteDecomposition

HermiteDecomposition[m]

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

Details and Options

  • The result is given in the form {u,r} where u is a unimodular matrix, r is an upper-triangular matrix, and u.m==r.

Examples

open allclose all

Basic Examples  (1)

Decompose m into a unimodular matrix u and an upper-triangular matrix r:

The determinant of u has absolute value 1:

Confirm the decomposition:

Scope  (12)

Basic Uses (8)

Find the Hermite decomposition of an integer square matrix:

Format the result:

Hermite decomposition of a singular matrix:

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

Hermite decomposition for a rectangular matrix:

The square matrix u brings m into diagonal rectangular form:

Use HermiteDecomposition for a rational matrix:

Hermite decomposition for a Gaussian integer matrix:

Hermite decomposition for a Gaussian rational matrix m:

Hermite decomposition works only with rational matrices:

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

Special Matrices (4)

Find the Hermite decomposition for sparse matrices:

Hermite decompositions of structured matrices:

Hermite decomposition of an IdentityMatrix consists of two identity matrices:

Hermite decomposition of HilbertMatrix:

Applications  (3)

HermiteDecomposition can be used to determine if two integer lattices are equivalent. If the generators of the lattices are put in row matrices, the lattices are equal if and only if the matrices of the Hermite decompositions of the corresponding matrices are the same. Consider the lattices generated by , , and , , :

As the matrices of and are equal, the two sets of generators create the same lattice:

Confirm the result using LatticeReduce, which gives the same reduction up to overall sign:

Solve a linear Diophantine equation :

Form a homogenized system:

Rows of are integer combinations of rows of :

The second row of gives a solution of :

The last two rows of give a basis of solutions to the homogeneous equation :

Reduce uses HermiteDecomposition to solve linear Diophantine equations:

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

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

A second application, to TemplateBox[{{(, {r, _, 1}, )}}, Transpose], gives a another unimodular matrix and a diagonal matrix:

Compare , and TemplateBox[{vt}, Transpose] with the result given by SmithDecomposition:

Properties & Relations  (7)

HermiteDecomposition gives a unimodular matrix and an upper-triangular matrix:

The matrices satisfy the equation u.m==r:

Det of a unimodular matrix has absolute value 1:

Inverse of a unimodular integer matrix is an integer matrix:

For an matrix , the matrix of HermiteDecomposition[a] has the same dimensions:

The matrix as a square matrix:

The matrix always has 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:

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 entries of the matrix are non-negative:

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

The real parts can be negative:

Both HermiteDecomposition and QRDecomposition give unimodular and triangular matrices:

For HermiteDecomposition the decomposition is m=TemplateBox[{u}, Inverse].h and the matrices returned are integer:

For QRDecomposition the decomposition is m=TemplateBox[{q}, ConjugateTranspose].r and matrices returned can have any values:

Elements of form an upper-triangular basis of the lattice generated by the rows of m:

The inverse of provides an explicit representation of rows of m in terms of the basis:

LatticeReduce gives a basis consisting of shorter vectors:

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

Text

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

CMS

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

APA

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

BibTeX

@misc{reference.wolfram_2022_hermitedecomposition, author="Wolfram Research", title="{HermiteDecomposition}", year="2007", howpublished="\url{https://reference.wolfram.com/language/ref/HermiteDecomposition.html}", note=[Accessed: 30-September-2022 ]}

BibLaTeX

@online{reference.wolfram_2022_hermitedecomposition, organization={Wolfram Research}, title={HermiteDecomposition}, year={2007}, url={https://reference.wolfram.com/language/ref/HermiteDecomposition.html}, note=[Accessed: 30-September-2022 ]}