Identity permutation as product of even number of 2-cycles

[Kaguro]

Homework Statement

Prove that the identity permutation can be written as $\beta_1 \beta_2...\beta_{r-1} \beta_r$ where $\beta$ are 2-cycles and r is even.

Relevant Equations

None

The book I'm following (Gallian) basically says:

r can't be 1 since then it won't map all elements to themselves.

If r=2, then it's already even, nothing else to do.

If r>2,
Then consider the last two factors: $\beta_{r-1} \beta_r$.
Let the last one be (ab).

Since the order of elements inside a two cycle is irrelevant (xy)=(yx), all possible ways to write the last two factors are:

(ab)(ab)
(ac)(ab)
(bc)(ab)
(cd)(ab)

Why?!

What happened to the other ones like : (ad)(ab) and (bd)(ab) ?

 

[fresh_42]

Homework Statement:: Prove that the identity permutation can be written as $\beta_1 \beta_2...\beta_{r-1} \beta_r$ where $\beta$ are 2-cycles and r is even.
Relevant Equations:: None

The book I'm following (Gallian) basically says:
r can't be 1 since then it won't map all elements to themselves.
If r=2, then it's already even, nothing else to do.
If r>2,
Then consider the last two factors: $\beta_{r-1} \beta_r$.
Let the last one be (ab).
Since the order of elements inside a two cycle is irrelevant (xy)=(yx), all possible ways to write the last two factors are:
(ab)(ab)
(ac)(ab)
(bc)(ab)
(cd)(ab)

Why?!

What happened to the other ones like : (ad)(ab) and (bd)(ab) ?

I don't understand the problem. Are you sure you translated it correctly? You can always write $1=\prod_{k=1}^ng_k \cdot \left(\prod_{k=1}^ng_k\right)^{-1}$ in any group. Here e.g. $(1)=\ldots (ef)(cd)(ab)(ab)(cd)(ef)\ldots$

 

[Kaguro]

Check this one:
https://math.stackexchange.com/ques...itten-as-the-product-of-r-transpositions-then

All the answers mention that if (ab) is the last element then there can be only 4 types of transpositions possible for the second last element.

 

[fresh_42]

Check this one:
https://math.stackexchange.com/ques...itten-as-the-product-of-r-transpositions-then

All the answers mention that if (ab) is the last element then there can be only 4 types of transpositions possible for the second last element.

Maybe, but you said: "if ... then can be written as ... " and I gave the answer that this is always trivially the case:
$$
1 = g_n (g_{n-1}(g_{n-2}(\ldots (g_3(g_2(g_1g_1^{-1})g_2^{-1})g_3^{-1}) \ldots )g_{n-2}^{-1})g_{n-1}^{-1})g_n^{-1}
$$
$2n$ elements whose product is $1$ - in any group.

 

[Kaguro]

See the proof from Gallian textbook:

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.Suppose that the rightmost 2-cycle is (ab). Then, since (ij) = ( ji), the product $\beta_{r-1} \beta_r$ can be expressed in one of the following forms shown on the right:
e= (ab)(ab),
(ab)(bc) = (ac)(ab),
(ac)(cb) = (bc)(ab),
(ab)(cd) = (cd)(ab).

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}$, and therefore, by the Second Principle of
Mathematical Induction, r -2 is even. In the other three cases, we replace the form of $\beta_{r-1} \beta_r$ on the right by its 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 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 process, 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.

 

[Kaguro]

I don't understand how can the author say only these are the possible elements..

Can you help me?

 

[Kaguro]

Maybe, but you said: "if ... then can be written as ... " and I gave the answer that this is always trivially the case:
$$
1 = g_n (g_{n-1}(g_{n-2}(\ldots (g_3(g_2(g_1g_1^{-1})g_2^{-1})g_3^{-1}) \ldots )g_{n-2}^{-1})g_{n-1}^{-1})g_n^{-1}
$$
$2n$ elements whose product is $1$ - in any group.

Yes. I see this is obviously one way to write the identity. I'm trying to see why every possible identity has to be a product of even number of 2-cycles?

 

[fresh_42]

Firstly, I think the statement which is proven is another than you wrote it is. It says:

If we have a product of length $r$ of transpositions which multiply to the identity, then $r$ is necessarily even.

It doesn't say there is such a representation, it says if there is such a representation, then its length is even. It is a step towards the theorem that the sign function is a group homomorphism $\varphi \, : \,\operatorname{Sym}(n) \longrightarrow \{\pm 1\}\, , \,\varphi (\sigma )=(-1)^r$.

Secondly, that there are only four possibilities is a simple observation: Given $(ab)$ as last transposition on the right, and having another transposition $(xy)$ on the left of it, then there are obviously four possibilities:
$\{a,b\}\cap\{x,y\}=\{a,b\}\, , \,\{a,b\}\cap\{x,y\}=\{a\}\, , \,\{a,b\}\cap\{x,y\}=\{b\}\, , \,\{a,b\}\cap\{x,y\}=\emptyset$. These are all possible constellations for the numbers $x,y.$

 

[Kaguro]

Secondly, that there are only four possibilities is a simple observation: Given $(ab)$ as last transposition on the right, and having another transposition $(xy)$ on the left of it, then there are obviously four possibilities:
$\{a,b\}\cap\{x,y\}=\{a,b\}\, , \,\{a,b\}\cap\{x,y\}=\{a\}\, , \,\{a,b\}\cap\{x,y\}=\{b\}\, , \,\{a,b\}\cap\{x,y\}=\emptyset$. These are all possible constellations for the numbers $x,y.$

... Oh.

Didn't think of it like that.. So c and d are just placeholders for any number which is not a and b. So (bc) and (bd) are equivalent. And (ac) and (ad) are equivalent...

Right... I'm an idiot.

 

[Kaguro]

Thank you very much! Now I can progress.