Lattice Basis Reduction

6 Lattice Basis Reduction

Lemma 1.10. Let x

1

, x

2

, . . . , x

n

and y

1

, y

2

, . . . , y

n

, be two bases for the

same lattice L ⊂ R

n

. Let X (respectively Y ) be the n × n matrix with x

i

(respectively y

i

) in row i for i = 1, 2, . . . , n. Then Y = CX for some n × n

matrix C with integer entries and determinant ±1.

Proof. Every y

i

belongs to the lattice with basis x

1

, x

2

, . . . , x

n

, and every x

i

belongs to the lattice with basis y

1

, y

2

, . . . , y

n

. It follows that

x

i

=

n

X

j=1

b

ij

y

j

, y

i

=

n

X

j=1

c

ij

x

j

(i = 1, 2 , . . . , n),

where B = (b

ij

) and C = (c

ij

) are n×n matrices with integer entries. Writing

these two equa tio ns in matrix form gives X = BY and Y = CX, and hence ...