- #1

nomadreid

Gold Member

- 1,677

- 210

- TL;DR Summary
- identity permutation = even # of transpositions proof has two details unclear to me: one, why something shifted to the left can't end up in the first transposition, and why one would end up with two identity transpositions together. Details in main text.

There is a proof that shows by induction (and by contradiction) that the identity permutation decomposes into an even number of transpositions. The proof is presented in the first comment here

https://math.stackexchange.com/ques...itten-as-the-product-of-r-transpositions-then

but I will summarize the arguments in order to emphasize the points, which the source treats as obvious, that are giving me difficulty (even if my exposition isn't as nice as the source's). If someone could unravel these "obvious" points, spelling them out in detail for me, I would be very grateful.

The general idea is this: suppose n transpositions; n=1 and n=2 are easy; the induction hypothesis is assumed true up to n, and then in the n+1st case, either the last two transpositions on the right end of the sequence are identical, reducing the transpositions to n-1, and induction kicks in, or you can use the following identities

(bc)(ab)=(ac)(bc)

(cd)(ab)=(ab)(cd)

(ac)(ab)=(ab)(cd)

i.e., shifting the "a" to the left.

So far, so good.

Here are two points I do not understand.

First, "a" can't end up in the first transposition (on the left of the sequence) because "a" isn't "fixed" by the transposition. This makes it sound as if "a" would necessarily be in the first transposition at the beginning (before the other "a" got shifted). So I'm lost there.

Secondly, since "a" doesn't end up in the first transposition, there must be some x so that you end up with (x,k)(x,k), which would allow the induction to kick in. But why would one end up with (x,k)(x,k)?

Thanks for any rays of light into my fog.

https://math.stackexchange.com/ques...itten-as-the-product-of-r-transpositions-then

but I will summarize the arguments in order to emphasize the points, which the source treats as obvious, that are giving me difficulty (even if my exposition isn't as nice as the source's). If someone could unravel these "obvious" points, spelling them out in detail for me, I would be very grateful.

The general idea is this: suppose n transpositions; n=1 and n=2 are easy; the induction hypothesis is assumed true up to n, and then in the n+1st case, either the last two transpositions on the right end of the sequence are identical, reducing the transpositions to n-1, and induction kicks in, or you can use the following identities

(bc)(ab)=(ac)(bc)

(cd)(ab)=(ab)(cd)

(ac)(ab)=(ab)(cd)

i.e., shifting the "a" to the left.

So far, so good.

Here are two points I do not understand.

First, "a" can't end up in the first transposition (on the left of the sequence) because "a" isn't "fixed" by the transposition. This makes it sound as if "a" would necessarily be in the first transposition at the beginning (before the other "a" got shifted). So I'm lost there.

Secondly, since "a" doesn't end up in the first transposition, there must be some x so that you end up with (x,k)(x,k), which would allow the induction to kick in. But why would one end up with (x,k)(x,k)?

Thanks for any rays of light into my fog.