Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/