In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, and in particular in
group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
, a cyclic permutation (or cycle) is a
permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
of the elements of some
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
''X'' which maps the elements of some
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
''S'' of ''X'' to each other in a cyclic fashion, while fixing (that is, mapping to themselves) all other elements of ''X''. If ''S'' has ''k'' elements, the cycle is called a ''k''-cycle. Cycles are often denoted by the list of their elements enclosed with parentheses, in the order to which they are permuted.
For example, given ''X'' = , the permutation (1, 3, 2, 4) that sends 1 to 3, 3 to 2, 2 to 4 and 4 to 1 (so ''S'' = ''X'') is a 4-cycle, and the permutation (1, 3, 2) that sends 1 to 3, 3 to 2, 2 to 1 and 4 to 4 (so ''S'' = and 4 is a fixed element) is a 3-cycle. On the other hand, the permutation 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 and .
The set ''S'' is called the
orbit
In celestial mechanics, an orbit is the curved trajectory of an object such as the trajectory of a planet around a star, or of a natural satellite around a planet, or of an artificial satellite around an object or position in space such as a p ...
of the cycle. Every permutation on finitely many elements can be decomposed into cycles on disjoint orbits.
The individual cyclic parts of a permutation are also called
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, and denoted (1, 3) (2, 4).
Definition
upright=1.7, Diagram of a cyclic permutation with two fixed points; a 6-cycle and two 1-cycles. , 190x190px
A
permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
is called a cyclic permutation
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicondi ...
it has a single nontrivial cycle (a cycle of length > 1).
For example, the permutation, written in
two-line notation (in two ways) and also cycle notation,
:
is a six-cycle; its cycle diagram is shown at right.
Some authors restrict the definition to only those permutations which consist of one nontrivial cycle (that is, no fixed points allowed).
A cyclic permutation with no trivial cycles; an 8-cycle., thumb
For example, the permutation
:
is a cyclic permutation under this more restrictive definition, while the preceding example is not.
More formally, a permutation
of a set ''X'', viewed as a
bijective function
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
, is called a cycle if the action on ''X'' of the subgroup generated by
has at most one orbit with more than a single element. This notion is most commonly used when ''X'' is a finite set; then of course the largest orbit, ''S'', is also finite. Let
be any element of ''S'', and put
for any
. If ''S'' is finite, there is a minimal number
for which
. Then
, and
is the permutation defined by
:
for 0 ≤ ''i'' < ''k''
and
for any element of
. The elements not fixed by
can be pictured as
:
.
A cycle can be written using the compact
cycle notation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or p ...
(there are no commas between elements in this notation, to avoid confusion with a ''k''-
tuple
In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
). 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
In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to it ...
. When cycle notation is used, the 1-cycles are often suppressed when no confusion will result.
Basic properties
One of the basic results on
symmetric group
In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group \m ...
s is that any permutation can be expressed as the product of
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. The
multiset
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
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
In mathematics, especially group theory, two elements a and b of a group are conjugate if there is an element g in the group such that b = gag^. This is an equivalence relation whose equivalence classes are called conjugacy classes. In other wor ...
of the permutation in the symmetric group are determined by it.
The number of ''k''-cycles in the symmetric group ''S''
''n'' is given, for
, by the following equivalent formulas:
A ''k''-cycle has
signature
A signature (; from la, signare, "to sign") is a handwritten (and often stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. The writer of a ...
(−1)
''k'' − 1.
The
inverse of a cycle
is given by reversing the order of the entries:
. In particular, since
, 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
![4-el perm matrix 14](https://upload.wikimedia.org/wikipedia/commons/3/37/4-el_perm_matrix_14.svg)
A cycle with only two elements is called a transposition. For example, the permutation
that swaps 2 and 4.
Properties
Any permutation can be expressed as the
composition
Composition or Compositions may refer to:
Arts and literature
*Composition (dance), practice and teaching of choreography
*Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include v ...
(product) of transpositions—formally, they are
generators for the
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic iden ...
. In fact, when the set being permuted is for some integer , then any permutation can be expressed as a product of
and so on. This follows because an arbitrary transposition can be expressed as the product of adjacent transpositions. Concretely, one can express the transposition
where
by moving to one step at a time, then moving back to where was, which interchanges these two and makes no other changes:
:
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:
:
This means the initial request is to move
to
to
to
and finally
to
Instead one may roll the elements keeping
where it is by executing the right factor first (as usual in operator notation, and following the convention in the article on
Permutations
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
). This has moved
to the position of
so after the first permutation, the elements
and
are not yet at their final positions. The transposition
executed thereafter, then addresses
by the index of
to swap what initially were
and
In fact, the
symmetric group
In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group \m ...
is a
Coxeter group
In mathematics, a Coxeter group, named after H. S. M. Coxeter, is an abstract group that admits a formal description in terms of reflections (or kaleidoscopic mirrors). Indeed, the finite Coxeter groups are precisely the finite Euclidean refl ...
, 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.
This permits the
parity of a permutation
In mathematics, when ''X'' is a finite set with at least two elements, the permutations of ''X'' (i.e. the bijective functions from ''X'' to ''X'') fall into two classes of equal size: the even permutations and the odd permutations. If any total or ...
to be a
well-defined
In mathematics, a well-defined expression or unambiguous expression is an expression whose definition assigns it a unique interpretation or value. Otherwise, the expression is said to be ''not well defined'', ill defined or ''ambiguous''. A funct ...
concept.
See also
*
Cycle sort
Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array, unlike any other in-place sorting algorithm. It is based on the idea that the pe ...
– 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
In mathematics, the cycles of a permutation ''π'' of a finite set S correspond bijectively to the orbits of the subgroup generated by ''π'' acting on ''S''. These orbits are subsets of S that can be written as , such that
: for , and .
The ...
*
Cyclic permutation of integer The digits of some specific integers permute or shift cyclically when they are multiplied by a number ''n''. Examples are:
*142857 × 3 = 428571 (shifts cyclically one place left)
*142857 × 5 = 714285 (shifts cyclically one place right ...
*
Cycle notation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or p ...
*
Circular permutation in proteins
A circular permutation is a relationship between proteins whereby the proteins have a changed order of amino acids in their peptide sequence. The result is a protein structure with different connectivity, but overall similar three-dimensional (3D ...
*
Fisher–Yates shuffle
The Fisher–Yates shuffle is an algorithm for generating a random permutation of a finite sequence—in plain terms, the algorithm shuffling, shuffles the sequence. The algorithm effectively puts all the elements into a hat; it continually deter ...
Notes
References
Sources
* Anderson, Marlow and Feil, Todd (2005), ''A First Course in Abstract Algebra'', Chapman & Hall/CRC; 2nd edition. .
*
*
*
External links
{{DEFAULTSORT:Cycle (Mathematics)
Permutations