Cycle notation

Cycle notation

In combinatorial mathematics, the cycle notation is a useful convention for writing down a permutation in terms of its constituent cycles.

Definition

Let S be a finite set, and
a_1,ldots,a_k,quad kgeq 2

be distinct elements of S. The expression

(a_1 ldots a_k)

denotes the cycle σ whose action is

a_1mapsto a_2mapsto a_3ldots a_k mapsto a_1.
For each index i,
sigma (a_i) = a_{i+1}.

There are k different expressions for the same cycle; the following all represent the same cycle:

(a_1 a_2 a_3 ldots a_k) = (a_2 a_3 ldots a_k a_1) = cdots = (a_k a_1 a_2 ldots a_{k-1}).,

A 1-element cycle is the same thing as the identity permutation and is omitted. It is customary to express the identity permutation simply as (),.

Permutation as product of cycles

Let pi be a permutation of S, and let

S_1,ldots, S_ksubset S,quad kinmathbb{N}

be the orbits of pi with more than 1 element. For each j=1,ldots,k let n_j denote the cardinality of S_j. Also, choose an a_{1,j}in S_j, and define

a_{i+1,j} = pi(a_{i,j}),quad iinmathbb{N}.,

We can now express pi as a product of disjoint cycles, namely

pi = (a_{1,1} ldots a_{n_1,1}) (a_{2,1} ldots a_{n_2,2}) ldots (a_{k,1} ldots a_{n_k,k}).,

Example

There are the 24 elements of the symmetric group on {1,2,3,4} expressed using the cycle notation, and grouped according to their conjugacy classes:

(),
(12), ;(13),; (14),; (23),; (24),; (34) (transpositions)
(123),; (132),; (124),; (142),; (134),; (143),; (234),; (243)
(12)(34),;(13)(24),; (14)(23)
(1234),; (1243),; (1324),; (1342),; (1423),; (1432)

See also

Search another word or see Cycle notationon Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature
FAVORITES
RECENT

;