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 II

5. Generalizing the $S_n$ results

Having the above results for the symmetric group in hand we would like to try to generalize as many of the $S_n$ results to other similar groups and algebras as we can. Work along this line began almost immediately after the discovery of the $S_n$ results and it continues today. In the current state of results this has been largely

(1)	successful for the complex reflection groups $G(r,p,n)$ and their “Hecke algebras,”
(2)	successful for tensor power centralizer algebras and their $q\text{-analogues,}$ and
(3)	unsuccessful for general Weyl groups and finite Coxeter groups.

Let us give a brief description of what the objects are in (1), (2), and (3). For more precise definitions and discussion of everything below see Appendix B.

Definitions

(1) Complex reflection groups $G(r,p,n)$ and their Hecke algebras

The complex reflection groups $G(r,p,n)$

A finite Coxeter group is a finite group which is generated by reflections in ${ℝ}^n\text{.}$ In other words, take a bunch of linear transformations of ${ℝ}^n$ which are reflections (in the sense of reflections and rotations in the orthogonal group) and see what group they generate. If the group is finite then it is a finite Coxeter group. Actually, this definition of finite Coxeter group is not the usual one (for that see Appendix B1), but since we have the following theorem we are not too far astray.

Theorem 5.1. A group is a finite group generated by reflections if and only if it is a finite Coxeter group.

The finite Coxeter groups have been classified completely and there is one group of each of the following “types” $$A_n,B_n,D_n,E_6,E_7,E_8,F_4,H_3,H_4,\text{or}{I}_2\left(m\right)\text{.}$$ The finite crystallographic reflection groups are called Weyl groups because of their connection with Lie theory. These are the finite Coxeter groups of types $$A_n,B_n,D_n,E_6,E_7,E_8,F_4,\text{and}{G}_2=I_2\left(6\right)\text{.}$$

A complex reflection group is a group generated by complex reflections, i.e. invertible linear transformations of ${ℂ}^n$ which have finite order and which have exactly one eigenvalue that is not $1\text{.}$ Every finite Coxeter group is also a finite complex reflection group. The finite complex reflection groups have been classified by Shephard and Todd [STo1954] and each such group is one of the groups

(a)	$G(r,p,n),$ where $r,p,n$ are positive integers such that $p$ divides $r,$ or
(b)	one of 34 “exceptional” finite complex reflection groups.

The groups $F(r,p,n)$ are very similar to the symmetric group $S_n$ in many ways and this is probably why generalizing the $S_n$ theory has been so successful for these groups. The symmetric groups and the finite Coxeter groups of types $B_n,$ and $D_n$ are all special cases of the groups $G(r,p,n)\text{.}$

The “Hecke algebras” of reflection groups

The Iwahori-Hecke algebra of a finite Coxeter group $W$ is an algebra which is a $q\text{-analogue,}$ or $q\text{-deformation,}$ of the group algebra $W\text{.}$ See Appendix B3 for a proper definition of this algebra. It has a basis $T_w,$ $w\in W,$ (so it is the same dimension as the group algebra of $W\text{)}$ but the multiplication in this algebra depends on a particular number $q\in ℂ,$ which can be chosen arbitrarily. These algebras are true Hecke algebras only when $W$ is a finite Weyl group.

The “Hecke algebras” of the groups $G(r,p,n)$ are $q\text{-analogues}$ of the group algebras of the groups $G(r,p,n)\text{.}$ It is only recently (1990-1994) that they have been defined. It is important to note that these algebras are not true Hecke algebras. In group theory, a Hecke algebra is a very specific kind of double coset algebra and the “Hecke algebras” of the groups $G(r,p,n)$ do not fit this mold. See Appendix B3-4 for the proper definition of a Hecke algebra and some discussion of how the “Hecke algebras” for the groups $G(r,p,n)$ are defined.

(2) Tensor power centralizer algebras

A tensor power centralizer algebra is an algebra which is isomorphic to ${\text{End}}_G\left(V^{\otimes k}\right)$ for some group (or Hopf algebra) $G$ and some representation $V$ of $G\text{.}$ In this definition $${\text{End}}_G\left(V^{\otimes k}\right)=\{T\in \text{End}\left(V^{\otimes k}\right)\hspace{0.17em}|\hspace{0.17em}Tgv=gTv,\hspace{0.17em}\text{for all}\hspace{0.17em}g\in G\hspace{0.17em}\text{and all}\hspace{0.17em}v\in V^{\otimes k}\}\text{.}$$ There are some examples of tensor power centralizer algebras that have been particularly important:

