The **symmetric group on n letters**, written S_{n}, has as its elements the n! distinct bijections from an n-element set (often taken to be {1...n}) to itself, with composition as the binary operation.^{1} Each element of S_{n} is called a **permutation** for obvious reasons.

# 1. Why it's a group

To be a group, S_{n} requires closure (trivial), associativity (follows from associativity of function composition), an identity (the identity permutation 1→1, 2→2, ..., n→n) and inverses (follows from the fact that any bijection has an inverse). So S_{n} is a group.

# 2. Cycle notation

For compactness, permutations are often written in **cycle notation**: this is a sequence of cycles grouped by parentheses, where the interpretation of (x_{1}x_{2}...x_{k}) is that the permutation maps x_{1} to x_{2}, x_{2} to x_{3}, and so on, with x_{n} mapping to x_{1}. Cycles that consist of a single element only are omitted. So for example the permutation that shifts each element of S_{5} up by one would be written (12345) (or (34512) or something---there is no requirement that a particular element appear first in the cycle) and the permutation that swaps 2 with 4 and 1 with 5 while leaving 3 alone would be written as (24)(15).

To obtain the cycle notation for a permutation, pick any element of the set and follow its **orbit**---the elements it is sent to by applying the permutation over and over again---until you get back to the original element. This gives one of the cycles of the permutation. For example, in the permutation { 1→2, 2→4, 3→5, 4→1, 5→3 } the orbit of 1 is 1, 2, 4, 1, ... and the corresponding cycle would be written as (124). We always get a cycle that returns to the first element because (a) the set is finite, so we must eventually repeat an element in the orbit, and (b) if we don't return to the initial element, i.e. we get an orbit of the form x_{0}x_{1}...x_{i-1}x_{i}...x_{j}x_{i} where x_{i} is the first repeated element, then the alleged permutation isn't injective, a contradiction. Continuing with our example, there is a second cycle starting a 3 consisting of 3 and 5, so the whole permutation could be written as (124)(35).

Multiplying permutations consists of tracking the individual elements through the various cycles. So for example, in S_{5}, (24)(15) * (12345) = (14)(23). To see this, follow each number through the two permutations: 1->2->4, 4->5->1, 2->3->3, 3->4->2, and 5->1->5. The cyclic decomposition of a permutation is a form of factoring: the permutation is obtained by multiplying the individual cycles together. Note that since the cycles in the cycle decomposition don't move any common elements, the order doesn't matter: in general this is *not* true.

# 3. The role of the symmetric group

The reason the symmetric groups are important is that they embed all other finite groups. Specifically, we have

- Theorem
Let G be a group with n elements. Then G is isomorphic to a subgroup of S

_{n}.- Proof
Let a

