6
$\begingroup$

When $q$ is a prime power, then on the one hand the $q$-binomial coefficient $\binom{n}{k}_q$ equals the number of $k$-dimensional subspaces of $\mathbb{F}_q^n$, and on the other hand it is the generating function of the sequence which sends $r$ to the number of words in two letters $X,Y$ of length $n$ with $k$ occurances of $X$ and with $r$ inversions (i.e. places where $Y$ comes before $X$). Therefore, there must a bijection

$$\{k\text{-dimensional subspaces of } \mathbb{F}_q^n\} \\ \downarrow{\small\cong}\\ \coprod_{r=0}^{k(n-k)} q^r \cdot \{\text{ words in X,Y of length } n \text{ with } k \text{ X's and } r \text{ inversions}\}$$

My question is if you can write down a nice, explicit bijection. I require that its description is independent of the theory of $q$-binomial coefficients, thus doesn't use the calculation of the cardinalities, and that it is also without recursion (since you can easily transform the inductive proof of the equality of cardinalities into a recursive bijection; this doesn't count here).

For $k=1$ the bijection looks as follows: It sends $\langle a_1,\dotsc,a_n \rangle$ to $(a_1/a_{r+1},\dotsc,a_r/a_{r+1}) \cdot Y^r X Y^{n-r-1}$, where $r$ is maximal with $a_{r+1} \neq 0$.

$\endgroup$

1 Answer 1

6
$\begingroup$

You may act similarly as follows.

Let $V$ be a $k$-dimensional subspace of $\mathbb F_q^n$. Take any its base, put its elements into the rows of some matrix, and make it to the reduced row echelon form $B$ (which is unique). The rows of $B$ still form a base of $V$.

Let $r_1$, $r_2$, $\dots$, $r_k$ be the indices of leading elements in rows $1,2,\dots,k$. Then you put into correspondence to $V$ the tuple of all elements of $B$ which are non-fixed (i.e., those not in the leading columns, and not to the left of leading elements), along with the word $Y^{r_1-1}XY^{r_2-r_1-1}XY^{r_3-r_2-1}X\dots XY^{n-r_k}$ read backwards. The freedom of the coefficients provides the exponent of $q$ being $$ (n-r_1-(k-1))+(n-r_2-(k-2))+\dots+(n-r_k), $$ and the number of inversions (in the reversed word) is clearly $$ (n-r_k)+(n-r_{k-1}-1)+(n-r_{k-2}-2)+\dots+(n-r_1-(k-1)), $$ so they trivially coincide.

$\endgroup$
7
  • $\begingroup$ Thank you! I still need to check the details. For some reason I have never heard that the reduced row echelon form only depends on the subspace (which you seem to say), do you have a reference for that? $\endgroup$ Sep 21, 2020 at 11:34
  • $\begingroup$ The reduced row echelon form of a matrix is unique —- see, e.g., en.wikipedia.org/wiki/Row_echelon_form ;) You may prove this just by choosing it from bottom to top. On the other hand, the matrices which can be obtained from a certain matrix via elementary row transforms are those with the same linear span of rows. $\endgroup$ Sep 21, 2020 at 11:39
  • $\begingroup$ Ok. I was aware that it only depends on the matrix, but your 2nd sentence explains why it then also only depends on the subspace generated by the rows. $\endgroup$ Sep 21, 2020 at 11:41
  • 4
    $\begingroup$ This is very standard. It is the Bruhat decomposition (a.k.a. Schubert cell decomposition) of the Grassmannian, in the case of finite fields. See the proof of Proposition 1.7.3 of Stanley's "Enumerative Combinatorics," Vol. 1, 2nd ed: math.mit.edu/~rstan/ec/ec1.pdf $\endgroup$ Sep 21, 2020 at 14:04
  • 4
    $\begingroup$ This bijection is described very clearly (but without reference to Schubert cells etc.) in D. E. Knuth, Subspaces, subsets, and partitions, J. Combin. Theory Ser. A 10 (1971), 178–180, sciencedirect.com/science/article/pii/0097316571900227 $\endgroup$
    – Ira Gessel
    Sep 21, 2020 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.