3
$\begingroup$

I'm interested in the representation theory of symmetric groups.

I'm now trying to search for the formula for the characters of $\Omega^{k}$, the set of $k$-tuple of elements of $\Omega$ a set of $n$ elements where $S_{n}$ acts in the standard way.

More precisely, I want to know the formula for the expansion of the characters of $\Omega^{k}$ into the linear combination of irreducible characters $\chi^{\lambda}$ labeled by the partitions $\lambda$.

It seems that such a formula was used in the old papers (for example papers of Frobenius) to compute the character tables.

So I hope there is some simple well-known formula.

Is there any? Or can we just use the Littlewood Richardson Rule on the power of $1 + \chi^{(n-1,1)}$ manually?

Any references are welcome.

$\endgroup$
5
  • 2
    $\begingroup$ This is the character of the Young permutation module $M^{(n-k,1^k)}$, or the character usually denoted $\pi^{(n-k,1^k)}$ and the decomposition is given by Young's rule. You can also use the more general Littlewood–Richardson Rule if you like. Anyway, the multiplicity of $\chi^\lambda$ is the number of semistandard $\lambda$-tableaux with content $(n-k,1^k)$, i.e. the number of standard $\lambda$-tableaux with $n-k$ $1$s, and one each of $2$, $\ldots$, $k+1$. $\endgroup$ Apr 13 at 16:57
  • 1
    $\begingroup$ @MarkWildon Hence the keyword is the Young permutation module! Thank you very much for your answer! $\endgroup$
    – gualterio
    Apr 13 at 16:59
  • 1
    $\begingroup$ @MarkWildon: wouldn't what you described be the action of $S_n$ on $k$-tuples of distinct elements of $[n]$? $\endgroup$ Apr 13 at 17:01
  • $\begingroup$ Since the action (for $k>1$) is not transitive, it cannot be the same as the action on a Young subgroup. But probably you can express it as a sum of these. $\endgroup$ Apr 13 at 17:16
  • 2
    $\begingroup$ Yes, I assumed, partly from the reference to Frobenius, that a transitive action was intended. But as you say, if the content is arbitrary one just gets a sum of the $\pi^{(n-j,1^j)}$: the multiplicity of $\pi^{(n-j,1^j)}$ is the number of partitions of $k$ into exactly $j$ parts. For instance if $k=4$ then we have $2\pi^{(n-2,1,1)}$, corresponding to the two orbits containing $(1,1,2,2)$ and $(1,1,1,2)$. $\endgroup$ Apr 13 at 17:20
6
$\begingroup$

