numbers (version 0.8-5)

Hermite normal form: Hermite Normal Form

Description

Hermite normal form over integers (in column-reduced form).

Usage

hermiteNF(A)

Value

List with two matrices, the Hermite normal form H and the unitary matrix U.

Arguments

A

integer matrix.

Details

An mxn-matrix of rank r with integer entries is said to be in Hermite normal form if:

(i) the first r columns are nonzero, the other columns are all zero;
(ii) The first r diagonal elements are nonzero and d[i-1] divides d[i] for i = 2,...,r .
(iii) All entries to the left of nonzero diagonal elements are non-negative
and strictly less than the corresponding diagonal entry.

The lower-triangular Hermite normal form of A is obtained by the following three types of column operations:

(i) exchange two columns
(ii) multiply a column by -1
(iii) Add an integral multiple of a column to another column

U is the unitary matrix such that AU = H, generated by these operations.

References

Cohen, H. (1993). A Course in Computational Algebraic Number Theory. Graduate Texts in Mathematics, Vol. 138, Springer-Verlag, Berlin, New York.

See Also

chinese

Examples

n <- 4; m <- 5
A = matrix(c(
 9,  6,  0, -8,  0,
-5, -8,  0,  0,  0,
 0,  0,  0,  4,  0,
 0,  0,  0, -5,  0), n, m, byrow = TRUE)
 
Hnf <- hermiteNF(A); Hnf
# $H =  1    0    0    0    0
#       1    2    0    0    0
#      28   36   84    0    0
#     -35  -45 -105    0    0
# $U = 11   14   32    0    0
#      -7   -9  -20    0    0
#       0    0    0    1    0
#       7    9   21    0    0
#       0    0    0    0    1

r <- 3                  # r = rank(H)
H <- Hnf$H; U <- Hnf$U
all(H == A %*% U)       #=> TRUE

##  Example: Compute integer solution of A x = b
#   H = A * U, thus H * U^-1 * x = b, or H * y = b
b <- as.matrix(c(-11, -21, 16, -20))

y <- numeric(m)
y[1] <- b[1] / H[1, 1]
for (i in 2:r)
    y[i] <- (b[i] - sum(H[i, 1:(i-1)] * y[1:(i-1)])) / H[i, i]
# special solution:
xs <- U %*% y         #  1 2 0 4 0

# and the general solution is xs + U * c(0, 0, 0, a, b), or
# in other words the basis are the m-r vectors c(0,...,0, 1, ...).
# If the special solution is not integer, there are no integer solutions.