You are here

Parity Theorem for Permutations

John O. Kiltinen

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

John O. Kiltinen, "Parity Theorem for Permutations," Convergence (December 2004)