Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Adjacent Transpositions of Permutations.

  1. Nov 3, 2008 #1
    Hi,

    Was wondering if anyone could explain to me what an adjacent transposition is (in relation to permutations, cycles etc).

    I know what a transposition is, eg the product of transpositions for (34785) would be (35)(38)(37)(34).
    I don't know what an adjacent transposition is though.

    Cheers in advance.
     
  2. jcsd
  3. Nov 3, 2008 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    An "adjacent transoposition" is just the transposition of two adjacent elements. (23) is an "adjacent transposition" because 2 and 3 are right next to each other (adjacent).
     
  4. Nov 3, 2008 #3
    Thanks, so if I was to express (34785) as the product of adjacent transpositions, would this just be (34) ?
     
  5. Nov 4, 2008 #4
    anyone ?
     
  6. Nov 4, 2008 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    No, of course, not. Why would you think it would reduce to just that? (34785) means "3 changes to 4, 4 changes to 7, 7 changes to 8, 8 changes to 5, and 5 changes back to 3". It is a shorthand for the permutation (12345678)->(12473685). Probably the simplest is just to work from left to right: 1 and 2 are fixed so swap 3 and 4 to get (12435678). Now I need to work that "5" back to the last position so use
    1) (56) to get (12436578)
    2) (57) to get (12436758)
    3) (58) to get (12436785)

    Now (67) is obvious. It gives (12437685). And finally, (37) gives (12473685), the final result. That is, (34785) is given by (34)(56)(57)(58)(67)(37).
     
  7. Nov 4, 2008 #6

    cup

    User Avatar

    Writing a cycle as a product of permutations is easy:

    (34785) = (34)(47)(78)(85)

    But (47) and (85)( =(58) ) are not adjacent, so we rewrite them as:

    (47) = [(56)(45)]-1(67)[(56)(45)] = [(45)(56)](67)[(56)(45)]
    (58) = [(67)(56)]-1(78)[(67)(56)] = [(56)(67)](78)[(67)(56)]

    (Make a drawing to see why this works)

    So:

    (34785) = (34)(45)(56)(67)(56)(45)(78)(56)(67)(78)(67)(56)

    Note: You "follow the permutation" from right to left, in the notation that I use.
     
  8. Nov 4, 2008 #7
    ah, thanks.

    Apologies for my ignorance ;)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Adjacent Transpositions of Permutations.
Loading...