# 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$?