## 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.

*Motivation*

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.

*Transpositions*

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

and

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 a*nd *.

**Theorem: ***Let , then cannot be written as both an even and odd amount of transpositions.*

**Proof: **Suppose that

and

Then,

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:

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

**References:**

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.

[…] definitions for the sign of a permutation and show that they’re equivalent to the one given here. Namely, the definitions given by the polynomial commonly denoted in Lang (viz. ref. 1 pg. 63-64) […]

Pingback by Permutations (Pt. VI Alternate Definitions of the Sign of a Permutation) « Abstract Nonsense | November 8, 2010 |

[…] So, from this we may finally verify that the definition of given in terms of is the same as the on given by us. […]

Pingback by Permutations (Pt. VI Alternate Definitions of the Sign of a Permutation cont.) « Abstract Nonsense | November 8, 2010 |

[…] we’ve made tacit use of the fact that (proof can be be found here) and that (since ). Thus, since was arbitrary the conclusion […]

Pingback by Symmetric and Antisymmetric forms « Abstract Nonsense | November 14, 2010 |

[…] the free vector space (which of course we can identify with the group algebra by ) and is the sign function. We lastly define a third function given by (order matters, so keep that in […]

Pingback by Row and Column Stabilizer « Abstract Nonsense | May 20, 2011 |

[…] the right tableau and the same column of the left tableau. Note that this is really saying that the transposition is in . If we obviously write . To get the first reason why this condition would ever come up in […]

Pingback by A Weird Condition on Tableaux « Abstract Nonsense | May 22, 2011 |