16
$\begingroup$

$\def\sign{\operatorname{sign}}$

For homework, I am trying to show that the map $\sign:S_n \to \{\pm 1\}$ is multiplicative, i.e. that for any permutations $\sigma_1,\sigma_2$ in the symmetric group $S_n$, we have $\sign(\sigma_1 \sigma_2) = \sign\sigma_1 \sign\sigma_2.$

The definition for $\sign$ that I am using is that if $\sigma = \gamma_1\cdots \gamma_k$ is the cycle decomposition of $\sigma \in S_n$ and $\ell_1,\ldots,\ell_k$ are the cycle lengths of $\gamma_1,\ldots,\gamma_k$ respectively, then

$\sign(\sigma):= (-1)^{\ell_1-1}\cdots(-1)^{\ell_k-1}.$

I showed first that the formula holds for two transpositions. Then I showed that it holds for a transposition and a cycle.

However, I got stuck trying to show that the formula holds for a transposition and a product of two cycles, i.e. $\sigma_1 = \tau$ and $\sigma_2 = \gamma_1\gamma_2$. I feel like this case is much more complicated than the others which makes me think I am taking the wrong approach.

If $\tau,\gamma_1,\gamma_2$ are all disjoint then the formula holds trivially because then $\gamma_1\gamma_2\tau$ is the cycle decomposition of $\sigma_1\sigma_2$. Otherwise they are not all disjoint, at which point it seems to get complicated very quickly and I don't know how to proceed.

Would someone please help me understand the best approach to this proof?

  • 0
    I would think the simplest thing is to show that the parity of a permutation is well defined, and that your definition of sign agrees with parity. See, e.g., [this question](http://math.stackexchange.com/questions/46403/alternative-proof-that-the-parity-of-permutation-is-well-defined/46407#46407)2011-11-08

2 Answers 2

4

It's not really that difficult to show it for a transposition that straddles two disjoint cycles. The key is to see that if we have an $n$-element cycle disjoint from a $k$-element cycle and compose with a transposition of one element in each cycle, then you always get an $(n+k)$-element cycle -- there's essentially only one way the transposition can connect the cycles. And then $(-1)^{n+k-1}=-1\times (-1)^{n-1}(-1)^{k-1}$.

Together with showing it for a transposition and a cycle that contains both transposed elements (which I imagine is exactly the reverse of the above case), this is all you need to show (by induction) that if a permutation is a product of $n$ transpositions, then its sign is $(-1)^n$.

For a general product of permutations, just decompose each factor into transpositions (you know you can always to this, right?) and count transpositions in each of them.

  • 1
    If you have $\tau\sigma$ where $\tau$ is a transposition and $\sigma$ an arbitrary permutation, then decompose $\sigma$ into disjoint cycles $\gamma_1\gamma_2\cdots\gamma_k$. There can be at most two cycles that contain the two elements $\tau$ exchanges; arrange the $\gamma$s such that those are $\gamma_1$ and $\gamma_2$. Now re-parenthesize to $(\tau\gamma_1\gamma_2)(\gamma_3\cdots\gamma_k)$ and apply the two-cycle reasoning to the first parenthesis. Because all of $\tau\gamma_1\gamma_2$ leave all of the _other_ cycles alone, you can then decompose their product separately.2011-11-09
1

Hennings answer is a great way to go. I thought you might find this alternative viewpoint of interest as well...

Each permutation can be realized by a permutation matrix (let $\sigma \in S_n$ and take the $n\times n$ identity and then send row $i$ to row $\sigma(i)$). It's not hard to show that if $A$ and $B$ are matrices corresponding to $\sigma$ and $\tau$, then $AB$ corresponds to $\sigma \tau$.

Now recall that swapping rows changes the sign of the determinant. From here it's not hard to show that the sign of a permutation is just the determinant of the corresponding matrix.

Now the homomorphism property of $\mathrm{sign}$ comes from: $\mathrm{det}(AB)=\mathrm{det}(A)\mathrm{det}(B)$ (the fact that the determinant is a homomorphism).

  • 0
    I don't think that replacing the word "permutation" by the words "n-tuple of indices" counts as avoiding mention of permutations, except in a superficial linguistic sense. (Also, I see no indication that anybody commented about *should* or interpreted your words in that light.)2011-11-08