Cyclic permutation

A cyclic permutation, or short cycle Cycles (from Greek κύκλος circle) is in combinatorics and group theory, a permutation that swaps specific elements of a set in a circle and the other holds. The first element of the cycle is mapped to the second, the second element of the third, and so on up to the last element, which is ready to return to the first. A cyclic permutation, in which exactly two elements are reversed, ie, exchange or transposition. A permutation that swaps each other in an ordered set following elements Nachbarvertauschung or neighbor transposition is called.

Cyclic permutations have a number of special characteristics. Thus, the concatenation of two cyclic permutations is commutative if these have disjoint support. The inverse permutation of a cyclic permutation is always also cyclical. Next give any powers of a cyclic permutation whose length is a prime number, again cyclic permutations. The cyclic permutations of fixed length also form conjugacy classes of the symmetric group of all permutations.

Any cyclic permutation can be decomposed into individual transpositions and if and therefore has a straight sign on if its length is odd. Every permutation can again be written as a concatenation of pairwise disjoint cycles, which is used in the Zykelschreibweise of permutations. The order of a permutation is then the least common multiple of the lengths of these cycles. Cyclic permutations with great Zykellänge play an important role in the construction of pseudo-random number generators.

• 5.1 Decomposition of cycles in partial cycles
• 5.2 decomposition of permutations into cycles

Definition

Is the symmetric group of all permutations of the set, then is called a permutation cycle of length or cycle when they exchanged a list of pairwise distinct numbers in the loop, ie

And all other numbers holds. So it must be true

As well as

The set is called the carrier or the web from. Cyclic permutations of length two are called permutations or transpositions. Applies to a permutation, then one speaks of a Nachbarvertauschung. More generally, even permutations of arbitrary finite quantities, for example alphabets are considered, but the analysis of the mathematical properties can be limited to the first natural numbers.

Notation

In addition to the above matrix notation in which the image is completely specified, a cyclic permutation can be recorded, characterized in that only the numbers are cyclically switched, as by means of indices

Be specified. Frequently a cyclic permutation is also listed in Zykelschreibweise by that figure to no delimiters in brackets:

In both notations, it is assumed that the total number of numbers is known. However, the index and Zykelschreibweisen are not unique, since the number of starts can be selected arbitrarily within the cycle. Each cycle can be as different ways

Or

Are described. Often set convention, however, is to choose the smallest or the largest number of the cycle.

Examples

A simple cyclic permutation of length three is

Here, the number of the number, the number is displayed on the number and the number back to the number. The permutation

Is a cyclic permutation of the length of two (ie, a transposition ) in which the numbers and the numbers are reversed, and are held and fixed. Any cyclic permutation of length one

Just corresponds to the identical permutation, which leaves all numbers unchanged. In the symmetric group, on the cyclic permutations listed in the adjacent table. Of the permutations accordingly only three permutations are not cyclic, namely those that exchange two pairs of numbers.

Properties

Number

In the set of different permutations of the numbers, there are exactly many cycles. Each permutation corresponding Tupelschreibweise namely a cycle, which can in turn be written in various ways. Refers now generally the amount of cycles in, then for

Because there are ways to select numbers. Thus applies to the total amount of all cyclic permutations of the identical permutation, including:

Commutativity

In general, the sequential execution of two cyclic permutations is not commutative. Do, however, two cyclic permutations and disjoint support, so true

Then can their order in the sequential execution of swap, which means that it applies

Cyclic permutations with disjoint carriers are also called disjoint cycles.

Seclusion and Inverse

The sequential execution of two cyclic permutations is not necessarily cyclically again, as the example

Shows. Therefore, the amount of cyclic permutation of the sub-group does not form a symmetrical group. However, the inverse permutation of a cyclic permutation is also always a cyclic permutation, namely the one that switches the number of cycles in the reverse order, that is

The inverse permutation is a transposition so that again the same transposition.

Potencies

Is a cyclic permutation is applied twice, then all indices move cyclically, that is, ready, to, and so on up to and on to. General move to cyclically by the initial application of a cyclic permutation of all indices. The -th power of a cyclic permutation of length exactly is then itself cyclically again after and are relatively prime. Specifically, results in the initial application of a cyclic permutation of the identity permutation, ie

And the initial application again yields the Ausgangspermutation, so

Therefore, the set

With the sequential execution of a subset of the symmetric group, wherein said inverse element is. This subgroup is isomorphic to the cyclic group and precisely then consists solely of cyclic permutations, if a prime number.

Conjugation

For a cyclic permutation

, calculate the conjugation with an arbitrary permutation

So they in turn yields a cycle. The amount forms for each one conjugacy class of the group.

Decompositions

Decomposition of cycles in partial cycles

Each cyclic permutation of the length can be at any position by means of

Decomposed into two sub-cycles. Applying these decomposition repeated to concerns that any cyclic permutation of the length by means of

Can be written as a concatenation of transpositions. Therefore applies to the sign of a cyclic permutation of length

Since transpositions always have an odd sign. A cyclic permutation is exactly then just when its length is odd.

Example

The cyclic permutation of length four can be extended by

Divided into three transpositions and is therefore odd.

Decomposition of permutations into cycles

Every permutation can be uniquely represented (up to permutation of factors ) as the concatenation of pairwise disjoint cycles. That is, it is

With pairwise disjoint supports for, where is. The Stirling numbers of the first type indicate in how many permutations can be written as a concatenation of just the cyclic permutations. The order of a permutation corresponding to the order of the corresponding cyclic group and is the least common multiple of the lengths of these cycles. Next, the sign of a permutation of the number of cycles of even length.

Example

The permutation

Divided into the three disjoint cycles

And thus has order. Since only one of three cycles has a straight length, which permutation is odd.

Applications

Cyclic permutations with great Zykellänge play an important role in the construction of pseudo-random number generators. The maximum period of such a random number generator corresponding to the number of possible states of the generator. In simple recursive generators of the form

With the number of possible states is straight. The period of such a generator is exactly at a maximum when the function is a cyclic permutation of the length of the set. In the case of linear congruential generators of the type

Is the set of Knuth sufficient and necessary conditions on the parameters and for the maximality of the period length.