# How many k-dimensional subspaces there are in n-dimentional vector space over $\mathbb F_p$?

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.

-
For (3), unfortunately, just choosing $k$ nonzero vectors (even if no two of them lie in the same one-dimensional subspace) won't necessarily give you a $k$-dimensional subspace because the $k$ vectors might not be linearly independent. Instead, you should count the number of possible bases of size $k$ by adding one vector at a time to the basis, remembering that each new vector must be linearly independent of the previous ones. (Do the case $k=2$ first.) After you count bases, you count subspaces by determining how many bases gives you the same subspace. –  Ted Oct 8 '11 at 6:44
"unfortunately, just choosing k nonzero vectors <...> won't necessarily give you a k-dimensional subspace because the k vectors might not be linearly independent." I completely agree with this, however, choosing k nonzero vectors from different 1-dimensional subspaces will give us a set of linear independent vectors. –  Daniil Oct 8 '11 at 6:48
No, it won't. Suppose you choose $x$, $y$, $x+y$, where $x$ and $y$ are not multiples of each other. No two of those lie in the same one-dimensional subspace, but they are not linearly independent. –  Ted Oct 8 '11 at 6:49
You are absolutely right, thank you. So for the k = 2 we have $p^n - 1$ choices for the 1st vector and $p^n - 1 - (p-1) = p^n -p$ for the second (since p-1 vectors are linearly dependent with the first one). Is it correct? I am not sure how to go about determining how many bases gives me the same subspace tho. –  Daniil Oct 8 '11 at 7:25
@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 ... –  Jyrki Lahtonen Oct 8 '11 at 7:29

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.
This is just there to make the calculation a bit easier. You can also derive a formula for the number of unordered sets, but the way to do that would be to find a formula for ordered sets and then dividing by $k!$. Then of course you have to do the same for the number of bases for the subspace (now thinking of a basis as an unordered set) and the factors $k!$ cancel out. –  Florian Oct 10 '11 at 8:40
Ok, so if I understand correctly, the number of order linear independent vectors of the size k is $(p^n-1)(p^n-p)(p^n - 1 - (p-1)^2)\cdots(p^n - 1 - (p - 1)^k)$ ? –  Daniil Oct 10 '11 at 10:27
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) –  Daniil Oct 10 '11 at 10:50
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.