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
A:=[[9,-36,30],[-36,192,-180],[30,-180,180]]:;
ihermite(A) |
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, MT.
Let A be the Hermite normal form of MT, and U an invertible
matrix in ℤ such that A=U MT. Transposing this,
you will get AT=M UT. Note that M times a column of UT equals the
corresponding column of AT. So if a column of AT is the zero
vector, then M times the corresponding column of UT will be the
zero vector. In fact, these columns of UT will be a
ℤ-basis for the nullspace of M.
Any columns of AT 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:
M:=[[1,4,7],[2,5,8],[3,6,9]] |
Find the Hermite decomposition:
(U,A):=ihermite(transpose(M)) |
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: