Permutation Representations

Core Idea

A permutation representation arises from a group action on a finite set X: each element g ∈ G permutes the elements of X, giving a homomorphism G → S_X. Linearizing this action over a field k produces a representation on k^X (the free vector space with basis X), where g acts by permuting basis vectors. The character of a permutation representation evaluated at g counts the number of fixed points of g on X. Permutation representations are the most concrete class of representations and provide a bridge between combinatorial group actions and linear algebra.

Explainer

A permutation representation starts with a group action G × X → X on a finite set X. Each g ∈ G defines a permutation σ_g: X → X, giving a homomorphism G → Sym(X). To get a linear representation, we linearize: form the free vector space k^X with basis {eₓ : x ∈ X} and define ρ(g)(eₓ) = e_{g·x}. The representing matrices are permutation matrices — exactly one 1 in each row and column — and the dimension is |X|. This is the most natural way to pass from combinatorial group theory to representation theory.

The character of a permutation representation has a beautiful combinatorial interpretation: χ(g) = |Fix(g)|, the number of elements of X fixed by g. This is because the trace of a permutation matrix counts the 1s on the diagonal, which correspond to basis vectors eₓ with g·x = x. This makes permutation characters far easier to compute than general characters — no eigenvalue calculations needed, just counting. Burnside's lemma, which counts orbits as the average number of fixed points, is a direct corollary: |X/G| = (1/|G|) Σ_{g∈G} χ(g) = ⟨χ, 1⟩, the inner product of the permutation character with the trivial character.

Every permutation representation contains the trivial subrepresentation spanned by Σ eₓ (since permutations preserve this sum). The augmentation subspace {Σ aₓeₓ : Σ aₓ = 0} is the complementary G-invariant subspace of codimension 1. For the natural action of Sₙ on {1, …, n}, this augmentation subspace is the standard representation of Sₙ, which is irreducible for n ≥ 2.

The connection to induced representations gives permutation representations their structural depth. If G acts transitively on X, then X ≅ G/H as a G-set, where H is the stabilizer of any point. The corresponding permutation representation is Ind_H^G(1_H), the induction of the trivial representation from H to G. This allows all tools of induced representations (Frobenius reciprocity, Mackey's formula) to be applied to permutation representations. Conversely, every induced representation of a 1-dimensional character is a generalized permutation representation, so the induction machinery is a direct generalization of the permutation construction.