[FrontPage] [TitleIndex] [WordIndex]

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

The symmetric group on n letters, written Sn, 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 Sn is called a permutation for obvious reasons.

1. Why it's a group

To be a group, Sn 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 Sn 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 (x1x2...xk) is that the permutation maps x1 to x2, x2 to x3, and so on, with xn mapping to x1. Cycles that consist of a single element only are omitted. So for example the permutation that shifts each element of S5 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 x0x1...xi-1xi...xjxi where xi 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 S5, (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 Sn.

Proof

Let a1, a2, ..., an be the elements of G. For each a in G define a function fa:G→G by fa(b) = ab. Each such fa is a bijection (fa^-1^ is it inverse), and the set of such functions is closed under composition (since fa(fb(c)) = abc = fab(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 Sn (relabel a1...an,, as 1...n).

For example, the cyclic group ℤm is isomorphic to the subgroup of Sm generated by (1 2 3 ... m). Many symmetry groups can easily be shown to be isomorphic to subgroups of Sn 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 Sn 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 S5 has type [23], while the permutation (12)(34) has type [1 22] (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 Sn 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 [1n-22], 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 (x1 x2 ... xk) = (x1 xk) (x1 xk-1) (x1 xk-2) ... (x1 x3) (x1 x2), in which each xi for i < k is first swapped into position x1 and then back into position xi+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)(a1 ... ak x b1 ... bm y) = (a1 ... ak y) (b1 ... bm x).

Proof

Walk the elements through both cycles on the LHS. Each ai except ak is still sent to ai+1, since ai+1 is not affected by (x y). The element ak is sent first to x and then y. The element y is sent to a1 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 (b1 ... bm x) forms the second cycle.

Corollary 2

(x y)(a1 ... ak y) (b1 ... bm x) = (a1 ... ak x b1 ... bm 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 Sn, called the alternating subgroup An: 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 An is exactly n!/2, or half the size of Sn. 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).

1. 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)

2014-06-17 11:58