# Number of $k$-dimensional subspaces in $V$ [duplicate]

I know my following question is somewhat similar to this one but still I need help .

How many $k$-dimensional subspaces of a $n$-dimensional vector space $V$ over the finite field $F$ with $q$ elements are there?

## marked as duplicate by Travis, Claude Leibovici, Marc van Leeuwen linear-algebra StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jan 5 '16 at 7:01

• Hint: First over count: compute the number $k$-tuples of $k$ independent vectors. Then ask: for a given $k$ dimensional subspace, how many possible basis does it have. This will tell you how much you have over counted by. – Lorenzo Jan 5 '16 at 5:58
• This number is given by the Gaussian binomial coefficient $\binom nk_q$, for which the question provides the main combinatorial interpretation. This is well known, refer to the link for details about these coefficients. – Marc van Leeuwen Jan 5 '16 at 7:00

Let us first look at the case of one-dimensional subspaces: Every one-dimensional subspace is spanned by non-zero vector, which there are $q^n-1$ many of. Two of these vectors span the same subspace if and only if they are non-zero scalar multiples of each other; we have $q-1$ such scalars. Thus we have $\frac{q^n-1}{q-1}$ one-dimensional subspaces.

Simlilary we can count the number of $k$-dimensional subspaces for $0 \leq k \leq n$. We will need the following formula:

Proposition Let $W$ be an $n$-dimensional vector space over $\mathbb{F}_q$, the finite field with $q$ elements, and let $0 \leq k \leq n$. Then there exist $$\frac{(q^n-1)(q^n-q)(q^n-q^2) \dotsm (q^n-q^{k-1})}{k!}$$ many linearly independent subsets of $W$ consisting of $k$ elements.

Proof: We first figure out the number of linearly independent families of $k$ elements: For the first member $b_1$ we can pick any non-zero vector, so we have $q^n-1$ choices. For the second member $b_2$ we can take any vector not in the span of $b_1$. So we have $q^n-q$ choices for $b_2$. Continuing this we can pick $b_i$ arbitrarily outside of the span of the previous members $b_1, \dotsc, b_{i-1}$, so we have $q^n - q^i$ choices for $b_i$. Thus we find that we have $$(q^n-1)(q^n-q)(q^n-q^2) \dotsm (q^n-q^{k-1})$$ many linearly independent families $(b_1, \dotsc, b_k)$.
Two of these families represent the same linearly indendent subset if and only if they are the same up to reorderding of its members. Because there are $k!$ such reorderings we have $$\frac{(q^n-1)(q^n-q)(q^n-q^2) \dotsm (q^n-q^{k-1})}{k!}$$ many linearly indepndent subsets consisting of $k$ elements.

We know that every $k$-dimensional subspace of $V$ is spanned by $k$ linearly indendent vectors of $V$. So by the above proposition we have at most $$\frac{(q^n-1)(q^n-q)(q^n-q^2) \dotsm (q^n-q^{k-1})}{k!}$$ $k$-dimensional subspaces.

Now the same subspace $U$ is spanned by many different linearly independent subsets, say $L$ many. These $L$ subsets are precisely the bases of $U$. By we above formula we know that there are $$\frac{(q^k-1)(q^k-q) \dotsm (q^k-q^{k-1})}{k!}$$ many such bases.

Putting this together we find that there are $$\frac{ \left( \frac{(q^n-1)(q^n-q)(q^n-q^2) \dotsm (q^n-q^{k-1})}{k!} \right) }{ \left( \frac{(q^k-1)(q^k-q)(q^k-q^2) \dotsm (q^k-q^{k-1})}{k!} \right) } = \frac{ (q^n-1)(q^n-q) \dotsm (q^n-q^{k-1}) }{ (q^k-1)(q^k-q) \dotsm (q^k-q^{k-1}) }$$ many different $k$-dimensional subspaces.

In this M.SE post it is proven that there are $$\frac{(q^n-1)(q^n-q)\cdots(q^n-q^{k-1})}{k!}$$ many unordered linearly independent sets of size $k$ of $\mathbb{F}_q^n$. Therefore the total number of possible bases is for a given subset is

$$\frac{(q^n-1)(q^n-q)\cdots(q^n-q^{k-1})}{k!}$$

However, we need to divide by the number of bases of $\mathbb{F}_q^k$, as any two choices of bases for the same copy of $\mathbb{F}_q^k$ produces the same subspace. Thus we get

$$\frac{(q^n-1)(q^n-q)\cdots(q^n-q^{k-1})}{(q^k-1)(q^k-q)\cdots(q^k-q^{k-1})}$$