In this article, I present a tactile, real-time proof of the Parity Theorem for Permutations.

Permutations on a finite set have been studied for several hundred years because they arise in the solution of problems such as finding roots of polynomials. Indeed, recognition that the set of permutations on a finite set form a group gave rise to the identification of groups as a class of structures worthy of independent study. [See Burns (1913), Cauchy (1815), and Kleiner  (1986) for accounts of this history.]

John O. Kiltinen is Professor of Mathematics at Northern Michigan University.

Because of both their central role in the history of group theory and their applicability, permutations are a standard topic in undergraduate abstract algebra courses and an occasional topic in discrete mathematics courses. The treatment almost always includes the Parity Theorem, which says that S_n, the set of all permutations on the set of integers between 1 and n, divides naturally into two equal sized classes, the even permutations and the odd ones.

A particular permutation is even or odd if it can be expressed using an even or an odd number of transpositions. The Parity Theorem assures that this distinction is meaningful, saying that a permutation cannot be expressed in one way using an even number and in another way using an odd number of transpositions. In abstract algebra texts, this theorem is usually proved.

There are many known proofs of the Parity Theorem. Some of the older ones were “clever” at getting the result from some indirect manifestation of parity, such as the sign of a certain polynomial. In recent years, introductory textbook writers have been gravitating toward proofs that stay closer to the definition of parity based upon transpositions. (A review of over 50 introductory texts published over the the past 40 years shows the trends. It can be found by following this link.)

All the approaches to the Parity Theorem, both old and new, require one to manipulate notation. This is of course what we expect to do in mathematics, but in recent years I have found myself looking for ways to present mathematics via tactile experience whenever possible, since students retain ideas better if they have had some hands-on experience with them.

I like to present permutations from a concrete perspective, modeling them by means of numbered markers being moved among numbered boxes. My earliest low-tech models involved egg cartons with numbered compartments and numbered disks in them, but nowadays, a computerized “high-tech egg carton” provides many advantages. My forthcoming book and software package (Kiltinen, in preparation) will make the approach available to others.

Is it possible to “see” a Parity Theorem proof in real-time as one moves numbered objects between numbered boxes? If so, such a proof would advance the state of the art of making parity understandable to beginning students of abstract algebra or discrete mathematics, giving them a physical, tactile model that renders tangible a rather abstract concept.

My purpose in this paper is to set forth a pedagogically new approach to the Parity Theorem. Like the common one in many recent texts, this approach reduces the problem to showing how an expression for the identity permutation as a sequence of transpositions can be shortened by two transpositions. However it differs in that it rests upon a real-time reduction algorithm rather than an after-the-fact notational one. An extensive search of the literature indicates that this real-time approach is new in the context of teaching this topic.

To support the approach, I have written a computer program that demonstrates the real-time reduction algorithm. The Parity Theorem Demo program is being made available with this paper. (Follow this link to a page from which you can download the program.)

By using the software and the proof algorithm, students will get a more concrete understanding of permutations, relating them to their prior experience with functions in other contexts. The proof based upon the real-time reduction algorithm should be easier to motivate, because it is the sort to which students might gravitate on their own.

A secondary goal of this article is to give the reader the flavor of the hands-on approach to permutations in which this new proof becomes meaningful. It is written with sufficient background to guide a presentation of this topic using the software. Some might find that their students can read and understand the article themselves.

Published December 2001

© 2001 by John O. Kiltinen

Permutations are bijective (one-to-one and onto) functions from a set to itself. When the set is {1, 2, …, n}, then its complete set of permutations is denoted by S_n, which is a group when composition of functions is taken as the operation.

A fundamental fact: Every permutation in S_n can be expressed as the composition of a sequence of transpositions.

A transposition is a very simple permutation that maps two distinct elements of the set to each other and everything else to itself. It can be represented by an ordered pair (a, b), where a and b denote the two elements that map to each other. This is clearly the simplest sort of permutation that there could possibly be, other than the identity permutation, which maps everything to itself.

It is easy to see why the claim in the preceding paragraph is true if one thinks of representing permutations in S_n by using n boxes numbered 1 through n and n similarly numbered markers. We may regard a distribution of the markers into the boxes, with one marker per box, as representing a permutation a in S_n. Specifically, we will think of such a distribution as telling us that a(i) = j when marker number i is to be found in box number j. For example, Figure 1 shows an arrangement of twelve numbered markers in twelve boxes. We will regard this arrangement of the markers as representing the permutation a such that a(1) =  12, a(2) =  5, a(3) =  8, etc.

