The sign (or parity) of a permutation is a group-homomorphism1 from to 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 be a permutation. Then we can write explicitly using two line notation, for example .
The parity, or sign of a permutation is defined as where is the non-identity Element in and . Basically looks at whether the number of inversions in 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 corresponds to the following picture:
What makes this nice, is that the number of lines that cross3 gives the number of so that and this number is . Whether or not this number is even or odd determines the sign. In this case, we see immediately that .
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:
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 be the number of crossings in a picture of . Hence whilst this number is not uniquely defined, we do know that .
From this fact, it follows that is a homomorphism. For if we draw the graphical representations of over each other, we obtain a graphical representation of . The total number of crossings is the number of crossings in plus the number of crossings in , and we hence have that which finishes the proof.
A more formal way of phrasing this is that if is an inversion in (i.e. taking then ), then either it is an inversion in or is an inversion in , but not both. If both are inversions, or neither of them is, then is not inversion in . Hence the parity of the number of inversions in is the sum (modulo 2) of the number of inversions in and .
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 we can define as the alternating group over elements. Because is a homomorphism it follows that is normal subgroup. For it can be shown that is the only nontrivial4 normal subgroup of .
Lastly, looking at a permutation in one line notation is fairly clear that by observing that one line crosses all of the other ones. Knowing that elements with same cycle type are conjugate and that is a homomorphism, this gives the following formula if is composed of disjoint cycles of length :
- 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 so that for all it holds that . is the group of all permutations over a set of objects. ↩
- 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. ↩
- 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 of a group is trivial if or . ↩