I learned the following theorem about the properties of permutation from Gallian's Contemporary Abstract Algebra.

Theorem 5.4 $\;$ Always Even or Always Odd

If a permutation $\alpha$ can be expressed as a product of an even number of $2$-cycles, then every decomposition of $\alpha$ into a product of $2$-cycles must have an even number of $2$-cycles. In symbols, if $$ \alpha = \beta_1 \beta_2 \dotsm \beta_r \quad\text{and}\quad \alpha = \gamma_1 \gamma_2 \dotsm \gamma_s $$ where the $\beta$'s and the $\gamma$'s are $2$-cycles, then $r$ and $s$ are both even or both odd.

When I tried to reconstruct the proof myself, I found that it suffices to prove the following lemma:

If $\epsilon=\beta_1\beta_2\cdots\beta_r$ where $\beta$'s are $2$-cycles, then $r$ is even.

The original proof for this lemma uses the following key property of the product of $\beta_1\beta_2$:

The product can always be expressed in one of the following forms on the left: $$\begin{align}(ab)(ab)&=\epsilon\\ (ab)(ac)&=(bc)(ab)\\ (ab)(cd)&=(cd)(ab)\\ (ab)(bc)&=(bc)(ac)\end{align}$$

The proof for the lemma is based on such property and mathematical induction. I found it really hard to remind of such property, so I set it as an exercise to give another proof. However, I have no idea how to actually do it.

So here is my question:

Does anybody know an alternative proof of the lemma or the theorem?

  • $\begingroup$ @Arturo: I really appreciate your edited for the title. Thanks! $\endgroup$ – Jack Jun 20 '11 at 4:23
  • 1
    $\begingroup$ I don't think we have to commit the boxed identities to memory in order to recall this proof: in general, if we have elements $x, y$ in a group, then $xy = (xyx^{-1})x$. Maybe I'm misinterpreting your words. $\endgroup$ – Dylan Moreland Jun 20 '11 at 5:32
  • $\begingroup$ @Dylan: I cannot catch up with you. How do you use $xy=(xyx^{-1})x$ here? $\endgroup$ – Jack Jun 20 '11 at 17:05
  • 5
    $\begingroup$ You find it hard to remember the lemma's proof since you are not giving the formulas a concrete meaning. All the proof needs is the 2nd and 3rd formulas, and they say that a product of 2 transpositions where the second factor moves a number which the first does not can be rewritten so the first factor moves that number and the second does not. The bibliography to my course handout www.math.uconn.edu/~kconrad/blurbs/grouptheory/sign.pdf gives references to a lot of proofs of your lemma, which is proved in the handout itself as Theorem 2.1 by the same method you describe in your question. $\endgroup$ – KCd Jun 20 '11 at 17:49

Here's a nice proof that uses group actions.

Let $x_1,\ldots,x_n$ be $n$ unknowns, and consider $$\Delta= \prod_{1\leq i\lt j\leq n} (x_j-x_i).$$

For example, for $n=4$, we would have $$\Delta = (x_2-x_1)(x_3-x_1)(x_4-x_1)(x_3-x_2)(x_4-x_2)(x_4-x_3).$$

Given a permutation $\sigma\in S_n$, define a function $f_{\sigma}\colon\{\Delta,-\Delta\}$ by letting $$f_{\sigma}(\Delta) = \prod_{1\leq i\lt j\leq n} (x_{\sigma(j)}-x_{\sigma(i)}),$$ and $f_{\sigma}(-\Delta)=-f_{\sigma}\Delta$.

Note that since $\sigma$ is a permutation, $f_{\sigma}(\Delta)=\Delta$ or $f_{\sigma}(\Delta) = -\Delta$. Also, if $\sigma,\rho$ are two permutations, then $f_{\sigma}\circ f_{\rho} = f_{\sigma\rho}$, as is easy to verify.

Now, let's consider what a transposition $\tau=(a,b)$ does to $\Delta$. Without loss of generality, say $a\lt b$.

The factors $(x_j-x_i)$ with neither $i$ nor $j$ equal to $a$ nor $b$ are unchanged.

For the pairs with exactly one index in $\{a,b\}$, we have two classes: those in which the other index is between $a$ and $b$, and those where the other index is not between $a$ and $b$.

