Results 1 to 7 of 7
Like Tree3Thanks
  • 2 Post By Deveno
  • 1 Post By Deveno

Math Help - Cycles as product of Transpositions:Questions?

  1. #1
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    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:"

    (a_1 a_2 \cdots a_r) = (a_r a_{r-1})(a_r a_{r-2}) \cdots (a_r a_3)(a_r a_3)(a_r a_2)(a_r a_1)


    Here product means composition.

    Then why and how is that a cycle:

    (12345) can be expressed as (54)(52)(51)(14)(32)(41)

    and why

    (12345) = (54)(52)(51)(14)(32)(41)

    Can anyone kindly tell me what transpositions really are?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: Cycles as product of Transpositions:Questions?

    Quote Originally Posted by x3bnm View Post
    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:"

    (a_1 a_2 \cdots a_r) = (a_r a_{r-1})(a_r a_{r-2}) \cdots (a_r a_3)(a_r a_3)(a_r a_2)(a_r a_1)


    Here product means composition.

    Then why and how is that a cycle:

    (12345) can be expressed as (54)(52)(51)(14)(32)(41)

    and why

    (12345) = (54)(52)(51)(14)(32)(41)

    Can anyone kindly tell me what transpositions really are?
    Found the answer.

    (ab) \text{ where } a \text{ and } b can be interchanged by definition of transposition.

    \text{So } (54)(52)(51)(14)(32)(41) = (41) \text{ means }4 \to 1 \text{ but we know } 1 \to 2, (32) \text{ means } 2 \to 3 \text{ and know that } 3 \to 4, (14) \text{ means } 4 \to 1, (51) \text{ means } 1 \to 5 , (52) \text{ means } 5 \to 2 \text{ and because cyclic  } 2 \to 5,  (54) \text{ means } 5 \to 4

    That's all. Back to where we started from. And that's the answer.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,386
    Thanks
    752

    Re: Cycles as product of Transpositions:Questions?

    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 from topsquark and x3bnm
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: Cycles as product of Transpositions:Questions?

    Thanks Deveno.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: Cycles as product of Transpositions:Questions?

    Quote Originally Posted by Deveno View Post

    ...
    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 (1 4 3 2) = (2 3)(1 2)(1 4)?

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

    According to your reply for (1 4) if you swap first and fourth place of (1 2 3 4) you get: (4 2 3 1)

    Next if you use (1 2) by swapping first and second place you get (4 1 3 2)

    Next for (2 3) by swapping second and third you get: (4 1 2 3)

    So shouldn't (4 1 2 3) = (1 2)(1 3)(1 4)?


    Can you kindly tell me how did you get (1 4 3 2)?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,386
    Thanks
    752

    Re: Cycles as product of Transpositions:Questions?

    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:

    \begin{pmatrix}1&2&3&4\\4&1&2&3 \end{pmatrix} = (1\ 4\ 3\ 2)

    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.
    Thanks from x3bnm
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: Cycles as product of Transpositions:Questions?

    Quote Originally Posted by Deveno View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Expressing as a product of transpositions
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: May 19th 2010, 12:33 AM
  2. Replies: 1
    Last Post: January 24th 2010, 11:24 AM
  3. Product of two prime cycles
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: January 13th 2009, 08:28 PM
  4. write (12345) as product of 3 cycles
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 4th 2008, 02:00 PM
  5. product of transpositions
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: August 7th 2007, 06:03 AM

Search Tags


/mathhelpforum @mathhelpforum