Cyclic permutation

Graph of a cyclic permutation of numbers from 1 to 8

A cyclic permutation , or cycle for short (from the Greek κύκλος 'circle' ), is a permutation in combinatorics and group theory that swaps certain elements of a set in a circle and holds the others. The first element of the cycle is mapped onto the second, the second element onto the third, and so on up to the last element, which is mapped back onto the first.

Cyclic permutations have a number of special properties. The concatenation of two cyclic permutations is commutative if they have disjoint carriers. The inverse permutation of a cyclic permutation is always cyclic as well. Furthermore, any powers of a cyclic permutation, the length of which is a prime number , again result in cyclic permutations. The cyclic permutations of fixed length also form conjugation classes of the symmetric group of all permutations.

Every cyclic permutation can be broken down into individual transpositions and therefore has an even sign if and only if its length is odd. Each permutation can in turn be written as a concatenation of pairwise disjoint cycles, which is used in the cycle notation of permutations. The order of a permutation then corresponds to the least common multiple of the lengths of these cycles. Cyclic permutations with long cycle lengths play an important role in the construction of pseudorandom number generators .

definition

If the symmetric group of all permutations of the set is , then a permutation is called cyclic with length or cycle if it interchanges a list of pairwise different numbers in a circle, that is ${\displaystyle S_{n}}$ ${\displaystyle \{1,\dotsc ,n\}}$ ${\displaystyle \pi =(\pi (1),\pi (2),\dotsc ,\pi (n))\in S_{n}}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k\leq n}$ ${\displaystyle i_{1},i_{2},\dotsc ,i_{k}\in \{1,\dotsc ,n\}}$

${\displaystyle i_{1}\mapsto i_{2}\mapsto \dotsb \mapsto i_{k}\mapsto i_{1}}$,

and holds all other numbers. So it must apply

${\displaystyle \pi (i_{1})=i_{2},~\pi (i_{2})=i_{3},\;\dotsc ,~\pi (i_{k-1})=i_{k}}$   and   ${\displaystyle \pi (i_{k})=i_{1}}$

such as

${\displaystyle \pi (j)=j}$   for   . ${\displaystyle j\not \in \{i_{1},\dotsc ,i_{k}\}}$

The amount is called the carrier or path of . In a more general way, permutations of any finite sets , for example alphabets , can be considered, but the analysis of the mathematical properties can be limited to the first natural numbers. ${\displaystyle \{i_{1},\dotsc ,i_{k}\}}$ ${\displaystyle \pi }$ ${\displaystyle n}$

notation

In addition to the above function notation , in which the figure is specified in full, a cyclic permutation can also be noted by using only the numbers that are cyclically exchanged as indices using ${\displaystyle \pi }$

${\displaystyle \pi _{i_{1},i_{2},\dotsc ,i_{k}}}$

can be specified. Often a cyclic permutation is also noted in cycle notation by putting these numbers in brackets without separators:

${\displaystyle (i_{1}~i_{2}~\dotso ~i_{k})}$

Both spellings assume that the total number of numbers is known. The index and cycle notation are not clear, however, because the starting number can be selected as desired within the cycle. Each cycle can do so in different ways ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k}$

${\displaystyle \pi _{i_{1},i_{2},\dotsc ,i_{k}}=\pi _{i_{2},\dotsc ,i_{k},i_{1}}=\dotsb =\pi _{i_{k},i_{1},\dotsc ,i_{k-1}}}$

or

${\displaystyle (i_{1}~i_{2}~\dotso ~i_{k})=(i_{2}~\dotso ~i_{k}~i_{1})=\dotsb =(i_{k}~i_{1}~\dotso ~i_{k-1})}$

to be discribed. However, the convention that is often set is to choose the smallest or the largest number of the cycle. ${\displaystyle i_{1}}$

Examples

Cyclic permutations in S ₄

length	Cyclic permutations	number
1	id	1
2	(1 2), (1 3), (1 4), (2 3), (2 4), (3 4)	6th
3	(1 2 3), (1 2 4), (1 3 2), (1 3 4), (1 4 2), (1 4 3), (2 3 4), (2 4 3)	8th
4th	(1 2 3 4), (1 2 4 3), (1 3 2 4), (1 3 4 2), (1 4 2 3), (1 4 3 2)	6th

Is a simple cyclic permutation of length three

${\displaystyle \pi _{123}=\pi _{231}=\pi _{312}=(1~2~3)=(2~3~1)=(3~1~2)={\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}}\in S_{3}}$.

