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

Permutations and Transpositions

  1. Dec 5, 2004 #1
    Can someone help me? I need to prove that for m>=2, m permutations can be written as at most m-1 transpositions. I can't figure this out for the life of me! thanks in advance :confused:
     
    Last edited: Dec 5, 2004
  2. jcsd
  3. Dec 5, 2004 #2

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    I don't think this is right. Say m = 2, so we have 2 permutations. Since a transposition is a permutation, we can have, say:

    (1 2)(3 4)

    There's m (2) permutatitions (specifically, they are transpositions, but transpositions are permutations). They can't be written in m-1 (1) transposition. I assume you meant something else by "m transpositions" but I'll let you clarify.
     
  4. Dec 5, 2004 #3
    ok...I had found one that said m>=2 but another for m>=3. Let's go with 3....then for instance (1 3 2) for S_5 can be written as a product of at most 2 transpositions...i.e. (1 3)(1 2) or a couple of others. I see this...but I can't figure how to prove for the nth term.
     
  5. Dec 5, 2004 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    samething there though:

    (12)(34)(56)

    Do you mean a cycle of length m (an m cycle?)
     
  6. Dec 5, 2004 #5
    yes...I suppose I mean a cycle of length m....that would be the m permutations I think. I'm really floundering when it comes to this permutation stuff...thanks.
     
  7. Dec 5, 2004 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    "m permutations" isn't an m-cycle. It is, well, m permutations, and to be honest is a strange phrase, hence why I clarified what you might want.
     
  8. Dec 5, 2004 #7
    This probelm is from Fraleigh's 4th ed....stated as follows
    Prove the following about S_n if n>=2.
    Every permutation in S_n can be written as a product of at most n-1 permutations.

    The m permutations phrase I picked up while trying to get more information about this idea. Maybe it's wrong?
     
  9. Dec 5, 2004 #8

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Hmm, what on earth does it define as "a permutation"?

    What you wrote makes no semantic sense to me at all. (Yes, I am a group theorist part of the time).

    A permutation is an element of S_n. It is writable as a single permutation: itself. The product of permutations is a permutation, hence the oddity in this question.

    Every cycle of length m can be written as a product of m-1 transpositions. Every permutation in S_n can be written as a product if disjoint cycles - at most floor(n/2) of them if we discount trivial cycles, n if we allow trivial cycles and the identity as the permutation in question, and n-1 if we mean a non-trivial permutation and allow trivial cycles in its decomposition.

    Is what you've written word for word the exact phrase that appears in the book?
     
  10. Dec 5, 2004 #9
    yep...word for word...now the book defines a transposition as "a cycle of length 2"...so I guess the problem might be saying to show that the most 2-cycles a permutation can have is m-1...is that right?
     
  11. Dec 5, 2004 #10
    oh and the book defines a permutation as a one to one function from a group A onto A.
     
  12. Dec 6, 2004 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Hopefully the book actually defines a permutation as a bijection on a *finite* set, and not a group.

    The permutations of a set are a group. Compose two permutations and get another one (closure) thus it makes little sense to write "can be written of the product of at most n-1" permutations. It is a permutation itself.... I mean it's as silly as asking: show that a number can be written as a product of at most n-1 other numbers.

    Here is a question that may make some sense: Show that evey element in S_n can be written as the product of n-1 or fewer transpositions.

    Saying "most" really makes little sense: the permutations (12) and (34)(12)(34 are the same - there is no maximum.
     
  13. Dec 6, 2004 #12
    hmmm..ok..that makes a little more sense to me. Maybe I can try to look at this prob again and see what I can get. Thanks for being so patient...this group theory is kicking my b**t ; )
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Permutations and Transpositions
Loading...