Unit 3: Symmetric Groups, Alternating Groups & Group Actions

1. The Symmetric Group $S_n$

Let $X = \{1, 2, \dots, n\}$ be a finite set of $n$ symbols.

Definition 3.1 (Permutation & Symmetric Group): A permutation of $X$ is a bijection $\sigma: X \to X$. The set of all permutations of $X$, equipped with functional composition $\circ$, forms the Symmetric Group of Degree $n$, denoted by $S_n$. The order of $S_n$ is:

Two-Line Notation:

A permutation $\sigma \in S_n$ is traditionally displayed as:

2. Cycle Notation and Disjoint Cycles

Definition 3.2 ($k$-Cycle): A permutation $\sigma \in S_n$ is called a cycle of length $k$ (or $k$-cycle), denoted by $(a_1 \; a_2 \; \dots \; a_k)$, if:

and $\sigma(x) = x$ for all $x \notin \{a_1, a_2, \dots, a_k\}$. A 2-cycle $(a \; b)$ is called a transposition.

Definition 3.3 (Disjoint Cycles):

Two cycles $(a_1 \; \dots \; a_k)$ and $(b_1 \; \dots \; b_m)$ are disjoint if they have no elements in common:

Proposition 3.1 (Commutativity of Disjoint Cycles):

Disjoint cycles in $S_n$ commute:

Proof: If $x$ is moved by $\sigma$, it is fixed by $\tau$, so $\tau(\sigma(x)) = \sigma(x) = \sigma(\tau(x))$. If $x$ is fixed by both, both sides leave $x$ unchanged. $\blacksquare$

3. The Disjoint Cycle Decomposition Theorem

Theorem 3.1 (Cycle Decomposition Theorem): Every permutation $\sigma \in S_n$ can be written uniquely (up to the order of factors) as a product of pairwise disjoint cycles.

Theorem 3.2 (Order of a Permutation):

The order of a permutation $\sigma \in S_n$ written in disjoint cycle form $\sigma = c_1 c_2 \dots c_r$ is the least common multiple of the lengths of its cycles:

1. Transposition Factorization

Any $k$-cycle can be expressed as a product of 2-cycles (transpositions):

Notice that a $k$-cycle decomposes into $(k - 1)$ transpositions.

Corollary 3.1: Every permutation $\sigma \in S_n$ can be expressed as a product of transpositions. (The symmetric group $S_n$ is generated by transpositions!)

2. The Parity Theorem & The Sign Function $\text{sgn}(\sigma)$

While the decomposition into transpositions is not unique (e.g. $(1 \; 2) = (1 \; 2)(1 \; 3)(1 \; 3)$), the parity of the number of transpositions is invariant!

Theorem 3.3 (Parity Invariance Theorem): If a permutation $\sigma \in S_n$ can be written as a product of $r$ transpositions and also as a product of $s$ transpositions:

then $r$ and $s$ have the same parity:

Definition 3.4 (Even and Odd Permutations):

• A permutation $\sigma \in S_n$ is Even if it can be written as a product of an even number of transpositions.
• A permutation $\sigma \in S_n$ is Odd if it can be written as a product of an odd number of transpositions.

The Sign (Signature) Homomorphism $\text{sgn}: S_n \to (\{+1, -1\}, \cdot)$ is:

satisfying $\text{sgn}(\sigma \tau) = \text{sgn}(\sigma) \cdot \text{sgn}(\tau)$.

3. The Alternating Group $A_n$

Definition 3.5 (Alternating Group): The set of all even permutations of $S_n$ forms a normal subgroup called the Alternating Group of Degree $n$, denoted by $A_n$:

Theorem 3.4 (Order of $A_n$):

For $n \ge 2$:

Proof: The map $\text{sgn}: S_n \to \{\pm 1\}$ is a surjective group homomorphism. By the First Isomorphism Theorem:

