Product of Disjoint Cycles

Date: 10/16/98 at 06:51:43
From: Joey Pelayo
Subject: Cycle decomposition

How do I express (1 2 3 5 7)(2 4 7 6) as the product of disjoint 
cycles?

I computed (1 2 3 5 7)(2 4 7 6) = (2 4 6 1 3). This is what I tried, 
but how do I express it as a product of disjoint cycles?

Date: 10/16/98 at 11:10:17
From: Doctor Rob
Subject: Re: Cycle decomposition

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.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/