Joel Gibson

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.

It takes on the order of a second or two to generate irreducible character tables for groups of size around S_{20}, S_{21}, S_{22}, and on the order of 1-2 mins to generate the character table for S_{30}, the maximum size allowed. The permutation modules take significantly longer. After S_{20} it becomes quite difficult for the browser to lay out the character table (it takes far longer for the browser to render the table to the screen than it does to generate it in the first place!), so the character values are hidden, and the character table turns into more of a “picker” for the tensor decompositions below.

Show characters for:


of the symmetric group on n = letters

About the program

This is the second generation of this program, taking advantage of modern web features such as true integers and a proper Map data structure. A key data structure used is a linear combination of partitions, represented as a map from partitions to BigInts. (A slight hitch: the Javascript Map type cannot deal with complex keys like partitions, so instead partitions are converted to and from integers when they are used as keys. More on that below). There are various helper functions for computing basic combinatorial data, like the size of a conjugacy class and so on. The more interesting algorithms are explained below, and the full code is available in a single file characters.ts.

Permutation characters

The column corresponding to the cycle type \mu = (\mu_1, \ldots, \mu_r) in the permutation character 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.

Irreducible characters via permutation 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.

Note however that this method is slower than the border strip method outlined below, since it takes a while to even generate the permutation character table. For example on my home computer, the border-strip method to calculate the irreducible character table of S_{20} runs in half a second, while generating the permutation character table for S_{20} runs in about 17 seconds. In the current version of the program, the border-strip method is used.

Irreducible characters via border strips

The change of basis matrix from the power sum symmetric functions to the Schur symmetric functions is identical (up to transpose) to the irreducible character table for S_n. Precisely, we have for a partition \mu of n that

p_\mu = \sum_{\lambda} \chi^\lambda(\mu) s_\lambda,
where \lambda runs over the partitions of size n, and \chi^\lambda(\mu) is the character of the Specht module S^\lambda, evaluated at the conjugacy class \mu. In other words, the expansion of p_\mu in the Schur basis generates a column of the irreducible character table.

To perform this expansion, we iterate a rule for taking the product of a Schur function s_\mu with a power sum generator p_k, which involves taking a sum over all the ways of adding border strips of length k to the partition \mu:

s_\mu p_k = \sum_\lambda (-1)^{\mathrm{ht}(\lambda/\mu)} s_\lambda,
where the sum is taken over all \lambda such that \lambda/\mu is a border strip of length k. The height of a border strip \mathrm{ht}(\lambda/\mu) is one less than the number of rows that the border strip touches. A border strip of length k is some way of adding k squares to \mu such that all added squares are connected, the resulting shape is a partition, and the strip always moves either north or east. An example to clarify things: here are the five border strips of length 4 that can be added to the partition (2, 1, 1):

Using this picture and the sum formula above, we get

s_{211} p_4 = s_{611} - s_{431} + s_{332} + s_{2222} - s_{2111111}.

Since each power sum corresponding to a partition is a product, for example p_{4, 2, 1} = p_4 p_2 p_1, this simple rule can be iterated over and over to expand a power sum function into the Schur basis, the base case being the empty partition: ((s_\varnothing p_4) p_2) p_1. With a little bit (or rather a lot) of thought about how to write efficient code to iterate over the ways of adding a border strip to a partition, this ends up being a remarkably efficient method of generating the character table. (The programs on this page generate character tables signficantly faster than Magma, for example).

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.

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.

Enumerating partitions

Now to address the hitch we had before: because of the way the Map type works in Javascript, we cannot use partitions (lists of integers) as keys, but rather we can only use basic types like numbers, strings, etc. A previous version of this program just JSON-encoded all partitions as strings to put them in and out of maps, but this is quite wasteful and causes a huge amount of allocations. When I’ve come across this issue in larger projects, I’ve written my own map type that can deal with complex keys (this is for example how characters are stored in LieVis). However, to keep this program self-contained and relatively short, we can do some lovely elementary combinatorics to find a way of sending partitions to integers and back again.

We will really be sending each partition \lambda to a pair (|\lambda|, \sigma(\lambda)) of its size, and its 0-indexed position in a sorted list of all partitions of size |\lambda|. (In Javascript we will further encode a pair to a single number via something like N\sigma(\lambda) + |\lambda|, where N is an upper limit on the size of a partition this encoding can handle, but this is a minor detail). The partitions of a fixed size n are sorted in increasing order lexicographically, for instance the partitions of 5 would be indexed

\sigma(\lambda)0123456
\lambda11111211122131132415

What we need is a quick way to start with a partition like (3, 2), and find its index in this list - preferably without having to generate or store every partition in the list. In order to do this we use a counting function: let P(n, k) be the number of partitions of n whose first part is k, and let R(n, k) be the number of partitions of n with rows of length \leq k. By considering the fact that chopping the first part off a partition with first part k we are left with the remainder of the partition having rows of length \leq k, we have the recurrences:

\begin{aligned} P(0, 0) &= 1, \\ P(n, 0) &= 0 & \text{if } n \geq 1, \\ P(n, k) &= 0 & \text{if } k > n, \\ P(n, k) &= R(n - k, k) & \text{if } k \leq n, \\ R(n, k) &= P(n, 0) + P(n, 1) + \cdots + P(n, k) & \text{for } 0 \leq k. \end{aligned}

It is straightforward to calculate a table of R values up to some fixed maximum size of n (in this program we use n < 64), and this table of size n^2 can be filled out in O(n^2) time. The P values are not actually needed in practice, but they make the recurrence much more clear.

The chosen total ordering on partitions of n means that all of the partitions with first part k have indices in the range [R(n, k - 1), R(n, k)). Furthermore, the set of partitions in this range is in order-preserving bijection with the set of partitions of size n - k with parts of size at most k, and hence we get a recursive method for converting a partition to its index. Going the other way, given an index \sigma(\lambda) we can find the k such that R(n, k - 1) \leq \sigma(\lambda) < R(n, k), and then do a similar recursion.

History