Representation theory of the symmetric group

Template:Short description Template:More footnotes needed In mathematics, the representation theory of the symmetric group is a particular case of the representation theory of finite groups, for which a concrete and detailed theory can be obtained. This has a large area of potential applications, from symmetric function theory to quantum chemistry studies of atoms, molecules and solids.<ref>Philip R. Bunker and Per Jensen (1998) Molecular Symmetry and Spectroscopy, 2nd ed. NRC Research Press, Ottawa [1] pp.198-202.Template:ISBN</ref><ref>R.Pauncz (1995) The Symmetric Group in Quantum Chemistry, CRC Press, Boca Raton, Florida</ref>

The symmetric group S_n has order n!. Its conjugacy classes are labeled by partitions of n. Therefore according to the representation theory of a finite group, the number of inequivalent irreducible representations, over the complex numbers, is equal to the number of partitions of n. Unlike the general situation for finite groups, there is in fact a natural way to parametrize irreducible representations by the same set that parametrizes conjugacy classes, namely by partitions of n or equivalently Young diagrams of size n.

Each such irreducible representation can in fact be realized over the integers (every permutation acting by a matrix with integer coefficients); it can be explicitly constructed by computing the Young symmetrizers acting on a space generated by the Young tableaux of shape given by the Young diagram. The dimension <math>d_\lambda</math> of the representation that corresponds to the Young diagram <math>\lambda</math> is given by the hook length formula.

To each irreducible representation ρ we can associate an irreducible character, χ^ρ. To compute χ^ρ(π) where π is a permutation, one can use the combinatorial Murnaghan–Nakayama rule .<ref>Richard Stanley, Enumerative Combinatorics, Vol. 2</ref> Note that χ^ρ is constant on conjugacy classes, that is, χ^ρ(π) = χ^ρ(σ⁻¹πσ) for all permutations σ.

Over other fields the situation can become much more complicated. If the field K has characteristic equal to zero or greater than n then by Maschke's theorem the group algebra KS_n is semisimple. In these cases the irreducible representations defined over the integers give the complete set of irreducible representations (after reduction modulo the characteristic if necessary).

However, the irreducible representations of the symmetric group are not known in arbitrary characteristic. In this context it is more usual to use the language of modules rather than representations. The representation obtained from an irreducible representation defined over the integers by reducing modulo the characteristic will not in general be irreducible. The modules so constructed are called Specht modules, and every irreducible does arise inside some such module. There are now fewer irreducibles, and although they can be classified they are very poorly understood. For example, even their dimensions are not known in general.

The determination of the irreducible modules for the symmetric group over an arbitrary field is widely regarded as one of the most important open problems in representation theory.

Low-dimensional representations

Symmetric groups

The lowest-dimensional representations of the symmetric groups can be described explicitly,<ref>Template:Citation</ref><ref>Template:Citation</ref> and over arbitrary fields.Template:SfnTemplate:Page needed The smallest two degrees in characteristic zero are described here:

Every symmetric group has a one-dimensional representation called the trivial representation, where every element acts as the one by one identity matrix. For Template:Nowrap, there is another irreducible representation of degree 1, called the sign representation or alternating character, which takes a permutation to the one by one matrix with entry ±1 based on the sign of the permutation. These are the only one-dimensional representations of the symmetric groups, as one-dimensional representations are abelian, and the abelianization of the symmetric group is C₂, the cyclic group of order 2.

For all n, there is an n-dimensional representation of the symmetric group of order n!, called the Template:Visible anchor, which consists of permuting n coordinates. This has the trivial subrepresentation consisting of vectors whose coordinates are all equal. The orthogonal complement consists of those vectors whose coordinates sum to zero, and when Template:Nowrap, the representation on this subspace is an Template:Nowrap-dimensional irreducible representation, called the standard representation. Another Template:Nowrap-dimensional irreducible representation is found by tensoring with the sign representation. An exterior power <math>\Lambda^k V</math> of the standard representation <math>V</math> is irreducible provided <math>0\leq k\leq n-1</math> Template:Harv.

For Template:Nowrap, these are the lowest-dimensional irreducible representations of S_n – all other irreducible representations have dimension at least n. However for Template:Nowrap, the surjection from S₄ to S₃ allows S₄ to inherit a two-dimensional irreducible representation. For Template:Nowrap, the exceptional transitive embedding of S₅ into S₆ produces another pair of five-dimensional irreducible representations.

Irreducible representation of <math>S_n</math>	Dimension	Young diagram of size <math>n</math>
Trivial representation	<math>1</math>	<math>(n)</math>
Sign representation	<math>1</math>	<math>(1^n)=(1,1,\dots,1)</math>
Standard representation <math>V</math>	<math>n-1</math>	<math>(n-1, 1)</math>
Exterior power <math>\Lambda^k V</math>	<math>\binom{n-1}{k}</math>	<math>(n-k, 1^k)</math>

