1.4 Permutations

Definition 1.10

  • A permutation of a set X is a bijection from X to X.
  • If \(X=\{1,2,\ldots,n\}\) we write \(S_n\) for the set of all permutations of X, and call \(S_n\) the symmetric group on n letters.

Sometimes, like when \(X=\{1,2,3,\ldots,n\}\), a set comes with a natural order. Then a permutation \(\sigma\) can be thought of as a re-ordering of X, since the elements \(\sigma(1),\sigma(2),\ldots,\sigma(n)\) are the numbers 1,2,…,n written in some different order.

If \(\sigma\) and \(\tau\) are permutations we will often write \(\sigma \circ \tau\) as \(\sigma \tau\), and refer to it as the product of \(\sigma\) and \(\tau\) instead of the composition.

1.4.1 Two row notation

To record an element \(\sigma\in S_n\), we need to say what \(\sigma(i)\) is for \(1\leq i \leq n\). One way to do this is two row notation in which we write the numbers 1 to n in a row and then write \(\sigma(i)\) beneath i: \[ \begin{pmatrix} 1 & 2 & \cdots & n-1 & n \\ \sigma(1) & \sigma(2) & \cdots & \sigma(n-1) & \sigma(n) \end{pmatrix} \] Because elements of \(S_n\) are bijections, the numbers appearing on the bottom row are just 1,2,…,n written in a possibly different order.

The inverse of a bijection is again a bijection so if \(\sigma \in S_n\) then \(\sigma^{-1} \in S_n\). If we have \(\sigma\) in two row notation it is easy to find its inverse: since \(\sigma^{-1}\) must send \(\sigma(i)\) to i, we just swap the two rows and then rearrange the columns so that the top row is in the correct order. For example, if we begin with \[ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 1 & 2 \end{pmatrix} \] then on swapping the rows we get \[ \begin{pmatrix} 3 & 4 & 5 & 1 & 2 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix} \] and rearranging gives \[ \sigma^{-1} = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 1 & 2 & 3 \end{pmatrix}.\]

Theorem 1.3 \(|S_n|=n!\).

Proof. Induction on n. When \(n=1\) there is a unique bijection \(\{1\}\to\{1\}\), namely the identity map, so \(|S_1|=1=1!\) as required.

For the inductive step, note that the number of elements of \(S_n\) is the number of different ways to order the elements \(1,2,\ldots,n\). An ordering of \(1,2,\ldots,n\) is the same thing as an ordering of \(1,2,\ldots,n-1\) with n inserted into one of n positions, so the number of possible orderings is n times the number of orderings of \(1,\ldots,n-1\), which is \((n-1)!\) by the inductive hypothesis. So \(|S_n|=n\times (n-1)!=n!\), completing the inductive step.

1.4.2 Cycles

Definition 1.11

  • Let \(a_0,\ldots,a_{m-1}\) be distinct elements of \(\{1,2,\ldots,n\}\). Then \((a_0,\ldots,a_{m-1})\) is the permutation in \(S_n\) such that \(a_i \mapsto a_{i+1}\) for \(0\leq i < m-1\), \(a_{m-1}\mapsto a_0\), and if \(x \neq a_1,\ldots,a_m\) then \(x \mapsto x\). Such a permutation is called an m-cycle
  • A permutation which is an m-cycle for some m is called a cycle.
  • Two cycles \((a_0,\ldots,a_{m-1})\) and \((b_0,\ldots,b_{l-1})\) are called disjoint if no \(a_i\) is equal to any \(b_j\).
Illustration of a 5-cycle. $a_0,a_1,a_2,a_3,a_4$ are shown in a circle with an arrow pointing from one to the next, then from $a_4$ back to $a_0$

Figure 1.7: Illustration of a 5-cycle. \(a_0,a_1,a_2,a_3,a_4\) are shown in a circle with an arrow pointing from one to the next, then from \(a_4\) back to \(a_0\)

