Subspaces and intersections

Question

Stuck in step 3! See my sketch of proof below the theorem I am trying to prove: Any other approach is welcome!

Theorem: Let $W$ be a k-dimensional subspace of $V$. The number of ${k'}$-dimensional subspaces of $V$ which intersect $W$ in an i-dimensional subspace is given by $$q^{(k'-i)(k-i)} {n-k \brack k'-i}_q{k\brack i}_q$$ Proof (Draft)

Step 1: Choose an i-dimensional subspace of W : ${k\brack i}_q$ ways

Step 2: Choose $(k'-i)$-dimensional subspace of $V\setminus W$ :${n-k \brack k'-i}_q$ ways

Step 3: How do we get the first term ($q^{(k'-i)(k-i)}$)??

P.S: this theorem was mentioned without proof in preliminaries on the paper I am studying (on some codes for distributed storage systems: "https://arxiv.org/abs/1701.07501"). In the paper there is a small section about Gaussian coefficient.

Answer 1

First recall that $$(q^n - 1) \cdots (q^n - q^{k - 1})$$ counts the number of ways to pick a linearly independent set of $k$-vectors in a vector space of size $q^n$. This over-counts the number of $k$-dimensional subspaces because two linearly independent sets may span the same subspace.

The quantity $$(q^k - 1) \cdots (q^k - q^{k - 1}) $$ counts the number of ways to pick a basis (linearly independent set of size $k$) for a given vector space of size $q^k$. Thus the number of $k$-dimensional subsets of a vector space of size $q^n$ is

$$ \frac{(q^n - 1) \cdots (q^n - q^{k - 1})}{(q^k - 1) \cdots (q^k - q^{k - 1})} = \begin{bmatrix} n \\ k \end{bmatrix}_q.$$

---

Now let $V$ be a given vector space of size $q^n$ and let $W$ be a fixed $k$-dimensional subspace of $V$. We know that there are $q^n - q^k$ vectors in $V \setminus W$. Thus we can pick a linearly independent set of size $k' - i$ from them in

$$ (q^n - q^k)(q^n - q^{k + 1}) \cdots (q^n - q^{k + k' - i - 1})$$

ways. We can factor out a $q^k$ from each of the $k' - i$ multiplicands to get

$$ q^{k(k' - i)} (q^{n - k} - 1)(q^{n - k} - q) \cdots (q^{n - k} - q^{k' - i - 1}). $$

Notice that we are over-counting by a factor of

$$ q^{i(k' - i)} (q^{k' - i} - 1) \cdots (q^{k' - i} - q^{k' - i - 1}). $$

Distributing a $q^i$ to each term gives

$$ (q^{k'} - q^{i}) \cdots (q^{k'} - q^{k' - 1}). \tag{$*$}$$

If $W'$ is the subspace of size $q^{k'}$ that we are interested in then $(*)$ tells us the number of ways to pick a set of $k' - i$ linearly independent vectors in $W'$. This counts the number of ways to extend a basis for $W' \cap W$ to a basis for $W$.

Correcting for this we have

$$ \begin{bmatrix} k \\ i \end{bmatrix}_q $$

ways to pick an $i$-dimensional subspace from $W$, times

$$ (q^n - q^k) \cdots (q^n - q^{k + k' - i - 1}) $$

ways to pick a linearly independent set that extends the $i$-dimensional subspace to a $k'$-dimensional one, $W'$. We divide by

$$ (q^{k'} - q^{i}) \cdots (q^{k'} - q^{k' - 1}) $$

which corrects for the fact that multiple choices of linearly independent sets give the same $W'$.

Hence in total we have

\begin{align} \begin{bmatrix} k \\ i \end{bmatrix}_q \frac{(q^n - q^k) \cdots (q^n - q^{k + k' - i - 1})}{(q^{k'} - q^{i}) \cdots (q^{k'} - q^{k' - 1})} &= \begin{bmatrix} k \\ i \end{bmatrix}_q \frac{q^{k(k' - i)} (q^{n - k} - 1) \cdots (q^{n - k} - q^{k' - i - 1})}{q^{i(k' - i)} (q^{k' - i} - 1) \cdots (q^{k' - i} - q^{k' - i - 1})} \\ &= q^{(k' - i)(k - i)} \begin{bmatrix} n - k \\ k' - i \end{bmatrix}_q \begin{bmatrix} k \\ i \end{bmatrix}_q. \end{align}

Answer 2

If you follow the reference associated with this claim, you can find the key result contained in the proof of Lemma 7, namely that given an $n$-dimensional subspace $X$, and an $i$-dimensional subspace $Z \subset X$, the number of $j$-spaces $Y$ with $Y \cap X = Z$ is given by $q^{(j-i)(k-i)}{n-k \brack j-i}_{q}$.

This count is obtained by counting the number of ways to complete the basis for $Y$ from a basis for $Z$: you have $q^{n} - q^{k}$ choices for the first additional vector (total number of vectors outside $X$), then you have $q^{n} - q^{k+1}$ choices for the next, $\ldots$, out to $q^{n} - q^{k+j-i-1}$. Then you need to divide by the total number of ways to complete a basis for a specific $Y$ from the basis for $Z$. I'll leave the reference to complete the details for this method of proof.