Symmetric group representation

Intuition [Beginner]

The symmetric group $S_n$ is the group of all ways to shuffle $n$ objects — $n!$ permutations in total. Asking how this group can act linearly on a vector space, with which symmetry patterns arise, leads to one of the most beautiful classifications in mathematics: irreducible representations of $S_n$ are labelled by partitions of $n$, the same partitions you write when you split a number into a non-increasing sum like $5=3+1+1$.

The intuition is that every linear pattern compatible with permuting $n$ things must respect some internal grouping of those things, and the partition records that grouping. The unit representation (everything fixed) corresponds to the row partition $(n)$. The sign representation (a swap multiplies by $-1$) corresponds to the column partition $(1,1,\dots ,1)$. In between sits a full ladder of irreducibles, one per partition.

Frobenius (1900) gave the character formula counting these representations; Young (the same year and continuing for three decades) built them concretely as projection operators on spaces of polynomials. The two pictures together — characters from above, tableaux from below — meet in the middle to give the complete representation theory.

Visual [Beginner]

The five partitions of $4$, drawn as Young diagrams: $(4)$, $(3,1)$, $(2,2)$, $(2,1,1)$, $(1,1,1,1)$. Each one labels a different irreducible representation of the symmetric group $S_4$, and the squared dimensions add to $4!=24$.

Worked example [Beginner]

Take $S_3$, the group of $6$ permutations of three letters $\{a,b,c\}$. Its irreducibles are labelled by the three partitions of $3$:

• $(3)$: the unit representation, dimension $1$. Every permutation acts as the number $1$.
• $(2,1)$: the standard representation, dimension $2$. Realise it on the plane $\{(x,y,z):x+y+z=0\}$, where $S_3$ permutes coordinates.
• $(1,1,1)$: the sign representation, dimension $1$. A permutation acts as $+1$ if it is even, $-1$ if it is odd.

Adding squared dimensions: $1^2+2^2+1^2=6=3!$. This matches the general dimension theorem for any finite group: the squared dimensions of irreducibles add to the order of the group. What this tells us: just three irreducibles, captured by three pictures (a single row, a hook, a single column), classify all linear symmetry patterns of three letters.

Check your understanding [Beginner]

Formal definition [Intermediate+]

Let $S_n$ denote the symmetric group on $n$ letters, of order $n!$. Conjugacy classes of $S_n$ are indexed by cycle types, which correspond bijectively to partitions of $n$:

