Double hashing

From formulasearchengine
Revision as of 21:17, 22 December 2013 by en>Mild Bill Hiccup (Classical applied data structure: spelling)
Jump to navigation Jump to search

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 Sn and specific Young tableau λ corresponding to a numbered partition of n, define two permutation subgroups Pλ and Qλ of Sn as follows:

Pλ={gSn:g preserves each row of λ}

and

Qλ={gSn:g preserves each column of λ}.

Corresponding to these two subgroups, define two vectors in the group algebra Sn as

aλ=gPλeg

and

bλ=gQλsgn(g)eg

where eg is the unit vector corresponding to g, and sgn(g) is the signature of the permutation. The product

cλ:=aλbλ=gPλ,hQλsgn(h)egh

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 Vn=VVV (n times). Let Sn act on this tensor product space by permuting the indices. One then has a natural group algebra representation SnEnd(Vn) on Vn.

Given a partition λ of n, so that n=λ1+λ2++λj, then the image of aλ is

Im(aλ):=aλVnSymλ1VSymλ2VSymλjV.

For instance, if n=4, and λ=(2,2), with the canonical Young tableau {{1,2},{3,4}}. Then the corresponding aλ is given by aλ=eid+e(1,2)+e(3,4)+e(1,2)(3,4). Let an element in V4 be given by v1,2,3,4:=v1v2v3v4. Then

aλv1,2,3,4=v1,2,3,4+v2,1,3,4+v1,2,4,3+v2,1,4,3=(v1v2+v2v1)(v3v4+v4v3).

The latter clearly span Sym2VSym2V.

The image of bλ is

Im(bλ)μ1Vμ2VμkV

where μ is the conjugate partition to λ. Here, SymiV and jV are the symmetric and alternating tensor product spaces.

The image Sncλ of cλ=aλbλ in Sn is an irreducible representation[1] of Sn, called a Specht module. We write

Im(cλ)=Vλ

for the irreducible representation.

Some scalar multiple of cλ is idempotent, that is cλ2=αλcλ for some rational number αλ. Specifically, one finds αλ=n!/dim Vλ. In particular, this implies that representations of the symmetric group can be defined over the rational numbers; that is, over the rational group algebra Sn.

Consider, for example, S3 and the partition (2,1). Then one has c(2,1)=e123+e213e321e312

If V is a complex vector space, then the images of cλ on spaces Vd provides essentially all the finite-dimensional irreducible representations of GL(V).

See also

Notes

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.