If the other index is between $a$ and $b$, then $x_j-x_a$ is sent to $-(x_b-x_j)$ and $x_b-x_j$ is sent to $-(x_j-x_a)$; the two sign changes cancel each other out.

If the other index is larger than $b$, then $x_j-x_a$ and $x_j-x_b$ are swapped, with no sign changes.

If the other index is smaller than $a$, then $x_a-x_i$ and $x_b-x_i$ are swapped, with no sign changes.

Finally, the factor $x_b-x_a$ is sent to $-(x_b-x_a)$.

In summary, if $\tau$ is a transposition, then $f_{\tau}(\Delta)=-\Delta$, $f_{\tau}(-\Delta)=\Delta$.

Now take an arbitrary permutation $\sigma$, and express it as a product of transpositions in two different ways: $$\sigma = \tau_1\cdots \tau_r = \rho_1\cdots\rho_s.$$ Then $$f_{\sigma}(\Delta) = f_{\tau_1\cdots\tau_r}(\Delta) = f_{\tau_1}\circ\cdots\circ f_{\tau_r}(\Delta) = (-1)^r\Delta$$ and $$f_{\sigma}(\Delta) = f_{\rho_1\cdots\rho_s}(\Delta) = f_{\rho_1}\circ\cdots\circ f_{\rho_s}(\Delta) = (-1)^s\Delta.$$ Therefore, $(-1)^r\Delta = (-1)^s\Delta$, so $r$ and $s$ have the same parity: both odd, or both even.

  • 6
    $\begingroup$ That's how Herstein does it, though what's really going on is that we're counting the (parity of the) number of "disorders". $\endgroup$ – Yuval Filmus Jun 20 '11 at 4:17
  • $\begingroup$ Hmm, it looks interesting, though it is much longer then the one I learned from Gallian's book. Is it from Herstein as @Yuval said? I have never read Herstein before. But it seems that his book is quite classical texts in algebra. $\endgroup$ – Jack Jun 20 '11 at 4:44
  • 1
    $\begingroup$ @Jack: Written this way, it's not from Herstein. Can't remember where I saw this proof, but it was a book that introduced group actions early on. Yes, Herstein's "Topics in Algebra" is a classic text. $\endgroup$ – Arturo Magidin Jun 20 '11 at 4:55
  • 2
    $\begingroup$ You can avoid enumerating cases by observing that $\Delta$ can be factored as $P \cdot (x_a - x_b) \cdot \prod_{i \neq a,b} (x_i - x_a) (x_i - x_b)$ for some polynomial $P$ which is independent of $x_a$ and $x_b$. Then obviously $f_{\tau}(\Delta) = -\Delta$. $\endgroup$ – sdcvvc Jun 25 '11 at 11:47
  • 3
    $\begingroup$ This polynomial occurs as determinant of Vandermonde matrix. $\endgroup$ – sdcvvc Oct 23 '11 at 4:20

Here's my favorite proof. Represent a permutation of $n$ letters as follows. Write the numbers $1$ to $n$ in a row and then write them in another row somewhat beneath the first row. Now connect the numbers in the top to the numbers in the bottom by curves representing the permutation.

So, if $\sigma$ is the permutation, connect $i$ to $\sigma(i)$ by a curve. For convenience, draw the curves so that they intersect each other in transverse double points. (That is, the tangent vectors to each curve when they intersect are not parallel, and no point has more than two curves passing through it.) Now I claim that the parity of the permutation matches the parity of the number of intersections.

