Chapter 128. Finite Fields

128.1 Introduction

A finite field is a field with finitely many elements. Finite fields are also called Galois fields and are commonly written as

or

where $q$ is the number of elements in the field.

Finite fields are important because they give linear algebra a discrete setting. Over $\mathbb{R}$ or $\mathbb{C}$, vector spaces contain infinitely many vectors. Over a finite field, every finite-dimensional vector space contains only finitely many vectors. This makes the subject useful in coding theory, cryptography, finite geometry, computer algebra, and digital communication. Finite fields exist exactly when the number of elements is a prime power $q=p^n$, and all finite fields of the same order are isomorphic.

The basic concepts of linear algebra remain the same: vectors, matrices, subspaces, bases, linear maps, rank, nullity, and determinants. What changes is the arithmetic.

128.2 Fields

A field is a set equipped with addition, subtraction, multiplication, and division by nonzero elements.

The familiar examples are

A field $F$ has two operations:

$$

• : F \times F \to F, $$

and

These operations satisfy the usual laws: associativity, commutativity, distributivity, additive identities, additive inverses, multiplicative identities, and multiplicative inverses for nonzero elements.

Linear algebra can be developed over any field. The scalars in a vector space do not have to be real or complex. They may come from a finite field.

128.3 Prime Fields

The simplest finite fields are the fields

where $p$ is prime.

The elements are residue classes modulo $p$:

Addition and multiplication are performed modulo $p$.

For example, in $\mathbb{F}_5$,

and

The number $p$ must be prime. If $p$ is composite, then some nonzero elements do not have multiplicative inverses. For example, modulo $6$,

although neither $2$ nor $3$ is zero. Thus arithmetic modulo $6$ does not form a field.

128.4 Characteristic

The characteristic of a field is the least positive integer $p$ such that

In a finite field, the characteristic is always prime.

For $\mathbb{F}_p$, the characteristic is $p$. This means that adding $1$ to itself $p$ times gives zero:

For example, in $\mathbb{F}_2$,

This identity changes many familiar formulas. In characteristic $2$, subtraction is the same as addition:

This fact is heavily used in binary coding theory and digital computation.

128.5 Vector Spaces over Finite Fields

Let $F$ be a finite field. A vector space over $F$ is a set $V$ whose vectors can be added and multiplied by scalars from $F$.

The standard example is

If $F=\mathbb{F}_q$, then

is the set of all $n$-tuples

Since each coordinate has $q$ possible values, the total number of vectors is

Thus a finite-dimensional vector space over a finite field is a finite set.

For example,

has

vectors.

They are

128.6 Linear Combinations

Linear combinations are defined as usual.

If

and

then

is a linear combination of the vectors.

The coefficients are chosen from the finite field.

For example, over $\mathbb{F}_2$, the only scalars are $0$ and $1$. Therefore a linear combination is simply a sum of selected vectors.

If

then their span over $\mathbb{F}_2$ is

The last vector appears because

in $\mathbb{F}_2^3$.

128.7 Subspaces

A subspace of $\mathbb{F}_q^n$ is a subset closed under addition and scalar multiplication.

If $W$ is a $k$-dimensional subspace of $\mathbb{F}_q^n$, then

This formula is specific to finite fields and is often useful.

For example, a $2$-dimensional subspace of $\mathbb{F}_3^5$ contains

vectors.

A $0$-dimensional subspace contains only the zero vector. A $1$-dimensional subspace over $\mathbb{F}_q$ contains $q$ vectors: the zero vector and $q-1$ nonzero scalar multiples of a single vector.

128.8 Bases and Dimension

A basis over a finite field is a linearly independent spanning set.

If

then the standard basis is

where $e_i$ has a $1$ in position $i$ and $0$ elsewhere.

Every vector has a unique coordinate representation:

The dimension is the number of basis vectors.

The number of vectors in an $n$-dimensional vector space over $\mathbb{F}_q$ is

This gives a direct relation between algebraic dimension and cardinality.

128.9 Matrices over Finite Fields

A matrix over $\mathbb{F}_q$ is a rectangular array whose entries lie in $\mathbb{F}_q$.

For example, over $\mathbb{F}_2$,

is a $2 \times 3$ matrix.

Matrix addition, scalar multiplication, and matrix multiplication are performed using the field operations.

For example, over $\mathbb{F}_2$,

The entry $1+1$ becomes $0$, since arithmetic is modulo $2$.

128.10 Linear Systems over Finite Fields

A system of linear equations over a finite field has the same matrix form:

The difference is that all arithmetic is performed in the field.

For example, over $\mathbb{F}_5$, consider

