Thread: Identity permutation has odd number of transpositions?

Suppose there is a group of permutation of a set with

Now this group has identity permutation( ) and inverse permutation( ) namely: and

But there is a theorem which says that:

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

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



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?

A transposition, by definition (at least in Wikipedia), has to consist of two different elements.

Originally Posted by emakarov

A transposition, by definition (at least in Wikipedia), has to consist of two different elements.

Thanks for the answer.

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:

S₁ has only even permutations, instead of half-and-half.
S₁ and S₂ are abelian (and cyclic!). A₂ is not generated by 3-cycles (it has none). the automorphism group of S₂ is trivial.
S₃: A₃ is cyclic (and thus abelian). all of the automorphisms of A₃ are outer (the inner automorphisms are trivial, since A₃ is abelian)
S₄: A₄ is not simple.
S₆: 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:

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

so when considering symmetric (permutation) groups, it pays to make sure that "n is big enough" (you might have an interesting counter-example).

Originally Posted by Deveno

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:

S₁ has only even permutations, instead of half-and-half.
S₁ and S₂ are abelian (and cyclic!). A₂ is not generated by 3-cycles (it has none). the automorphism group of S₂ is trivial.
S₃: A₃ is cyclic (and thus abelian). all of the automorphisms of A₃ are outer (the inner automorphisms are trivial, since A₃ is abelian)
S₄: A₄ is not simple.
S₆: 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:

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

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.