1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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