24
$\begingroup$

I am asked to find how many there are $k$-dimensional subspaces in vector space $V$ over $\mathbb F_p$, $\dim V = n$.

My attempt: 1) Let's find a total number of elements in $V$: assume that $\{v_1, v_2, \cdots, v_n\}$ is a basis in $V$. Then, for every $v \in V$ we can write down $ v = a_1 v_1 + a_2 v_2 + \cdots + a_n v_n $ and since the coordinates ($a_1, \cdots, a_n$) are from $\mathbb F_p$ there are $p^n$ vectors in $V$; $p-1$ without the zero vector.

2) Let's look at a situation where $k=1$. Let's call this 1-dimensional space V'. \forall v' \in V'. v' = a_1 v_1 where $v_1$ is a basis in V'. We know that if there are two non-zero vectors u \in V'_1 and v \in V'_2, they are not linear dependant. So, every 1-dimensional subspace has $(p-1)$ basises. Therefore, there are $\frac{p^n - 1}{p-1}$ possible 1-dimensional subspaces in $V$

3) k-dimensional subspace is defined by the set of it's basises. Since basis can not contain zero vectors we can write down the formula for selecting $k$ linear independent vectors: $C^k_m (p-1)^k$, where $m = \frac{p^n - 1}{p-1}$. Here we first choose $k$ 1-dimentioanl subspaces and then we choose one of $(p-1)$ non-zero vectors from each of the subspaces.

4) .. unfortunately, this is where I am stuck. My intuition says that the answer may be $\frac{p^n - 1}{(p-1)^k}$, but this might be completely wrong and I don't know how to go about finishing the problem.

Thanks in advance.

  • 0
    @Daniil That is correct. To count the number of (ordered) bases giving you the same subspace you just redo the same calculation. Keeping in mind that this time you can only pick the vectors from this **fixed** $k$-dimensional subspace ...2011-10-08

3 Answers 3

5

Let $n=\dim V$, where $V$ is a vector space over any finite field $\mathbb{F}$ with $|\mathbb{F}|=r$ and $W$ is a $k$-dimensional subspace of $V$. First of all we count the number of basis of $W$. There are $r^k-1$ non zero vectors in $W$, so to select a base for $W$, first member could be selected in $r^k-1$ way. Second member in $r^k-r$ way and so on. Hence the total number is $s=(r^k-1)(r^k-r)\cdots (r^k-r^{k-1})$.

How many $k$-element subsets are there in $V$, each of which generates a $k$-dimensional subspace of $V$? The answer is as follows: to construct such a subset $A=\{v_1,\cdots , v_k\}$, obviously $v_1$ could be selected in $r^n-1$ way, the vector $v_2$ in $r^n-r$ way, $\cdots$, and $v_k$ in $r^n-r^{k-1}$ way. So there are $t=(r^n-1)( r^n-r)(r^n-r^{k-1})$ of such subsets. Let us to call this family of subsets of $V$ with $\mathcal{B}$ and the family of basis of $W$ with $\mathcal{A}$. The size of $\mathcal{A}$ is $s$ and the size of $\mathcal{B}$ is $t$. A member $A$ in $\mathcal{B}$ generates $W$ if and only if $A$ lies in $\mathcal{A}$, on the other hand any $k$-dimensional subspace of $V$ corresponds to a member of $\mathcal{B}$ and as $W$ was typical, in $\mathcal{B}$ there are $s$ elements which all of them generate same subspace. Therefore the number of different $k$-dimensional subspaces of $V$ is $t/s$.

8

Just for the record, the number asked for here is the Gaussian binomial coefficient $\binom nk_q$ evaluated at $q=p$. The indeterminate of the Gaussian binomial coefficient is traditionally called $q$, and I guess this is in particular because of the usefulness of setting it equal to the order of a finite field.

  • 1
    ...and also because of its usefulness when dealing with things like "q"uantum groups.2013-06-17
7

Here is a hint: Find a formula for the number of possibilities to choose $k$ linearly indepenent vectors in $\mathbb{F}_p ^n$ (where order matters). Each of these choices serves as a basis for a $k$-dimensional subspace, but for each subspace there are several bases, so you have to divide by the number of bases for each subspace - and computing this number involves essentially the same formula as above.

  • 1
    Sorry, that should be $(p^n-1)(p^n-p)\cdots(p^n-p^{k-1})$ since for $k$th vector there are $p^{k-1}$ vectors in previous subspaces (so if we choose a vector from such subspace it would be linear dependent with previous one)2011-10-10