0
$\begingroup$

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?

$\endgroup$

marked as duplicate by Travis, Claude Leibovici, Marc van Leeuwen linear-algebra Jan 5 '16 at 7:01

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 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. $\endgroup$ – Lorenzo Jan 5 '16 at 5:58
  • $\begingroup$ 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. $\endgroup$ – Marc van Leeuwen Jan 5 '16 at 7:00
4
$\begingroup$

Let me try to answer your question:

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.

$\endgroup$
2
$\begingroup$

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})}$$

$\endgroup$

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