Cyclic permutation

In mathematics, a cyclic permutation, also known as a cycle, is a permutation of a finite set that can be expressed as a single cycle mapping its elements in a circular fashion, where each element is sent to the next in the sequence and the last returns to the first.^[1] For a set with $m$ elements, an $m$-cycle is a bijective function $f$ such that there exist distinct elements $a_1, a_2, \dots, a_m$ where $f(a_1) = a_2$, $f(a_2) = a_3$, ..., $f(a_{m-1}) = a_m$, and $f(a_m) = a_1$.^[1] Cyclic permutations are fundamental in the study of the symmetric group $S_n$, which consists of all permutations of $n$ elements, as every permutation can be uniquely decomposed into a product of disjoint cycles.^[2] Cycle notation provides a compact way to represent cyclic permutations, enclosing the elements in parentheses in the order they are mapped, such as $(a_1 \, a_2 \, \dots \, a_m)$ for the cycle described above; rotations of the sequence, like $(a_2 \, \dots \, a_m \, a_1)$, denote the same cycle.^[1] The order of an $m$-cycle, defined as the smallest positive integer $k$ such that applying the permutation $k$ times yields the identity, is exactly $m$.^[1] In group theory, the inverse of an $m$-cycle $(a_1 \, a_2 \, \dots \, a_m)$ is $(a_m \, a_{m-1} \, \dots \, a_1)$, and the number of distinct $n$-cycles in $S_n$ is $(n-1)!$.^[1] Cyclic permutations play a central role in permutation groups, where the composition of cycles follows function composition rules, and disjoint cycles commute under multiplication.^[2] They are used to analyze the structure of symmetric groups, compute determinants via permutation expansions, and model symmetries in combinatorics and algebra.^[3] For instance, the alternating group $A_n$, consisting of even permutations, can be generated by 3-cycles for $n \geq 3$.^[4]

Fundamentals

Definition

A permutation of a finite set $S$ is a bijective function $\sigma: S \to S$.^[5] A cyclic permutation is a permutation $\sigma$ of a finite set $S$ that consists of a single cycle. More precisely, $\sigma$ is a $k$-cycle for some integer $k \geq 1$ if there exist distinct elements $a_1, a_2, \dots, a_k \in S$ such that $\sigma(a_i) = a_{i+1}$ for $1 \leq i < k$, $\sigma(a_k) = a_1$, and $\sigma(x) = x$ for all $x \in S \setminus \{a_1, \dots, a_k\}$.^[6] Unlike arbitrary permutations, which can decompose into multiple disjoint cycles acting on different subsets of elements, a cyclic permutation involves exactly one such cycle on its support—the set of elements it moves—with no fixed points or additional disjoint cycles within that support.^[5] For example, on the set $S = \{1, 2, 3\}$, the permutation $\sigma$ given by $\sigma(1) = 2$, $\sigma(2) = 3$, $\sigma(3) = 1$ is a cyclic permutation, as it cycles all three elements in a single loop.^[7] This is commonly denoted in cycle notation as $(1\ 2\ 3)$.

Cycle Notation

