Combinatorial Representation Theory

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia

Last update: 17 September 2013

Part I

2. Answers for Sn, the symmetric group

Most people in the field of combinatorial representation theory agree that the field begins with the fundamental results for the symmetric group Sn. Let us give the answers to the main questions for the case of Sn. The precise definitions of all the objects used below can be found in Appendix A2. As always, by a representation of the symmetric group we mean a representation of its group algebra A=Sn.

I. What are the irreducible Sn-modules?

(a) How do we index/count them?
There is a bijection Partitionsλofn 1-1 Irreducible representationsSλ.
(b) What are their dimensions?
The dimension of the irreducible representation Sλ is given by dim(Sλ) = # of standard tableaux of shapeλ = n!xλhx, where hx is the hook length at the box x in λ, see Appendix A2.
(c) What are their characters?
Let χλ(μ) be the character of the irreducible representation Sλ evaluated at a permutation of cycle type μ=μ1,μ2,,μ. Then the character χλ(μ) is given by χλ(μ)=T wtμ(T), where the sum is over all standard tableaux T of shape λ and wtμ(T)= i=1nf (i,T), where f(i,T)= { -1, ifiB(μ) andi+1 is sw ofi, 0, ifi,i+1 B(μ),i+1 is ne ofi, and i+2is sw of i+1, 1, otherwise, and B(μ)={μ1+μ2++μk|1k}. In the formula for f(i,T), sw means strictly south and weakly west and ne means strictly north and weakly east.

C. How do we construct the irreducible modules?

There are several interesting constructions of the irreducible Sλ.

(i) via Young symmetrizers.
Let T be a tableau. Let R(T) = permutations which fix the rows ofT, as sets; C(T) = permutations which fix the columns ofT, as sets; P(T)=wR(T) w,andN(T)= wC(T)ε (w)w, where ε(w) is the sign of the permutation w. Then SλSnP(T) N(T), where the action of the symmetric group is by left multiplication.
(ii) Young’s seminormal construction.
Let Sλ=-span- {vT|Tare standard tableaux of shapeλ} so that the vectors vT are a basis of Sλ. The action of Sn on Sλ is given by sivT= (si)TT vT+ (1+(si)TT) vsiT,where (si)TT= 1c(T(i+1))-c(T(i)) and si=(i,i+1). In this formula T(i)denotes the box containingi inT; c(b)=j-i is thecontent of the boxb, where (i,j)is the position of binλ; siTis the same asT except that the entriesiand i+1are switched; vsiT=0if siTis not a standard tableau. There are other important constructions of the irreducible representations Sλ. We do not have room to discuss these constructions here, see the Notes and References (10-12) below and A3 in the appendix. The main ones are:
(iii) Young’s orthonormal construction,
(iv) The Kazhdan-Lusztig construction,
(v) The Springer construction.

S. Particularly interesting representations

(S1) Let k+=n. The module SλSk×SSn is the same as Sλ except that we only look Sk×S. Then SλSk×SSn= μk,ν (SμSν)cμνλ =μ,νcμνλ (SμSν), where cμνλ is the number of column strict fillings of λ/μ of content ν such that the word of the filling is a lattice permutation. The positive integers cμνλ are the Littlewood-Richardson coefficients. See Appendix A2.
(S2) Let μ=(μ1,,μ) be a partition of n. Let Sμ=Sμ1××Sμ. The module 1SμSn is the vector space 1SμSn= (Sn/Sμ)= -span{wSμ|wSn} where the action of sn on the cosets is by left multiplication. Then 1SμSn= λKλμ Sλ, where Kλμ= # of column strict tableaux of shapeλ and weightμ. This representation also occurs in the following context: 1SμSn H*(u), where u is a unipotent element of GL(n,) with Jordan decomposition μ and u is the variety of Borel subgroups in GL(n,) containing u. This representation is related to the Springer construction mentioned in C(v) above. See Appendix A3 for further details.
(S3) If μ,νn then the tensor product Sn-module SμSν is defined by w(mn)=wmwn, for all wSn, mSμ and νSν. There are positive integers γmuνλ such that SμSν= λn γμνλSλ. Except for a few special cases the positive integers γμνλ are still unknown. See [Rem1992] for a combinatorial description of the cases for which the coefficients γμνλ are known.

Notes and references

(1) The bijection in (Ia), between irreducible representations and partitions, is due to Frobenius [Fro1900]. Frobenius is the founder of representation theory and the symmetric group was one of the first examples that he worked out.
(2) The formula in (Ib) for the dimension of Sλ as the number of standard tableaux is immediate from the work of Frobenius, but it really came into the fore from the work of Young [You1901-1952]. The “hook formula” for dim(Sλ) is due to Frame-Robinson-Thrall [FRT1954].
(3) The formula for the characters of the symmetric group which is given in (Ic) is due to Fomin and Greene [FGr1998]. For them, this formula arose by application of their theory of noncommutative symmetric functions. Roichman [Roi1997] discovered this formula independently in the more general case of the Iwahori-Hecke algebra. The formula for the Iwahori-Hecke algebra is exactly the same as the formula for the Sn case except that the 1 appearing in case 3 of the definition of f(i,T) should be changed to a q.
(4) There is a different and more classical formula for the characters than the formula given in (Ic) which is called the Murnaghan-Nakayama rule [Mur1937] [Nak1940]. We have described the Murnaghan-Nakayama rule in the appendix, Theorem A2.2. Once the formula in (Ic) is given it is not hard to show combinatorially that it is equivalent to the Murnaghan-Nakayama rule but if one does not know the formula it is nontrivial to guess it from the Murnaghan-Nakayama rule.
(5) We do not know if anyone has compared the algorithmic complexity of the formula given in (Ic) with the algorithmic complexity of the Murnaghan-Nakayama rule. One would expect that they have the same complexity: the formula above is a sum over more objects than the sum in the Murnaghan-Nakayama rule but these objects are easier to create and many of them have zero weight.
(6) One of the beautiful things about the formula for the character of Sλ which is given in (Ic) is that it is a sum over the same set that we have used to describe the dimension of Sλ.
(7) The construction of Sλ by Young symmetrizers is due to Young [You1900,You1902] from 1900. It is used so often and has so many applications that it is considered classical. A review and generalization of this construction to skew shapes appears in [GWa1989].
(8) The seminormal form construction of Sλ is also due to Young [You1931,You1934] although it was discovered some thirty years after the Young symmetrizer construction.
(9) Young’s orthonormal construction differs from the seminormal construction only by multiplication of the basis vectors by certain constants. A comprehensive treatment of all three constructions of Young is given in the book by Rutherford [Rut1948].
(10) The Kazhdan-Lusztig construction uses the Iwahori-Hecke algebra in a crucial way. It is combinatorial but relies crucially on certain polynomials which seem to be impossible to compute in practice except for very small n, see [Bre1994] for further information. This construction has important connections to geometry and other parts of representation theory. The paper [GMa1988] and the book [Hum1990] give elementary treatments of the Kazhdan-Lusztig construction.
(11) Springer’s construction is a geometric construction. In this construction the irreducible module Sλ is realized as the top cohomology group of a certain variety, see [Spr1978], [CGi1997], and Appendix A3.
(12) There are many ways of constructing new representations from old ones. Among the common techniques are restriction, induction, and tensoring. The special representations (S1), (S2), and (S3) given above are particularly nice examples of these constructions. One should note that tensoring of representations works for group algebras (and Hopf algebras) but not for general algebras.

Notes and references

This is the survey paper Combinatorial Representation Theory, written by Hélène Barcelo and Arun Ram.

Key words and phrases. Algebraic combinatorics, representations.

Barcelo was supported in part by National Science Foundation grant DMS-9510655.
Ram was supported in part by National Science Foundation grant DMS-9622985.
This paper was written while both authors were in residence at MSRI. We are grateful for the hospitality and financial support of MSRI..

page history