1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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...