19
$\begingroup$

I am aware that there are a couple of well-known proofs of this theorem, but I'm specifically grappling with the proof given in Fraleigh's A First Course in Abstract Algebra (Theorem 9.15 in the textbook).

Let $s$ be a permutation in the symmetric group of degree $n$, and let $t$ be a transposition $(i,j)$ in the same group. If $n$ is $1$ or infinite, we are done. Otherwise, ....[details of the proof omitted.] (We use the right-to-left convention to multiply permutations.)

Okay, we have shown that the number of orbits of $s$ and $ts$ differ by 1. This part, I understand. But I don't understand how to infer the theorem from here. I would be very grateful if someone can help me clear my blind spot. Thank you so much!


Added by Dylan. Here is Fraleigh's explanation (please don't sue me):

We have shown that the number of orbits of $\tau \sigma$ differs from the number of orbits of $\sigma$ by $1$. The identity permutation $\iota$ has $n$ orbits, because each element is the only member of its orbit. Now the number of orbits of a given permutation $\sigma \in S_n$ differs from $n$ by either an even or odd number, but not both. Thus it is impossible to write $ \sigma = \tau_1 \tau_2 \cdots \tau_m \iota $ where the $\tau_k$ are transpositions, in two ways, once with $m$ even and once with $m$ odd. $\qquad \diamond$

  • 1
    Thanks for helpfully adding the scan! My confusion arose from Fraleigh implicitly setting s to be the identity here (multiplying it by the sequence of transpositions), but still using the same symbol to now refer to the new expression, without explicitly indicating the switch. And I guess I confused myself further by carelessly thinking about the number of orbits instead of the *parity* of the number of orbits. Srivatsan's answer below is excellent because he used different symbols to denote the two different permutations, and it also reads more intuitively than Fraleigh's concise proof.2011-12-27

3 Answers 3

14

Let $\newcommand{\orb}{\operatorname{orbits}} \orb(s)$ be the number of orbits in $s$. I will assume you have already showed that $\orb(ts)$ differs from $\orb(s)$ by $1$ for any transposition $t$. In particular, we have $\orb(ts) \equiv \orb(s) + 1 \pmod 2 .$ By a simple induction (on $k$), this implies that $\orb(t_1 t_2 \cdots t_k s) \equiv \orb(s) + k \pmod 2$ for any sequence of $k$ transpositions $t_1, \ldots, t_k$. Finally, setting $s$ to be the identity permutation, we have $ \orb(t_1 t_2 \cdots t_k) \equiv n + k \pmod 2. \tag{$\dagger$} $

Now if a permutation $\sigma$ is expressed as a product of transpositions as $\sigma= t_1 t_2 \cdots t_k$, then $(\dagger)$ says that $k \equiv \orb(\sigma) + n \pmod 2$. In other words, in any representation of $\sigma$ as a product of transpositions, the parity of the number of transpositions used is an invariant, equal to $(\orb(\sigma) + n) \bmod 2$. This invariant of the permutation is what will shortly (in your book!) be called its signature.

  • 1
    Does Fraleigh actually ever define the signature?2016-04-19
7

I still find the polynomial (in $n$ commuting indeterminates) $s(x_1,x_2,\ldots, x_n) = \prod _{i < j} (x_i - x_j)$ to be the easiest way to see that the sign of a permutation $\sigma$ is well defined. Setting $s^{\sigma}(x_1,x_2,\ldots, x_n) = \prod _{i < j} (x_{\sigma(i)} - x_{\sigma(j)})$ for a permutation $\sigma$ makes it clear that $s^{\sigma} = \pm s,$ and that the sign is $(-1)^{m(\sigma)},$ where $m(\sigma)$ is the number of ordered pairs $(i,j)$ with $i < j$ and $\sigma(i) > \sigma(j).$ It is clear that $(-1)^{m(\sigma)} = -1$ if $\sigma$ is a transposition. This doesn't really help to explain the proof in Fraleigh, though.

  • 0
    I should probably have added that it is clear that $\sigma \to (-1)^{m(\sigma)}$ is a group homomorphism from $S_n \to \{1,-1 \}.$2011-12-27
1

Sorry if this should be a new post. Please let me know if it should. I'm asking for clarification for Srivatsan's proof - based on Fraleigh's - so I thought it'd be more convenient for future readers if I asked here. Thanks.

$\Large{\text{1 -}}$ How exactly does $\orb(ts) \equiv \orb(s) + 1 \pmod 2 \Longrightarrow \orb(t_1 t_2 \cdots t_k s) \equiv \orb(s) + k \pmod 2$?

My guess --- I understand the proof for any transposition $t$ - $\orb(\color{green}{ts}) \equiv \orb(\color{cornflowerblue}{s}) +1\pmod 2 \tag{$\clubsuit$}$ So do we just apply this to $\orb(\color{green}{t_1 t_2s})$ to get - $\orb(\color{green}{t_1 t_2s}) \equiv \orb(\color{cornflowerblue}{t_1s}) + 1 \pmod 2 ?$

My concern is that the RHS of {$\clubsuit$} has $\color{cornflowerblue}{s}$, NOT ($ts$).

$\Large{\text{2 -}}$ Shouldn't $\orb(t_1 t_2 \cdots t_k) \equiv n + k \pmod 2 \iff k \equiv \orb(t_1 t_2 \cdots t_k) \LARGE{\text{ MINUS }} \normalsize n \pmod 2 ?$ $\Large{\text{3 -}}$ How does $k \equiv \orb(\sigma) - n \pmod 2$ mean that k (= parity of the number of transpositions) cannot be both odd and even? My introductory course didn't cover signature or invariant.

$\Large{\text{4 -}}$ Many thanks to Ryan and Srivatsan for separating ($\clubsuit$) as a lemma. I was completely confused over - in Fraleigh's book - how ($\clubsuit$) related to the Theorem. But how would you expect to need ($\clubsuit$) to prove the theorem? If not for you and the textbook, I'd never see to start with ($\clubsuit$).

  • 0
    As described [here](http://math.stackexchange.com/privileges/comment), you need at least 50 reputation to comment on someone else's post.2012-12-24