Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Discrete Math
College Modern Algebra
High School Discrete Mathematics
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search