# 23.1 Lattices

Let  be linearly independent vectors in -dimensional real space . This means that every -dimensional real vector  can be written in the form



with real numbers  that are uniquely determined by . The lattice generated by  is the set of vectors of the form



where  are integers. The set  is called a basis of the lattice. A lattice has infinitely many possible bases. For example, suppose  is a basis of a lattice. Let  be an integer and let  and . Then  is also a basis of the lattice: Any vector of the form  can be written as  with  and , and similarly any integer linear combination of  and  can be written as an integer linear combination of  and .

# Example

Let  and . The lattice generated by  and  is the set of all pairs  with  integers. Another basis for this lattice is . A third basis is . More generally, if  is a matrix with determinant , then  is a basis of this lattice (Exercise 4).

The length of a vector  is



Many problems can be related to finding a shortest nonzero vector in a lattice. In general, the shortest vector problem is hard to solve, especially when the dimension of the lattice is large. In the following section, we give some methods that work well in small dimensions.

# Example

A shortest vector in the lattice generated by



is  (another shortest vector is ). How do we find this vector? This is the subject of the next section. For the moment, we verify that  is in the lattice by writing



In fact,  is a basis of the lattice. For most purposes, this latter basis is much easier to work with than the original basis since the two vectors  and  are almost orthogonal (their dot product is , which is small). In contrast, the two vectors of the original basis are nearly parallel and have a very large dot product. The methods of the next section show how to replace a basis of a lattice with a new basis whose vectors are almost orthogonal.