0
$\begingroup$

Prove that for $n>4$ every permutation in $S_n$ can be written as the product of 4-cycles.

Consider $\alpha=(a_1 a_2 a_3)(a_4 a_5)$ is the product of two disjoint cycles and $\alpha\in S_5$. We can write (according to a previous theorem) the following number of cycles $\alpha=(a_1 a_3)(a_1a_2)(a_4 a_5)$, which is less than 4.

Question:

1) Is $\alpha=(a_1 a_3)(a_1a_2)(a_4 a_5)$ the biggest number of cycles that can be written on this particular case? I have only learnt this technique.

2) How do I maximize or minimize the number of cycles for a given permutation?

$\endgroup$
  • $\begingroup$ A $4$-cycle is a permutation of the form $( \alpha \beta \gamma \delta)$. I think the theorem is saying every element of $S_n$ can be expressed in the form $(b_{11} b_{12} b_{13} b_{14}) \cdots (b_{k1} b_{k2} b_{k3} b_{k4})$ ? $\endgroup$ – Donald Splutterwit Oct 14 '17 at 20:24
  • $\begingroup$ How can you build $( \alpha \beta \gamma \delta)$ with 5 elements permutation like the one I presented? the number that follows $n>4$ is 5. Just to clarify the notation $S_n$ means the permutations of $\{1,...,n\}$ elements. Thanks for your insight. $\endgroup$ – Pedro Gomes Oct 14 '17 at 20:29
  • $\begingroup$ The $4$-cycles are not required to be disjoint. $\endgroup$ – Somos Oct 14 '17 at 20:50
  • $\begingroup$ @Somos I am considering all the possibilities, so that I can prove the preposition. $\endgroup$ – Pedro Gomes Oct 14 '17 at 21:06
  • 1
    $\begingroup$ @Somos Yes by $S_n$ I mean the symmetric group on $n$ elements. Every element of a permutation group can be expressed as the product of transpositions. Now $(1423)(1425)(1432)=(45)$ so every transposition can be expressed as the product of $4-$ cycles and therfore any any element of a permutation group can be expressed as a product of $4$-cycles. Thus the theorem is proved (albeit by quite a greedy algorithm). $\endgroup$ – Donald Splutterwit Oct 14 '17 at 21:12
2
$\begingroup$

Another approach: $S_n$ is generated by $A_n$ and any odd permutation, because $A_n$ has index $2$. $A_n$ is generated by $3$-cycles: This is much easier to verify. And $(1234)(1243)=(132)$. By similar arguments, we've generated all $3$-cycles we need. Thus the $4$-cycles generate $A_n$. And the $4$-cycles themselves are odd permutation, thus also $S_n$ is generated.

$\endgroup$
1
$\begingroup$

Every element of a permutation group can be expressed as the product of transpositions. Every transposition can be expressed as the product of $4$-cycles E.g $(1423)(1425)(1432)=(45)$ so every element of a permutation group can be expressed as a product of $4$-cycles. Thus the theorem is proved.

$\endgroup$
  • $\begingroup$ +1 for writing that transposition as product of $4$-cycles. I am lazy and was too impatient to find such product. So I have another indirect approach. $\endgroup$ – user441558 Oct 15 '17 at 5:32
0
$\begingroup$

For question (2) the minimum is achieved if the cycles are disjoint but there is no maximum because you can always add $(ab)(ab)$ to a composition of cycles permutation unless the cycles must be disjoint.

$\endgroup$
  • $\begingroup$ The "maximum" question can be more fruitfully interpreted as, among all permutations of $n$ symbols, which ones require the most transpositions, and how many do they require? But I think the simple answer is that an $n$-cycle requires $n-1$, and no other permutation requires more. $\endgroup$ – Gerry Myerson Oct 14 '17 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.