Lete $n\in \mathbb{N}$. Show that the transformation $$sgn: S_n \rightarrow \{\pm 1\}$$

(where $S_n$ is the set of all permutations of the integers in the set $\{1,...,n\}$),given by $\sigma \mapsto sgn(\sigma)$, $\sigma \in S_n$, is a group homomorphism, i.e. the following equality holds:

$$sgn(\sigma_1 \circ \sigma_2) = sgn(\sigma_1)sgn(\sigma_2)$$

Def.(sgn) : Let $\sigma \in S_n$ be a permutation that can be expressed as l transpositions. Then $sgn(\sigma) := (-1)^l$

My attempt:

Since every permutation $\sigma$ can be expressed as the product of a given number of transpositions, I have the following:

Let $\sigma_1 = \tau_1 \circ \tau_2 \circ .... \circ \tau_l$ and $\sigma_2 = \tau_1 \circ \tau_2 \circ .... \circ \tau_k$. Then it follows that $\sigma_1 \circ \sigma_2 = \tau_1 \circ \tau_2 \circ .... \circ \tau_l \circ \tau_1 \circ \tau_2 \circ .... \circ \tau_k$. Now I'm not exactly sure how to go from here and whether my approach is correct. I kind of doubt it, since I need $l + k$ transpositions to derive $\sigma_1 \circ \sigma_2$, but the sum of those could easily be greater than $n$, right? In case my approach was correct thus far, how can I show that the equality holds, could I case cases depending on whether l and k are even or odd to prove the equality?

  • $\begingroup$ How is $sgn$ defined? As long as that is unclear it is impossible to prove that it is a grouphomomorphism. $\endgroup$ – H.B. Apr 17 '14 at 17:38
  • $\begingroup$ I edited the post. $\endgroup$ – eager2learn Apr 17 '14 at 17:45

The hard part of $sgn$ is to show that any transposition decomposition of a permutation will always have an odd number or and even number of transposition, regardless of how you decompose it--you can have as many transpositions as you want, even more than $n$ transpositions. So you assign permutations with an even number of transpositions 1 and permutations with an odd number of transpositions the number -1.

Now that you have established this well definedness property of sgn the problem becomes much easier. You can consider the 4 possible cases when l and k are even and odd respectively.

  • $\begingroup$ Thanks for the answer. We actually did prove that in a lecture, but I didn't really know whether I needed to apply this here. I think I still haven't completely understood the notion of transposition. From what I understand is that every permutation can be expressed through a number of transposition starting with the identity permutation. Is that correct? Is every product of transpositions applied on the ID or can any random starting permutation be used? $\endgroup$ – eager2learn Apr 17 '14 at 17:51
  • 1
    $\begingroup$ You just need to convince yourself that every cyclic permutation can be written as a product of transpositions. Here is how: (a b c d e f) = (a b)(b c)(c d)(d e)(e f). Now given any permutation, you write it down as in a decomposition of cyclic permutations, each of which you can write out in transpositions. Just remember, a transposition is a function that swaps two objects. (a b) is the transposition that gives b when given a, and gives a when given b. $\endgroup$ – breeden Apr 17 '14 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.