Undergrad Prove Even # Transpositions in Identity Permutation w/ Induction & Contradiction

[nomadreid]

TL;DR

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.

 

[pasmith]

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.

We start with the rightmost transposition, which is defined to be (a\,b). As you note, after applying any of the three identities you have listed, the rightmost transposition no longer involves a.

We can continue to apply these rules, obtaining at stage k a product where the rightmost k permutations do not involve a. Either we at some stage encounter a sequence (a\,x)(a\,x) which cancels, or we end up with a appearing in the leftmost transposition and only in the leftmost transposition. But this is impossible, because the product is then not the identity: none of the previous transpositions touched a, so when this last transposition moves a it is never moved back.

Thus the only possibility is that at some stage we encountered a sequence (a\,x)(a\,x), and cancelled two transpositions.

 

[nomadreid]

We start with the rightmost transposition, which is defined to be (a\,b). As you note, after applying any of the three identities you have listed, the rightmost transposition no longer involves a.

We can continue to apply these rules, obtaining at stage k a product where the rightmost k permutations do not involve a. Either we at some stage encounter a sequence (a\,x)(a\,x) which cancels, or we end up with a appearing in the leftmost transposition and only in the leftmost transposition. But this is impossible, because the product is then not the identity: none of the previous transpositions touched a, so when this last transposition moves a it is never moved back.

Thus the only possibility is that at some stage we encountered a sequence (a\,x)(a\,x), and cancelled two transpositions.

Thanks, pasmith, but you have basically rephrased a little the argument as given in the source and in my summary. I am afraid my questions remain unanswered.

Perhaps a concrete example would illustrate. Suppose one starts with the possibility of three transpositions (ef)(cd)(ab). Applying the identity to shift a over, we get (ef)(ab)(cd), and then again (ab)(ef)(cd). Nowhere along the way did we encounter either (ax)(ax) or (a a). Where is my basic misunderstanding?

 

[mathematicsIMA]

okay i understand your confusion. now think it like this if there are n 2-cycles and from which let say one 2-cycle is like (ab) and i know every 2-cycle must be of this type cause we don't count (aa) okay. so now this is only one way to move right to left by starting from rightmost 2-cycle to make it visually better okay so if we move in this way and we don't find any (ba) for (ab) then it will never be identity cause in the end a is still mapped to some c for example. okay now question is why only (ba) but not some other element like (ac), cause will will use our identity there and again make it a single a on left side. but because it is identity it must end somewhere. so it must have a pair (ba) and because this theory ensure that for every (ab) there exist such pair we are done.

 

[WWGD]

Nomad Reid, are you fixing the size $n$ of your matrix here; does the result apply to any $n \times n$ matrix; n=1,2,..( finite $n$ , of course)?

 

[nomadreid]

okay i understand your confusion. now think it like this if there are n 2-cycles and from which let say one 2-cycle is like (ab) and i know every 2-cycle must be of this type cause we don't count (aa) okay. so now this is only one way to move right to left by starting from rightmost 2-cycle to make it visually better okay so if we move in this way and we don't find any (ba) for (ab) then it will never be identity cause in the end a is still mapped to some c for example. okay now question is why only (ba) but not some other element like (ac), cause will will use our identity there and again make it a single a on left side. but because it is identity it must end somewhere. so it must have a pair (ba) and because this theory ensure that for every (ab) there exist such pair we are done.

Thanks, mathematicsIMA. (sorry for the delay in the reply.)

 

[nomadreid]

Nomad Reid, are you fixing the size $n$ of your matrix here; does the result apply to any $n \times n$ matrix; n=1,2,..( finite $n$ , of course)?

WWGD, as far as I see, it should be applicable to any even n. (Sorry for the delay in my reply.)

 

[pasmith]

Thanks, pasmith, but you have basically rephrased a little the argument as given in the source and in my summary. I am afraid my questions remain unanswered.

Perhaps a concrete example would illustrate. Suppose one starts with the possibility of three transpositions (ef)(cd)(ab). Applying the identity to shift a over, we get (ef)(ab)(cd), and then again (ab)(ef)(cd). Nowhere along the way did we encounter either (ax)(ax) or (a a). Where is my basic misunderstanding?

Remember, we want to show that the identity permutation consists of an even number of transpositions. Your example (ef)(cd)(ab) is not the identity permutation.

Applying the identity twice, we end up with (ab)(ef)(cd). That has exactly one transposition which touches a (the leftmost), so cannot be the identity permutation. This is why not finding a pair (a x)(a x) at some stage is a contradiction: if we don't find that, then what we started with was not the identity.

 

[nomadreid]

Super, pasmith! Thanks very much for finding the error in my example. This is a tremendous help.