(a)	The group algebras, $ℂS_k,$ of the symmetric groups $S_k,$
(b)	The Iwahori-Hecke algebras, $H_k\left(q\right),$ of type $A_{k-1},$
(c)	The Temperley-Lieb algebras, $T{L}_k\left(x\right),$
(d)	The Brauer algebras, $B_k\left(x\right),$
(e)	The Birman-Murakami-Wenzl algebras, $BM{W}_k(r,q)\text{.}$
(f)	The spider algebras,
(f)	The rook monoid algebras,
(g)	The Solomon-Iwahori algebras,
(h)	The wall algebras,
(i)	The $q\text{-wall}$ algebras,
(j)	The partition algebras.

We certainly do not have space to discuss all of these objects in this paper, and thus we will limit ourselves to the cases (a)-(e) in our discussion below and in the Appendix, §B5-8. References for the remaining cases are as follows.

The spider algebras. These algebras were written down combinatorially and studied by G. Kuperberg [Kup1996-2,Kup1994-3].

The rook monoid algebras. L. Solomon (unpublished work) recognized that this very natural monoid (the combinatorics of which has also been studied in [GRe1986]) appears as a tensor power centralizer.

The Solomon-Iwahori algebras. This algebra was introduced in [Sol1990]. The fact that it is a tensor power centralizer algebra is an unpublished result of L. Solomon, see [Sol1995].

The wall algebras. These algebras were introduced in a nice combinatorial form in [BCH1994] and in other forms in [Koi1989] and Procesi [Pro1976] and other older invariant theory works [Wey1946]. All of these works were related to tensor power centralizers and/or fundamental theorems of invariant theory.

The $q\text{-wall}$ algebras. These algebras were introduced by Kosuda and Murakami [KMu1993,KMu1992] and studied subsequently in [Led1994] and [Hal1996,Hal1995].

The partition algebras. These algebras were introduced by V. Jones in [Jon1993] and have been studied subsequently by P. Martin [Mar1996].

Notes and references for answers to the main questions

Some partial results giving answers to the main questions for the complex reflection groups $G(r,p,n),$ their “Hecke algebras”, the Temperley-Lieb algebras, the Brauer algebras, and the Birman-Murakami-Wenzl algebras can be found in Appendix B. The appropriate references are as follows.

(1) Complex reflection groups $G(r,p,n)$ and their Hecke algebras

The complex reflection groups $G(r,p,n)$

I. What are the irreducible modules?

The indexing, dimension formulas and character formulas for the representations of the groups $G(r,p,n)$ are originally due to

Young [You1900]	for finite Coxeter groups of types $B_n$ and $D_n,$ and
Specht [Spe1932]	for the group $G(r,1,n)\text{.}$

We do not know who first did the general $G(r,p,n)$ case but it is easy to generalize Young and Specht’s results to this case. See [Ari1995] and [HRa1998] for recent accounts.

Essentially what one does to determine the indexing, dimensions and the characters of the irreducible modules is to use Clifford theory to reduce the $G(r,1,n)$ case to the case of the symmetric group $S_n\text{.}$ Then one can use Clifford theory again to reduce the $G(r,p,n)$ case to the $G(r,1,n)$ case. The original reference for Clifford theory is [Cli1937] and the book by Curtis and Reiner [CRe1987] has a modern treatment. The articles [Ste1989-2] and [HRa1998] explain how the reduction from $G(r,p,n)$ to $G(r,1,n)$ is done. The dimension and character theory for the case $G(r,1,n)$ has an excellent modern treatment in [Mac1995], Appendix B to Chapter I.

C. How do we construct the irreducible modules?

The construction of the irreducible representations by Young symmetrizers was extended to the finite Coxeter groups of types $B_n$ and $D_n$ by Young himself in his paper [You1929]. The authors don’t know when the general case was first treated in the literature, but it is not difficult to extend Young’s results to the general case $G(r,p,n)\text{.}$ The $G(r,p,n)$ case does appear periodically in the literature, see for example [All1997].