_{1}, a_{2}, ..., a_{n}be the elements of G. For each a in G define a function f_{a}:G→G by f_{a}(b) = ab. Each such f_{a}is a bijection (f_{a^-1^ is it inverse), and the set of such functions is closed under composition (since f}a_{(f}b_{(c)) = abc = f}ab_{(c)); thus it's a subgroup of the group of all bijections from the elements of G to the elements of G, which is isomorphic to S}n_{ (relabel a}1_{...a}n,, as 1...n).

For example, the cyclic group ℤ_{m} is isomorphic to the subgroup of S_{m} generated by (1 2 3 ... m). Many symmetry groups can easily be shown to be isomorphic to subgroups of S_{n} for some n by labeling the vertices of the geometrical figure and describing group operations in terms of how they permute these vertices.

(See BiggsBook §21.5 for more on this.)

# 4. Permutation types, conjugacy classes, and automorphisms

An automorphism of a group is an isomorphism between the group and itself. Automorphisms of S_{n} are obtained by **conjugating** by some group element σ; this is the operation that sends τ to στσ^{-1}. Intuitively, conjugation corresponds to relabeling the elements being permuted: σ^{-1} undoes the relabeling, τ permutes the original elements, and σ restores the relabeling. It is easy to see that conjugation by σ is an isomorphism: its inverse is conjugation by σ^{-1} (since σ^{-1}(στσ^{-1})σ = τ) and it preserves multiplication: (στσ^{-1})(σρσ^{-1})=στ(σ^{-1}σ)ρσ^{-1}=σ(τρ)σ^{-1}.

Conjugation can be used to define an equivalence relation on permutations: two permutations τ and ρ are **conjugate** if there is some σ such that ρ = στσ^{-1}. The simplest way to detect if two permutations are conjugate is to look at their cycle decompositions: τ and ρ are conjugate if and only if they have the same number of cycles of each length (see BiggsBook Theorem 12.5). The number of cycles of each length is summarized as the **type** of a permutation, which is writen as a sequence of cycle lengths, possibly with counts as exponents, in brackets. For example, the permutation (124)(35) on S_{5} has type [23], while the permutation (12)(34) has type [1 2^{2}] (the 1 is for the omitted (5) cycle of length 1). It's not at all clear what this is useful for, but BiggsBook makes a big deal about it in §12.5.

# 5. Odd and even permutations

There is a homomorphism from S_{n} to ℤ_{2} that classifies all permutations as **odd** (those mapped to 1) or **even** (those mapped to 0). The essential idea is that a permutation is odd or even depending on whether the number of cycles in its cycle decomposition (including the length-1 cycles that we usually don't bother to write down) is odd or even, except that for odd n the correspondence is reversed, as otherwise the identity permutation (with an odd number of cycles) wouldn't map to the identity element 0 of ℤ_{2}. The surprising fact is that oddness and evenness adds as in ℤ_{2} when permutations are multiplied. The oddness or evenness of a permutation σ is often encoded as -1 for odd and 1 for even, and is called the **sign** of the permutation, written sgn(σ) and equal to (-1)^{k}(-1)^{n} where k is the number of cycles and n is the size of the underlying set. The reason for this encoding is that we can map multiplication of permutations directly to multiplication of integers: sgn(στ) = sgn(σ)sgn(τ). This avoids dealing with ℤ_{2} directly, which was a popular dodge back in the early days of group theory when this notation was invented.

Note that we still haven't proved that sgn is indeed a homomorphism. The easiest way to do this is to reduce all permutations to products of a smaller basis of odd permutations, and show that if σ = τ_{1}τ_{2}...τ_{k} where each τ_{i} is in the basis, then sgn(σ) = ∏_{i} sgn(τ_{i}). The basis we will use consists of all **transpositions**, permutations of type [1^{n-2}2], or alternatively permutations that exchange two elements with each other while leaving the others untouched. Since each transposition consists of exactly n-1 cycles, it has sign (-1)^{n-1}(-1)^{n} = -1. If we can show that sgn(σ) = ∏_{i} sgn(τ_{i}), we get an alternate (and more standard) definition of sgn(σ) as the parity number of transpositions needed to generate σ, which we can then use to argue that sgn(στ) = sgn(σ)sgn(τ) since we can express στ as just the product of the two sequences of transpositions that generate σ and τ.

First we must show that any permutation σ can be written as a product of transpositions. There are a couple of ways to prove this. A computer programmer will probably swap the correct value to position 1, then the correct value to position 2, and so on. This works, but it is not quite as clean a proof as the observation that any cycle (x_{1} x_{2} ... x_{k}) = (x_{1} x_{k}) (x_{1} x_{k-1}) (x_{1} x_{k-2}) ... (x_{1} x_{3}) (x_{1} x_{2}), in which each x_{i} for i < k is first swapped into position x_{1} and then back into position x_{i+1} (remember that permutations are applied right to left). Since any permutation is a product of cycles, and each cycle can be represented as a product of transpositions, we get that any permutation is a product of transpositions.

Now, we can do transpositions all afternoon, and after a while we won't be generating any more permutations. So in general the same permutation may arise as the product of different sequences of transpositions---and even sequences of different length. But what we will show is that the number of transpositions in each sequence generating σ is always odd or even depending on the sign of σ. The proof of this is to show that while a transposition may have unpredictable effects on the number of cycles in σ, it always increases or decreases this number by exactly 1. So the parity of the number of cycles in the product of an even number of transpositions is always the same, and since σ has a unique cycle decomposition (up to reordering the cycles), the number of cycles in the decomposition determines whether there are an even or an odd number of transpositions in any decomposition into transpositions.

- Lemma 1
(x y)(a

_{1}... a_{k}x b_{1}... b_{m}y) = (a_{1}... a_{k}y) (b_{1}... b_{m}x).- Proof
Walk the elements through both cycles on the LHS. Each a

_{i}except a_{k}is still sent to a_{i+1}, since a_{i+1}is not affected by (x y). The element a_{k}is sent first to x and then y. The element y is sent to a_{1}by the right-hand cycle and then is unaffected by (x y). This gives us our first cycle on the RHS. A similar argument shows that (b_{1}... b_{m}x) forms the second cycle.- Corollary 2
(x y)(a

_{1}... a_{k}y) (b_{1}... b_{m}x) = (a_{1}... a_{k}x b_{1}... b_{m}y)- Proof
Multiply both sides of the equation in the lemma by (x y); since (x y)

^{2}= e this gives the equation in the corollary (after swapping the LHS with the RHS).

So now we have:

- Lemma 3
- If σ is a permutation with k cycles and τ a transposition, then τσ has either k-1 or k+1 cycles.
- Proof
- Either τ swaps two elements of the same cycle in σ, Lemma 1 applies, and τσ has k+1 cycles, or τ swaps two elements of different cycles, Corollary 2 applies, and τσ has k-1 cycles.

which gives:

- Corollary 4
- If σ is a permutation and τ a transposition, then sgn(τσ) = sgn(τ)sgn(σ) = -sgn(σ).
- Proof
(-1)

^{(k-1)}= (-1)^{k+1}= -(-(-1)^{k}).

and finally:

- Theorem
- For any permutations σ and ρ, sgn(σρ) = sgn(σ)sgn(ρ).
- Proof
- Rewrite σ as a product of transpositions, and then apply Corollary 4 once for each transposition in the expansion of σ.

One consequence of the classification into odd and even permutations is that the even permutations form a subgroup of S_{n}, called the **alternating subgroup** A_{n}: the inverse of an even permutation is even (expand it into transpositions and then invert the product) and the product of two even permutations is even. The size of A_{n} is exactly n!/2, or half the size of S_{n}. We can prove this by observing that multiplication by any transposition τ gives a bijection between the even permutations and the odd permutations, an observation that is a special case of the proof of Lagrange's Theorem (see GroupTheory or BiggsBook §20.8).

Sometimes reversed composition, so that πρ means do π then ρ rather than the usual do ρ then π; watch out for different authors handling this in different ways. (1)