Cycle notation provides a compact and standardized way to represent cyclic permutations, which are bijections on a finite set that consist of a single non-trivial cycle and possibly fixed points. A cyclic permutation of length $k$ on elements $a_1, a_2, \dots, a_k$ is denoted by $(a_1 \, a_2 \, \dots \, a_k)$, where the parentheses enclose the sequence of elements cycled in order. This notation indicates that the permutation maps $a_1$ to $a_2$, $a_2$ to $a_3$, ..., $a_{k-1}$ to $a_k$, and $a_k$ back to $a_1$, while leaving all other elements unchanged (acting as the identity on fixed points).^[5][8] The notation is invariant under cyclic rotations of the elements within the cycle; for instance, $(1 \, 2 \, 3)$ is equivalent to $(2 \, 3 \, 1)$ and $(3 \, 1 \, 2)$, as each represents the same mapping. Fixed points, which are 1-cycles, are conventionally omitted from the notation to emphasize the non-trivial structure, so the identity permutation on a set is often left blank or denoted simply as the empty product. For permutations composed of multiple disjoint cycles, the cycles are written side by side in any order (since disjoint cycles commute), but the focus here remains on single cycles. A special case is the 2-cycle, or transposition, written as $(a \, b)$, which swaps $a$ and $b$ while fixing all else; for example, $(1 \, 2)$ maps 1 to 2 and 2 to 1.^[5][8] To interpret the notation as a function, one traces the arrows defined by the sequence: in $(1 \, 3 \, 2)$, 1 maps to 3, 3 to 2, and 2 to 1, with all other elements fixed. Another example is the 4-cycle $(a \, b \, c \, d)$, which sends $a \to b \to c \to d \to a$. This representation highlights the cyclic structure efficiently, avoiding the need to list mappings for every element in the set.^[5][8] The cycle notation was introduced by Augustin-Louis Cauchy in his 1844 memoir "Mémoire sur les arrangements que l’on peut former avec des lettres données," building on his earlier work on permutation theory from 1815.^[9][10]

Properties

Basic Properties

Cyclic permutations in the symmetric group $S_n$ generate cyclic subgroups under composition. Specifically, for a $k$-cycle $\sigma \in S_n$, the subgroup $\langle \sigma \rangle = \{\sigma^m \mid m \in \mathbb{Z}\}$ is cyclic of order $k$.^[11][12] The composition of two cyclic permutations whose supports are disjoint commutes and yields a permutation that is the product of those disjoint cycles. For example, if $\alpha = (a_1 \dots a_k)$ and $\beta = (b_1 \dots b_m)$ with $\{a_1, \dots, a_k\} \cap \{b_1, \dots, b_m\} = \emptyset$, then $\alpha \circ \beta = \beta \circ \alpha = (a_1 \dots a_k)(b_1 \dots b_m)$.^[12] The inverse of a $k$-cycle $\sigma = (a_1 \, a_2 \, \dots \, a_k)$ is the $k$-cycle $\sigma^{-1} = (a_k \, a_{k-1} \, \dots \, a_1)$, which reverses the cyclic order.^[13][12] The $m$-th power of a $k$-cycle $\sigma = (a_1 \, a_2 \, \dots \, a_k)$ acts by shifting each element $m$ positions along the cycle, so $\sigma^m(a_i) = a_{i+m \mod k}$.^[12] All $k$-cycles in $S_n$ (for $n \geq k$) are conjugate to one another. That is, for any two $k$-cycles $\alpha$ and $\beta$, there exists $\tau \in S_n$ such that $\tau \alpha \tau^{-1} = \beta$, and explicitly, $\tau (a_1 \dots a_k) \tau^{-1} = (\tau(a_1) \dots \tau(a_k))$.^[14][12]

Cycle Length and Order

The length of a cycle, denoted as $k$ for a $k$-cycle, refers to the number of distinct elements it permutes, which determines the minimal period over which the permutation repeats its action on those elements.^[15][16] In the symmetric group $S_n$, a $k$-cycle with $k \leq n$ acts by cyclically shifting these $k$ elements while leaving the remaining $n - k$ elements unchanged, known as fixed points.^[16][17] The order of a permutation $\sigma$ in $S_n$ is the smallest positive integer $m$ such that $\sigma^m$ is the identity permutation. For a $k$-cycle $\sigma = (a_1 \, a_2 \, \dots \, a_k)$, the order is exactly $k$, as $\sigma^k$ returns each $a_i$ to its original position, and no smaller positive exponent achieves this due to the orbit size of $k$ under the cyclic action.^[15][16] This follows from the fact that applying $\sigma^m$ shifts each element by $m$ positions modulo $k$, so $\sigma^m = \mathrm{id}$ if and only if $m \equiv 0 \pmod{k}$:

$$\sigma^m(a_i) = a_{i + m \mod k},$$

