Results 1 to 5 of 5
Like Tree2Thanks
  • 1 Post By emakarov
  • 1 Post By Deveno

Math Help - Identity permutation has odd number of transpositions?

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

    Identity permutation has odd number of transpositions?

    Suppose there is a group G of permutation f = \binom{1}{1} of a set A with 1 \in A

    Now this group has identity permutation( \varepsilon) and inverse permutation( f^{-1}) namely: \varepsilon = \binom{1}{1} and f^{-1} = \binom{1}{1}

    But there is a theorem which says that:

    "No matter how \varepsilon is written as a product of transpositions, the number of transpositions is even."

    Now by decomposing \varepsilon to cycle I get a transposition like this:

    (1) = (1 1)

    It consists of a single transposition. So the number of transposition for this identity permutation is odd.


    Can anyone kindly tell me why this example of transposition for identity permutation does not violate the above mentioned theorem?

    And why is my logic wrong here and where am I wrong?
    Last edited by x3bnm; December 13th 2012 at 10:15 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Identity permutation has odd number of transpositions?

    A transposition, by definition (at least in Wikipedia), has to consist of two different elements.
    Thanks from x3bnm
    Follow Math Help Forum on Facebook and Google+

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

    Re: Identity permutation has odd number of transpositions?

    Quote Originally Posted by emakarov View Post
    A transposition, by definition (at least in Wikipedia), has to consist of two different elements.
    Thanks for the answer.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,152
    Thanks
    591

    Re: Identity permutation has odd number of transpositions?

    the type of function you are talking about is called a 1-cycle. all 1-cycles are equal to the identity:

    e = (1) = (1)(2) = (1)(2)(3), etc.

    for example, if f(k) = k, and f(x) = x for all other x except k, then f(x) = x for ALL x.

    since 1-cycles are trivial, they are omitted in cycle decompositions (just as we typically omit e in products, or 0 in sums).

    transpositions are 2-cycles: they are of the form (i j) where i ≠ j. in fact, it is traditional to write them in the form (i j), where i < j (this is handy for making sure lists of transpositions do not contain duplicates).

    this rule is helpful to keep in mind:

    for a k-cycle, if k is odd, the k-cycle is an EVEN permutation: 1 cycles, 3-cycles, 5-cycles, etc. are even permutations.

    if k is even, a k-cycles is ODD. so 2-cycles, 4-cycles, 6-cycles, etc. are all odd permutations.

    quick way to keep it straight:

    e = (1 2)(1 2) <---even (2 transpositions)
    (1 2) <---odd (1 transposition)

    if S is a set with 1 element, there is only ONE possible bijection S-->S, the identity. there ARE no 2-cycles on S, and in this one special case, we have that the even permutations are ALL the permutations, so every permutation can only be written as a product of 0 transpositions, because there AREN'T any transpositions. some of the "general theorems" for permutations groups "break down" at the lower ends:

    S1 has only even permutations, instead of half-and-half.
    S1 and S2 are abelian (and cyclic!). A2 is not generated by 3-cycles (it has none). the automorphism group of S2 is trivial.
    S3: A3 is cyclic (and thus abelian). all of the automorphisms of A3 are outer (the inner automorphisms are trivial, since A3 is abelian)
    S4: A4 is not simple.
    S6: has an outer automorphism (an automorphism that is not of the form x-->gxg-1) <--this is a strange thing.

    these anomalies disappear as long as n is large enough:

    Sn,An are non-abelian
    |An| = (1/2)|Sn|
    An is generated by 3-cycles
    An is simple
    Aut(Sn) = Aut(An) = Sn.

    so when considering symmetric (permutation) groups, it pays to make sure that "n is big enough" (you might have an interesting counter-example).
    Last edited by Deveno; December 13th 2012 at 11:00 AM.
    Thanks from x3bnm
    Follow Math Help Forum on Facebook and Google+

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

    Re: Identity permutation has odd number of transpositions?

    Quote Originally Posted by Deveno View Post
    the type of function you are talking about is called a 1-cycle. all 1-cycles are equal to the identity:

    e = (1) = (1)(2) = (1)(2)(3), etc.

    for example, if f(k) = k, and f(x) = x for all other x except k, then f(x) = x for ALL x.

    since 1-cycles are trivial, they are omitted in cycle decompositions (just as we typically omit e in products, or 0 in sums).

    transpositions are 2-cycles: they are of the form (i j) where i ≠ j. in fact, it is traditional to write them in the form (i j), where i < j (this is handy for making sure lists of transpositions do not contain duplicates).

    this rule is helpful to keep in mind:

    for a k-cycle, if k is odd, the k-cycle is an EVEN permutation: 1 cycles, 3-cycles, 5-cycles, etc. are even permutations.

    if k is even, a k-cycles is ODD. so 2-cycles, 4-cycles, 6-cycles, etc. are all odd permutations.

    quick way to keep it straight:

    e = (1 2)(1 2) <---even (2 transpositions)
    (1 2) <---odd (1 transposition)

    if S is a set with 1 element, there is only ONE possible bijection S-->S, the identity. there ARE no 2-cycles on S, and in this one special case, we have that the even permutations are ALL the permutations, so every permutation can only be written as a product of 0 transpositions, because there AREN'T any transpositions. some of the "general theorems" for permutations groups "break down" at the lower ends:

    S1 has only even permutations, instead of half-and-half.
    S1 and S2 are abelian (and cyclic!). A2 is not generated by 3-cycles (it has none). the automorphism group of S2 is trivial.
    S3: A3 is cyclic (and thus abelian). all of the automorphisms of A3 are outer (the inner automorphisms are trivial, since A3 is abelian)
    S4: A4 is not simple.
    S6: has an outer automorphism (an automorphism that is not of the form x-->gxg-1) <--this is a strange thing.

    these anomalies disappear as long as n is large enough:

    Sn,An are non-abelian
    |An| = (1/2)|Sn|
    An is generated by 3-cycles
    An is simple
    Aut(Sn) = Aut(An) = Sn.

    so when considering symmetric (permutation) groups, it pays to make sure that "n is big enough" (you might have an interesting counter-example).
    Thanks Deveno. I wish I were half as smart as you are. Again thanks.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Identity and Inverse of a Permutation set
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: April 12th 2010, 05:26 AM
  2. Replies: 1
    Last Post: January 24th 2010, 11:24 AM
  3. kth power of permutation equals identity element
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: November 14th 2009, 03:52 PM
  4. transpositions
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 3rd 2008, 03:20 AM
  5. Transpositions
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: August 7th 2007, 10:38 AM

Search Tags


/mathhelpforum @mathhelpforum