First signs of life


The sign (or parity) of a permutation is a group-homomorphism from S_n to S_2 1 that appears in the definition of the determinant. Proving that the sign defines a group-homomorphism is not difficult,  but the (very short) standard proof2 that is given is fairly unintuitive. Therefore:

This post describes a more visual proof of the fact that the sign of a permutation is a homomorphism and gives some interesting facts relating to the sign.

Permutations – a visual description

Let \pi \in S_n be a permutation. Then we can write \pi explicitly using two line notation, for example \pi=\left(\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 1 & 5 & 3 & 4\end{matrix}\right) is the permutation that sends 1 to 2, and 2 to 1, 3 to 5 and so on.

The parity, or sign of a permutation is defined as sgn(\pi) := (-1)^{N(\pi)} where  (-1) is the non-identity element in S_2 (it is easy to see that S_2 has two elements, one of which is the identity, denoted by 1) and N(\pi) := |\{a,b \in \mathbb{N} : 1 \leq a < b \leq n, \pi(a) > \pi(b) \}|. Basically sgn(\pi) looks at whether the number of inversions in \pi is even or odd. A nice way of visualising permuations is by drawing which elements get sent where. In this way, the permutation \pi corresponds to the following picture:


Crossings and the sign

The number of lines that cross3 gives the number of a < b so that \pi(a) > \pi(b) and this number is N(\pi).  Whether or not this number is even or odd determines the sign. In this case, we see immediately that sgn(\pi) = -1.

The graphical representation (called picture for this post) also tells us that the sign of the identity is 1 and that inverting an element does not change the sign (just flip the picture).

Compositions of permutations can be drawn graphically:


Even if the lines drawn are not straight and cross each other multiple times, we can still use the parity of the number of crossings to calculate the sign. This is because as long as the lines are reasonably well behaved (such as not going above/under the top/bottom row, each crossing consisting only of two lines), adding one crossing means we need to add another one to compensate for it on the way back. If we define $latex  C(\pi)$ to be the number of crossings in a particular picture of \pi, then this number might be different for a different picture of \pi. However, we do know that (-1)^{C(\pi)} = (-1)^{N(\pi)}, by the argument above.

From this fact, it follows that sgn is a homomorphism. For if we draw the pictures of \sigma and \tau \in S_n over each other, we obtain a picture of \tau \circ \sigma. The total number of crossings is the number of crossings in \tau plus the number of crossings in \sigma. Calling C(\tau) the number of crossings in this picture of \tau (and similarly for C(\sigma) and C(\tau + \sigma) we have that (-1)^{C(\tau \circ \sigma)} = (-1)^{C(\tau) + C(\sigma)} = (-1)^{C(\tau)}(-1)^{C(\sigma)} which finishes the proof.

A more formal way of phrasing this is that if \{a,b\} is an inversion in \tau \circ \sigma (i.e. taking a < b then (\tau \circ \sigma)(a) > (\tau \circ \sigma)(b)), then either it is an inversion in  \sigma or \{\sigma(a),\sigma(b)\} is an inversion in \tau, but not both. If both are inversions, or neither of them is, then  \{a,b\} is not inversion in \tau \circ \sigma. Hence the parity of the number of inversions in \tau \circ \sigma is the sum (modulo 2) of the number of inversions in \sigma and \tau.

Signs in the wild

Apart from being used in the formula for calculating determinants, the sign of a permutation is also useful in other contexts. For example, for every S_n we can define A_n :=\mathop{Ker}(sgn) as the alternating group over n elements. Because sgn is a homomorphism it follows that A_n is normal subgroup. For n \geq 5 it can be shown that A_n is the only nontrivial4 normal subgroup of S_n.

Permutations also are used to define orientations of objects in differential geometry. Here it is useful to say that the triangle with vertices \pi(u_1),\pi(u_2),\pi(u_3) is  sgn(\pi) times the triangle with vertices u_1,u_2,u_3, where \pi \in S_3. The vertices of both triangles are of course the same, but they are treated as different objects depending on how their vertices are ordered.

Lastly, looking at a permutation in  one line notation is fairly clear that  sgn( (1\dots k )) = (-1)^{k - 1} by observing that one line crosses all of the other ones. Knowing that elements with same cycle type are conjugate and that sgn is a homomorphism, this gives the following formula if \pi is composed of k disjoint cycles of length r_1 \dots r_k:

sgn(\pi) = \Pi_{i = 1}^k (-1)^{r_i -1}

  1. A group can be thought of as some set of bijective functions over some set that is non-empty and contains all inverses and compositions of elements of the set. Groups tend to encode information about symmetries. The usual definition of a group follows from the one given here by Cayley’s theorem. A group homomorphism between groups G and H is a function f:G\rightarrow H so that for all a,b \in G it holds that f(a \circ b) = f(a) \circ f(b). S_n is the group of all permutations over a set of n \in \mathbb{N} objects. 
  2. I have seen a proof in two separate linear algebra classes so far in which the sign is calculated in terms of a quotient of two products. See also this for a proof that goes along similar lines. 
  3. We need to arrange the objects so that no more than 2 lines cross at one point. 
  4. A normal subgroup is a subgroup that is the kernel of a homomorphism. A subgroup H of a group G is trivial if H = G or |H| = 1

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s