8 Chapter 1. Groups I Here is another example: let us write σ = (1 2)(1 3 4 2 5)(2 5 1 3) as a product of disjoint cycles in S5. To find the two-rowed notation for σ, evaluate, starting with the cycle on the right: σ : 1 → 3 → 4 → 4 σ : 4 → 4 → 2 → 1 σ : 2 → 5 → 1 → 2 σ : 3 → 2 → 5 → 5 σ : 5 → 1 → 3 → 3. Thus, σ = (1 4)(2)(3 5). Proposition 1.4. Every permutation α ∈ Sn is either a cycle or a product of disjoint cycles. Proof. The proof is by induction on the number k of points moved by α. The base step k = 0 is true, for now α is the identity, which is a 1-cycle. If k 0, let i1 be a point moved by α. Define i2 = α(i1), i3 = α(i2),... , ir+1 = α(ir), where r is the smallest integer for which ir+1 ∈ {i1,i2,...,ir} (since there are only n possible values, the list i1,i2,i3,...,ik,... must eventually have a repetition). We claim that α(ir) = i1. Otherwise, α(ir) = ij for some j ≥ 2. But α(ij−1) = ij since r j − 1, this contradicts the hypothesis that α is an injection. Let σ be the r-cycle (i1 i2 i3 . . . ir). If r = n, then α = σ. If r n, then σ fixes each point in Y , where Y consists of the remaining n − r points, while α(Y ) = Y . Define α to be the permutation with α (i) = α(i) for i ∈ Y that fixes all i / ∈ Y , and note that α = σα . The inductive hypothesis gives α = β1 · · · βt, where β1,...,βt are disjoint cycles. Since σ and α are disjoint, α = σβ1 · · · βt is a product of disjoint cycles. • The inverse of a function f : X → Y is a function g : Y → X with gf = 1X and fg = 1Y . A function has an inverse if and only if it is a bijection (FCAA, p. 95), and inverses are unique when they exist. Every permutation is a bijection how do we find its inverse? In the pictorial representation on page 6 of a cycle α as a clockwise rotation of a circle, its inverse α−1 is just the counterclockwise rotation. Proposition 1.5. (i) The inverse of the cycle α = (i1 i2 . . . ir) is the cycle (ir ir−1 . . . i1): (i1 i2 . . . ir)−1 = (ir ir−1 . . . i1). (ii) If γ ∈ Sn and γ = β1 · · · βk, then γ−1 = βk −1 · · · β1 −1 . Proof. FCAA, p. 115. •

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2010 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.