The sign function of the symmetric group

Our aim in this post is to decide whether there is an epimorphism from S_n to C_2. Obviously we need n\ge 2. Also S_2\cong C_2, so we might as well assume n\ge 3. Let us fix some notation. As before, we will write elements of S_n in cycle notation. Let 0 be the identity element of C2 and let 1 be the other element of C2. Feel free to play before reading on. Note: some authors would use multiplicative notation for C2, which would mean 1 would be its identity and -1 would be the non-trivial element. I’ve always linked the cyclic groups with modular arithmetic so haven’t done this…so watch out!

Let us first try the naive approach. Let \delta send (1 2) to 1 and everything else to 0. This is a surjective function. Is it a homomorphism?

Think back to conjugacy in S_n. For any \sigma \in S_n, we have

\sigma^{-1}(1\;2)\sigma=((1)\sigma (2)\sigma).

Thus, by carefully choosing \sigma, we have \sigma^{-1} (1\;2)\sigma=(m_1\;m_2) for any 1\le m_1, m_2\le n and that \delta(\sigma)=\delta(\sigma^{-1})=0. Thus \delta is not a homomorphism, since if m_1\not\in \{1, 2\}, then \delta(\sigma^{-1}(1\;2)\sigma)=\delta(\sigma^{-1})\delta((1\;2))\delta(\sigma)=0+1+0=1 but \delta(\sigma^{-1}(1\;2)\sigma)=\delta((m_1\;m_2))=0. The only way to get around this is to set \phi((m_1\;m_2))=1 for every 1\le m_1, m_2\le n. But then, for \phi to be a homomorphism, \phi((m_1\;m_2)(m_1'\;m_2'))=\phi((m_1\;m_2))\phi((m_1'\;m_2'))=1+1=0. Let’s continue down this path. We want to know if \phi can be extended in a well defined way to all permutations of S_n.

We start with the most difficult case, showing that \phi is well defined on the 2-cycles of S_n. Note that a 2-cycle is a permutation (x y) where x≠y. For \phi to not be well defined on the 2-cycles, it must be that we can multiply together an even number of 2-cycles and obtain a 2-cycle. Let \sigma be a counterexample so that it is equal to a 2-cycle, consists of an even number of 2-cycles, and that it is minimal in this regard: there is no \omega shorter than \sigma, equal to a single 2-cycle, and a product of an even number of 2-cycles. Let \sigma=(m_1\;m_2) and let a be a number appearing in a 2-cycle of \sigma with a\not\in \{m_1, m_2\}. This is possible since \sigma consists of at least two 2-cycles and (m_1\;m_2)(m_1\;m_2) is the identity. Now pick the leftmost occurrence of a in \sigma. We may move this 2-cycle (a b) so that it appears at the start (the ‘leftmost’ 2-cycle) of \sigma. This is because either (a b) is disjoint from the 2-cycle to the left of it – and so they commute – or we note that (b c)(a b)=(a b c)=(a b)(a c). Note that in both cases we have not changed the number of 2-cycles. Thus \sigma=(a b)\sigma' and both have the same number of 2-cycles. Now pick the leftmost occurrence of a in \sigma' and move this as left as possible. If any of the 2-cycles cancel i.e. if (a b)(a b) occurs, this contradicts that \sigma has minimal length amongst all counterexamples. We may then simplify the 2-cycles appearing at the start of our product of 2-cycles by using that (a c)(a b)=(a c b)=(a b)(b c). But completing this process we obtain that \sigma=(a\;d)\sigma'' where (a\;d)\sigma'' comprises of the same number of 2-cycles as \sigma but \sigma'' contains no occurrences of a. Hence (a\;d)\sigma'' does not fix a. But a\not\in \{m_1, m_2\} so this contradicts that (a\;d)\sigma''=\sigma=(m_1\;m_2). This case for the 2-cycles implies that the identity element of S_n can only be written as a product of an even number of 2-cycles.

Consider \sigma \in S_n. Then \sigma restricts to permutations on some partition of n, and this is equivalent to saying it splits into disjoint cycles \sigma_1\sigma_2\ldots\sigma_k where k\le n. This is clearly unique up to choosing an ordering of the \sigma_i and choosing a representative for each \sigma_i e.g. (3 1 2)=(2 3 1) but these are really the same permutation, since (3 1 2) and (2 3 1) are just cyclically reordered representatives of (1 2 3). If it makes you feel more comfortable, we can say each \sigma_i is chosen by using the representative with the smallest first entry and the \sigma_i are ordered by the size of their first entries e.g. (1 2 4)(3 5 8)(6 7) is the representative we choose over (3 5 8)(1 2 4)(6 7) or (2 4 1)(3 5 8)(7 6).

If we can show that when any \sigma_i is written as a product of 2-cycles, the number of 2-cycles is always even or always odd, we will have that \phi, our ‘hopeful’ homomorphism, is well defined. This is because given \sigma, we may uniquely decompose it into \sigma_1\ldots\sigma_k and, for each i, \phi(\sigma_i) is well defined i.e. for any \alpha and \beta which are products of 2-cycles equalling \sigma_i, we have \phi(\alpha)=\phi(\beta). Since we know \phi behaves on 2-cycles and want to work out if it is well defined on all other lengths of cycles, induction seems a sensible approach. Our induction hypothesis is that \phi is well defined on all cycles up to length k. Now take a (k+1)-cycle. We have that (m_1\;m_2\ldots m_{k+1})=(m_1\;m_2\ldots m_k)(m_1\;m_{k+1}) and so \phi((m_1\;m_2\ldots m_{k+1}))=\phi((m_1\;m_2\ldots m_k)(m_1\;m_{k+1}))=\phi((m_1\;m_2\ldots m_k))+1 which by our induction hypothesis means that the image of \phi on every (k+1)-cycle is also well defined. This proof also provides a way to write a k-cycle as a product of 2-cycles: (m_1\;m_2\ldots m_k)=(m_1\;m_2)(m_1\;m_3)\ldots(m_1\;m_k). An immediate consequence is…

Lemma. For any n\in \mathbb{N}, S_n is generated by 2-cycles.

If we had started by assuming that \theta((1\;2))=0, then every 2-cycle would be sent to 0. Since every permutation is a product of 2-cycles, this would mean that \theta(S_n)=0 (boring!). The function \phi that we have produced actually has its own name. It is called the sign function of a permutation. Rather than writing \phi you could therefore write sign or sgn…both are frequently used (though note that if we consider Cas {-1, 1} with multiplication, then a formulae for sign might not immediately apply).

Definition. Let \sigma \in S_n. If the sign function on \sigma outputs 0, we say that \sigma is an even permutation. If it outputs 1, we say that \sigma is an odd permutation.

In the next post I’ll give more examples of computing the sign of a permutation, but see if you can do the following without my help! (I’ll work through these in the next post.)

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)

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

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.

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?

In linear algebra, you may have been introduced to the kernel of a map (in a vector space this is the set of elements being mapped to 0, the zero vector).

Definition. Let \phi: G\rightarrow H be a homomorphism. Then the kernel of \phi, denoted ker(\phi), consists of all the elements of G that are sent to the identity element of H.

Note that the kernel of a homomorphism is a subset of elements of the domain.

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

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

Definition. Let n\in \mathbb{N}. Then the kernel of the sign function of S_n is the subgroup consisting of all even permutations of S_n, and is denoted A_n.

The following is a very standard exercise. Note that the kernel of a group homomorphism cannot be empty (why?).

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

We’ll come back to the following, but have a go!

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

The sign function of the symmetric group

Leave a Reply

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

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s