Vector Spaces Over Finite Fields

Vectors When the Scalars Are Residues

Vector-space calculations do not require real numbers as scalars. For a prime \(p\), the field \(\mathbb{F}_p\) consists of the residue classes modulo \(p\), represented by \(0,1,\dots,p-1\). Addition, subtraction, and multiplication are performed modulo \(p\). For example, in \(\mathbb{F}_5\), \(4+3=2\) and \(2\cdot 3=1\), because \(7\) has remainder \(2\) and \(6\) has remainder \(1\) on division by \(5\). The primality condition matters: every nonzero element of \(\mathbb{F}_p\) has a multiplicative inverse, so the scalars form a field.

A vector in \(\mathbb{F}_p^n\) is a column of \(n\) elements of \(\mathbb{F}_p\). Vector addition and scalar multiplication are performed coordinate by coordinate, always reducing each result modulo \(p\). Thus vectors that look like ordinary integer columns are not being calculated over \(\mathbb{R}\): their entries and coefficients belong to \(\mathbb{F}_p\).

These rules have the same form over \(\mathbb{F}_p\) as over \(\mathbb{R}\), but the calculations that verify them take place in the finite field. The zero vector in \(\mathbb{F}_p^n\) has every coordinate equal to \(0\). The additive inverse of a vector is found by taking the additive inverse of each coordinate; for instance, \(-2=3\) in \(\mathbb{F}_5\).

Why Tuples, Matrices, and Polynomials Are Vector Spaces

Proof. The field operations in \(\mathbb{F}_p\) are closed and obey the field laws. For tuples, adding two \(n\)-coordinate columns or multiplying one by a scalar produces another \(n\)-coordinate column over \(\mathbb{F}_p\). The zero column is an additive identity, and negating each entry gives an additive inverse. Each vector-space identity holds in every coordinate: for example, the \(i\)th coordinate of \(a(\mathbf{u}+\mathbf{v})\) is \(a(u_i+v_i)=au_i+av_i\), which is the \(i\)th coordinate of \(a\mathbf{u}+a\mathbf{v}\). Associativity, commutativity, the scalar addition rule, compatibility of scalar multiplication, and the identity-scalar rule follow coordinate by coordinate from the corresponding field laws. For fixed-size matrices, the same argument applies to each matrix entry, so the zero matrix and entrywise additive inverses supply the required zero and inverses. For polynomials, addition and scalar multiplication act on each coefficient. Sums and scalar multiples of polynomials still have only finitely many nonzero coefficients, and the zero polynomial and coefficientwise negatives supply the additive identity and inverses. Each axiom then holds coefficient by coefficient by the field laws. Therefore all three sets satisfy the vector-space axioms. \(\square\)

For a polynomial, “coefficientwise” means that like powers of \(x\) are combined. It does not mean that the exponent is reduced modulo \(p\). For example, over \(\mathbb{F}_2\), the coefficients \(1+1\) cancel to \(0\), but the term \(x^3\) remains a term of degree \(3\).

Computing Linear Combinations

A linear combination of \(\mathbf{v}_1,\dots,\mathbf{v}_k\) over \(\mathbb{F}_p\) is \(c_1\mathbf{v}_1+\cdots+c_k\mathbf{v}_k\), where each coefficient \(c_i\) is in \(\mathbb{F}_p\). The vector addition and scalar multiplication are those of the space in question. In particular, each coordinate or matrix entry is reduced modulo \(p\) as the calculation proceeds.

To form a span, allow all possible coefficients from the field, not just the coefficients \(0\) and \(1\). The resulting collection is a set of vectors in the same vector space.

Spans Are Closed Under the Vector-Space Operations

Proof. Let \(S=\operatorname{span}\{\mathbf{v}_1,\dots,\mathbf{v}_k\}\). The zero vector belongs to \(S\), since choosing every coefficient to be \(0\) gives \(0\mathbf{v}_1+\cdots+0\mathbf{v}_k=\mathbf{0}\). Take any \(\mathbf{x},\mathbf{y}\in S\). By the definition of span, there are coefficients \(a_1,\dots,a_k,b_1,\dots,b_k\in\mathbb{F}_p\) such that \(\mathbf{x}=\sum_{i=1}^k a_i\mathbf{v}_i\) and \(\mathbf{y}=\sum_{i=1}^k b_i\mathbf{v}_i\). Using the vector-space distributive laws, \(\mathbf{x}+\mathbf{y}=\sum_{i=1}^k(a_i+b_i)\mathbf{v}_i\). Each \(a_i+b_i\) is in \(\mathbb{F}_p\), so this sum belongs to \(S\). Now take any \(c\in\mathbb{F}_p\). Then \(c\mathbf{x}=\sum_{i=1}^k(ca_i)\mathbf{v}_i\), and each \(ca_i\) is in \(\mathbb{F}_p\), so \(c\mathbf{x}\in S\). Thus \(S\) contains zero and is closed under addition and scalar multiplication; it is a subspace. \(\square\)

This result explains why the word “span” is useful: it describes a collection that stays within the same vector space when its elements are added or multiplied by scalars. To establish that one vector belongs to a span, it is enough to exhibit coefficients and verify the resulting combination. To establish that a whole set is the span requires accounting for all possible coefficients, a different task from checking one membership claim.

Finite-Field Operations in Matrices and Polynomials

Common Pitfall: Reducing Only at the End

A frequent error is to leave an answer as though the entries were ordinary integers. For example, over \(\mathbb{F}_5\), a mistaken calculation might write \(3\begin{bmatrix}1\\2\end{bmatrix}=\begin{bmatrix}3\\6\end{bmatrix}\) and conclude that this is the final vector. The correction is to reduce each entry modulo \(5\): \(6=1\), so the scalar multiple is \(\begin{bmatrix}3\\1\end{bmatrix}\). The unreduced column does not use entries in the chosen representative set \(0,1,2,3,4\).

The modulus itself is another essential condition. Modulo \(6\), the nonzero residue \(2\) has no multiplicative inverse: the possible products \(2\cdot0,2\cdot1,\dots,2\cdot5\) have remainders \(0,2,4,0,2,4\), never \(1\). Thus the residues modulo \(6\) do not form a field, and they cannot serve as the scalar field in the vector-space definition used here. For \(\mathbb{F}_p\), keep \(p\) prime, and reduce every coordinate, entry, and coefficient using that same modulus.