find the number of subspaces $W$ such that $U\subseteq W$

Let $$V$$ be a vector space of dimension $$n$$ over a finite field $$F$$ with $$q$$ elements, and let $$U\subseteq V$$ be a subspace of dimension $$k$$. How many subspaces $$W\subseteq V$$ of dimension $$m$$ such that $$U\subseteq W$$ do we have $$(k\leq m\leq n)$$?

Hint: look at the set: $$\{ (U,W) \mid U \subseteq W \subseteq V; \, \dim(U)=k, \, \dim(W)=m \}$$

I have no idea how to use the hint. I know that the number of subspaces of dimension $$k$$ is: $$\frac{\prod_{i=0}^{k-1} (q^{n-1}-1)}{\prod_{i=0}^{k-1} (q^{k-1}-1)}$$ and I don't know how to proceed from here.

• Hint: dig into why that formula counts subspaces of dimension $k \leq n$. Commented Jul 20, 2022 at 17:16

Given a basis $$\{v_1,v_2,\dots, v_k\}$$ for $$U$$, how many ways can you extend the basis to a larger linearly independent set?

So, the next vector can't be a linear combination of the $$v_1,\dots, v_k$$. How many linear combinations are there? There are $$q^k$$. So since the vector space has $$q^n$$ elements, we get $$q^n-q^k$$ ways of adding one more linearly independent vector.

Similarly, for the next one there are $$q^n-q^{k+1}$$.

So, we get $$\prod_{j=0}^{n-k-1}(q^n-q^{k+j})$$.

Now we need to remember that there are $$l_m=(q^n-1)(q^n-q)\dots (q^n-q^{m-1})$$ different bases for each $$m$$-dimensional subspace (by similar reasoning) . So we divide.

Get $$\prod_{j=0}^{n-k-1}(q^n-q^{k+j})/l_{k+j+1}$$

Cpc's answer is fantastic, but here is a more high-level presentation. Noether's fourth isomorphism says that the subspaces of $$V$$ which contain $$U$$ are in bijection with subspaces of $$V/U$$. Therefore, the number of $$W$$ with $$U\subseteq W\subseteq V$$ and $$\dim W=m$$ is the same as the number of subspaces of $$V/U$$ with dimension $$m-k$$, which is just the $$q$$-binomial coefficient $$\binom{n-k}{m-k}_q$$.

The point of the hint is to count the elements of that set: given what you already know, it is easy to do it by first choosing $$W$$ then choosing $$U$$. Doing it the other way is easy in terms of the number you're trying to compute. And the two enumerations must be the same. This avoids repeating the argument that you used to establish the subspace counting formula in the first place.

• No, $U$ cannot be chosen because it is fixed, given. Plus, your answer, being stated in words and not in formulae, is very unclear and confusing. Commented Jul 21, 2022 at 14:44
• @JBL’s answer is trying to explain the hint, without doing the problem for you. $U$ is fixed in the original problem you’re trying to solve but not in the problem described in the hint. As JBL says, try to count the set in the hint in two ways. One is easy: For each $W$ count all the $U$’s. One involves the answer to the question you’re interested in: for each $U$ count all the $W$’s. They both tell you the size of the set in the hint, so the answers must be equal. Commented Jul 21, 2022 at 15:27
• Thanks, Jamie Radcliffe. Alex M., the next time you're confused about something, perhaps you should try politely asking for clarification.
– JBL
Commented Jul 21, 2022 at 17:26