There are two steps to showing this. First is to show that the intersection number is well-defined modulo 2. Second is to show that it matches the number of transpositions. To see that it is well-defined modulo 2, note that we just have to show that the intersection between two given curves is well-defined modulo 2. Indeed if the permutation swaps the endpoints of the arcs, then they should intersect an odd number of times and if the permutation does not reverse the order of the endpoints, then the arcs intersect an even number of times. (This is because an arc locally disconnects the plane, so in order to get from one side to the other I have to cross the arc, and if I do it twice, I'm back on the side I started with.) So we have a well-defined intersection number modulo 2.

Now write $\sigma$ as a product of transpositions $\tau_j$, and correspondingly stack the pictures for each $\tau_j$ to get a picture for $\sigma$. Then we just need to verify that the number of crossings in some standard picture of $\tau_j$ is odd, which is easy. All the arcs are straight except two, which form an X-shape. The X shape has one intersection point in the middle and crosses all of the other straight arcs in pairs. So it is an odd intersection number.

If you're familiar with the braid group, you'll notice that this looks likes the braid group, only crossing information has been dropped. Perhaps that's why it appeals to me as a topologist. In any event, I've found that this is a quick way of calculating the parity of a permutation in practice.

A closely related proof, but without nice pictures, is to say that the parity of a permutation is the number of inversions modulo 2, where an inversion is a pair $i<j$ where $\sigma (i)>\sigma(j)$.


I personally like the following proof which sweeps some of the annoying technicalities for some fairly elementary linear algebra.

Consider the action of $S_n$ on $\mathbb R^n$ where $\sigma$ acts by permuting the basis elements, that is, if $v=\sum a_ie_i$ where $\{e_i\}$ is the standard basis for $\mathbb R^n$, then every $\sigma\in S_n$ determines a linear transformation $M_\sigma(v)=\sum a_i e_{\sigma(i)}$. Hence, we have a map $\rho\colon S_n\to GL_n(\mathbb R)$, the group of invertible $n\times n$ real-valued matrices.

This $\rho$ is in fact a group homomorphism since $M_\sigma M_\tau=M_{\sigma\tau}$ by definition of the linear transformations $M_\sigma$.

Now, the determinant in turn is a group homomorphism $GL_n(\mathbb R)\to\{-1,1\}$, the latter being a group under multiplication, so composing it with $\rho$ we get a group homomorphism $\det\circ\rho\colon S_n\to\{-1,1\}$.

Thinking of the determinant as an alternating multilinear form (function on $n$ vectors, linear on each variable, that flips sign when two of its inputs are switched), we see that $\det\circ\rho(\sigma)=\det(M_\sigma)=\det(e_{\sigma(1)}, e_{\sigma(2)},\dots, e_{\sigma(n)})$. Now the fact that transpositions of basis vectors flips the sign of the determinant tells us that transpositions get sent by our map to $-1$, while the identity map gets sent to $1$. Since the determinant is multiplicative, then $\sigma=\tau_1\dots\tau_m$ where $\tau_i$ are transpositions gets sent to $(-1)^m$ which depends only on the parity of $m$, hence $m$ is either always even or always odd.

Update: I now think the linear algebra is too ad-hoc and that counting inversions $\bmod2$ is more natural, as long as its done as follows.

For each permutation $\sigma$, let $N(\sigma)=\{(i,j):\sigma(i)>\sigma(j)$ but $i<j$), i.e. let $N(\sigma)$ be the set of pairs of elements put out of order by the permutation.

Then it follows easily from the definition that

  1. $N((i,i+1))=\{i,i+1\}$ for any adjacent transposition $(i,i+1)$.
  2. $N(\sigma\circ\tau)=\tau(N(\sigma))\Delta N(\tau)$ where $\Delta$ is the symmetric difference of sets, i.e. given $i<j$, we have $\sigma\circ\tau(i)>\sigma\circ\tau(j)$ if and only if either $\{i,j\}\in N(\tau)$ or $\{\tau(i),\tau(j)\}\in N(\sigma)$, but not both.

Then 1. gives that $|N((i,i+1))|=1$ for any adjacent transposition and 2. gives that $|N(\sigma\circ\tau)|=|\tau(N(\sigma))\Delta N(\tau)|=|\tau(N(\sigma))|+|N(\tau)|-2|\tau(N(\sigma))\cap N(\tau)|=|N(\tau)|+|N(\sigma)|-2|\tau N(\sigma)\cap N(\tau)|$ by inclusion-exclusion and permutations being bijections, hence $\tau\mapsto|N(\tau)|\bmod2$ is precisely the parity function on permutations.

In fact, with a little bit of induction, one can show that $|N(\sigma)|$ is the minimimal number of adjacent transpositions needed to write down the permutation $\sigma$. Even better, this point of view suggests what I've found to be the most practical definition of the notion of Coxeter group (c.f. M. Dyer's Reflection Subgroups of Coxeter Systems).

Namely a Coxeter group is a group $G$ generated by a set $S$ of order two elements such that there is a (necessarily unique) well-defined function $G\xrightarrow{N}\bigoplus_{t\in T}\left<t\right>$ where $T=\bigcup_{g\in G}g^{-1}Sg$ such that

  1. $N(s)=s$
  2. $N(gh)=g^{-1}N(h)g+N(g)$

