# Determine sign of a permutation, calculate number of elements in the subgroup of permutations with sign = 1

Question:

(a) Determine sign$(\tau)$ for $$\left( \begin{array}{ccccccc} 1&2&3&4&5&6&7 \\ 2&3&5&7&1&6&4 \end{array} \right )$$.

(b) Let $A_{n} = \{\tau \in S_{n} | \mbox{sign}(\tau) = 1\}$. Show that $A_{n}$ is a sub group of $S_{n}$ and calculate the number of elements (Tip: Show that for any transposition $\tau$, $S_{n}$ is the disjoint union of $A_{n}$ and $A_{n}\circ\tau$).

My attempt so far: (a) So I have this formula for sign$(\sigma) = \displaystyle \prod_{i < j} \frac{\sigma(j)-\sigma(i)}{j-i}$. This wouldn't be so difficult, however it's apparently ok to count the number of elements for which $i<j$ but $\sigma(i)>\sigma(j)$ (these are called inversions, I believe). If this number is even, sign$(\sigma)=1$ if odd, $-1$. In this case I named $(1,5),(2,5),(3,5),(3,7),(4,5),(4,6),(4,7),(6,7) \Rightarrow \mbox{sign}(\tau) =1$

(b) To begin with, if I want to show that something is a subgroup, I have to show that: (i)$a,b \in U \Rightarrow a \circ b \in U$ and that (ii)$a \in U \Rightarrow a^{-1} \in U$ correct? (I'm actually a little confused at why we can just assume that the identity element is still part of a subgroup, for instance if the exercise were a little different and I was checking if $A_{n} = \{\tau \in S_{n} | \mbox{sign}(\tau) = -1\}$ was a sub group, I would say that the identity element for permutations $123...n$ has no inversions $\Rightarrow$ sign$(\tau) = 1 \Rightarrow \tau \notin A_{n}$... I mean, subgroups are groups themselves, right?

Well anyway, for (i) I tried to show it by writing:

Let $\tau, \sigma \in A_{n}$

$\Rightarrow$ sign$(\tau) = 1$ and sign$(\sigma)=1$

For a polynomial (I honestly don't totally understand this or know if I need to put this stuff with 'g' in...) $g=g(x_{1},...,x_{n})$, sign$(\tau \circ \sigma)g= (\tau \circ \sigma)(g)=\tau(\sigma(g))=\tau((\mbox{sign}\sigma)g)=(\mbox{sign}\tau)(\mbox{sign}\sigma)g$

$\Rightarrow$ sign$(\tau \circ \sigma) = (1)(1) = 1 \Rightarrow (\tau \circ \sigma) \in A_{n}$

with (ii) my attempt was:

Let $\sigma \in A_{n}$

If $\sigma \circ \sigma^{-1} = \epsilon$ (this should represent the identity element)

$\Rightarrow$ sign$(\sigma \circ \sigma^{-1}) = \mbox{sign}\epsilon$

$(\mbox{sign}\sigma)(\mbox{sign}\sigma^{-1})=1$ (Because sign$(\epsilon)=1$)

$(1)(\mbox{sign}(\sigma^{-1}))=1$ (Because $\sigma \in A_{n}\Rightarrow \mbox{sign}(\sigma) = 1$)

sign$(\sigma^{-1})=1 \Rightarrow \sigma^{-1} \in A_{n}$

Out of (i) and (ii) follows the conclusion that $A_{n}$ is a subgroup of $S_{n}$...

So hopefully that would all be on the right track so far... With the calculate the number of elements part, I don't know what to do or why. Following the tip I would try to show that $S_{n}$ is the disjoint union (not the same as showing that the intersection is empty, right?) of $A_{n}$ and $A_{n} \circ \tau$ (where $\tau$ is a transposition). I don't understand this, but directly out of the book is the statement "We call $\tau$ a transposition. If $i<j$, then there are $2(j-i=1)+1$ inversions in $\tau$, and hence the transposition $\tau$ is odd." Accordingly I think I could use sign$(\tau \circ \sigma)=(\mbox{sign}\tau)(\mbox{sign}\sigma)$ to show that the product of an odd and even permutation is odd and therefore $A_{n} \circ \tau$ is odd and $A_{n}$ has no elements in common with $A_n \circ \tau$. But even then how does one calculate a number of elements?

-

Your work on (a) got cut off somehow. For your comment on (b), if you have $a,b \in U \Rightarrow a \circ b \in U$ and $a \in U \Rightarrow a^{-1} \in U$ then you have $a \circ a^{-1} \in U$ so you don't have to check the identity (as long as $U$ is nonempty). Showing the identity is not in U is another way to prove U is not a subgroup. You are right that subgroups are groups themselves, but I think you would have trouble showing the product to two odd permutations is odd. To say $S_n$ is a disjoint union of $A_n$ and $A_{n} \circ \tau$, you need the intersection to be empty and that every element of $S_n$ is in one of them. In calculating the number of elements, if every element is either odd or even and there are the same number of odd ones and even ones...
@Ross so is it first of all correct to say that $S_n$ has $n$ elements? And my answer would be in terms of $n$? –  ghshtalt Dec 15 '10 at 0:17
$S_n$ does not have n elements. –  Sean Tilson Dec 15 '10 at 0:32
@user3711: No, $S_n$ has n! elements. As above, $S_3$ has 6 elements. So yes, your answer would be in terms of n. –  Ross Millikan Dec 15 '10 at 0:32
I would think you need to show that there are the same number of even and odd. For a given transpostions $\tau$, can you have two elements $a,b \in A_n$ such that $a\tau=b\tau$? The "as above" in my previous comment was confusion with another question. –  Ross Millikan Dec 15 '10 at 1:01