Lattice Basis Reduction

226 Lattice Basis Reduction

By invertible over Z we mean that U is invertible and that both U a nd

U

−1

have entries in Z. This is equivalent to the condition that det(U) = ±1.

Definition 14.8. Let H be an m × n matrix over Z. We say that H is in

Hermite normal form (or HNF) if the following conditions are satisfied:

(1) For some r with 0 ≤ r ≤ m we have H

ij

= 0 for r < i ≤ m and

1 ≤ j ≤ n.

(2) For some j

1

, j

2

, . . . , j

r

with 1 ≤ j

1

< j

2

< ··· < j

r

≤ n we have

H

ij

= 0 for 1 ≤ j < j

i

and H

ij

i

≥ 1.

(3) For all i and k with 1 ≤ k < i ≤ r we have 0 ≤ H

kj

i

< H

ij

i

.

Theorem 14.9. If A is an m ×n matrix over Z then there is a unique m ×n

matrix H over Z satisfying these