Thread: Signum function on symmetric groups

1. Signum function on symmetric groups

Let $\Omega$ be a set. Any $g \in \text{Sym}(\Omega)$ can be written uniquely as a cycle decomposition in the form $g = c_1c_2...c_k$. Define $\text{sgn }: \text{Sym}(\Omega) \rightarrow \{-1,1\}$ by $\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 $\Omega$.

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

b). Show that for all $g,h \in \text{Sym}(\Omega)$, $\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 $\Omega$ be a set. Any $g \in \text{Sym}(\Omega)$ can be written uniquely as a cycle decomposition in the form $g = c_1c_2...c_k$. Define $\text{sgn }: \text{Sym}(\Omega) \rightarrow \{-1,1\}$ by $\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 $\Omega$.

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

b). Show that for all $g,h \in \text{Sym}(\Omega)$, $\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 $\Omega = \{1,2,...,n\}$.

Without lose of generality say that $t=(12)$. Let $g$ be a non-identity element with cycle decomposition $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 $1,2$ are not found as entries in any one of the cycles and so $tg$ has cycle decomposition $(12)c_1...c_k$ and now apply the definition of the signum function. The second case is that $1,2$ are found as entries in the cycle but $1,2$ are found both in a single cycle $c_1$ (by relabeling if necessary). Therefore, we can think of $c_1$ as $c=(1,a_1,...,a_j,2,b_1,...,b_i)$. Now $(12)c_1 = (1,a_1,...,a_j)(2,b_1,...,b_i)$ and so $(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 $1,2$ are found as entries in the cycle by $1,2$ are found in different cycles say $c_1,c_2$ (by relabeling if necessary). So say that $c_1 = (1,a_1,...,a_j)$ and $c_2 = (2,b_1,...,b_k)$ now compute $(12)c_1c_2$ and apply the definition again. And finally there are cases when $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 $\Omega = \{1,2,...,n\}$.

Without lose of generality say that $t=(12)$. Let $g$ be a non-identity element with cycle decomposition $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 $1,2$ are not found as entries in any one of the cycles and so $tg$ has cycle decomposition $(12)c_1...c_k$ and now apply the definition of the signum function. The second case is that $1,2$ are found as entries in the cycle but $1,2$ are found both in a single cycle $c_1$ (by relabeling if necessary). Therefore, we can think of $c_1$ as $c=(1,a_1,...,a_j,2,b_1,...,b_i)$. Now $(12)c_1 = (1,a_1,...,a_j)(2,b_1,...,b_i)$ and so $(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 $1,2$ are found as entries in the cycle by $1,2$ are found in different cycles say $c_1,c_2$ (by relabeling if necessary). So say that $c_1 = (1,a_1,...,a_j)$ and $c_2 = (2,b_1,...,b_k)$ now compute $(12)c_1c_2$ and apply the definition again. And finally there are cases when $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 $t$ is a transposition it means that $\text{sgn}(t) = (-1)^{n-1}$ also $\text{sgn}(g) = (-1)^{n-k}$. The second part of the exercise claims that $\text{sgn}(tg) = \text{sgn}(t)\text{sgn}(g)$. But by the first part of exercise $\text{sgn}(tg) = -\text{sgn}(g)$. This means that $\text{sgn}(t)\text{sgn}(g) = - \text{sgn}(g)$. Canceling we get that $\text{sgn}(t) = -1$ however $\text{sgn}(t) = (-1)^{n-1}$ and we we are saying that $(-1)^{n-1} = (-1)$. This is not true unless $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