Prove in a Symmetric group, have any transposition given by product of three transpositions.

Question

Let, there be need to show that $(i\ j)$ be given by product of three transpositions in $S_n.$

But, transpositions are composed of two elements only, so different. More restrictions on cycle size means should be able to take advantage of this rule too?

Now need to show using cycles, any element can be mapped to another. To prove this as possible, need consider first the restricted form, of $2$-cycles. If it is proved in restricted form of $2$-cycles, then can extend to cycles too.

Still unclear, as how to conclude.

Also, unclear if such approach has unique representation?

Request hint in either case.

Next, seems exactly $n-1$ transposition are needed.

Answer 1

Remember that any permutation $\sigma$ can be written as a product of transpositions, so the statement is true if it’s true for transpositions $(i, j)$. We already proved that

$$(i, j)=(j, j-1)(i, j-1)(j, j-1)$$

So we can prove the statement by induction on $j\geq 3$.

If $j$ is equal to $3$, then

if $i=2$, we get $(2, 3)$ and we have done,

while if $i=1$, then $(1, 3)=(3, 2)(1, 2)(3, 2)$ and we have done too.

Suppose the statement is true for some $j’\leq j$. Our claim is to prove it for $j$.

We know that

$$(i, j)=(j, j-1)(i, j-1)(j, j-1)$$

However $j>i+1$ so $j-1\geq i+1$. If $j-1=i+1$, then we get $(i, j-1)=(i, i+1)$ and we have done, while if $j-1>i+1$, then we can apply inductive hypothesis to $j’:=j-1$ to say that the statement is true for $(i, j-1)$. Hence the statement results to be true also for $(i, j)$.