Characters of the Symmetric Group

This program computes character table of the symmetric group, and automatically decomposes tensor products of representations into their irreducible summands, i.e. it computes Kronecker coefficients. It can also decompose permutation modules (or tensor products of permutation modules) into irreducible components, and compute symmetric, exterior, and tensor powers of representations.

In the character table below, the rows and columns are labelled by partitions, written in compact notation where \lambda = [2^3, 1^2] means the partition \lambda = (2, 2, 2, 1, 1). The rows correspond to characters (either irreducible characters for the Specht module S^\lambda, or the character of the permutation module M^\lambda), and the columns correspond to cycle types. The number of elements having a given cycle type is written at the top of each column. After selecting one or more rows, a second table will appear, decomposing the given character.

Show characters for:

of the symmetric group on n = letters

How does it work?

The program is written in TypeScript, the source code is characters.ts. The key data structure used throughout is a linear combination of partitions, which is represented as a map from partitions to numbers. (The code for this is awkward, since Javascript has no built-in data structure capable of storing and retrieving partitions, so I convert partitions to and from strings a lot). There are various helper functions for computing combinatorial information about partitions: for example computing the size of a conjugacy class labelled by a partition, which is used when computing the inner product on class functions. The interesting algorithms are explained below.

Generating permutation characters

First, the character table for the permutation modules is calculated. The column corresponding to the cycle type \mu = (\mu_1, \ldots, \mu_r) in this table is the expansion of the power sum symmetric function p_\mu into the basis of monomial symmetric functions. Since p_\mu = m_{(\mu_1)} \cdots m_{(\mu_r)} is a product of monomial symmetric functions with a single part, it suffices to have a rule to expand the product m_{(r)} m_{(\lambda_1, \ldots, \lambda_k)} as a sum of monomial symmetric functions, since we can then iterate this rule to recover the expansion of p_\mu. It is more convenient to use the augmented monomial functions M_\mu, which are scalings of the original functions m_\mu by an integer: if \mu = (1^{a_1}, 2^{a_2}, \ldots, k^{a_k}) then

M_\mu = a_1! \cdots a_k! \, m_\mu.

A monomial symmetric function is a sum over the orbit of a composition under a group action, wheras an augmented monomial is more like the sum over the group elements.

The rule for the product m_{(r)} m_{(\lambda_1, \ldots, \lambda_k)} then takes a simple form:

m_{(r)} M_{(\lambda_1, \ldots, \lambda_k)} = M_{(r, \lambda_1, \ldots, \lambda_k)} + M_{(\lambda_1 + r, \ldots, \lambda_k)} + \cdots + M_{(\lambda_1, \ldots, \lambda_k + r)}
(where we need to sort the compositions appearing on the right hand side back into being partitions). Finally, after expanding p_\mu into a sum of the M_\lambda, we scale the coefficient of each M_\lambda to recover the decomposition of p_\mu into a sum of the m_\lambda, which is the \mu column of the permutation character table.

Generating irreducible characters

Denote the permutation modules M^\mu, and the irreducible modules S^\mu. These modules satisfy a unitriangularity property with respect to the dominance order on partitions: if the irreducible S^\lambda appears inside the permutation module M^\mu, then \mu dominates \lambda. The lexicographic order (the one used in the table) is a refinement of the dominance order, which means that for the row labelled by \lambda, the irreducible S^\lambda only appears in the permutation modules M^\mu for those \mu which are equal to or below \lambda in the table. Furthermore, S^\lambda appears in M^\lambda exactly once, and S^{(n)} = M^{(n)} (the top row of both tables are the same).

This gives an inductive way of transforming the permutation character table into the irreducible character table. Beginning with the first row (which is already irreducible), use the inner product on class functions to determine how often that irreducible appears in the lower rows. Then, subtract that irreducible from each of the lower rows as many times as it appeared in each row. After this is done, the second row must be irreducible, and we repeat the same process to the rows below the second (leaving the rows above untouched), until every row is irreducible.

Computing tensor product decompositions

Given two characters \chi_1 and \chi_2, the character \chi_1 \otimes \chi_2 corresponding to their tensor product is given by the pointwise product of class functions: (\chi_1 \otimes \chi_2)(g) = \chi_1(g) \chi_2(g). In order to decompose this new class function back into a sum of irreducible characters, we use the inner product on class functions:

