Section 1.2. Permutations 7 Proposition 1.3. Disjoint permutations α, β ∈ Sn commute. Proof. It suﬃces to prove that if 1 ≤ i ≤ n, then αβ(i) = βα(i). If β moves i, say, β(i) = j = i, then β also moves j [otherwise, β(j) = j and β(i) = j contradict β’s being an injection] since α and β are disjoint, α(i) = i and α(j) = j. Hence βα(i) = j = αβ(i). The same conclusion holds if α moves i. Finally, it is clear that αβ(i) = i = βα(i) if both α and β fix i. • Aside from being cumbersome, there is a major problem with the two-rowed notation for permutations. It hides the answers to elementary questions such as: Is a permutation a cycle? Is the square of a permutation the identity? The algorithm we now introduce, which factors a permutation into a product of disjoint cycles, will remedy this defect. Let α = 1 2 3 4 5 6 7 8 9 6 4 7 2 5 1 8 9 3 . Begin by writing “(1.” Now α: 1 → 6 write “(1 6.” Next, α: 6 → 1, and the parentheses close: α begins “(1 6).” The first number not having appeared is 2, and we write “(1 6)(2.” Now α: 2 → 4 write “(1 6)(2 4.” Since α: 4 → 2, the parentheses close once again, and we write “(1 6)(2 4).” The smallest remaining number is 3 now 3 → 7, 7 → 8, 8 → 9, and 9 → 3 this gives the 4-cycle (3 7 8 9). Finally, α(5) = 5 we claim that α = (1 6)(2 4)(3 7 8 9)(5). Since multiplication in Sn is composition of functions, our claim is that α(i) = [(1 6)(2 4)(3 7 8 9)(5)](i) for every i between 1 and 9 [after all, two functions f and g are equal if and only if they have the same domain, the same target,5 and f(i) = g(i) for every i in their domain]. The right side is the value of the composite βγδ, where β = (1 6), γ = (2 4), and δ = (3 7 8 9) [we may ignore the 1-cycle (5) when we are evaluating, for it is the identity function]. Now α(1) = 6 let us evaluate the composite on the right when i = 1: βγδ(1) = β(γ(δ(1))) = β(γ(1)) because δ = (3 7 8 9) fixes 1 = β(1) because γ = (2 4) fixes 1 = 6 because β = (1 6). Similarly, we can show that α(i) = βγδ(i) for every i, proving the claim. We multiply permutations from right to left, because multiplication here is composition of functions 6 that is, to evaluate αβ(1), we compute α(β(1)). 5If X Y is a proper subset, then this definition shows that the inclusion i: X → Y is not equal to the identity 1X , for they have different targets. 6There are authors who multiply permutations differently, so that their αβ is our βα. This is a consequence of their putting “functions on the right”: instead of writing α(i) as we do, they write (i)α. Consider the composite of permutations α and β in which we first apply β and then apply α. We write i → β(i) → α(β(i)). In the right-sided notation, i → (i)β → ((i)β)α. Thus, the notational switch causes a switch in the order of multiplication we write αβ they write βα.

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.