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 ?
Great article! By the way, your count of the size of GL(n,q) seems to be off by a factor of (q-1)^n.
Whoops. So it is. Thanks for the correction!
[…] I should check the previous post first. Ok, now I’m back to Qiaochu Yuan’s post “Young diagrams, q-analogues, and one of my favorite proofs“, which at first sight, seem accessible by me. Young […]
[…] In this post, I plan to discuss two (and a half) different applications of category theory to combinatorics. One is reasonably well-known; one is silly and (as far as I know) original, but hopefully gives some insight into something else that’s interested me ever since Qiaochu mentioned it. […]
[…] IV: The unreaso… on GILA III: The orbit-counting …GILA IV: The unreaso… on Young diagrams, q-analogues, a…fermatprime on Self-referential jokes in popu…Qiaochu Yuan on GILA I: Group actions and […]
[…] the weight enumerator is equal to the -factorial […]
Qiaochu, have you looked at Bruce Sagan’s The Symmetric Group? I don’t really grok a lot of the things in this post, but it’s a wonderful introduction to Young tableaux and the representation theory of S_n.
No, I haven’t, but thanks for the suggestion. There’s a lot of books I need to find at MIT once I get back…
I don’t know the answers to any of the questions you’ve asked, but I’ll mention a few things this post reminds me of.
(1) Young tableaux with at most n rows classify irreps of SL(n) (over complex numbers, or rather over any algebraically closed field of characteristic zero). So this provides one connection between GL(n) and the symmetric group.
(2) Over C, it makes sense to talk about “quantum SL(n)” for any non-zero number q. When q is not a root of unity, the representation theory of quantum SL(n) is almost exactly the same as the classical theory — only the Clebch-Gordon decomposition changes, because quantizing only changes the tensor product to be noncommutative (just like it makes multiplication noncommutative). But when q is a pth root of unity, the representation theory is very close to the representation theory “in characteristic p”, except that p need not be a prime.
So this is an answer to what the non-integer values of q should be like. Although it’s a little disappointing.
(3) There is another project, which is to understand SL(n) when n is not a positive integer. Some of this is known: when n is a negative integer there is a reasonable theory, called “supersymmetry” (because it’s better than symmetry). My adviser has suggested that I might look try to understand the non-integer story (and more generally try to classify “semisimple Lie categories” better than has been done). But I haven’t thought about it yet. And for me it would only be over characteristic 0, probably.
Point being, there are really two parameters: q and n. And then one can consider quantum groups in positive characteristic, when I guess there are three parameters, but I believe that these are very poorly understood. Indeed, one of the reasons to study quantum groups is that they give characteristic-zero approximations of positive-characteristic groups of Lie type, as I mentioned above.
Theo-
(1) That connection of the symmetric group to GL(n) is rather different from the one gotten by looking at the field with one element. For one thing, it actually goes horribly wrong (or beautifully wrong, if you like Schur algebras) in characteristic p. Also, it’s wrong for other groups. It’s just one of those odd things about type A that the “Brauer algebra” of GL(n) is the group algebra of the symmetric group.
(3) I hope you’ve read this post http://sbseminar.wordpress.com/2009/02/25/a-warmup-gl_t-for-t-not-an-integer/