Decomposing a permutation into 3-cycles

Question

I have two exercises I don't know how to solve:

1. Write the permutation $α = (1 2)(3 4)$ as a product of 3-cycles
2. Write the permutation $α = (1 2 8 3 7)(4 5 6)$ as a product of 3-cycles

I know how to convert a permutation into a composition of 2-cycles, but not of 3-cycles. I imagine there is a rule for when this is possible, depending on odd/even properties, but since I'm am using the exercises mentioned to help me to learn about permutation parity, I can't yet follow arguments based on that understanding.

Also, I am working with left to right composition such that $(123) = (12)(13)$.

Thanks in advance for any help.

Answer 1

First, notice that, since 3-cycles are even, and products of even permutations are even themselves (if you know what it means, this comes from the fact that the map sending each permutation to its sign is a homomorphism), for a permutation to be written as a product of 3-cycles you need it to be even. Luckily, your $\alpha$'s are.

Now, let me give you the general argument here, that hopefully you will be able to specialize to the cases above. Take an even permutation $\sigma$ and write it as a product of transpositions, say $\tau_1\cdots\tau_k$, where $k$ must be even. Looking at $\tau_1\tau_2$, you can suppose $\tau_1\neq\tau_2$, otherwise their product is the identical permutation. Then, you have two cases:

1. $\tau_1=(ab),\tau_2=(ac)$, i.e. $\tau_1,\tau_2$ permute a common number, say $a$. In this situation, as you noted for $(123)$, $(ab)(ac)=(abc)$, so $\tau_1\tau_2$ is a 3-cycle;
2. $\tau_1=(ab),\tau_2=(cd)$, with $a,b,c,d$ different, i.e. they are disjoint. In this case, write $(ab)(cd)=(ab)(bc)(bc)(cd)$ and you get a product of two 3-cycles by point 1.

Iterating and using the fact that $k$ is even, you get a full decomposition of $\sigma$ in 3-cycles. Incidentally, this actually proves that any even permutation can be written as a product of 3-cycles (again, provided you are familiar with the terminology, $A_n$ is generated by 3-cycles).

Answer 2

Cristofer already answered your question, so I'll just add the general case since you were wondering if there's a "rule" for when things could be decomposed. This is something I learned from Beardon Algebra and Geometry but surely there are more references.

Theorem. Let $\sigma\in S_n$ be a permutation, $2 \leq m \leq n.$ Then $\sigma$ can be decomposed as a product of $m$-cycles $\iff$ either $m$ is even or $\sigma$ is an even permutation.

Proof. $\implies$ should be easy, as if $\sigma$ is an odd permutation then all the $m$-cycles needs to be odd permutations, so $m$ is even.

$\impliedby$ Case I. If $\sigma$ is an even permutation, then notice $\left(a_{1} a_{2}\right)\left(a_{1} a_{3}\right)=\left(a_{1} a_{2} a_{3} a_{4} \cdots a_{m}\right)\left(a_{m} \cdots a_{4} a_{3} a_{1} a_{2}\right)$ (or, the other way since you are using left-to-right composition) and Cristofer's trick in (2) that $(ab)(cd)=(ab)(bc)(bc)(cd)$ would allow you to write $\sigma$ as a product of $m$-cycles.

Case II. If $\sigma$ is an odd permutation but $m$ is even, then apply Case I to decompose $\sigma (1 2 3 ... m)$ into $m$-cycles which is an even permutation, and multiply $(m (m-1) ... 2 1)$ on the right when you finish gives you $m$-cycle decomposition of $\sigma$.