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,665
203
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:

1. What is a transposition in mathematics?

A transposition in mathematics is an operation that swaps two elements in a set or permutation, while leaving all other elements unchanged. In the context of identity permutation, a transposition would swap two elements in the permutation while keeping the identity element (usually denoted as e) in the same position.

2. What is the identity permutation?

The identity permutation is a permutation that leaves all elements in a set unchanged. In other words, it is a permutation that maps each element to itself. The identity element (e) is usually denoted as the first element in the permutation.

3. How can induction be used to prove that all even # transpositions in identity permutation result in the identity permutation?

Induction is a mathematical proof technique that involves proving a statement for a base case, and then showing that if the statement holds for a particular case, it also holds for the next case. To prove that all even # transpositions in identity permutation result in the identity permutation, we can use induction by showing that the statement holds for the base case of one transposition, and then showing that if the statement holds for n transpositions, it also holds for n+2 transpositions.

4. What is the contradiction method in mathematical proofs?

The contradiction method is a proof technique that involves assuming the opposite of what we want to prove and showing that it leads to a contradiction. In the context of proving that all even # transpositions in identity permutation result in the identity permutation, we can use the contradiction method by assuming that there exists an even # of transpositions that do not result in the identity permutation, and then showing that it leads to a contradiction.

5. How does the proof of even # transpositions in identity permutation relate to real-world applications?

The proof of even # transpositions in identity permutation may seem abstract, but it has real-world applications in fields such as computer science and cryptography. In computer science, it is used in algorithms for sorting and shuffling data. In cryptography, it is used in encryption techniques to ensure that data remains unchanged during the encryption process.

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
  • General Math
Replies
11
Views
2K
Replies
13
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
Replies
4
Views
1K
Back
Top