One could equally well reverse the roles of marker numbers and box numbers in terms of which represents the domain and which the range variables. The representation set forth here reflects a tactile point of view. We think of a function as going from the domain to the range. Thus, we are interpreting a(i) = j as saying that the marker that originally came from box i has gone to box j.

If we think about permutations in this way, then a transposition (a, b) is a permutation represented by the swapping of the contents of two boxes, namely box a and box b. If we compose a sequence of transpositions, then we can represent this by a sequence of steps of swapping pairs of markers between boxes. It does not take very long doing this, or even just thinking about it, before one sees clearly that one can achieve any permutation one wants by a sequence of swaps of markers. Equivalently, one can easily see how one could restore each marker to its home box in Figure 1 by doing a sequence of swaps.

There is no unique way to express a permutation using transpositions. Imagine starting with n numbered boxes and markers with the identity permutation represented by having marker i in box i for each i. Now suppose that you have some target permutation that you want to achieve by means of a sequence of transpositions. Clearly there are many different orders in which you could do your swaps to get there.

In spite of the variability, one feature is constant in this process: the parity of the number of transpositions that are used for a given permutation. Any two expressions for a given permutation in terms of transpositions have the numbers of transpositions used being of the same parity. Stated formally, the Parity Theorem is this:

The Parity Theorem. Suppose that a is a permutation in S_n. If and are two expressions for a as compositions of sequences of k and m transpositions, then either k and m are both even or they are both odd.

One way to prove the Parity Theorem is first to prove the

Even Identity Lemma. If e is the identity permutation in S_n that maps every element to itself, and if where the t_i’s are transpositions, then k is an even number.

Before considering a proof of this lemma, let us show how it leads very directly to a proof of the Parity Theorem. Suppose that we have two expressions, and , for a permutation a in terms of transpositions. Then, since the inverse of a composition of a sequence of permutations is the composition of their inverses in the reverse order, and since every transposition is its own inverse, it follows that

This shows that e can be expressed using k + m transpositions. Once the lemma is established, we will know that k + m is an even number. This assures that k and m are either both even numbers or they are both odd numbers.

One technique for proving the Even Identity Lemma is to prove

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.

Let us first see how this lemma leads to the Even Identity Lemma. The argument is reductio ad absurdum. If there were an expression for e that used an odd number of transpositions, then by applying the Reduction Lemma to this expression, and then repeatedly to the successors, one could eventually get an expression for the identity in terms of one transposition. This is clearly impossible. If we think in terms of our model, if each marker is in its home box and we swap two of them, then these two are no longer in their home boxes.

To prove the Reduction Lemma, one wants to set forth an algorithm for shortening by two transpositions an expression for the identity permutation. The usual approach is to process the notation for such an expression through a series of steps in which one rewrites certain adjacent pairs of transpositions. After following the algorithm repeatedly, it can be argued that eventually an adjacent pair of equal transpositions must occur. This pair then “drops out” because doing a transposition twice is the same as not doing it at all.

Our proof rests upon a reduction algorithm that tells one how to modify a sequence of transpositions step-by-step to produce a different shorter one. With our algorithm, you can be producing the shorter sequence of transpositions simultaneously while someone is producing the original sequence by swapping markers between boxes.

The development to this point is well known. What comes now is new: an approach to the Reduction Lemma based on hands-on experience doing transpositions with objects, not notation. The approach is also supported by a computer program that allows the student to gain experience with the algorithm underlying the proof of the Reduction Lemma. We will postpone stating the rules for the algorithm and its proof until after we explore the algorithm a bit by means of the software.

Figure 2 shows the user interface for our Parity Theorem Demo program. (In the Macintosh implementation, the menu bar shown here is not in the window of the program but instead the menu items shown are included on the main menu bar at the top of the screen.) One sees a set of twelve numbered boxes that contain two sets of numbered markers. The human user of the software performs transpositions on the green markers on the left side. This is done simply by “dragging” a green marker from one box to another with the pointer and with the mouse button depressed. When the drag reaches the destination box and one releases the mouse button, the computer will swap the green markers between the source box and the destination box.

