A Proof of the Reduction Lemma

[Close this window to return to the Main Article.]

Our purpose in this sidebar is to show that our reduction algorithm leads to a proof of

The Reduction Lemma. If is any expression for the identity permutation in terms of k transpositions, k > 0, then there is another expression for e that uses k - 2 transpositions.

Specifically, we will prove that if one applies the algorithm given in Page 7 to a sequence of transpositions equal to the identity permutation e, then one produces a modified truncated sequence also equal to e that has two fewer transpositions. We will work out the proof while visualizing the two-marker-set model of the demonstration program and describing things in the terminology relevant to this model. Note that we interpret our notation in a left-to-right order, which, given the long history of evaluating functions from right to left, is not always done.

Let us denote the original sequence by . We let a be the number of the source box for the first green marker transposition and k the number of the transposition that first returns green marker a to box a. We denote the modified truncated sequence by . Note that, for each i, is the blue transposition defined in response to green transposition . There are no transpositions and because these are the ones that are avoided to make the green modified truncated sequence shorter by two transpositions.

Now we define to be the number of the Tagged Box right after the transpositions and have been performed. We do this for i ’s between 1 and k-1, since the tagging is not needed after transposition k. We can prove by induction that

(*)   For each i between 1 and k-1, after performance of the transposition and the prescribed response with the blue markers,

1. the green marker a (from the First Box) is in the Tagged Box, which is box number ;
   
2. the blue marker a is in the First Box number a;
   
3. whatever number is on the green marker in the First Box is the same as the number on the blue marker in the Tagged Box; and
   
4. all boxes other than the First Box and the Tagged Box contain green and blue markers having the same numbers on them.

This claim is clear for i = 1 since the initial definition of the Tagged Box has this being the box to which marker number a is first moved, making (i) true. There is no transposition of the blue markers in response, so (ii), (iii), and (iv) are clearly true.

Assuming the truth of the claim for an integer r, it follows for r+1. Too see this, let us start by supposing the transposition falls under case 2b of the algorithm. In this case, the green marker a is moved, and the algorithm has the tag moving with it, which makes (i) true. The other box involved in this transposition (its number is as it is the new Tagged Box) had green and blue markers with the same number, and these are both moved to the former Tagged Box numbered . Thus, (iv) remains true. Since the blue marker a is not moved from the First Box, (ii) remains true, and clearly (iii) remains true as well, given that the relevant blue marker moved along with the tag.

Case 2a is the easiest, so the details are left to the reader. Let us consider case 2c. In this case, the transposition of the green marker is of the form (a, b), where b is not the number of the current Tagged Box. The response is to do the transposition (, b) involving the current Tagged Box and box b. Since the green marker in the First Box and the blue marker in the Tagged Box had the same numbers prior to these transpositions, box b has the same number on each of the markers in it following these transpositions. Also, since box b had the same number on the two markers in it prior to the transpositions, it is now the case that the green marker in the First Box number a has the same number as the blue marker in the Tagged Box number  = . These are the relevant changes which, along with the things that remain the same, cause (*) to remain true.

Having seen that the induction step just outlined is true, the claim (*) is verified by induction. The consequence of (*) is that

(**)      For each i from 1 to k-1 inclusive, .

When i = 1, we interpret the right side of the equation as being e. This says that the product of the first i transpositions of the original sequence is always just one transposition away from agreeing with the product of i-1 transpositions . Given our definition of k, we have , which means that . Since by 3 of the algorithm for all i with i > k, clearly , so . We have verified that the modified truncated sequence produced by the algorithm is two transpositions shorter and, like the original, equals the identity permutation.

[Close this window to return to the Main Article.]