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

In summary, the identity permutation = even # of transpositions proof has two details that are unclear: one, why something shifted to the left can't end up in the first transposition, and two, why one would end up with two identity transpositions together. The source treats these as obvious, but they are giving difficulty. A concrete example is used to illustrate the confusion.
  • #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.
 
Mathematics news on Phys.org
  • #2
nomadreid said:
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 [itex](a\,b)[/itex]. As you note, after applying any of the three identities you have listed, the rightmost transposition no longer involves [itex]a[/itex].

We can continue to apply these rules, obtaining at stage [itex]k[/itex] a product where the rightmost [itex]k[/itex] permutations do not involve [itex]a[/itex]. Either we at some stage encounter a sequence [itex](a\,x)(a\,x)[/itex] which cancels, or we end up with [itex]a[/itex] 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 [itex]a[/itex], so when this last transposition moves [itex]a[/itex] it is never moved back.

Thus the only possibility is that at some stage we encountered a sequence [itex](a\,x)(a\,x)[/itex], and cancelled two transpositions.
 
  • #3
pasmith said:
We start with the rightmost transposition, which is defined to be [itex](a\,b)[/itex]. As you note, after applying any of the three identities you have listed, the rightmost transposition no longer involves [itex]a[/itex].

We can continue to apply these rules, obtaining at stage [itex]k[/itex] a product where the rightmost [itex]k[/itex] permutations do not involve [itex]a[/itex]. Either we at some stage encounter a sequence [itex](a\,x)(a\,x)[/itex] which cancels, or we end up with [itex]a[/itex] 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 [itex]a[/itex], so when this last transposition moves [itex]a[/itex] it is never moved back.

Thus the only possibility is that at some stage we encountered a sequence [itex](a\,x)(a\,x)[/itex], 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?
 
Last edited:

Similar threads

  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
4
Views
4K
Replies
5
Views
1K
  • Math Proof Training and Practice
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
Replies
13
Views
2K
  • General Math
Replies
11
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
Replies
4
Views
1K
Back
Top