with the identity requiring $m$ to be a multiple of $k$.^[15] Fixed points remain invariant under all powers of $\sigma$, preserving their status through iteration.^[16] Consider the example of $\sigma = (1 \, 2 \, 3 \, 4)$ in $S_4$, a 4-cycle with no fixed points. Then $\sigma(1) = 2$, $\sigma(2) = 3$, $\sigma(3) = 4$, $\sigma(4) = 1$. Computing powers:

• $\sigma^1 = (1 \, 2 \, 3 \, 4)$,
• $\sigma^2 = (1 \, 3)(2 \, 4)$,
• $\sigma^3 = (1 \, 4 \, 3 \, 2)$,
• $\sigma^4 = \mathrm{id}$.

This confirms the order is 4, as each power cycles the elements until returning to the identity.^[15][16]

Decomposition and Representation

Cycle Decomposition

Every permutation in the symmetric group $S_n$, which consists of all bijections on a finite set of $n$ elements, can be uniquely expressed as a product of disjoint cycles, up to the order of the cycles and the starting point within each cycle.^[18][19] This decomposition theorem establishes that cyclic permutations serve as the fundamental building blocks for representing any permutation $\sigma \in S_n$. The proof of existence proceeds by induction on the size of the set: for a base case of one element, the identity is a trivial 1-cycle; inductively, select an element $x$ not fixed by $\sigma$, form the cycle by iterating $\sigma$ until returning to $x$, and apply induction to the restriction on the remaining elements after removing the cycle's support.^[20] Uniqueness follows from the fact that the orbits under $\sigma$—the sets of elements cycled together—are uniquely determined, ensuring no overlapping cycles in any valid decomposition.^[18] Formally, any $\sigma \in S_n$ decomposes as $\sigma = c_1 \circ c_2 \circ \cdots \circ c_m$, where the $c_i$ are disjoint cycles whose supports partition the moved elements of $\{1, 2, \dots, n\}$, and fixed points are omitted as 1-cycles.^[19] To compute this decomposition algorithmically, proceed as follows: initialize a list of visited elements as empty; for each unvisited element $x$ in $\{1, 2, \dots, n\}$, start a new cycle with $x$, then iteratively append $\sigma(y)$ for the current $y$ in the cycle until returning to $x$, marking all elements in this cycle as visited; repeat until all elements are visited. This process yields the disjoint cycles in linear time relative to $n$.^[20] Since the cycles in the decomposition are disjoint, they commute under composition: if $c_i$ and $c_j$ ($i \neq j$) have no common elements, then $c_i \circ c_j = c_j \circ c_i$.^[18][19] Moreover, the order of $\sigma$—the smallest positive integer $k$ such that $\sigma^k$ is the identity—is the least common multiple of the lengths of the cycles $c_1, \dots, c_m$.^[18][19] For example, consider the permutation $\sigma$ in $S_5$ defined by $\sigma(1) = 3$, $\sigma(3) = 4$, $\sigma(4) = 1$, $\sigma(2) = 5$, $\sigma(5) = 2$. Starting with 1 (unvisited), the cycle is $1 \to 3 \to 4 \to 1$, giving $(1\ 3\ 4)$; next, 2 (unvisited) yields $2 \to 5 \to 2$, giving $(2\ 5)$. Thus, $\sigma = (1\ 3\ 4) \circ (2\ 5)$.^[18]

Relation to Transpositions

A cyclic permutation, or $k$-cycle, can be expressed as a product of $k-1$ transpositions. One standard decomposition is given by

$$(a_1 \, a_2 \, \dots \, a_k) = (a_1 \, a_k)(a_1 \, a_{k-1}) \dotsm (a_1 \, a_3)(a_1 \, a_2),$$

where the transpositions are multiplied from right to left.^[21][22] This equality can be verified by induction on $k$. For the base case $k=2$, the $2$-cycle is already a transposition, so the product is trivial with $2-1=1$ transposition. Assume the statement holds for a $(k-1)$-cycle: $(a_1 \, a_2 \, \dots \, a_{k-1}) = (a_1 \, a_{k-1}) \dotsm (a_1 \, a_2)$. For the $k$-case, let $C = (a_1 \, a_2 \, \dots \, a_{k-1})$ and $P = (a_1 \, a_k) \circ C$. Then:

