Hermite normal form

Last updated

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 Rn, 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] cryptography, [2] and abstract algebra. [3]

Contents

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 H if there is a square unimodular matrix U where H=UA and H has the following restrictions: [4] [5] [6]

  1. H is upper triangular (that is, hij = 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 [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 H if there is a square unimodular matrix U where H=AU and H has the following restrictions: [8] [10]

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

Existence and uniqueness of the Hermite normal form

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. [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.

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. One such algorithm is described in. [13] : 43--45  But only in 1979 an algorithm for computing the Hermite normal form that ran in strongly polynomial time was first developed; [14] 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] [15] [16] The LLL algorithm can also be used to efficiently compute the Hermite normal form. [17] [18]

Applications

Lattice calculations

A typical lattice in Rn has the form where the ai are in Rn. If the columns of a matrix A are the ai, 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, 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 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 ( if and only if ), deciding if a vector v is in a lattice ( if and only if ), and for other calculations. [19]

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 y = U−1x and H is the column-style Hermite normal form of A. Checking that Hy = b has an integer solution is easier than Ax = b because the matrix H is triangular. [11] : 55 

Implementations

Many mathematical software packages can compute the Hermite normal form:

Over an arbitrary Dedekind domain

Hermite normal form can be defined when we replace Z by an arbitrary Dedekind domain. [20] (for instance, any principal-ideal domain). For instance, in control theory it can be useful to consider Hermite normal form for the polynomials F[x] over a given field F.

See also

Related Research Articles

In mathematics, the determinant is a scalar-valued function of the entries of a square matrix. The determinant of a matrix A is commonly denoted det(A), det A, or |A|. Its value characterizes some properties of the matrix and the linear map represented, on a given basis, by the matrix. In particular, the determinant is nonzero if and only if the matrix is invertible and the corresponding linear map is an isomorphism.

<span class="mw-page-title-main">Diophantine equation</span> Polynomial equation whose integer solutions are sought

In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, for which only integer solutions are of interest. A linear Diophantine equation equates to a constant the sum of two or more monomials, each of degree one. An exponential Diophantine equation is one in which unknowns can appear in exponents.

<span class="mw-page-title-main">Gaussian elimination</span> Algorithm for solving systems of linear equations

In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of row-wise operations performed on the corresponding matrix of coefficients. This method can also be used to compute the rank of a matrix, the determinant of a square matrix, and the inverse of an invertible matrix. The method is named after Carl Friedrich Gauss (1777–1855). To perform row reduction on a matrix, one uses a sequence of elementary row operations to modify the matrix until the lower left-hand corner of the matrix is filled with zeros, as much as possible. There are three types of elementary row operations:

Magma is a computer algebra system designed to solve problems in algebra, number theory, geometry and combinatorics. It is named after the algebraic structure magma. It runs on Unix-like operating systems, as well as Windows.

In linear algebra, the Cholesky decomposition or Cholesky factorization is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose, which is useful for efficient numerical solutions, e.g., Monte Carlo simulations. It was discovered by André-Louis Cholesky for real matrices, and posthumously published in 1924. When it is applicable, the Cholesky decomposition is roughly twice as efficient as the LU decomposition for solving systems of linear equations.

In linear algebra, an n-by-n square matrix A is called invertible if there exists an n-by-n square matrix B such thatwhere In denotes the n-by-n identity matrix and the multiplication used is ordinary matrix multiplication. If this is the case, then the matrix B is uniquely determined by A, and is called the (multiplicative) inverse of A, denoted by A−1. Matrix inversion is the process of finding the matrix which when multiplied by the original matrix gives the identity matrix.

In linear algebra, a matrix is in row echelon form if it can be obtained as the result of Gaussian elimination. Every matrix can be put in row echelon form by applying a sequence of elementary row operations. The term echelon comes from the French échelon, and refers to the fact that the nonzero entries of a matrix in row echelon form look like an inverted staircase.

In mathematics, and in particular linear algebra, the Moore–Penrose inverse⁠⁠ of a matrix ⁠⁠, often called the pseudoinverse, is the most widely known generalization of the inverse matrix. It was independently described by E. H. Moore in 1920, Arne Bjerhammar in 1951, and Roger Penrose in 1955. Earlier, Erik Ivar Fredholm had introduced the concept of a pseudoinverse of integral operators in 1903. The terms pseudoinverse and generalized inverse are sometimes used as synonyms for the Moore–Penrose inverse of a matrix, but sometimes applied to other elements of algebraic structures which share some but not all properties expected for an inverse element.

In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming.

In mathematics the determinant of an m×m skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries, a polynomial with integer coefficients that only depends on m. When m is odd, the polynomial is zero. When m is even, it is a nonzero polynomial of degree m/2, and is unique up to multiplication by ±1. The convention on skew-symmetric tridiagonal matrices, given below in the examples, then determines one specific polynomial, called the Pfaffian polynomial. The value of this polynomial, when applied to the entries of a skew-symmetric matrix, is called the Pfaffian of that matrix. The term Pfaffian was introduced by Cayley, who indirectly named them after Johann Friedrich Pfaff.

In mathematics, a unimodular matrixM is a square integer matrix having determinant +1 or −1. Equivalently, it is an integer matrix that is invertible over the integers: there is an integer matrix N that is its inverse. Thus every equation Mx = b, where M and b both have integer components and M is unimodular, has an integer solution. The n × n unimodular matrices form a group called the n × n general linear group over , which is denoted .

In mathematics, the Smith normal form is a normal form that can be defined for any matrix with entries in a principal ideal domain (PID). The Smith normal form of a matrix is diagonal, and can be obtained from the original matrix by multiplying on the left and right by invertible square matrices. In particular, the integers are a PID, so one can always calculate the Smith normal form of an integer matrix. The Smith normal form is very useful for working with finitely generated modules over a PID, and in particular for deducing the structure of a quotient of a free module. It is named after the Irish mathematician Henry John Stephen Smith.

A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1)-matrix is a matrix with entries from the Boolean domain B = {0, 1}. Such a matrix can be used to represent a binary relation between a pair of finite sets. It is an important tool in combinatorial mathematics and theoretical computer science.

In numerical linear algebra, the Jacobi eigenvalue algorithm is an iterative method for the calculation of the eigenvalues and eigenvectors of a real symmetric matrix. It is named after Carl Gustav Jacob Jacobi, who first proposed the method in 1846, but only became widely used in the 1950s with the advent of computers.

In numerical analysis and linear algebra, lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix. The product sometimes includes a permutation matrix as well. LU decomposition can be viewed as the matrix form of Gaussian elimination. Computers usually solve square systems of linear equations using LU decomposition, and it is also a key step when inverting a matrix or computing the determinant of a matrix. The LU decomposition was introduced by the Polish astronomer Tadeusz Banachiewicz in 1938. To quote: "It appears that Gauss and Doolittle applied the method [of elimination] only to symmetric equations. More recent authors, for example, Aitken, Banachiewicz, Dwyer, and Crout … have emphasized the use of the method, or variations of it, in connection with non-symmetric problems … Banachiewicz … saw the point … that the basic problem is really one of matrix factorization, or “decomposition” as he called it." It is also sometimes referred to as LR decomposition.

Numerical linear algebra, sometimes called applied linear algebra, is the study of how matrix operations can be used to create computer algorithms which efficiently and accurately provide approximate answers to questions in continuous mathematics. It is a subfield of numerical analysis, and a type of linear algebra. Computers use floating-point arithmetic and cannot exactly represent irrational data, so when a computer algorithm is applied to a matrix of data, it can sometimes increase the difference between a number stored in the computer and the true number that it is an approximation of. Numerical linear algebra uses properties of vectors and matrices to develop computer algorithms that minimize the error introduced by the computer, and is also concerned with ensuring that the algorithm is as efficient as possible.

In mathematics, particularly matrix theory and combinatorics, a Pascal matrix is a matrix containing the binomial coefficients as its elements. It is thus an encoding of Pascal's triangle in matrix form. There are three natural ways to achieve this: as a lower-triangular matrix, an upper-triangular matrix, or a symmetric matrix. For example, the 5 × 5 matrices are:

In mathematics, a polynomial matrix or matrix of polynomials is a matrix whose elements are univariate or multivariate polynomials. Equivalently, a polynomial matrix is a polynomial whose coefficients are matrices.

<span class="mw-page-title-main">Matrix (mathematics)</span> Array of numbers

In mathematics, a matrix is a rectangular array or table of numbers, symbols, or expressions, with elements or entries arranged in rows and columns, which is used to represent a mathematical object or property of such an object.

In algebra, linear equations and systems of linear equations over a field are widely studied. "Over a field" means that the coefficients of the equations and the solutions that one is looking for belong to a given field, commonly the real or the complex numbers. This article is devoted to the same problems where "field" is replaced by "commutative ring", or, typically "Noetherian integral domain".

References

  1. ↑ 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 .
  2. ↑ Evangelos, Tourloupis, Vasilios (2013-01-01). "Hermite normal forms and its cryptographic applications". University of Wollongong Thesis Collection 1954-2016. University of Wollongong.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  3. ↑ Adkins, William; Weintraub, Steven (2012-12-06). Algebra: An Approach via Module Theory. Springer Science & Business Media. p. 306. ISBN   9781461209232.
  4. ↑ "Dense matrices over the integer ring — Sage Reference Manual v7.2: Matrices and Spaces of Matrices". doc.sagemath.org. Retrieved 2016-06-22.
  5. 1 2 Mader, A. (2000-03-09). Almost Completely Decomposable Groups. CRC Press. ISBN   9789056992255.
  6. ↑ Micciancio, Daniele; Goldwasser, Shafi (2012-12-06). Complexity of Lattice Problems: A Cryptographic Perspective. Springer Science & Business Media. ISBN   9781461508977.
  7. ↑ Weisstein, Eric W. "Hermite Normal Form". mathworld.wolfram.com. Retrieved 2016-06-22.
  8. 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.
  9. ↑ "Hermite normal form of a matrix - MuPAD". www.mathworks.com. Archived from the original on 2019-02-17. Retrieved 2016-06-22.
  10. ↑ Martin, Richard Kipp (2012-12-06). Large Scale Linear and Integer Optimization: A Unified Approach. Springer Science & Business Media. ISBN   9781461549758.
  11. 1 2 3 Schrijver, Alexander (1998-07-07). Theory of Linear and Integer Programming. John Wiley & Sons. ISBN   9780471982326.
  12. ↑ Cohen, Henri (2013-04-17). A Course in Computational Algebraic Number Theory. Springer Science & Business Media. ISBN   9783662029459.
  13. ↑ Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN   978-3-642-78242-8, MR   1261419
  14. ↑ 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.
  15. ↑ "Euclidean Algorithm and Hermite Normal Form". 2 March 2010. Archived from the original on 7 August 2016. Retrieved 25 June 2015.
  16. ↑ 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.
  17. ↑ 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.
  18. ↑ Havas, George; Majewski, Bohdan S.; Matthews, Keith R. (1998). "Extended GCD and Hermite normal form algorithms via lattice basis reduction". Experimental Mathematics. 7 (2): 130–131. doi:10.1080/10586458.1998.10504362. ISSN   1058-6458. S2CID   263873475.
  19. ↑ Micciancio, Daniele. "Basic Algorithms" (PDF). Retrieved 25 June 2016.
  20. ↑ Cohen, Henri (1999). Advanced Topics in Computational Number Theory. Springer. §1.4.2. ISBN   0-387-98727-4.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.