40
$\begingroup$

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.

  • 1
    First, let's count the number of ordered bases. Start by counting the number of ways to choose the first vector....2012-05-08

1 Answers 1

52

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 a $n$ dimensional subspace.

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$

Related Reading

  • 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.

  • 0
    I would just note that the numerator and denominator in the $\binom{n}{k}_q$ symbol defined above count *ordered* bases.2014-04-25