Here, the number is the number , the number of the number and the number back on the number displayed. The permutation ${\displaystyle 1}$ ${\displaystyle 2}$ ${\displaystyle 2}$ ${\displaystyle 3}$ ${\displaystyle 3}$ ${\displaystyle 1}$

${\displaystyle \pi _{24}=\pi _{42}=(2~4)=(4~2)={\begin{pmatrix}1&2&3&4\\1&4&3&2\end{pmatrix}}\in S_{4}}$

is a cyclic permutation of length two in which the numbers and are swapped and the numbers and are retained. Any cyclic permutation of length one ${\displaystyle 2}$ ${\displaystyle 4}$ ${\displaystyle 1}$ ${\displaystyle 3}$

${\displaystyle \pi _{1}=\pi _{2}=\dotsb =\pi _{n}=(1)=(2)=\dotsb =(n)={\begin{pmatrix}1&2&\cdots &n\\1&2&\cdots &n\end{pmatrix}}\in S_{n}}$

corresponds exactly to the identical permutation , which leaves all numbers unchanged. The cyclic permutations listed in the adjacent table are found in the symmetric group . Of the permutations in , only three permutations are therefore non-cyclic, namely those that exchange two pairs of numbers. ${\displaystyle \operatorname {id} }$ ${\displaystyle S_{4}}$ ${\displaystyle 24}$ ${\displaystyle S_{4}}$

Special cases

The following special cases are considered for cyclic permutations:

Exchange or transposition

A cyclic permutation that swaps exactly two elements with one another, i.e.

${\displaystyle \pi _{i,j}=(i~j)}$   for   . ${\displaystyle i,j\in \{1,\dotsc ,n\},i\neq j}$

Neighbor swap or neighboring transposition

A cyclic permutation that interchanges two successive elements, i.e.

${\displaystyle \pi _{i,i+1}=(i~i+1)}$   for   . ${\displaystyle i\in \{1,\dotsc ,n-1\}}$

Cyclic shift to the right

A cyclic permutation that swaps all elements in ascending order in a circle, i.e.

${\displaystyle \pi _{1,2,\dotsc ,n}=(1~2~\dotso ~n)}$.

Cyclic left shift

A cyclic permutation that swaps all elements in a circle in descending order, i.e.

${\displaystyle \pi _{n,n-1,\dotsc ,1}=(n~n-1~\dotso ~1)}$.

properties

number

Number of k cycles in S _n

${\displaystyle {}_{n}\!\diagdown \!\!{}^{k}}$	1	2	3	4th	5	6th	total
1	1						1
2	1	1					2
3	1	3	2				6th
4th	1	6th	8th	6th			21st
5	1	10	20th	30th	24		85
6th	1	15th	40	90	144	120	410

In the set of the various permutations of the numbers there are exactly many cycles. Each permutation in tuple notation corresponds to a cycle , which in turn can be written in different ways. If now generally denotes the set of -cycles in , then applies to ${\displaystyle n!}$ ${\displaystyle \{1,\dotsc ,n\}}$ ${\displaystyle (n-1)!}$ ${\displaystyle n}$ ${\displaystyle (i_{1},i_{2},\dotsc ,i_{n})}$ ${\displaystyle n}$ ${\displaystyle (i_{1}~i_{2}~\dotso ~i_{n})}$ ${\displaystyle n}$ ${\displaystyle Z_{n,k}}$ ${\displaystyle k}$ ${\displaystyle S_{n}}$ ${\displaystyle k=2,\dotsc ,n}$

${\displaystyle |Z_{n,k}|={\binom {n}{k}}(k-1)!}$    (Follow A111492 in OEIS ),

because there are ways to choose from numbers. For the total amount of all cyclic permutations including the identical permutation, the following applies: ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle Z_{n}}$ ${\displaystyle S_{n}}$

${\displaystyle |Z_{n}|=1+\sum _{k=2}^{n}{\binom {n}{k}}(k-1)!}$    (Follow A121726 in OEIS )

Commutativity

In general, the sequential execution of two cyclic permutations is not commutative . However , if they have two cyclic permutations and disjoint carriers, the following applies ${\displaystyle \pi _{i_{1},\dotsc ,i_{k}}\in Z_{n,k}}$ ${\displaystyle \pi _{j_{1},\dotsc ,j_{l}}\in Z_{n,l}}$

${\displaystyle \{i_{1},\dotsc ,i_{k}\}\cap \{j_{1},\dotsc ,j_{l}\}=\emptyset }$,

