# Thread: Signum function on symmetric groups

1. ## Signum function on symmetric groups

Let $\displaystyle \Omega$ be a set. Any $\displaystyle g \in \text{Sym}(\Omega)$ can be written uniquely as a cycle decomposition in the form $\displaystyle g = c_1c_2...c_k$. Define $\displaystyle \text{sgn }: \text{Sym}(\Omega) \rightarrow \{-1,1\}$ by $\displaystyle \text{sgn}(g) = (-1)^{n-k}$, where k is the number of cycles in the cycle decomposition of g and n is the size of $\displaystyle \Omega$.

a). Let $\displaystyle g,t \in \text{Sym}(\Omega)$ with t a transposition. Prove that $\displaystyle \text{sgn}(tg) = -\text{sgn}(g)$.

b). Show that for all $\displaystyle g,h \in \text{Sym}(\Omega)$, $\displaystyle \text{sgn}(gh) = \text{sgn}(g)\text{sgn}(h)$.

These are both giving me a lot of trouble.. any ideas?

2. Originally Posted by dancavallaro
Let $\displaystyle \Omega$ be a set. Any $\displaystyle g \in \text{Sym}(\Omega)$ can be written uniquely as a cycle decomposition in the form $\displaystyle g = c_1c_2...c_k$. Define $\displaystyle \text{sgn }: \text{Sym}(\Omega) \rightarrow \{-1,1\}$ by $\displaystyle \text{sgn}(g) = (-1)^{n-k}$, where k is the number of cycles in the cycle decomposition of g and n is the size of $\displaystyle \Omega$.

a). Let $\displaystyle g,t \in \text{Sym}(\Omega)$ with t a transposition. Prove that $\displaystyle \text{sgn}(tg) = -\text{sgn}(g)$.

b). Show that for all $\displaystyle g,h \in \text{Sym}(\Omega)$, $\displaystyle \text{sgn}(gh) = \text{sgn}(g)\text{sgn}(h)$.

These are both giving me a lot of trouble.. any ideas?
We can just think of $\displaystyle \Omega = \{1,2,...,n\}$.

Without lose of generality say that $\displaystyle t=(12)$. Let $\displaystyle g$ be a non-identity element with cycle decomposition $\displaystyle g=c_1c_2...c_k$ where these cycles are non-identity cycles. The way you prove this is by exploring various cases. The first case is that $\displaystyle 1,2$ are not found as entries in any one of the cycles and so $\displaystyle tg$ has cycle decomposition $\displaystyle (12)c_1...c_k$ and now apply the definition of the signum function. The second case is that $\displaystyle 1,2$ are found as entries in the cycle but $\displaystyle 1,2$ are found both in a single cycle $\displaystyle c_1$ (by relabeling if necessary). Therefore, we can think of $\displaystyle c_1$ as $\displaystyle c=(1,a_1,...,a_j,2,b_1,...,b_i)$. Now $\displaystyle (12)c_1 = (1,a_1,...,a_j)(2,b_1,...,b_i)$ and so $\displaystyle (12)g = (1,a_1,...,a_j)(2,b_1,...,b_i)c_2...c_k$ and apply the definition of signum function. Another case is when $\displaystyle 1,2$ are found as entries in the cycle by $\displaystyle 1,2$ are found in different cycles say $\displaystyle c_1,c_2$ (by relabeling if necessary). So say that $\displaystyle c_1 = (1,a_1,...,a_j)$ and $\displaystyle c_2 = (2,b_1,...,b_k)$ now compute $\displaystyle (12)c_1c_2$ and apply the definition again. And finally there are cases when $\displaystyle 1\text{ or }2$ (but not both) appear as entries in one of the cycles. Just do all these cases and the proof ought to be complete. For the second part I imagine you need to use the result that every permutation is a product of transpositions.

3. Originally Posted by ThePerfectHacker
We can just think of $\displaystyle \Omega = \{1,2,...,n\}$.

