Cyclic permutation
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
- ,
and holds all other numbers. So it must apply
- and
such as
- for .
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.
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
can be specified. Often a cyclic permutation is also noted in cycle notation by putting these numbers in brackets without separators:
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
or
to be discribed. However, the convention that is often set is to choose the smallest or the largest number of the cycle.
Examples
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
- .
Here, the number is the number , the number of the number and the number back on the number displayed. The permutation
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
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.
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.
- for .
- Neighbor swap or neighboring transposition
- A cyclic permutation that interchanges two successive elements, i.e.
- for .
- Cyclic shift to the right
- A cyclic permutation that swaps all elements in ascending order in a circle, i.e.
- .
- Cyclic left shift
- A cyclic permutation that swaps all elements in a circle in descending order, i.e.
- .
properties
number
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
because there are ways to choose from numbers. For the total amount of all cyclic permutations including the identical permutation, the following applies:
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
- ,
then their order can be reversed when they are executed one after the other, that is, it applies
- .
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
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
- .
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.
- ,
and the repeated application results in the initial permutation, that is
- .
Hence the crowd forms
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 .
conjugation
For a cyclic permutation
which is calculated conjugation with an arbitrary permutation to
- ,
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.
Decompositions
Breakdown of cycles into sub-cycles
Every cyclic permutation of the length can be changed at any point using
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
can be written as a chain of transpositions. For the sign of a cyclic permutation of the length, the following applies
- ,
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
split into three transpositions and is therefore odd.
Decomposition of permutations into 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
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.
example
The permutation
breaks down into the three disjoint cycles
and thus has the order . Since only one of the three cycles is even in length, the permutation is odd.
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
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
Knuth's theorem provides sufficient and necessary conditions for the parameters and for the maximality of the period length.
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)