RSA Laboratories

A.5 Vector spaces and lattices

In most undergraduate programs in mathematics the theory of linear algebra and vector spaces is introduced before the theory of groups and rings. This makes sense as vector spaces are easier to comprehend than groups and rings. The reason for putting this section after the preceding sections is simply that we now need fewer axioms to define a vector space.

An n-dimensional vector space over the real numbers can be viewed as the set Rn of n-tuples (a1, ¼, an) of real numbers. The n-tuples are called vectors. There are two basic operations on such a set: addition and scalar multiplication. Addition of vectors is defined as

(a1, ¼, an) + (b1, ¼, bn) = (a1 + b1, ¼, an+ bn),

while multiplication of a scalar (real number) r and a vector (a1, ¼an) is defined as

r ·(a1, ¼, an) = (r a1, ¼, r an).

Given a set S = {v1, ¼, vk} of vectors in Rn, the lattice L(S) generated by S is the set of all integer combinations of elements in S. That is, L(S) contains all linear combinations

n1 v1 + ¼+ nk vk,

where n1, ¼, nk Î Z. For example, the set of all vectors in R3 with integer coordinates is the lattice generated by the unit vectors (1, 0, 0), (0, 1, 0), and (0,0,1).

Formally, a vector space over the field F is a set V of elements called vectors together with an operation + : V ×V® V called addition and an operation ·: F ×V® V called scalar multiplication such that

  1. V is an abelian group under addition.
  2. a ·(b ·v) = (ab) ·v for all a,b Î F, v Î V.
  3. a·(v+w) = a·v + a ·w for all a Î F, v, w Î V.

One may replace F with an arbitrary ring R, but then V is called a module over R and not a vector space. For example, a lattice is a module over Z.

The elements v1, ¼, vk Î V in a vector space are linearly dependent if there are elements a1, ¼, ak Î F not all 0 such that

a1 ·v1 + ¼+ ak ·vk = 0.

Otherwise the vectors v1, ¼, vk are linearly independent. The vectors e1, ¼, en form a basis for V if they are linearly independent and span V, that is, for each v Î V, there are elements a1, ¼, an Î F such that

a1 e1 + ¼+ an en = v. (1)

If there is such a basis, then every basis has the same number of elements; this number is called the dimension of V. In fact, every vector space has a basis, but it need not be finite in general.

With a fixed basis {e1, ¼, en} of the n-dimensional vector space V, any element v Î V can be written as an n-tuple (a1, ¼, an), where a1, ¼, an are the unique elements satisfying (1). Objects in the ordinary three-dimensional space such as planes and lines are easily generalized to arbitrary finite-dimensional vector spaces. For example, an affine hyperplane in V is the set of all points x = (x1, ¼, xn) satisfying the equation

a1 x1 + ¼+ an xn = b,

where a1, ¼, an, b Î F are some fixed constants (not all ai are zero). The word ``affine'' simply means that the element b does not have to be 0. The concept of a hyperplane generalizes the concept of an affine plane in R3, which has the form

a x + b y + c z = d

for some constants a,b,c,d Î R. A line in V is a set of the form { av+(1-a)w : a Î F}, where v, w Î V are two different vectors. With w = 0, we obtain a line through the origin.

Top of the page