Permutation groups and cycle notation
Shuffling a list, relabeling the corners of a solid and swapping two entries of a table all rearrange a finite set. How should a rearrangement be written so that two of them can be composed at a glance, and what does every way of building one out of swaps have in common?
Where you are 6 in Groups
Why this exists
A symmetry of a square moves its corners among themselves, and a shuffle moves cards among positions: each is a rearrangement of a finite set, and composing two of them is the group operation. The groups of all rearrangements are not abelian, every finite group is isomorphic to a subgroup of one (Isomorphisms), and they carry an invariant, parity, that no way of building a rearrangement out of swaps can change. This lesson gives a notation in which products are computed by eye, and proves the two facts everything later relies on: each permutation splits into disjoint cycles, and each is even or odd but never both.
Definition
A permutation of a set X is a bijection X \to X (One-to-one, onto and bijective functions). The permutations of X form a group \operatorname{Sym}(X) under composition (Binary operations and the group axioms, Example 6). For a positive integer n, the symmetric group S_n is \operatorname{Sym}(\{1, \dots, n\}). A permutation group is a subgroup of some \operatorname{Sym}(X).
Products. The product \sigma\tau means the composite \sigma \circ \tau, so (\sigma\tau)(x) = \sigma(\tau(x)): \tau acts first, and products are read right to left, as composition is in Composing functions between sets, and when an inverse exists. The identity permutation is e, and \sigma^{-1} is the inverse map.
Two-line form. A permutation of \{1, \dots, n\} is given by listing each x above its image: \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} sends 1 \mapsto 3, 2 \mapsto 1, 3 \mapsto 2.
Cycles. Let k \ge 2 and let a_1, \dots, a_k be distinct elements of X. The cycle (a_1\ a_2\ \cdots\ a_k) is the permutation with
that fixes every other element of X. It has length k, and a_1, \dots, a_k are its entries; a cycle of length 2 is a transposition. The same cycle can be written starting at any entry, (1\ 3\ 2) = (3\ 2\ 1) = (2\ 1\ 3), and its inverse runs backward, (a_1\ a_2\ \cdots\ a_k)^{-1} = (a_k\ \cdots\ a_2\ a_1). A 1-cycle (a) would be e and is not written. Two cycles are disjoint if they have no entry in common.
Parity. A permutation of a finite set is even if it is a product of an even number of transpositions and odd if of an odd number; by Theorems 5 and 7 it is exactly one of these when the set has at least two elements. For \sigma \in S_n let c(\sigma) be the number of cycles of \sigma, counting each fixed point as a cycle of length 1; the sign of \sigma is
The alternating group A_n is the set of even permutations in S_n.
Intuition
Draw a dot for each element of X and an arrow from each x to \sigma(x). As \sigma is a bijection, every dot has one arrow out and one in, so the picture falls apart into closed loops: the cycles.
Composing with a transposition (a\ b) on the left redirects only the two arrows into a and into b, each onto the other. If a and b sat on one loop, it is cut in two; if they sat on different loops, the two are joined. Either way the number of loops changes by one, and that is the whole idea behind the sign.
Results
Theorem 1 (the symmetric group). S_n is a group of order n!. For n \ge 3 it is not abelian.
Theorem 2 (disjoint cycles commute). If \gamma and \delta are disjoint cycles in \operatorname{Sym}(X), then \gamma\delta = \delta\gamma.
Theorem 3 (cycle decomposition). Let X be finite and \sigma \in \operatorname{Sym}(X), \sigma \ne e. Then \sigma is a product of pairwise disjoint cycles, and these cycles are unique: any two such factorizations have the same factors, in some order.
Theorem 4 (order). A cycle of length k has order k. If \sigma is a product of disjoint cycles of lengths k_1, \dots, k_r, then \operatorname{ord}(\sigma) = \operatorname{lcm}(k_1, \dots, k_r).
Theorem 5 (transpositions). For distinct a_1, \dots, a_k,
a product of k - 1 transpositions. So if |X| \ge 2, every permutation of X is a product of transpositions.
Lemma 6 (one swap, one cycle more or less). Let \sigma \in S_n and \tau = (a\ b). If a and b lie in the same cycle of \sigma, then c(\tau\sigma) = c(\sigma) + 1; if not, c(\tau\sigma) = c(\sigma) - 1.
Theorem 7 (sign). (a) If \sigma \in S_n is a product of m transpositions, then \operatorname{sgn}(\sigma) = (-1)^m. So no permutation is both even and odd, and \sigma is even exactly when \operatorname{sgn}(\sigma) = 1. (b) \operatorname{sgn}(\sigma\tau) = \operatorname{sgn}(\sigma)\operatorname{sgn}(\tau). (c) A cycle of length k has sign (-1)^{k - 1}, so \sigma is even exactly when its decomposition has an even number of cycles of even length.
Theorem 8 (the alternating group). For n \ge 2, A_n \le S_n and \displaystyle |A_n| = \frac{n!}{2}.
Why it is true
Proof of Theorem 1. S_n is a group by Binary operations and the group axioms, Example 6. A permutation of \{1, \dots, n\} is fixed by the list \sigma(1), \dots, \sigma(n), which is an arrangement of 1, \dots, n, and every arrangement comes from exactly one permutation; there are n! arrangements (Arrangements and factorials). For n \ge 3, (1\ 2)(1\ 3) sends 1 \mapsto 3 while (1\ 3)(1\ 2) sends 1 \mapsto 2. \square
Proof of Theorem 2. Let A and B be the entry sets. A cycle maps its entries to entries and fixes everything else. If x \notin A \cup B, both sides fix x. If x \in A, then \gamma(x) \in A, so \delta fixes x and \gamma(x), and \gamma\delta(x) = \gamma(x) = \delta\gamma(x). The case x \in B is the same. \square
Proof of Theorem 3. As \operatorname{Sym}(X) is finite, the powers of \sigma are not all distinct, so \sigma has finite order m (Cyclic groups, Theorem 4). Write x \sim y if y = \sigma^i(x) for some integer i. This is an equivalence relation: x = \sigma^0(x); y = \sigma^i(x) gives x = \sigma^{-i}(y); and \sigma^j(\sigma^i(x)) = \sigma^{i + j}(x). Fix x. As \sigma^m(x) = x, there is a least k \ge 1 with \sigma^k(x) = x. Dividing, i = qk + r with 0 \le r < k (The division algorithm) gives \sigma^i(x) = \sigma^r(x), so the class of x is \{x, \sigma(x), \dots, \sigma^{k - 1}(x)\}; these are distinct, since \sigma^i(x) = \sigma^j(x) with 0 \le i < j < k would give \sigma^{j - i}(x) = x, against the choice of k. On this class \sigma acts as the cycle \gamma_x = (x\ \sigma(x)\ \cdots\ \sigma^{k - 1}(x)).
Let \gamma_1, \dots, \gamma_r be the cycles of the classes with at least two elements, disjoint as the classes are. For y in the class of \gamma_j the other factors fix y and \sigma(y), so \gamma_1 \cdots \gamma_r(y) = \gamma_j(y) = \sigma(y); a point alone in its class is fixed by all. So \sigma = \gamma_1 \cdots \gamma_r.
For uniqueness let \sigma = \delta_1 \cdots \delta_s with disjoint cycles. On the entries of \delta_j the other factors act trivially, so \sigma = \delta_j there, and by induction \delta_j lists x, \sigma(x), \sigma^2(x), \dots for any entry x: \delta_j = \gamma_x. Every point \sigma moves is an entry of some \delta_j, so the \delta’s are the \gamma’s. \square
Proof of Theorem 4. For \gamma = (a_1\ \cdots\ a_k), induction gives \gamma^i(a_j) = a_{j + i}, indices read mod k. So \gamma^k = e, while \gamma^i(a_1) \ne a_1 for 0 < i < k: \operatorname{ord}(\gamma) = k. Now let \sigma = \gamma_1 \cdots \gamma_r with disjoint \gamma_i of lengths k_i. The factors commute (Theorem 2), so \sigma^m = \gamma_1^m \cdots \gamma_r^m, and \gamma_i^m moves only entries of \gamma_i. Hence \sigma^m = e if and only if every \gamma_i^m = e, that is, k_i \mid m for every i (Cyclic groups, Theorem 4); the least such m \ge 1 is the lcm. \square
Proof of Theorem 5. Apply the right side to each point, rightmost factor first. a_1 goes to a_2 under (a_1\ a_2), and the later factors fix a_2. For 2 \le j \le k - 1, a_j is fixed until (a_1\ a_j) sends it to a_1, the next factor sends a_1 to a_{j + 1}, and the rest fix a_{j + 1}. a_k is fixed until the last factor sends it to a_1. Every other point is fixed. This is the cycle. With Theorem 3 every \sigma \ne e is a product of transpositions, and e = (a\ b)(a\ b) for any a \ne b. \square
Proof of Lemma 6. Let p = \sigma^{-1}(a) and q = \sigma^{-1}(b). Then \tau\sigma(x) = \sigma(x) unless \sigma(x) \in \{a, b\}, while \tau\sigma(p) = b and \tau\sigma(q) = a: only the arrows out of p and q change. If a and b share a cycle a \to \cdots \to q \to b \to \cdots \to p \to a, then in \tau\sigma the stretch from a to q closes through q \to a and the stretch from b to p through p \to b: two cycles (one of length 1 if q = a or p = b). Cycles a \to \cdots \to p \to a and b \to \cdots \to q \to b join into a \to \cdots \to p \to b \to \cdots \to q \to a. \square
Proof of Theorem 7. (a) c(e) = n, so \operatorname{sgn}(e) = 1, and by Lemma 6, \operatorname{sgn}(\tau\sigma) = -\operatorname{sgn}(\sigma) for every transposition \tau. If \sigma = \tau_1 \cdots \tau_m, induction on m gives \operatorname{sgn}(\sigma) = (-1)^m. Two expressions of \sigma with m and m' transpositions therefore have (-1)^m = (-1)^{m'}. (b) By Theorem 5 write \sigma and \tau with m and l transpositions; \sigma\tau is then a product of m + l. (c) Theorem 5 writes a k-cycle with k - 1 transpositions; then apply (b) to the decomposition of Theorem 3. \square
Proof of Theorem 8. e \in A_n, and by Theorem 7(b) products of even permutations are even, as are their inverses, since \operatorname{sgn}(\sigma^{-1})\operatorname{sgn}(\sigma) = 1. So A_n \le S_n (Subgroups, Theorem 2). By Theorems 5 and 7, S_n is the disjoint union of A_n and the set O of odd permutations, and \sigma \mapsto (1\ 2)\sigma, its own inverse, swaps them. So \displaystyle |A_n| = |O| = \frac{n!}{2}. \square
Worked examples
From two-line form to cycles
Write \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 5 & 8 & 1 & 4 & 3 & 2 & 6 & 7 \end{pmatrix} in cycle notation. Find \sigma^{-1} in both forms, \operatorname{ord}(\sigma) and \operatorname{sgn}(\sigma).
SolutionFollow 1: 1 \mapsto 5 \mapsto 3 \mapsto 1. The first unused point is 2: 2 \mapsto 8 \mapsto 7 \mapsto 6 \mapsto 2. Only 4 is left, and it is fixed. So \sigma = (1\ 5\ 3)(2\ 8\ 7\ 6), as in the first figure. Reversing each cycle (the factors commute by Theorem 2) gives \sigma^{-1} = (1\ 3\ 5)(2\ 6\ 7\ 8), with bottom row 3, 6, 5, 4, 1, 7, 8, 2. By Theorem 4, \operatorname{ord}(\sigma) = \operatorname{lcm}(3, 4) = 12. With the fixed point, c(\sigma) = 3, so \operatorname{sgn}(\sigma) = (-1)^{8 - 3} = -1: \sigma is odd, as Theorem 7(c) also says.
Products in both orders
In S_5 let \sigma = (1\ 4\ 2\ 5) and \tau = (2\ 3\ 5). Compute \sigma\tau and \tau\sigma.
SolutionFor \sigma\tau, apply \tau first. 1: \tau fixes it, \sigma sends it to 4. 4: fixed by \tau, then 4 \mapsto 2. 2: \tau gives 3, which \sigma fixes. 3: \tau gives 5, and \sigma sends 5 \mapsto 1, closing the cycle. 5: \tau gives 2, and \sigma sends 2 \mapsto 5. So \sigma\tau = (1\ 4\ 2\ 3), fixing 5.
For \tau\sigma, apply \sigma first: 1 \mapsto 4 \mapsto 4, 4 \mapsto 2 \mapsto 3, 3 \mapsto 3 \mapsto 5, 5 \mapsto 1 \mapsto 1, and 2 \mapsto 5 \mapsto 2. So \tau\sigma = (1\ 4\ 3\ 5), fixing 2. The products differ, though both are odd 4-cycles, as Theorem 7(b) requires.
The largest order in S_8
Find the largest order of an element of S_8, and count the elements of that order.
SolutionBy Theorems 3 and 4, the order of \sigma is the lcm of the lengths of its cycles, whose lengths sum to at most 8. One cycle gives at most 8. Two cycles of lengths a, b \ge 2 with a + b \le 8 give \operatorname{lcm}(a, b) \le ab, with equality only for coprime a, b: the coprime pairs give 2 \cdot 3, 2 \cdot 5, 3 \cdot 4 and 3 \cdot 5, and the others, (2, 2), (2, 4), (2, 6), (3, 3), (4, 4), give at most 6. The largest is 15. Three or four cycles of length at least 2 come from the lengths 2, 2, 2; 2, 2, 3; 2, 2, 4; 2, 3, 3 and 2, 2, 2, 2, with lcm at most 6. So the largest order is 15.
Order 15 needs cycle lengths divisible by 5 and by 3, which in 8 points forces a 5-cycle and a disjoint 3-cycle. There are (k - 1)! cycles on a given set of k points (smallest entry first, the rest in any order). Choosing the 5 points (\binom{8}{5} = 56 ways), a 5-cycle on them (4! = 24) and a 3-cycle on the rest (2! = 2) gives 56 \cdot 24 \cdot 2 = 2{,}688 elements of order 15.
A ballroom line
Mei coaches a ballroom formation team of five, member i starting in position i of a line. Andre calls two figures in turn, starting with a: in a the members in positions 1, 2 trade places, as do those in 3, 4; in b those in 2, 3 trade, and those in 4, 5. After how many figures is the starting line first restored, and which lines occur?
SolutionRecord a line as the permutation \rho with \rho(i) the member in position i; the start is e. After figure a = (1\ 2)(3\ 4), position i holds the member who stood at a(i), so the line becomes \rho a; likewise b = (2\ 3)(4\ 5) gives \rho b. After 2j figures the line is (ab)^j, and after 2j + 1 it is (ab)^j a. Applying b first,
of order 5 by Theorem 4. An odd count never restores the line: (ab)^j a = e would make a = (ab)^{-j}, but a has order 2 and every element of \langle ab \rangle but e has order 5 (Cyclic groups, Theorem 8). So the line is first restored after 10 figures, and the same argument shows the ten lines (ab)^j, (ab)^j a (0 \le j \le 4) are distinct. Read from position 1 to 5 they are 12345, 21435, 24153, 42513, 45231, 54321, 53412, 35142, 31524, 13254; halfway, the line is reversed.
When reversal is even
For n \ge 2 let \rho_n \in S_n be the reversal \rho_n(i) = n + 1 - i. Find \operatorname{ord}(\rho_n), and find for which n the reversal is even.
Solution\rho_n swaps i with n + 1 - i, which differ unless 2i = n + 1, so it is the product of the \lfloor n/2 \rfloor disjoint transpositions (i\ \ n + 1 - i) with i \le \lfloor n/2 \rfloor. By Theorem 4 its order is 2, and by Theorem 7, \operatorname{sgn}(\rho_n) = (-1)^{\lfloor n/2 \rfloor}. For n = 4q + s with 0 \le s \le 3, \lfloor n/2 \rfloor is 2q, 2q, 2q + 1, 2q + 1 for s = 0, 1, 2, 3: \rho_n is even exactly when n \equiv 0 or 1 \pmod 4. In Example 4, 54321 = (1\ 5)(2\ 4) is even, as it must be, since a and b are even.
The center of a symmetric group
Prove that for n \ge 3 the center of S_n (Subgroups, Example 3) is \{e\}.
SolutionProof. Let \sigma \ne e; choose a with b = \sigma(a) \ne a. As n \ge 3, there is c \notin \{a, b\}; let \tau = (b\ c). Then \sigma\tau(a) = \sigma(a) = b, since \tau fixes a, while \tau\sigma(a) = \tau(b) = c. As b \ne c, \sigma\tau \ne \tau\sigma, so \sigma is not in the center. \square For n = 2 the conclusion fails: S_2 = \{e, (1\ 2)\} is abelian.
Boundaries
- Non-disjoint cycles. Theorems 2 and 4 need disjointness. (1\ 2) and (2\ 3) do not commute, and (1\ 2\ 3)(3\ 4\ 5) is a 5-cycle, not of order \operatorname{lcm}(3, 3) = 3 (Exercise 4).
- A convention. Some books compose left to right, so their \sigma\tau is our \tau\sigma. Cycle decompositions, orders and signs do not depend on the convention; products do.
- Infinite sets. On \mathbb{Z} the shift k \mapsto k + 1 is a permutation with no cycle at all, so Theorem 3 needs X finite, and parity makes sense only for permutations moving finitely many points.
- Small n. S_2 is abelian, and \displaystyle |A_n| = \frac{n!}{2} fails for n = 1.
Where this goes next
A regular polygon’s symmetries permute its vertices, so the Dihedral groups sit inside S_n; the eight lines of Exercise 12 form one. By Lagrange's theorem every subgroup of S_n has order dividing n!. Isomorphisms proves Cayley’s theorem, that every group is isomorphic to a permutation group, and A_n is the first family of Normal subgroups. Conjugates have the same cycle lengths (Exercise 14), which Group actions, orbits and stabilizers uses to count conjugacy classes, and Solvable groups proves that S_5 is not solvable, the reason there is no formula by radicals for the general quintic.
Exercises
Cycle notation and products
- Write \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 4 & 9 & 3 & 7 & 2 & 8 & 1 & 6 & 5 \end{pmatrix} as a product of disjoint cycles, and find its order and sign.
- In S_6 let \alpha = (1\ 3\ 6)(2\ 5) and \beta = (1\ 2\ 3\ 4). Compute \alpha\beta and \beta\alpha.
- Find the inverse and the square of \gamma = (1\ 6\ 2\ 7\ 3) and of \delta = (1\ 2)(3\ 4\ 5\ 6).
- Write (1\ 2\ 3)(3\ 4\ 5) as a product of disjoint cycles and find its order.
- Write (1\ 2\ 3\ 4\ 5\ 6) and (1\ 3)(2\ 5\ 4) as products of transpositions, and give the sign of each.
Orders, counting and parity
- List the possible orders of elements of S_5 and the number of elements of each order.
- Find the largest order of an element of S_{10} and the number of elements of that order.
- List the elements of A_4 with the order of each.
- How many elements of S_6 have order 2?
- Which of these lie in A_7? (a) (1\ 2)(3\ 4)(5\ 6\ 7); (b) (1\ 2\ 3\ 4)(5\ 6); (c) (1\ 2\ 3\ 4\ 5\ 6\ 7); (d) (1\ 7)(1\ 6)(1\ 5).
- Mei’s team grows to six members. Andre now alternates a = (1\ 2)(3\ 4)(5\ 6) and b = (2\ 3)(4\ 5), starting with a, as in Example 4. After how many figures is the line first restored, and what is the line after six figures?
- A team of four alternates a = (1\ 2)(3\ 4) and b = (2\ 3), starting with a. List the lines until the start returns, and show that no sequence of a’s and b’s in any order reaches a line outside this list.
Proofs
- Prove that the only subgroup of S_n containing (1\ 2), (1\ 3), \dots, (1\ n) is S_n.
- Prove that for \sigma \in S_n and distinct a_1, \dots, a_k, \sigma(a_1\ \cdots\ a_k)\sigma^{-1} = (\sigma(a_1)\ \cdots\ \sigma(a_k)). Deduce that \sigma\pi\sigma^{-1} has the same cycle lengths as \pi for every \pi \in S_n.
- Prove that the only subgroup of S_n containing (1\ 2) and (1\ 2\ \cdots\ n) is S_n.
- Prove that for n \ge 3 every element of A_n is a product of 3-cycles.
- Prove that every permutation of odd order is even.
- Let H \le S_n contain an odd permutation. Prove that exactly half the elements of H are even.
Answers
- 1 \mapsto 4 \mapsto 7 \mapsto 1, 2 \mapsto 9 \mapsto 5 \mapsto 2, 6 \mapsto 8 \mapsto 6, and 3 is fixed: (1\ 4\ 7)(2\ 9\ 5)(6\ 8). Order \operatorname{lcm}(3, 3, 2) = 6; with c = 4, the sign is (-1)^{9 - 4} = -1, odd.
- Applying \beta first, 1 \mapsto 2 \mapsto 5, 5 \mapsto 2, 2 \mapsto 3 \mapsto 6, 6 \mapsto 1, 3 \mapsto 4, 4 \mapsto 1 \mapsto 3: \alpha\beta = (1\ 5\ 2\ 6)(3\ 4). Applying \alpha first, 1 \mapsto 3 \mapsto 4, 4 \mapsto 1, 2 \mapsto 5, 5 \mapsto 2 \mapsto 3, 3 \mapsto 6, 6 \mapsto 1 \mapsto 2: \beta\alpha = (1\ 4)(2\ 5\ 3\ 6).
- \gamma^{-1} = (3\ 7\ 2\ 6\ 1) = (1\ 3\ 7\ 2\ 6) and \gamma^2 = (1\ 2\ 3\ 6\ 7), each entry moving two steps along \gamma. \delta^{-1} = (1\ 2)(3\ 6\ 5\ 4) and \delta^2 = (3\ 5)(4\ 6), as (1\ 2)^2 = e.
- Applying (3\ 4\ 5) first: 1 \mapsto 2, 2 \mapsto 3, 3 \mapsto 4, 4 \mapsto 5, 5 \mapsto 3 \mapsto 1. So the product is (1\ 2\ 3\ 4\ 5), of order 5.
- By Theorem 5, (1\ 2\ 3\ 4\ 5\ 6) = (1\ 6)(1\ 5)(1\ 4)(1\ 3)(1\ 2), five transpositions, so odd. (2\ 5\ 4) = (2\ 4)(2\ 5), so (1\ 3)(2\ 5\ 4) = (1\ 3)(2\ 4)(2\ 5), three transpositions, so odd.
- By cycle type: e (1); transpositions (10) and products of two disjoint transpositions (15), order 2; 3-cycles (20), order 3; 4-cycles (30), order 4; 5-cycles (24), order 5; a 3-cycle times a disjoint transposition (20), order 6. Orders 1, 2, 3, 4, 5, 6 occur 1, 25, 20, 30, 24, 20 times, totaling 120.
- 30, from cycles of lengths 2, 3, 5. If the order is q_1 \cdots q_s, prime powers to distinct primes, each q_i divides a cycle length, and a length shared by several is at least their product, hence their sum; so q_1 + \dots + q_s \le 10, and the largest such product is 2 \cdot 3 \cdot 5 = 30 (then 3 \cdot 7 = 21). Order 30 in 10 points forces lengths exactly 2, 3, 5: \binom{10}{5} \cdot 4! \cdot \binom{5}{3} \cdot 2! = 120{,}960 elements.
- Twelve elements (Theorem 8): e, of order 1; the eight 3-cycles (1\ 2\ 3), (1\ 3\ 2), (1\ 2\ 4), (1\ 4\ 2), (1\ 3\ 4), (1\ 4\ 3), (2\ 3\ 4), (2\ 4\ 3), of order 3; and (1\ 2)(3\ 4), (1\ 3)(2\ 4), (1\ 4)(2\ 3), of order 2.
- 75: order 2 means every cycle has length 2. One transposition: \binom{6}{2} = 15; two: \displaystyle \frac{15 \cdot 6}{2} = 45; three: \displaystyle \frac{15 \cdot 6 \cdot 1}{3!} = 15.
- By Theorem 7(c): (a) two even-length cycles, even, in A_7; (b) two even-length cycles, even, in A_7; (c) a 7-cycle, even, in A_7; (d) three transpositions, odd, not in A_7.
- ab = (1\ 2\ 4\ 6\ 5\ 3) has order 6, and (ab)^j a = e would make a the one element of order 2 in \langle ab \rangle, which is (ab)^3 = (1\ 6)(2\ 5)(3\ 4) \ne a. So the line first returns after 12 figures. After six it is (ab)^3: the line reads 654321, fully reversed.
- ab = (1\ 2\ 4\ 3), of order 4, and a \ne (ab)^2 = (1\ 4)(2\ 3), so the start returns after 8 figures: 2143, 2413, 4231, 4321, 3412, 3142, 1324, 1234. As b = a(ab) and a(ab)^j = (ab)^{-j}a (from a(ab)a = ba = (ab)^{-1}), every word in a, b equals some (ab)^j or (ab)^j a: one of the eight lines.
- Proof. Let H be such a subgroup. For distinct a, b \ne 1, (1\ a)(1\ b)(1\ a) sends a \mapsto 1 \mapsto b, b \mapsto 1 \mapsto a and 1 \mapsto a \mapsto 1, and fixes the rest, so (a\ b) = (1\ a)(1\ b)(1\ a) \in H. So H contains every transposition, and by Theorem 5 every permutation. \square
- Proof. Let \gamma = (a_1\ \cdots\ a_k). For x = \sigma(a_i), \sigma\gamma\sigma^{-1}(x) = \sigma(\gamma(a_i)) = \sigma(a_{i + 1}), indices mod k. If x is not of this form, \sigma^{-1}(x) is not an entry of \gamma, so \sigma\gamma\sigma^{-1}(x) = \sigma\sigma^{-1}(x) = x. That is the cycle (\sigma(a_1)\ \cdots\ \sigma(a_k)). If \pi = \gamma_1 \cdots \gamma_r with disjoint cycles, then \sigma\pi\sigma^{-1} = (\sigma\gamma_1\sigma^{-1}) \cdots (\sigma\gamma_r\sigma^{-1}), and these cycles have the same lengths and are disjoint, as the bijection \sigma maps disjoint entry sets to disjoint sets. \square
- Proof. Let H contain t = (1\ 2) and \gamma = (1\ 2\ \cdots\ n). By Exercise 14, \gamma^j t \gamma^{-j} = (1 + j\ \ 2 + j), so H contains (i\ \ i + 1) for 1 \le i \le n - 1. If (1\ i) \in H with 2 \le i < n, then (i\ \ i + 1)(1\ i)(i\ \ i + 1) = (1\ \ i + 1) \in H, by Exercise 14, as (i\ \ i + 1) is its own inverse. Starting from (1\ 2), induction shows H contains (1\ i) for all i, and H = S_n by Exercise 13. \square
- Proof. A 3-cycle is even (Theorem 7(c)). An element of A_n is a product of an even number of transpositions; group them in consecutive pairs. A pair is (a\ b)(a\ b) = e, or shares one point and can be written (a\ b)(a\ c) = (a\ c\ b), or is disjoint, and then (a\ b)(c\ d) = (a\ c\ b)(a\ c\ d); each identity is checked by following a, b, c, d. The identity is the empty product, or (1\ 2\ 3)^3. \square
- Proof. If \sigma = \gamma_1 \cdots \gamma_r with disjoint cycles of lengths k_i, then \operatorname{ord}(\sigma) = \operatorname{lcm}(k_1, \dots, k_r) is a multiple of each k_i (Theorem 4). If it is odd, every k_i is odd, each \gamma_i has sign (-1)^{k_i - 1} = 1, and \sigma is even by Theorem 7. \square
- Proof. Let \pi \in H be odd, and let E and D be the even and the odd elements of H. By Theorem 7(b), x \mapsto \pi x maps E into D, and x \mapsto \pi^{-1}x maps D into E; they are inverse to each other. So |E| = |D|, and |H| = |E| + |D| = 2|E|. \square