Permutation Groups

Overview

Let $A$ be a nonempty set and $Sym (A)$ be the collection of all permutations of $A$ . Then $Sym (A)$ is a group under composition. We call $Sym (A)$ the symmetric group on $A$ under permutation multiplication. A subgroup of $Sym (A)$ is called a permutation group.

Let $B$ be the finite set ${1, 2, \dots, n}$ . The group of all permutations of $B$ is the symmetric group on $n$ letters, denoted by $S_{n}$ .

Group $S_{n}$ has $n!$ elements. It is abelian if and only if $n \leq 2$ .

Alternating Groups

The subgroup of $S_{n}$ consisting of the even permutations of $n$ letters is the alternating group $A_{n}$ on $n$ letters.

If $n = 1$ , the group has order $1$ . If $n \geq 2$ , the group has order $n! / 2$ .

Cayley's Theorem

Every group $G$ is isomorphic to a group of permutations.

Let $G$ be a group. The function $ϕ : G \to Sym (G)$ given by $ϕ (x) = λ_{x}$ , where $λ_{x} (a) = x a$ for all $a \in G$ , is called the left regular representation of $G$ . The function $μ : G \to Sym (G)$ given by $μ (x) = ρ_{x^{- 1}}$ , where $ρ_{x} (a x) = a x$ for all $a \in G$ , is called the right regular representation of $G$ .

Orbits

Let $A$ be a nonempty set and $σ \in Sym (A)$ . For a fixed $a \in A$ , the orbit of $a$ under $σ$ is the set

O_{a, σ} = {σ^{n} (a) ∣ n \in Z} .

The orbits of $σ$ are the equivalence classes in $A$ determined by the following equivalence relation $\sim$ :

\forall a, b \in A, [a \sim b ⟺ b = σ^{n} (a) for some n \in Z] .

Cycles

A permutation $σ \in S_{n}$ is a cycle if it has at most one orbit containing more than one element. The length of a cycle is the number of elements in its largest orbit. A cycle $μ$ is denoted using cyclic notation $μ = (a_{1}, a_{2}, \dots, a_{n})$ .

This notation indicates $μ$ maps $a_{1} \mapsto a_{2}$ , $a_{2} \mapsto a_{3}$ , $\dots$ , $a_{n} \mapsto a_{1}$ .

We say a product of cycles are disjoint if any element is moved by at most one of the cycles. Every permutation of a finite set is a product of disjoint cycles.

Transpositions

A transposition is a cycle of length $2$ . A permutation of a finite set is even or odd according to whether it can be expressed as a product of an even number of transpositions or the product of an odd number of transpositions, respectively. Every permutation in $S_{n}$ is either even or odd, but not both.

Cycles are often decomposed into transpositions in one of two ways:

Star Form: $(a_{1}, a_{2}, \dots, a_{n}) = (a_{1}, a_{n}) (a_{1}, a_{n - 1}) \dots (a_{1}, a_{2})$
Path Form: $(a_{1}, a_{2}, \dots, a_{n}) = (a_{1}, a_{2}) (a_{2}, a_{3}) \dots (a_{n - 1}, a_{n})$

A permutation of a finite set is even or odd according to whether it can be expressed as a product of an even or odd number of transpositions, respectively. No permutation can be expressed as both an even or odd number of transpositions.

Transitivity

If $A$ is a set, then a subgroup $H$ of $Sym (A)$ is transitive on $A$ if for each $a, b \in A$ , there exists $σ \in H$ such that $σ (a) = b$ .

Dihedral Groups

The $n$ th dihedral group, denoted $D_{n}$ , is the group of symmetries of the regular $n$ -gon.