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. 

  1. How many permutations are there in \(\mathcal{S}_k\) ?
  2. 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. 

  1. If \(\sigma\) and \(\tau\) are permutations (in \(\mathcal{S}_k\) ), then there exists a unique permutation \(\pi\) such that \(\sigma \pi = \tau\) .
  2. 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\) .

  1. Every permutation has an order.
  2. What is the order of a \(p\) -cycle?
  3. If \(\sigma\) is a \(p\) -cycle, \(\tau\) is a \(q\) -cycle, and \(\sigma\) and \(\tau\) are disjoint, what is the order of \(\sigma \tau\) ?
  4. Give an example to show that the assumption of disjointness is essential in (c).
  5. 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\) .)