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.

 

 

Advertisements
Computing the sign of a permutation

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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