Hermite normal form

Various authors may prefer to talk about Hermite normal form in either row-style or column-style. They are essentially the same up to transposition.

A matrix $A\; \backslash in\; \backslash mathbb\{Z\}^\{m\; \backslash times\; n\}$ has a (row) Hermite normal form $H$ if there is a square unimodular matrix $U$ where $H=UA$.

$H$ has the following restrictions:{{Cite web|url=http://doc.sagemath.org/html/en/reference/matrices/sage/matrix/matrix_integer_dense.html|title=Dense matrices over the integer ring — Sage Reference Manual v7.2: Matrices and Spaces of Matrices|website=doc.sagemath.org|access-date=2016-06-22}}{{Cite book | url=https://books.google.com/books?id=i3RktxvUgB8C|title=Almost Completely Decomposable Groups |last=Mader|first=A.|date=2000-03-09|publisher=CRC Press| isbn=9789056992255 | language=en}}{{Cite book|url=https://books.google.com/books?id=-HjrBwAAQBAJ|title=Complexity of Lattice Problems: A Cryptographic Perspective | last1=Micciancio|first1=Daniele|last2=Goldwasser|first2=Shafi|date=2012-12-06|publisher=Springer Science & Business Media|isbn=9781461508977|language=en}}

1. $H$ is upper triangular (that is, $h\_\{ij\}=0$ for $i>j$), and any rows of zeros are located below any other row.
2. The leading coefficient (the first nonzero entry from the left, also called the pivot) of a nonzero row is always strictly to the right of the leading coefficient of the row above it; moreover, it is positive.
3. The elements below pivots are zero and elements above pivots are nonnegative and strictly smaller than the pivot.

The third condition is not standard among authors, for example some sources force non-pivots to be nonpositive{{Cite web| url=http://mathworld.wolfram.com/HermiteNormalForm.html |title=Hermite Normal Form|last=Weisstein | first = Eric W.| website=mathworld.wolfram.com|language=en|access-date=2016-06-22}}{{Cite book|url=https://books.google.com/books?id=4DwAX3-3ovQC|title=Computer Aided Verification: 21st International Conference, CAV 2009, Grenoble, France, June 26 - July 2, 2009, Proceedings|last1=Bouajjani|first1=Ahmed|last2=Maler|first2=Oded|date=2009-06-19|publisher=Springer Science & Business Media|isbn=9783642026577|language=en}} or place no sign restriction on them.{{Cite web|url=http://www.mathworks.com/help/symbolic/mupad_ref/linalg-hermiteform.html|title=Hermite normal form of a matrix - MuPAD|website=www.mathworks.com|access-date=2016-06-22|archive-date=2019-02-17|archive-url=https://web.archive.org/web/20190217142212/https://www.mathworks.com/help/symbolic/mupad_ref/linalg-hermiteform.html|url-status=dead}} However, these definitions are equivalent by using a different unimodular matrix $U$. A unimodular matrix is a square integer matrix whose determinant is 1 or −1 (and hence invertible). In fact, a unimodular matrix is invertible over the integers, as can be seen, for example, from Cramer's Rule.

A matrix $A\; \backslash in\; \backslash mathbb\{Z\}^\{m\; \backslash times\; n\}$ has a (column) Hermite normal form $H$ if there is a square unimodular matrix $U$ where $H=AU$ and $H$ has the following restrictions:{{Cite book|url=https://books.google.com/books?id=c_7xBwAAQBAJ|title=Large Scale Linear and Integer Optimization: A Unified Approach|last=Martin|first=Richard Kipp|date=2012-12-06|publisher=Springer Science & Business Media|isbn=9781461549758|language=en}}

1. $H$ is lower triangular ($h\_\{ij\}=0$ for
2. The leading coefficient (the first nonzero entry from the top, also called the pivot) of a nonzero column is always strictly below of the leading coefficient of the column before it; moreover, it is positive.d
3. The elements to the right of pivots are zero and elements to the left of pivots are nonnegative and strictly smaller than the pivot.

Note that the row-style definition has a unimodular matrix $U$ multiplying $A$ on the left (meaning $U$ is acting on the rows of $A$), while the column-style definition has the unimodular matrix action on the columns of $A$. The two definitions of Hermite normal forms are simply transposes of each other.

Every full row rank m-by-n matrix A with integer entries has a unique m-by-n matrix H in Hermite normal form, such that H=UA for some square unimodular matrix U.{{Cite book|url=https://books.google.com/books?id=zEzW5mhppB8C|title=Theory of Linear and Integer Programming|last=Schrijver| first=Alexander | date=1998-07-07|publisher=John Wiley & Sons|isbn=9780471982326|language=en}}{{Cite book|url=https://books.google.com/books?id=5TP6CAAAQBAJ | title=A Course in Computational Algebraic Number Theory|last=Cohen|first=Henri|date=2013-04-17|publisher=Springer Science & Business Media| isbn=9783662029459 | language=en}}

In the examples below, {{mvar|H}} is the Hermite normal form of the matrix {{mvar|A}}, and {{mvar|U}} is a unimodular matrix such that {{math|1=UA = H}}.

A=\begin{pmatrix}

3 & 3 & 1 & 4 \\

0 & 1 & 0 & 0 \\

0 & 0 & 19 & 16 \\

0 & 0 & 0 & 3

\end{pmatrix}

\qquad

H=\begin{pmatrix}

3 & 0 & 1 & 1\\

0 & 1 & 0 & 0\\

0 & 0 &19 & 1\\

0 & 0 & 0 & 3

\end{pmatrix}

\qquad

U = \left(\begin{array}{rrrr}

1 & -3 & 0 & -1 \\

0 & 1 & 0 & 0 \\

0 & 0 & 1 & -5 \\

0 & 0 & 0 & 1

\end{array}\right)

A = \begin{pmatrix}

2 & 3 & 6 & 2 \\

5 & 6 & 1 & 6 \\

8 & 3 & 1 & 1

\end{pmatrix}

\qquad

H = \left(\begin{array}{rrrr}

1 & 0 & 50 & -11 \\

0 & 3 & 28 & -2 \\

0 & 0 & 61 & -13

\end{array}\right)

\qquad

U = \left(\begin{array}{rrr}

9 & -5 & 1 \\

5 & -2 & 0 \\

11 & -6 & 1

\end{array}\right)

If {{mvar|A}} has only one row then either {{math|1=H = A}} or {{math|1=H = −A}}, depending on whether the single row of {{mvar|A}} has a positive or negative leading coefficient.

There are many algorithms for computing the Hermite normal form, dating back to 1851. One such algorithm is described in.{{Cite Geometric Algorithms and Combinatorial Optimization}}{{Rp|page=|pages=43--45}} But only in 1979 an algorithm for computing the Hermite normal form that ran in strongly polynomial time was first developed;{{Cite journal|last1=Kannan|first1=R.|last2=Bachem|first2=A.|date=1979-11-01|title=Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix|url=http://www.math.tamu.edu/~rojas/kannanbachemhermitesmith79.pdf|journal=SIAM Journal on Computing| volume=8|issue=4|pages=499–507|doi=10.1137/0208040|issn=0097-5397}} that is, the number of steps to compute the Hermite normal form is bounded above by a polynomial in the dimensions of the input matrix, and the space used by the algorithm (intermediate numbers) is bounded by a polynomial in the binary encoding size of the numbers in the input matrix.

One class of algorithms is based on Gaussian elimination in that special elementary matrices are repeatedly used.{{Cite web| url=http://www.ifor.math.ethz.ch/teaching/lectures/integer_prog_ss10/chapter02|title=Euclidean Algorithm and Hermite Normal Form|date=2 March 2010|access-date=25 June 2015 | archive-url=https://web.archive.org/web/20160807042503/http://www.ifor.math.ethz.ch/teaching/lectures/integer_prog_ss10/chapter02|archive-date=7 August 2016|url-status=dead}}{{Cite book|chapter-url=https://books.google.com/books?id=c_7xBwAAQBAJ|title=Large Scale Linear and Integer Optimization: A Unified Approach| last=Martin|first=Richard Kipp|date=2012-12-06|publisher=Springer Science & Business Media|isbn=9781461549758|language=en|chapter=Chapter 4.2.4 Hermite Normal Form}} The LLL algorithm can also be used to efficiently compute the Hermite normal form.{{Cite book|chapter-url=https://books.google.com/books?id=XGjMBQAAQBAJ|title=Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications|last=Bremner|first=Murray R.| date=2011-08-12|publisher=CRC Press|isbn=9781439807040|language=en|chapter=Chapter 14: The Hermite Normal Form}}{{Cite journal|last1=Havas|first1=George| last2=Majewski|first2=Bohdan S.|last3=Matthews|first3=Keith R.|date=1998|title=Extended GCD and Hermite normal form algorithms via lattice basis reduction| url=https://projecteuclid.org/euclid.em/1048515660|journal=Experimental Mathematics|volume=7|issue=2|pages=130–131|doi=10.1080/10586458.1998.10504362|s2cid=263873475 |issn=1058-6458}}

A typical lattice in Rⁿ has the form $$

L = \left\{\left. \sum_{i=1}^n \alpha_i \mathbf a_i \; \right\vert \; \alpha_i \in{\textbf Z} \right\}

where the a_i are in Rⁿ. If the columns of a matrix A are the a_i, the lattice can be associated with the columns of a matrix, and A is said to be a basis of L. Because the Hermite normal form is unique, it can be used to answer many questions about two lattice descriptions. For what follows, $L\_A$ denotes the lattice generated by the columns of A. Because the basis is in the columns of the matrix A, the column-style Hermite normal form must be used. Given two bases for a lattice, A and A', the equivalence problem is to decide if $L\_\{A\}\; =\; L\_\{A\text{'}\}.$ This can be done by checking if the column-style Hermite normal form of A and A' are the same up to the addition of zero columns. This strategy is also useful for deciding if a lattice is a subset ($L\_\{A\}\; \backslash subseteq\; L\_\{A\text{'}\}$ if and only if $L\_\{[A\; \backslash mid\; A\text{'}]\}\; =\; L\_\{A\text{'}\}$), deciding if a vector v is in a lattice ($v\; \backslash in\; L\_\{A\}$ if and only if $L\_\{[v\; \backslash mid\; A]\}\; =\; L\_A$), and for other calculations.{{Cite web|url=https://cseweb.ucsd.edu/classes/sp14/cse206A-a/lec4.pdf|title=Basic Algorithms | last=Micciancio|first=Daniele|access-date=25 June 2016}}

The linear system {{math|1=Ax = b}} has an integer solution {{math|x}} if and only if the system {{math|1=Hy = b}} has an integer solution {{math|y}} where {{math|1=y = U⁻¹x}} and {{math|H}} is the column-style Hermite normal form of {{math|A}}. Checking that {{math|1=Hy = b}} has an integer solution is easier than {{math|1=Ax = b}} because the matrix {{math|H}} is triangular.{{Rp|55}}

Many mathematical software packages can compute the Hermite normal form:

• Maple with [https://www.maplesoft.com/support/help/maple/view.aspx?path=LinearAlgebra%2FHermiteForm HermiteForm]
• MATLAB with [http://www.mathworks.com/help/symbolic/hermiteform.html hermiteForm]
• NTL with [http://www.shoup.net/ntl/doc/HNF.cpp.html HNF]
• PARI/GP with [https://pari.math.u-bordeaux.fr/dochtml/html-stable/Vectors__matrices__linear_algebra_and_sets.html#mathnf mathnf]
• SageMath with [http://doc.sagemath.org/html/en/reference/matrices/sage/matrix/matrix_integer_dense.html#sage.matrix.matrix_integer_dense.Matrix_integer_dense.hermite_form hermite_form]
• {{WolframAlpha |id=HermiteDecomposition |title=HermiteDecomposition}}{{cite url|author=Wolfram Research|title=HermiteDecomposition|year=2007 |url=https://reference.wolfram.com/language/ref/HermiteDecomposition.html

|quote=HermiteDecomposition[m] gives the Hermite normal form decomposition of an integer matrix {{mono|m}}.

|access-date={{date|06-March-2025}}}}

Hermite normal form can be defined when we replace Z by an arbitrary Dedekind domain.{{cite book |last1=Cohen |first1=Henri |title=Advanced Topics in Computational Number Theory |date=1999 |publisher=Springer |isbn=0-387-98727-4 | at=§1.4.2}} (for instance, any principal-ideal domain). For instance, in control theory it can be useful to consider Hermite normal form for the polynomials {{math|F[x]}} over a given field {{math|F}}.

• Hermite ring
• Smith normal form
• Howell normal form
• Diophantine equation

{{reflist}}

Category:Linear algebra

Category:Matrix normal forms