# Chapter 128. Finite Fields # 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 $$ \mathbb{F}_q $$ or $$ \operatorname{GF}(q), $$ 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 $$ \mathbb{Q}, \qquad \mathbb{R}, \qquad \mathbb{C}. $$ A field \(F\) has two operations: $$ + : F \times F \to F, $$ and $$ \cdot : F \times F \to F. $$ 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 $$ \mathbb{F}_p $$ where \(p\) is prime. The elements are residue classes modulo \(p\): $$ \mathbb{F}_p = \{0,1,2,\ldots,p-1\}. $$ Addition and multiplication are performed modulo \(p\). For example, in \(\mathbb{F}_5\), $$ 3+4 = 7 \equiv 2 \pmod 5, $$ and $$ 3 \cdot 4 = 12 \equiv 2 \pmod 5. $$ The number \(p\) must be prime. If \(p\) is composite, then some nonzero elements do not have multiplicative inverses. For example, modulo \(6\), $$ 2 \cdot 3 \equiv 0 \pmod 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 $$ p \cdot 1 = 0. $$ 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: $$ \underbrace{1+1+\cdots+1}_{p \text{ times}} = 0. $$ For example, in \(\mathbb{F}_2\), $$ 1+1=0. $$ This identity changes many familiar formulas. In characteristic \(2\), subtraction is the same as addition: $$ a-b = a+b. $$ 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 $$ F^n. $$ If \(F=\mathbb{F}_q\), then $$ \mathbb{F}_q^n $$ is the set of all \(n\)-tuples $$ (x_1,\ldots,x_n), \qquad x_i \in \mathbb{F}_q. $$ Since each coordinate has \(q\) possible values, the total number of vectors is $$ q^n. $$ Thus a finite-dimensional vector space over a finite field is a finite set. For example, $$ \mathbb{F}_2^3 $$ has $$ 2^3 = 8 $$ vectors. They are $$ 000,\ 001,\ 010,\ 011,\ 100,\ 101,\ 110,\ 111. $$ ## 128.6 Linear Combinations Linear combinations are defined as usual. If $$ v_1,\ldots,v_k \in V $$ and $$ a_1,\ldots,a_k \in \mathbb{F}_q, $$ then $$ a_1v_1+\cdots+a_kv_k $$ 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 $$ v_1 = \begin{bmatrix} 1\\ 0\\ 1 \end{bmatrix}, \qquad v_2 = \begin{bmatrix} 0\\ 1\\ 1 \end{bmatrix}, $$ then their span over \(\mathbb{F}_2\) is $$ \left\{ \begin{bmatrix}0\\0\\0\end{bmatrix}, \begin{bmatrix}1\\0\\1\end{bmatrix}, \begin{bmatrix}0\\1\\1\end{bmatrix}, \begin{bmatrix}1\\1\\0\end{bmatrix} \right\}. $$ The last vector appears because $$ \begin{bmatrix} 1\\ 0\\ 1 \end{bmatrix} + \begin{bmatrix} 0\\ 1\\ 1 \end{bmatrix} = \begin{bmatrix} 1\\ 1\\ 0 \end{bmatrix} $$ 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 $$ |W| = q^k. $$ This formula is specific to finite fields and is often useful. For example, a \(2\)-dimensional subspace of \(\mathbb{F}_3^5\) contains $$ 3^2 = 9 $$ 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 $$ V = \mathbb{F}_q^n, $$ then the standard basis is $$ e_1,\ldots,e_n, $$ where \(e_i\) has a \(1\) in position \(i\) and \(0\) elsewhere. Every vector has a unique coordinate representation: $$ v = a_1e_1+\cdots+a_ne_n, \qquad a_i \in \mathbb{F}_q. $$ The dimension is the number of basis vectors. The number of vectors in an \(n\)-dimensional vector space over \(\mathbb{F}_q\) is $$ q^n. $$ 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\), $$ A = \begin{bmatrix} 1 & 0 & 1\\ 0 & 1 & 1 \end{bmatrix} $$ 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\), $$ \begin{bmatrix} 1 & 1\\ 0 & 1 \end{bmatrix} + \begin{bmatrix} 1 & 0\\ 1 & 1 \end{bmatrix} = \begin{bmatrix} 0 & 1\\ 1 & 0 \end{bmatrix}. $$ 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: $$ Ax=b. $$ The difference is that all arithmetic is performed in the field. For example, over \(\mathbb{F}_5\), consider $$ \begin{aligned} x+2y &= 3,\\ 3x+y &= 4. \end{aligned} $$ Eliminate \(x\). Multiply the first equation by \(3\): $$ 3x+6y = 9. $$ Modulo \(5\), this becomes $$ 3x+y = 4. $$ 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: | Operation | Meaning | |---|---| | Swap two rows | Reorder equations | | Multiply a row by a nonzero scalar | Rescale an equation | | Add a scalar multiple of one row to another row | Replace an equation by an equivalent one | 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 $$ 3\cdot 5 = 15 \equiv 1 \pmod 7. $$ Thus division by \(3\) means multiplication by \(5\). ## 128.12 Rank and Nullity For a matrix $$ A \in M_{m,n}(\mathbb{F}_q), $$ the rank is the dimension of its column space. The nullity is the dimension of its null space: $$ \ker(A)=\{x\in \mathbb{F}_q^n : Ax=0\}. $$ The rank-nullity theorem remains valid: $$ \operatorname{rank}(A)+\operatorname{nullity}(A)=n. $$ If the nullity is \(r\), then the homogeneous system $$ Ax=0 $$ has $$ q^r $$ solutions. This counting form is one of the characteristic features of finite-field linear algebra. ## 128.13 Invertible Matrices A square matrix $$ A \in M_n(\mathbb{F}_q) $$ is invertible if there exists a matrix \(A^{-1}\) such that $$ AA^{-1}=A^{-1}A=I. $$ Equivalently: | Condition | Statement | |---|---| | Full rank | \(\operatorname{rank}(A)=n\) | | Trivial kernel | \(\ker(A)=\{0\}\) | | Nonzero determinant | \(\det(A)\neq0\) | | Bijective map | \(x\mapsto Ax\) is one-to-one and onto | The set of all invertible \(n \times n\) matrices over \(\mathbb{F}_q\) is called the general linear group: $$ \operatorname{GL}_n(\mathbb{F}_q). $$ Its order is $$ |\operatorname{GL}_n(\mathbb{F}_q)| = (q^n-1)(q^n-q)(q^n-q^2)\cdots(q^n-q^{n-1}). $$ 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, $$ \mathbb{F}_4,\quad \mathbb{F}_8,\quad \mathbb{F}_9,\quad \mathbb{F}_{16} $$ are finite fields. A field with \(p^n\) elements may be constructed as $$ \mathbb{F}_{p^n} \cong \mathbb{F}_p[x]/(f(x)), $$ 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 $$ \mathbb{F}_2[x]/(x^2+x+1). $$ Let \(\alpha\) be the image of \(x\). Then $$ \alpha^2+\alpha+1=0. $$ Since the characteristic is \(2\), subtraction equals addition, so $$ \alpha^2 = \alpha+1. $$ The four elements are $$ 0,\quad 1,\quad \alpha,\quad \alpha+1. $$ Addition is polynomial addition modulo \(2\). Multiplication uses the rule $$ \alpha^2=\alpha+1. $$ For example, $$ \alpha(\alpha+1) = \alpha^2+\alpha = (\alpha+1)+\alpha = 1. $$ Thus \(\alpha+1\) is the multiplicative inverse of \(\alpha\). ## 128.16 Frobenius Map In a finite field of characteristic \(p\), the Frobenius map is $$ \varphi(x)=x^p. $$ It satisfies $$ \varphi(x+y)=\varphi(x)+\varphi(y) $$ and $$ \varphi(xy)=\varphi(x)\varphi(y). $$ The identity $$ (x+y)^p=x^p+y^p $$ holds in characteristic \(p\), because the intermediate binomial coefficients are divisible by \(p\). In \(\mathbb{F}_{p^n}\), every element satisfies $$ x^{p^n}=x. $$ Thus the roots of $$ X^{p^n}-X $$ 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: $$ \mathbb{F}_q^\times = \mathbb{F}_q \setminus \{0\}. $$ This group has $$ q-1 $$ elements. A fundamental theorem states that $$ \mathbb{F}_q^\times $$ is cyclic. Therefore there exists an element \(g\) such that every nonzero element can be written as $$ g^k $$ 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 $$ C \subseteq \mathbb{F}_q^n. $$ The elements of \(C\) are called codewords. If \(C\) has dimension \(k\), then it contains $$ q^k $$ codewords. A generator matrix is a matrix whose rows form a basis for \(C\). If $$ G $$ is a \(k \times n\) generator matrix, then every codeword has the form $$ uG, \qquad u \in \mathbb{F}_q^k. $$ A parity-check matrix is a matrix \(H\) such that $$ C = \{x \in \mathbb{F}_q^n : Hx=0\}. $$ 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 $$ g^k=h. $$ 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 $$ \mathbb{F}_q^n $$ are the points of projective space $$ \mathbb{P}^{n-1}(\mathbb{F}_q). $$ The number of one-dimensional subspaces of \(\mathbb{F}_q^n\) is $$ \frac{q^n-1}{q-1}. $$ 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: | Concept | Statement | |---|---| | Finite field | A field with finitely many elements | | Order | Always \(p^n\), where \(p\) is prime | | Prime field | \(\mathbb{F}_p\), arithmetic modulo \(p\) | | Extension field | \(\mathbb{F}_{p^n}\), built using irreducible polynomials | | Vector space size | \(|\mathbb{F}_q^n|=q^n\) | | Subspace size | A \(k\)-dimensional subspace has \(q^k\) elements | | Linear systems | Solved by ordinary row reduction using field arithmetic | | Multiplicative group | \(\mathbb{F}_q^\times\) is cyclic | | Applications | Coding theory, cryptography, finite geometry | 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.