# Computing the sign of a permutation

In this post we’ll go through the exercises of the last. It will therefore mostly be examples based. Let’s recap. We introduced the sign function. We found that $S_n$ was generated by 2-cycles. The sign function was an epimorphism from $S_n$ to $C_2$, defined by sending the 2-cycles of $S_n$ to the non-trivial element of $C_2$. We used $C_2=\{0, 1\}$ with binary operation addition modulo 2.

Exercise 1. Compute the value of the sign function for the following permutations.

i) (1 2)    ii) (2 3)    iii) (1 2 3)    iv) (1 2 3 4)    v) (1 2 3 4 5)    vi) (3 1 4 2)    vii) (1 2)(3 4)

viii) (1 3)(2 4)    ix) (1 2 3 4)(7 8 9)    x) (1 2 3)(1 2 3 4)

First, sign((1 2))=sign((2 3))=1 by the definition of sign. Since (1 2 3)=(1 2)(1 3), we have sign((1 2 3))=sign((1 2)(1 3)). Using that sign is a homomorphism we then have that sign((1 2)(1 3))=sign((1 2))+sign((1 3))=1+1=0. Here we are using, from the previous post, that $(m_1\;m_2\ldots m_k)=(m_1\;m_2)(m_1\;m_3)\ldots(m_1\;m_k)$. Thus (1 2 3 4)=(1 2)(1 3)(1 4) so that sign((1 2 3 4))=sign((1 2))+sign((1 3))+sign((1 4))=1+1+1=1. Similarly sign(1 2 3 4 5) =1+1+1+1=0.

For (vi), either use that (3 1 4 2)=(3 1)(3 4)(3 2) or that (3 1 4 2)=(1 4 2 3)=(1 4)(1 2)(1 3) to get that sign((3 1 4 2))=1+1+1=1. With (vii) and (viii) we may immediately use that sign is a homomorphism so that sign((1 2)(3 4))=sign((1 2))+sign((3 4))=0 and sign((1 3)(2 4))=0. With (ix) we may use (iv) to see that sign((1 2 3 4)(7 8 9))=sign((1 2 3 4))+sign((7 8 9)) is 1+sign((7 8 9))=1+0=1. Similarly (x) follows from (iii) and (iv), the answer again being 1.

Exercise 2. Based on the previous question, what is the sign of (1 2 … r)? Use this to compute the sign of (1 2 3 … 100) and (1 2 3 … 101).

Hopefully you’ve noticed that the sign function doesn’t really care about the numbers you give it. Given an r-cycle we have that $(m_1\;m_2\ldots m_r)=(m_1\;m_2)(m_1\;m_3)\ldots(m_1\;m_r)$ and so $\textrm{sign}(m_1\;m_2\ldots m_r)=\textrm{sign}(m_1\;m_2)+\textrm{sign}(m_1\;m_3)+\ldots+\textrm{sign}(m_1\;m_r)=r-1$.

Lemma. If r is even then $\textrm{sign}(m_1\;m_2\ldots m_r)=1$ [simple check: r=2]. If r is odd then $\textrm{sign}(m_1\;m_2\ldots m_r)=0$ [simple check: r=1 or r=3].

Applying this lemma we see that sign(1 2 3 … 100)=1 and sign(1 2 3 … 101)=0.

Exercise 3. Write out steps explaining to someone how they can compute the sign function of i) a cycle of any given length ii) an arbitrary permutation of $S_n$.

Quite a few ways to phrase this, and worth thinking about. Given $\sigma\in S_n$ we have that $\sigma=\sigma_1\ldots\sigma_k$ and, from our lemma above, it is only the even length cycles that contribute to the sign function. Thus…

Lemma. If there are an odd number of even length cycles then sign($\sigma$)=1, and if there are an even number of even length cycles then sign($\sigma$)=0.

Exercise 4. What is the value of the sign function when you multiply:

i) two even permutations?  ii) two odd permutations?  iii) an odd and even permutation?

Consider if $\sigma_1, \sigma_2$ are even and $\omega_1, \omega_2$ are odd. Then sign($\sigma_1\sigma_2$)=sign($\sigma_1$)sign($\sigma_2$)=0+0=0; sign($\omega_1\omega_2$)=sign($\omega_1$)sign($\omega_2$)=1+1=0; and sign($\sigma_1\omega_1$)=sign($\sigma_1$)sign($\omega_1$)=0+1=1.

Exercise 5. What is ker$(\phi)$, where $\phi$ is the sign function for $S_4$?

This amounts to writing out the even permutations of $S_4$, which are

$\{id, (1 2 3), (1 3 2), (1 2 4), (1 4 2), (1 3 4), (1 4 3), (2 3 4), (2 4 3), (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)\}.$

Note that half the elements of $S_n$ are even. We’ll cover this in more detail at a later point.

Exercise 6. Verify that the kernel of a homomorphism $\phi: G\rightarrow H$ is a subgroup of G.

Associativity follows from all elements in G satisfying the associative law. From ‘More on homomorphisms‘, $\phi(e_G)=e_H$ and so ker($\phi$) contains $e_G$. If $x, y \in$ ker($\phi$) then $\phi(x)=\phi(y)=e_H$ and so $\phi(xy)=\phi(x)\phi(y)=e_He_H=e_H$ meaning $xy \in$ ker($\phi$). Finally $x \in$ ker($\phi$) means $e_H=\phi(xx^{-1})=\phi(x)\phi(x^{-1})=e_H\phi(x^{-1})$ and so $\phi(x^{-1})=e_H$ i.e. $x^{-1} \in$ ker($\phi$).

Exercise 7. Let $\phi: G\rightarrow H$ be a group homomorphism. Show $|\textrm{ker}(\phi)|=1\Leftrightarrow \phi$ injective.

We know that $e_G\in$ ker($\phi$) and so |ker($\phi$)|$\ge 1$. Consider if ker($\phi$)=$\{e_G\}$. Then $\phi(x)=\phi(y)\Rightarrow x=y$. Why? Well $\phi(x)=\phi(y) \Rightarrow \phi(x)\phi(y)^{-1}=e_H\Rightarrow \phi(x)\phi(y^{-1})=e_H$ $\Rightarrow \phi(xy^{-1})=e_H\Rightarrow xy^{-1}=e_G$ since ker($\phi$)=$\{e_G\}$.

Now consider if $\phi$ injective i.e. $\phi(x)=\phi(y)\Rightarrow x=y$. But $z\in$ ker($\phi$) means $\phi(z)=\phi(e_G)$ so $z=e_G$. Hence ker($\phi$)=$\{e_G\}$.

Exercise 9. Let $n\ge 3$. Is there a homomorphism $\phi: C_n\rightarrow D_n$? Is there a homomorphism $\theta: D_n\rightarrow C_n$?

Picturing $C_n$ as the rotational symmetries of a circle and $D_n$ as the symmetries of an n-gon provide an inclusion which is a homomorphism (the first part). The second part has some tricky things going on, which we’ll come back to.