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