28
$\begingroup$

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?

  • 5
    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.2011-06-20

7 Answers 7

24

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\} \to \{\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.

  • 0
    This is also the way the proof is given in Dummitt and Foote, and I found it to be much more insightful this way than as presented in the OP.2014-07-04
19

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 where $\sigma (i)>\sigma(j)$.

14

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), 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, 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$ 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.

  • 0
    If you expand an arbitrary element of the ideal generated by $v\otimes v$, you will see that the result can only be a monomial $e_{i_1}\otimes\cdots\otimes e_{i_k}$ if $e_{i_1}\otimes\dots\otimes e_{i_j-1}\otimes e_{i_{j+1}}\otimes e_{i_j}\otimes e_{i_{j+2}}\cdots\otimes e_{i_k}$ is also in the ideal for some $j$ (this relies on the ground ring being commutative). By ordering the monomials lexicographically, it follows that there is no smallest monomial in the ideal, hence no monomial at all.2016-06-06
8

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 and a permutation $\pi$, let $\psi(\pi,i,j)$ be $1$ if $\pi(i)>\pi(j)$, and $0$ otherwise. Let $\Psi(\pi) = \sum_{i. So $\Psi(\pi)$ be the number of indices $i 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 and $i. 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 and $l. Similar to Case 1.

Case 3: Pairs $k and $i. 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. 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.

  • 0
    Your second paragraph introduces $e$ and $n$ without defining them. What are they?2011-06-20
1

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 ij^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.

  • 0
    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$.2018-01-05
1

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}^{'}$
And
$\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}^{'}$
And
$\qquad \text{The transposition } \beta \text{ acts on } n + 1$ (or $\beta = \text{Identity}$)
And
$\qquad s + 1 \le M \text{ and } M = s + 1 \text{ mod 2}$ when $\beta \ne \text{Identity}$
And
$\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.
Proof
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.
Proof
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$

0

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$".)