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}.
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=1transposition. 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})andP = (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.
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:| n | k=2 | k=3 | k=4 | k=5 |
|---|---|---|---|---|
| 3 | 3 | 2 | - | - |
| 4 | 6 | 8 | 6 | - |
| 5 | 10 | 20 | 30 | 24 |