Young diagrams, q-analogues, and one of my favorite proofs

I’ve decided to start blogging a little more about the algebraic combinatorics I’ve learned over the past year. In particular, I’d like to present one of my favorite proofs from Stanley’s Enumerative Combinatorics I.

The theory of Young tableaux is a great example of the richness of modern mathematics: although they can be defined in an elementary combinatorial fashion, interest in the theory is primarily driven (as I understand it) by their applications to representation theory and other fields of mathematics. The standard application is in describing the irreducible representations of the symmetric group in characteristic zero. I’ll be describing a more elementary aspect of the theory: the relationship between Young diagrams and -binomial coefficients.

Young diagrams can be defined as a visual representations of partitions. A partition of is a weakly decreasing sequence such that . Partitions uniquely describe cycle decompositions, hence conjugacy classes, of the symmetric group, which is a hint at the connection to representation theory. A Young diagram of the partition consists of rows of boxes where the row has boxes. Let denote the poset of Young diagrams that fit into an box, ordered by inclusion: equivalently, one can define the full Young lattice and define to be the elements less than or equal to the partition. (One can then define a standard Young tableau to be a chain in the Young lattice, but we will not need this notion.) One can easily check that the following is true.

Proposition: .

The rest of this post explains the -analogue of this result.

If this counting result isn’t clear, note that a Young diagram uniquely describes a path from the bottom left to the top right corner of an box, so this is a path-counting exercise.

Now, to specialize a counting result we usually introduce an auxiliary combinatorial parameter. There are many natural parameters associated to Young diagrams, such as size of the largest partition, but the one we want to investigate is perhaps the simplest: the number of boxes, which we’ll denote since the number of boxes in a Young diagram describes its rank in the Young lattice, hence in . Our goal today is to compute the rank generating function

.

Since , we should expect this function to behave like a generalization of the binomial coefficients. This hypothetical (for now) generalization we’ll refer to as a -binomial coefficient. By taking “transposes” of Young diagrams (flipping them across the diagonal), it’s clear that , so at least one property of the usual binomial coefficients carry through. What other properties do we want to prove? Well, the usual binomial coefficients are characterized by the identities

(The binomial coefficient is equal to zero both for the obvious combinatorial reason and so that the second identity is true without qualification.) The first identity is also true for ; the empty partition has rank zero. The second identity generalizes as follows.

Proposition: .

The proof is more or less a generalization of the proof for the binomial coefficient identity. Consider the first (longest) row of a Young diagram in . If it is not of length , then the Young diagram fits into a “thinner” box; that is, it is an element of . Otherwise, we can delete it to obtain a “shorter” box; that is, it corresponds to an element of . The factor of accounts for the deletion.

This last identity characterizes the -binomial coefficients, which are defined as follows: define

.

Since , we take this as our -analogue of the number . We then define the -factorial

and finally the -binomial coefficient

.

Although it is not obvious from the definition, the -binomial coefficient is a polynomial with non-negative integer coefficients in . I claim that

,

which then gives the desired identity by induction over . However, without a combinatorial interpretation of the -binomial coefficient it is difficult to give a conceptual (read: bijective) proof of either this identity or the desired result, so it’s time to give one.

Proposition: If is a power of a prime, then is the number of -dimensional subspaces of .

The philosophy here is that there is a strong formal similarity between the poset of subspaces of a vector space and the poset of subsets of a set; there is an even deeper philosophy that (pointed) sets are “really” vector spaces over a mysterious object called , the field with one element. Of course, there is no field with one element. You can find some interesting discussion of this idea at the Wikipedia article, week186, week259, the n-category cafe, the Secret Blogging Seminar, Neverending Books, …. In any case, isn’t it great that mathematicians can think about statements like “Coxeter groups are algebraic groups over ” before having a rigorous framework in which to prove them?

Anyway, this is all a little bit over my head, to say the least, but at least this particular proof is not too bad. Stanley’s proof is by a neat counting argument, but I’d like to take this opportunity to introduce another object. The group consists of the group of invertible linear transformations on , i.e. invertible matrices with entries in . We construct such a matrix column-by-column. The first column can be an arbitrary nonzero vector, so there are possibilities. The next columns are arbitrary, except that they must be linearly independent of the previous choices, so there are possibilities for the second column, for the third, etc.; finally, there are possibilities for the last column. We find that

.

Of course, we should expect this; there is a sense in which should reduce to the symmetric group in the limit . (Actually, for reasons Stanley discusses, this analogy is not quite right.) acts transitively on the set of -dimensional subspaces of , which is an example of a Grassmannian. It follows from the orbit-stabilizer theorem that

where denotes the stabilizer subgroup of any particular -dimensional subspace. Without loss of generality, we can compute the stabilizer subgroup of the space spanned by the first standard basis vectors, which is not too hard to describe: any stabilizer is block upper-triangular with a block consisting of an element of and columns chosen arbitrarily so that the resulting transformation has full rank. By the same argument as in the case, the first block can be chosen in ways and the rest of the columns can be chosen in ways. We find that

as desired. For comparison’s sake, here is the corresponding proof: acts transitively on the set of subsets of size , and a stabilizer of a subset of size consists of a permutation in fixing the subset and a permutation in fixing its complement.

As interesting as this computation is, what does it have to do with Young diagrams? Remember that we’re trying to prove the following:

Theorem: .

So Young diagrams should appear as a convenient way to organize some “decomposition” of the Grassmannian. According to Stanley, this decomposition is called the “cellular decomposition” of the Grassmannian, and it touches on some deep stuff like Bruhat decomposition and Schubert cells. The actual decomposition, however, is wonderfully simple: it’s just row reduction!

More precisely, to every matrix with entries in of full rank one can associate its row space, which is an element of ; this gives an equivalence relation on such matrices. The standard choice of representative of each equivalence class is a matrix in row-reduced echelon form. Stanley’s example of a typical such matrix for is

where the asterisks denote that the entry in that location is arbitrary. Such matrices are uniquely characterized by the locations of the first nonzero entry in each row, which must be a , and the entries in asterisks. But as you can see, the asterisked entries have precisely the shape of a Young diagram in . (The columns without asterisks are the ones occupied by s, of which there are .) Constructing an rref matrix from a Young diagram is easy as well. I hope the placement of s is clear from the example; if not, you can refer to the details in the second edition of the first chapter of EC1, which is freely available online.

In other words, counts the number of ways to fill each box of a Young diagram in with entries from . Such a filling uniquely determines a reduced row echelon form of a matrix whose row space uniquely determines an element of . And the result follows. (More precisely, we have proven that two polynomials in one variable take the same value at an infinite number of integers, from which it follows that the two polynomials are identically equal.) As far as I can tell, the abstract theory of Grassmannians is a way to repeat this argument in a coordinate-free setting. I wish I knew more about it.

Questions

Sometimes there’s a way to interpret the -binomial coefficients at non-integer values. The big example I’m thinking of is , for the following reason: let be the Fibonacci numbers and define the “fibotorial”

.

Then we have the curious identity

.

(This is just an application of Binet’s formula.) These functions are sometimes referred to as Fibonomial coefficients. So, what combinatorial can be attached to Fibonomial coefficients that relates them to Young diagrams? In what sense is it possible to construct an analogue of finite field theory for non-integer values of ?

About these ads