Finite Vector Spaces

Fp is the field of prime order p.

Fpn is the set of all n-tuples 0 , δ1, ..., δn - 1) of elements of Fp.

The Position Map

The position map lays out Fp2m as a square of order pm. In the square, the rows and columns are numbered from 0 to pm-1. Let x = (δ0, δ1, ..., δ2m-1) be an element of Fp2m. Let

δi = μ(di),

0 ≤ di < p,

i = 0, ..., 2m-1 .

Then Px is the cell at row r and column c, where

r = d0pm-1 + d1pm-2 + ... + dm-1

c = dmpm-1 + dm+1pm-2 + ... + d2m-1 .

What's going on here? The coordinates of x are interpreted as integers from 0 to p-1; they are separated into two groups of m numbers, which are then used as the "digits" of r and c in base p.

Here is a demonstration of how the position map works. The "P" and "M" controls allow you to select a square whose order pm is between 2 and 32. The other controls allow you to select values for d0 , ... , d2m-1 . The corresponding position in the square is shown in green. Alternatively, if you click on a position in the square, then the corresponding values of d0 , ... , d2m-1 are displayed in the controls.

P: M:
r =
c =

The Content Map

Just as the position map assigns a cell in the pm × pm square to every element of Fp2m, the content map assigns to every such element a number in the range 0 ≤ n < p2m. As before, let x = (δ0 , δ1 ,..., δ2m-1) be an element of Fp2m. Let

δi = μ(di),

0 ≤ di < p,

i = 0, ..., 2m-1 .

Then

Cx = d0p2m-1 +...+ d2m-1.

In effect, the coordinates of x are being used as digits in the base-p expansion of Cx.

Vector Addition

In a vector space over Fp, two elements can be added or subtracted, and an element of the vector space can be multiplied by an element of Fp . The sum of two elements of Fpn is defined thus:

0 , δ1 ,..., δn-1) + (δ′0 , δ′1 ,..., δ′n-1) = (δ0+δ′0 ,..., δn-1+δ′n-1) .

Here is a demonstration of addition on Fp2m arranged as a square of order pm. In the equation U + V = W, the three vectors are color-coded. As in the previous display, there are "P" and "M" controls with which to select the order of the square. For U and V, there are controls for the values of d0 ,..., d2m-1. The corresponding values for W are shown. You can also change the positions of U and V in the square: clicking on a position will bring up a dialog which gives you the choice of moving either U or V to that position.

P: M:
U: r =
c =
V: r =
c =
W: r =
c =

Multiplication of a Field Element and a Vector

The product of an element of an element Fp and an element of Fpn is defined thus:

κ(δ0 , δ2 ,..., δn) = (κδ0 , κδ2 ,..., κδn) .

Here is a demonstration of multiplication by a field element κ in Fp of an element U in Fp2m. The "P" and "M" controls are like those in the previous demos. There are selectors for the values of d0 ,..., d2m for U, and there is another for the value of κ. In the square, U is represented by a red cell, and W = κU is represented in blue. If you click on a position in the square, U will be moved to that position.

P: M:
κ:
U: r =
c =
W: r =
c =

Hey, Wait a Minute

Aren't vectors geometrical? I'm pretty sure I remember learning that a vector was something that had length and direction.

Well, yes; if the field elements are real numbers, elements of R rather than elements of Fp, then the vectors are geometrical. R2 is a useful algebraic tool for studying plane geometry, and R3 is the same for solid geometry. Now R2 and R3 are just special cases of Rn. If you do your geometry using the algebra of vectors, then the extension from two or three dimensions to four or more is almost easier to do than to refrain from doing. The extension to other base fields, such as Fp, empowers us to use our intuitions about lines and planes in a different and novel context.

Linear Subspaces and Affine Subspaces

Lines and planes in space are described in linear algebra as affine subspaces. To begin with, a linear subspace is a set of vectors which includes u + v if it includes u and v, and includes κ u if it includes u and κ is a field element. An affine subspace is a set that can be constructed from a linear subspace by adding a fixed vector to each member of it. That is, A is an affine subspace if there is a linear subspace S and a vector w such that A consists of those vectors w + x where x belongs to S. We say that A is parallel to S, and that all the affine spaces parallel to S are parallel to one another.

Affine subspaces are sometimes called flats. I will generally adhere to this usage; when the dimension of a flat is particularly important, I will call it a 2-flat, 3-flat, etc.

Here is a demonstration of the behavior of flats in Fp2m. You can select a set of points in the vector space, and the applet will show you the flat which they span, that is, the smallest flat containing them. This set is independent if no proper subset spans the same flat. The demo will only let you choose an independent set of points. The points belonging to the flat are shown in green, and the spanning set are emphasized by dots. To manipulate the spanning set, you can click over a cell. A dialog box will show you what operations are available for this cell; if it is one of the selected points then you can remove it, or if it is not already in the affine subspace you can add it to the spanning set. The flat can be translated to a parallel flat using the pop-up menu; if you click a cell belonging to the flat and select "Translate", then clicking on another cell will have the effect of moving the former cell of the flat to the latter point, and translating the entire flat accordingly.

Parallel flats can be displayed in another way as well. If you press the button marked "Color parallel flats at random," then a random color will be chosen for each flat, and its points will be marked by lozenges of that color. The button marked "Blank out parallel flats" will remove the colored lozenges.

P: M:

Linear and Affine Functions

On the vector space Fpn, a linear function is a function f from the vector space to Fp, satisfying
f(u + v) = f(u) + f(v)
and
f(κu) = κf(u)
where u and v belong to Fpn and κ belongs to Fp.

An affine function is a linear function plus a constant. More formally, it is a function of the form u → f(u) + λ where f is linear and λ is an element of Fp. An affine function is determined by its values at a set of points that is independent and spans the entire space.

The accompanying demonstration shows affine functions on vector spaces of the form Fp2m displayed as squares. Having chosen the values of p and m, you can specify the affine function in one of two ways. The first is to select the value of λ and the value of the linear part at each of the points e0 ,..., e2m-1, where ei has all components 0 except for a 1 at the i-th place. Controls are provided to select these values; the labels also indicate the positions of the points ei in the square. The other way is to select the values of the affine function itself, at 2m + 1 points: Z = (0,0,...,0) and e0 ,..., e2m-1. These points are highlighted in pale green. If you click on one of these points, a dialog box will appear with a selector for the value of the affine function at that point.

P: M:

If an affine function A has the form A(u) = L(u) + c where c is constant and L is linear, then we shall call L the linear part of A, and c the constant part.

Linear and Affine Maps

If L0, ..., L2m-1 are linear functions, then they determine a linear map L from Fp2m to itself, thus:

Lu = (L0u, ..., L2m-1u) .

Similarly, if A0, ..., A2m-1 are affine functions, then they determine an affine map A:

Au = (A0u, ..., A2m-1u) .

We will say that L0, ..., L2m-1 and A0, ..., A2m-1 are the components of L and A respectively.

Last modified on $Date: 2015-05-02 12:51:16 -0400 (Sat, 02 May 2015) $

Christopher J. Henrich