then their order can be reversed when they are executed one after the other, that is, it applies

${\displaystyle \pi _{i_{1},\dotsc ,i_{k}}\circ \pi _{j_{1},\dotsc ,j_{l}}=\pi _{j_{1},\dotsc ,j_{l}}\circ \pi _{i_{1},\dotsc ,i_{k}}}$.

Cyclic permutations with disjoint carriers are also called disjoint cycles.

Isolation and Inverse

Executing two cyclic permutations one after the other is not necessarily cyclic again, like the example

${\displaystyle \pi _{1234}\circ \pi _{1234}={\begin{pmatrix}1&2&3&4\\3&4&1&2\end{pmatrix}}=\pi _{13}\circ \pi _{24}}$

shows. Therefore, the amount of the cyclic permutations forms for any subgroup of the symmetric group . However, the inverse permutation of a cyclic permutation is always also a cyclic permutation, namely the one that cyclically interchanges the numbers in the reverse order, that is ${\displaystyle Z_{n}}$ ${\displaystyle n\geq 4}$ ${\displaystyle S_{n}}$ ${\displaystyle \pi _{i_{1},\dotsc ,i_{k}}}$ ${\displaystyle i_{1},\dotsc ,i_{k}}$

${\displaystyle (\pi _{i_{1},\dotsc ,i_{k}})^{-1}=\pi _{i_{k},\dotsc ,i_{1}}}$.

The inverse permutation of a transposition is thus the same transposition again.

Potencies

Move is a cyclic permutation applied twice in succession, all the indices cyclically , that is, is set to ready, on and so on until the on and on . In general, by applying a cyclic permutation one time, all indices are shifted cyclically . The -th power of a cyclic permutation of the length is itself cyclic again if and only if and are coprime . In particular, the repeated application of a cyclic permutation results in the identical permutation, i.e. ${\displaystyle 2}$ ${\displaystyle i_{1}}$ ${\displaystyle i_{3}}$ ${\displaystyle i_{2}}$ ${\displaystyle i_{4}}$ ${\displaystyle i_{k-1}}$ ${\displaystyle i_{1}}$ ${\displaystyle i_{k}}$ ${\displaystyle i_{2}}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle \pi \in Z_{n,k}}$

${\displaystyle \pi ^{k}=\operatorname {id} }$,

and the repeated application results in the initial permutation, that is ${\displaystyle (k+1)}$

${\displaystyle \pi ^{k+1}=\pi }$.

Hence the crowd forms

${\displaystyle \{\pi ,\pi ^{2},\dotsc ,\pi ^{k-1},\pi ^{k}\}}$

with the sequential execution of a subset of the symmetric group , wherein the inverse element to be. This subgroup is isomorphic to the cyclic group and consists exclusively of cyclic permutations if and only if is a prime number . ${\displaystyle S_{n}}$ ${\displaystyle \pi ^{k-j}}$ ${\displaystyle \pi ^{j}}$ ${\displaystyle C_{k}}$ ${\displaystyle k}$

conjugation

For a cyclic permutation

${\displaystyle \pi =(i_{1}~i_{2}~\dotso ~i_{k})\in Z_{n,k}}$

which is calculated conjugation with an arbitrary permutation to ${\displaystyle \sigma \in S_{n}}$

${\displaystyle \sigma \circ \pi \circ \sigma ^{-1}=\left(\sigma (i_{1})~\sigma (i_{2})~\dotso ~\sigma (i_{k})\right)}$,

so it again results in a cycle. The set forms a conjugation class for each group . In general, two permutations are conjugated to each other if and only if their cycle type matches. ${\displaystyle k}$ ${\displaystyle Z_{n,k}}$ ${\displaystyle k\in \{1,\dotsc ,n\}}$ ${\displaystyle S_{n}}$ ${\displaystyle \pi ,\sigma \in S_{n}}$

Decompositions

Breakdown of cycles into sub-cycles

Every cyclic permutation of the length can be changed at any point using ${\displaystyle k>2}$ ${\displaystyle l\in \{2,\dotsc ,k-1\}}$

${\displaystyle \pi _{i_{1},\dotsc ,i_{k}}=\pi _{i_{1},\dotsc ,i_{l}}\circ \pi _{i_{l},\dotsc ,i_{k}}}$

break it down into two sub-cycles. If this decomposition is applied repeatedly , it results that every cyclic permutation of the length is by means of ${\displaystyle l=2,3,\dotsc ,k-1}$ ${\displaystyle k}$

