# Counting subspaces

We are given the finite vector space $V = V(n,p) = \mathbb{F}_p^n$ and two fixed subspaces $W_1, W_2 \subseteq V$ of dimensions $m_1$, $m_2$ respectively. Suppose that the dimension of $W_1 \cap W_2$ is $r$.

How many $k$-dimensional subspaces of $V$ simultaneously intersect $W_1$ in dimension $n_1$, $W_2$ in dimension $n_2$, and $W_1 \cap W_2$ in dimension $r'$?

Further, is there a general argument for counting subspaces when more than two fixed subspaces are involved, given their dimensions and those of their $s$-fold intersections?

P.S. I would also appreciate any references to textbooks or papers where this type of "$q$-combinatorics" is explored in depth.

• I think the way to deal with the first question is to choose an $r^{\prime}$-dimensional subspace $U$ of $W_{1} \cap W_{2}$ and work in $V/U$. The number of choices for $U$ is easily calculated. Jul 19, 2015 at 13:56
• @GeoffRobinson There are ${r \brack r'}_p$ choices for $U$. Then $V/U = W_1/U \bigoplus W_2/U$, but what is the count in $V/U$? Jul 19, 2015 at 14:06
• In $V/U$ you are reduced to counting subspaces which have zero intersection with $W_{1} \cap W_{2}$ (by the way, I don't see the claim that $V/U$ is a direct sum as you state). There is still work to be done, but it's an easier situation. Jul 19, 2015 at 14:10
• The number of $j$-dimensional subspaces of $V$ that are disjoint from a fixed $k$-dimensional subspace is $q^{jk}\left[ {n-k\atop j}\right]$, where $\left[ {n-k\atop j}\right]$ is the $q$-binomial coefficient. A reference for this kind of combinatorics is Section 1.10 and Exercises 1.174-1.202 of Enumerative Combinatorics, vol.\ 1, second ed. Jul 20, 2015 at 1:06
• van Lint and Wilson's ''A Course in Combinatorics''. See also John Baez's week184 and some notes I wrote. Jul 26, 2015 at 23:38

Ok, so the right way to think about this is to consider the maximal filtration generated by $W_1$ and $W_2$. This consists of $0,W_1\cap W_2,W_1,W_2, W_1+W_2,V$. Let these have dimension $0, a, a+b, a+c, a+b+c,a+b+c+e$ and let their intersection with the fixed subspace have dimension $0,a',a'+b',a'+c',a'+b'+c'+d', a'+b'+c'+d'+e'$

This is a relabeling of your parameters except i have added one new variable. Then such a subspace gives:

An $a'$-dimensional subspace of the $a$-dimensional $W_1 \cap W_2$

A $b'$-dimensional subspace of the $b$-dimensional $W_1/(W_1\cap W_2)$

A $c'$-dimensional subspace of the $c$-dimensional $W_1/(W_1\cap W_2)$

Two $d'$-dimensional subspaces, one of $W_1+W_2/W_2$ modulo its $b'$-dimensional subspace, and one of $W_1+W_2/W_1$ modulo its $c'$-dimensional subspace, and an isomorphism between them.

An $e'$-dimensional subspace of the $e$-dimensional $V/(W_1+W_2)$.

A bunch of extension classes.

Other than the extension classes we just get a $q$-analogue of

$$\pmatrix{ a \\ a'}\pmatrix{ b\\ b'}\pmatrix{ c\\ c'}\pmatrix{ b-b'\\ d'}\pmatrix{ c-c' \\ d'}\pmatrix{ e \\ e'} (d'!)$$

And the extension class is

$$p^{(b'+c'+d')(a-a')+e'(a+b+c-a'-b'-c'-d')}$$

Then you can sum over $d'$ to get the answer to your problem.

Messy version:

Given such a subspace, we can choose a basis consisting of

1. $r'$ vectors in $W_1 \cap W_2$
2. $n_1-r'$ additional vectors in $W_1$ that remain linearly independent in $W_1 / (W_1 \cap W_2)$
3. $n_2-r'$ additional vectors in $W_2$ that remain linearly independent in $W_2 / (W_2 \cap W_2)$
4. $\alpha$ additional vectors in $W_1+W_2$ that, modulo the $n_1+n_2-r'$-dimensional subspace spanned by the previous vectors, do not intersect the $m-n_1$-dimensional image of $W_1$ or the $m-n_2$-dimensional image of $W_2$.

5. $\beta$ additional vectors in $V$ that remain linearly independent in $V/(W_1+W_2)$.

where $\alpha+ \beta=k-n_1-n_2+r'$.

It's easy to count the number of possible lists of vectors for the first three, and the number of choices in a fixed subspace. I think it's $$\left[\matrix{ r \\ r'} \right]_p \left[\matrix{ m_1-r \\ n_1-r'} \right]_p \left[\matrix{ m_2-r \\ n_2-r'} \right]_p p^{(r-r') (n_1+n_2-2r')}$$ (A simpler argument along these lines gives a proof of the identity Richard Stanly mentions in the comments)

Similarly for the fifth one

$$\left[\matrix{n-m_1-m_2+r \\ \beta}\right]_p p^{\beta (m_1+m_2-r-k+\beta)}$$

So it remains to see how much the fourth kind of vectors increases the count. Each successive vector of the fourth type we choose must avoid two subspaces - $W_1$ plus the previous vectors and $W_2$ plus the previous vectors. We can count these using inclusion-exclusion because we know the intersection of each type of subspace with the others, as the new vectors we are adding at the fourth step increase the dimension of each by one and the dimension of the intersection by two.

$$\prod_{i=0}^{\alpha-1} ( p^{m_1+m_2-k} - p^{m_1+ n_2-k' + i} - p^{m_2+ n_1-k' + i}+ p^{k+n_1+n_2-2k' +2i})=\prod_{i=0}^{\alpha-1} (p^{m_2-n_2+k'-k-i}-1)(p^{m_1-n_1+k'-k-i}-1)p^{k+n_1+n_2-2k'+2i}$$

The denominator is given by a simpler formula - the number of choices for the remainder of the basis is just $$(\alpha!)_p p^{ \alpha (n_1+n_2-r')}$$

$$\left[\matrix{ r \\ r'} \right]_p \left[\matrix{ m_1-r \\ n_1-r'} \right]_p \left[\matrix{ m_2-r \\ n_2-r'} \right]_p p^{(r-r')(n_1+n_2-2r')}\sum_{\alpha+\beta=n_1+n_2-k'}\left[\matrix{m_2-n_2+k'-k \\ \alpha} \right]_p \left[ \matrix {m_1-n_1+k'-k \\ \alpha}\right]_p (\alpha!)_p\left[\matrix{n-m_1-m_2+r \\ \beta}\right]_p p^{\alpha(k+n_1+n_2-2k'+\alpha-1) +\beta (m_1+m_2-r-k+\beta)}$$

Note that as $p$ goes to $1$ this becomes a perfectly ordinary product of binomial coefficients, because the $\alpha!$ vanishes for $\alpha$ nonzero.

• I am not sure this is correct. In the extreme case where $W_1 = W_2$, I get the count ${r \brack r'}_p {n-r \brack k-r'}_p p^{(k-r')(r-r')}$, using R. Stanley's formula in the comments, but your count yields something different. I hope I didn't mess up my algebra. Jul 27, 2015 at 2:29
• @the_fox Yes, that's not right. I wrote down the subspaces you have to avoid wrong. In fact there is no simple product formula. However if you fix the dimension of the intersection the $k$-dimensional subspace with $W_1 \cup W_2$ you get a product formula. So you have to sum over all these products. Jul 27, 2015 at 2:47
• I'll post an edited version soon. Jul 27, 2015 at 2:58
• Make sure you do that in time so I can award the bounty :) Jul 27, 2015 at 15:06