Symmetric Group · aiwiki.page

The symmetric group on a set $X$ , denoted $\operatorname{Sym}(X)$ , is the group of all bijections from $X$ to itself, with function composition as the group operation. These bijections are called permutations. For a finite set of $n$ elements, the symmetric group is usually written $S_n$ . It is a fundamental object in group theory: its elements describe every possible rearrangement of $n$ distinct objects. (ocw.mit.edu)

Definition and basic properties

For $X=\{1,2,\ldots,n\}$ ,

S_n=\{\sigma:X\to X\mid \sigma\text{ is bijective}\}.

Using the standard right-to-left convention,

(\sigma\tau)(i)=\sigma(\tau(i)).

Thus the rightmost permutation acts first. Composition is associative, the identity permutation fixes every element, and each permutation has an inverse that reverses its mapping. These properties make $S_n$ a group. (ocw.mit.edu)

There are $n$ choices for the image of the first element, $n-1$ for the second, and so on. Consequently,

|S_n|=n!,

where $n!$ is the factorial of $n$ . Relabeling an $n$ -element set gives an isomorphic symmetric group, so the abstract group depends on the number of elements rather than their names. $S_0$ and $S_1$ are trivial groups; $S_2$ has two elements. (ocw.mit.edu)

A symmetric group contains all permutations of its underlying set. A permutation group, by contrast, may be any subgroup of that full group. The permutations preserving additional structure need not constitute the whole symmetric group. (math.mit.edu)

Notation and cycle decomposition

Two-line notation records the images explicitly:

\sigma= \begin{pmatrix} 1&2&3&4&5\\ 3&1&2&5&4 \end{pmatrix}.

The same permutation has cycle notation

\sigma=(1\,3\,2)(4\,5).

The first cycle sends $1$ to $3$ , $3$ to $2$ , and $2$ back to $1$ ; the second exchanges $4$ and $5$ . Elements absent from the notation are understood to be fixed. (math.mit.edu)

Every permutation of a finite set decomposes into disjoint cycles. The decomposition is unique up to reordering the cycles and cyclically rotating the notation within each cycle. Disjoint cycles commute. The inverse is obtained by reversing each cycle. (bookdown.org)

The order of a permutation is the smallest positive integer $m$ for which $\sigma^m$ is the identity. If its disjoint cycles have lengths $\ell_1,\ldots,\ell_r$ , then

\operatorname{ord}(\sigma) =\operatorname{lcm}(\ell_1,\ldots,\ell_r),

their least common multiple. The permutation in the example therefore has order $6$ . (bookdown.org)

A transposition exchanges two elements and fixes all others. Every cycle, and hence every permutation, is a product of transpositions:

(a_1\,a_2\,\cdots\,a_k) =(a_1\,a_k)(a_1\,a_{k-1})\cdots(a_1\,a_2).

These factorizations are generally not unique. (kconrad.math.uconn.edu)

Parity and the alternating group

Although transposition factorizations are not unique, the parity of their length is. A permutation is even if it is a product of an even number of transpositions and odd otherwise. Its sign is

\operatorname{sgn}(\sigma)= \begin{cases} +1,&\sigma\text{ even},\\ -1,&\sigma\text{ odd}. \end{cases}

The sign is a group homomorphism:

\operatorname{sgn}(\sigma\tau) =\operatorname{sgn}(\sigma)\operatorname{sgn}(\tau).

A $k$ -cycle has sign $(-1)^{k-1}$ . Equivalently, if $c(\sigma)$ counts all disjoint cycles, including fixed points, then $\operatorname{sgn}(\sigma)=(-1)^{n-c(\sigma)}.$ (kconrad.math.uconn.edu)

The even permutations form the alternating group $A_n$ , the kernel of the sign homomorphism. For $n\geq2$ , it is a normal subgroup of index $2$ , with

|A_n|=\frac{n!}{2}.

Thus exactly half the permutations are even and half are odd. (kconrad.math.uconn.edu)

Generators and relations

The adjacent transpositions

s_i=(i\,\,i+1),\qquad 1\leq i<n,

generate $S_n$ . They give the presentation

s_i^2=e,\qquad s_i s_j=s_j s_i\quad(|i-j|>1),\qquad s_i s_{i+1}s_i=s_{i+1}s_i s_{i+1}.

These relations express cancellation of a repeated swap, commutation of nonoverlapping swaps, and the braid relation for neighboring swaps. With these generators, $S_n$ is the Coxeter group of type $A_{n-1}$ . (jmilne.org)

For $n\geq3$ , $S_n$ is not an abelian group. For example,

(1\,2)(2\,3)=(1\,2\,3), \qquad (2\,3)(1\,2)=(1\,3\,2),

so changing the order of two operations can change the result. (bookdown.org)

Conjugacy and structural results

Conjugating a cycle simply relabels its entries:

\tau(a_1\,\ldots\,a_k)\tau^{-1} =(\tau(a_1)\,\ldots\,\tau(a_k)).

