First signs of life

The sign (or parity) of a permutation is a group-homomorphism1 from S_n to S_2 that is generally introduced in a first-year linear algebra course together with the determinant. Whilst showing that the sign defines a group-homomorphism is conceptually very simple, the standard proof2 that is given is fairly unintuitive despite the fact that it is short. Whilst the standard proof may be nice for introducing students to abstract reasoning, it is hard to visualize what is going on and therefore:

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

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

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 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 this is by drawing which elements get sent to where by a permutation. In this way, the \pi corresponds to the following picture:

image1

What makes this nice, is that 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 (a.k.a picture in this post) also tells us that the sign of the identity is 1 and that inverting an element does not change the sign.

Compositions of permutations can be drawn graphically:

image2

Another nice thing that can be seen is that even if the lines drawn are not straight and may 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, adding one crossing means we need to add another one to compensate for it on the way back. Let C(\pi) be the number of crossings in a picture of \pi. Hence whilst this number is not uniquely defined, we do know that (-1)^{C(\pi)} = (-1)^{N(\pi)}.

From this fact, it follows that sgn is a homomorphism. For if we draw the graphical representations of \sigma, \tau \in S_n over each other, we obtain a graphical representation of \tau \circ \sigma. The total number of crossings is the number of crossings in \tau plus the number of crossings in \sigma, and we hence 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.

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.

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 is a subset of permutations (i.e bijective functions) over some set that is non-empty and closed under taking inverses. Other definitions of a group also exist, this definition follows from 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

Hello, and welcome to this blog

There are many ways to start a blog, and I have decided to choose the one more travelled by.

What this blog is about

Aside from trying to keep my personal life and this blog separate, there are not many constraints to what I am willing to blog about. Basically anything I see as a positive contribution to the Internet goes. A sizeable portion of this blog will be devoted to mathematics, and proofs will be explicit when given. Apart from mathematics, I will be blogging about various other issues that I think I know enough about to be able to say something of value. These areas might include philosophy (though hopefully not very much of it), politics, religion, literature and the sciences. Basically:

Come for the mathematics, stay for all the other interesting stuff.

Because I want to maintain the quality of the posts herein, I will not blog very often.

Who I am

Without going into any existential questions  – I am a mathematics student living in a first-world country who now has a blog.  I go by Matty Wacksen, a name that is a  fairly obscure reference to a literary character (if you can guess what to, tell me) and has very little to do with my real name. I ask anyone who thinks they know my actual name to refrain from posting it. Mathematics plays a much smaller part in my life than in this blog, which is one of the reasons why I will not be posting very often.

 ‘Categorical Observations’

The “Observations” part should not need any more explanation. A Category is a set1  (whose elements we call ‘objects’) and some “arrows”. An arrow goes from one object (its domain) to another object (its codomain), and there can be any number of arrows between any given pair of objects. Arrows are composable (if the codomain of the first arrow is the domain of the second one), with composition being associative. Lastly, every object has an identity arrow that is the right and left identity for composition with any arrows that can be composed with it.

All of this has very little to do with the content of this blog. However,the categorical point of view that focuses less on the objects in a category, and more on the arrows between them will hopefully feature in most mathematical posts.

The main reason for using “Categorical” is actually that this blog is very mathematics-heavy and I wanted to use a title that reflects that.

 


  1. Actually “set” is not completely accurate as we run into foundational issues once we look at something like the “category of sets”. Some authors therefore use “collection” instead of “set”.