Clarification needed regarding why identity can be written only as a product of even number of 2-cycles

Question

I'm writing in reference to the answer to the question: If $\epsilon = \beta_1 \beta_2 ...... \beta_r$ where the $\beta's$ are 2- cycles, then r is even.

To be honest, even after looking after the answer a few things are unclear to me.

1. I don't understand the use of expressing $\epsilon$ in the forms:

   $\epsilon = (ab)(ba)$,

   $(ab)(bc)=(ac)(bc)$,

   $(ac)(cb)=(bc)(ab)$,

   $(ab)(cd)=(cd)(ab)$

   Could someone tell me how he came up with these random forms of permutations (for the last two positions)? Is there any logic involved which I'm missing?

   If $\beta_{r-1}\beta_r$ is in the first form I understand that that would be equal to the identity permutation and in that case we can just omit $\beta_{r-1}\beta_r$. BUT, how can we conclude from that $r-2$ is even, from there? Gallian says that it is by "Second Principle of Mathematical Induction". No idea what that means.

2. Gallian says that in the other three cases we need to replace the form of $\beta_{r-1}\beta_r$ on the right by "its counterpart on the left"? What does "counterpart" mean in this context? (I'm sorry if that's a silly question, but English isn't my first language, so I might be having trouble interpreting)

3. Moreover, what does he mean by "to obtain a new product of $r$ 2-cycles that is still the identity, but where the rightmost occurrence of the integer $a$ is in the second-from-the-rightmost 2-cycle". We now repeat the procedure just described with $\beta_{r-2}\beta_{r-1}$ and as before we obtain a product of $(r-2)$ 2-cycles equal to the identity or a new product of $r$ $2$-cycles where the rightmost occurrence of $a$ is in the third $2$-cycle from the right"?

Answer 1

Rather than discuss this specific proof, let me try to explain transpositions ($2$-cycles) a little more clearly and see if you can then understand Gallian's proof.

It seems that this author is using left multiplication, so we read the permutations right-to-left. That is, the permutation $\sigma\gamma = (a \quad b)(c \quad d)$ is read $\gamma = (c \quad d)$ first and then $\sigma = (a \quad b)$.

Now, the identity is the permutation that maps everything to itself. We can write this as $\varepsilon$, or as $1$, or as $(1)(2)\cdots(n-1)(n) = (n)(n-1)\cdots(2)(1)$ depending on your preference of notation. To show whether a permutation is even or odd, we have to decompose it into a product of transpositions and then count how many transpositions there are --- if it's even, then the permutation is even; if it's odd, the permutation is odd.

Consider the permutation product $$ (a \quad b)(a \quad b). $$ In this product, we have that $a \mapsto b$ in the first (the rightmost) permutation, and then $b \mapsto a$ in the second (the leftmost) permutation, so that $a \mapsto b \mapsto a$ and we see that $a$ maps to itself under this permutation. Similarly, we have that $b \mapsto a \mapsto b$ so that $b$ also maps to itself. Thus, the product is $$ (a \quad b)(a \quad b) = (b)(a) = \varepsilon. $$ So the product of any transposition with itself is the identity transposition. But since these are cyclic permutations, writing $(a \quad b)$ is exactly the same as $(b \quad a)$ --- they both indicate that $a$ maps to $b$ and that $b$ maps to $a$. So, we can write $$ (a \quad b)(a \quad b) = (a \quad b)(b \quad a) = (b \quad a)(a \quad b) = (b \quad a)(b \quad a) $$ as they all mean the same thing, and in fact all are the identity permutation.

Now, what the author is doing is showing that any product of transpositions can be written a couple of different ways. The base case for the induction is your first point. We just saw that $(a \quad b)(b \quad a)$ is the identity, and then the remainder of the first point is just analysing the different forms of the products of permutations. The inductive part is that the base case is proved to be true when $r = 2$ which is even, so assume that it's true for even $r$ up to $r - 2$. You show then that it is true for $r$ by breaking it up into an product of $r - 2$ transpositions (which is identity by assumption) and a product of transpositions that are also the identity. This is elaborated in Kenny Lau's answer.

Answer 2

Here is the inductive step phrased more concretely:

Let $\epsilon = (a_1 b_1) (a_2 b_2) (a_3 b_3) \cdots (a_{r-1} b_{r-1}) (a_r b_r)$.

Now, we will show that we can reduce the product to the product of $r-2$ 2-cycles.

1. If $a_{r-1} = a_r$ and $b_{r-1} = b_r$, then just remove the last two 2-cycles and we are done.

2. If $a_{r-1} = a_r$, i.e. it matches the right hand side of the second pattern $(ac)(ab)$ with $a=a_r$ and $b=b_r$ and $c=b_{r-1}$, then rewrite it as $(ab)(bc)$, i.e. now we have $$\epsilon = (a_1 b_1) (a_2 b_2) (a_3 b_3) \cdots (a_r b_r) (b_r b_{r-1})$$ Note how $a_r$ is no longer in the last cycle.

3. If $a_{r-1} = b_r$, i.e. it matches the right hand side of the third pattern $(bc)(ab)$ with $a=a_r$ and $b=b_r$ and $c=b_{r-1}$, then rewrite it as $(ac)(cb)$, i.e. now we have $$\epsilon = (a_1 b_1) (a_2 b_2) (a_3 b_3) \cdots (a_r b_{r-1}) (b_{r-1} b_r)$$ Note how $a_r$ is no longer in the last cycle.

4. If $a_{r-1}$, $b_{r-1}$, $a_r$, $b_r$ are all distinct, i.e. it matches the right hand side of the fourth pattern $(cd)(ab)$ with $a=a_r$ and $b=b_r$ and $c=a_{r-1}$ and $d=b_{r-1}$, then rewrite it as $(ab)(cd)$, i.e. now we have $$\epsilon = (a_1 b_1) (a_2 b_2) (a_3 b_3) \cdots (a_r b_r) (a_{r-1} b_{r-1})$$ Note how $a_r$ is no longer in the last cycle.

In the last three cases (2, 3, 4), we still have $r$ 2-cycles, but $a_r$ is now moved to the first position of the second-last 2-cycles, so we can repeat this until we moved $a$ to the first position. Note that in the process of repeating, we may match the first case and terminate.

We will have a contradiction once we successfully moved $a$ to the first position, because then $a$ would not be fixed by $\epsilon$.

Answer 3

We are in an induction step and want to show that if $\epsilon$ can be expressed as product of $r$ 2-cycles, then $r$ is even; for this, we may make use of the induction hypothesis: If $\epsilon$ can be expressed as product of $r'$ 2-cycles with $r'<r$, then $r'$ is even.

In particular, if we find an expression for $\epsilon$ with $r-2$ 2-cycles, we conclude from the induction hypothesis that $r-2$ is even and hence also that $r$ is even. For the rest of the argument, we may therefore assume that $\epsilon$ cannot be expressed with $r-2$ 2-cycles. Now can formalize the rest of the argument with a slightly different angle of view: Let $a$ be a number affected by the first 2-cycle. Then we can show

If $1\le k\le r$, then there exists an expression for $\epsilon$ with $r$ two-cycles such that $a$ occurs in the $k$th 2-cycle but not in any earlier 2-cycle.

This claim about $k$ calls for another induction. The case $k=1$ is clear by the choice of $a$. Assume $1<k\le r$ and $k-1$ has said property. So we can write $\epsilon=\beta_1\cdots \beta_{r}$ where $a$ occurs in $\beta_{k-1}$ but not earlier. Say, $\beta_{k-1}=(a\,b)=(b\,a)$ for some $b\ne a$. Then $\beta_k\ne (a\, b)$ because that would allow us to drop these and obtain an expression with $r-2$ 2-cycles. Hence $\beta_k$ has at most one number in common with $\beta_{k-1}$. Depending on if and which, we can thus write $\beta_k=(a\,c)$ or $\beta_k=(b\,c)$ or $\beta_k=(c\,d)$, where $c,d\notin\{a,b\}$. But $(a\,b)(a\,c)=(b\,c)(a\,b)$, $(a\,b)(b\,c)=(b\,c)(a\,c)$, and $(a\,b)(c\,d)=((c\,d)(a\,b)$ so that by replacing $\beta_{k-1}$ and $\beta_k$ accordingly, we obtain the desired expression for $\epsilon$ with $r$ 2-cycles and $a$ occurring in the $k$th 2-cyle but not earlier. $\square$

As a consequence, we can express $\epsilon=\beta_1\cdots\beta_r$ where $a$ occurs in $\beta_r$ and in none of the other $\beta_i$. But then the right hand side maps $a$ away from $a$, contradiction.