A surprising amount of linear algebra doesn’t depend on the field you’re working over. You can implicitly assume you’re working over the real numbers R and prove all the basic theorems—say all the theorems that come before getting into eigenvalues in a typical course—and all or nearly all of the theorems remain valid if you swap out the complex numbers for the real numbers. In fact, they hold for any field, even a finite field.
Subspaces over infinite fields
Given an n-dimensional vector space V over a field F we can ask how many subspaces of V there are with dimension k. If our field F is the reals and 0 < k < n then there are infinitely many such subspaces. For example, if n = 2, every line through the origin is a subspace of dimension 1.
Now if we’re still working over R but we pick a basis
e1, e2, e3, …, en
and ask for how many subspaces of dimension k there are in V that use the same basis elements, now we have a finite number. In fact the number is the binomial coefficient
because there are as many subspaces as there are ways to select k basis elements from a set of n.
Subspaces over finite fields
Let F be a finite field with q elements; necessarily q is a prime power. Let V be an n-dimensional vector space over F. We might need to know how many subspaces of V there are of various dimensions when developing algebraic codes, error detection and correction codes based on vector spaces over finite fields.
Then the number of subspaces of V with dimension k equals the q-binomial coefficient
![\binom{n}{k}_q \equiv \frac{[n]_q!}{[k]_q! [n-k]_q!}](https://www.johndcook.com/q_binomial.svg){kind=small}
mentioned in the previous post. Here [n]q! is the q-factorial of n, defined by
![[n]_q! \equiv [1]_q [2]_q [3]_q \cdots [n]_q](https://www.johndcook.com/q_factorial.svg){kind=small}
and [n]q! is the q-analog of n, defined by
![[n]_q \equiv \frac{1 - q^n}{1-q} = 1 + q + q^2 + \cdots q^{n-1}](https://www.johndcook.com/q_analog.svg){kind=small}
The fraction definition holds for all n, integer or not, when q ≠ 1. The fraction equals the polynomial in q when n is a non-negative integer.
You can derive the expression for the number of subspaces directly from a combinatorial argument, not using any of the q-analog notation, but this notation makes things much more succinct.
Python code
We can easily code up the definitions above in Python.
def analog(n, q):
return (1 - q**n)//(1 - q)
def qfactorial(n, q):
p = 1
for k in range(1, n+1):
p *= analog(k, q)
return p
def qbinomial(n, k, q):
d = qfactorial(k, q)*qfactorial(n-k, q)
return qfactorial(n, q)/d
Example
To keep things small, let’s look at the field with q = 3 elements. Here addition and multiplication are carried out mod 3.
Let n = 3 and k = 1. So we’re looking for one-dimensional subspaces of F³ where F is the field of integers mod 3.
A one-dimensional subspace of vector space consists of all scalar multiples of a vector. We can only multiply a vector by 0, 1, or 2. Multiplying by 0 gives the zero vector, multiplying by 1 leaves the vector the same, and multiplying by 2 turns 1s into 2s and vice versa. So, for example, the vector (1, 2, 0) is a basis for the subspace consisting of
(0, 0, 0), (1, 2, 0}, (2, 1, 0).
We can find all the subspaces by finding a base for each subspace. And with a little brute force effort, here’s a list.
- (1, 0, 0)
- (0, 1, 0)
- (0, 0, 1)
- (0, 1, 1)
- (1, 0, 1)
- (1, 1, 0)
- (1, 2, 0)
- (0, 1, 2)
- (2, 1, 0)
- (1, 1, 1)
- (2, 1, 1)
- (1, 2, 1)
- (1, 1, 2)
It’s easy to check that none of these vectors is a multiple mod 3 of another vector on the list. The theory above says we should expect to find 13 subspaces, and we have, so we must have found them all.
