15.2.13  Hermite normal form

The Hermite normal form of a matrix A with integer coefficients is a sort of integer row-echelon form. It is an upper triangular matrix B such that B=UA for a matrix U which is invertible in ℤ (det(U)=± 1). The ihermite command finds the Hermite normal form of a matrix.

• ihermite takes A, a matrix with coefficients in ℤ.
• ihermite(A) return a list [U,B] as above, and the absolute value of the elements above the diagonal of B are less than the pivot of the column divided by 2.

The result is obtained by a Gauss-like reduction algorithm using only operations of rows with integer coefficients and invertible in ℤ.

Example

Application: Compute a ℤ-basis of the kernel of a matrix having integer coefficients.

Let M be a matrix with integer coefficients. To find the nullspace of M, you want find what you can multiply M by on the right to get the zero vector, but the Hermite command returns a matrix that you multiply on the left of M. So consider the transpose of M, M^T.

Let A be the Hermite normal form of M^T, and U an invertible matrix in ℤ such that A=U M^T. Transposing this, you will get A^T=M U^T. Note that M times a column of U^T equals the corresponding column of A^T. So if a column of A^T is the zero vector, then M times the corresponding column of U^T will be the zero vector. In fact, these columns of U^T will be a ℤ-basis for the nullspace of M.

Any columns of A^T which are all zeros correspond to the rows of A which are all zeros. Since A is in Hermite form, these will be at the bottom, and so the corresponding rows of U will be at the bottom, and will be a ℤ-basis for the nullspace of M.

As an example, consider the matrix M:

Find the Hermite decomposition:

Only the third row of A consists of all zeros, so a ℤ-basis for the nullspace of M consists of only the third row of U, namely [−1,2,−1].

You can check that this is in the nullspace: