The number of subspaces over a finite field [duplicate]

How to prove this conclusion

If $V$ is a vector space of dimension $n$ and $F$ is a finite field with $q$ elements then number of subspaces of dim $k$ is

Solution 1:

You want to construct a subspace of dimension $k$, i.e. you want to find the number of ways you can choose $k$ independent vector out of a vector space of dimension $n$.

First see that, no. of elements in $V=q^n$ (because there are $n$ linearly independent vectors in $V$ and each element when multiplied with a scalar from field produce a new element of $V$ )

Now, for the first vector in basis of subspace of dim $k$ can be choosen in $(q^n-1)$ ways (any non zero vector).

Second vector can be choosen in $(q^n-q)$ ways.(any vector independent of first vector will work and there are $q$ multiples of a vector as number of elements in field is $q$).

For third vector, you need it to be independent of first two, so you will get $(q^n-q^2)$

Proceeding in similar manner you will get no. of options of $k_{th}$ vector is $(q^n-q^{k-1})$

This will create your numerator.

Now, same vector space can be made with different basis.

Basically by numerator you get how to choose $k$ linearly independent vector.

Now some of these may generate same vector space.

Thus, to get number of distinct vector spaces we will divide it by number of basis of a $k$ dimensional vector space, which you can calculate by the same procedure as we had done above.

Solution 2:

You want to find the number of subspaces of $\mathbb{F}_q^n$ of dimension $k$.

Consider the following problem: in how many ways can we choose the first $k$ columns of an $n \times n$ matrix over the finite field $\mathbb{F}_q$ so that these $k$ columns are linearly independent. The first column can be any nonzero vector, and so can be chosen in $q^n-1$ ways. The second column can be any vector in the vector space $\mathbb{F}_q^n$ except the $q$ elements in the subspace spanned by the first column (in order to have linear independence). Thus, the second column can be chosen in $q^n-q$ ways. Continuing in this manner, we see that the $k$th column can be any vector in $\mathbb{F}_q^n$ except for vectors in the $(k-1)$-dimensional subspace spanned by the previous columns. Thus, the $k$th column can be chosen in $q^n-q^{k-1}$ ways. This is the numerator in your expression, and it is the number of different bases $(b_1,\ldots,b_k)$ (where order matters) for $k$-dimensional subspaces of $\mathbb{F}_q^n$.

However, different bases can span the same subspace. The number of different bases for a given $k$-dimensional subspace can be obtained using the same approach mentioned in the previous paragraph and is equal to the denominator of your expression. Thus, the ratio is the number of distinct $k$-dimensional subspaces of $\mathbb{F}_q^n$.