Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $V_{n}(F)$ be a vector space over field $F=\mathbb Z_{p}$ with $\dim V_{n} = n$ i.e. cardinality of $V_{n}(\mathbb Z_{p}) = p^{n}$. What is the general criteria to find out the number of bases in such a vector spaces. For example find number of bases in $ V_{2}(\mathbb Z_{3})$. Further how to find out number of subspaces of dimension say $r$. I need a justification with proof. I have a formula but i am unable to understand basic idea behind that formula.

share|improve this question
    
First, let's count the number of ordered bases. Start by counting the number of ways to choose the first vector.... –  Hurkyl May 8 '12 at 11:24
add comment

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer
3  
Will the downvoter care to explain? –  user21436 May 8 '12 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 '12 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? –  srijan May 8 '12 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 '12 at 12:17
    
sir number of elements in a space generated by span(v) will be q-1 . Am i correct? –  srijan May 8 '12 at 12:54
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.