While the human user is performing transpositions with the green markers on the left, the computer is doing the same with the blue markers on the right. In the initial “Human First” mode, the computer reacts to the transpositions that the human user enters by producing a second sequence of transpositions that will ultimately use two fewer of them when all markers are returned to their home boxes. After learning the algorithm, the human user can confirm an understanding of it by switching to “Computer First” mode wherein the computer generates a sequence of transpositions and the human user produces the shorter sequence.

The program is available in versions for both the Macintosh and Windows platforms, and can be downloaded by the interested reader. Detailed online instructions are included and are accessed from the “Help” menu. The program also does an automated demonstration, which the user initiates with a command from the “Action” menu.

Figure 2 gives insight into the shortening algorithm. It reflects the state after the human user has performed four transpositions, namely, (1, 8), (6, 7), (12, 5), and (6, 1) in that order. (Note that the numbers refer to the boxes involved in each swap, not the numbers of the markers being swapped.)

After the first transposition was performed, the computer marked box number 1 as the “First Box” by highlighting its background in gold, and it marked box number 8 as the “Tagged Box” by highlighting its background in beige, but it did no transposition on the blue markers. It responded to the next three transpositions by performing the sequence (6, 7), (12, 5), and (6, 8) on the blue markers.

Note that the human user’s fourth transposition (6, 1) on the green markers moved marker 7 from box 6 into the First Box number 1 and moved green marker 8 out of box 1 and into box 6. The computer avoided a transposition involving the First Box but instead responded by moving blue marker 7 from box 6 into the Tagged Box number 8 while moving marker 8 that had been there into box 6. After these two sequences of transpositions, the arrangements of the green and blue markers are the same except for the ones in the highlighted First and Tagged Boxes. The computer is “ahead of the game,” however, in terms of returning to the identity arrangement because it has its marker in the First Box being the one that is at home there.

The reader may find it useful to try out the demonstration program for a few minutes before reading further. As is the case with most algorithms, one learns this one more easily be seeing it in action than by reading the rules for it.

In the demonstration program, the computer performs a shortening algorithm that is based on a simple idea. Since starts with all markers in their home boxes, performs a sequence of transpositions, and eventually returns every marker to its home box, the first marker moved is eventually going to be brought home. There is a potential for shortening the sequence of transpositions by eliminating the transposition that moves this first marker away and the transposition that moves it back home.

To produce a shortening algorithm built on this idea, all one needs is to devise rules for modifying the sequence of transpositions to adjust for the elimination of the two transpositions we have identified. We will set forth some rules that meet this objective. Building on our hands-on experience with the demonstration program, let us state the rules for the algorithm in terms of the computer’s response with the blue markers to the transpositions that the human user performs with the green markers.

1. When the human does the first swap, the computer does not do one. Instead, it makes note of the first marker the human moved, and labels the box from which it came as the “First Box, ” and tags the other box involved in this swap, and calls it the “Tagged Box”. (The First Box will remain fixed throughout this procedure, but the box designated as the Tagged Box may change.)

2. The computer responds to subsequent swaps of green markers on the left by the human by doing swaps of its set of blue markers on the right, using the following rules:
   
   
   1. If the human’s green swap involves neither the First Box nor the Tagged Box, the computer does its swap between the same two boxes.

   2. If the green swap involves the Tagged Box but not the First Box, the blue swap is between the same two boxes, but the computer also moves the tag, so as to keep it with the green disk from the First Box.

   3. If the green swap involves the First Box but not the Tagged Box, the computer does a swap between the Tagged Box and the other box, not the First, that the human used.

   4. If the green swap involves both the First Box and the current Tagged Box, the computer does not do any swap.

3. Once case d of step 2 has happened -- which it must since the first green marker moved is always in the Tagged Box and the first person is eventually going to bring it back home -- the computer does all subsequent swaps between the same boxes as the human.

If one follows the procedure described here, it will produce a modified truncated sequence of transpositions that has two fewer transpositions at the point that the original sequence returns the first marker moved to its home box. Since the modified truncated sequence is the same as the original one from that point on, it uses two fewer transpositions in the end when each has returned all of the markers to their home boxes.

You may wish to work out the proof that this algorithm leads to the Reduction Lemma on your own, or you can follow this link for a proof.

Since this approach to the Parity Theorem and the supporting demonstration software are new, I have had only one abstract algebra class in which to test it. This limited experience gives some pedagogical insight, however, which others might find helpful.

