# Identity permutation has odd number of transpositions?

• Dec 13th 2012, 09:09 AM
x3bnm
Identity permutation has odd number of transpositions?
Suppose there is a group $\displaystyle G$ of permutation $\displaystyle f = \binom{1}{1}$ of a set $\displaystyle A$ with $\displaystyle 1 \in A$

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

But there is a theorem which says that:

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

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

$\displaystyle (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?
• Dec 13th 2012, 10:13 AM
emakarov
Re: Identity permutation has odd number of transpositions?
A transposition, by definition (at least in Wikipedia), has to consist of two different elements.
• Dec 13th 2012, 10:16 AM
x3bnm
Re: Identity permutation has odd number of transpositions?
Quote:

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

• Dec 13th 2012, 10:57 AM
Deveno
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).
• Dec 13th 2012, 05:02 PM
x3bnm
Re: Identity permutation has odd number of transpositions?
Quote:

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:

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.