A Review of Pedagogical Approaches to the Parity Theorem

Sidebar to The Parity Theorem for Permutations
by John O. Kiltinen

I review here the transition in the pedagogical approach to the Parity Theorem over the past forty years. The reference numbers link to the entries in the References at the end of the main article -- use your Back button to return to this page.

Gallian (1998) mentions that the Parity Theorem is due to Cauchy. See Burns (1913) or Kleiner (1986) for background on Cauchy’s role in the development of group theory. Bartlow (1972), in his brief history of the Parity Theorem, gives a reference to Cauchy’s 1815 proof [Cauchy (1815), pp. 98-104], and tells that it is one of Type CJS. (See Table 1 below for the definitions of the categorizations that we are using here.)

As Bartlow points out, permutation groups first came under study because of their relevance to Galois theory, which deals with polynomials over fields, and that gives motivation for the Type P proof, in which one considers the polynomials

The proof rests on the observation that the second polynomial is times the first, depending on whether the permutation a is even or odd. We will call it and its variants Type P proofs.

The Type P proof was once the most common used in textbooks. It is interesting to note that in the 1960s, the writers of the undergraduate texts were not necessarily satisfied with the Type P proof.

Herstein (1964) used this proof in his Topics in Algebra text. He included along with the proof on page 67 the statement,

“Frankly, we are not happy with the proof we give of this fact for it introduces a polynomial which seems extraneous to the matter at hand.”

Closely related to the Type P proof is the Type S proof, which uses the sign or signum of a permutation a defined by taking the quotient of

and observes that this number is according as a is even or odd.

This proof involves similar details, but at least it avoids bringing polynomials into the discussion. However at least one writer who used it gave hints of wishing for something simpler. Hall (1966) included the following statement about this proof:

“The reader may find the remainder of this section difficult to follow. The difficulty lies largely in the notation; the ideas are fairly intuitive, but it is unfortunately not possible to explain them with reasonable rigour without introducing symbolism which makes them appear more difficult than they in fact are. The work is kept as simple as possible and it is well worth while making some effort to understand it.”
Comments such as these had some influence. Spitznagel (1968) quoted Herstein giving a variation of the Type RA proof, as did Liebeck (1969) while giving an incomplete, flawed proof with yet another approach, and also Bartlow (1972), when he gave an historical review and a Type CJs proof, like Cauchy’s original approach. Although Herstein was not satisfied with the proof, he stayed with it over the decades. The same proof is given in the 1975 second edition of Topics in Algebra and in his Abstract Algebra (Herstein, 1986), although he dropped the “not happy” statement in this new textbook.

The dissatisfaction with Type P and Type S proofs of the 1960s and the spate of journal articles that followed led to a major change in the pedagogical approach beginning in the 1980s. We have done a survey of over fifty different abstract algebra and discrete mathematics texts, mostly at the undergraduate level, dating back to the 1960s, and have characterized their approaches to the Parity Theorem. The results are presented in Table 1 below. We note that there has been a trend over the past twenty years toward proofs which stay close to the definition of parity in terms of transpositions.

Type RA (for Reduction Algorithm), the category to which our variant belongs, has been the most favored in recent years. Of the 34 texts in the survey that have first appeared since 1980, 14 (41%) have used this type of proof. Since 1990, seven of the 15 texts appearing for the first time, or 47%, have given a Type RA proof.

Of the 14 post-1980 texts that use a Type RA proof, several represent switches to this type in new editions of earlier books. For example, Fraleigh switched to Type RA in his 1982 third edition, McCoy/Janusz switched in their 1987 fourth edition, and Gallian added this type of proof in his 1990 second edition after having referred the reader to Fraleigh’s second edition for a proof in his first edition. Hillman, Alexanderson, and Grassl give this type of proof in their 1987 discrete mathematics text, which is a switch from the Type P proof in the 1978 Hillman and Alexanderson abstract algebra text. Fraleigh did not stay with Type RA beyond his third edition, switching to Type CJs in his 1989 fourth edition. He has tinkered with his approach a bit in the subsequent fifth and sixth editions.

The paper by Miller (1971) had some influence on bringing the Type RA proof into the mainstream. Saracino (1980) and Fraleigh (1982) cite this paper as the source of this type of proof, and probably other writers have picked up on it from these two texts. However Miller was not the first to find this approach to the Parity Theorem. Spitznagel (1968) does it in essentially the same way, and we see in Brenner (1957) a Type RA proof with a more complex reduction technique.

In fact, Brenner’s method is similar to my approach in that it makes the reduction by dropping two separated transpositions from a sequence which equals the identity, as opposed to two identical and adjacent transpositions gotten by a rewriting of the expression. Given this similarity to our approach, this work of over forty years ago is worthy of some comment.

Brenner observes that if are all distinct, then