The the above proofs go word for word, characterizing the lengths and parity functions on Coxeter groups. Even better you use this definition as an intermediate step in figuring out easy proofs of the two standard characterizations of Coxeter groups by generators and relations given by a Cartan matrix, and by generators satisfying the (strong) exchange condition. The advantage to this approach is that you don't have to take a detour through linear algebra and representation theory which is what most expositions do. But even for the representation theory, the $G$-module $T$ is useful as it captures canonically the simple roots of a root system.

  • 1
    $\begingroup$ Do you really have a definition of determinant that doesn't use parity of permutation? (I.e. why such multilinear form exists?) $\endgroup$ – Grigory M Jun 20 '11 at 9:04
  • $\begingroup$ @Grigory M: Yes. For any linear map $f:V\to V$ on a vector space of dimension $n$ you can consider the map $\Lambda^n f : \Lambda^n V \to \Lambda^n V$ on the $n$-fold exterior product of $V$. This space is one-dimensional and $\Lambda^n f(x) = x\cdot\det f$. If you look long enough at this, this will morph into @Arturo's proof. $\endgroup$ – Greg Graviton Jun 20 '11 at 12:06
  • 2
    $\begingroup$ @Greg It's obvious that $\dim \Lambda^{top}V\le 1$ but the standard proof of the fact that it is (not 0- but) 1-dimensional uses the theorem from the OP, I believe -- i.e. well-definedness of the parity exactly. (Well, of course, Arturo's proof can be used to define parity, essentially, and then...). $\endgroup$ – Grigory M Jun 20 '11 at 12:51
  • 4
    $\begingroup$ @Grigory: I may be mistaken (elementary facts are sometimes assumed unconsciencely), but if $(e_1,...,e_n)$ is a basis of $V$ then $\bigwedge^n V$ contains $e_1\wedge ...\wedge e_n$. This being zero means $e_1\otimes ...\otimes e_n$ is in the ideal of the tensor algebra $T(V)$ generated by $v\otimes v$. But this is not the case. $\endgroup$ – wildildildlife Jun 20 '11 at 13:43
  • 1
    $\begingroup$ Why is it obvious that $e_1 \otimes ... \otimes e_n$ is not in the ideal generated by $v \otimes v$? $\endgroup$ – Sridhar Ramesh Jun 5 '16 at 19:25

There are lots of possible proofs, here's one based on the cycle decomposition of the permutation. We show that if we multiply a permutation by a transposition from the right (i.e. first applying the transposition), then the parity of the number of cycles always changes.

The number of cycles in the identity permutation is the same as the number of points $n$ (since there are $n$ cycles). Thus for $n$ even, if you multiply an even number of transpositions, you always get a permutation with an even number of cycles; if you multiply an odd number of transpositions, you always get a permutation with an odd number of cycles. For $n$ odd the association is reversed.

Suppose the transposition is $(12)$. There are two cases: either $1,2$ belong to the same cycle or not.

Case 1: $1,2$ belong to the same cycle $(1\alpha2\beta)$. Then in the new permutation the cycle splits to $(1\beta)(2\alpha)$.

Case 2: $1,2$ belong to two different cycles $(1\alpha)(2\beta)$. Then in the new permutation the two cycles join to $(1\beta2\alpha)$.

In the first case we gain one cycle, in the second we lose one cycle. So in both cases, the parity changes.

Here's another one, from Herstein's book. For $i<j$ and a permutation $\pi$, let $\psi(\pi,i,j)$ be $1$ if $\pi(i)>\pi(j)$, and $0$ otherwise. Let $\Psi(\pi) = \sum_{i<j} \psi(\pi,i,j)$. So $\Psi(\pi)$ be the number of indices $i<j$ such that $\pi(i) > \pi(j)$. For the identity we have $\Psi(e) = 0$.

Let $k < l$ and $\tau = \pi (k l)$, so that $\tau(t) = \pi(t)$ for $t \neq k,l$, $\tau(k) = \pi(l)$ and $\tau(l) = \pi(k)$. Since $k,l$ are the only changed entries, in order to consider the change in $\Psi$ we only have to consider pairs $i,j$ in which one of the indices (at least) is $k$ or $l$.

