Combinatorial Representation Theory

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last update: 17 September 2013

Part I

2. Answers for $S_n,$ 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 $S_n\text{.}$ Let us give the answers to the main questions for the case of $S_n\text{.}$ 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=ℂS_n\text{.}$

I. What are the irreducible $S_n\text{-modules?}$

(a)	How do we index/count them?
	There is a bijection $$\text{Partitions}\hspace{0.17em}\lambda \hspace{0.17em}\text{of}\hspace{0.17em}n\stackrel{1-1}{⟷}\text{Irreducible representations}\hspace{0.17em}{S}^{\lambda }\text{.}$$
(b)	What are their dimensions?
	The dimension of the irreducible representation $S^{\lambda }$ is given by $$\begin{array}{ccc}\text{dim}\left(S^{\lambda }\right)& =& \text{\# of standard tableaux of shape}\hspace{0.17em}\lambda \\ & =& \frac{n!}{{\prod }_{x\in \lambda }{h}_x},\end{array}$$ where $h_x$ is the hook length at the box $x$ in $\lambda ,$ see Appendix A2.
(c)	What are their characters?
	Let ${\chi }^{\lambda }\left(\mu \right)$ be the character of the irreducible representation $S^{\lambda }$ evaluated at a permutation of cycle type $\mu ={\mu }_1,{\mu }_2,\dots ,{\mu }_{\ell }\text{.}$ Then the character ${\chi }^{\lambda }\left(\mu \right)$ is given by $${\chi }^{\lambda }\left(\mu \right)=\sum _T{\text{wt}}^{\mu }\left(T\right),$$ where the sum is over all standard tableaux $T$ of shape $\lambda$ and $${\text{wt}}^{\mu }\left(T\right)=\prod _{i=1}^{n}f(i,T),$$ where $$f(i,T)=\{\begin{array}{cc}-1,& \text{if}\hspace{0.17em}i\notin B\left(\mu \right)\hspace{0.17em}\text{and}\hspace{0.17em}i+1\hspace{0.17em}\text{is sw of}\hspace{0.17em}i\text{,}\\ 0,& \text{if}\hspace{0.17em}i,i+1\notin B\left(\mu \right)\text{,}\hspace{0.17em}i+1\hspace{0.17em}\text{is ne of}\hspace{0.17em}i\text{, and}\hspace{0.17em}i+2\hspace{0.17em}\text{is sw of}\hspace{0.17em}i+1\text{,}\\ 1,& \text{otherwise,}\end{array}$$ and $B\left(\mu \right)=\{{\mu }_1+{\mu }_2+\cdots +{\mu }_k\hspace{0.17em}|\hspace{0.17em}1\le k\le \ell \}\text{.}$ 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^{\lambda }\text{.}$

(i)	via Young symmetrizers. Let $T$ be a tableau. Let $$\begin{array}{ccc}R\left(T\right)& =& \text{permutations which fix the rows of}\hspace{0.17em}T\text{, as sets;}\\ C\left(T\right)& =& \text{permutations which fix the columns of}\hspace{0.17em}T\text{, as sets;}\\ \multicolumn{3}{c}{P\left(T\right)=\sum _{w\in R\left(T\right)}w,\text{and}N\left(T\right)=\sum _{w\in C\left(T\right)}\epsilon \left(w\right)w,}\end{array}$$ where $\epsilon \left(w\right)$ is the sign of the permutation $w\text{.}$ Then $$S^{\lambda }\cong ℂS_{n}P\left(T\right)N\left(T\right),$$ where the action of the symmetric group is by left multiplication.
(ii)	Young’s seminormal construction. Let $$S^{\lambda }=ℂ\text{-span-}\left\{v_T\hspace{0.17em}\right|\hspace{0.17em}T\hspace{0.17em}\text{are standard tableaux of shape}\hspace{0.17em}\lambda \}$$ so that the vectors $v_T$ are a basis of $S^{\lambda }\text{.}$ The action of $S_n$ on $S^{\lambda }$ is given by $$s_i{v}_T={\left(s_i\right)}_{TT}{v}_T+(1+{\left(s_i\right)}_{TT})v_{s_{i}T},\text{where}{\left(s_i\right)}_{TT}=\frac{1}{c\left(T(i+1)\right)-c\left(T\left(i\right)\right)}$$ and $s_i=(i,i+1)\text{.}$ In this formula $$\begin{array}{c}T\left(i\right)\hspace{0.17em}\text{denotes the box containing}\hspace{0.17em}i\hspace{0.17em}\text{in}\hspace{0.17em}T\text{;}\\ c\left(b\right)=j-i\hspace{0.17em}\text{is the}\hspace{0.17em}\text{content}\hspace{0.17em}\text{of the box}\hspace{0.17em}b\text{, where}\hspace{0.17em}(i,j)\hspace{0.17em}\text{is the position of}\hspace{0.17em}b\hspace{0.17em}\text{in}\hspace{0.17em}\lambda \text{;}\\ s_{i}T\hspace{0.17em}\text{is the same as}\hspace{0.17em}T\hspace{0.17em}\text{except that the entries}\hspace{0.17em}i\hspace{0.17em}\text{and}\hspace{0.17em}i+1\hspace{0.17em}\text{are switched;}\\ v_{s_{i}T}=0\hspace{0.17em}\text{if}\hspace{0.17em}{s}_{i}T\hspace{0.17em}\text{is not a standard tableau.}\end{array}$$ There are other important constructions of the irreducible representations $S^{\lambda }\text{.}$ 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+\ell =n\text{.}$ The module $S^{\lambda }{\downarrow }_{S_k\times S_{\ell }}^{S_n}$ is the same as $S^{\lambda }$ except that we only look $S_k\times S_{\ell }\text{.}$ Then $$S^{\lambda }{\downarrow }_{S_k\times S_{\ell }}^{S_n}=\underset{\mu ⊢k,\nu ⊢\ell }{⨁}{(S^{\mu }\otimes S^{\nu })}^{\oplus c_{\mu \nu }^{\lambda }}=\sum _{\mu ,\nu }{c}_{\mu \nu }^{\lambda }(S^{\mu }\otimes S^{\nu }),$$ where $c_{\mu \nu }^{\lambda }$ is the number of column strict fillings of $\lambda /\mu$ of content $\nu$ such that the word of the filling is a lattice permutation. The positive integers $c_{\mu \nu }^{\lambda }$ are the Littlewood-Richardson coefficients. See Appendix A2.
(S2)	Let $\mu =({\mu }_1,\dots ,{\mu }_{\ell })$ be a partition of $n\text{.}$ Let $S_{\mu }=S_{{\mu }_1}\times \cdots \times S_{{\mu }_{\ell }}\text{.}$ The module $1{\uparrow }_{S_{\mu }}^{S_n}$ is the vector space $$1{\uparrow }_{S_{\mu }}^{S_n}=ℂ(S_n/S_{\mu })=ℂ\text{-span}\left\{w{S}_{\mu }\hspace{0.17em}\right|\hspace{0.17em}w\in S_n\}$$ where the action of $s_n$ on the cosets is by left multiplication. Then $$1{\uparrow }_{S_{\mu }}^{S_n}=\sum _{\lambda }{K}_{\lambda \mu }{S}^{\lambda },$$ where $$K_{\lambda \mu }=\text{\# of column strict tableaux of shape}\hspace{0.17em}\lambda \hspace{0.17em}\text{and weight}\hspace{0.17em}\mu \text{.}$$ This representation also occurs in the following context: $$1{\uparrow }_{S_{\mu }}^{S_n}\cong H^{*}\left({ℬ}_u\right),$$ where $u$ is a unipotent element of $GL(n,ℂ)$ with Jordan decomposition $\mu$ and ${ℬ}_u$ is the variety of Borel subgroups in $GL(n,ℂ)$ containing $u\text{.}$ This representation is related to the Springer construction mentioned in C(v) above. See Appendix A3 for further details.
(S3)	If $\mu ,\nu ⊢n$ then the tensor product $S_n\text{-module}$ $S^{\mu }\otimes S^{\nu }$ is defined by $w(m\otimes n)=wm\otimes wn,$ for all $w\in S_n,$ $m\in S^{\mu }$ and $\nu \in S^{\nu }\text{.}$ There are positive integers ${\gamma }_{mu\nu \lambda }$ such that $$S^{\mu }\otimes S^{\nu }=\sum _{\lambda ⊢n}{\gamma }_{\mu \nu \lambda }{S}^{\lambda }\text{.}$$ Except for a few special cases the positive integers ${\gamma }_{\mu \nu \lambda }$ are still unknown. See [Rem1992] for a combinatorial description of the cases for which the coefficients ${\gamma }_{\mu \nu \lambda }$ 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^{\lambda }$ 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 $\text{dim}\left(S^{\lambda }\right)$ 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 $S_n$ case except that the 1 appearing in case 3 of the definition of $f(i,T)$ should be changed to a $q\text{.}$
(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^{\lambda }$ 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^{\lambda }\text{.}$
(7)	The construction of $S^{\lambda }$ 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^{\lambda }$ 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^{\lambda }$ 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