Theorem 5.2 Disjoint Cycles Commute

PROOF For definiteness, let us say that aand b are permutations of the set

S5{a₁,a₂, . . . ,a_m,b₁,b₂, . . . ,b_n,c₁,c₂, . . . ,c_k}

where the c’s are the members of Sleft fixed by both aand b(there may not be any c’s). To prove that ab 5 ba, we must show that (ab)(x) 5 (ba)(x) for all xin S. If xis one of the aelements, say a_i, then

(ab)(a_i) 5 a(b(a_i)) 5 a(a_i) 5a_i11,

since bfixes all aelements. (We interpret a_i11as a₁if i5m.) For the same reason,

(ba)(a_i) 5 b(a(a_i)) 5 b(a_i11) 5a_i11.

Hence, the functions of aband baagree on the aelements. A similar argument shows that ab and ba agree on the b elements as well.

Finally, suppose that xis a celement, say c_i. Then, since both aand b fix celements, we have

(ab)(c_i) 5 a(b(c_i)) 5 a(c_i) 5c_i and

(ba)(c_i) 5 b(a(c_i)) 5 b(c_i) 5c_i. This completes the proof.

In demonstrating how to multiply cycles, we showed that the product (13)(27)(456)(8)(1237)(648)(5) can be written in disjoint cycle

If the pair of cycles a 5(a₁, a₂, . . . , a_m) and b 5(b₁,b₂, . . . , b_n) have no entries in common, then ab 5 ba.

102 ^Groups

form as (1732)(48)(56). Is economy in expression the only advantage to writing a permutation in disjoint cycle form? No. The next theorem shows that the disjoint cycle form has the enormous advantage of allowing us to “eyeball” the order of the permutation.

Theorem 5.3 Order of a Permutation (Ruffini—1799)

PROOF First, observe that a cycle of length nhas order n. (Verify this yourself.) Next, suppose that a and bare disjoint cycles of lengths m and n, and let kbe the least common multiple of mand n. It follows from Theorem 4.1 that both a^kand b^kare the identity permutation eand, since aand bcommute, (ab)^k5 a^kb^kis also the identity. Thus, we know by Corollary 2 to Theorem 4.1 (a^k5e implies that |a|divides k) that the order of ab—let us call it t—must divide k. But then (ab)^t5 a^tb^t5 e, so that a^t5 b^2t. However, it is clear that if aand bhave no common symbol, the same is true for a^tand b^2t, since raising a cycle to a power does not introduce new symbols. But, if a^tand b^2tare equal and have no common symbol, they must both be the identity, because every sym- bol in a^tis fixed by b^2tand vice versa (remember that a symbol not ap- pearing in a permutation is fixed by the permutation). It follows, then, that both mand n must divide t. This means that k, the least common multiple of mand n, divides talso. This shows that k5t.

Thus far, we have proved that the theorem is true in the cases where the permutation is a single cycle or a product of two disjoint cycles. The general case involving more than two cycles can be han- dled in an analogous way.

Theorem 5.3 is an enomously powerful tool for calculating the or- ders of permuations. We demonstrate this in the next example.

EXAMPLE 4 To determine the orders of the 5040 elements of , we need only consider the possible disjoint cycle structures of the elements of . For convenience, we denote an n-cycle by (n). Then, ar- ranging all possible disjoint cycle structures of elements of according to longest cycle lengths left to right, we have

S₇ S₇

S₇ The order of a permutation of a finite set written in disjoint cycle form is the least common multiple of the lengths of the cycles.

16509_ch05_p095-121 pp3 11/17/08 9:58 AM Page 102

5 | Permutation Groups 103

(7) (6) (1) (5) (2) (5) (1) (1) (4) (3) (4) (2) (1) (4) (1) (1) (1) (3) (3) (1) (3) (2) (2) (3) (2) (1) (1) (3) (1) (1) (1) (1) (1) (2) (2) (2) (1) (2) (2) (1) (1) (1) (2) (1) (1) (1) (1) (1) (1) (1) (1) (1) (1) (1) (1).

Now, from Theorem 5.3 we see that the orders of the elements of are 7, 6, 10, 5, 12, 4, 3, 2, and 1. To do the same for the

elements of would be nearly as simple.

As we will soon see, a particularly important kind of permutation is a cycle of length 2—that is, a permutation of the form (ab) where a2b. Many authors call these permutations transpositions,since the effect of (ab) is to interchange or transpose aand b.

Theorem 5.4 Product of 2-Cycles

PROOF First, note that the identity can be expressed as (12)(12), and so it is a product of 2-cycles. By Theorem 5.1, we know that every per- mutation can be written in the form

(a₁a₂? ? ?a_k)(b₁b₂? ? ?b_t) ? ? ?(c₁c₂? ? ?c_s).

A direct computation shows that this is the same as

(a₁a_k)(a₁a_k21) ? ? ?(a₁a₂)(b₁b_t)(b₁b_t21) ? ? ?(b₁b₂)

? ? ?(c₁c_s)(c₁c_s21) ? ? ?(c₁c₂).

This completes the proof.

The decompositions in the following example demonstrate this technique.

Every permutation in S_n, n .1, is a product of 2-cycles.

S₁₀

10!53,628,800 S₇

104 ^Groups

EXAMPLE 5

(12345) 5(15)(14)(13)(12) (1632)(457) 5(12)(13)(16)(47)(45)

The decomposition of a permutation into a product of 2-cycles given in the proof of Theorem 5.4 is not the only way a permutation can be written as a product of 2-cycles. Although the next example shows that even the numberof 2-cycles may vary from one decomposition to an- other, we will prove in Theorem 5.5 (first proved by Cauchy) that there is one aspect of a decomposition that never varies.

EXAMPLE 6

(12345) 5(54)(53)(52)(51)

(12345) 5(54)(52)(21)(25)(23)(13) We isolate a special case of Theorem 5.5 as a lemma.

Lemma

PROOF Clearly,r21, since a 2-cycle is not the identity. If r52, we are done. So, we suppose that r .2, and we proceed by induction.

Since (ij) 5(ji), the product b_r21b_rcan be expressed in one of the fol- lowing forms shown on the right:

e 5(ab)(ab) (ab)(bc) 5(ac)(ab) (ac)(cb) 5(bc)(ab) (ab)(cd) 5(cd)(ab).

If the first case occurs, we may delete b_r21b_rfrom the original product to obtain e 5 b₁b₂? ? ? b_r22. In the other three cases, we replace the form of b_r21b_ron the right by its counterpart on the left to obtain a new product of r2-cycles that is still the identity, but where the rightmost occurrence of the integer ais in the second-from-the-rightmost 2-cycle of the product instead of the rightmost 2-cycle. We now repeat the proce- dure just described with b_r22b_r21, and, as before, we obtain a product of (r 22) 2-cycles equal to the identity or a new product of r 2-cycles, where the rightmost occurrence of ais in the third 2-cycle from the right.

If e 5 b₁b₂? ? ? b_r, where the b’s are 2-cycles, then r is even.

16509_ch05_p095-121 pp3 11/17/08 9:58 AM Page 104

5 | Permutation Groups 105

Continuing this process, we must obtain a product of (r22) 2-cycles equal to the identity, because otherwise we have a product equal to the identity in which the only occurrence of the integer ais in the leftmost 2- cycle, and such a product does not fix a, whereas the identity does. Hence, by the Second Principle of Mathematical Induction,r22 is even, and r is even as well.