algebra

The sign (or parity) of a permutation is a group-homomorphism from $S_n$ to $latex 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 proof[^2] 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 cross¹ 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$ . Deforming a single line can change the number of crossings, but (provided that each crossing is proper and no more than two lines cross at a point) doing so introduces/removes an even number of crossings so the sign is well-defined.

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 :

The idea is that if we “deform” the black lines into the blue lines, we can only get rid of even numbers of crossings in the process. If you look at the picture above long enough this should be clear.

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 nontrivial² normal subgroup of $S_n$ .

Permutations also are used to define orientations of objects in differential geometry and algebraic topology. 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}$

We need to arrange the objects so that no more than 2 lines cross at one point. ↩
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$ . ↩

Categorical Obervations

Matty Wacksen's blog

First signs of life

	Matty Wacksen on Knowledge as the Only Modern…
	Lou Keep on Knowledge as the Only Modern…