Section 1.2. Permutations 7 Proposition 1.3. Disjoint permutations α, β Sn commute. Proof. It suffices 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 βα.
Previous Page Next Page