Thread: Permutations, groups, cycles

Hi.

I want to achieve this permutation:


1 2 3 4 5 6 7 8 9
7 3 6 2 8 4 9 5 1

That is two line notation.




But I can't get it right, here's my best permutation, I mean effort:


1 7 2 3 6 4 8 5 9




But...with that I get these cycles;


1 -> 7
2 -> 3
3 -> 6
4 -> 8 wrong
5 -> 9 wrong
6 -> 4
7 -> 2 wrong
8 -> 5
9 -> 1


I have 3 cycles wrong. I have tried many variations, for example;


(1 7 2) (3 6 4 8 5 9)
(1 7 3 6 4 2 8 5 9)
(1 7 2 3 6 ) (4 8 5 9)


But no, I just can't get it right.




And this shorter one is really close:


I want to achieve this:


1 2 3 4 5
2 1 4 3 5


Here is my best permutation:


(1 2) (3 4 ) ( 5 ) and that will be:


1 2 3 4
2 1 4 3


But 5 is missing after 4. How I get that 5 so that will be;

1 2 3 4 5
2 1 4 3 5



I would really appreciate help.

Originally Posted by RiverAlex

Hi.

I want to achieve this permutation:


1 2 3 4 5 6 7 8 9
7 3 6 2 8 4 9 5 1

That is two line notation.




But I can't get it right, here's my best permutation, I mean effort:


1 7 2 3 6 4 8 5 9




But...with that I get these cycles;


1 -> 7
2 -> 3
3 -> 6
4 -> 8 wrong
5 -> 9 wrong
6 -> 4
7 -> 2 wrong
8 -> 5
9 -> 1


I have 3 cycles wrong. I have tried many variations, for example;


(1 7 2) (3 6 4 8 5 9)
(1 7 3 6 4 2 8 5 9)
(1 7 2 3 6 ) (4 8 5 9)


But no, I just can't get it right.




And this shorter one is really close:


I want to achieve this:


1 2 3 4 5
2 1 4 3 5


Here is my best permutation:


(1 2) (3 4 ) ( 5 ) and that will be:


1 2 3 4
2 1 4 3


But 5 is missing after 4. How I get that 5 so that will be;

1 2 3 4 5
2 1 4 3 5



I would really appreciate help.

Try to follow the diagram. There should be three disjoint cycles. The order of the cycles does not matter because disjoint cycles commute.

Attachment 24957

Follow each color until you get back to its starting point.

let's write your permutation as a function f: {1,2,3,4,5,6,7,8,9} → {1,2,3,4,5,6,7,8,9}. so

f(1) = 7
f(2) = 3
f(3) = 6
f(4) = 2
f(5) = 8
f(6) = 4
f(7) = 9
f(8) = 5
f(9) = 1.

it should be clear that our cycle decomposition should start:

(1 7......) since f(1) = 7. what should be the next number? f(7). what is f(7)? looking above, we see that f(7) = 9. so we continue:

(1 7 9 ....)

now, we need to find f(9). and f(9) = 1, so we have our first "cycle" (a 3-cycle), so we have:

