Permutations (Pt.V Transpositions and the Sign of a Permutation)
Point of post: This post (which will undoubtedly spill over into continuations) will discuss the last topic in this sequence of posts on permutations. Namely, we will be discussing the concepts of permutations and the real goal (for our linear algebraic purposes) the sign of a permutation.
Up until this point we’ve found a relatively simple class of permutations, cycles, for which every permutation can be written as a product of them. We take this one step further and show that every cycle can be written as the product of cycles of length 2, or transpositions. Mathematically the sign of a permutation can be thought of as the answer to the hypothetical question “if is a function such that the interchanging of any two of it’s arguments results in negative the original (e.g. ). Then, if is or ?”. Another way to think about it is this. Suppose that we had a regular -gon in the plane whose “front” is colored red and whose “back” is colored green. Suppose that the vertices are labeled . Then, we could imagine switching two of the vertices by “flipping” the over the line perpendicular to the line connecting those two vertices. But, we see that in the process we’ve now exposed the green side of . Switching two more vertices results in another flip so that now the red side is exposed. If we permuted the vertices to the configuration the sign of the permutation will tell us whether the red or green side of is showing.
A cycle is called a transposition if is of length two, in other words if . Intuitively a transposition is the process of switching just two objects and leaving the rest fixed. The first interesting thing we notice about transpositions is that every (non-trivial) cycle can be written as the product of them. Indeed:
Theorem: Let , then
Proof: Evidently the it suffices to show that the two agree on (since they both leave elements, if there are any, not in unchanged. So, we merely note that if
and if then
The conclusion follows.
Corollary: Every non-trivial permutation may be written as the product of transpositions.
Remark: This enables us to lend credence to the idea that every permutation can be made by making successive “switches”.
We next note that every transposition is it’s own inverse. Indeed, if then
Thus, we are left with the appealing result that if is given by then
Remark: Intuitively this says that you can undo a permutation that you did in successive switches by undoing the switches in the reverse order in which you performed them.
So, just as with cycles we wonder what the corresponding permutation matrices look like, and in particular (as we shall see why) what their determinant is.
Theorem: Let be a transposition, then if is the associated permutation matrix is the identity matrix with columns and switched.
Proof: We can describe the matrix resulting from switching the and columns of as where
but noting that if we have that and . Thus, with this in mind the above may be written equally well as
from where it immediately follows that .
Corollary: If is a transposition then .
Proof: This follows from elementary matrix analysis where it’s proven that interchanging the rows of a matrix changes the sign of the determinant. Thus, .
We are now prepared to prove the theorem for which all of these posts has been building up to, namely that a permutation cannot be written both as an even and odd amount of polynomials. In other words, it says that if then you can’t have and .
Theorem: Let , then cannot be written as both an even and odd amount of transpositions.
Proof: Suppose that
and thus remembering that the determinant is a multiplicative function
which is a contradiction. Thus, it follows that may not be written as both and even and odd amount of transpositions.
With this theorem we may unambiguously define the sign of the permutation , denoted , to be if the permutation may be written as an even number of transpositions and if it can be written as an odd number of transpositions. Unsurprisingly if we call the permutation even and if we call it odd. In fact, the above shows the following corollary:
Believe it or not, the main purpose for considering permutation matrices was to make the above proof nice. The usual way to do this uses an ugly induction or sketchy counting technique. The above is clean-cut and intuitive. Also, the above corollary now allows us to give a very quick proof of the following:
Theorem: Let , then
Proof: This follows from the corollary since .
1. Dummit, David Steven., and Richard M. Foote. Abstract Algebra. Hoboken, NJ: Wiley, 2004. Print.
2. Fraleigh, John B., and Victor J. Katz. A First Course in Abstract Algebra. Boston: Addison-Wesley, 2003. Print.