Hermite normal form

In linear algebra, the Hermite normal form is an analogue of reduced echelon form for matrices over the integers Z. Just as reduced echelon form can be used to solve problems about the solution to the linear system Ax=b where x is in Rⁿ, the Hermite normal form can solve problems about the solution to the linear system Ax=b where this time x is restricted to have integer coordinates only. Other applications of the Hermite normal form include integer programming,^[1] and cryptography,^[2] and abstract algebra.^[3]

Definition

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.

Row-style Hermite Normal Form

An m by n matrix A with integer entries has a (row) Hermite normal form (HNF) H if there is a square unimodular matrix U where H=U*A and H has the following restrictions:^[4]^[5]^[6]

H is upper triangular, h_ij = 0 for i > j', and any rows of zeros are located below any other row.
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.
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^[7]^[8] or place no sign restriction on them.^[9] However, these definitions are equivalent by using a different unimodular matrix U. A unimodular matrix is a square invertible integer matrix whose determinant is 1 or -1.

Column-style Hermite Normal Form

A m by n matrix A with integer entries has a (column) Hermite normal form (HNF) H if there is a square unimodular matrix U where H=A*U and H has the following restrictions:^[8]^[10]

H is lower triangular, h_ij = 0 for i < j, and any columns of zeros are located on the right.
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.
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.

Existence and uniqueness of the Hermite normal form

For every m by n matrix A with integer entries has a unique m by n matrix H (HNF), such that H=UA for some square unimodular matrix U.^[5]^[11]^[12]

Examples

In the examples below, H is the Hermite normal form of the matrix A, and U is a unimodular matrix such that 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}0&0&5&0&1&4\\0&0&0&-1&-4&99\\0&0&0&20&19&16\\0&0&0&0&2&1\\0&0&0&0&0&3\\0&0&0&0&0&0\end{pmatrix}}\qquad H={\begin{pmatrix}0&0&5&0&0&2\\0&0&0&1&0&1\\0&0&0&0&1&2\\0&0&0&0&0&3\\0&0&0&0&0&0\\0&0&0&0&0&0\\\end{pmatrix}}\qquad U=\left({\begin{array}{rrrrrr}1&20&1&30&-676&0\\0&39&2&59&-1317&0\\0&20&1&31&-675&0\\0&0&0&0&1&0\\0&40&2&61&-1351&0\\0&0&0&0&0&1\end{array}}\right)$

$A=\left({\begin{array}{rrrr}2&3&6&2\\5&6&1&6\\8&3&1&1\end{array}}\right)\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 A has only one row then either H = A or H = -A, depending on whether the single row of A has a positive or negative leading coefficient.

Algorithms

There are many algorithms for computing the Hermite normal form dating back to 1851. It was not until 1979 when an algorithm for computing the Hermite normal form that ran in strongly polynomial time was first developed;^[13] 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.^[11]^[14]^[15] The LLL algorithm can also be used to efficiently compute the Hermite normal form.^[16]

Applications

Lattice calculations

A typical lattice in Rⁿ has the form $L=\left\{\left.\sum _{i=1}^{n}\alpha _{i}a_{i}\;\right\vert \;\alpha _{i}\in {\mathbb {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 basis for a lattice, A and A', the equivalence problem is to decide if $L_{A}=L_{A'}.$ 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}\subseteq L_{A'}$ if and only if $L_{[A\mid A']}=L_{A'}$ ), deciding if a vector v is in a lattice ( $v\in L_{A}$ if and only if $L_{[v\mid A]}=L_{A}$ ), and for other calculations.^[17]

Integer solutions to linear systems

The linear system Ax=b has an integer solution x if and only if the system Hy=b has an integer solution y where Uy=x and H is the column-style Hermit normal form of H.^[11]^:55 Checking that Hy=b has an integer solution is easier than Ax=b because the matrix H is triangular.

Implementations

Many mathematical software packages can compute the Hermite normal form

References

↑ Hung, Ming S.; Rom, Walter O. (1990-10-15). "An application of the Hermite normal form in integer programming". Linear Algebra and its Applications. 140: 163–179. doi:10.1016/0024-3795(90)90228-5.
↑ Evangelos, Tourloupis, Vasilios (2013-01-01). "Hermite normal forms and its cryptographic applications". University of Wollongong.
↑ Adkins, William; Weintraub, Steven (2012-12-06). Algebra: An Approach via Module Theory. Springer Science & Business Media. p. 306. ISBN 9781461209232.
↑ "Dense matrices over the integer ring — Sage Reference Manual v7.2: Matrices and Spaces of Matrices". doc.sagemath.org. Retrieved 2016-06-22.
1 2 Mader, A. (2000-03-09). Almost Completely Decomposable Groups. CRC Press. ISBN 9789056992255.
↑ Micciancio, Daniele; Goldwasser, Shafi (2012-12-06). Complexity of Lattice Problems: A Cryptographic Perspective. Springer Science & Business Media. ISBN 9781461508977.
↑ W., Weisstein, Eric. "Hermite Normal Form". mathworld.wolfram.com. Retrieved 2016-06-22.
1 2 Bouajjani, Ahmed; Maler, Oded (2009-06-19). Computer Aided Verification: 21st International Conference, CAV 2009, Grenoble, France, June 26 - July 2, 2009, Proceedings. Springer Science & Business Media. ISBN 9783642026577.
↑ "Hermite normal form of a matrix - MuPAD". www.mathworks.com. Retrieved 2016-06-22.
↑ Martin, Richard Kipp (2012-12-06). Large Scale Linear and Integer Optimization: A Unified Approach. Springer Science & Business Media. ISBN 9781461549758.
1 2 3 Schrijver, Alexander (1998-07-07). Theory of Linear and Integer Programming. John Wiley & Sons. ISBN 9780471982326.
↑ Cohen, Henri (2013-04-17). A Course in Computational Algebraic Number Theory. Springer Science & Business Media. ISBN 9783662029459.
↑ Kannan, R.; Bachem, A. (1979-11-01). "Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix" (PDF). SIAM Journal on Computing. 8 (4): 499–507. doi:10.1137/0208040. ISSN 0097-5397.
↑ "Euclidean Algorithm and Hermite Normal Form". 2 March 2010. Retrieved 25 June 2015.
↑ Martin, Richard Kipp (2012-12-06). "Chapter 4.2.4 Hermite Normal Form". Large Scale Linear and Integer Optimization: A Unified Approach. Springer Science & Business Media. ISBN 9781461549758.
↑ Bremner, Murray R. (2011-08-12). "Chapter 14: The Hermite Normal Form". Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications. CRC Press. ISBN 9781439807040.
↑ Micciancio, Daniele. "Basic Algorithms" (PDF). Retrieved 25 June 2016.

This article is issued from Wikipedia - version of the 8/21/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.