• $P(a_1) = (a_1 \, a_k)(C(a_1)) = (a_1 \, a_k)(a_2) = a_2$,
• $P(a_i) = (a_1 \, a_k)(C(a_i)) = (a_1 \, a_k)(a_{i+1}) = a_{i+1}$ for $2 \leq i \leq k-2$,
• $P(a_{k-1}) = (a_1 \, a_k)(C(a_{k-1})) = (a_1 \, a_k)(a_1) = a_k$,
• $P(a_k) = (a_1 \, a_k)(C(a_k)) = (a_1 \, a_k)(a_k) = a_1$.

This matches the action of the $k$-cycle $(a_1 \, a_2 \, \dots \, a_k)$, confirming the decomposition uses exactly $k-1$ transpositions.^[22][21] The sign (or parity) of a $k$-cycle follows directly from this decomposition, as the sign of a product of transpositions is $(-1)$ raised to the number of factors. With $k-1$ transpositions, the sign is $(-1)^{k-1}$. Thus, a $k$-cycle is an even permutation if $k$ is odd (even number of transpositions) and odd if $k$ is even (odd number of transpositions). This parity determines membership in the alternating group $A_n$, the subgroup of even permutations in the symmetric group $S_n$.^[22] The number $k-1$ is minimal: no $k$-cycle can be written as a product of fewer than $k-1$ transpositions. For a permutation in $S_n$ consisting of $m$ disjoint cycles (including fixed points as $1$-cycles), the minimal number of transpositions is $n-m$. A pure $k$-cycle has $m = n-k+1$ cycles, so the minimum is $n - (n-k+1) = k-1$.^[22] For example, consider the $4$-cycle $(1 \, 2 \, 3 \, 4)$. It decomposes as $(1 \, 4)(1 \, 3)(1 \, 2)$. Applying this product from right to left completes the cycle, sending $1 \to 2 \to 3 \to 4 \to 1$. With $3$ transpositions (odd), the parity is odd, matching $(-1)^{4-1} = -1$, so $(1 \, 2 \, 3 \, 4) \notin A_4$.^[21][22]

Applications

In Group Theory

In group theory, cyclic permutations play a fundamental role in the structure of the symmetric group $S_n$, which consists of all permutations of $n$ elements under composition. The subgroup generated by a single $k$-cycle $\sigma \in S_n$ is the cyclic subgroup $\langle \sigma \rangle$, which has order $k$ since $\sigma^k$ is the identity and no smaller positive power yields the identity. This subgroup is isomorphic to the cyclic group $\mathbb{Z}_k$.^[16] All $k$-cycles in $S_n$ form a single conjugacy class under conjugation by elements of $S_n$, meaning that for any two $k$-cycles $\sigma$ and $\tau$, there exists $\pi \in S_n$ such that $\pi \sigma \pi^{-1} = \tau$. The size of this conjugacy class is $\frac{n!}{k (n-k)!}$, reflecting the number of distinct $k$-cycles up to the action of conjugation.^[14] Cyclic permutations of odd length, such as 3-cycles, are even permutations and lie in the alternating group $A_n$, the kernel of the sign homomorphism from $S_n$ to $\mathbb{Z}/2\mathbb{Z}$. In fact, $A_n$ for $n \geq 3$ is generated by all 3-cycles, illustrating how these cyclic permutations generate the entire even permutation subgroup.^[23] The centralizer of a $k$-cycle $\sigma$ in $S_n$, denoted $C_{S_n}(\sigma)$, consists of all elements that commute with $\sigma$ and has order $k (n-k)!$. It is generated by the powers of $\sigma$ and the symmetric group on the $n-k$ fixed points of $\sigma$, so $C_{S_n}(\sigma) \cong \mathbb{Z}_k \times S_{n-k}$. The normalizer of the subgroup $\langle \sigma \rangle$ in $S_n$ is larger, incorporating automorphisms of $\langle \sigma \rangle$, and has order $k (n-k)! \cdot \phi(k)$ where $\phi$ is Euler's totient function, accounting for the ways to conjugate $\sigma$ to other generators of the same subgroup.^[24][25] The study of cyclic permutations in symmetric groups originated with Augustin-Louis Cauchy, who in 1844 introduced the concept of cycle decomposition and used it to classify permutations, laying foundational work for the theory of permutation groups as an autonomous subject.^[10] For example, in $S_3$, the 3-cycle $(1\,2\,3)$ generates the cyclic subgroup $A_3$ of order 3, which is the alternating group on 3 elements; adjoining a transposition like $(1\,2)$ generates the full $S_3$. Similarly, in $A_4$, the 3-cycles such as $(1\,2\,3)$ and $(1\,2\,4)$ together generate the entire group of order 12.^[16]