Young’s seminormal construction was generalized to the “Hecke algebras” of $G(r,p,n)$ in the work of Ariki and Koike [AKo1994] and Ariki [Ari1995]. One can easily set $q=1$ in the constructions of Ariki and Koike and obtain the appropriate analogues for the groups $G(r,p,n)\text{.}$ We do not know if the analogue of Young’s seminormal construction for the groups $G(r,p,n)$ appeared in the literature previous to the work of Ariki and Koike on the “Hecke algebra” case.

S. Special/Interesting representations.

The authors do not know if the analogues of the $S_n$ results, (S1-3) of Section 2, have explicitly appeared in the literature. It is easy to use symmetric functions and the character formulas of Specht, see [Mac1995] Chpt. I, App. B, to derive formulas for the $G(r,1,n)$ case in terms of the symmetric group results. Then one proceeds as described above to compute the necessary formulas for $G(r,p,n)$ in terms of the $G(r,1,n)$ results. See [Ste1989-2] for how this is done.

The “Hecke algebras” of reflection groups

The definition.

The “Hecke algebras” corresponding to the groups $G(r,p,n)$ were defined by

Ariki and Koike [AKo1994],	for the case $G(r,1,n),$ and
Broué and Malle [BMa1993] and Ariki [Ari1995],	for the general case $G(r,p,n)\text{.}$

See Appendix B4 for a definition of these algebras and some partial answers to the main questions. Let us give references to the literature for the answers to the main questions for these algebras.

I. What are the irreducibles?

The results of Ariki-Koike [AKo1994] and Ariki [Ari1995] say that the “Hecke algebras” of $G(r,p,n)$ are $q\text{-deformations}$ of the group algebras of the groups $G(r,p,n)\text{.}$ Thus, it follows from the Tits deformation theorem (see [Car1985] Chapt 10, 11.2 and [CRe1987] §68.17) that the indexings and dimension formulas for the irreducible representations of these algebras must be the same as the indexings and dimension formulas for the groups $G(r,p,n)\text{.}$ Finding analogues of the character formulas requires a bit more work and a Murnaghan-Nakayama type rule for the “Hecke algebras” of $G(r,p,n)$ was given by Halverson and Ram [HRa1998]. As far as we know, the formula for the irreducible characters of $S_n$ as a weighted sum of standard tableaux which we gave in the symmetric group section has not yet been generalized to the case of $G(r,p,n)$ and its “Hecke algebras”.

C. How do we construct the irreducible modules?

Analogues of Young’s seminormal representations have been given by

Hoefsmit [Hoe1974] and Wenzl [Wen1988], independently, for Iwahori-Hecke algebras of type $A_{n-1},$ Hoefsmit [Hoe1974], for Iwahori-Hecke algebras of types $B_n$ and $D_n,$ Ariki and Koike [AKo1994] for the “Hecke algebras” of $G(r,1,n),$ and Ariki [Ari1995] for the general “Hecke algebras” of $G(r,p,n)\text{.}$

There seems to be more than one appropriate choice for the analogue of Young symmetrizers for Hecke algebras. The definitions in the literature are due to

Gyoja [Gyo1986], for the Iwahori-Hecke algebras of type $A_{n-1},$ Dipper and James [DJa1986] and Murphy [Mur1992,Mur1995] for the Iwahori-Hecke algebras of type $A_{n-1},$ King and Wybourne [KWy1992] and Duchamp, et al [DKL1995] for the Iwahori-Hecke algebras of type $A_{n-1},$ Dipper, James, and Murphy [DJa1992], [DJM1995] for the Iwahori-Hecke algebras of type $B_n,$ Pallikaros [Pal1994], for the Iwahori-Hecke algebras of type $D_n\text{.}$ Mathas [Mat1999] and Murphy [Mur1996], for the “Hecke algebras” of $G(r,p,n)\text{.}$

The paper [GLe1996] also contains important ideas in this direction.

S. Special/Interesting representations.

It follows from the Tits deformation theorem (or rather, an extension of it) that the results for the “Hecke algebras” of $G(r,p,n)$ must be the same as for the case of the groups $G(r,p,n)\text{.}$

(2) Tensor power centralizer algebras

The definitions.

The references for the combinatorial definitions of the various centralizer algebras are as follows.

