Permutation Groups and Symmetric Groups

Permutation groups form the historical and conceptual bedrock of group theory, providing concrete, finite models for abstract algebraic structures. Mastering them is essential not only for pure algebra but also for understanding symmetry in chemistry, cryptography, and combinatorics. At the heart of this study lies the symmetric group $S_n$, which consists of all possible rearrangements of $n$ distinct objects.

The Symmetric Group $S_n$ and Its Subgroups

Formally, for a finite set $X=\{1,2,...,n\}$, the symmetric group $S_n$ is the set of all bijective functions (permutations) from $X$ to itself, with the group operation being function composition. The order (number of elements) of $S_n$ is $n!$. Any subset of $S_n$ that itself forms a group under composition is called a permutation group. A fundamental theorem, Cayley's Theorem, states that every finite group is isomorphic to a permutation group, highlighting $S_n$'s universal role.

A permutation $\sigma$ is often written in two-line notation, but a more powerful notation is cycle notation. A cycle $(a_1,a_2,...,a_k)$ represents the permutation that sends $a_1$ to $a_2$, $a_2$ to $a_3$, ..., and $a_k$ back to $a_1$. Every permutation can be written uniquely as a product of disjoint cycles (cycles that share no common elements). For example, in $S_5$, the permutation mapping $1\to 3,2\to 5,3\to 1,4\to 4,5\to 2$ is written in cycle notation as $(13)(25)(4)$. Cycles of length one, like $(4)$, are often omitted, simplifying the notation to $(13)(25)$. The cycle structure of a permutation (the lengths of its disjoint cycles) is a crucial invariant.

Cycle Notation and Transposition Decompositions

While disjoint cycles are optimal for seeing structure, any permutation can also be decomposed into a product of transpositions. A transposition is a 2-cycle $(ij)$ that simply swaps two elements. Unlike disjoint cycle decomposition, transposition decomposition is not unique. However, a key invariant emerges: for a given permutation, the parity (evenness or oddness) of the number of transpositions in any decomposition is always the same.

A standard algorithm to find a transposition decomposition is to first write the permutation as a product of disjoint cycles, and then break each cycle into transpositions. A cycle of length $k$ can be expressed as a product of $k-1$ transpositions: $$(a_1,a_2,...,a_k)=(a_1,a_k)(a_1,a_{k-1})...(a_1,a_2).$$ Using our earlier example, $(13)(25)=(13)(25)$. Here, both cycles are already transpositions. The cycle $(1423)$ would decompose as $(13)(12)(14)$.

The Sign of a Permutation

The sign (or signature) of a permutation $\sigma$, denoted $\text{sgn}(\sigma )$, is a homomorphism from $S_n$ to the multiplicative group $\{+1,-1\}$. It is defined as $+1$ if $\sigma$ can be written as an even number of transpositions (an even permutation), and $-1$ if it can be written as an odd number of transpositions (an odd permutation).

An efficient way to compute the sign without finding a full transposition decomposition is via the cycle structure. A cycle of length $k$ has sign $(-1{)}^{k-1}$. Since the sign is multiplicative over disjoint cycles, the sign of a permutation is the product of the signs of its disjoint cycles. For $\sigma =(13)(25)$ in $S_5$, both cycles have length 2, so each has sign $(-1{)}^{2-1}=-1$. The product is $(-1)\ast (-1)=+1$, confirming $\sigma$ is an even permutation. This map, $\text{sgn}:S_n\to \{\pm 1\}$, is a surjective group homomorphism.

The Alternating Group $A_n$

The kernel of the sign homomorphism is a subgroup of $S_n$ consisting of all even permutations. This is the alternating group $A_n$. It is a normal subgroup of $S_n$ of index 2 and order $n!/2$. The group $A_n$ is simple (has no non-trivial proper normal subgroups) for all $n\ge 5$, a fact of profound importance.

The simplicity of $A_n$ for $n\ge 5$ is directly connected to the most famous application of permutation groups: the insolvability of the general quintic polynomial equation. In the context of Galois theory, a polynomial is solvable by radicals if and only if its Galois group is a solvable group. A solvable group is one derived from abelian groups via a series of extensions. The symmetric group $S_n$ is solvable only for $n\le 4$. Crucially, for $n\ge 5$, the simplicity of $A_n$ makes $S_n$ non-solvable. Since the general polynomial of degree $n$ has Galois group $S_n$, it follows that equations of degree 5 and higher are not solvable by a general algebraic formula (radicals).

Common Pitfalls

1. Misreading Cycle Notation as Composition Order: When multiplying (composing) cycles, the standard convention is right-to-left: $\sigma \tau$ means apply $\tau$ first, then $\sigma$. In the product $(123)(14)$, you first apply $(14)$ (sending 1 to 4), then $(123)$. Starting with 1: $(14)$ sends 1→4, then $(123)$ acts on 4 but does nothing, so final result: 1→4. This is different from the left-to-right reading.
2. Assuming Cycle Decomposition is Unique in All Ways: Disjoint cycle decomposition is unique up to the order of the cycles (which commute). However, a decomposition into transpositions is highly non-unique. For instance, the identity can be written as $(12)(12)$ or $(12)(34)(12)(34)$. The parity (even/odd count) is what's unique.
3. Confusing Even Permutation with Cycles of Even Length: A permutation is even if its sign is +1. A cycle is an even cycle if its length is even. An even-length cycle, like a 2-cycle or 4-cycle, is actually an odd permutation because $(-1{)}^{\text{even}-1}=-1$. This terminological inversion is a classic source of error.
4. Overlooking the Trivial Case in $A_n$: The alternating group $A_n$ is defined for $n\ge 2$. For $n=1$ and $n=2$, it is the trivial group. For $n=3$, $A_3$ is cyclic of order 3, and for $n=4$, $A_4$ is non-simple of order 12. The statement "$A_n$ is simple" holds only for $n\ge 5$.

Summary

• The symmetric group $S_n$, of order $n!$, is the group of all permutations of $n$ symbols, and its subgroups are permutation groups.
• Cycle notation expresses a permutation as a product of disjoint cycles, revealing its structure. Any permutation can also be decomposed into a product of transpositions (2-cycles).
• The sign of a permutation, $\text{sgn}(\sigma )=\pm 1$, classifies it as even or odd. It is efficiently computed as $(-1{)}^{n-k}$ where $k$ is the number of disjoint cycles (including 1-cycles).
• The set of all even permutations forms the alternating group $A_n$, a normal subgroup of $S_n$ of order $n!/2$. It is simple for $n\ge 5$.
• The solvability of the general polynomial equation of degree $n$ by radicals is governed by the structure of $S_n$ and $A_n$. The simplicity of $A_n$ for $n\ge 5$ implies the non-solvability of the general quintic and higher-degree equations.