Editing Cyclic permutation

{{short description|Type of (mathematical) permutation with no fixed element}}
{{other uses|Cyclic (mathematics)}}
In [[mathematics]], and in particular in [[group theory]], a '''cyclic permutation''' is a [[permutation]] consisting of a single cycle.<ref name=":0">{{Cite book |last=Gross |first=Jonathan L. |title=Combinatorial methods with computer applications |date=2008 |publisher=Chapman & Hall/CRC |isbn=978-1-58488-743-0 |series=Discrete mathematics and its applications |location=Boca Raton, Fla. |pages=29}}</ref><ref name=":1">{{Cite book |last=Knuth |first=Donald E. |title=The Art of Computer Programming |publisher=Addison-Wesley |year=2002 |pages=35}}</ref> In some cases, cyclic permutations are referred to as '''cycles''';<ref name=":2">{{Cite book |last=Bogart |first=Kenneth P. |title=Introductory combinatorics |date=2000 |publisher=Harcourt Academic Press |isbn=978-0-12-110830-4 |edition=3 |location=London |pages=554}}</ref> if a cyclic permutation has ''k'' elements, it may be called a '''''k''-cycle'''. Some authors widen this definition to include permutations with fixed points in addition to at most one non-trivial cycle.<ref name=":2" /><ref name=":3">{{Cite book |last=Rosen |first=Kenneth H. |title=Handbook of discrete and combinatorial mathematics |date=2000 |publisher=CRC press |isbn=978-0-8493-0149-0 |location=Boca Raton London New York}}</ref> In [[Permutation#Cycle notation|cycle notation]], cyclic permutations are denoted by the list of their elements enclosed with parentheses, in the order to which they are permuted.

For example, the permutation (1 3 2 4) that sends 1 to 3, 3 to 2, 2 to 4 and 4 to 1 is a 4-cycle, and the permutation (1 3 2)(4) that sends 1 to 3, 3 to 2, 2 to 1 and 4 to 4 is considered a 3-cycle by some authors. On the other hand, the permutation (1 3)(2 4) that sends 1 to 3, 3 to 1, 2 to 4 and 4 to 2 is not a cyclic permutation because it separately permutes the pairs {1, 3} and {2, 4}.

For the wider definition of a cyclic permutation, allowing fixed points, these fixed points each constitute trivial [[orbit (group theory)|orbit]]s of the permutation, and there is a single non-trivial orbit containing all the remaining points. This can be used as a definition: a cyclic permutation (allowing fixed points) is a permutation that has a single non-trivial orbit. Every permutation on finitely many elements can be decomposed into cyclic permutations whose non-trivial orbits are disjoint.<ref>{{cite book|title=Fundamental Concepts of Abstract Algebra|series=Dover Books on Mathematics|first=Gertrude|last=Ehrlich|publisher=Courier Corporation|year=2013|isbn=9780486291864|page=69|url=https://books.google.com/books?id=1dGjAQAAQBAJ&pg=PA69}}</ref>

The individual cyclic parts of a permutation are also called '''[[Cycles and fixed points|cycles]]''', thus the second example is composed of a 3-cycle and a 1-cycle (or ''fixed point'') and the third is composed of two 2-cycles.

== Definition ==
[[image:050712_perm_2.png|A cyclic permutation consisting of a single 8-cycle.|thumb]]

There is not widespread consensus about the precise definition of a cyclic permutation. Some authors define a [[permutation]] {{mvar|σ}} of a set {{mvar|X}} to be cyclic if "successive application would take each object of the permuted set successively through the positions of all the other objects",<ref name=":0" /> or, equivalently, if its representation in cycle notation consists of a single cycle.<ref name=":1" /> Others provide a more permissive definition which allows fixed points.<ref name=":2" /><ref name=":3" />

A nonempty subset {{mvar|S}} of {{mvar|X}} is a ''cycle'' of <math>\sigma</math> if the restriction of <math>\sigma</math> to {{mvar|S}} is a cyclic permutation of {{var|S}}. If {{mvar|X}} is [[finite set|finite]], its cycles are [[disjoint sets|disjoint]], and their [[set union|union]] is {{mvar|X}}. That is, they form a [[partition of a set|partition]], called the [[cycle decomposition (group theory)|cycle decomposition]] of <math>\sigma.</math> So, according to the more permissive definition, a permutation of {{mvar|X}} is cyclic if and only if {{mvar|X}} is its unique cycle.

For example, the permutation, written in [[cycle notation]] and [[Permutation#Two-line notation|two-line notation]] (in two ways) as
:<math>\begin{align}
(1\ 4\ 6\ &8\ 3\ 7)(2)(5) \\
&=
\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 4 & 2 & 7 & 6 & 5 & 8 & 1 & 3 \end{pmatrix} \\
&=
\begin{pmatrix} 1 & 4 & 6 & 8 & 3 & 7 & 2 & 5 \\ 4 & 6 & 8 & 3 & 7 & 1 & 2 & 5 \end{pmatrix} \end{align}</math>
has one 6-cycle and two 1-cycles its cycle diagram is shown at right. Some authors consider this permutation cyclic while others do not.

[[image:050712_perm_3.png|thumb|A permutation that is cyclic for the enlarged definition but not for the restricted one, with two fixed points (1-cycles) and a 6-cycle]]With the enlarged definition, there are cyclic permutations that do not consist of a single cycle. 

More formally, for the enlarged definition, a permutation <math>\sigma</math> of a set ''X'', viewed as a [[bijection|bijective function]] <math>\sigma:X\to X</math>, is called a cycle if the action on ''X'' of the subgroup generated by <math>\sigma</math> has at most one orbit with more than a single element.<ref>{{harvnb|Fraleigh|1993|loc=p. 103}}</ref> This notion is most commonly used when ''X'' is a finite set; then the largest orbit, ''S'', is also finite. Let <math>s_0</math> be any element of ''S'', and put <math>s_i=\sigma^i(s_0)</math> for any <math>i\in\mathbf{Z}</math>. If ''S'' is finite, there is a minimal number <math>k \geq 1</math> for which <math>s_k=s_0</math>. Then <math>S=\{ s_0, s_1, \ldots, s_{k-1}\}</math>, and <math>\sigma</math> is the permutation defined by

:<math>\sigma(s_i) = s_{i+1}</math> for 0 ≤ ''i'' < ''k''

and <math>\sigma(x)=x</math> for any element of <math>X\setminus S</math>. The elements not fixed by <math>\sigma</math> can be pictured as

:<math>s_0\mapsto s_1\mapsto s_2\mapsto\cdots\mapsto s_{k-1}\mapsto s_k=s_0</math>.

A cyclic permutation can be written using the compact [[cycle notation]] <math>\sigma = (s_0~s_1~\dots~s_{k-1})</math> (there are no commas between elements in this notation, to avoid confusion with a ''k''-[[tuple]]). The ''length'' of a cycle is the number of elements of its largest orbit.  A cycle of length ''k'' is also called a ''k''-cycle.

The orbit of a 1-cycle is called a ''fixed point'' of the permutation, but as a permutation every 1-cycle is the [[identity permutation]].<ref>{{harvnb|Rotman|2006|loc=p. 108}}</ref> When cycle notation is used, the 1-cycles are often omitted when no confusion will result.<ref>{{harvnb|Sagan|1991|loc=p. 2}}</ref>

== Basic properties ==
{{Hatnote|In the remainder of the article, the enlarged definition is used.}}
One of the basic results on [[symmetric group]]s is that any permutation can be expressed as the product of [[Disjoint sets|disjoint]] cycles (more precisely: cycles with disjoint orbits); such cycles commute with each other, and the expression of the permutation is unique up to the order of the cycles.{{efn|Note that the cycle notation is not unique: each ''k''-cycle can itself be written in ''k'' different ways, depending on the choice of <math>s_0</math> in its orbit.}} The [[multiset]] of lengths of the cycles in this expression (the [[cycle type]]) is therefore uniquely determined by the permutation, and both the signature and the [[conjugacy class]] of  the permutation in the symmetric group are determined by it.<ref>{{harvnb|Rotman|2006|loc=p. 117, 121}}</ref>

The number of ''k''-cycles in the symmetric group ''S''<sub>''n''</sub> is given, for <math>1\leq k\leq n</math>, by the following equivalent formulas:
<math display="block">\binom nk(k-1)!=\frac{n(n-1)\cdots(n-k+1)}{k}=\frac{n!}{(n-k)!k}.</math>

A ''k''-cycle has [[signature of a permutation|signature]] (−1)<sup>''k''&nbsp;−&nbsp;1</sup>.

The [[inverse function|inverse]] of a cycle <math>\sigma = (s_0~s_1~\dots~s_{k-1})</math> is given by reversing the order of the entries: <math>\sigma^{-1} = (s_{k - 1}~\dots~s_1~s_{0})</math>.  In particular, since <math>(a ~ b) = (b ~ a)</math>, every two-cycle is its own inverse.  Since disjoint cycles commute, the inverse of a product of disjoint cycles is the result of reversing each of the cycles separately.

== Transpositions ==
{{redirect|Transposition (mathematics)|matrix transposition|Transpose}}
[[File:4-el perm matrix 14.svg|thumb|120px|[[Permutation matrix|Matrix]] of <math>\pi</math>]]
A cycle with only two elements is called a '''transposition'''.  For example, the permutation <math>\pi = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 4 & 3 & 2 \end{pmatrix}</math> that swaps 2 and 4. Since it is a 2-cycle, it can be written as <math>\pi = (2,4)</math>.

=== Properties ===
Any permutation can be expressed as the [[function composition|composition]] (product) of transpositions—formally, they are [[Generating set of a group|generators]] for the [[group (mathematics)|group]].<ref>{{harvnb|Rotman|2006|loc=p. 118, Prop. 2.35}}</ref> In fact, when the set being permuted is {{math|{{mset|1, 2, ..., ''n''}}}} for some integer {{math|''n''}}, then any permutation can be expressed as a product of '''{{visible anchor|adjacent transpositions}}''' <math>(1~2), (2~3), (3~4),</math> and so on.  This follows because an arbitrary transposition can be expressed as the product of adjacent transpositions. Concretely, one can express the transposition <math>(k~~l)</math> where <math>k < l</math> by moving {{math|''k''}} to {{math|''l''}} one step at a time, then moving {{math|''l''}} back to where {{math|''k''}} was, which interchanges these two and makes no other changes:

:<math>(k~~l) = (k~~k+1)\cdot(k+1~~k+2)\cdots(l-1~~l)\cdot(l-2~~l-1)\cdots(k~~k+1).</math>

The decomposition of a permutation into a product of transpositions is obtained for example by writing the permutation as a product of disjoint cycles, and then splitting iteratively each of the cycles of length 3 and longer into a product of a transposition and a cycle of length one less:

:<math>(a~b~c~d~\ldots~y~z) = (a~b)\cdot (b~c~d~\ldots~y~z).</math>

This means the initial request is to move <math>a</math> to <math>b,</math> <math>b</math> to <math>c,</math> <math>y</math> to <math>z,</math> and finally <math>z</math> to <math>a.</math> Instead one may roll the elements keeping <math>a</math> where it is by executing the right factor first (as usual in operator notation, and following the convention in the article [[Permutation#Product and inverse|Permutation]]). This has moved <math>z</math> to the position of <math>b,</math> so after the first permutation, the elements <math>a</math> and <math>z</math> are not yet at their final positions. The transposition <math>(a~b),</math> executed thereafter, then addresses <math>z</math> by the index of <math>b</math> to swap what initially were <math>a</math> and <math>z.</math>

In fact, the [[symmetric group]] is a [[Coxeter group]], meaning that it is generated by elements of order 2 (the adjacent transpositions), and all relations are of a certain form.

One of the main results on symmetric groups states that either all of the decompositions of a given permutation into transpositions have an even number of transpositions, or they all have an odd number of transpositions.<ref>{{harvnb|Rotman|2006|loc=p. 122}}</ref> This  permits the [[parity of a permutation]] to be a [[well-defined]] concept.

== See also ==
* [[Cycle sort]] – a sorting algorithm that is based on the idea that the permutation to be sorted can be factored into cycles, which can individually be rotated to give a sorted result
* [[Cycles and fixed points]]
* [[Cyclic permutation of integer]]
* [[Cycle notation]]
* [[Circular permutation in proteins]]
* [[Fisher–Yates shuffle]]

==Notes==
{{notelist}}

==References==
{{reflist|30em}}

=== Sources ===
* Anderson, Marlow and Feil, Todd (2005), ''A First Course in Abstract Algebra'', Chapman & Hall/CRC; 2nd edition. {{ISBN|1-58488-515-7}}.
*{{citation|first=John|last=Fraleigh|title=A first course in abstract algebra|edition=5th|year=1993|publisher=Addison Wesley|isbn=978-0-201-53467-2}}
* {{citation|first=Joseph J.|last=Rotman|title=A First Course in Abstract Algebra with Applications|edition=3rd|year=2006|publisher=Prentice-Hall|isbn=978-0-13-186267-8}}
* {{citation|first=Bruce E.|last=Sagan|title=The Symmetric Group / Representations, Combinatorial Algorithms & Symmetric Functions|year=1991|publisher=Wadsworth & Brooks/Cole|isbn=978-0-534-15540-7}}

==External links==
* [https://www.youtube.com/watch?v=MpKG6FmcIHk Cycle Notation of Permutations], video explains cyclic decomposition.
<!--
* [http://www.cut-the-knot.org/Curriculum/Combinatorics/PermByTrans.shtml Permutations as a Product of Transpositions]
-->

{{PlanetMath attribution|id=2262|title=cycle}}

{{DEFAULTSORT:Cycle (Mathematics)}}
[[Category:Permutations]]