That is, the first and last transpositions in the sequence on the left can be dropped. Brenner does not make it clear if he is evaluating from left to right or vice-versa, but the equation is true either way. If one evaluates from left to right as I do, both sides of this equation reduce to the cycle . Evaluating right to left, one gets the inverse of this cycle.

He then goes on to take an assumed odd-length product of transpositions equaling the identity that uses a minimal number of transpositions. He does some Miller-like rewriting of this sequence to get one which has an “initial chain” of distinct entries of the sort that is subject to the reduction above, thus getting a contradiction to the minimality.

His method of dropping a pair of separated transpositions is similar to ours, but it is not as general because it assumes a shared common element between adjacent transpositions.

TABLE 1

A Selection of Abstract Algebra and Discrete Mathematics Texts, 1960 to 2001,
Organized According to Their Approach to the Parity Theorem

Type RA (Reduction Algorithm) proof: Show that the identity is even by reducing by two any expression for it as a sequence of transpositions. Extend to the general result.

• 1980: Dan Saracino, Abstract Algebra: A First Course, Addison-Wesley. [Citation of Miller paper. Same proof in the reissue of this text in 1996 by Waveland Press.]
• 1982: John B. Fraleigh, A First Course in Abstract Algebra, 3rd ed., Addison-Wesley. [Citation of Miller paper.]
• 1982: Charles C. Pinter, A Book of Abstract Algebra, McGraw-Hill Publishing Co. [Same proof in 2nd ed., 1990.]
• 1987: David C. Buchthal and Douglas E. Cameron, Modern Abstract Algebra, Prindle, Weber & Schmidt.
• 1987: Elbert A. Walker, Introduction to Abstract Algebra, Random House, 1987.
• 1987: Abraham P. Hillman, Gerald L. Alexanderson, Richard M. Grassl, Discrete and Combinatorial Mathematics, Dellen Publishing Company. [This is a change from the Hillman-Alexanderson abstract algebra text, which has a Type P proof.]
• 1987: Neal H. McCoy and Gerald J. Janusz, Introduction to Modern Algebra, 4th edition, Allyn and Bacon. [Presumably Janusz is responsible for the switch from a Type P proof in the previous McCoy-only editions.]
• 1990: Thomas W. Hungerford, Abstract Algebra: An Introduction, Saunders College Publishing.
• 1990: Richard A. Dean, Classical Abstract Algebra, Harper and Row Publishers.
• 1990: John A. Beachy and William D. Blair, Abstract Algebra, Prentice Hall. [Also in their second edition published by Waveland Press, Inc., 1996.]
• 1990: Joseph A. Gallian, Contemporary Abstract Algebra, 2nd ed., D. C. Heath & Co, 1990. [Proof added with 2nd edition. Stated without proof in first. Same proof in 3rd ed., D. C. Heath, 1994, and 4th ed., Houghton Mifflin, 1998.]
• 1993: W. Keith Nicholson, Introduction to Abstract Algebra, PWS-Kent Publishing Company. [Same proof in his thicker 2nd edition published by John Wiley and Sons, Inc. in 1999.]
• 1996: Theodore Shifrin, Abstract Algebra: A Geometrical Approach, Prentice Hall.
• 2001: Robert H. Redfield, Abstract Algebra: A Concrete Approach, Addison-Wesley. [A very cumbersome proof that the identity is even.]

and show that the first is plus or minus the second according as a is even or odd.

• 1960: Neal H. McCoy, Introduction to Modern Algebra, Allyn and Bacon. [Same in the 3rd edition in 1975, and presumably also in the 2nd edition in 1968. Changed to Type RA in 1987 4th edition.]
• 1964: I. N. Herstein, Topics in Algebra, Blaisdell Publishing Company. [Same proof in the 2nd edition, Xerox College Publishing, 1975.]
• 1966: Sam Perlis, Introduction to Algebra, Ginn Blaisdell.
• 1972: Neal H. McCoy, Fundamentals of Abstract Algebra, Allyn and Bacon, 1972. [Same as in his thinner 1960 book.]
• 1975: Otto F. G. Schilling and W. Stephen Piper, Basic Abstract Algebra, Allyn and Bacon, 1975. [Proof not presented, but outlined as an exercise.]
• 1978: Abraham P. Hillman and Gerald L. Alexanderson, A First Undergraduate Course in Abstract Algebra, 2nd edition, Wadsworth Publishing Company. [Presumably same proof in first ed. 1973. They also discuss ideas of the Type CJs proof. Stays the same in the 3rd ed., 1983 and 4th ed., 1988.]
• 1983: R. B. J. T. Allenby, Rings, Fields and Groups: An Introduction to Abstract Algebra, Edward Arnold. [Also outlines Type CJs proof in the exercises.]
• 1983: Gertrude Erlich, Fundamental Concepts of Abstract Algebra, PWS-Kent Publishing Company. [Method applied to the show that the identity is even. More than the usual detail given. Type CI proof outlined as an exercise.]
• 1984: Jimmie Gilbert and Linda Gilbert, Elements of Modern Algebra, PWS Publishers. [Same approach in their 2nd edition, 1988 through their 4th edition, 1996.]
• 1986: I. N. Herstein, Abstract Algebra, Macmillan. [Same proof in the posthumous 1990 2nd edition.]
• 1991: R. F. Lax, Modern Algebra and Discrete Structures, Harper Collins Publishers.
• 1991: David S. Dummit and Richard M. Foote, Abstract Algebra, Prentice Hall.
• 1998: Frederick M. Goodman, Algebra: Abstract and Concrete, Prentice Hall. [Done in the exercises.]