There are several possible interpretations of $\Omega^k$ (admittedly some don't quite align with what you ask): ordered/unordered subsets of $k$ distinct/not necessarily distinct elements of $[n]$. There are two questions about them, "what is the character?" and "what are the multiplicities of irreducibles?".

Case 1: ordered, not necessarily distinct

In this case we can recognise the permutation representation as just the $k$-th tensor power of $\mathbb{C}^n$ (with the usual action). Since the character of $\mathbb{C}^n$ on an element of cycle type $\mu$ is just $m_1(\mu)$ (the number of parts of size $1$ in $\mu$), the character of $\Omega^k$ is $m_1(\mu)^k$. The multiplicity rules can be easily deduced from the rule for taking the tensor product with $\mathbb{C}^n$. Details can be found in RSK Insertion for Set Partitions and Diagram Algebras and the answer is "vacillating tableaux of shape $\lambda$ and size $k$". (Caveat: you need to be a little more careful if $n$ is smaller than $2k$, for example if $n=1$, then any tensor power of $\mathbb{C}^n$ is still just $\mathbb{C}^n$, which is definitely not true if $n > 1$. Feel free to ask for more detail if Secion 2 of the paper doesn't address your concerns.)

Case 2: unordered, not necessarily distinct

In this case, we can recognise $\Omega^k$ as the $k$-th symmetric power of $\mathbb{C}^n$. One way to view this is as the restriction of $\mathrm{Sym}^k(\mathbb{C}^n)$ from $GL_n(\mathbb{C})$ to $S_n$ (viewed as the subgroup of permutation matrices). Hence the character is obtained by evaluating the Schur polynomial $s_k(x_1, x_2, \ldots, x_n)$ at the eigenvalues of a permutation matrix (each $r$-cycle contributes the set of all $r$-th roots of unity). You can read more about this approach in Symmetric group characters as symmetric functions. As for the multiplicities, there is a (well-known?) formula which can be found in Exercise 7.74 of Enumerative Combinatorics Vol. 2 which states that the multiplicity of the irreducible $S^\mu$ in the $GL_n(\mathbb{C})$ irreducible indexed by $\lambda$ is

$$\langle s_\lambda, s_\mu[1 + h_1 + h_2 + \cdots ] \rangle$$

where $s_\lambda, s_\mu$ are Schur functions, square brackets denote plethysm, and $h_i$ are complete symmetric functions. In our case, $\lambda = (k)$ and we can use some tricks (which I can elaborate on, if requested) to deduce that the multiplicity is the number of semi-standard Young tableau of shape $\mu$ and weight $\nu$, such that $0 \nu_1 + 1 \nu_2 + 2 \nu_3 + \cdots = k$.

Case 3: ordered, distinct

Note first of all that if we require distinctness, $k \leq n$. As Mark Wildon pointed out in the comments, we may recognise $\Omega^k$ as the permutation module $M^{(n-k, 1^k)}$ (i.e. indexed by the partition that has $k$ parts of size 1, and one part of size $n-k$). The number of fixed points of an elements of cycle type $\mu$ is ${m_1(\mu) \choose k}$ (so this is the character). The multiplicity of $S^\lambda$ is given by the number of semi-standard Young tableaux of shape $\lambda$ and weight $(n-k, 1^k)$.

Case 4: unordered, distinct

We can identify $\Omega^k$ as the permutation module $M^{(n-k,k)}$. Although this has a basis that can be identified with the $k$-th exterior power of $\mathbb{C}^n$, that is not the correct representation because swapping two adjacent elements of a wedge monomial incurs a sign, while swapping to elements of an unordered set does not. This was investigated by Stier, Wellman, and Xu in Dihedral Sieving on Cluster Complexes; see Theorem 6.4. Similarly to Case 2, This gives a polynomial, which when evaluated at eigenvalues of a permutation matrix, gives the character. As for the multiplicities, they are given by the number of semi-standard Young tableaux of shape $\lambda$ and weight $(n-k,k)$.

$\endgroup$
2
  • $\begingroup$ Nice summary!.. $\endgroup$ Apr 13 at 18:57
  • $\begingroup$ I think your answer will be helpful for my further study in this area. Thank you for the references! $\endgroup$
    – gualterio
    Apr 14 at 7:58
2
$\begingroup$

EDIT: I realized my previous answer used buggy code. The stuff below should be more correct.

The Frobenius characteristics for different values of $n$, $1\leq k\leq n$ are $$ \begin{array}{lllll} s_1 & \text{} & \text{} & \text{} & \text{} \\ s_2+s_{11} & s_2 & \text{} & \text{} & \text{} \\ s_3+s_{21} & s_3+s_{21} & s_3 & \text{} & \text{} \\ s_4+s_{31} & s_4+s_{22}+s_{31} & s_4+s_{31} & s_4 & \text{} \\ s_5+s_{41} & s_5+s_{32}+s_{41} & s_5+s_{32}+s_{41} & s_5+s_{41} & s_5 \\ \end{array} $$

In general, the Frobenius characteristic is just $h_{n-k}h_k$ where $h$ is a complete homogeneous symmetric function. Expanding these in the Schur basis can be done with the Pieri rule, and here we see that the multiplicities are Kostka coefficients (i.e., a number of SSYT).

I just follow these steps to compute the Frobenous characteristic explicitly. We let $M$ be the $S_n$-module with basis $\{x_{T}\}$ with $T\subset \binom{[n]}{k}$. This is clearly $\binom{n}{k}$-dimensional. Also, $S_n$ act on $M$ by acting on the variable indices.

We want to see how $\sigma \in S_n$ act on a basis vector. Here, $$ \sigma (x_S) = 0 x_{T_1} + 0 x_{T_2}+ \dotsb + 1 x_{\sigma(S)}+ \dotsb + 0 x_{T_\ell}, $$ for general $\sigma \in S_n$. We express this as a square matrix, with $\binom{n}{k}$ rows/columns. The trace of this matrix is the character value of $\sigma$. We sum $p_{\lambda(\sigma)}$ over all $\sigma$, and divide the total with $n!$. This gives the following table.

\begin{array}{lllll} p_1 & \text{} & \text{} & \text{} & \text{} \\ p_{11} & \frac{1}{2} \left(p_2+p_{11}\right) & \text{} & \text{} & \text{} \\ \frac{1}{6} \left(3 p_{21}+3 p_{111}\right) & \frac{1}{6} \left(3 p_{21}+3 p_{111}\right) & \frac{1}{6} \left(2 p_3+3 p_{21}+p_{111}\right) & \text{} & \text{} \\ \frac{1}{24} \left(8 p_{31}+12 p_{211}+4 p_{1111}\right) & \frac{1}{24} \left(6 p_{22}+12 p_{211}+6 p_{1111}\right) & \frac{1}{24} \left(8 p_{31}+12 p_{211}+4 p_{1111}\right) & \frac{1}{24} \left(6 p_4+3 p_{22}+8 p_{31}+6 p_{211}+p_{1111}\right) & \text{} \\ \frac{1}{120} \left(30 p_{41}+15 p_{221}+40 p_{311}+30 p_{2111}+5 p_{11111}\right) & \frac{1}{120} \left(20 p_{32}+30 p_{221}+20 p_{311}+40 p_{2111}+10 p_{11111}\right) & \frac{1}{120} \left(20 p_{32}+30 p_{221}+20 p_{311}+40 p_{2111}+10 p_{11111}\right) & \frac{1}{120} \left(30 p_{41}+15 p_{221}+40 p_{311}+30 p_{2111}+5 p_{11111}\right) & \frac{1}{120} \left(24 p_5+20 p_{32}+30 p_{41}+15 p_{221}+20 p_{311}+10 p_{2111}+p_{11111}\right) \\ \end{array}

Converting to the Schur basis gives the decomposition into irreducibles.

$\endgroup$
5
  • 2
    $\begingroup$ I'm confused by this answer: first the OP seemed to want the product not the set of size $k$ subsets, and second you seem to be claiming that Sn acts trivially on size k subsets, which is false. $\endgroup$ Apr 13 at 18:12
  • $\begingroup$ @PhilTosteson Yeah, I realized I had some mistakes in my code. It now agrees with the answer above. $\endgroup$ Apr 13 at 19:07
  • 1
    $\begingroup$ You're still answering the question for subsets and not tuples. The subsets question is well-known and explained for instance in Stanley's EC 2, Example 7.18.8(a) (as I had mentioned in a previous comment which I deleted after realizing the OP was interested in tuples). $\endgroup$ Apr 13 at 19:08
  • $\begingroup$ @SamHopkins Ah, right! I was too hasty. $\endgroup$ Apr 14 at 6:41
  • 1
    $\begingroup$ Thank you for your answer! I will study your answer. $\endgroup$
    – gualterio
    Apr 14 at 8:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.