\chi_1 \otimes \chi_2 = \sum_{\lambda} (\chi_1 \otimes \chi_2, s_\lambda) s_\lambda.
Since we already have the entire character table available, it is straightforward to compute the numbers (\chi_1 \otimes \chi_2, s_\lambda) for each partition \lambda of n.

Computing alternating, symmetric, and tensor powers

Given a representation \rho: G \to \operatorname{End}_{\mathbb{C}}(V) of groups, we naturally obtain representations of G on the exterior powers \wedge^r(V), the symmetric powers S^r(V), and the tensor powers \otimes^r V, by functorality. If we only know the character \chi(g) = \operatorname{trace}(\rho(g)) of the representation \rho, it is possible to compute the characters of the exterior, symmetric, and tensor powers.

The most straightforward to compute is the tensor power, since a tensor product of representations correpsonds to a pointwise product of characters. So if \chi is the character of V, then (\otimes^r \chi)(g) = \chi(g)^r is the character of \otimes^r(V).

Now, consider the exterior power \wedge^r (V) and the symmetric power S^r(V). For each group element g, we need to compute the trace of \rho(g) on \wedge^r (V) and on S^r(V). The matrix \rho(g) has finite order, and hence diagonalises, say with eigenvalues \lambda_1, \ldots, \lambda_n (counted with multiplicity). By considering bases for \wedge^r (V) and S^r(V), it is easy to see that

\operatorname{trace}(\rho(g) | \wedge^r A) = \sum_{1 \leq i_1 < \cdots < i_r \leq n} \lambda_{i_1} \cdots \lambda_{i_r} = e_r(\lambda_1, \ldots, \lambda_n),
\operatorname{trace}(\rho(g) | S^r A) = \sum_{1 \leq i_1 \leq \cdots \leq i_r \leq n} \lambda_{i_1} \cdots \lambda_{i_r} = h_r(\lambda_1, \ldots, \lambda_n),
where e_r is the rth elementary symmetric function, and h_r is the rth complete symmetric function. Knowing this is not immediately helpful, since it’s still unclear how to produce (for example) the number e_r(\lambda_1, \ldots, \lambda_n) if all we know is the trace \chi(g) = \lambda_1 + \cdots + \lambda_n.

However, since the character \chi contains the trace of every group element, we can notice that

\operatorname{trace}(\rho(g)^r) = \sum_{1 \leq i \leq n} \lambda_i^r = p_r(\lambda_1, \ldots, \lambda_n),
where p_r is the rth power sum symmetric function. We can actually compute this value from \chi, since \rho(g)^r = \rho(g^r), hence p_r(\lambda_1, \ldots, \lambda_n) = \chi(g^r). In the case of symmetric groups, all that this requires knowing is how to compute “powers” of cycle types: if g \in S_n has cycle type \mu, then determine what the cycle type of g^r is.

Finally, in order to compute e_r(\lambda_1, \ldots, \lambda_n) and h_r(\lambda_1, \ldots, \lambda_n), we use Newton’s identities which express the (elementary / complete) symmetric functions in terms of power sums. For the elementary symmetric functions, the recurrence is

e_r = \frac{1}{r} \sum_{j = 1}^r (-1)^{r + 1} e_{r - j} p_j
which in terms of a character \chi, tells us that the character \wedge^r \chi corresponding to the rth exterior power \wedge^r V is given by
(\wedge^r \chi)(g) = \frac{1}{r} \sum_{j = 1}^r (-1)^{r + 1} (\wedge^{r - j} \chi)(g) \cdot \chi(g^j),
which requires knowing the class functions \wedge^0 \chi, \cdots, \wedge^{r-1} \chi. We begin the induction with \wedge^0 \chi being the trivial character, and then compute as many exterior powers as necessary.

Computing symmetric powers is almost the same as computing exterior powers; applying the \omega involution to the above recurrence for elementary symmetric functions gives

h_r = \frac{1}{r} \sum_{j = 1}^r h_{r - j} p_j,
allowing all of the characters S^r \chi to be computed in the same manner.