Without lose of generality say that $\displaystyle t=(12)$. Let $\displaystyle g$ be a non-identity element with cycle decomposition $\displaystyle g=c_1c_2...c_k$ where these cycles are non-identity cycles. The way you prove this is by exploring various cases. The first case is that $\displaystyle 1,2$ are not found as entries in any one of the cycles and so $\displaystyle tg$ has cycle decomposition $\displaystyle (12)c_1...c_k$ and now apply the definition of the signum function. The second case is that $\displaystyle 1,2$ are found as entries in the cycle but $\displaystyle 1,2$ are found both in a single cycle $\displaystyle c_1$ (by relabeling if necessary). Therefore, we can think of $\displaystyle c_1$ as $\displaystyle c=(1,a_1,...,a_j,2,b_1,...,b_i)$. Now $\displaystyle (12)c_1 = (1,a_1,...,a_j)(2,b_1,...,b_i)$ and so $\displaystyle (12)g = (1,a_1,...,a_j)(2,b_1,...,b_i)c_2...c_k$ and apply the definition of signum function. Another case is when $\displaystyle 1,2$ are found as entries in the cycle by $\displaystyle 1,2$ are found in different cycles say $\displaystyle c_1,c_2$ (by relabeling if necessary). So say that $\displaystyle c_1 = (1,a_1,...,a_j)$ and $\displaystyle c_2 = (2,b_1,...,b_k)$ now compute $\displaystyle (12)c_1c_2$ and apply the definition again. And finally there are cases when $\displaystyle 1\text{ or }2$ (but not both) appear as entries in one of the cycles. Just do all these cases and the proof ought to be complete. For the second part I imagine you need to use the result that every permutation is a product of transpositions.
Thanks, that makes perfect sense! For part b), a hint I was given was to use the result in part a) as a base case for an inductive argument. But I can't really figure out what to induct on, or how to do it. Any suggestions?

4. Originally Posted by dancavallaro
Thanks, that makes perfect sense! For part b), a hint I was given was to use the result in part a) as a base case for an inductive argument. But I can't really figure out what to induct on, or how to do it. Any suggestions?
I do not think what you wrote is true (the equation in (b) is wrong). This is because if $\displaystyle t$ is a transposition it means that $\displaystyle \text{sgn}(t) = (-1)^{n-1}$ also $\displaystyle \text{sgn}(g) = (-1)^{n-k}$. The second part of the exercise claims that $\displaystyle \text{sgn}(tg) = \text{sgn}(t)\text{sgn}(g)$. But by the first part of exercise $\displaystyle \text{sgn}(tg) = -\text{sgn}(g)$. This means that $\displaystyle \text{sgn}(t)\text{sgn}(g) = - \text{sgn}(g)$. Canceling we get that $\displaystyle \text{sgn}(t) = -1$ however $\displaystyle \text{sgn}(t) = (-1)^{n-1}$ and we we are saying that $\displaystyle (-1)^{n-1} = (-1)$. This is not true unless $\displaystyle n$ is an even number.

(Even though this problem seems to be faulty the general idea outlined
in my first post is one possible way to approach such a problem).

5. Hmm.. well I know for a fact that the sgn function is a homomorphism, which is what part b) is asking to prove. Maybe my definition was wrong.. it would be fine if n was, instead of being the number of elements in the set, the number of elements in the cycle, wouldn't it? Because then that way, n for a transposition would be 2, and k would be 1, so sgn(t) = (-1)^(2-1) = -1. Alternatively, a definition of sgn that I know is correct is sgn(g) = 1 if g is an even permutation, and sgn(g) = -1 if g is an odd permutation. Now can you think of a way to do part b)?

6. Ah ok, I clarified the definition of signum with my professor. n is still the size of the set but k is the number of cycles in the cycle decomposition of g, but including all of the 1-cycles too