Permutation Cycle — Definition, Formula & Examples

A permutation cycle is a sequence of distinct elements where each element maps to the next, and the last element maps back to the first. Every permutation can be written as a product of disjoint cycles.

Given a permutation $\sigma$ on a finite set $S$ , a cycle $(a_1 \; a_2 \; \cdots \; a_k)$ is a subset $\{a_1, a_2, \ldots, a_k\} \subseteq S$ such that $\sigma(a_i) = a_{i+1}$ for $1 \leq i < k$ and $\sigma(a_k) = a_1$ , while $\sigma$ fixes all elements not in the cycle. The integer $k$ is called the length of the cycle. Every permutation of a finite set decomposes uniquely (up to ordering) into a product of disjoint cycles.

How It Works

To find the cycle decomposition of a permutation, start with any element and repeatedly apply the permutation until you return to the starting element — that sequence forms one cycle. Then pick any element not yet included and repeat the process. Continue until every element belongs to a cycle. Fixed points (elements mapped to themselves) are 1-cycles and are usually omitted from the notation. Two disjoint cycles commute, so their order in the product does not matter.

Worked Example

Problem: Write the permutation

\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 1 & 4 & 2 \end{pmatrix}

in cycle notation.

Step 1: Start with 1. Follow the mapping:

1 \to 3 \to 1

. This gives the cycle

(1\;3)

\sigma(1)=3,\quad \sigma(3)=1

Step 2: Next unused element is 2. Follow:

2 \to 5 \to 2

. This gives the cycle

(2\;5)

\sigma(2)=5,\quad \sigma(5)=2

Step 3: The remaining element is 4. Since

\sigma(4) = 4

, it is a fixed point and we omit the 1-cycle

(4)

\sigma(4)=4

Answer:

\sigma = (1\;3)(2\;5)

. The permutation consists of two disjoint 2-cycles (transpositions).

Why It Matters

Cycle decomposition reveals key properties of a permutation at a glance: the order of a permutation equals the least common multiple of its cycle lengths, and parity (even or odd) is determined by counting cycles of even length. These facts are essential in abstract algebra when studying symmetric groups and in combinatorics when counting permutations by cycle type.

Common Mistakes

Mistake: Reading cycle notation as mapping each element to the previous element instead of the next.

Correction: In the cycle

(a\;b\;c)

, the permutation sends

a \to b

b \to c

, and

c \to a

. Each element maps to the element on its right, with the last wrapping to the first.