Section 1.2. Permutations 11 so that γ = αβα−1, by Lemma 1.7. Note that rewriting the cycles of β, for example, as β = (1 2 3)(5)(4), gives another choice for α. Theorem 1.9. Permutations γ and σ in Sn have the same cycle structure if and only if there exists α ∈ Sn with σ = αγα−1. Proof. Suﬃciency was proved in Lemma 1.7. For the converse, place one complete factorization over the other so that each cycle below lies under a cycle of the same length: γ = δ1δ2 · · · (i1 i2 . . . ) · · · δt σ = η1η2 · · · (k . . . ) · · · ηt. Now define α to be the “downward” function, as in the example hence, α(i1) = k, α(i2) = , and so forth. Note that α is a permutation, for there are no repetitions of symbols in the factorization of γ (the cycles η are disjoint). It now follows from Lemma 1.7 that σ = αγα−1. • Here is another useful factorization of a permutation. Proposition 1.10. If n ≥ 2, then every α ∈ Sn is a transposition or a product 7 of transpositions. Proof. In light of Proposition 1.4, it suﬃces to factor an r-cycle β into a product of transpositions, and this is done as follows: β = (1 2 . . . r) = (1 r)(1 r − 1) · · · (1 3)(1 2). • Every permutation can thus be realized as a sequence of interchanges, but such a factorization is not as nice as the factorization into disjoint cycles. First, the trans- positions occurring need not commute: (1 2 3) = (1 3)(1 2) = (1 2)(1 3) second, neither the factors themselves nor the number of factors are uniquely determined. For example, here are some factorizations of (1 2 3) in S4: (1 2 3) = (1 3)(1 2) = (2 3)(1 3) = (1 2)(2 3) = (1 3)(4 2)(1 2)(1 4) = (1 3)(4 2)(1 2)(1 4)(2 3)(2 3). Is there any uniqueness at all in such a factorization? We will prove that the parity of the number of factors is the same for all factorizations of a permutation α that is, the number of transpositions is always even or always odd [as suggested by the factorizations of α = (1 2 3) displayed above]. 7It is convenient to generalize the term product to apply when there is only one factor. We can now rephrase the statement of Proposition 1.10 to say that every permutation in Sn is a product of transpositions. Similarly, we can rephrase Proposition 1.4 to say that every permutation in Sn is a product of disjoint cycles.

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.