# Combinatorics in finite vector space

Let $q$ be a prime power and $V$ a finite $\mathbb F_q$-vector space with two subspaces $I$ and $J$. Let $k$, $a$ and $b$ be non-negative integers. Determine the number of subspaces $K$ of $V$ with $\dim(K) = k$, $\dim(K\cap I) = a$ and $\dim(K\cap J) = b$.

The answer should depend on the numbers $a,b,k$ and $v = \dim(V)$, $i = \dim(I)$, $j = \dim(J), c = \dim(I\cap J)$, but otherwise be independent of the exact choice of $I$ and $J$.

In the case that only a single subspace $I$ is given (say $J = \{0\}$ and $b = 0$), I found the answer $$q^{(k-a)(i-a)}\binom{i}{a}_{\!q} \binom{v-i}{k-a}_{\!q},$$ where $\binom{x}{y}_q$ denotes the Gaussian binomial coefficient.

However for two subspaces $I$ and $J$, this problems looks quite hard to me. Any ideas are welcome. Even the special cases $I \cap J = \{0\}$ or $J \subseteq I$ (both generalizing the case $J = \{0\}$ discussed above) are not clear to me.

-
An interesting question. Can you make progress by grouping the subspaces $K$ according to the dimension of the space $K\cap (I+J)$? Possibly needing to add the dimension of $K\cap I\cap J$ to the mix? –  Jyrki Lahtonen May 15 '13 at 10:55
@JyrkiLahtonen: Thanks for your suggestion! This sounds quite reasonable. In my (unsuccessful) attempts so far I always tried to break it down with respect to $\dim(K\cap I\cap J)$. But I guess I didn't consider do further break it down with respect to $\dim(K\cap (I + J))$. I will think about it. –  azimut May 15 '13 at 11:48
I'm not sure that it works, but it felt impossible to get going without such a grouping (or something else that is invariant under the action of $GL(V)$). Good luck! –  Jyrki Lahtonen May 15 '13 at 11:51

It is usually easier to convert these kind of problems to finite projective geometry, and to look at your subspaces as projective spaces. There is an entire branch of research dedicated to finite projective geometry and I think these basic questions are all solved there. In what I write below, I have ignored the difference of $1$ between vector and projective dimension, to keep it readable for you (as I presume you are more used to vector geometry).

I don't have the books here, so I can't give you a ready formula, but the main idea is always the following: pick an arbitrary I,J with your properties. Now, denote $C=I\cap J$ and denote an extra variable $t=\dim(I\cap J\cap K)$. We will first compute the requested number for a given value of $t$. This is much easier (and that's probably why you succeeded on the $J=\{0\}$ case, as here $t$ is fixed).

Since we know the group actions, we know that indeed all choices are projectively equivalent, hence indeed the number will be independent of the exact spaces chosen. If you want you can even give them special coordinates of your choosing.

Then, within I and J, compute the number of possibilities for $K\cap I$ and $K\cap J$. The number of $t$-spaces in $I\cap J$ is $N_1(t)$, this can be computed. Now, fix any such $t$-space $T=I\cap J\cap K$. Each such choice will yield the same number, so it's merely taking a product with $N_1$ at the end.

In $I$, one can compute the number of $a$-spaces $A$ which have $A\cap C=T$, denote this number by $N_2(t)$. In $J$, one can compute the number of $b$-spaces $B$ which have $B\cap C=T$, denote this number by $N_3(t)$. Now fix such subspaces $A$ and $B$ (again, it doesn't matter which one, since all choices within these constraints are projectively equivalent).

Now, all that is left is counting how many $k$-spaces $K$ there are with $A=I\cap K$ and $B=J\cap K$. This is equivalent to saying that $\langle A,B\rangle = \langle I,J\rangle \cap K$. Denote $X=\langle A,B\rangle$ and $Y=\langle I,J\rangle$, then the problem that we are left with is "Determine the number of $k$-spaces $K$ which intersect $Y$ in $X$." This number is fixed (since $X$ and $Y$ are fixed) and should be a lot easier than your original problem; denote it by $N_4(t)$.

Then the total number for given $t$ is $N_1(t)\cdot N_2(t)\cdot N_3(t)\cdot N_4(t)$, and the original total number you requested (which is for any $t$) is just $$\sum_t N_1(t)\cdot N_2(t)\cdot N_3(t)\cdot N_4(t),$$ where the summation is taken over all nonzero values of the product (there are only finitely many).

-
Many thanks for this answer! My first feeling was that this won't work, since I had tried similar things. But checking the details, I don't see a problem! I get $N_1 = \binom{c}{t}_q$, $N_2 = q^{(a-t)(c-t)}\binom{i-t}{a-t}_q$, $N_3 = q^{(c-t)(b-t)}\binom{j-t}{b-t}_q$. For $N_4$, $X$ has dimension $a + b - t$ and $Y$ has dimension $i + j - c$. This leads to $N_4 = q^{(i + j + t - a - b - c)(k - a - b + t)}\binom{v - a - b + t}{k - a - b + t}_q$. Now the questions are 1) Did I get all the numbers right (probably not)? and 2) Can the resulting formula be simplified? –  azimut Jun 23 '13 at 13:35