6.48.13  Hermite normal form: ihermite

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 one argument:
  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.
Input:

Output:

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’ll 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 0s correspond to the rows of A which are all 0s. 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:
Input:

Find the Hermite decomposition:
Input:

Output:

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

You can check that this is in the nullspace:
Input:

Output: