Cyclic permutation

Last updated July 22, 2023

In mathematics, and in particular in group theory, a cyclic permutation is a permutation consisting of a single cycle.^[1]^[2] In some cases, cyclic permutations are referred to as cycles;^[3] 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.^[3]^[4] In 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}.

The set of elements that are not fixed by a cyclic permutation is called the orbit of the cyclic permutation.^{[ citation needed ]} Every permutation on finitely many elements can be decomposed into cyclic permutations 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.

Definition

A cyclic permutation consisting of a single 8-cycle. 050712 perm 2.png — A cyclic permutation consisting of a single 8-cycle.

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

A nonempty subset $S$ of $X$ is a cycle of $\sigma$ if the restriction of $\sigma$ to $S$ is a cyclic permutation of S. If $X$ is finite, its cycles are disjoint, and their union is $X$ . That is, they form a partition, called the cycle decomposition of $\sigma .$ So, according to the more permissive definition, a permutation of $X$ is cyclic if and only if $X$ is its unique cycle.

For example, the permutation, written in cycle notation and two-line notation (in two ways) as

{\begin{aligned}(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{aligned}}

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.

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 050712 perm 3.png — 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 $\sigma$ of a set X, viewed as a bijective function $\sigma :X\to X$ , is called a cycle if the action on X of the subgroup generated by $\sigma$ has at most one orbit with more than a single element.^[5] This notion is most commonly used when X is a finite set; then the largest orbit, S, is also finite. Let $s_{0}$ be any element of S, and put $s_{i}=\sigma ^{i}(s_{0})$ for any $i\in \mathbf {Z}$ . If S is finite, there is a minimal number $k\geq 1$ for which $s_{k}=s_{0}$ . Then $S=\{s_{0},s_{1},\ldots ,s_{k-1}\}$ , and $\sigma$ is the permutation defined by

\sigma (s_{i})=s_{i+1}

for 0 ≤ i < k

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

s_{0}\mapsto s_{1}\mapsto s_{2}\mapsto \cdots \mapsto s_{k-1}\mapsto s_{k}=s_{0}

.

A cyclic permutation can be written using the compact cycle notation $\sigma =(s_{0}~s_{1}~\dots ~s_{k-1})$ (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.^[6] When cycle notation is used, the 1-cycles are often omitted when no confusion will result.^[7]

Basic properties

One of the basic results on symmetric groups 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.^{[lower-alpha 1]} 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.^[8]

The number of k-cycles in the symmetric group S_n is given, for $1\leq k\leq n$ , by the following equivalent formulas:

{\binom {n}{k}}(k-1)!={\frac {n(n-1)\cdots (n-k+1)}{k}}={\frac {n!}{(n-k)!k}}.

A k-cycle has signature (−1)^k − 1.

The inverse of a cycle $\sigma =(s_{0}~s_{1}~\dots ~s_{k-1})$ is given by reversing the order of the entries: $\sigma ^{-1}=(s_{k-1}~\dots ~s_{1}~s_{0})$ . In particular, since $(a~b)=(b~a)$ , 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

A cycle with only two elements is called a transposition. For example, the permutation $\pi ={\begin{pmatrix}1&2&3&4\\1&4&3&2\end{pmatrix}}$ that swaps 2 and 4. Since it is a 2-cycle, it can be written as $\pi =(2,4)$ .

Properties

Any permutation can be expressed as the composition (product) of transpositions—formally, they are generators for the group.^[9] In fact, when the set being permuted is ${1, 2, ..., n}$ for some integer $n$ , then any permutation can be expressed as a product of adjacent transpositions $(1~2),(2~3),(3~4),$ and so on. This follows because an arbitrary transposition can be expressed as the product of adjacent transpositions. Concretely, one can express the transposition $(k~~l)$ where $k<l$ by moving $k$ to $l$ one step at a time, then moving $l$ back to where $k$ was, which interchanges these two and makes no other changes:

(k~~l)=(k~~k+1)\cdot (k+1~~k+2)\cdots (l-1~~l)\cdot (l-2~~l-1)\cdots (k~~k+1).

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:

(a~b~c~d~\ldots ~y~z)=(a~b)\cdot (b~c~d~\ldots ~y~z).

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

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.^[10] This permits the parity of a permutation to be a well-defined concept.

Notes

↑ Note that the cycle notation is not unique: each k-cycle can itself be written in k different ways, depending on the choice of $s_{0}$ in its orbit.

Related Research Articles

In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and only if the matrix is invertible and the linear map represented by the matrix is an isomorphism. The determinant of a product of matrices is the product of their determinants (the preceding property is a corollary of this one). The determinant of a matrix $A$ is denoted $det(A)$ , $det A$ , or $| A |$ .

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 itself). The group of all permutations of a set M is the symmetric group of M, often written as Sym(M). The term permutation group thus means a subgroup of the symmetric group. If M = {1, 2, ..., n} then Sym(M) is usually denoted by S_n, and may be called the symmetric group on n letters.

In mathematical physics and mathematics, the Pauli matrices are a set of three $2 \times 2$ complex matrices which are Hermitian, involutory and unitary. Usually indicated by the Greek letter sigma, they are occasionally denoted by tau when used in connection with isospin symmetries.

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 $defined over a finite set of symbols consists of the permutations that can be performed on the symbols. Since there are such permutation operations, the order of the symmetric group is .$

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 process of changing the linear order of an ordered set.

<span class="mw-page-title-main">Conjugacy class</span> In group theory, equivalence class under the relation of conjugation

In mathematics, especially group theory, two elements $and of a group are conjugate if there is an element in the group such that This is an equivalence relation whose equivalence classes are called conjugacy classes . In other words, each conjugacy class is closed under for all elements in the group.$

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 ordering of X is fixed, the parity (oddness or evenness) of a permutation $of X can be defined as the parity of the number of inversions for σ, i.e., of pairs of elements x, y of X such that x < y and σ (x) > σ (y) .$

In group theory, the quaternion group Q₈ (sometimes just denoted by Q) is a non-abelian group of order eight, isomorphic to the eight-element subset $of the quaternions under multiplication. It is given by the group presentation$

In linear algebra, the permanent of a square matrix is a function of the matrix similar to the determinant. The permanent, as well as the determinant, is a polynomial in the entries of the matrix. Both are special cases of a more general function of a matrix called the immanant.

In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column and 0s elsewhere. Each such matrix, say $P$ , represents a permutation of $m$ elements and, when used to multiply another matrix, say $A$ , results in permuting the rows or columns of the matrix $A$ .

In mathematics, Muirhead's inequality, named after Robert Franklin Muirhead, also known as the "bunching" method, generalizes the inequality of arithmetic and geometric means.

In quantum mechanics, a two-state system is a quantum system that can exist in any quantum superposition of two independent quantum states. The Hilbert space describing such a system is two-dimensional. Therefore, a complete basis spanning the space will consist of two independent states. Any two-state system can also be seen as a qubit.

In geometry and linear algebra, a Cartesian tensor uses an orthonormal basis to represent a tensor in a Euclidean space in the form of components. Converting a tensor's components from one such basis to another is done through an orthogonal transformation.

In mathematical physics, the gamma matrices, $also called the Dirac matrices, are a set of conventional matrices with specific anticommutation relations that ensure they generate a matrix representation of the Clifford algebra It is also possible to define higher-dimensional gamma matrices. When interpreted as the matrices of the action of a set of orthogonal basis vectors for contravariant vectors in Minkowski space, the column vectors on which the matrices act become a space of spinors, on which the Clifford algebra of spacetime acts. This in turn makes it possible to represent infinitesimal spatial rotations and Lorentz boosts. Spinors facilitate spacetime computations in general, and in particular are fundamental to the Dirac equation for relativistic spin particles.$

In mathematics, Molien's formula computes the generating function attached to a linear representation of a group G on a finite-dimensional vector space, that counts the homogeneous polynomials of a given total degree that are invariants for G. It is named for Theodor Molien.

In linear algebra, the Laplace expansion, named after Pierre-Simon Laplace, also called cofactor expansion, is an expression of the determinant of an $n \times n$ matrix $B$ as a weighted sum of minors, which are the determinants of some $(n - 1) \times (n - 1)$ submatrices of $B$ . Specifically, for every $i$ ,

In combinatorial mathematics a cycle index is a polynomial in several variables which is structured in such a way that information about how a group of permutations acts on a set can be simply read off from the coefficients and exponents. This compact way of storing information in an algebraic form is frequently used in combinatorial enumeration.

In group theory, a branch of mathematics, the automorphisms and outer automorphisms of the symmetric groups and alternating groups are both standard examples of these automorphisms, and objects of study in their own right, particularly the exceptional outer automorphism of S₆, the symmetric group on 6 elements.

Symmetries in quantum mechanics describe features of spacetime and particles which are unchanged under some transformation, in the context of quantum mechanics, relativistic quantum mechanics and quantum field theory, and with applications in the mathematical formulation of the standard model and condensed matter physics. In general, symmetry in physics, invariance, and conservation laws, are fundamentally important constraints for formulating physical theories and models. In practice, they are powerful methods for solving problems and predicting what can happen. While conservation laws do not always give the answer to the problem directly, they form the correct constraints and the first steps to solving a multitude of problems.

The affine symmetric groups are a family of mathematical structures that describe the symmetries of the number line and the regular triangular tiling of the plane, and related higher-dimensional objects. Each one is an infinite extension of a finite symmetric group, the group of permutations (rearrangements) of a finite set. In addition to their geometric description, the affine symmetric groups may be defined as collections of permutations of the integers that are periodic in a certain sense, or in purely algebraic terms as a group with certain generators and relations. They are studied as part of the fields of combinatorics and representation theory.

References

1 2 Gross, Jonathan L. (2008). Combinatorial methods with computer applications. Discrete mathematics and its applications. Boca Raton, Fla.: Chapman & Hall/CRC. p. 29. ISBN 978-1-58488-743-0.
1 2 Knuth, Donald E. (2002). The Art of Computer Programming. Addison-Wesley. p. 35.
1 2 3 Bogart, Kenneth P. (2000). Introductory combinatorics (3 ed.). London: Harcourt Academic Press. p. 554. ISBN 978-0-12-110830-4.
1 2 Rosen, Kenneth H. (2000). Handbook of discrete and combinatorial mathematics. Boca Raton London New York: CRC press. ISBN 978-0-8493-0149-0.
↑ Fraleigh 1993 , p. 103
↑ Rotman 2006 , p. 108
↑ Sagan 1991 , p. 2
↑ Rotman 2006 , p. 117, 121
↑ Rotman 2006 , p. 118, Prop. 2.35
↑ Rotman 2006 , p. 122

Sources

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

External links

This article incorporates material from cycle on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[8] Note that the cycle notation is not unique: each k-cycle can itself be written in k different ways, depending on the choice of $s_{0}$ in its orbit.

[:0-1] 1 2 Gross, Jonathan L. (2008). Combinatorial methods with computer applications. Discrete mathematics and its applications. Boca Raton, Fla.: Chapman & Hall/CRC. p. 29. ISBN 978-1-58488-743-0.

[:1-2] 1 2 Knuth, Donald E. (2002). The Art of Computer Programming. Addison-Wesley. p. 35.

[:2-3] 1 2 3 Bogart, Kenneth P. (2000). Introductory combinatorics (3 ed.). London: Harcourt Academic Press. p. 554. ISBN 978-0-12-110830-4.

[:3-4] 1 2 Rosen, Kenneth H. (2000). Handbook of discrete and combinatorial mathematics. Boca Raton London New York: CRC press. ISBN 978-0-8493-0149-0.

[5] Fraleigh 1993 , p. 103

[6] Rotman 2006 , p. 108

[7] Sagan 1991 , p. 2

[9] Rotman 2006 , p. 117, 121

[10] Rotman 2006 , p. 118, Prop. 2.35

[11] Rotman 2006 , p. 122

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[lower-alpha 1]

[8]

[9]

[10]