hermite: Hermite Normal Form In numbers: Number-Theoretic Functions

Description

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

Usage

 1 hermiteNF(A)

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.

Value

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

Note

Another normal form often used in this context is the Smith normal form.

References

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

Examples

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 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 <- b / 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.

Example output

\$H
[,1] [,2] [,3] [,4] [,5]
[1,]    1    0    0    0    0
[2,]    1    2    0    0    0
[3,]   28   36   84    0    0
[4,]  -35  -45 -105    0    0

\$U
[,1] [,2] [,3] [,4] [,5]
[1,]   11   14   32    0    0
[2,]   -7   -9  -20    0    0
[3,]    0    0    0    1    0
[4,]    7    9   21    0    0
[5,]    0    0    0    0    1

 TRUE

numbers documentation built on May 15, 2021, 1:08 a.m.