# 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.

## 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

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:

### 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:

### 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

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

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

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