Permutation groups and the symmetric group

A permutation of a set \(X\) is a bijection from \(X\) to itself. The permutations of \(X\) form a group under composition: composing two bijections gives a bijection, composition of functions is associative, the identity map is the identity, and every bijection has an inverse bijection. When \(X = \{1, 2, \dots, n\}\) this group is the symmetric group \(S_n\). It has \(n!\) elements, because a permutation can send 1 to any of \(n\) places, then 2 to any of the remaining \(n - 1\), and so on.

Symmetric groups are the historical starting point of group theory, the setting for Galois's work on equations, and in a precise sense they contain every finite group: Cayley's theorem, proved in lesson 8, says that every group of order \(n\) is the same as a group of permutations of \(n\) objects. This lesson develops the standard notation for permutations, shows how to compute with them and proves the most important fact about them, that every permutation is either even or odd.

Two-line and cycle notation

One way to write a permutation \(\sigma \in S_n\) is to list each number above its image:

\[ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 5 & 4 & 1 & 2 & 6 \end{pmatrix}. \]

This is two-line notation: \(\sigma(1) = 3\), \(\sigma(2) = 5\), and so on. It is clear but bulky. Cycle notation is more compact and shows the structure. Start at 1 and follow it: \(1 \mapsto 3 \mapsto 4 \mapsto 1\). That is a cycle, written \((1\,3\,4)\). Next take the smallest number not yet used, 2: \(2 \mapsto 5 \mapsto 2\), the cycle \((2\,5)\). Finally \(6 \mapsto 6\) is a fixed point, usually omitted. So \(\sigma = (1\,3\,4)(2\,5)\).

A cycle \((a_1\,a_2\,\dots\,a_k)\) sends \(a_1 \mapsto a_2 \mapsto \cdots \mapsto a_k \mapsto a_1\) and fixes everything else. Its length is \(k\); a cycle of length \(k\) is a \(k\)-cycle, and a 2-cycle is a transposition. The same cycle can be written starting at any of its entries: \((1\,3\,4) = (3\,4\,1) = (4\,1\,3)\), but \((1\,4\,3)\) is a different cycle, its inverse.

Multiplying permutations

We compose permutations right to left, as functions: \(\sigma\tau\) means apply \(\tau\) first, then \(\sigma\). To compute \((1\,2\,3)(2\,4)\) in \(S_4\), follow each number through the right-hand factor and then the left. Start with 1: \((2\,4)\) fixes 1, then \((1\,2\,3)\) sends 1 to 2, so 1 goes to 2. Next 2: \((2\,4)\) sends 2 to 4, then \((1\,2\,3)\) fixes 4, so 2 goes to 4. Next 4: \((2\,4)\) sends 4 to 2, then \((1\,2\,3)\) sends 2 to 3, so 4 goes to 3. Finally 3 goes to 1. The product is \((1\,2\,4\,3)\).

Computing in the other order, \((2\,4)(1\,2\,3)\) sends 1 to 4, 4 to 2, 2 to 3 and 3 to 1, giving \((1\,4\,2\,3)\). The two products differ, so \(S_4\) is not abelian. In fact \(S_n\) is nonabelian for every \(n \ge 3\), since \((1\,2)(1\,3) = (1\,3\,2)\) but \((1\,3)(1\,2) = (1\,2\,3)\).

Disjoint cycle decomposition

Two cycles are disjoint if they have no entries in common. Disjoint cycles commute, because each moves only numbers the other fixes: \((1\,3\,4)(2\,5) = (2\,5)(1\,3\,4)\).

Theorem. Every permutation of a finite set is a product of disjoint cycles, and this product is unique apart from the order of the cycles and the omission of 1-cycles.

Proof sketch: define \(i \sim j\) if \(j = \sigma^k(i)\) for some integer \(k\). This is an equivalence relation, so it partitions \(\{1, \dots, n\}\) into classes, called the orbits of \(\sigma\). Within one orbit, starting at \(i\), the elements \(i, \sigma(i), \sigma^2(i), \dots\) eventually repeat because the set is finite; the first repeat must be \(i\) itself, since \(\sigma\) is injective, so the orbit is \(\{i, \sigma(i), \dots, \sigma^{k-1}(i)\}\) for some \(k\), and \(\sigma\) acts on it as the \(k\)-cycle \((i\,\sigma(i)\,\dots\,\sigma^{k-1}(i))\). Multiplying these cycles over all orbits gives \(\sigma\). Uniqueness holds because the orbits and the action of \(\sigma\) on each are determined by \(\sigma\). Lesson 11 will meet orbits again in the general setting of group actions.