Alternating groups

File:Compound of five tetrahedra.png

The compound of five tetrahedra, on which A₅ acts, giving a 3-dimensional representation.

The representation theory of the alternating groups is similar, though the sign representation disappears. For Template:Nowrap, the lowest-dimensional irreducible representations are the trivial representation in dimension one, and the Template:Nowrap-dimensional representation from the other summand of the permutation representation, with all other irreducible representations having higher dimension, but there are exceptions for smaller n.

The alternating groups for Template:Nowrap have only one one-dimensional irreducible representation, the trivial representation. For Template:Nowrap there are two additional one-dimensional irreducible representations, corresponding to maps to the cyclic group of order 3: Template:Nowrap and Template:Nowrap.

• For Template:Nowrap, there is just one irreducible representation of degree Template:Nowrap, and this is the smallest degree of a non-trivial irreducible representation.
• For Template:Nowrap the obvious analogue of the Template:Nowrap-dimensional representation is reducible – the permutation representation coincides with the regular representation, and thus breaks up into the three one-dimensional representations, as Template:Nowrap is abelian; see the discrete Fourier transform for representation theory of cyclic groups.
• For Template:Nowrap, there is just one Template:Nowrap irreducible representation, but there are the exceptional irreducible representations of dimension 1.
• For Template:Nowrap, there are two dual irreducible representations of dimension 3, corresponding to its action as icosahedral symmetry.
• For Template:Nowrap, there is an extra irreducible representation of dimension 5 corresponding to the exceptional transitive embedding of A₅ in A₆.

Tensor products of representations

Kronecker coefficients

The tensor product of two representations of <math>S_n</math> corresponding to the Young diagrams <math>\lambda,\mu</math> is a combination of irreducible representations of <math>S_n</math>,

<math>

V_\lambda\otimes V_\mu \cong \sum_\nu C_{\lambda,\mu,\nu} V_\nu </math> The coefficients <math>C_{\lambda\mu\nu}\in\mathbb{N}</math> are called the Kronecker coefficients of the symmetric group. They can be computed from the characters of the representations Template:Harv:

<math>

C_{\lambda,\mu,\nu} = \sum_\rho \frac{1}{z_\rho} \chi_\lambda(C_\rho)\chi_\mu(C_\rho)\chi_\nu(C_\rho) </math> The sum is over partitions <math>\rho</math> of <math>n</math>, with <math>C_\rho</math> the corresponding conjugacy classes. The values of the characters <math>\chi_\lambda(C_\rho)</math> can be computed using the Frobenius formula. The coefficients <math>z_\rho</math> are

<math>

z_\rho = \prod_{j=0}^n j^{i_j}i_j! = \frac{n!}{|C_\rho|} </math> where <math>i_j</math> is the number of times <math>j</math> appears in <math>\rho</math>, so that <math>\sum i_jj = n</math>.

A few examples, written in terms of Young diagrams Template:Harv:

<math>

(n - 1, 1) \otimes (n - 1, 1) \cong (n) + (n - 1, 1) + (n - 2, 2) + (n - 2, 1,1) </math>

<math>

(n - 1, 1) \otimes (n - 2, 2) \underset{n>4}{\cong} (n - 1, 1) + (n - 2, 2) + (n - 2, 1, 1) + (n - 3, 3) + (n - 3, 2, 1) </math>

<math>

(n - 1, 1) \otimes (n - 2, 1,1) \cong (n - 1, 1) + (n - 2, 2) + (n - 2, 1,1) + (n - 3, 2, 1) + (n - 3, 1,1,1) </math>

<math>

\begin{align} (n - 2, 2) \otimes (n - 2, 2) \cong & (n) + (n - 1, 1) + 2(n - 2, 2) + (n - 2, 1,1) + (n - 3, 3) \\ & + 2(n - 3, 2, 1) + (n - 3, 1,1,1) + (n - 4, 4) + (n - 4, 3, 1) + (n - 4, 2, 2) \end{align} </math> There is a simple rule for computing <math>(n-1,1)\otimes \lambda</math> for any Young diagram <math>\lambda</math> Template:Harv: the result is the sum of all Young diagrams that are obtained from <math>\lambda</math> by removing one box and then adding one box, where the coefficients are one except for <math>\lambda</math> itself, whose coefficient is <math>\#\{\lambda_i\}-1</math>, i.e., the number of different row lengths minus one.

A constraint on the irreducible constituents of <math>V_\lambda\otimes V_\mu</math> is Template:Harv

<math>

C_{\lambda,\mu,\nu}>0 \implies |d_\lambda-d_\mu| \leq d_\nu \leq d_\lambda+d_\mu </math> where the depth <math>d_\lambda=n-\lambda_1</math> of a Young diagram is the number of boxes that do not belong to the first row.

