Cycles

A simple example of a permutation is obtained as follows: choose any two distinct integers between and , say, and , and write The permutation so defined is denoted by ; every permutation of this form is called a transposition . If is a transposition, then .

Another useful way of constructing examples is to choose distinct integers between and , say, , and to write The permutation so defined is denoted by . If , then ; if , then is a transposition. For any with , every permutation of the form is called a p-cycle , or simply a cycle ; the -cycles are exactly the transpositions. Warning: it is not assumed that . If, for instance, and , then there are twenty distinct cycles. Observe also that the notation for cycles is not unique; the symbols , , and all denote the same permutation. Two cycles and are disjoint if none of the ’s is equal to any of the ’s. If and are disjoint cycles, then , or, in other words, and commute.

Theorem 1. Every permutation is the product of pairwise disjoint cycles.

Proof. If is a permutation and if is such that (assume, for the moment, that ), form the sequence . Since there are only a finite number of distinct integers between and , there must exist exponents and such that . The one-to-one character of implies that , or, with an obvious change of notation, what we have proved is that there must exist a strictly positive exponent such that . If is selected to be the smallest exponent with this property, then the integers are distinct from each other. (Indeed, if and , then , contradicting the minimality of .) It follows that is a -cycle. If there is a between and different from each of and different from , we repeat the procedure that led us to this cycle, with in place of . We continue forming cycles in this manner as long as after each step we can still find a new integer that does not send on itself; the product of the disjoint cycles so constructed is . The case is covered by the rather natural agreement that a product with no factors, an “empty product,” is to be interpreted as the identity permutation. ◻

Theorem 2. Every cycle is a product of transpositions.

Proof. Suppose that is a -cycle; for the sake of notational simplicity, we shall give the proof, which is perfectly general, in the special case . The proof itself consists of one line: A few added words of explanation might be helpful. In view of the definition of the product of permutations, the right side of the last equation operates on each integer between and from the inside out, or, perhaps more suggestively, from right to left. Thus, for example, the result of applying to is calculated as follows: , , , , so that . ◻

For the sake of reference we put on record the following immediate corollary of the two preceding theorems.

Theorem 3. Every permutation is a product of transpositions.

Observe that the transpositions in Theorems 2 and 3 were not asserted to be disjoint; in general they are not.

EXERCISES

Exercise 1.

How many permutations are there in ?
How many distinct -cycles are there in ( )?

Exercise 2. If and are permutations (in ), then .

Exercise 3.

If and are permutations (in ), then there exists a unique permutation such that .
If , , and are permutations such that , then .

Exercise 4. Give an example of a permutation that is not the product of disjoint transpositions.

Exercise 5. Prove that every permutation in is the product of transpositions of the form , where . Is this factorization unique?

Exercise 6. Is the inverse of a cycle also a cycle?

Exercise 7. Prove that the representation of a permutation as the product of disjoint cycles is unique except possibly for the order of the factors.

Exercise 8. The order of a permutation is the least integer ( ) such that .

Every permutation has an order.
What is the order of a -cycle?
If is a -cycle, is a -cycle, and and are disjoint, what is the order of ?
Give an example to show that the assumption of disjointness is essential in (c).
If is a permutation of order and if , then is divisible by .

Exercise 9. Every permutation in ( ) can be written as a product, each factor of which is one of the transpositions .

Exercise 10. Two permutations and are called conjugate if there exists a permutation such that . Prove that and are conjugate if and only if they have the same cycle structure. (This means that in the representation of as a product of disjoint cycles, the number of -cycles is, for each , the same as the corresponding number for .)

EXERCISES

Quick Links

Social Media