9.4.1.1. Finite Fields and Finite Vector Spaces

(Finite) Fields

In algebra,

A group \((G, \circ)\) is a set \(G\) equipped with an operation \(\circ : G \times G \rightarrow G\) that

• Is associative: \(x \circ (y \circ z) = (x \circ y) \circ z\),
• Has an identity element \(e\): \(x \circ e = e \circ x = x\) for all \(x \in S\), and
• Has an inverse element \(x^{-1} \in S\) for every element \(x \in S\): \(x \circ x^{-1} = x^{-1} \circ x = e\).

A group is commutative or Abelian if \(x \circ y = y \circ x\) for all \(x, y \in S\).

A field \((F, +, *)\) is a set \(F\) equipped with two operations \(+ : F \times F \rightarrow F\) and \(* : F \times F \rightarrow F\), called addition and multiplication, such that

• \((F,+)\) and \((F \setminus \{0\},*)\) are Abelian groups, where \(0\) is the identity element of \((F,+)\), and
• \(*\) and \(+\) are distributive: \(a * (b + c) = a * b + a * c\).

The real numbers together with standard addition and multiplication form a field \((\mathbb{R},+,*)\).

The rational numbers together with standard addition and multiplication form a field \((\mathbb{Q},+,*)\).

The set of integers together with standard addition and multiplication do not form a field because the only integers that have multiplicative inverses in \(\mathbb{Z} \setminus \{0\}\) are \(1\) and \(-1\). (However, \((\mathbb{Z},+,*)\) is a ring, which only requires multiplication to be associative and to have an identity element.)

The field we care about here is the Galois field of size \(\boldsymbol{2}\), \(\textrm{GF}[2] = (\{0,1\}, \oplus, \otimes)\), where \(x \oplus y = (x + y) \bmod 2\) and \(x \otimes y = x * y\). This is a finite field because it has only a finite number of elements.

Vector Spaces Over \(\boldsymbol{\textbf{GF}[2]}\)

Just as we can define vector spaces over the real numbers, we can define vector spaces over \(\textrm{GF}[2]\), that is, vector spaces whose vectors have coordinates in \(\textrm{GF}[2]\).

A vector space over a field \((F, \oplus, \otimes)\) is a subset \(S \subseteq F^d\) such that, for all \(x = (x_1, \ldots, x_d), y = (y_1, \ldots, y_d) \in S\) and \(\lambda \in F\),

• \(x \oplus y = (x_1 \oplus y_1, \ldots, x_d \oplus y_d) \in S\) and
• \(\lambda \otimes x = (\lambda \otimes x_1, \ldots, \lambda \otimes x_d) \in S\).

In particular, it is easy to verify that \(F^d\) is itself a vector space.

Given a vector space \(S\) over some field \((F, \oplus, \otimes)\), a vector \(v \in S\) is a linear combination of a set of vectors \(v_1, \ldots, v_k \in S\) if there exist coefficients \(\lambda_1, \ldots, \lambda_k \in F\) such that \(v = \sum_{i=1}^k \lambda_iv_i\).

A set of vectors \(V \subseteq S\) in a vector space \(S\) over some field \((F, \oplus, \otimes)\) is linearly independent if none of the vectors in \(V\) is a linear combination of the other vectors in \(V\).

The dimension \(\dim(S)\) of a vector space \(S\) is the size of the largest subset of linearly independent vectors in \(S\).

The dimension of \(F^d\) is \(d\). Any proper subspace of \(F^d\) has dimension less than \(d\).

Given a subset \(S \subseteq F^d\), the vector space spanned by \(S\) is the smallest superset of \(S\) that is a vector space.

Another way of saying this is that the vector space spanned by \(S\) is the set of all vectors that can be written as linear combinations of elements in \(S\).