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

1 | ```
hermiteNF(A)
``` |

`A` |
integer matrix. |

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.

List with two matrices, the Hermite normal form `H`

and the unitary
matrix `U`

.

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

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

`chinese`

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[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.
``` |

Questions? Problems? Suggestions? Tweet to @rdrrHQ or email at ian@mutexlabs.com.

All documentation is copyright its authors; we didn't write any of that.