Temperley-Lieb algebras. These algebras are due, independently, to many different people. Some of the discoverers were Rumer-Teller-Weyl [RTW1932], Penrose [Pen1969,Pen1971], Temperley-Lieb [TLi1971], Kaufmann [Kau1987] and Jones [Jon1983]. The work of V. Jones was crucial in making them so important in combinatorial representation theory today.

The Iwahori-Hecke algebras of type $A_{n-1}$. Iwahori [Iwa1964] introduced these algebras in 1964 in connection with $GL(n,{𝔽}_q)\text{.}$ Jimbo [Jim1986] realized that they arise as tensor power centralizer algebras for quantum groups.

Brauer algebras. These algebras were defined by Brauer in 1937 [Bra1937]. Brauer also proved that they are tensor power centralizers.

Birman-Murakami-Wenzl algebras. These algebras are due to Birman and Wenzl [BWe1989] and Murakami [Mur1987]. It was realized early [Res1987] [Wen1990] that these arise as tensor power centralizers but there was no proof in the literature for some time. See the references in [CPr1994] §10.2.

I. What are the irreducibles?

Indexing of the representations of tensor power centralizer algebras follows from double centralizer theory (see Weyl [Wey1946]) and a good understanding of the indexings and tensor product rules for the group or algebra which it is centralizing (i.e. $GL(n,ℂ),$ $O(n,ℂ),$ $U_q𝔰𝔩\left(n\right),$ etc.). The references for resulting indexings and dimension formulas for the irreducible representations are as follows:

Temperley-Lieb algebras. These results are classical and can be found in the book by Goodman, de la Harpe, and Jones [GHJ1989].

Brauer algebras. These results were known to Brauer [Bra1937] and Weyl [Wey1946]. An important combinatorial point of view was given by Berele [Ber1986,Ber1986-2] and further developed by Sundaram [Sun1990,Sun1990-2,Sun1990-3].

Iwahori-Hecke algebras of type $A_{n-1}\text{.}$ These results follow from the Tits deformation theorem and the corresponding results for the symmetric group.

Birman-Murakami-Wenzl algebras. These results follow from the Tits deformation theorem and the corresponding results for the Brauer algebra.

The indexings and dimension formulas for the Temperley-Lieb and Brauer algebras also follow easily by using the techniques of the Jones basic construction, see [Wen1988-2] and [HRa1995].

The references for the irreducible characters of the various tensor power centralizer algebras are as follows:

Temperley-Lieb algebras. Character formulas can be derived easily by using Jones Basic Construction techniques [HRa1995].

Iwahori-Hecke algebras of type $A_{n-1}\text{.}$ The analogue of the formula for the irreducible characters of $S_n$ as a weighted sum of standard tableaux was found by Roichman [Roi1997]. Murnaghan-Nakayama type formulas were found by several authors [KWy1992], [vdJ1991], [VKe1989], [SUe1991], and [Ram1991-2].

Brauer algebras and Birman-Murakami-Wenzl algebras. Murnaghan-Nakayama type formulas were derived in [Ram1995] and [HRa1995], respectively.

Brauer algebra and Birman-Murakami-Wenzl algebra analogues of the formula for the irreducible characters of the symmetric groups as a weighted sum of standard tableaux have not appeared in the literature.

C. How do we construct the irreducibles?

Temperley-Lieb algebras. An application of the Jones Basic Construction (see [Wen1988-2] and [HRa1995]) gives a construction of the irreducible representations of the Temperley-Lieb algebras. This construction is classical and has been rediscovered by many people. In this case the construction is an analogue of the Young symmetrizer construction. The analogue of the seminormal construction appears in [GHJ1989].

Iwahori-Hecke algebras of type $A_{n-1}\text{.}$ The analogue of Young’s seminormal construction for this case is due, independently, to Hoefsmit [Hoe1974] and Wenzl [Wen1988]. Analogues of Young symmetrizers (different analogues) have been given by Gyoja [Gyo1986] and Dipper, James, and Murphy [DJa1986], [Mur1992,Mur1995], King and Wybourne [KWy1992] and Duchamp, et al. [DKL1995].