I used the program in the lecture in which I presented the Parity Theorem to the class. The students were given the software to use on their own computers as they studied the theorem. They were told they would be required to demonstrate their ability to use the algorithm on the mid-semester exam. I tested them by watching them carry out the algorithm with the demonstration software set in the “Computer First” mode, wherein the computer performs transpositions and the human user responds to produce a shorter sequence of transpositions.

The highlighting feature was turned off, so students had to know without the visual cue which box was the fixed First Box and which was the movable Tagged Box. The result was that all eight students in the course were able to demonstrate the ability to carry out the algorithm. Only two of them made a single mistake each, and each corrected the error on a second try.

The students were also told that on the final exam there would be a question asking them to explain why the shortening algorithm leads to a proof of the Parity Theorem. The results here confirm an experienced teacher’s insight that knowing how to perform an algorithm is a different thing from understanding its significance. The students’ responses varied from impressionistic discussions that focused too much attention on the reduction by two transpositions to ones that focused on the appropriate sequence of ideas but left out some important details.

I conclude that this proof offers no royal road to immediate understanding of the proof of the Parity Theorem. However, by giving them an approach that not only stays close to the definition of parity but also builds on hands-on experience, it lays a foundation for deeper understanding for those students who choose to return to the topic looking for mastery. This proof also has advantages for a lower division discrete mathematics course where there is less emphasis on proofs but where an appreciation for algorithms is important.

Bartlow, T. L. (1972), “An Historical Note on the Parity of Permutations,” American Mathematical Monthly, Vol. 79, No. 7, 766-769.

Brenner, J. L. (1957), “A New Proof That No Permutation is Both Even and Odd,” American Mathematical Monthly, Vol. 64, No. 7, 499-500.

Burns, J. E. (1913), “The Foundation Period in the History of Group Theory,” American Mathematical Monthly, Vol. 20, No. 5, 141-148.

Cauchy, A.-L. (1815), “Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égale et de signes contraires par suite des transposition opérées entre les variables qu’elles renferment,” J. de l’École polytechnique, Vol. 10, 29-112; Oeuvres Complètes, ser II. vol. pp. 91-169.

Fraleigh, J. B. (1982), A First Course in Abstract Algebra, 3rd ed., Addison-Wesley.

Gallian, J. A. (1998), Contemporary Abstract Algebra, 4th edition, Houghton-Mifflin.

Gray, E. L. (1963), “An Alternative Proof for the Invariance of Parity of a Permutation Written as a Product of Transpositions,” American Mathematical Monthly, Vol. 70, No. 9, 995.

Hall, F. M. (1966), An Introduction to Abstract Algebra, Cambridge University Press.

Halperin, I. (1960), “Odd and Even Permutations,” Canadian Math. Bulletin, Vol. 3, 185-186.

Herstein, I. N. (1964), Topics in Algebra, Blaisdell Publishing Company.

Herstein, I. N. (1986), Abstract Algebra, Macmillan.

Higgs, D., and P. de Witte, (1979), “On Products of Transpositions and Their Graphs,” American Mathematical Monthly, Vol. 86, No. 5, 376-380.

Kiltinen, J. O. (in preparation), Oval Track and Other Permutation Puzzles (And Just Enough Group Theory to Solve Them), book and software package.

Kleiner, I. (1986), “The Evolution of Group Theory,” Mathematics Magazine , Vol. 59, No. 4, 195-213.

Liebeck, H. (1969), “Even and Odd Permutations,” American Mathematical Monthly, Vol. 76, No. 6, 668.

Miller, W. I. (1971), “Even and Odd Permutations,” American Mathematical Association of Two-Year Colleges Journal, Vol. 5, 32.

Nelson, S. (1987), “Defining the Sign of a Permutation,” American Mathematical Monthly, Vol. 94, No. 6, 543-545.

Phillips, T. W. (1967), “On the Definition of Even and Odd Permutations,” American Mathematical Monthly, Vol. 74, No. 10, 1249-1251.

Saracino, D. (1980), Abstract Algebra: A First Course, Addison-Wesley.

Spitznagel, E. L., Jr., (1968), “Note on the Alternating Group,” American Mathematical Monthly, Vol. 75, No. 1, 68-69.

Weil, C. E. (1964), “Another Approach to the Alternating Subgroup of the Symmetric Group,” American Mathematical Monthly, Vol. 71, No. 5, 545-546.

• A Review of Pedagogical Approaches to the Parity Theorem

   

• A Proof of the Reduction Lemma

   

• A Program to Demonstrate a Reduction Algorithm that Leads to a Proof of the Parity Theorem