Case 1: Pairs $i<k$ and $i<l$. It is easy to see that $\psi(\pi,i,k) = \psi(\tau,i,l)$ and $\psi(\pi,i,l) = \psi(\tau,i,k)$. So the contribution to $\Psi$ is the same.

Case 2: Pairs $k<i$ and $l<i$. Similar to Case 1.

Case 3: Pairs $k<i$ and $i<l$. This time $\psi(\pi,k,i) = 1 - \psi(\tau,i,l)$ and $\psi(\pi,i,l) = 1 - \psi(\tau,k,i)$. In total, $$ \psi(\pi,k,i) + \psi(\pi,i,l) = 2 - (\psi(\tau,k,i) + \psi(\tau,i,l)). $$

Case 4: The pair $k<l$. Clearly $\psi(\pi,k,l) = 1 - \psi(\tau,k,l)$.

Only Case 4 changes the parity of $\Psi$, and we deduce that multiplying by a transposition changes the parity of $\Psi$. So $\pi$ is a product of an even number of transpositions iff $\Psi(\pi)$ is even.

  • $\begingroup$ Your second paragraph introduces $e$ and $n$ without defining them. What are they? $\endgroup$ – Gerry Myerson Jun 20 '11 at 4:55

Another proof with some similarity to Yuval's 2nd proof:

For elements $w$ of the symmetric group $\mathrm{Sym}(n)$ define the set of inversions of $w$ as $\mathrm{Inv}(w) := \{(i\quad j) \in \mathrm{Sym}(n)\mid i<j \mbox{ and } i^w>j^w\} = \{(i\quad j) \in \mathrm{Sym}(n)\mid \frac{i-j}{i^w-j^w} < 0\}$.

Claim: $\mathrm{Inv}(w_1\cdot w_2) = \mathrm{Inv}(w_1)+\mathrm{Inv}(w_2)^{w_1^{-1}}$, where $+$ denotes the symmetric difference of sets.

Proof: $(i\quad j) \in \mathrm{Inv}(w_1\cdot w_2)$ is equivalent to $\displaystyle\frac{i-j}{i^{w_1w_2}-j^{w_1w_2}} = \frac{i-j}{i^{w_1}-j^{w_1}}\cdot\frac{i^{w_1}-j^{w_1}}{i^{w_1w_2}-j^{w_1w_2}}<0$, and the latter is equivalent to either $(i\quad j) \in \mathrm{Inv}(w_1)$ or $(i\quad j)^{w_1} = (i^{w_1}\quad j^{w_1}) \in \mathrm{Inv}(w_2)$.

Defining now $\mathrm{sgn}(w) := |\mathrm{Inv}(w)| \bmod 2$ to be the cardinality of the set of inversions modulo $2$, the claim shows that $\mathrm{sgn}(w)$ is a group homomorphism from $\mathrm{Sym}(n)$ to $Z_2$, which is onto, as clearly $\mathrm{Inv}((i\quad i+1)) = \{(i\quad i+1)\}$. Since all transpositions are conjugate, so are their images under $\mathrm{sgn}$, i.e., $\mathrm{sgn}(\tau) = 1$ (we write $Z_2$ additively here), implying Theorem 5.4.

  • $\begingroup$ Instead of the action on the set of transpositions by conjugation one can take also the equivalent action on ordered pairs $(i, j)$ with $1\le i<j\le n$. $\endgroup$ – j.p. Jan 5 '18 at 6:45
  • $\begingroup$ The power set of a (finite) set is an elementary abelian $2$-group with respect to symmetric difference and cardinality mod $2$ a homomorphism to $Z_2$. $\endgroup$ – j.p. Jan 5 '18 at 6:59

We develop all the necessary theory here without recourse to cycles/orbits/etc.

You are about to enter another dimension. A dimension not only of sight and sound, but of mind. A journey into a wondrous land of imagination.

Next stop, the Transparent-Transposition-Transformation-Tour!

Recall that the symmetric group $S_n$ has $n!$ elements; we assume here that the transformations in $S_n$ operate on the set $\{1,2,\dots,n\}$. We also have

Proposition 1: There is a canonical injection ${\iota_{n+1}^n}: S_n \to S_{n+1}$ sending the bijections in $S_n$ to the bijections in $S_{n+1}$ that keep $n+1$ fixed.