$$\lambda =({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_k),{\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_k\ge 1,{\lambda }_1+\cdots +{\lambda }_k=n.$$

Write $\lambda ⊢n$ for "$\lambda$ is a partition of $n$." Let $p(n)$ denote the number of such partitions. For $n\le 6$: $p(1)=1,p(2)=2,p(3)=3,p(4)=5,p(5)=7,p(6)=11$.

Theorem (Frobenius-Young classification). Over $\mathbb{C}$, the irreducible representations of $S_n$ are in bijection with partitions of $n$. Write $V^{\lambda }$ (or $S^{\lambda }$ in the modular setting) for the irreducible labelled by $\lambda ⊢n$.

The bijection is implemented in two complementary ways:

(i) Frobenius character formula (1900). For $\lambda ⊢n$, the character ${\chi }^{\lambda }$ is the coefficient of a specific monomial in a determinantal expansion of the power-sum symmetric polynomials. Concretely, with variables $x_1,\dots ,x_n$ and the Vandermonde $\Delta ={\prod }_{i<j}(x_i-x_j)$,

$${\chi }^{\lambda }(\mu )=\left[x^{\lambda +\delta }\right]p_{\mu }\cdot \Delta ,\delta =(n-1,n-2,\dots ,1,0),$$

where $\mu ⊢n$ is the cycle type of the conjugacy class, $p_{\mu }=p_{{\mu }_1}{p}_{{\mu }_2}\cdots$ is the product of power-sum symmetric polynomials, and $[\cdot ]$ extracts the coefficient.

(ii) Young tableau realisation (Young 1900-1933). For each $\lambda ⊢n$, draw the Young diagram of $\lambda$ — left-justified rows of boxes, ${\lambda }_i$ boxes in row $i$ — and fill the boxes with $1,2,\dots ,n$. A Young symmetriser $c_{\lambda }\in \mathbb{C}[S_n]$ is built as a signed sum of row-symmetrisers and column-antisymmetrisers, and the irreducible $V^{\lambda }$ is the left ideal $\mathbb{C}[S_n]\cdot c_{\lambda }$.

Hook length formula (Frame-Robinson-Thrall, 1954). The dimension of $V^{\lambda }$ is

$$\dim V^{\lambda }=\frac{n!}{{\prod }_{(i,j)\in \lambda }h(i,j)},$$

where $h(i,j)$ is the hook length of the cell $(i,j)$ — the number of cells to its right in the same row plus the number below in the same column, plus $1$ for the cell itself.

Specific irreducibles. Three families of partitions are universally named:

• $\lambda =(n)$: the unit representation, $\dim =1$, every permutation acts as $1$.
• $\lambda =(1,1,\dots ,1)=(1^n)$: the sign representation, $\dim =1$, $\sigma \mapsto \mathrm{sgn}(\sigma )$.
• $\lambda =(n-1,1)$: the standard representation, $\dim =n-1$, realised on the hyperplane $\{x_1+\cdots +x_n=0\}$ in ${\mathbb{C}}^n$ where $S_n$ permutes coordinates.

The full list of dimensions for any $S_n$ is computed by the hook formula and squared-summed by ${\sum }_{\lambda ⊢n}(\dim V^{\lambda }{)}^2=n!$.

Key theorem with proof [Intermediate+]

Theorem (Bijection between partitions and irreducibles of $S_n$). Over $\mathbb{C}$, the map

$$\{\lambda :\lambda ⊢n\}\stackrel{1:1}{\leftrightarrow }\{\text{irreducible }{S}_n\text{-reps}\}/\cong ,\lambda \mapsto V^{\lambda }:=\mathbb{C}[S_n]\cdot c_{\lambda }$$

is a bijection.

Proof.

The strategy proceeds by counting both sides and matching.

Counting irreducibles. For any finite group $G$, the number of irreducible complex representations equals the number of conjugacy classes (a standard consequence of character orthogonality and the Schur-orthogonality machinery built on 07.01.02). For $S_n$, two permutations are conjugate iff they have the same cycle type, and cycle types correspond to partitions of $n$. So there are exactly $p(n)$ irreducibles.

Constructing irreducibles from tableaux. For a partition $\lambda ⊢n$, fill the Young diagram of $\lambda$ row by row with $1,2,\dots ,n$ to obtain a standard Young tableau $T$. Define two subgroups of $S_n$:

• $R(T)$: row stabiliser — permutations preserving each row of $T$ as a set.
• $C(T)$: column stabiliser — permutations preserving each column.

Form the Young symmetriser

$$c_{\lambda }:=a_T\cdot b_T,a_T=\sum _{p\in R(T)}p,b_T=\sum _{q\in C(T)}\mathrm{sgn}(q)q,$$

an element of the group algebra $\mathbb{C}[S_n]$. The element $c_{\lambda }$ is quasi-idempotent: $c_{\lambda }^2=n_{\lambda }\cdot c_{\lambda }$ for a non-zero scalar $n_{\lambda }=n!/\dim V^{\lambda }$.

Irreducibility. The left ideal $V^{\lambda }:=\mathbb{C}[S_n]\cdot c_{\lambda }$ is an $S_n$-representation. To show it is irreducible: for any $x\in \mathbb{C}[S_n]$, compute $c_{\lambda }x{c}_{\lambda }$. By a combinatorial lemma (the fundamental identity of Young), this product is a scalar multiple of $c_{\lambda }$. Hence ${\mathrm{End}}_{S_n}(V^{\lambda })=\mathbb{C}$, and Schur's lemma 07.01.02 forces $V^{\lambda }$ irreducible.

Distinct labels give distinct representations. For $\lambda \ne \mu$, the Young symmetrisers $c_{\lambda }$ and $c_{\mu }$ generate non-isomorphic ideals: an explicit calculation shows $c_{\mu }\cdot \mathbb{C}[S_n]\cdot c_{\lambda }=0$ whenever $\lambda$ and $\mu$ are different partitions and $\lambda$ does not dominate $\mu$ in the dominance order. Combined with the count from Step 1, the $p(n)$ representations $\{V^{\lambda }{\}}_{\lambda ⊢n}$ exhaust the irreducibles. $\square$

The combinatorial lemmas (quasi-idempotency of $c_{\lambda }$, vanishing of cross products) are the technical core; complete proofs are in Sagan Ch. 2 or Fulton-Harris §4. The genius of Young's construction is that the entire representation theory becomes a calculation with diagrams and tableaux rather than abstract characters.

Bridge. The construction here builds toward later units of the strand, where the same pattern is taken up at higher structure. The defining pattern appears again in those units in a sharpened form, where the local data is glued or quotiented. Putting these together, the foundational insight is that the data of this unit gives the structural signature that the rest of the strand reads off.

Exercises [Intermediate+]

Lean formalization [Intermediate+]

lean_status: partial — Mathlib has Equiv.Perm.cycleType and basic symmetric-group structure plus Combinatorics.YoungDiagram, but the irreducibility of Specht modules and the Frobenius-Young classification are not yet formalised.

[object Promise]

Advanced results [Master]

Murnaghan-Nakayama rule (Murnaghan 1937; Nakayama 1940). The character ${\chi }^{\lambda }$ at a permutation of cycle type $\mu$ is computed recursively by stripping border strips (rim hooks) of length ${\mu }_1$ from the Young diagram of $\lambda$:

$${\chi }^{\lambda }(\mu )=\sum _{\xi }(-1{)}^{\mathrm{ht}(\xi )}{\chi }^{\lambda \setminus \xi }(\mu \setminus {\mu }_1),$$

where the sum is over border strips $\xi$ of length ${\mu }_1$ in $\lambda$, and $\mathrm{ht}(\xi )$ is the height of the strip (number of rows minus one). This reduces character evaluation to a tractable combinatorial walk, and is the standard computational tool for $S_n$ characters.

Frobenius character formula. Assemble the partitions and characters into the characteristic map $\mathrm{ch}:R(S_n)\to {\Lambda }_n$ (representation ring to symmetric polynomials of degree $n$):

$$\mathrm{ch}(V^{\lambda })=s_{\lambda },$$

the Schur function indexed by $\lambda$. The characteristic map is a ring isomorphism ${⨁}_{n}R(S_n)\stackrel{\sim }{\to }\Lambda$, transporting the rep theory of all symmetric groups simultaneously into the algebra of symmetric functions. Tensor product of representations corresponds to the Littlewood-Richardson product of Schur functions, and induction-restriction along $S_n\times S_m\hookrightarrow S_{n+m}$ corresponds to the comultiplication on $\Lambda$.

Robinson-Schensted-Knuth correspondence (Robinson 1938, Schensted 1961, Knuth 1970). A bijection

$$S_n\stackrel{1:1}{\leftrightarrow }\underset{\lambda ⊢n}{⨆}\mathrm{SYT}(\lambda )\times \mathrm{SYT}(\lambda ),$$

between permutations of $n$ and pairs of standard Young tableaux of the same shape. Counting $|\mathrm{SYT}(\lambda )|=\dim V^{\lambda }$ and squaring recovers $n!={\sum }_{\lambda }(\dim V^{\lambda }{)}^2$. The RSK correspondence is one of the most fertile bijections in modern combinatorics, with applications to longest-increasing subsequences (Ulam's problem; Vershik-Kerov-Logan-Shepp asymptotic), random matrices (Tracy-Widom), and crystal bases.

Schur-Weyl duality and beyond. The symmetric group representations are the centralisers of ${\mathrm{GL}}_d$ on $V^{\otimes n}$. Generalisations:

• Brauer algebra (Brauer 1937): centraliser of $\mathrm{O}(V)$ or $\mathrm{Sp}(V)$ on $V^{\otimes n}$, replacing partitions with Brauer diagrams.
• Hecke algebra $H_n(q)$ (Iwahori 1964): $q$-deformation of $\mathbb{C}[S_n]$, classifies ${\mathrm{GL}}_n({\mathbb{F}}_q)$-representations of unipotent type, and connects to Kazhdan-Lusztig polynomials.
• Cyclotomic Hecke algebras / cellular algebras (Graham-Lehrer 1996): vast generalisation framing all of these as cellular categories.

Symmetric functions and integrable systems. The ring $\Lambda$ of symmetric functions carries multiple distinguished bases (monomial $m_{\lambda }$, elementary $e_{\lambda }$, complete $h_{\lambda }$, power-sum $p_{\lambda }$, Schur $s_{\lambda }$, Hall-Littlewood, Macdonald). Macdonald's $(q,t)$-symmetric functions interpolate between Schur ($q=t$), Hall-Littlewood ($q=0$), and Jack polynomials, and connect to integrable systems, double affine Hecke algebras, and the Calogero-Sutherland model.

Categorification and crystals. The ring $\Lambda$ is the Grothendieck ring of a categorical structure (Heisenberg category, Khovanov 2010), and Schur functions appear as classes of irreducibles. Crystal bases (Kashiwara) provide combinatorial skeletons of representations; for $S_n$, RSK is the crystal-theoretic statement.

Synthesis. This construction generalises the pattern fixed in 07.01.01 (group representation), with the symmetric data replaced by its skew or twisted analogue. Read in the opposite direction, the construction is dual to the metric story: complements and orthogonality are taken with respect to the bilinear datum of this unit, not a metric, and the resulting category of subobjects is the one the rest of the strand classifies. The central insight is that this datum identifies algebra with geometry: functions become vector fields, subspaces become quotients, and invariants become cohomology classes — and that identification is the engine driving every theorem downstream.

Full proof set [Master]

The full Frobenius-Young classification proof — counting irreducibles via conjugacy classes, constructing $V^{\lambda }$ via Young symmetrisers, verifying irreducibility through the von Neumann lemma, and showing distinctness by dominance-order arguments — is given in Sagan The Symmetric Group §2.1-§2.5 (about 30 pages of careful exposition), Fulton-Harris §4 (briefer; emphasises the symmetric-function angle), and Fulton Young Tableaux §7 (most combinatorial). The hook length formula has multiple proofs: original Frame-Robinson-Thrall via determinantal manipulation; Greene-Nijenhuis-Wilf 1979 probabilistic proof using a random hook walk; Novelli-Pak-Stoyanovskii 1997 fully bijective proof. The Frobenius character formula derivation from the Vandermonde-power-sum determinant is Macdonald Symmetric Functions and Hall Polynomials I.7. The Murnaghan-Nakayama recursion is proven via the Frobenius formula by extracting coefficients of $\Delta \cdot p_{\mu }$.

Connections [Master]

• 07.01.01 gives the underlying notion of group representation; the symmetric-group case is the quintessential finite example. 07.01.02 (Schur's lemma) is invoked at the irreducibility step in the Young symmetriser proof. 07.05.02 (Young diagrams and tableaux) packages the combinatorial scaffolding and is the visual core of every concrete computation. 07.05.03 (Specht modules) extends the construction to arbitrary characteristic, where the modular representation theory of $S_n$ replaces the semisimple complex picture. The Schur-Weyl bridge connects to the highest-weight classification of ${\mathrm{GL}}_d$ representations 07.03.01 and through it to the Cartan-Weyl classification 07.04.01. The Frobenius character formula sits in the ring of symmetric functions, which appears in Hodge theory 04.09.01 (cohomology of Grassmannians has a Schur-polynomial basis) and Schubert calculus.

Historical & philosophical context [Master]

Ferdinand Georg Frobenius created character theory of finite groups in 1896, and his 1900 paper Über die Charaktere der symmetrischen Gruppe (in Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften zu Berlin) gave the explicit determinantal formula for ${\chi }^{\lambda }(\mu )$ in terms of partitions. Frobenius's calculation was a tour de force of formal power-series manipulation: he evaluated character sums by extracting coefficients in products of Vandermonde and power-sum polynomials, and recognised that the coefficients organise themselves by the dominance order on partitions.

Alfred Young (1873-1940) approached the same classification from the opposite direction. An English mathematician who took holy orders in 1908 and served as rector of Birdbrook in Essex, Young pursued mathematics seriously throughout his parish work, publishing a nine-paper series On Quantitative Substitutional Analysis in Proceedings of the London Mathematical Society spanning 1900, 1902, 1928, 1929, 1930, 1931, 1932, 1933, and 1934. The first paper introduced what are now called Young diagrams and Young tableaux; later papers built the Young symmetrisers $c_{\lambda }\in \mathbb{C}[S_n]$ and verified that $\mathbb{C}[S_n]\cdot c_{\lambda }$ realises the irreducible $V^{\lambda }$ concretely. Young's combinatorial constructions made the abstract characters of Frobenius into explicit projection operators that can be applied to vectors in tensor spaces.

The synthesis of the two pictures came over the following decades. Issai Schur's 1901 dissertation and 1927 paper introduced Schur-Weyl duality, identifying the $S_n$-irreducibles with the centralisers of ${\mathrm{GL}}_d$ on tensor space. Hermann Weyl's 1939 The Classical Groups unified Young's tableau methods, Frobenius's character calculus, and the highest-weight theory of Lie groups into a single classification. Later refinements: Murnaghan and Nakayama (1937, 1940) gave the recursive border-strip rule for characters; Frame, Robinson, and Thrall (1954) found the hook length formula; Robinson (1938), Schensted (1961), and Knuth (1970) developed the RSK correspondence; James (1976) and James-Kerber (1981) systematised the modular representation theory of $S_n$ via Specht modules in arbitrary characteristic.

The principle that irreducible representations of $S_n$ are labelled by partitions of $n$ is one of the most concrete and most widely applied classification theorems in algebra, with applications from quantum mechanics (identical-particle statistics) to statistics (random matrices, longest-increasing subsequences) to algebraic geometry (cohomology of Grassmannians, Schubert calculus). The combinatorics of partitions, tableaux, and symmetric functions has grown into an independent subfield with its own monographs (Macdonald, Stanley) and conferences. ^{[Frobenius 1900; Young 1900-1933]}

Bibliography [Master]

• Frobenius, Über die Charaktere der symmetrischen Gruppe, Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften zu Berlin (1900).
• Young, On Quantitative Substitutional Analysis I-IX, Proceedings of the London Mathematical Society (1900, 1902, 1928, 1929, 1930, 1931, 1932, 1933, 1934).
• Schur, Über eine Klasse von Matrizen, die sich einer gegebenen Matrix zuordnen lassen (dissertation, 1901); Über die rationalen Darstellungen der allgemeinen linearen Gruppe (1927).
• Weyl, The Classical Groups (Princeton, 1939).
• Frame-Robinson-Thrall, "The hook graphs of the symmetric group," Canadian Journal of Mathematics (1954).
• Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions (Springer GTM 203, 2nd ed.).
• Fulton-Harris, Representation Theory: A First Course (Springer GTM 129) §4-§6.
• Fulton, Young Tableaux: With Applications to Representation Theory and Geometry (LMS Student Texts, 1997).
• James, The Representation Theory of the Symmetric Groups (LNM 682, 1978).
• James-Kerber, The Representation Theory of the Symmetric Group (Encyclopedia of Mathematics, 1981).
• Macdonald, Symmetric Functions and Hall Polynomials (2nd ed., Oxford 1995).
• Stanley, Enumerative Combinatorics Vol. II Ch. 7 (RSK and symmetric functions).