${\displaystyle \pi _{i_{1},\dotsc ,i_{k}}=\pi _{i_{1},i_{2}}\circ \dotsb \circ \pi _{i_{k-1},i_{k}}}$

can be written as a chain of transpositions. For the sign of a cyclic permutation of the length, the following applies ${\displaystyle k-1}$ ${\displaystyle k}$

${\displaystyle \operatorname {sgn} (\pi _{i_{1},\dotsc ,i_{k}})=\operatorname {sgn} (\pi _{i_{1},i_{2}})\dotsm \operatorname {sgn} (\pi _{i_{k-1},i_{k}})=(-1)^{k-1}}$,

since transpositions always have an odd sign. A cyclic permutation is even if and only if its length is odd.

example

The cyclic permutation of length four can be passed through ${\displaystyle \pi _{1423}\in S_{4}}$

${\displaystyle \pi _{1423}=\pi _{14}\circ \pi _{42}\circ \pi _{23}}$

split into three transpositions and is therefore odd.

Decomposition of permutations into cycles

Graph of a permutation of the numbers from 1 to 7, which breaks down into three disjoint cycles

Each permutation can be clearly represented (except for the interchanging of the factors) as a concatenation of pairs of disjoint cycles. That is, it applies ${\displaystyle \pi \in S_{n}}$ ${\displaystyle m\leq n}$

${\displaystyle \pi =\pi _{I_{1}}\circ \dotsb \circ \pi _{I_{m}}}$

with pairwise disjoint carriers for , where is. The Stirling numbers of the first kind indicate how many permutations can be written in as a concatenation of exactly cyclic permutations. The order of a permutation corresponds to the order of the associated cyclic group and is therefore the smallest common multiple of the lengths of these cycles. Furthermore, the sign of a permutation results from the number of cycles of even length. ${\displaystyle I_{j}=\{i_{j,1},\dotsc ,i_{j,n_{j}}\}}$ ${\displaystyle j=1,\dotsc ,m}$ ${\displaystyle n_{1}+\dotsb +n_{m}=n}$ ${\displaystyle s_{n,m}}$ ${\displaystyle S_{n}}$ ${\displaystyle m}$ ${\displaystyle n_{1},\dotsc ,n_{m}}$

example

The permutation

${\displaystyle \pi ={\begin{pmatrix}1&2&3&4&5&6\\3&6&4&1&5&2\end{pmatrix}}\in S_{6}}$

breaks down into the three disjoint cycles

${\displaystyle \pi =\pi _{134}\circ \pi _{26}\circ \pi _{5}}$

and thus has the order . Since only one of the three cycles is even in length, the permutation is odd. ${\displaystyle \operatorname {kgV} (3,2,1)=6}$

Applications

Cyclic permutations with long cycle lengths play an important role in the construction of pseudorandom number generators . The maximum period of such a random number generator corresponds to the number of possible states of the generator. With simple recursive generators of the form

${\displaystyle x_{i+1}=f(x_{i})}$

with the number of possible states is even . The period of such a generator is then maximal if the function represents a cyclic permutation of the length of the set . In the case of linear congruence generators of the type ${\displaystyle f\colon \{0,\dotsc ,m-1\}\to \{0,\dotsc ,m-1\}}$ ${\displaystyle m}$ ${\displaystyle f}$ ${\displaystyle m}$ ${\displaystyle \{0,\dotsc ,m-1\}}$

${\displaystyle x_{i+1}=(ax_{i}+b){\bmod {m}}}$

Knuth's theorem provides sufficient and necessary conditions for the parameters and for the maximality of the period length. ${\displaystyle a,b}$ ${\displaystyle m}$

literature

• Albrecht Beutelspacher : Linear Algebra. An introduction to the science of vectors, maps, and matrices . 6th edition. Vieweg, 2009, ISBN 3-528-56508-X .
• Gerd Fischer : Textbook of Algebra . Springer, 2007, ISBN 3-8348-0226-3 .
• Jens Carsten Jantzen, Joachim Schwermer : Algebra . Springer, 2005, ISBN 3-540-21380-5 .

Web links

• DA Suprunenko: Permutation of a set . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . Springer-Verlag , Berlin 2002, ISBN 978-1-55608-010-4 (English, online ).
• Eric W. Weisstein : Permutation Cycle . In: MathWorld (English).
• yark, Pedro Sanchez: Cycle . In: PlanetMath . (English)