(1 7 9)(2......

and what is f(2)? f(2) = 3, so our 2nd cycle begins like this:

(1 7 9)(2 3 ....)

we have to look up f(3), now, and we find that f(3) = 6. next will be f(6), and we see that f(6) = 4. finally, we see that f(4) = 2, which "closes" our 2nd cycle:

(1 7 9)(2 3 6 4)

so...which numbers aren't listed? 5 and 8, right? so we start out 3rd cycle as:

(1 7 9)(2 3 6 4)(5 ....)

now f(5) = 8, and f(8) = 5, so we finish with a 2-cycle, and we're done:

(1 7 9)(2 3 6 4)(5 8).

*************

for your 2nd problem:

(1 2)(3 4) = (1 2)(3 4)(5), since all 1-cycles are the identity (why?)

Thank you TheEmptySet. But Great thanks to Deveno!
That was really good explanation, and
it helped me to understand. I tried, before your answer, those three disjoint cycles, but
they were wrong.

You asked why all 1-cycles are the identity. Well, because 1-cycle build its own cycle, for example (5).


I have one more question.

First;
Sign of a permutation s can be defined from its decomposition into the product of transpositions as
sgn(s) = (-1)^m

(-1)^m, where m means the number of transpositions in the decomposition. I am sure you know.


so, I wonder that how many changes ( and what they are ) are in this same permutation:

1 2 3 4 5 6 7 8 9
7 3 6 2 8 4 9 5 1


I have thought this over many times and this is my solution:

(2 7), (1 2), (2 3), (3 6), (4 5), (7 9).

I believe those are correct and that there are six changes. ? Thus, (-1)^6.

-----------------------
I believe you're reading right to left. So 4->5 according to your product of transpositions, but 4->2 according to your permutation.

-----------------------
A useful fact is that .

Thus once you've broken a permutation into cycles (which might seem confusing now, but becomes very easy with a bit of experience), you can use that fact to break each of those cycles into transpositions, and hence the whole permutation into a product of transpositions. It also means that a cycle's parity is one different than its length, which makes detemining the sign of the permutation easy once you've broken it down into cycles.

-----------------------
An important observations is that, when a permutation is written as a product of transpoitions, the number of transpositions is *NOT* fixed. What IS fixed is the parity (i.e. even or odd) of the number of transpositions (that's a theorem). You said you thought your permutation was a product of 6 transpositions. The number 6 doesn't matter there - what matters is that 6 is EVEN. The immediate content of saying you've written a permutation as a product of 6 transpositions is that your permutation is EVEN.

And that's why you see, and it's meaningful, this:

A permutation might be written as a product of 5, or 213, transpositions. What matters is that number is odd, so you get the same result, -1, when you raise -1 to a power that's the number of transpositions, no matter which of the many ways you discover to write it as a product of transpositions.

-----------------------
Another methodical way to write a permutation as a product of transpositions is to "send each one home" via a transposition. This is easiest to explain by showing an example:
Let p = your permutation. Then p sends 1 to 7, so send 1 back home by mutliplying after p by the transposition (1 7):
Then (1 7)p sends 1 to 1.
Now send 2 home. See that (1 7)p sends 2 to 3, so (2 3)(1 7)p sends 2 to 2.
Now send 3 home. See that (2 3)(1 7)p sends 3 to 6, so (3 6)(2 3)(1 7)p sends 3 to 3.
Now send 4 home. See that (3 6)(2 3)(1 7)p sends 4 to 6, so (4 6)(3 6)(2 3)(1 7)p sends 4 to 4.
Now send 5 home. See that (4 6)(3 6)(2 3)(1 7)p sends 5 to 8, so (5 8)(4 6)(3 6)(2 3)(1 7)p sends 5 to 5.
Now send 6 home. See that (5 8)(4 6)(3 6)(2 3)(1 7)p sends 6 to 6, so no change required, as 6 is already home.
Now send 7 home. See that (5 8)(4 6)(3 6)(2 3)(1 7)p sends 7 to 9, so (7 9)(5 8)(4 6)(3 6)(2 3)(1 7)p sends 7 to 7.
Now send 8 home. See that (7 9)(5 8)(4 6)(3 6)(2 3)(1 7)p sends 8 to 8, so no change required, as 8 is already home.
Now send 9 home. See that (7 9)(5 8)(4 6)(3 6)(2 3)(1 7)p sends 9 to 9, so no change required, as 9 is already home.
(Whew - If 9, the last one, weren't already home, it would mean that I screwed up - because there's nothing left for 9 to switch with. Everything else is already home. If this has been done without any blunders, then the last one at the last stage is guaranteed to already be home.)

So it should be that (7 9)(5 8)(4 6)(3 6)(2 3)(1 7)p = identity. You can mentally check for yourself as I just did that it is.

Thus p = inverse of [ (7 9)(5 8)(4 6)(3 6)(2 3)(1 7) ] = (1 7)(2 3)(3 6)(4 6)(5 8)(7 9). Again, you can mentally check that it equals p.

if you have a permutation p expressed as a product of DISJOINT cycles, there is a trick you can use to easily calculate sgn(p).

first of all, sgn is a homomorphism, which means that:

sgn(ps) = sgn(p)sgn(s).

next, note we can write any k-cycle:



thus if s is a k-cycle, sgn(s) = (-1)^k-1.

so if k is ODD, s is an EVEN permutation, if k is EVEN, s is an ODD permutation

(the easy way to remember this is that 1-cycles (the identity) and 3-cycles are even, and single transpositions (2-cycles) are odd).

ok, so if p = (1 7 9)(2 3 6 4)(5 8), we have:

sgn(p) = sgn((1 7 9))sgn((2 3 6 4))sgn((5 8)) = even*odd*odd = even, or more explicitly:

sgn((1 7 9)) = (-1)² = 1
sgn((2 3 6 4)) = (-1)³ = -1
sgn((5 8)) = -1, so

sgn(p) = (1)(-1)(-1) = 1, so p is even.

explicitly, we can write p as a product of transpositions (one way out of many possible other ways):

p = (1 7 9)(2 3 6 4)(5 8) = (1 9)(1 7)(2 4)(2 6)(2 3)(5 8).

counting the transpositions in the decomposition above, we have 6, so p is even.

Thank you Johnsomeone and Deveno! You both explained things really well! Yes, indeed. Many thanks to you.
Your answers are really useful. I also found 20 inversions and that is (-1)^20 = 1.