Reduced Kronecker coefficients

For <math>\lambda</math> a Young diagram and <math>n\geq \lambda_1</math>, <math>\lambda[n]=(n-|\lambda|,\lambda)</math> is a Young diagram of size <math>n</math>. Then <math>C_{\lambda[n],\mu[n],\nu[n]}</math> is a bounded, non-decreasing function of <math>n</math>, and

<math>

\bar{C}_{\lambda,\mu,\nu} = \lim_{n\to\infty} C_{\lambda[n],\mu[n],\nu[n]} </math> is called a reduced Kronecker coefficient<ref name="bor09"/> or stable Kronecker coefficient.<ref name="as18"/> There are known bounds on the value of <math>n</math> where <math>C_{\lambda[n],\mu[n],\nu[n]}</math> reaches its limit.<ref name="bor09"/> The reduced Kronecker coefficients are structure constants of Deligne categories of representations of <math>S_n</math> with <math>n\in \mathbb{C}-\mathbb{N}</math>.<ref name="ent14"/>

In contrast to Kronecker coefficients, reduced Kronecker coefficients are defined for any triple of Young diagrams, not necessarily of the same size. If <math>|\nu|=|\lambda|+|\mu|</math>, then <math>\bar{C}_{\lambda,\mu,\nu}</math> coincides with the Littlewood-Richardson coefficient <math>c_{\lambda,\mu}^\nu</math>.<ref name="Dvir91"/> Reduced Kronecker coefficients can be written as linear combinations of Littlewood-Richardson coefficients via a change of bases in the space of symmetric functions, giving rise to expressions that are manifestly integral although not manifestly positive.<ref name="as18"/> Reduced Kronecker coefficients can also be written in terms of Kronecker and Littlewood-Richardson coefficients <math>c^\lambda_{\alpha\beta\gamma}</math> via Littlewood's formula<ref name="lit58"/><ref name="oz17"/>

<math>

\bar{C}_{\lambda,\mu,\nu} = \sum_{\lambda',\mu',\nu',\alpha,\beta,\gamma} C_{\lambda',\mu',\nu'} c^{\lambda}_{\lambda'\beta\gamma} c^{\mu}_{\mu'\alpha\gamma} c^\nu_{\nu'\alpha\beta} </math> Conversely, it is possible to recover the Kronecker coefficients as linear combinations of reduced Kronecker coefficients.<ref name="bor09"/>

Reduced Kronecker coefficients are implemented in the computer algebra system SageMath.<ref name="oz15"/><ref name="sage"/>

Eigenvalues of complex representations

Given an element <math>w\in S_n</math> of cycle-type <math>\mu=(\mu_1,\mu_2,\dots,\mu_k)</math> and order <math>m=\text{lcm}(\mu_i)</math>, the eigenvalues of <math>w</math> in a complex representation of <math>S_n</math> are of the type <math>\omega^{e_j}</math> with <math>\omega=e^{\frac{2\pi i}{m}}</math>, where the integers <math>e_j\in \frac{\mathbb{Z}}{m\mathbb{Z}}</math> are called the cyclic exponents of <math>w</math> with respect to the representation.<ref name="ste89"/>

There is a combinatorial description of the cyclic exponents of the symmetric group (and wreath products thereof). Defining <math>\left(b_\mu(1),\dots,b_\mu(n)\right) = \left(\frac{m}{\mu_1},2\frac{m}{\mu_1},\dots, m, \frac{m}{\mu_2},2\frac{m}{\mu_2},\dots, m,\dots\right)</math>, let the <math>\mu</math>-index of a standard Young tableau be the sum of the values of <math>b_\mu</math> over the tableau's descents, <math>\text{ind}_\mu(T) = \sum_{k\in \{\text{descents}(T)\}} b_\mu(k)\bmod m</math>. Then the cyclic exponents of the representation of <math>S_n</math> described by the Young diagram <math>\lambda</math> are the <math>\mu</math>-indices of the corresponding Young tableaux.<ref name="ste89"/>

In particular, if <math> w </math> is of order <math>n</math>, then <math>b_\mu(k)=k</math>, and <math>\text{ind}_\mu(T)</math> coincides with the major index of <math>T</math> (the sum of the descents). The cyclic exponents of an irreducible representation of <math>S_n</math> then describe how it decomposes into representations of the cyclic group <math> \frac{\mathbb{Z}}{n\mathbb{Z}}</math>, with <math>\omega^{e_j}</math> being interpreted as the image of <math>w</math> in the (one-dimensional) representation characterized by <math>e_j</math>.

See also

• Alternating polynomials
• Symmetric polynomials
• Schur functor
• Robinson–Schensted correspondence
• Schur–Weyl duality
• Jucys–Murphy element
• Garnir relations

Cited Publications

• Template:Cite book
• Template:Cite book
• Template:Citation
• Template:Citation