Counting Vectors and Subspaces Over F_p

Counting by Coordinates

Over \(\mathbb{R}\), a line contains infinitely many vectors. Over a finite field, every coordinate has only finitely many possible values, so a finite-dimensional vector space has finitely many vectors. The basis gives a direct way to count them: each vector is specified by one scalar for each basis vector. The count depends both on the dimension and on the number of scalars in the field.

Throughout, \(p\) is prime and \(\mathbb{F}_p\) is the field of integers modulo \(p\), with elements represented by \(0,1,\dots,p-1\). Thus \(\mathbb{F}_p\) has exactly \(p\) elements. All vectors and subspaces in this tutorial are over \(\mathbb{F}_p\). A basis is an ordered list that is linearly independent and spans the space; its length is the dimension of the space. Each vector has a unique expression as a linear combination of the vectors in a basis.

Proof. Fix a basis \((\mathbf{b}_1,\dots,\mathbf{b}_n)\) of \(V\). Every vector \(\mathbf{v}\in V\) has a unique coordinate expression \(\mathbf{v}=a_1\mathbf{b}_1+\cdots+a_n\mathbf{b}_n\), where each \(a_i\in\mathbb{F}_p\). There are \(p\) choices for each coefficient, so there are \(p^n\) coefficient lists. Uniqueness means that different lists give different vectors, and spanning means that every vector is obtained from a list. Therefore the number of vectors is \(p^n\). When \(n=0\), there is one empty coefficient list and its vector is \(\mathbf{0}\), so the same count gives \(p^0=1\). \(\square\)

The count is a consequence of a bijection: assigning a vector its basis coordinates pairs the vectors of \(V\) one-to-one with the \(n\)-tuples in \(\mathbb{F}_p^n\). There are \(p^n\) such tuples because each of the \(n\) positions can be chosen in \(p\) ways. This is a count of vectors, not a statement that the dimension itself is the number of vectors.

Why a Subspace Has \(p^k\) Vectors

Let \(U\) be a subspace of a finite-dimensional space \(V\). If \(U\) has dimension \(k\), a basis of \(U\) gives \(p^k\) combinations within \(U\). To compare those combinations with all the vectors in \(V\), it is useful to extend the basis of \(U\) to a basis of \(V\). The following argument justifies that extension in the finite-dimensional setting.

Proof. Write a basis of \(V\) as \((\mathbf{c}_1,\dots,\mathbf{c}_n)\), and start with a basis of \(U\). Process the vectors \(\mathbf{c}_1,\dots,\mathbf{c}_n\) in order. Whenever the current list does not span \(\mathbf{c}_i\), append \(\mathbf{c}_i\); otherwise leave the list unchanged. Each appended vector is outside the span of the list at that moment, so appending it preserves linear independence: a relation with a nonzero coefficient on the new vector would express that vector as a combination of the old list. At the end, every \(\mathbf{c}_i\) is in the span of the resulting list. Since the \(\mathbf{c}_i\) span \(V\), the resulting list spans \(V\) as well. It is both independent and spanning, so it is a basis of \(V\) containing the original basis of \(U\). \(\square\)

Proof. Choose a basis \((\mathbf{u}_1,\dots,\mathbf{u}_k)\) of \(U\). By the basis extension result, add vectors \(\mathbf{w}_1,\dots,\mathbf{w}_{n-k}\) to obtain a basis of \(V\). Each vector of \(V\) has a unique expression \(\sum_{i=1}^{k}a_i\mathbf{u}_i+\sum_{j=1}^{n-k}b_j\mathbf{w}_j\). The vectors in \(U\) are exactly those whose coefficients \(b_1,\dots,b_{n-k}\) are all zero. Indeed, such an expression is a combination of the \(\mathbf{u}_i\), so it lies in \(U\). Conversely, a vector in \(U\) is a combination of the \(\mathbf{u}_i\); uniqueness of coordinates in the extended basis forces all its \(b_j\) to be zero. There are \(p^k\) choices for the \(a_i\), giving \(p^k\) vectors in \(U\). The whole space has \(p^n\) vectors, and \(U\) and \(V\setminus U\) are disjoint and together contain every vector of \(V\). Subtracting gives \(p^n-p^k\) vectors outside \(U\). If \(k=0\), this counts \(U=\{\mathbf{0}\}\); if \(k=n\), it gives zero vectors outside \(U=V\). \(\square\)

The added basis vectors provide the remaining \(n-k\) coordinates in \(V\). Setting all those coordinates to zero describes \(U\); allowing them to vary gives vectors outside \(U\) as well. This is why the subspace count depends on \(k\), even when the surrounding space has dimension \(n\).

Dimension and Cardinality Are Different

Dimension counts basis vectors. Cardinality counts all vectors. Over a fixed field, the formula \(p^n\) connects the two, but the values need not be equal. Moreover, if the field changes, dimension alone does not determine which of two spaces has more vectors.

Common Counting Mistakes

Mistake: adding the number of coordinates to the number of field elements. A tempting but incorrect calculation is to say that \(\mathbb{F}_3^4\) has \(3+4=7\) vectors. This treats the four coordinates as if they contributed only four extra choices. In fact, each of the four coordinates can be chosen independently in three ways, so the count is \(3\cdot3\cdot3\cdot3=3^4=81\).

Mistake: confusing dimension with cardinality. A two-dimensional space over \(\mathbb{F}_5\) has \(5^2=25\) vectors, not two. A zero-dimensional space has one vector, not zero: its only vector is \(\mathbf{0}\). These checks are useful because the formula must count the zero vector as well as every nonzero vector.

Mistake: using the ambient dimension for a subspace count. In \(\mathbb{F}_3^4\), a two-dimensional subspace has \(3^2=9\) vectors, not \(3^4=81\). The latter counts the entire ambient space. The subspace uses two basis coordinates, and the other two coordinates in an extended basis must be zero for a vector to lie in that subspace.

These counts are useful whenever finite-field vectors are used as a finite set of possible states or configurations. They also provide a quick consistency check: an \(n\)-dimensional space over \(\mathbb{F}_p\) must have \(p^n\) vectors, and a \(k\)-dimensional subspace must have \(p^k\). The formulas count elements in a specified space or subspace; they do not count how many different subspaces of a given dimension exist.