Thread: Cycles as product of Transpositions:Questions?

I'm trying to know what transpositions really are but having difficulty in understanding them.

Pinter's abstract algebra states that(on pg-79):

"It's a fact that ...every cycle can be expressed as a product of one or more transpositions. In fact:"




Here product means composition.

Then why and how is that a cycle:

can be expressed as

and why



Can anyone kindly tell me what transpositions really are?

Originally Posted by x3bnm

I'm trying to know what transpositions really are but having difficulty in understanding them.

Pinter's abstract algebra states that(on pg-79):

"It's a fact that ...every cycle can be expressed as a product of one or more transpositions. In fact:"




Here product means composition.

Then why and how is that a cycle:

can be expressed as

and why



Can anyone kindly tell me what transpositions really are?

Found the answer.

can be interchanged by definition of transposition.



That's all. Back to where we started from. And that's the answer.

it's easiest to see what is going on with a small number of things to permute.

suppose i have 3 things: A,B and C. they start out in three positions: 1st, 2nd and 3rd.

now i could do a "round-robin" send A to the 2nd position, B to the 3rd position, and C to the first position:

so ABC would become CAB.

now doing that required me to move all 3 objects at the same time. can we do it just with "swaps" (two at a time)?

well, let's try it. since we want C to wind up at the beginning, and A is there now, let's swap A and C:

ABC --> CBA

now we want A in the 2nd position, but B is there now, so we swap B and A:

CBA--->CAB. well, what do you know...it worked.

ok, let's try it with FOUR things:

ABCD. the end result we want to achieve is everything moves one position to the right, except for D, which goes to the beginning:

ABCD --> DABC

and our rule is: we can only exchange "2 at a time". ok, let's swap A and D:

ABCD --> DBCA

now we'll swap A and B (to get A in the 2nd place where we want it):

DBCA --> DACB

next, we'll swap B and C, to get B in the 3rd place where we want it:

DACB --> DABC....and there it is.

this means that: (1 4 3 2) = (2 3)(1 2)(1 4)

note that there are "other ways" we could do this same thing:

we might swap A and D first:

ABCD --> DBCA

then we might swap A and C:

DBCA --> DBAC

then we might swap A and B:

(1 4 3 2) = (1 2)(1 3)(1 4)

(now since (1 2 3 4) = (1 4 3 2)^-1, by the rules of inverses we have: (1 2 3 4) = (1 4)^-1(1 3)^-1(1 2)^-1 = (1 4)(1 3)(1 2) since (a b) is its own inverse).

so the break-down into "swaps" (transpositions) isn't *unique*, but it turns out it's always *possible*: any re-arrangement of a finite number of letters can be done by changing "two at a time".

the method mr. pinter gives is just one of many (and different than the two methods i gave above).

Thanks Deveno.

Originally Posted by Deveno

...
ok, let's try it with FOUR things:

ABCD. the end result we want to achieve is everything moves one position to the right, except for D, which goes to the beginning:

ABCD --> DABC

and our rule is: we can only exchange "2 at a time". ok, let's swap A and D:

ABCD --> DBCA

now we'll swap A and B (to get A in the 2nd place where we want it):

DBCA --> DACB

next, we'll swap B and C, to get B in the 3rd place where we want it:

DACB --> DABC....and there it is.

this means that: (1 4 3 2) = (2 3)(1 2)(1 4)
....

I'm reviving this thread because I've a question.

Sorry for simple question. Deveno, how did you get ?

I'm asking this because (it's a composition so I'm reading from right to left):

According to your reply for if you swap first and fourth place of you get:

Next if you use by swapping first and second place you get

Next for by swapping second and third you get:

So shouldn't ?


Can you kindly tell me how did you get ?

you're confusing cycle notation with "image notation".

by (1 4 3 2) i mean THIS function f:

1-->4
2-->1
3-->2
4-->3

that is (1 f(1) f(f(1)) f(f(f(1)))) = (1 4 f(4) f(f(4))) = (1 4 3 f(3)) = (1 4 3 2), and NOT this function:

1-->1
2-->4
3-->3
4-->2.

let's compose (right-to-left) (13)(1 2)(1 4):

first we do (1 4):

1-->4
2-->2
3-->3
4-->1

next we apply (1 2): (i'll keep the first function on the left so you can see the "original order"):

1-->4-->4
2-->2-->1
3-->3-->3
4-->1-->2

finally, we apply (2 3):

1-->4-->4-->4
2-->2-->1-->1
3-->3-->3-->2
4-->1-->2-->3 so you see the start and end places are the same as the 4-cycle (1 4 3 2).

********

i can understand your confusion, however, because my example is confusing.

you're probably wondering: how does the shuffle ABCD-->DABC get represented by the permutation (1 4 3 2) instead of (4 1 2 3)? write the image below the domain:

ABCD
|| ||
vvvv (imagine these are downward arrows)
DABC

we see A-->D, B-->A,C-->B,D-->C that is A gets mapped to the 4th ELEMENT (although it winds up in the 2nd POSITION).

that is the "image set" (f(1) f(2) f(3) f(4)) isn't the same as the "cycle notation" (1 f(1) f(f(1)) f(f(f(1))), the permutation:



because there are these two different, but similar, ways of looking at permutations, (one focuses on what happens to the domain, the other focuses on what happens to the image) it pays to be very careful about what your notation is saying. because we usually take permutations to be FUNCTIONS, it makes more sense to "focus on the domain", rather than the images (which turns out amounts to looking at the INVERSE permutations).

note that (4 1 2 3) = (1 2 3 4) (it makes more sense if you arrange the numbers 1 through 4 in a circle), and that (1 2 3 4) and (1 4 3 2) are inverses.

Originally Posted by Deveno

you're confusing cycle notation with "image notation".
...
note that (4 1 2 3) = (1 2 3 4) (it makes more sense if you arrange the numbers 1 through 4 in a circle), and that (1 2 3 4) and (1 4 3 2) are inverses.
...

Yes you're right about my confusion. I understand now what you're saying. Thanks for help.