Two elements of $S_n$ belong to the same conjugacy class exactly when they have the same cycle lengths. Consequently, conjugacy classes are indexed by integer partitions of $n$ . If there are $m_i$ cycles of length $i$ , the class size is $\frac{n!}{\prod_{i=1}^{n}i^{m_i}m_i!}.$ (tomaszlukowski.github.io)

For $n\geq5$ , $A_n$ is a nonabelian simple group, and the only normal subgroups of $S_n$ are $\{e\}$ , $A_n$ , and $S_n$ . In particular, $S_n$ itself is not simple for these values of $n$ . The group $S_4$ has an additional normal subgroup: $\{e,(1\,2)(3\,4),(1\,3)(2\,4),(1\,4)(2\,3)\}.$ (jmilne.org)

Another exceptional case is $S_6$ . Every automorphism of $S_n$ is inner—given by conjugation by a group element—unless $n=6$ . The group $S_6$ has an outer automorphism; its outer automorphism group has order $2$ . (people.math.harvard.edu)

Group actions and Cayley’s theorem

A group action of $G$ on $X$ is equivalently a homomorphism

\rho:G\longrightarrow\operatorname{Sym}(X).

Each group element acts as a permutation, and the homomorphism condition ensures compatibility with multiplication. The action is faithful precisely when $\rho$ is injective. (math.mit.edu)

Cayley’s theorem states that every group is isomorphic to a subgroup of a symmetric group. The construction lets $G$ act on its own underlying set by left multiplication:

\rho(g)(x)=gx.

This action is faithful because the image of the identity element under $\rho(g)$ is $g$ . A finite group of order $m$ therefore embeds in $S_m$ , though a faithful action on a smaller set may also exist. The theorem does not say that every group is itself a full symmetric group. (math.mit.edu)

Representation theory

In representation theory, permutations are realized as invertible linear operators. The natural permutation representation sends basis vectors according to

P_\sigma e_i=e_{\sigma(i)}.

Its matrices have one entry $1$ in every row and column and zero elsewhere. These matrices satisfy

P_{\sigma\tau}=P_\sigma P_\tau, \qquad \det P_\sigma=\operatorname{sgn}(\sigma),

connecting permutation parity with the determinant. (kconrad.math.uconn.edu)

Over the complex numbers, irreducible representations of $S_n$ are indexed by partitions $\lambda$ of $n$ , drawn as Young diagrams. Their dimensions are given by the hook-length formula:

\dim V_\lambda =\frac{n!}{\prod_{b\in\lambda}h(b)},

where $h(b)$ counts the box $b$ , the boxes to its right, and those below it. (tomaszlukowski.github.io)

Algebraic applications

In Galois theory, automorphisms of the splitting field of a separable polynomial permute its roots faithfully, identifying its Galois group with a subgroup of $S_n$ . Over a characteristic-zero field, the polynomial with algebraically independent coefficients has Galois group $S_n$ . Since $S_n$ is a solvable group exactly when $n\leq4$ , this explains why no general formula using radicals exists for degree $5$ or higher. Particular higher-degree equations can nevertheless be solvable by radicals. (jmilne.org)

The symmetric group also acts by permuting variables in a polynomial ring. Its invariant polynomials are the symmetric polynomials. Every symmetric polynomial over a commutative coefficient ring can be expressed uniquely as a polynomial in the elementary symmetric polynomials. This connects permutations of roots with the coefficients of an equation. (jmilne.org)

Infinite sets

The definition of $\operatorname{Sym}(X)$ also applies when $X$ is infinite. It must be distinguished from the finitary symmetric group, whose elements move only finitely many points. For a countably infinite set, the finitary group is the union of the finite symmetric groups obtained by successively allowing more points to move. It is a proper subgroup of the full symmetric group. (jmilne.org)

Historical development

Permutation groups developed from the study of algebraic equations. In 1770, Joseph-Louis Lagrange examined how expressions in polynomial roots changed under permutations. Évariste Galois subsequently connected solvability of equations with the structure of groups of root permutations. Augustin-Louis Cauchy developed permutation theory systematically, including cycle notation and the relationship between conjugacy and cycle structure. Arthur Cayley’s work in 1854 helped establish the abstract group concept and the realization of groups through permutations. (mathshistory.st-andrews.ac.uk)

References

Algebra I Student Notesocw.mit.edu
600: Lecture 1 — Permutations and combinations, Pascal's triangle, learning to countmath.mit.edu
5 Symmetric Groups and Cyclesbookdown.org
The Sign of a Permutationkconrad.math.uconn.edu
Group Theoryjmilne.org
Classification of representations for symmetric groupstomaszlukowski.github.io
Informal lecture notespeople.math.harvard.edu
The Symmetric Groupmath.mit.edu
Fields and Galois Theoryjmilne.org
The development of group theorymathshistory.st-andrews.ac.uk