The lengths of the cycles in the decomposition, listed in decreasing order, form the cycle type of the permutation. The permutation \((1\,3\,4)(2\,5)\) in \(S_6\) has cycle type \((3, 2, 1)\).

Theorem. The order of a permutation is the least common multiple of the lengths of its disjoint cycles. Proof: a \(k\)-cycle has order \(k\). If \(\sigma = c_1 c_2 \cdots c_r\) with disjoint cycles, then because they commute, \(\sigma^m = c_1^m c_2^m \cdots c_r^m\), and because they move disjoint sets this is the identity exactly when each \(c_i^m\) is the identity, that is when each length divides \(m\). So \((1\,3\,4)(2\,5)\) has order \(\operatorname{lcm}(3, 2) = 6\). The largest order of an element of \(S_7\) is 12, from cycle type \((4, 3)\), not 7.

Transpositions and parity

Every cycle is a product of transpositions: \((a_1\,a_2\,\dots\,a_k) = (a_1\,a_k)(a_1\,a_{k-1}) \cdots (a_1\,a_2)\), which you can check by following each \(a_i\). Since every permutation is a product of cycles, every permutation is a product of transpositions. The transpositions generate \(S_n\). The expression is far from unique: \((1\,2\,3) = (1\,3)(1\,2) = (2\,3)(1\,3) = (1\,3)(2\,3)(1\,2)(1\,3)\). But the parity of the number of transpositions is always the same.

Theorem. A permutation cannot be written both as a product of an even number of transpositions and as a product of an odd number.

Proof: for a permutation \(\sigma\) of \(\{1, \dots, n\}\), an inversion is a pair \(i < j\) with \(\sigma(i) > \sigma(j)\). Let \(N(\sigma)\) be the number of inversions and define the sign \(\operatorname{sgn}(\sigma) = (-1)^{N(\sigma)}\). We show that multiplying by any transposition changes the sign. First consider an adjacent transposition \(\tau = (k\,\,k{+}1)\). The permutation \(\sigma\tau\) is \(\sigma\) with the values in positions \(k\) and \(k + 1\) swapped. This changes whether the pair of positions \((k, k + 1)\) is an inversion and leaves every other pair's status alone, since the other positions see the same two values, just in swapped places. So \(N\) changes by exactly 1 and the sign flips. Any transposition \((i\,j)\) with \(i < j\) is a product of \(2(j - i) - 1\) adjacent transpositions (move \(i\) step by step up to position \(j\), then the displaced entry back down), an odd number, so multiplying by it also flips the sign. The identity has no inversions and sign \(+1\). Hence a product of \(m\) transpositions has sign \((-1)^m\), and \(m\) cannot be both even and odd.

A permutation is even if it is a product of an even number of transpositions, odd otherwise. The sign is \(+1\) for even and \(-1\) for odd permutations, and \(\operatorname{sgn}(\sigma\tau) = \operatorname{sgn}(\sigma)\operatorname{sgn}(\tau)\). A \(k\)-cycle is a product of \(k - 1\) transpositions, so it is even when \(k\) is odd and odd when \(k\) is even, the opposite of what the names suggest. A permutation of cycle type \((k_1, \dots, k_r)\) has sign \((-1)^{\sum (k_i - 1)}\).

The alternating group

The even permutations of \(\{1, \dots, n\}\) form a group \(A_n\), the alternating group: the product of two even permutations is even, the identity is even and the inverse of a product of transpositions is the same transpositions in reverse order, which has the same count. For \(n \ge 2\), exactly half the permutations are even: multiplying by \((1\,2)\) is a bijection from even permutations to odd ones. So \(|A_n| = n!/2\). For instance \(A_3 = \{e, (1\,2\,3), (1\,3\,2)\}\) is cyclic of order 3, and \(A_4\) has 12 elements: the identity, eight 3-cycles and three products of two transpositions such as \((1\,2)(3\,4)\). The alternating groups \(A_n\) for \(n \ge 5\) are the smallest examples of the simple groups met in lesson 9, and their simplicity is the reason the general quintic is not solvable by radicals.

