I have the following problem from Van Lint and Wilson's book on combinatorics and have no idea how to solve it. The problem is the following:

Determine the exponents $e_i$ (the may be functions of $m$,$n$, and $k$ as well as $i$ ) so that the following identity is valid: $${n + m\choose k}_q = \sum_{i = 0}^{k}q^{e_i}{n\choose i}_q{m\choose k-i }_q$$

Could anyone give me a hint on how to solve this problem? I understand that the left hand side is counting the number of $k$-dimensional subspaces of a vector space of dimension $n + m$. In the left hand side, the two q-binomial terms are trying to count the number of subspaces of dimension $k$ by counting first the number of subspaces of dimension $i$ from a vector space of dimension $n$ and the the number of subspaces of dimension $k-i$ of a vector space of dimension $m$, however, I don't understand how to think of the $q^{e_i}$ term.

Thanks for any help or helpful reading!

  • $\begingroup$ Try for $k=0$ or $1$, and some simple $m,n$. I dont know the theory of q-analogs but try to start from the more simple cases to see if you can see a pattern. $\endgroup$ – Masacroso Sep 25 '16 at 3:28

After a year a think restraining ourselves to a hint is unnecessary.

Here's a $\mathbb{F}_q$-linear algebraic interpretation of Chu-Vandermonde convolution's $q$-analog:

$$ \left[\begin{array}{c} m+n \\ k \end{array}\right]_q=\sum_{r+s=k} q^{r(n-s)} \left[\begin{array}{c} m \\ r \end{array}\right]_q\left[\begin{array}{c} n \\ s \end{array}\right]_q . $$

Identify $\mathbb{F}_q^{\,m+n}$ with $\mathbb{F}_q^{\,m}\times\mathbb{F}_q^{\,n}$. Given any subspace $V$ (of dimension $k$), its elements look like $(x,y)$ in this direct product, and if we have $(x,a),(x,b)\in V$ then their difference $(0,a-b)\in V$ too. In light of this, define $X$ to be the image of $V$ under the projection to the first factor $\mathbb{F}_q^{\,m}$ and define $Y$ to be the intersection of $V$ with $0\times\mathbb{F}_q^{\,n}$, i.e. the kernel of the projection's restriction to $V$. For every element $x\in X$ there are a range of $v\in\mathbb{F}_q^{\,n}$ for which $(x,v)\in V$, and all of them are equal modulo the subspace $Y$. Thus, $V$ induces a linear map $X\to \mathbb{F}_q^{\,n}/Y$.

Conversely, given any pair of subspaces $X\le\mathbb{F}_q^{\, m}$, $Y\le\mathbb{F}_q^{\,n}$ and linear map $\phi:X\to \mathbb{F}_q^{\,n}/Y$, we can reconstruct $V$ as the union of cosets $\bigcup_{x\in X}\big(x+\phi(x)\big)$. If $\dim X=r$ and $\dim Y=s$, then the number of such linear maps equals the number of $(n-s)\times r$ matrices over $\mathbb{F}_q$, which is $q^{r(n-s)}$.


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.