# Maximal chains of nested subspaces

I need to answer the following question:

Let $$V_n(q)$$ be $$n$$-dimensional vector space over $$\mathbb {F}_q$$ with $$\mathbb{F}_q$$ fields with $$q$$ elements. How many different maximal chains of nested subspaces of $$V_n(q)$$ are there?

I know what a maximal chain of an ordered set is but have no idea how to connect it with a vector space. I was desperatedly looking for some explanation but didn't find anything. Any help of you would be very much appreciated!

## 1 Answer

A maximal chain of subspaces will be of the form $$0 \subset F_1 \subset F_2 \subset \ldots \subset F_n = V_n(q)$$, where each $$F_i$$ is $$i$$-dimensional. Indeed, such a chain is maximal because we can't have any subspace $$F$$ with $$F_i \subsetneq F \subsetneq F_{i+1}$$. Conversely, if we have a chain of length $$m < n$$, say $$0 \subset F_1 \subset \ldots \subset F_m \subseteq F_{m+1} := V_n(q)$$, then for some $$i$$, we have $$\dim F_{i+1} - \dim F_i > 1$$ (or $$F_m \subsetneq F_{m+1}$$, in which case we can extend the chain by adding $$V_n(q)$$ at the end). Then we can construct $$F_i \subsetneq F \subsetneq F_{i+1}$$ by picking some $$v \in F_{i+1}\setminus F_i$$ and letting $$F = \text{span}(F_i,v)$$.

Now note that giving a subspace $$F_i$$ is the same as giving a basis for it, and that if $$F_i \subset F_{i+1}$$, we can extend a basis of $$F_i$$ to a basis of $$F_{i+1}$$. So we have reduced the question to finding ordered bases $$\{v_1 < v_2 < \ldots < v_n\}$$ of $$V_n(q)$$ (we then define $$F_i := \text{span}(v_1,\ldots,v_i)$$). Now we just have to be careful to identify two bases $$\{v_i\}$$ and $$\{w_i\}$$ if each $$v_i$$ is a scalar multiple of $$w_i$$, because in that case the bases will give rise to the same subspaces.

Now the question is purely combinatorial. Note that we can never pick the zero vector as a $$v_i$$. Since the $$\mathbb F_q$$-span of a vector has size $$q -1$$ (excluding $$0$$) and $$V_n(q)$$ has $$q^n$$ elements, we have $$(q^n - 1)/(q-1)$$ options for $$v_1$$.

Now $$v_2$$ should not be in $$F_1 = \text{span}(v_1)$$, so there are $$q^n - q$$ choices. However, from these options, $$v_2$$ and $$v_2'$$ give rise to the same subspace $$F_2$$ whenever $$v_2 - v_2' \in F_1$$, so really we want an equivalence class of such an element in $$V_n(q)/F_1$$; i.e. for the counting argument we have to divide by $$q$$ an additional time. Thus there are $$(q^{n}-q)/q(q-1)$$ options for $$v_2$$, $$(q^n - q^2)/q^2(q-1)$$ options for $$v_3$$, etc. So we get $$\prod_{k=0}^{n-1} \frac{q^{n}-q^k}{q^k(q-1)} = \prod_{k=0}^{n-1}\frac{q^{n-k}-1}{q-1}$$ total such chains.