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.
Previous Page Next Page