Computing with permutations

The code below implements composition, cycle decomposition, sign by counting inversions and sign by cycle type, and checks that they agree on every element of \(S_5\). It then tallies \(S_5\) by cycle type, giving the number of elements of each order.

from itertools import permutations
from math import lcm
from collections import Counter

def compose(s, t):            # s after t, permutations of 0..n-1 as tuples
    return tuple(s[t[i]] for i in range(len(t)))

def cycles(p):
    seen, out = set(), []
    for i in range(len(p)):
        if i not in seen:
            c, j = [], i
            while j not in seen:
                seen.add(j); c.append(j); j = p[j]
            out.append(tuple(x + 1 for x in c))      # print 1-based
    return out

def sign_inversions(p):
    n = len(p)
    inv = sum(1 for i in range(n) for j in range(i + 1, n) if p[i] > p[j])
    return (-1) ** inv

def sign_cycles(p):
    return (-1) ** sum(len(c) - 1 for c in cycles(p))

def order(p):
    return lcm(*[len(c) for c in cycles(p)])

S5 = list(permutations(range(5)))
print("|S5| =", len(S5), "| signs agree:", all(sign_inversions(p) == sign_cycles(p) for p in S5))
print("even permutations:", sum(1 for p in S5 if sign_cycles(p) == 1))

types = Counter(tuple(sorted((len(c) for c in cycles(p)), reverse=True)) for p in S5)
for ct, count in sorted(types.items(), key=lambda kv: (-kv[0][0], kv[0])):
    rep = next(p for p in S5 if tuple(sorted((len(c) for c in cycles(p)), reverse=True)) == ct)
    par = "even" if sign_cycles(rep) == 1 else "odd"
    print(f"type {str(ct):16s} count {count:3d}  order {order(rep):2d}  {par}")

a, b = (1, 2, 0, 3, 4), (0, 3, 2, 1, 4)        # (1 2 3) and (2 4)
print("(1 2 3)(2 4) =", cycles(compose(a, b)), " (2 4)(1 2 3) =", cycles(compose(b, a)))

|S5| = 120 | signs agree: True
even permutations: 60
type (5,)             count  24  order  5  even
type (4, 1)           count  30  order  4  odd
type (3, 1, 1)        count  20  order  3  even
type (3, 2)           count  20  order  6  odd
type (2, 1, 1, 1)     count  10  order  2  odd
type (2, 2, 1)        count  15  order  2  even
type (1, 1, 1, 1, 1)  count   1  order  1  even
(1 2 3)(2 4) = [(1, 2, 4, 3), (5,)]  (2 4)(1 2 3) = [(1, 4, 2, 3), (5,)]

The table shows the seven cycle types of \(S_5\). For example there are 24 five-cycles, all of order 5 and even, and 20 elements of type \((3, 2)\), of order 6 and odd. The counts add to 120, and the even ones (types \((5)\), \((3,1,1)\), \((2,2,1)\) and the identity) add to 60, the order of \(A_5\).

The fifteen puzzle

Parity has a famous application. The fifteen puzzle consists of fifteen numbered tiles and one empty space in a \(4 \times 4\) frame; a move slides a tile into the empty space. In the 1880s a version was popularized with tiles 14 and 15 swapped and a prize offered for restoring the order. No one could, because it is impossible. In 1879 William Johnson and William Story had proved that exactly half of all arrangements can be reached.

The argument is a parity count. Treat the empty space as a sixteenth tile. Each move is a transposition of the space with a neighbouring tile, so it changes the parity of the arrangement as a permutation of 16 objects. Colour the squares of the frame like a chessboard; each move also changes the colour of the square the space sits on. If the space starts and ends in the bottom-right corner, it has made an even number of moves, so the overall permutation is even. Swapping only 14 and 15, with the space back in its corner, is a single transposition, which is odd. So that arrangement cannot be reached. The Rubik's cube has a similar parity constraint: the permutation of the corner pieces and the permutation of the edge pieces always have the same sign, which is one of the reasons the cube group in lesson 12 is smaller than the set of all sticker arrangements.