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 \tau so defined is denoted by (p, q) ; every permutation of this form is called a transposition . If \tau is a transposition, then \tau^2 = \epsilon .
Another useful way of constructing examples is to choose p distinct integers between 1 and k , say, i_1, \ldots, 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 \sigma so defined is denoted by (i_1, \ldots, i_p) . If p = 1 , then \sigma = \epsilon ; if p = 2 , then \sigma is a transposition. For any p with 1 < p \leq k , every permutation of the form (i_1, \ldots, 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 < \cdots < 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, \ldots, i_p) and (j_1, \ldots, j_q) are disjoint if none of the i ’s is equal to any of the j ’s. If \sigma and \tau are disjoint cycles, then \sigma \tau = \tau \sigma , or, in other words, \sigma and \tau commute.
Theorem 1. Every permutation is the product of pairwise disjoint cycles.
Proof. If \pi is a permutation and if i is such that \pi (i) \neq i (assume, for the moment, that \pi \neq \epsilon ), form the sequence (i, \pi (i), \pi^2 (i), \ldots) . 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 \pi^p (i) = \pi^q (i) . The one-to-one character of \pi implies that \pi^{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 \pi^p (i) = i . If p is selected to be the smallest exponent with this property, then the integers i, \ldots, \pi^{p-1} (i) are distinct from each other. (Indeed, if 0 \leq q < r < p and \pi^r (i) = \pi^q (i) , then \pi^{r-q} (i) = i , contradicting the minimality of p .) It follows that (i, \ldots, \pi^{p-1} (i)) is a p -cycle. If there is a j between 1 and k different from each of i, \ldots, \pi^{p-1} (i) and different from \pi (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 \pi does not send on itself; the product of the disjoint cycles so constructed is \pi . The case \pi = \epsilon 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 \sigma 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 \mathcal{S}_k ?
- How many distinct p -cycles are there in \mathcal{S}_k ( 1 \leq p \leq k )?
Exercise 2. If \sigma and \tau are permutations (in \mathcal{S}_k ), then (\sigma \tau)^{-1} = \tau^{-1} \sigma^{-1} .
Exercise 3.
- If \sigma and \tau are permutations (in \mathcal{S}_k ), then there exists a unique permutation \pi such that \sigma \pi = \tau .
- If \pi , \sigma , and \tau are permutations such that \pi \sigma = \pi \tau , then \sigma = \tau .
Exercise 4. Give an example of a permutation that is not the product of disjoint transpositions.
Exercise 5. Prove that every permutation in \mathcal{S}_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 \pi is the least integer p ( > 0 ) such that \pi^p = \epsilon .
- Every permutation has an order.
- What is the order of a p -cycle?
- If \sigma is a p -cycle, \tau is a q -cycle, and \sigma and \tau are disjoint, what is the order of \sigma \tau ?
- Give an example to show that the assumption of disjointness is essential in (c).
- If \pi is a permutation of order p and if \pi^q = \epsilon , then q is divisible by p .
Exercise 9. Every permutation in \mathcal{S}_k ( k > 1 ) can be written as a product, each factor of which is one of the transpositions (1, 2), (1, 3), (1, 4), \ldots, (1, k) .
Exercise 10. Two permutations \sigma and \tau are called conjugate if there exists a permutation \pi such that \sigma \pi = \pi \tau . Prove that \sigma and \tau are conjugate if and only if they have the same cycle structure. (This means that in the representation of \sigma as a product of disjoint cycles, the number of p -cycles is, for each p , the same as the corresponding number for \tau .)
