Sidebar to *The Parity Theorem for Permutations*

by John O. Kiltinen

by John O. Kiltinen

[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

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, **

**the green marker***a*(from the First Box) is in the Tagged Box, which is box number ;

**the blue marker***a*is in the First Box number*a*;

**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**

**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.]