Let ${S_n}^{'} = {\iota_{n+1}^n}(S_n) \subset S_{n+1}$.

Theorem 2: For every bijection $\sigma \in S_{n+1}$ not in ${S_n}^{'}$ there exists a unique $\sigma^{'} \in {S_n}^{'}$ and transposition of the form $(n+1 \, k) \,\text{with}\, 1 \le k \le n$ such that

$\tag 1 \sigma = \sigma^{'} \circ (n+1 \, k)$ Proof
Assume that ${{\sigma}_0}^{'} \circ (n+1 \, k_0) = {{\sigma}_1}^{'} \circ (n+1 \, k_1)$. Now ${{\sigma}_0}^{'} \circ (n+1 \, k_0)$ applied to $k_0$ must be $n + 1$ and ${{\sigma}_1}^{'} \circ (n+1 \, k_1)$ applied to $k_1$ must also be $n + 1$. Since we are dealing with injective mappings, $k_0$ must be equal to $k_1$. But then of course, ${{\sigma}_0}^{'} = {{\sigma}_1}^{'}$.

Since $(n+1)! = (n + 1) n!$, a counting argument shows that these unique representations 'cover' all the permutations in $S_{n+1}$ not in ${S_n}^{'}$. $\quad \blacksquare$

To assist in understanding and increase the 'aesthetics quotient', you can regard the (1) representation as true for any element in $S_{n+1}$, where you allow $k$ to be $0$ and agree that $(n+1 \, 0)$ is the identity transformation.

Corollary 3: Every permutation in $S_{n}$ not equal to the identity transformation $1_{Id}$ can be expressed as the composition of $n-1$ or fewer transpositions.
Proof (Sketch)
Use induction and apply theorem 2. $\quad \blacksquare$

Corollary 4: Let $A: \{2,3,\dots,n\} \to \{1, 2,3,\dots,n\}$ be any function satisfying $A(k) \lt k$. Then the $n-1$ transpositions $(k \, A(k))$ generate the symmetric group $S_n$.
Proof: Exercise.

We are now prepared to answer the OP's question.

Lemma 5: Let $\sigma \in S_{n+1}$ be represented as the composition of $M$ transpositions. Then it can also be expressed as the composition of $M$ transpositions,

$\tag 2 \sigma = \alpha_1 \alpha_2 \cdots \alpha_s \beta_1 \beta_2 \cdots \beta_t \text{ with } M = s + t$ satisfying

$\qquad \text{Each } \alpha_u \in {S_n}^{'}$
$\qquad \text{Each transposition } \beta_u \text{ acts on } n + 1$

Proof (Sketch)
Using elementary facts about transpositions (see next section), we can keep 'pushing to the right side' transpositions that act on $n+1$ to new transpositions that still act on $n +1$. $\quad \blacksquare$

The idea now is, see what happens when you try to push $\beta_1$ to the right. The answer is either $M$ remains the same with $s$ increasing by 1 and $t$ decreasing by $1$, or $M$ goes down by $2$ with $t$ decreasing by $2$.

Example 6: Let $n + 1 = 10$ and $\beta_1 = (10 \, 5)$ and $\beta_2 = (10 \, 6)$. Then $\beta_1 \circ \beta_2 = (6 \, 5) \circ (10 \, 5)$.

Example 7: Let $n + 1 = 10$ and $\beta_1 = (10 \, 5)$ and $\beta_2 = (10 \, 5)$. Then $\beta_1 \circ \beta_2$ collapses to the identity transformation.

Lemma 8: Let $\sigma \in S_{n+1}$ be represented as the composition of $M$ transpositions. Then it can also be expressed as the composition of $s + 1$ transpositions,

$\tag 3 \sigma = \alpha_1 \alpha_2 \cdots \alpha_s \beta$ satisfying

$\qquad \text{Each } \alpha_u \in {S_n}^{'}$
$\qquad \text{The transposition } \beta \text{ acts on } n + 1$ (or $\beta = \text{Identity}$)
$\qquad s + 1 \le M \text{ and } M = s + 1 \text{ mod 2}$ when $\beta \ne \text{Identity}$
$\qquad s \le M \text{ and } M = s \text{ mod 2}$ when $\beta = \text{Identity}$

Proof: Exercise.

Theorem 9: Let a permutation $\sigma$ be expressed as the product of $k$ transpositions and also as the product of $j$ transpositions. Then either $k$ and $j$ are both even or they are both odd.
We shall use induction on the number of elements $\{1,2,\dots,n\}$ that are being permuted.

One can see immediately that the theorem holds for $n = 2$.

Suppose the theorem is true for $n$ and let $\sigma$ be a permutation in $S_{n+1}$ represented as the product of $M$ transpositions. If $\sigma(n+1) = n+1$, then $\sigma \in {S_n}^{'}$ and the argument falls right into a case that can be directly handled by our induction hypothesis. Otherwise, we can apply lemma 8 and put $\sigma$ into the form (3), with $\beta$ not the identity. By our induction hypothesis, the length of the $\alpha\text{-stuff}$ can only be odd or even. Adding $1$ for $\beta$ changes nothing in terms of stating that the parity is well-defined. $\quad \blacksquare$

The OP mentioned these elementary facts about transpositions:

\begin{align}(ab)(ab)&= 1_{Id}\\ (ab)(ac)&=(bc)(ab)\\ (ab)(cd)&=(cd)(ab)\\ (ab)(bc)&=(bc)(ac)\end{align}

With $a = n + 1$, you see how you can 'push to the right' the '$n + 1\text{-transpositions}$', occasionally getting a 'collapse' upon encountering $(ab)(ab)$, since the inverse transformations cancel out.

We prove the following lemma that was analyzed by the OP:

Lemma: If $1_{Id} =\tau_1\tau_2\cdots\tau_M$ where the $\tau$'s are transpositions on $\{1,2,\dots,n+1\}$, then $M$ is even.
The lemma is true for $n = 0$ and also (if you are skeptical) for $n = 1$.
Assume that the lemma holds for any $n \gt 1$. By lemma 8, for the identity transformation $1_{Id} \in S_{n+1}$ we have a (2) representation,

$\tag 1 1_{Id} = \alpha_1 \alpha_2 \cdots \alpha_s \beta$

respecting the original parity of $M$. Now $\alpha_1 \alpha_2 \cdots \alpha_s$ is in ${S_n}^{'}$. By theorem 2 there is one and only one such representation, so $\beta$ must be the identity (not really there). So we have

$\tag 2 1_{Id} = \alpha_1 \alpha_2 \cdots \alpha_s$

But each $\alpha_u \in {S_n}^{'}$, so by our inductive hypothesis $s$ is even and so $M$ must also be even. $\quad \blacksquare$


You can prove that a presentation of $S_n$ is given by:

$$S_n = \langle \tau_1, \ldots, \tau_{n-1} \mid \tau_i^2 = 1, \tau_i \tau_j = \tau_j \tau_i \mathrm{~for~}|i-j|\ge 2, \tau_i \tau_{i+1} \tau_i = \tau_{i+1} \tau_i \tau_{i+1} \rangle.$$

Here, $\tau_i$ represents the transposition of $i$ and $i+1$. From this presentation, it is straightforward to check that there is a unique homomorphism $S_n \to \{ \pm 1 \}$ which sends each $\tau_i$ to $-1$.

For a rough outline of how to prove this presentation: it is fairly straightforward (and probably a common exercise) to prove that $\tau_1, \ldots, \tau_{n-1}$ generate $S_n$. Now, using the relations given, it is possible to show that any product of these transpositions can be expressed, modulo the given relations, as $$\sigma = C_{m_n, n} C_{m_{n-1}, n-1} \cdots C_{m_2, 2}$$ for some $m_2, \ldots, m_n$, where $C_{i, j} = \tau_i \tau_{i+1} \cdots \tau_{j-1}$ (and in particular, $C_{j, j} = 1$). But now, if this combination is equal to the identity in $S_n$, then it is straightforward to check that $\sigma(n) = m_n$, so $m_n = n$ and $C_{m_n, n}$ is formally the identity. Then, from there, you conclude $\sigma(n-1) = m_{n-1} = n-1$, and so on, so $\sigma$ was already the identity. This shows that the given set of identities generates all identities.

(Incidentally, the form of the presentation I have given was chosen so that if you drop the relations $\tau_i^2 = 1$, you get exactly a presentation of the braid group on $n$ strands, with $\tau_i$ representing "passing strand $i$ over strand $i+1$".)


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.