Theorem 3.5 (Simplicity of $A_n$): The alternating group $A_n$ is a simple group (contains no non-trivial proper normal subgroups) for all $n \ge 5$. (This theorem is the Galois-theoretic cornerstone establishing the insolvability of the quintic by radicals!)

1. Geometric Symmetries of Regular Polygons

The Dihedral Group $D_{2n}$ (also denoted $D_n$) is the group of all rigid planar symmetries (rotations and reflections) of a regular $n$-gon. The group has order:

consisting of:

• $n$ planar rotations: $R_k = \frac{2\pi k}{n}$ for $k = 0, 1, \dots, n-1$.
• $n$ planar reflections across symmetry axes: $s, sr, sr^2, \dots, sr^{n-1}$.

2. Group Presentation of $D_{2n}$

The group $D_{2n}$ is completely generated by two elements:

• $r$: Counterclockwise rotation by $2\pi/n$ (order $n$).
• $s$: Reflection across an axis passing through a vertex (order 2).

Theorem 3.6 (Presentation of $D_{2n}$):

The fundamental relation $s r = r^{-1} s = r^{n-1} s$ allows any word in $\{r, s\}$ to be reduced into canonical form:

1. Formal Definition of a Group Action

Definition 3.6 (Group Action): Let $G$ be a group and $X$ a non-empty set. A group action of $G$ on $X$ is a map $\cdot: G \times X \to X$ satisfying:

1. Identity: $e \cdot x = x, \quad \forall x \in X$.
2. Compatibility / Associativity: $(g_1 g_2) \cdot x = g_1 \cdot (g_2 \cdot x), \quad \forall g_1, g_2 \in G, \; x \in X$.

We write $G \curvearrowright X$ to denote $G$ acting on $X$.

2. Orbits and Stabilizers

Let $G \curvearrowright X$ and $x \in X$.

Definition 3.7 (Orbit):

The orbit of $x$, denoted by $\text{Orb}(x)$ or $G \cdot x$, is the set of all elements in $X$ to which $x$ can be moved by elements of $G$:

The orbits form an equivalence partition of the set $X$: $X = \coprod \text{Orb}(x)$.

Definition 3.8 (Stabilizer / Isotropy Subgroup):

The stabilizer of $x$, denoted by $\text{Stab}(x)$ or $G_x$, is the set of elements in $G$ that fix $x$:

Proposition: $\text{Stab}(x)$ is a subgroup of $G$ for every $x \in X$.

3. The Orbit-Stabilizer Theorem

Theorem 3.7 (The Orbit-Stabilizer Theorem): Let $G$ be a finite group acting on a set $X$. For every $x \in X$:

Equivalently:

Complete Proof:

Let $H = \text{Stab}(x) \le G$. Let $G / H$ denote the set of left cosets $\{g H : g \in G\}$. Define the map $f: G / H \to \text{Orb}(x)$ by:

1. Well-Definedness and Injectivity:

This chain of equivalences proves that $f$ is both well-defined (left to right) and injective (right to left).

2. Surjectivity:

Any element in $\text{Orb}(x)$ has the form $y = g \cdot x = f(g H)$, so $f$ is surjective. Thus $f$ is a bijection between $G/H$ and $\text{Orb}(x)$. Therefore $|\text{Orb}(x)| = |G/H| = [G : H] = \frac{|G|}{|H|} = \frac{|G|}{|\text{Stab}(x)|}$. Multiplying by $|\text{Stab}(x)|$ yields $|G| = |\text{Orb}(x)| \cdot |\text{Stab}(x)|$. $\blacksquare$

4. Burnside's Lemma (Frobenius Counting Formula)

Let $X^g = \{ x \in X : g \cdot x = x \}$ denote the set of elements fixed by $g \in G$.

Theorem 3.8 (Burnside's Lemma / Cauchy-Frobenius Theorem): The number of distinct orbits $N$ of a finite group $G$ acting on a finite set $X$ is the average number of fixed points: