Murnaghan–Nakayama rule

In group theory, a branch of mathematics, the Murnaghan–Nakayama rule is a combinatorial method to compute irreducible character values of a symmetric group.[1] There are several generalizations of this rule beyond the representation theory of symmetric groups, but they are not covered here.

The irreducible characters of a group are of interest to mathematicians because they concisely summarize important information about the group, such as the dimensions of the vector spaces in which the elements of the group can be represented by linear transformations that “mix” all the dimensions. For many groups, calculating irreducible character values is very difficult; the existence of simple formulas is the exception rather than the rule.

The Murnaghan–Nakayama rule is a combinatorial rule for computing symmetric group character values χ^λ
_ρ using a particular kind of Young tableaux. Here λ and ρ are both integer partitions of some integer n, the order of the symmetric group under consideration. The partition λ specifies the irreducible character, while the partition ρ specifies the conjugacy class on whose group elements the character is evaluated to produce the character value. The partitions are represented as weakly decreasing tuples; for example, two of the partitions of 8 are (5,2,1) and (3,3,1,1).

There are two versions of the Murnaghan-Nakayama rule, one non-recursive and one recursive.

Non-recursive version

Theorem:

${\displaystyle \chi _{\rho }^{\lambda }=\sum _{T\in BST(\lambda ,\rho )}(-1)^{ht(T)}}$

where the sum is taken over the set BST(λ,ρ) of all border-strip tableaux of shape λ and type ρ. That is, each tableau T is a tableau such that

• the k-th row of T has λ_k boxes
• the boxes of T are filled with integers, with the integer i appearing ρ_i times
• the integers in every row and column are weakly increasing
• the set of squares filled with the integer i form a border strip, that is, a connected skew-shape with no 2×2-square.

The height, ht(T), is the sum of the heights of the border strips in T. The height of a border strip is one less than the number of rows it touches.

It follows from this theorem that the character values of a symmetric group are integers.

For some combinations of λ and ρ, there are no border-strip tableaux. In this case, there are no terms in the sum and therefore the character value is zero.

Example

Consider the calculation of one of the character values for the symmetric group of order 8, when λ is the partition (5,2,1) and ρ is the partition (3,3,1,1). The shape partition λ specifies that the tableau must have three rows, the first having 5 boxes, the second having 2 boxes, and the third having 1 box. The type partition ρ specifies that the tableau must be filled with three 1's, three 2's, one 3, and one 4. There are six such border-strip tableaux:

Example of the border-strip tableaux involved in computing a particular symmetric group character value using the non-recursive Murnaghan-Nakayama rule.

If we call these ${\displaystyle T_{1}}$, ${\displaystyle T_{2}}$, ${\displaystyle T_{3}}$, ${\displaystyle T_{4}}$, ${\displaystyle T_{5}}$, and ${\displaystyle T_{6}}$, then their heights are

${\displaystyle {\begin{aligned}ht(T_{1})=0+1+0+0=1\\ht(T_{2})=1+0+0+0=1\\ht(T_{3})=1+0+0+0=1\\ht(T_{4})=2+0+0+0=2\\ht(T_{5})=2+0+0+0=2\\ht(T_{6})=2+1+0+0=3\end{aligned}}}$

and the character value is therefore

${\displaystyle \chi _{(3,3,1,1)}^{(5,2,1)}=(-1)^{1}+(-1)^{1}+(-1)^{1}+(-1)^{2}+(-1)^{2}+(-1)^{3}=-1-1-1+1+1-1=-2}$

Recursive version

Theorem:

${\displaystyle \chi _{\rho }^{\lambda }=\sum _{\xi \in BS(\lambda ,\rho _{1})}(-1)^{ht(\xi )}\chi _{\rho \backslash \rho _{1}}^{\lambda \backslash \xi }}$

where the sum is taken over the set BS(λ,ρ₁) of border strips within the Young diagram of shape λ that have ρ₁ boxes and whose removal leaves a valid Young diagram. The notation ${\displaystyle \lambda \backslash \xi }$ represents the partition that results from removing the border strip ξ from λ. The notation ${\displaystyle \rho \backslash \rho _{1}}$ represents the partition that results from removing the first element ρ₁ from ρ.

Note that the right-hand side is a sum of characters for symmetric groups that have smaller order than that of the symmetric group we started with on the left-hand side. In other words, this version of the Murnaghan-Nakayama rule expresses a character of the symmetric group S_n in terms of the characters of smaller symmetric groups S_k with k<n.

Applying this rule recursively will result in a tree of character value evaluations for smaller and smaller partitions. Each branch stops for one of two reasons: Either there are no border strips of the required length within the reduced shape, so the sum on the right is zero, or a border strip occupying the entire reduced shape is removed, leaving a Young diagram with no boxes. At this point we are evaluating χ^λ
_ρ when both λ and ρ are the empty partition (), and the rule requires that this terminal case be defined as having character ${\displaystyle \chi _{()}^{()}=1}$.

This recursive version of the Murnaghan-Nakayama rule is especially efficient for computer calculation when one computes character tables for S_k for increasing values of k and stores all of the previously computed character tables.

Example

We will again compute the character value with λ=(5,2,1) and ρ=(3,3,1,1).

To begin, consider the Young diagram with shape λ. Since the first part of ρ is 3, look for border strips that consist of 3 boxes. There are two possibilities:

Example of the border-strip tableaux involved in computing a particular symmetric group character value using the recursive Murnaghan-Nakayama rule.

In the first diagram, the border strip has height 0, and removing it produces the reduced shape (2,2,1). In the second diagram, the border strip has height 1, and removing it produces the reduced shape (5). Therefore, one has

${\displaystyle \chi _{(3,3,1,1)}^{(5,2,1)}=\chi _{(3,1,1)}^{(2,2,1)}-\chi _{(3,1,1)}^{(5)}}$,

expressing a character value of S₈ in terms of two character values of S₅.

Applying the rule again to both terms, one finds

${\displaystyle \chi _{(3,1,1)}^{(2,2,1)}=-\chi _{(1,1)}^{(2)}}$

and

${\displaystyle \chi _{(3,1,1)}^{(5)}=\chi _{(1,1)}^{(2)}}$,

reducing to a character value of S₂.

Applying again, one finds

${\displaystyle \chi _{(1,1)}^{(2)}=\chi _{(1)}^{(1)}}$,

reducing to the only character value of S₁.

A final application produces the terminal character ${\displaystyle \chi _{()}^{()}=1}$:

${\displaystyle \chi _{(1)}^{(1)}=\chi _{()}^{()}=1}$

Working backwards from this known character, the result is ${\displaystyle \chi _{(3,3,1,1)}^{(5,2,1)}=-2}$, as before.

References

1. Richard Stanley, Enumerative Combinatorics, Vol. 2