Not every permutation is a cycle, e.g. \[ \begin{pmatrix} 1&2&3&4\\ 2&1&4&3 \end{pmatrix}. \] On the other hand, as we will prove in this section, any permutation can be written as a product of disjoint cycles: you can check that the permutation above is equal to \((1,2)(3,4)\). To give the proof, we need some further ideas related to permutations. First we are going to define powers of permuations in such a way that the usual exponent laws apply.

Definition 1.12 Let \(m\in\mathbb{Z}\) and \(\sigma\in S_n\). Then \[ \sigma^m = \begin{cases} \sigma \circ \cdots \circ \sigma \;\; (m \text{ times}) & m>0 \\ \id & m=0 \\ \sigma^{-1}\circ \cdots \circ \sigma^{-1} \;\; (-m \text{ times}) & m<0 \end{cases} \]

It’s slightly tedious, but you can check that for any \(a,b\in\mathbb{Z}\) we have \[ \sigma^a \sigma^b = \sigma^{a+b}.\] There is a proof of a more general result in the section of these notes on groups.

Definition 1.13 Let \(x \in \{1,2,\ldots,n\}\) and \(\sigma \in S_n\). The orbit of x under \(\sigma\), written \(\operatorname{orb}(x)\), is \[ \operatorname{orb}(x) = \{\sigma^m(x) : m \in \mathbb{Z}\} .\]

Despite appearances, \(\operatorname{orb}(x)\) is a finite set because it is a subset of \(\{1,\ldots,n\}\). We can say a little about what \(\operatorname{orb}(x)\) looks like using the following result:

Proposition 1.4 Let \(x \in \{1,\ldots,n\}\) and \(\sigma \in S_n\). Then there is a whole number \(r>0\) such that \(\sigma^r(x)=x\).
Proof. The elements \(\sigma^m(x)\) for \(m=0,1,2,\ldots\) can’t all be different, so there must exist \(i<j\) such that \(\sigma^i(x)=\sigma^j(x)\). Then \(\sigma^{-i}\sigma^i (x) = \sigma^{-i}\sigma^j (x)\), so \(x =\sigma^{j-i}(x)\) and we can take \(r=j-i\).

Finally we’re ready to describe the orbit of x:

Proposition 1.5 Let \(\sigma\in S_n\) and \(x \in \{1,2,\ldots,n\}\), and let r be the smallest strictly positive natural number such that \(\sigma^r(x)=x\). Then

  • \(\orb(x)=\{x, \sigma(x), \ldots, \sigma^{r-1}(x)\}\), and
  • all of the elements \(x,\sigma(x),\ldots,\sigma^{r-1}(x)\) are different.
Notice that we needed the proposition before this to establish that such an r exists.

Proof.

  • Let \(\sigma^a \in \orb(x)\), we have to show that it equals one of \(x, \sigma (x), \ldots, \sigma^{r-1}(x)\). To do that, write \(a=qr+b\) where b is the remainder on dividing a by r, so that \(0 \leq b < r\). Then \(\sigma^a(x)= \sigma^{qr+b}(x) = \sigma^b( \sigma^{rq}(x))\). But \(\sigma^r(x)=x\), so \(\sigma\) to the power of any multiple of r sends x to itself too. Thus \(\sigma^a(x) = \sigma^b(x) \in \{x,\sigma(x),\ldots,\sigma^{r-1}(x)\}\).
  • If \(\sigma^i(x)=\sigma^j(x)\) for some \(1\leq i<j<r\) then \(x=\sigma^{j-i}(x)\) as before, and \(0<j-i<r\) which contradicts r being the smallest strictly positive natural number with \(\sigma^r(x)=x\).

This actually gives a way of calculating orbits: if we want \(\orb(x)\) we just find \(x, \sigma(x), \sigma^2(x),\) and so on, stopping when we first get back to x. The last proposition guarantees that this list is the complete orbit of x with no repetitions.

Proposition 1.6 Let \(\sigma \in S_n\). Define a relation \(\sim\) on \(\{1,2,\ldots,n\}\) by \(x\sim y\) if and only if \(x \in \orb(y)\). Then \(\sim\) is an equivalence relation and the equivalence classes are the orbits of \(\sigma\).

Proof.

  • (R): certainly \(x \in \orb(x)\), so \(x\sim x\).
  • (S): if \(x ~y\) then \(x\in \orb(y)\), so \(x=\sigma^a(y)\) for some a, so \(\sigma^{-a}(x) = \sigma^{-a}\sigma^a(y)=y\). Therefore \(y \in \orb(x)\), and \(y\sim x\).
  • (T): if \(x\sim y\sim z\) then \(x\in \orb(y)\), so \(x=\sigma^a(y)\) for some a, and \(y \in \orb(z)\), so \(y=\sigma^b(z)\) for some b. Then \(x=\sigma^a(\sigma^b(z))=\sigma^{a+b}(z) \in \orb(z)\), so \(x\sim z\). Since \(y\sim x\) if and only if \(y \in \orb(x)\), the equivalence class \([x]\) is \(\orb(x)\).
Theorem 1.4 Every element of \(S_n\) can be written as a product of disjoint cycles.

Proof. Let \(\sigma \in S_n\) and let the distinct orbits of \(\sigma\) be \(\orb(x_1),\ldots,\orb(x_m)\). These are the equivalence classes for an equivalence relation, so every element of \(\{1,2,\ldots, n\}\) belongs to exactly one of these orbits. We also know that \[ \orb(x_i) = \{x_i, \sigma(x_i), \ldots , \sigma^{r_i-1}(x_i)\} \] where \(r_i\) is the smallest strictly positive natural number such that \(\sigma^{r_i}(x_i)=x_i\).

Let \(c_i\) be the cycle \((x_i, \sigma(x_i), \ldots, \sigma^{r_i-1}(x_i))\), so that the \(c_i\)s are disjoint cycles because the orbits of \(\sigma\) are disjoint. We will show that \[ \sigma = c_1 c_2 \cdots c_m \] To prove this we need to show that if j is any element of \(\{1,2,\ldots,n\}\) then the product of disjoint cycles on the right sends j to \(\sigma(j)\). But this is true, because in each cycle \(c_i\) every element \(\sigma^a(a_i)\) is sent to \(\sigma^{a+1}(x_i) = \sigma ( \sigma^a(a_i))\).

The theorem gives us a way of expressing a given permutation as a product of disjoint cycles: first we find the orbits, then each orbit gives rise to a cycle and the product of these cycles is equal to our original permutation.

1.4.3 Transpositions and the sign of a permutation

Definition 1.14 A transposition is a 2-cycle.
Lemma 1.2 If \(a_0, \ldots, a_{m-1}\) are distinct then \[(a_0, a_1, \ldots, a_{m-1}) = (a_0,a_1)(a_1, a_2)\cdots (a_{m-2},a_{m-1})\]

Proof. Induction on m. For \(m=2\) there is nothing to prove. For the inductive step, we can assume that \((a_0,a_1)\cdots (a_{m-2}, a_{m-1}) = (a_0,\ldots,a_{m-1})\) and we must show that if we multiply this on the right by \((a_{m-1}, a_m)\) we get \((a_0,\ldots,a_m)\).

Consider the permutation \[ (a_0,\ldots,a_{m-1})(a_{m-1},a_m).\] Every number not an \(a_i\) is sent to itself by this permutation. Every \(a_i\) for \(i \leq m-2\) is sent to \(a_{i+1}\), since it is fixed by the 2-cycle. \(a_{m-1}\) is sent to \(a_m\) by the 2-cycle and this is fixed by the m-cycle. \(a_m\) is sent to \(a_{m-1}\) by the 2-cycle and then to \(a_0\) by the m-cycle. Summarizing, \(a_i\) goes to \(a_{i+1}\) for \(i<m\) and \(a_m\) goes to \(a_0\), hence this permutation is the m+1 cycle \((a_0,\ldots,a_m)\).
Proposition 1.7 Every permutation is equal to a product of transpositions.
Proof. Let \(\sigma\) be any permutation. Theorem 1.4 says we can express \(\sigma\) as a product of disjoint cycles. The previous lemma says we can express each of these cycles as a product of transpositions. This expresses \(\sigma\) as a product of transpositions.
Definition 1.15 A permutation is even if it can be written as a product of an even number of transpositions, and odd if it can be written as an odd number of transpositions.

