Results 1 to 3 of 3

Math Help - How to decompose a permutation into a product of transpositions

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    64

    How to decompose a permutation into a product of transpositions

    Hi, I kind of know how to do this, but I don't know how my teacher has reached the result he gives us.

    So I have to express (1 2 4 6 3) as a product of transpositions. I got (1,3)(1,6)(1,4)(1,2) or (1,2)(2,4)(4,6)(6,3). However, the answer the teacher gives says: (1,2)(3,4)(4,6)(2,3). But where does that come from?

    I would really appreciate it if you could explain me the procedure he's used... Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,619
    Thanks
    592

    Re: How to decompose a permutation into a product of transpositions

    Hey juanma101285.

    I think the best way to approach this is to apply every transposition one at a time and write down the permutation results for each transposition. Once you do that we can see if you have made a mistake, where it is, what it was, and where the mis-understanding is in that mistake.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,383
    Thanks
    750

    Re: How to decompose a permutation into a product of transpositions

    The short answer is: it doesn't matter. There are many ways to decompose a permutation into transpositions, such a decomposition is NOT unique.

    The method I usually use gave me:

    (1 2 4 6 3) = (3 6)(1 3)(1 4)(1 2) (writing the multiplication "composition-style" i.e., (1 2) gets applied first).

    The method your teacher MAY have used:

    any k-cycle can be viewed as a transposition times a (k-1)-cycle like so:

    (a1 a2 ... ak) = (a1 a2)(a2 a3 ...ak).

    Applied to (1 2 4 6 3), this gives us:

    (1 2 4 6 3) = (1 2)(2 4 6 3).

    We can also write a k-cycle this way:

    (a1 a2 ... ak) = (a2 a3 ... ak)(a1 ak)

    and so (2 4 6 3) = (4 6 3)(2 3), so:

    (1 2 4 6 3) = (1 2)(4 6 3)(2 3) = (1 2)(3 4 6)(2 3) (cycles are usually written with the smallest number first).

    By our first type of decomposition applied to (3 4 6), we find that: (3 4 6) = (3 4)(4 6), so we have:

    (1 2 4 6 3) = (1 2)(3 4)(4 6)(2 3).

    This doesn't mean YOUR decompositions are "wrong". The number and which transpositions it takes to get a k-cycle is not an invariant of the k-cycle, only its PARITY is.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Identity permutation has odd number of transpositions?
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: December 13th 2012, 05:02 PM
  2. Cycles as product of Transpositions:Questions?
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: December 13th 2012, 03:53 AM
  3. [SOLVED] Expressing as a product of transpositions
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: May 19th 2010, 12:33 AM
  4. Replies: 1
    Last Post: January 24th 2010, 11:24 AM
  5. product of transpositions
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: August 7th 2007, 06:03 AM

Search Tags


/mathhelpforum @mathhelpforum