Permutation Groups — Mathematics Knowledge System

Overview

A permutation group is a group whose elements are permutations (bijections) of a set, with the group operation being function composition. The symmetric group Sₙ, consisting of all permutations of n objects, is the archetypal example, and by Cayley's theorem every group can be realized as a permutation group.

Formal Definition

Definition

The symmetric group Sₙ is the set of all bijections σ: {1,...,n} → {1,...,n} under composition. A permutation group is any subgroup of some Sₙ:

|S_n| = n!

Order of the symmetric group on n elements

(\sigma \circ \tau)(i) = \sigma(\tau(i))

Composition of permutations

\sigma = (a_1\, a_2\, \dots\, a_k)

Cycle notation for a k-cycle

Properties

Cayley's theorem

\text{Every group } G \text{ is isomorphic to a subgroup of } \operatorname{Sym}(G).

Disjoint cycle decomposition

\text{Every permutation factors uniquely (up to order) into disjoint cycles.}

Even/odd parity

\text{Every permutation is a product of transpositions; the parity (even/odd) of the count is well-defined.}

Alternating group

A_n = \{\sigma \in S_n : \sigma \text{ is even}\} \trianglelefteq S_n, \quad |A_n| = n!/2 \ (n \geq 2).

Applications

Permutation groups model shuffle algorithms, sorting network analysis, and error-correcting codes based on symmetric group structure.

Worked Examples

Apply right-to-left: track where each element goes. Start with 1: (2 4) fixes 1, then (1 2 3) sends 1→2. So σ(1)=2.
$\sigma(1) = 2$
Track 2: (2 4) sends 2→4, then (1 2 3) fixes 4. So σ(2)=4.
$\sigma(2) = 4$
Track 4: (2 4) sends 4→2, then (1 2 3) sends 2→3. So σ(4)=3. Track 3: (2 4) fixes 3, (1 2 3) sends 3→1. So σ(3)=1.
$\sigma(4)=3,\ \sigma(3)=1$
This gives the single 4-cycle (1 2 4 3). A k-cycle decomposes into k-1 transpositions, so this is 3 transpositions: odd.
$(1\,2\,4\,3) = (1\,3)(1\,4)(1\,2)$

Answer: σ = (1 2 4 3), an odd permutation (3 transpositions), so σ ∈ S₄ \ A₄.

Practice Problems

Difficulty 5/10

What is the order of the permutation σ = (1 2 3)(4 5) in S₅, and why?

Summary

A permutation group is a subgroup of the symmetric group Sₙ, acting on a set of n objects under composition.
Cayley's theorem shows every abstract group embeds as a permutation group.
Permutations decompose uniquely into disjoint cycles; cycle lengths determine the element's order via lcm.
Parity (even/odd) is well-defined, splitting Sₙ into even permutations (the alternating group Aₙ) and odd ones.

References

WebsiteWikipedia — Permutation group