Cyclic permutation

(Redirected from Adjacent transposition)

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.

Definition

edit
 
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   if the restriction of   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   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

 

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

With the enlarged definition, there are cyclic permutations that do not consist of a single cycle.

More formally, for the enlarged definition, a permutation   of a set X, viewed as a bijective function  , 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.[6] This notion is most commonly used when X is a finite set; then 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 cyclic permutation can be written using the compact cycle notation   (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.[7] When cycle notation is used, the 1-cycles are often omitted when no confusion will result.[8]

Basic properties

edit

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.[a] 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.[9]

The number of k-cycles in the symmetric group Sn is given, for  , by the following equivalent formulas:  

A k-cycle has signature (−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

edit
 
Matrix of  

A cycle with only two elements is called a transposition. For example, the permutation   that swaps 2 and 4. Since it is a 2-cycle, it can be written as  .

Properties

edit

Any permutation can be expressed as the composition (product) of transpositions—formally, they are generators for the group.[10] 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   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 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:

 

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

See also

edit

Notes

edit
  1. ^ Note that the cycle notation is not unique: each k-cycle can itself be written in k different ways, depending on the choice of   in its orbit.

References

edit
  1. ^ a b 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. ^ a b Knuth, Donald E. (2002). The Art of Computer Programming. Addison-Wesley. p. 35.
  3. ^ a b c Bogart, Kenneth P. (2000). Introductory combinatorics (3 ed.). London: Harcourt Academic Press. p. 554. ISBN 978-0-12-110830-4.
  4. ^ a b 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.
  6. ^ Fraleigh 1993, p. 103
  7. ^ Rotman 2006, p. 108
  8. ^ Sagan 1991, p. 2
  9. ^ Rotman 2006, p. 117, 121
  10. ^ Rotman 2006, p. 118, Prop. 2.35
  11. ^ Rotman 2006, p. 122

Sources

edit
  • 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
edit

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