The restriction problem

Submitted by Mike Zabrocki

A representation of Gl_n(\mathbb{C}) is a homomorphism \phi from Gl_n(\mathbb{C}) to Gl_k(\mathbb{C}) . The value of k is the dimension of the representation.

Up to isomorphism, there is one irreducible polynomial Gl_n(\mathbb{C}) representation for each partition \lambda with the length of \lambda less or equal to n . The character of that irreducible representation is the Schur function s_{\lambda}(x_1, x_2, \ldots, x_n) indexed by the partition \lambda . The dimension of that representation is the number of column strict tableaux of shape \lambda with entries in \{1, 2, \ldots, n\} .

Since the permutation matrices are a natural subgroup of Gl_n(\mathbb{C}) , when an irreducible Gl_n(\mathbb{C}) representation is restricted from Gl_n(\mathbb{C}) to S_n it decomposes as a direct sum of irreducible representations.

The restriction problem is the following:

OPAC-020. Find a combinatorial description of the decomposition of the irreducible Gl_n(\mathbb{C}) module indexed by the partition \lambda into symmetric group S_n -irreducibles.

This problem has a very long history, but generally very few people publish partial progress or failed attempts so there is very little written about it after the 1980’s beyond special cases.

To determine how a Gl_n(\mathbb{C}) irreducible decomposes into S_n irreducibles we can use the character s_{\lambda}(x_1, x_2, \ldots, x_n) of the irreducible Gl_n(\mathbb{C}) module and its evaluation at eigenvalues of permutation matrices S_n \subseteq Gl_n(\mathbb{C}) . Let \gamma be a partition of n and (\zeta_{\gamma,1}, \zeta_{\gamma,2}, \ldots, \zeta_{\gamma,n}) be the eigenvalues of a permutation matrix of cycle structure \gamma (up to reordering, this list only depends on the cycle structure).

If we evaluate the symmetric function s_{\lambda}(x_1, x_2, \ldots, x_n) at the eigenvalues (\zeta_{\gamma,1}, \zeta_{\gamma,2}, \ldots, \zeta_{\gamma,n}) , this is the value of the S_n character at a permutation of cycle structure \gamma .

Representation theory provides a formula for the multiplicity for a symmetric group irreducible indexed by \mu (where \mu is a partition of n and the character of this irreducible is denoted \chi^\mu ). It is equal to

A_{\lambda,\mu} := \sum_{\gamma} s_{\lambda}(\zeta_{\gamma,1}, \zeta_{\gamma,2}, \ldots, \zeta_{\gamma,n}) \chi^\mu(\gamma)/z_{\gamma}

where the sum is over all partitions \gamma of n .

Computing a few examples of this formula should indicate why it is not a particularly satisfactory answer beyond as a means of arriving at a numerical value. Littlewood [2, 9] showed in the 50’s that the multiplicity can be computed using the operation of plethysm:

A_{\lambda,\mu} = \langle s_{\lambda}, s_{\mu}[1 + s_1 + s_2 + \cdots]\rangle

This is an advance in the problem, but recasts the solution of one problem in terms of another for which we don’t have a combinatorial formula.

I first became interested in this problem in the early 2000’s because, from time to time, I would encounter a module for which a formula for the Gl_n(\mathbb{C}) character was well known, but the symmetric group module structure was not. Then in 2016, Rosa Orellana and I [5] found a basis of the symmetric functions that are the the characters of the symmetric group as permutation matrices S_n \subseteq Gl_n(\mathbb{C}) in the same way that the Schur functions are characters of Gl_n(\mathbb{C}) . That, is there is a basis \{\tilde{s}_{\mu}\} (and one could take the following formula as a definition of this basis) such that for all n sufficiently large,

\displaystyle s_{\lambda} = \sum_{\mu \colon |\mu| \leq |\lambda|} A_{\lambda,(n-|\mu|,\mu)} \tilde{s}_{\mu}.

Then, for \gamma a partition of n , we have \tilde{s}_{\mu}(\zeta_{\gamma,1}, \zeta_{\gamma,2}, \ldots, \zeta_{\gamma,n}) = \chi^{(n-|\mu|,\mu)}(\gamma) .

For each partition \lambda , following symmetric function encodes all of the values of the symmetric group character of this representation:

\displaystyle F_{\lambda,n} := \sum_{\gamma} s_{\lambda}(\zeta_{\gamma,1}, \zeta_{\gamma,2}, \ldots, \zeta_{\gamma,n}) \frac{p_{\gamma}}{z_{\gamma}}

where the sum is over all \gamma partitions of n . An answer to the restriction problem would provide a Schur expansion of this expression as a symmetric function of degree n . Note that if \ell(\lambda) > n , then F_{\lambda,n} = 0 .

Programs for computing data are easily accessible in Sage [7, 8] through the ring of symmetric functions. For instance, the following code:
sage: s = SymmetricFunctions(QQ).schur()
sage: s[3].character_to_frobenius_image(4)
s[2, 1, 1] + s[2, 2] + 4*s[3, 1] + 3*s[4]
computes the Schur expansion of F_{(3),4} by evaluating the character s_{(3)}(x_1, x_2, x_3, x_4) at the eigenvalues of permutation matrices and computing the Schur expansion of that expression.

In the case when \lambda = (r) , we have the following, which should be a special case of what the answer might look like in general:

Proposition. (Reformulation of [1]; see Exercise 7.73 of [10]; MacMahon’s Master Theorem [4] can be used to derive this.) The coefficient of the Schur function s_{\mu} in F_{(r),n} (where \mu is a partition of n ) is equal to the coefficient of q^r in the Schur function evaluation s_{\mu}(1, q, q^2, \ldots) .


[1] A. C. Aitken, On induced permutation matrices and the symmetric group, Proc. Edinburgh Math. Soc., 5 (1937), no. 1, 1–13. DOI: 10.1017/S0013091500008208

[2] D. E. Littlewood, Products and Plethysms of Characters with Orthogonal, Symplectic and Symmetric Groups, Canad. J. Math., 10 (1958), 17–32. DOI: 10.4153/CJM-1958-002-7

[3] I. G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd Edition, Oxford University Press, 1995.

[4] P. A. MacMahon, Combinatory Analysis, Vol. 1, Cambridge, 1915.

[5] R. Orellana, M. Zabrocki, Characters of the symmetric group as symmetric functions, prepint (2016). arXiv:1605.06672

[6] B. Sagan, The symmetric group. Representations, combinatorial algorithms, and symmetric functions, 2nd edition, Graduate Text in Mathematics 203. Springer-Verlag, 2001.

[7] W. A. Stein et al. Sage Mathematics Software (Version 6.10), The Sage Development Team, , 2016.

[8] The Sage-Combinat community. Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics, , 2008.

[9] T. Scharf, J. Y. Thibon, A Hopf-algebra approach to inner plethysm. Adv. in Math. 104 (1994), 30–58. DOI: 10.1006/aima.1994.1019

[10] R. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create your website at
Get started
%d bloggers like this: