(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...

| cite | improve this answer | |
  • $\begingroup$ @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$? $\endgroup$ – ghshtalt Dec 15 '10 at 0:17
  • $\begingroup$ $S_n$ does not have n elements. $\endgroup$ – Sean Tilson Dec 15 '10 at 0:32
  • $\begingroup$ @user3711: No, $S_n$ has n! elements. As above, $S_3$ has 6 elements. So yes, your answer would be in terms of n. $\endgroup$ – Ross Millikan Dec 15 '10 at 0:32
  • $\begingroup$ @Ross, ok sorry, I definitely should have known that! Sorry if this is painfully obvious as well, but is it ok to just assume that there are the same number of odd and even elements, or do I need to show that somehow? $\endgroup$ – ghshtalt Dec 15 '10 at 0:51
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Dec 15 '10 at 1:01

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.