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, 0, 1)
- (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.
So each of those 13 subspaces must contain (0,0,0).
{(1,1,2), (0,2,0), (2,0,1)} is a line it adds to (0,0,0) but does not contain it, so it is not a subspace. Is that right?