Type S (Signum of a permutation) proof: Start with the sign of a permutation defined as the quotient of the expressions

and show that it is according as a is even or odd.

• 1964: W. E. Deskins, Abstract Algebra, Macmillan. [Only done in the exercises in the context of determinants.]
• 1966: F. M. Hall, An Introduction to Abstract Algebra, Cambridge University Press.
• 1970: Jacob K. Goldhaber and Gertrude Ehrlich, Algebra, Macmillan.
• 1970: Garrett Birkhoff & Thomas C. Bartee, Modern Applied Algebra, McGraw-Hill.
• 1984: Charles C. Sims, Abstract Algebra: A Computational Approach, John Wiley and Sons. [Defines the sgn of a permutation, but doesn’t really do much with parity.]
• 1984: Rudolf Lidl and Günter Pilz, Applied Abstract Algebra, Springer-Verlag. [Also in the 2nd ed., 1998.]
• 1987: Larry J. Gerstein, Discrete Mathematics and Algebraic Structures, W. H. Freeman.
• 1988: David M. Burton, Abstract Algebra, William C. Brown Publishers.
• 1993: Franklin D. Petersen, Modern Algebra: A Conceptual Approach, Wm. C. Brown Publishers. [Proof done in the exercises.]
• 1997: D. .S. Malik, John N. Mordeson, M. K. Sen, Fundamentals of Abstract Algebra, McGraw-Hill.

Type CJs (Cycle Joining and Splitting) proof: Looks at the cycle structure for a permutation. Shows that composing with a transposition either merges two cycles or splits two cycles, and changes the Cauchy number (total number moved minus the number of nontrivial cycles) of the permutation by .

• 1973: Larry Joel Goldstein, Abstract Algebra: A First Course, Prentice Hall.
• 1974: Nathan Jacobson, Basic Algebra I, W. H. Freeman and Company. [Same in 2nd edition, 1985.]
• 1989: John B. Fraleigh, A First Course in Abstract Algebra, 4th ed., Addison-Wesley. [Switched from Type RA in 3rd edition, as suggested by David M. Bloom. In the 1994 5th edition, he modified his proof with suggestions made by Eric Wilson, and included in the exercises another proof by David M. Berman, published in 1978, that makes use of “switches” which are transpositions of consecutive numbers. In the 1999 6th edition, he stayed with a CJs proof, but added a proof that uses the determinants of permutation matrices. He eliminated the exercise involving the Berman proof.]
• 1996: Joseph J. Rotman, A First Course in Abstract Algebra, Prentice Hall. [Same in 2nd ed. in 2000.]

Type CI (Counting Inversions) proof: Based upon a count of the number of inversions for a permutation a, which is the number of instances of pairs (i, j) such that i < j while a(i) > a(j). Show that the parity of this count agrees with the parity of the permutation.

• 1965: Seth Warner, Modern Algebra, Prentice Hall.
• 1971: Seth Warner, Classical Modern Algebra, Prentice Hall.

Type D (Determinants) Proof: A proof that relates the parity of a permutation to the sign of the determinant of the related permutation matrix.

• 1991: Michael Artin, Algebra, Prentice Hall.

Type NP (No Proof): The Parity Theorem is stated but not proven.

• 1986: Joseph A. Gallian, Contemporary Abstract Algebra, D. C. Heath & Co. [Added Type RA proof in the 2nd edition.]
• 1987: Norman J. Bloch, Abstract Algebra with Applications, Prentice-Hall.
• 1987: Bernard Kolman and Robert C. Busby, Introductory Discrete Structures with Applications, Prentice Hall.
• 1992: John R. Durbin, Modern Algebra: An Introduction, 3rd ed., John Wiley & Sons, Inc. [Same in 4th ed, 2000. In 2nd edition, 1985, he does not even mention the Parity Theorem.]

[Note: Four discrete mathematics textbooks that were reviewed included no coverage of the Parity Theorem and are therefore not listed.]