Show that the order of a cycle is Sn is the length of the cy

Show that the order of a cycle is S_n is the length of the cycle. For example, the order of (1234) is 4. What is the order of a product of two disjoint cycles? Begin (of course!) by considering some examples. Note, for instance, that the product of a 2-cycle and a 3-cycle (disjoint) is 6, while the order of the product of two disjoint 2-cycles is 2.

Solution

Consider (1 2 3 5 7)(2 4 7 6) as the product of disjoint cycles

I assume you are composing your permutations from left to right (apply the left permutation first, then the right one.) Some people do it the other way around!

Then you can write the two permutations using the following notation:

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

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

This notation means that the number in the first row of the 2-by-7 array is mapped to the number in the second row just below it. Now rearrange the second array\'s columns so that its top row matches the bottom row of the first array, and write them one on top of the other:

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

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

Now merge them by striking out the two equal middle rows:

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

This array represents the composition or product of the two permutations you started with.

To write this in cycle form, start with the smallest number 1, and see that it is mapped to 4, which is mapped to 7, which is mapped back to 1. That gives you the cycle (1 4 7). Now start with 2, the smallest number not in the previously found cycles, and find its cycle. Continue until all numbers are in a cycle. Put all the cycles together to get the answer. They are all disjoint because at each step you pick a number not in a previously found cycle, and because permutations are one-to-one.

You can do this directly from the product form (1 2 3 5 7)(2 4 7 6) as follows. Start with 1. The first permutation maps 1 to 2, and the second permutation maps that 2 to a 4. Thus together they move 1 to 4. The cycle starts (1 4 ...). Now what happens to the 4? The first permutation leaves 4 alone, and the second maps 4 to 7. Together, 4 maps to 7. Now the beginning of this cycle looks like (1 4 7 ...). How about 7? The first permutation maps 7 to 1 and the second leaves 1 alone, so together 7 maps to 1. That gives you the cycle (1 4 7), as before. Now start with 2, the smallest number not in the previously found cycles, and so on.

Thus order = max(order_1 , order_2)