Brauer algebras. Analogues of Young’s seminormal representations have been given, independently, by Nazarov [Naz1996] and Leduc and Ram [LRa1977]. An analogue of the Young symmetrizer construction can be obtained by applying the Jones Basic Construction to the classical Young symmetrizer construction and this is the one that has been used by many authors [BBL1990], [HWa1989], [Ker1990], [GLe1996]. The actual element of the algebra which is the analogue of the Young symmetrizer involves a central idempotent for which there is no known explicit formula and this is the reason that most authors work with a quotient formulation of the appropriate module.

Birman-Murakami-Wenzl algebras. Analogues of Young’s seminormal representations have been given by Murakami [Mur1990] and Leduc and Ram [LRa1977]. The methods in the two works are different, the work of Murakami uses the physical theory of Boltzmann weights and the work of Leduc and Ram uses the theory of ribbon Hopf algebras and quantum groups. Exactly in the same way as for the Brauer algebra, an analogue of the Young symmetrizer construction can be obtained by applying the Jones Basic Construction to the Young symmetrizer constructions for the Iwahori-Hecke algebra of type $A_{n-1}\text{.}$ As in the Brauer algebra case one should work with a quotient formulation of the module to avoid using a central idempotent for which there is no known explicit formula.

(3) Reflection groups of exceptional type.

Generalizing the $S_n$ theory to finite Coxeter groups of exceptional type, finite complex reflection groups of exceptional type and the corresponding Iwahori-Hecke algebras, has been largely unsuccessful. This is not to say that there haven’t been some very nice partial results only that at the moment nobody has any understanding of how to make a good combinatorial theory to encompass all the classical and exceptional types at once. Two amazing partial results along these lines are $$\text{the Springer construction}\text{and}\text{the Kazhdan-Lusztig construction.}$$ The Springer construction is a construction of the irreducible representations of the crystallographic reflection groups on cohomology of unipotent varieties [Spr1978]. It is a geometric construction and not a combinatorial construction. See Appendix A3 for more information in the symmetric group case. It is possible that this construction may be combinatorialized in the future, but to date no one has done this.

The Kazhdan-Lusztig construction [KLu1979] is a construction of certain representations called cell representations and it works for all finite Coxeter groups. The cell representations are almost irreducible but unfortunately not irreducible in general, and nobody understands how to break them up into irreducibles, except in a case by case fashion. The other problem with these representations is that they depend crucially on certain polynomials, the Kazhdan-Lusztig polynomials, which seem to be impossible to compute or understand well except in very small cases, see [Bre1994] for more information. See [Car1985] for a summary and tables of the known facts about representation of finite Coxeter groups of exceptional type.

Remarks

(1)	A Hecke algebra is a specific “double coset algebra” which depends on a group $G$ and a subgroup $B\text{.}$ Iwahori [Iwa1964] studied these algebras in the case that $G$ is a finite Chevalley group and $B$ is a Borel subgroup of $G$ and defined what are now called Iwahori-Hecke algebras. These are $q\text{-analogues}$ of the group algebras of finite Weyl groups. The work of Iwahori yields a presentation for these algebras which can easily be extended to define Iwahori-Hecke algebras for all Coxeter groups but, except for the original Weyl group case, these have never been realized as true Hecke algebras, i.e. double coset algebras corresponding to an appropriate $G$ and $B\text{.}$ The “Hecke algebras” corresponding to the groups $G(r,p,n)$ are $q\text{-analogues}$ of the group algebras of $G(r,p,n)\text{.}$ Although these algebras are not true Hecke algebras either, Broué and Malle [BMa1993] have shown that many of these algebras arise in connection with non-defining characteristic representations of finite Chevalley groups and Deligne-Lusztig varieties.
(2)	There is much current research on generalizing symmetric group results to affine Coxeter groups and affine Hecke algebras. The case of affine Coxeter groups was done by Kato [Kat1983] using Clifford theory ideas. The case of affine Hecke algebras has been intensely studied by Lusztig [Lus1987, Lus1987-2, Lus1989, Lus1988, Lus1989-2, Lus1995, Lus1995-2], Kazhdan-Lusztig [KLu0862716], and Ginzburg [Gin1987], [CGi1997], but most of this work is very geometric and relies on intersection cohomology/K-theory methods. Hopefully some of their work will be made combinatorial in the near future.
(3)	Wouldn’t it be great if we had a nice combinatorial representation theory for finite simple groups!!

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