Eliminate $x$. Multiply the first equation by $3$:

Modulo $5$, this becomes

This is exactly the second equation. Hence the two equations are dependent, and the system has more than one solution.

The usual methods still apply: row reduction, rank computation, and null space computation. The arithmetic is finite, but the structure is unchanged.

128.11 Gaussian Elimination

Gaussian elimination works over any field.

The allowed row operations are:

The only requirement is that every nonzero scalar used for division has an inverse. Fields satisfy this requirement.

For example, in $\mathbb{F}_7$, the inverse of $3$ is $5$, since

Thus division by $3$ means multiplication by $5$.

128.12 Rank and Nullity

For a matrix

the rank is the dimension of its column space. The nullity is the dimension of its null space:

The rank-nullity theorem remains valid:

If the nullity is $r$, then the homogeneous system

has

solutions.

This counting form is one of the characteristic features of finite-field linear algebra.

128.13 Invertible Matrices

A square matrix

is invertible if there exists a matrix $A^{-1}$ such that

Equivalently:

The set of all invertible $n \times n$ matrices over $\mathbb{F}_q$ is called the general linear group:

Its order is

The formula comes from choosing linearly independent columns. The first column can be any nonzero vector. The second column can be any vector outside the span of the first. The $k$-th column must lie outside the span of the previous $k-1$ columns.

128.14 Field Extensions

Not every finite field has prime order. Finite fields also exist with $p^n$ elements, where $p$ is prime and $n \geq 1$.

For example,

are finite fields.

A field with $p^n$ elements may be constructed as

where $f(x)$ is an irreducible polynomial of degree $n$ over $\mathbb{F}_p$. In this construction, elements are represented by polynomials of degree less than $n$, and multiplication is reduced modulo $f(x)$.

128.15 Example: The Field $\mathbb{F}_4$

The field $\mathbb{F}_4$ has four elements. It cannot be the integers modulo $4$, since arithmetic modulo $4$ is not a field.

Instead, construct it from

Let $\alpha$ be the image of $x$. Then

Since the characteristic is $2$, subtraction equals addition, so

The four elements are

Addition is polynomial addition modulo $2$. Multiplication uses the rule

For example,

Thus $\alpha+1$ is the multiplicative inverse of $\alpha$.

128.16 Frobenius Map

In a finite field of characteristic $p$, the Frobenius map is

It satisfies

and

The identity

holds in characteristic $p$, because the intermediate binomial coefficients are divisible by $p$.

In $\mathbb{F}_{p^n}$, every element satisfies

Thus the roots of

are precisely the elements of $\mathbb{F}_{p^n}$.

128.17 Multiplicative Group

The nonzero elements of a finite field form a group under multiplication:

This group has

elements.

A fundamental theorem states that

is cyclic. Therefore there exists an element $g$ such that every nonzero element can be written as

for some integer $k$. Such an element is called a primitive element.

This fact is important in coding theory, cryptography, and computational algebra.

128.18 Linear Codes

A linear code is a subspace of a finite-dimensional vector space over a finite field.

Most commonly, one studies subspaces

The elements of $C$ are called codewords.

If $C$ has dimension $k$, then it contains

codewords.

A generator matrix is a matrix whose rows form a basis for $C$. If

is a $k \times n$ generator matrix, then every codeword has the form

A parity-check matrix is a matrix $H$ such that

Thus coding theory is linear algebra over finite fields.

128.19 Cryptographic Use

Finite fields are also used in cryptography.

The multiplicative group $\mathbb{F}_q^\times$ supports discrete logarithm problems. Given a primitive element $g$ and an element $h$, one asks for an integer $k$ such that

For carefully chosen fields, this problem can be computationally difficult.

Finite fields also appear in elliptic curve cryptography, where the points of an elliptic curve are defined over a finite field. The field supplies the arithmetic; the curve supplies the group structure.

128.20 Finite Geometry

Finite vector spaces give finite geometries.

For example, the one-dimensional subspaces of

are the points of projective space

The number of one-dimensional subspaces of $\mathbb{F}_q^n$ is

This follows because there are $q^n-1$ nonzero vectors, and each one-dimensional subspace contains $q-1$ nonzero vectors.

Finite geometry is closely connected with combinatorics, design theory, coding theory, and group theory.

128.21 Summary

Finite fields provide a discrete scalar system for linear algebra. Their arithmetic is finite, exact, and algebraic.

The main facts are:

Finite-field linear algebra keeps the structural form of ordinary linear algebra but replaces continuous arithmetic with exact finite arithmetic. This makes it one of the main tools for discrete mathematics and computation.