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 uppertriangular 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 is a unit:

Scope  (5)

A singular matrix m:

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

Rectangular matrices m:

A rational matrix m:

u is a unimodular integer matrix; r is an upper-triangular rational matrix:

A Gaussian integer matrix m:

u is a unimodular Gaussian integer matrix; r is an upper-triangular Gaussian integer matrix:

A Gaussian rational matrix m:

u is a unimodular Gaussian integer matrix; r is an upper-triangular Gaussian rational matrix:

Applications  (1)

Solve a linear Diophantine equation A.x==b:

Form a homogenized system:

Rows of r are integer combinations of rows of m:

The second row of r gives a solution of A.x==b:

The last two rows of r give a basis of solutions to the homogeneous equation A.x==0:

Reduce uses HermiteDecomposition to solve linear Diophantine equations:

Properties & Relations  (2)

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

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

Det of a unimodular matrix is a unit:

Inverse of a unimodular integer matrix is an integer matrix:

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

The inverse of u 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_2021_hermitedecomposition, author="Wolfram Research", title="{HermiteDecomposition}", year="2007", howpublished="\url{https://reference.wolfram.com/language/ref/HermiteDecomposition.html}", note=[Accessed: 08-December-2021 ]}

BibLaTeX

@online{reference.wolfram_2021_hermitedecomposition, organization={Wolfram Research}, title={HermiteDecomposition}, year={2007}, url={https://reference.wolfram.com/language/ref/HermiteDecomposition.html}, note=[Accessed: 08-December-2021 ]}