Double hashing

In mathematics, a Young symmetrizer is an element of the group algebra of the symmetric group, constructed in such a way that the image of the element corresponds to an irreducible representation of the symmetric group over the complex numbers. A similar construction works over any field, and the resulting representations are called Specht modules. The Young symmetrizer is named after British mathematician Alfred Young.

Definition

Given a finite symmetric group S_n and specific Young tableau λ corresponding to a numbered partition of n, define two permutation subgroups $P_{\lambda }$ and $Q_{\lambda }$ of S_n as follows:

$P_{\lambda }=\{g\in S_n:g\text{ preserves each row of }\lambda \}$

and

$Q_{\lambda }=\{g\in S_n:g\text{ preserves each column of }\lambda \}.$

Corresponding to these two subgroups, define two vectors in the group algebra $\mathbb{ℂ}{S}_n$ as

$a_{\lambda }=\sum _{g\in P_{\lambda }}{e}_g$

and

$b_{\lambda }=\sum _{g\in Q_{\lambda }}\mathrm{sgn}(g)e_g$

where $e_g$ is the unit vector corresponding to g, and $\mathrm{sgn}(g)$ is the signature of the permutation. The product

$c_{\lambda }:=a_{\lambda }{b}_{\lambda }=\sum _{g\in P_{\lambda },h\in Q_{\lambda }}\mathrm{sgn}(h)e_{gh}$

is the Young symmetrizer corresponding to the Young tableau λ. Each Young symmetrizer corresponds to an irreducible representation of the symmetric group, and every irreducible representation can be obtained from a corresponding Young symmetrizer. (If we replace the complex numbers by more general fields the corresponding representations will not be irreducible in general.)

Construction

Let V be any vector space over the complex numbers. Consider then the tensor product vector space $V^{\otimes n}=V\otimes V\otimes \cdots \otimes V$ (n times). Let S_n act on this tensor product space by permuting the indices. One then has a natural group algebra representation $\mathbb{ℂ}{S}_n\to \text{End}(V^{\otimes n})$ on $V^{\otimes n}$.

Given a partition λ of n, so that $n={\lambda }_1+{\lambda }_2+\cdots +{\lambda }_j$, then the image of $a_{\lambda }$ is

$\text{Im}(a_{\lambda }):=a_{\lambda }{V}^{\otimes n}\cong {\text{Sym}}^{{\lambda }_1}V\otimes {\text{Sym}}^{{\lambda }_2}V\otimes \cdots \otimes {\text{Sym}}^{{\lambda }_j}V.$

For instance, if $n=4$, and $\lambda =(2,2)$, with the canonical Young tableau $\{\{1,2\},\{3,4\}\}$. Then the corresponding $a_{\lambda }$ is given by $a_{\lambda }=e_{\text{id}}+e_{(1,2)}+e_{(3,4)}+e_{(1,2)(3,4)}$. Let an element in $V^{\otimes 4}$ be given by $v_{1,2,3,4}:=v_1\otimes v_2\otimes v_3\otimes v_4$. Then

$a_{\lambda }{v}_{1,2,3,4}=v_{1,2,3,4}+v_{2,1,3,4}+v_{1,2,4,3}+v_{2,1,4,3}=(v_1\otimes v_2+v_2\otimes v_1)\otimes (v_3\otimes v_4+v_4\otimes v_3).$

The latter clearly span ${\text{Sym}}^{2}V\otimes {\text{Sym}}^{2}V$.

The image of $b_{\lambda }$ is

$\text{Im}(b_{\lambda })\cong {\bigwedge }^{{\mu }_1}V\otimes {\bigwedge }^{{\mu }_2}V\otimes \cdots \otimes {\bigwedge }^{{\mu }_k}V$

where μ is the conjugate partition to λ. Here, ${\text{Sym}}^{i}V$ and ${\bigwedge }^{j}V$ are the symmetric and alternating tensor product spaces.

The image $\mathbb{ℂ}{S}_n{c}_{\lambda }$ of $c_{\lambda }=a_{\lambda }\cdot b_{\lambda }$ in $\mathbb{ℂ}{S}_n$ is an irreducible representation of S_n, called a Specht module. We write

$\text{Im}(c_{\lambda })=V_{\lambda }$

for the irreducible representation.

Some scalar multiple of $c_{\lambda }$ is idempotent, that is $c_{\lambda }^2={\alpha }_{\lambda }{c}_{\lambda }$ for some rational number ${\alpha }_{\lambda }\in \mathbb{\mathbb{Q}}$. Specifically, one finds ${\alpha }_{\lambda }=n!/\text{dim }{V}_{\lambda }$. In particular, this implies that representations of the symmetric group can be defined over the rational numbers; that is, over the rational group algebra $\mathbb{\mathbb{Q}}{S}_n$.

Consider, for example, S₃ and the partition (2,1). Then one has $c_{(2,1)}=e_{123}+e_{213}-e_{321}-e_{312}$

If V is a complex vector space, then the images of $c_{\lambda }$ on spaces $V^{\otimes d}$ provides essentially all the finite-dimensional irreducible representations of GL(V).

See also

• Representation theory of the symmetric group

References

• William Fulton. Young Tableaux, with Applications to Representation Theory and Geometry. Cambridge University Press, 1997.
• Lecture 4 of Template:Fulton-Harris
• Bruce E. Sagan. The Symmetric Group. Springer, 2001.