Product of Disjoint CyclesDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/