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

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

I just don't understand the proof given in gallian to this, help would be appreciated

Proof: Clearly, r $\neq$1, since a 2 cycle is not the identity. If $r =2$, we are done. So, we suppose that $r>2$ and we proceed by induction.

Since, $(ij) = (ji)$, the product $\beta_{r-1}\beta_r$ can be expressed in one of the following forms shown on the right :

$\epsilon = (ab)(ab)$

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

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

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

What is the use of analyzing such expressions, 2 cycles are still retained?

If the first case occurs, we may delete $\beta_{r-1}\beta_r$ from the original product to obtain $\epsilon = \beta_1 \beta_2 ...... \beta_{r-2}$.

In the other three cases, we may replace the form of $\beta_{r-1}\beta_r$ on the right by it's counterpart on the left 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 of the product instead of the rightmost 2 cycle. we now repeat the 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.

Continuing this product we must obtain a product of $(r-2)~ 2$ cycles equal to the identity because otherwise we have a product equal to the identity in which the only occurrence of the integer a is in the leftmost 2 cycle, and such a product does not fix a, whereas the identity does. Hence, by the second principle of mathematical induction, $r-2$ is even and r is even as well.

So, basically, what they are doing is removing the last terms. The motive's a little confusing, so, can anyone please tell me what they are basically trying to do in a simpler language?

Thank you

Solution 1:

The idea is to have a equation RHS of which is the identity permutation (thus fixing every number) and whose LHS is a permutation which doesn't fix atleast one object ($a$ in the proof) thus arriving at a contradiction.

Observe that if the first case occurs,i.e., $\epsilon=(ab)(ab)$, then you can use induction hypothesis to deduce that $r$ must be even. The remaining portion is arguing that we'll eventually get $r-2$ cycles in rest of the cases also. For that, same representation of the first two-cycles is changed slightly so as to have the occurence of $a$ from the first cycle to the second one. (Note that there is nothing special about $a$ here. You can follow the same procedure with any of the symbols.) Now continue above procedure with the second and third two-cycles. Now $a$ occurs at second position. So we will shift it to $3$rd position. Continuing, we'll get $\epsilon$ = an expression of two-cycles where $a$ occurs exactly in the last cycle. But this is not possible because identity fixes $a$ but in the expression on RHS $a$ is occuring $only\ in$ the last cycle so it can never be fixed as for fixing it we need its occurence in any other cycle of the expression.