Cycle type of non-disjoint permutation

Printable View

June 4th 2009, 05:32 AM
knarQ

Cycle type of non-disjoint permutation

What is the cycle type of the permutation $(1265)(1365)(2346) \in S6$ ? I feel kind of stupid, but I have no clue.
June 4th 2009, 05:58 AM
TheAbstractionist

Quote:

Originally Posted by knarQ

What is the cycle type of the permutation $(1265)(1365)(2346) \in S6$ ? I feel kind of stupid, but I have no clue.

$(1\,2\,6\,5)(1\,3\,6\,5)(2\,3\,4\,6)\ =\ (1\,3\,4)(2\,5).$ (Note that the permutation fixes 6.) Do you know how to work this out?
June 4th 2009, 06:22 AM
knarQ

I'm afraid I don't. :(
June 4th 2009, 07:58 AM
amitface

Quote:

Originally Posted by TheAbstractionist

$(1\,2\,6\,5)(1\,3\,6\,5)(2\,3\,4\,6)\ =\ (1\,3\,4)(2\,5).$ (Note that the permutation fixes 6.) Do you know how to work this out?

EDIT: This is wrong: I multiplied from left to right rather than from right to left.
Correct me if I'm wrong, but shouldn't it be
$(1~3~2~5~4~6)$

as we have:

$1\mapsto 2\mapsto 2 \mapsto 3$

$3\mapsto 3\mapsto 6 \mapsto 2$

$2\mapsto 6\mapsto 5 \mapsto 5$

$5\mapsto 1\mapsto 3 \mapsto 4$

$4\mapsto 4\mapsto 4 \mapsto 6$

$6\mapsto 5\mapsto 1 \mapsto 1$

?
June 4th 2009, 08:15 AM
knarQ

I still don't get it. I know that the cycle type for a disjoint permutation, say $(1\,2)(3\,4\,5\,6)$ is $[2^1\,4^1]$ , but how does it work for this non-disjoint one?
June 4th 2009, 08:23 AM
amitface

EDIT: This is incorrect.

You can write the non-disjoint one as a disjoint one using the method that I described above.

So assuming I didn't make any serious mistakes, we'd have:

$(1\,2\,6\,5)(1\,3\,6\,5)(2\,3\,4\,6)\ =(1~3~2~5~4~6)$ ,

and you can find the cycle type of that permutation.
June 4th 2009, 08:28 AM
amitface

I apologize. I multiplied incorrectly. The Abstractionist had it right. You should still be able to find the cycle type from his answer though.
June 4th 2009, 10:25 AM
knarQ

Quote:

Originally Posted by TheAbstractionist

$(1\,2\,6\,5)(1\,3\,6\,5)(2\,3\,4\,6)\ =\ (1\,3\,4)(2\,5).$ (Note that the permutation fixes 6.) Do you know how to work this out?

Ok, so the cycle type would be $[3^1\,2^1\,1^1]$ ?

Next i would like to write that same permutation $(1\,2\,6\,5)(1\,3\,6\,5)(2\,3\,4\,6)$ as a product of transpositions. My Biggs book explains this quite poorly so any help is appreciated.
June 4th 2009, 11:06 AM
Gamma

All you need to do is multiply these cycles out, and I think that is the problem, I am guessing you are not used to cycle notation. It can be a little confusing at first, but in the end it is waaay faster. The thing to remember is that each individual thing inside of parentheses is a permutation, which is a function that simply rearranges the set of n objects. The operation in $S_n$ is function composition. As with normal functions for some reason we compose from right to left $g \circ f (x)=g(f(x))$ . You do f first, and then g which seems backwards as we read left to right.

Anyway, the point is within each set of () you read left to right, but you do the permutations from right to left.
(1 2 6 5)(1 3 6 5)(2 3 4 6)

Start with 1 and see where it goes. (2 3 4 6) does not affect 1, so carry on to the next one we see (1 3 6 5) $1 \rightarrow 3$ because 3 follows the 1. Now check to see what (1 2 6 5 ) does to 3... nothing, so this whole set of three cycles takes 1 to 3.

$1\rightarrow 3$

Now you check to see what happens to 3.
(2 3 4 6) takes 3 to 4.
(1 3 6 5) does not affect 4
(1 2 6 5) does not affect 4

Thus we get overall
$3 \rightarrow 4$

Now check on 4
$4\rightarrow 6 \rightarrow 5 \rightarrow 1$
This completes the cycle, so write ( 1 3 5 ) as the Abstractionist pointed out.

Now the smallest number not included in this cycle is 2, check and see what happens to 2.
$2 \rightarrow 3\rightarrow 6\rightarrow 5$
Now see what happens to 5.
$5 \rightarrow 5 \rightarrow 1\rightarrow 2$
This completes the cycle so write (2 5)

The only one missing is 6, so check on this.
$6\rightarrow 1 \rightarrow 6$ so it is fixed as he points out.

So you are left with the final disjoint cycle decomposition theAbstractionist gave you:

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

It can be shown this disjoint cycle decomposition is unique up to reordering (disjoint cycles commute) and up to cycling within each cycle [(1 2 3) = (2 3 1)= (3 1 2)]. So you will see this cycle type is perserved. In fact the cycle type is even perserved under conjugation.