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$
7
  • $\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$ Commented Oct 14, 2017 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$ Commented Oct 14, 2017 at 20:29
  • $\begingroup$ The $4$-cycles are not required to be disjoint. $\endgroup$
    – Somos
    Commented Oct 14, 2017 at 20:50
  • $\begingroup$ @Somos I am considering all the possibilities, so that I can prove the preposition. $\endgroup$ Commented Oct 14, 2017 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$ Commented Oct 14, 2017 at 21:12

3 Answers 3

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$
1
  • $\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
    Commented Oct 15, 2017 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$
1
  • $\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$ Commented Oct 14, 2017 at 21:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .