How many subspaces can be formed in a vector space over a finite field?

[Euge]

Here is this week's POTW:

-----
Find a formula for the number of subspaces of a vector space of dimension $n$ over a finite field with $p$ elements.

-----

Remember to read the https://mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to https://mathhelpboards.com/forms.php?do=form&fid=2!

 

[Euge]

No one answered this week's problem. You can read my solution below.

Spoiler

Let $V$ be an $n$-vector space over a finite field $\Bbb F_p$ of $p$ elements. The number of subspaces of $V$ is

$$1 + \sum_{k = 1}^n \frac{(p^n - 1)(p^n - p)\cdots (p^n - p^{k-1})}{(p^k - 1)(p^k - p)\cdots (p^k - p^{k-1})}$$

Let $k$ be a fixed integer $>1$. First we enumerate the number of subspaces of dimension $k$. A $k$-dimensional subspace is formed by $k$ linearly independent vectors. The first independent vector $v_1$ must be nonzero, so there are $p^n - 1$ choices for $v_1$. Having chosen independent vectors $v_1,\ldots, v_{j}$, we choose $v_{j+1}$ outside the $j$-dimensional subspace spanned by $v_1,\ldots, v_j$, which has $p^j$ elements. Hence there are $p^n - p^j$ ways to choose $v_{j+1}$. Thus, there are $(p^n - 1)(p^n - p)\cdots (p^n - p^{k-1})$ ways to form a linearly independent set $\{v_1,\ldots, v_k\}$ of $k$-vectors. However, there may be repetition: two sets of $k$-linearly independent vectors span the same subspace if and only if they are bases of the subspace. So we divide by the total number of bases of a vector space of dimension $k$. A similar argument to the one given is $(p^k - 1)(p^k - p)\cdots (p^k - p^{k-1})$. So there are
$$\frac{(p^n - 1)(p^n - p)\cdots (p^n - p^{k-1})}{(p^k - 1)(p^k - p)\cdots (p^k - p^{k-1})}$$ subspaces of $V$ of dimension $k$. Since there is only one subspace of dimension zero, the total number of subspaces of $V$ is

$$\sum_{k = 0}^n (\text{no. of subspaces of $V$ of dimension $k$}) = 1 + \sum_{k = 1}^n \frac{(p^n - 1)(p^n - p)\cdots (p^n - p^{k-1})}{(p^k - 1)(p^k - p)\cdots (p^k - p^{k-1})}$$