# How many k-dimensional subspaces there are in n-dimensional 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, 2011 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. Oct 8, 2011 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, 2011 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. Oct 8, 2011 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 ... Oct 8, 2011 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.

• What I don't really understand is why does the order matter? A basis is unordered set of vectors, after all, no? Oct 9, 2011 at 6:21
• 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. Oct 10, 2011 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)$ ? Oct 10, 2011 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) Oct 10, 2011 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.

• ...and also because of its usefulness when dealing with things like "q"uantum groups. Jun 17, 2013 at 13:01

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