# How to count number of bases and subspaces of a given dimension in a vector space over a finite field? [duplicate]

Let $V_{n}(F)$ be a vector space over the field $F=\mathbb Z_{p}$ with $\dim V_{n} = n$, i.e., the cardinality of $V_{n}(\mathbb Z_{p}) = p^{n}$. What is a general criterion to find the number of bases in such a vector space? For example, find the number of bases in $V_{2}(\mathbb Z_{3})$. Further, how can we find the number of subspaces of dimension, say, $r$?

I need a justification with proof. I have a formula, but I am unable to understand the basic idea behind that formula.

• First, let's count the number of ordered bases. Start by counting the number of ways to choose the first vector....
– user14972
May 8, 2012 at 11:24

Definition 1

For any natural numbers $$n$$ and $$k$$, define the Gaussian binomial coefficient, $$\binom n k_q$$ by the number of $$k$$-dimensional subspaces of an $$n$$-dimensional vector space.

Theorem 2

$$\binom n k_q=\dfrac{(q^n-1)(q^n-q)\cdots(q^n-q^{k-1})}{(q^k-1)(q^k-q)\cdots(q^k-q^{k-1})}$$

Proof.

To specify a $$k$$-dimensional subspace, we need to specify $$k$$ linearly independent vectors. The first vector can be chosen from among the non-zero vectors in $$q^n-1$$ ways. Note that $$0 \in S \implies S$$ is linearly dependent. The second vector must be chosen outside the span of this vector. Since, the first vector generates a subspace of dimension $$1$$, we have that there are $$q^n-q$$ choices. Proceeding this way, we get that, there are $$(q^n-1)(q^n-q) \cdots(q^n-q^{k-1})$$ ways of specifying a linearly independent set of cardinality $$k$$.

Now note that, there are many linearly independent $$k$$ sets, that generate the same subspace. So, we need to divide this number by the number of $$k$$ sets that generate the same subspace. But, this is what we have already counted in a different fashion: We are asking for the number of basis for a $$k$$ dimensional subspace. That will be the number of linearly independent $$k$$ sets in a $$k$$-dimensional space. So, set $$n=k$$ in the previous count.

This gives us the claim. $$\blacksquare$$

• This blogpost by Prof. Peter Cameron is a nice exposition on Gaussian Coefficients.

• Prof. Amritanshu prasad wrote an expository note on counting subspaces that appeared in Resonance in two parts.

• Will the downvoter care to explain?
– user21436
May 8, 2012 at 11:39
• To the OP: My notation is different from yours. Please note that I have replace $p$ by $q$ in my answer.
– user21436
May 8, 2012 at 11:43
• I am confused about the choice of second vector. i mean how $q^{n}-q$ for second vector is coming? can you explain please? May 8, 2012 at 12:16
• You have chosen the first vector. Say, $v$ wass your choice. What is the span of this vector $v$?
– user21436
May 8, 2012 at 12:17
• I would just note that the numerator and denominator in the $\binom{n}{k}_q$ symbol defined above count ordered bases.
– user145584
Apr 25, 2014 at 4:02