Cycle (mathematics)

From Wikipedia, the free encyclopedia

It has been suggested that this article or section be merged into Cyclic permutation. (Discuss)

Let <math>S</math> be a set. A cycle is a permutation (bijective function of a set onto itself) such that there exist distinct elements <math>a_1, a_2,\ldots,a_k</math> of <math>S</math> such that

<math>f(a_i) = a_{i+1}\qquad \mbox{and}\qquad f(a_k)=a_1~,</math>

that is

<math>\begin{matrix} f(a_1)&=&a_{2}\\ f(a_{2})&=&a_{3}\\ &\vdots&\\ f(a_{k})&=&a_{1}\\ \end{matrix}</math>

and <math>f(x)=x</math> for any other element of <math>S.</math>

This can also be pictured as

<math>a_1\mapsto a_{2}\mapsto a_{3}\mapsto\cdots\mapsto a_{k}\mapsto a_{1}</math>

and

<math>x\mapsto x</math>

for any other element <math>x\in S</math>, where <math>\mapsto</math> represents the action of <math>f.</math>

Instead writing its explicit table <math>f = \left[{a_1~a_2~...~a_k \atop a_2~...~a_k~a_1}\right]</math>, such a cycle is usually written in the compact form <math>f = (a_1~a_2~...~a_k)</math>. (There are no commas between elements in this notation, else it would be an k-tuple, and as such the map <math>1\mapsto a_1,...,k\mapsto a_k</math>, which in turn would be the permutation having 1,2,...,k in the first, and <math>a_1,a_2,...,a_k</math> in the second line of its "table style" notation.)

Equivalently, one can define a cycle as a permutation having exactly one orbit which is not a singleton. (The orbits of a permutation f of S are the sets { f^{k^{(x) ; k∈Z}, x∈ S; they form a partition of S.)}}

The length of a cycle, denoted by |f|, L(f) or o(f) (since it turns out to be equal to the order of f), is the number of elements of its nontrivial orbit. A cycle of length k is also called a k-cycle.

A k-cycle f has signature sgnf=(-1)^k-1.

One of the basic results on symmetric groups says that any permutation can be expressed as product of disjoint cycles (more precisely: cycles of disjoint support suppf = { x∈S | f(x) ≠ x }). Furthermore, the representation of a permutation as a product of disjoint cycles is unique up to the order of the cycles. (It can be easily seen that disjoint cycles commute.) It thus follows that the number of the cycles in such a representation and its parity are functions of the permutation.