For example, the identity permutation \(\id = (1,2)(1,2)\) so it is even. It follows straight from the definition that an even permutation multiplied by another even permutation is even, even times odd is odd, odd times even is odd, and odd times odd is even.

It’s not clear however that a permutation couldn’t be odd and even at the same time.

Theorem 1.5 Every permutation is either odd or even, but not both.

Proof. (Sketch). First we know from the previous proposition that every permutation can be written as a product of transpositions, so the only problem is to prove that it is not possible to find two expressions for a given permutation, one using a product \(s_1 s_2 \cdots s_{2m+1}\) of an odd number of transpositions and one using a product \(t_1 t_2 \cdots t_{2l}\) of an even number of transpositions. The steps are as follows:

  • If this were the case then we would have \(\id = t_{2l}\cdots t_1 s_1 \cdots s_{2m+1}\), expressing the identity as a product of an odd number of transpositions, so it is enough to prove this impossible.
  • Observe that any transposition \((i,j)\) can be written \[ (j-1,j)\cdots (i+2,i+3)(i+1,i+2) \times (i,i+1) \times (i+1,i+2)(i+2,i+3)\cdots (j-1,j)\] where we have assumed without loss of generality that \(i<j\). This is a product of an odd number of adjacent transpositions, i.e. transpositions of the form \((k,k+1)\).
  • So it is enough to show that the identity cannot be written as a product of an odd number of adjacent transpositions.
  • Consider polynomials in the n variables \(x_1,\ldots,x_n\). If you have such a polynomial \(f(x_1,\ldots,x_n)\) and a permutation \(\sigma \in S_n\), you get a new polynomial \(\sigma(f)\) by replacing each \(x_i\) in f with \(x_{\sigma(i)}\). For example, if \(\sigma = (1,2,3)\) and \(f=x_1+x_2^2\) then \(\sigma(f)=x_2+x_3^2\). Define \[ \Delta = \prod_{1\leq i<j \leq n}(x_i-x_j)\]
  • Observe that for any k, \((k,k+1)(\Delta) = -\Delta\), and so any product of an odd number of adjacent transpositions sends \(\Delta\) to \(-\Delta\) too.
  • Get a contradiction from the fact that \(\id(\Delta) = \Delta\).

Proposition 1.8

  • The identity permutation is even.
  • An m-cycle is even if m is odd and odd if m is even.

Proof.

  • \(\id = (1,2)(1,2)\).
  • This follows from 1.2.
Definition 1.16 The sign of a permutation \(\sigma\), written \(\sgn(\sigma)\), is \[ \sgn(\sigma) = \begin{cases} \phantom{-}1 & \sigma \text{ is even} \\ -1 & \sigma \text{ is odd.} \end{cases} \]

Thus \(\sgn (a_0,\ldots,a_{m-1}) = (-1)^{m-1}\). Sign has a nice property:

Proposition 1.9 For any permutations \(\sigma\) and \(\tau\) we have \(\sgn(\sigma \tau) = \sgn(\sigma)\sgn(\tau)\).
Proof. This is just a restatement of the fact that an even permutation composed with an even permutation is even, an odd permutation composed with an odd permutation is even, and an odd permutation composed with an even permutation is odd.

This lets us find the sign of an arbitrary permutation: first express it as a product of cycles (they don’t have to be disjoint), then use this result and the fact that even length cycles are odd and odd length cycles are even.