In Combinatorics

In combinatorics, cyclic permutations play a key role in enumerative problems, particularly in counting the structures within the symmetric group $S_n$. The number of permutations in $S_n$ that consist of a single $k$-cycle (with the remaining $n-k$ elements fixed) is given by $\binom{n}{k} (k-1)!$, which simplifies to $\frac{n!}{k (n-k)!}$ for $1 < k \leq n$. This formula arises by first choosing $k$ elements out of $n$ to form the cycle, which can be done in $\binom{n}{k}$ ways, and then arranging them into a cycle, which requires $(k-1)!$ distinct cyclic orders since rotations of the same arrangement represent the same permutation.^[26] For example, the number of 3-cycles in $S_5$ is $\frac{5!}{3 \cdot 2!} = \frac{120}{6} = 20$. More generally, the values for small $n$ and corresponding $k > 1$ illustrate the growth: These counts are computed using the formula above, highlighting how the number peaks near intermediate $k$ values relative to $n$.^[26] Cyclic permutations also connect to the cycle index polynomial, a tool in Pólya enumeration for counting distinct objects under group actions. The cycle index $Z(G)$ of a permutation group $G$ acting on a set of size $n$ is $Z(G) = \frac{1}{|G|} \sum_{g \in G} \prod_{i=1}^n x_i^{c_i(g)}$, where $c_i(g)$ denotes the number of cycles of length $i$ in $g$. When $G$ is the cyclic group generated by an $n$-cycle, the cycle index encodes the fixed points under rotations, enabling counts of orbits like necklace colorings, where cyclic symmetries identify equivalent arrangements. Burnside's lemma, which equates the number of orbits to the average number of fixed points, relies on this cycle structure to solve such problems.^[27][28] A key application appears in counting derangements (fixed-point-free permutations) and more generally fixed-point-free permutations, which exclude 1-cycles in their decomposition. The exponential generating function for all permutations is $\exp\left( \sum_{k=1}^\infty \frac{x^k}{k} \right)$, but for those without 1-cycles, it becomes $\exp\left( \sum_{k=2}^\infty \frac{x^k}{k} \right) = \frac{e^{-x}}{1-x}$, yielding the derangement count $ !n = n! \sum_{i=0}^n \frac{(-1)^i}{i!} $. This ties to cycle decompositions, as derangements sum the sizes of conjugacy classes with no 1-cycles, using cyclic permutation counts as building blocks.^[29] Finally, cyclic permutations relate to unsigned Stirling numbers of the first kind $|s(n,k)|$, which count the total number of permutations in $S_n$ with exactly $k$ cycles (including 1-cycles as fixed points). Specifically, $|s(n,k)| = (-1)^{n-k} s(n,k)$, where $s(n,k)$ is the signed version, and the generating function $\sum_{k=0}^n s(n,k) x^k = x(x+1)\cdots(x+n-1)$ reflects the cycle structure distribution. This connection allows enumeration of multi-cycle permutations via compositions involving single cyclic components.^[30]