Cyclic permutation

For other uses, see Cyclic (mathematics).

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}.

For the wider definition of a cyclic permutation, allowing fixed points, these fixed points each constitute trivial orbits of the permutation, and there is a single non-trivial orbit containing all the remaining points. This can be used as a definition: a cyclic permutation (allowing fixed points) is a permutation that has a single non-trivial orbit. Every permutation on finitely many elements can be decomposed into cyclic permutations whose non-trivial orbits are disjoint.[5]

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.

  1. ^ 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.
  2. ^ Knuth, Donald E. (2002). The Art of Computer Programming. Addison-Wesley. p. 35.
  3. ^ a b Bogart, Kenneth P. (2000). Introductory combinatorics (3 ed.). London: Harcourt Academic Press. p. 554. ISBN 978-0-12-110830-4.
  4. ^ Rosen, Kenneth H. (2000). Handbook of discrete and combinatorial mathematics. Boca Raton London New York: CRC press. ISBN 978-0-8493-0149-0.
  5. ^ Ehrlich, Gertrude (2013). Fundamental Concepts of Abstract Algebra. Dover Books on Mathematics. Courier Corporation. p. 69. ISBN 9780486291864.