Cycles

A simple example of a permutation is obtained as follows: choose any two distinct integers between $1$ and $k$ , say, $p$ and $q$ , and write \begin{align} \tau (p) &= q,\\ \tau (q) &= p,\\ \tau (i) &= i \text{ whenever } i \neq p \text{ and } i \neq q. \end{align}The permutation $τ$ so defined is denoted by $(p, q)$ ; every permutation of this form is called a transposition . If $τ$ is a transposition, then $τ^{2} = ϵ$ .

Another useful way of constructing examples is to choose $p$ distinct integers between $1$ and $k$ , say, $i_{1}, \dots, i_{p}$ , and to write \begin{align} \sigma (i_j) &= i_{j+1} \text{ whenever } 1 \leq j < p,\\ \sigma (i_p) &= i_1,\\ \sigma (i) &= i \text{ whenever } i \neq i_1, \ldots, i \neq i_p. \end{align}The permutation $σ$ so defined is denoted by $(i_{1}, \dots, i_{p})$ . If $p = 1$ , then $σ = ϵ$ ; if $p = 2$ , then $σ$ is a transposition. For any $p$ with $1 < p \leq k$ , every permutation of the form $(i_{1}, \dots, i_{p})$ is called a p-cycle , or simply a cycle ; the $2$ -cycles are exactly the transpositions. Warning: it is not assumed that $i_{1} < \dots < i_{p}$ . If, for instance, $k = 5$ and $p = 3$ , then there are twenty distinct cycles. Observe also that the notation for cycles is not unique; the symbols $(1, 2, 3)$ , $(2, 3, 1)$ , and $(3, 1, 2)$ all denote the same permutation. Two cycles $(i_{1}, \dots, i_{p})$ and $(j_{1}, \dots, j_{q})$ are disjoint if none of the $i$ ’s is equal to any of the $j$ ’s. If $σ$ and $τ$ are disjoint cycles, then $σ τ = τ σ$ , or, in other words, $σ$ and $τ$ commute.

Theorem 1. Every permutation is the product of pairwise disjoint cycles.

Proof. If $π$ is a permutation and if $i$ is such that $π (i) \neq i$ (assume, for the moment, that $π \neq ϵ$ ), form the sequence $(i, π (i), π^{2} (i), \dots)$ . Since there are only a finite number of distinct integers between $1$ and $k$ , there must exist exponents $p$ and $q$ $(0 \leq p < q)$ such that $π^{p} (i) = π^{q} (i)$ . The one-to-one character of $π$ implies that $π^{q - p} (i) = i$ , or, with an obvious change of notation, what we have proved is that there must exist a strictly positive exponent $p$ such that $π^{p} (i) = i$ . If $p$ is selected to be the smallest exponent with this property, then the integers $i, \dots, π^{p - 1} (i)$ are distinct from each other. (Indeed, if $0 \leq q < r < p$ and $π^{r} (i) = π^{q} (i)$ , then $π^{r - q} (i) = i$ , contradicting the minimality of $p$ .) It follows that $(i, \dots, π^{p - 1} (i))$ is a $p$ -cycle. If there is a $j$ between $1$ and $k$ different from each of $i, \dots, π^{p - 1} (i)$ and different from $π (j)$ , we repeat the procedure that led us to this cycle, with $j$ in place of $i$ . We continue forming cycles in this manner as long as after each step we can still find a new integer that $π$ does not send on itself; the product of the disjoint cycles so constructed is $π$ . The case $π = ϵ$ is covered by the rather natural agreement that a product with no factors, an “empty product,” is to be interpreted as the identity permutation. ◻

Theorem 2. Every cycle is a product of transpositions.

Proof. Suppose that $σ$ is a $p$ -cycle; for the sake of notational simplicity, we shall give the proof, which is perfectly general, in the special case $p = 5$ . The proof itself consists of one line: $(i_{1}, i_{2}, i_{3}, i_{4}, i_{5}) = (i_{1}, i_{5}) (i_{1}, i_{4}) (i_{1}, i_{3}) (i_{1}, i_{2}) .$ A few added words of explanation might be helpful. In view of the definition of the product of permutations, the right side of the last equation operates on each integer between $1$ and $k$ from the inside out, or, perhaps more suggestively, from right to left. Thus, for example, the result of applying $(i_{1}, i_{5}) (i_{1}, i_{4}) (i_{1}, i_{3}) (i_{1}, i_{2})$ to $i_{3}$ is calculated as follows: $(i_{1}, i_{2}) (i_{3}) = i_{3}$ , $(i_{1}, i_{3}) (i_{3}) = i_{1}$ , $(i_{1}, i_{4}) (i_{1}) = i_{4}$ , $(i_{1}, i_{5}) (i_{4}) = i_{4}$ , so that $(i_{1}, i_{5}) (i_{1}, i_{4}) (i_{1}, i_{3}) (i_{1}, i_{2}) (i_{3}) = i_{4}$ . ◻

For the sake of reference we put on record the following immediate corollary of the two preceding theorems.

Theorem 3. Every permutation is a product of transpositions.

Observe that the transpositions in Theorems 2 and 3 were not asserted to be disjoint; in general they are not.

EXERCISES

Exercise 1.

How many permutations are there in $𝒮_{k}$ ?
How many distinct $p$ -cycles are there in $𝒮_{k}$ ( $1 \leq p \leq k$ )?

Exercise 2. If $σ$ and $τ$ are permutations (in $𝒮_{k}$ ), then $(σ τ)^{- 1} = τ^{- 1} σ^{- 1}$ .

Exercise 3.

If $σ$ and $τ$ are permutations (in $𝒮_{k}$ ), then there exists a unique permutation $π$ such that $σ π = τ$ .
If $π$ , $σ$ , and $τ$ are permutations such that $π σ = π τ$ , then $σ = τ$ .

Exercise 4. Give an example of a permutation that is not the product of disjoint transpositions.

Exercise 5. Prove that every permutation in $𝒮_{k}$ is the product of transpositions of the form $(j, j + 1)$ , where $1 \leq j < k$ . Is this factorization unique?

Exercise 6. Is the inverse of a cycle also a cycle?

Exercise 7. Prove that the representation of a permutation as the product of disjoint cycles is unique except possibly for the order of the factors.

Exercise 8. The order of a permutation $π$ is the least integer $p$ ( $> 0$ ) such that $π^{p} = ϵ$ .

Every permutation has an order.
What is the order of a $p$ -cycle?
If $σ$ is a $p$ -cycle, $τ$ is a $q$ -cycle, and $σ$ and $τ$ are disjoint, what is the order of $σ τ$ ?
Give an example to show that the assumption of disjointness is essential in (c).
If $π$ is a permutation of order $p$ and if $π^{q} = ϵ$ , then $q$ is divisible by $p$ .

Exercise 9. Every permutation in $𝒮_{k}$ ( $k > 1$ ) can be written as a product, each factor of which is one of the transpositions $(1, 2), (1, 3), (1, 4), \dots, (1, k)$ .

Exercise 10. Two permutations $σ$ and $τ$ are called conjugate if there exists a permutation $π$ such that $σ π = π τ$ . Prove that $σ$ and $τ$ are conjugate if and only if they have the same cycle structure. (This means that in the representation of $σ$ as a product of disjoint cycles, the number of $p$ -cycles is, for each $p$ , the same as the corresponding number for $τ$ .)

EXERCISES

Quick Links

Social Media