3: The Symmetric Groups

Recall that if \(n\) is a positive integer, \([n]=\{ 1, 2, \ldots, n \}\). A permutation of \([n]\) is a one-to-one, onto function from \([n]\) to \([n]\) and \(S_n\) is the set of all permutations of \([n]\). If these terms are not familiar, it would be a good idea to take some time to study Appendix B before proceeding.

Let us discuss the different ways to specify a function from \([ n ]\) to \([ n ]\) and how to tell when we have a permutation. It is traditional (but not compulsory) to use lower case Greek letters such as \(\sigma\), \(\tau\), \(\alpha\), \(\beta\), etc., to indicate elements of \(S_n\). To be specific let \(n = 4\). We may define a function \(\sigma:[4] \to [4]\) by specifying its values at the elements \(1,2,3,\) and \(4\). For example, let’s say: \[\sigma(1) = 2 \qquad \sigma(2) = 3 \qquad \sigma(3) = 1 \qquad \sigma(4) = 4.\nonumber \] Another way to specify \(\sigma\) is by exhibiting a table which gives its value: \[\nonumber \sigma= \left ( \begin{array} {cccc} 1&2&3&4\\ 2&3&1&4 \end{array} \right ).\] We call this the two line or two row notation. The function \(\sigma\) just defined is one-to-one and onto, that is, it is a permutation of \([4]\).

For another example, let \[\nonumber \tau = \left ( \begin{array} {cccc} 1&2&3&4\\ 1&3&1&4 \end{array} \right ).\] The function \(\tau\) is not one-to-one since \(1 \ne 3\) but \(\tau(1) = \tau(3)\). This problem can always be identified by the existence of the same element more than once in the second line of the two line notation. \(\tau\) is also not onto since the element \(2\) does not appear in the second line.

Let \[\sigma= \left ( \begin{array} {cccc} 1&2&\cdots&n\\ \sigma(1)&\sigma(2)&\cdots&\sigma(n) \end{array} \right ).\] be the two line notation of an arbitrary function \(\sigma: [n] \to [n]\). Then:

1. \(\sigma\) is one-to-one if and only if no element of \([n]\) appears more than once in the second line.
2. \(\sigma\) is onto if and only if every element of \([n]\) appears in the second line at least once.

Thus \(\sigma\) is a permutation if and only if the second row is just a rearrangement or shuffling of the numbers \(1, 2, \ldots, n\).

The Composition of Two Permutations

If \(\sigma\) and \(\tau\) are elements of \(S_n\), then \(\sigma\tau\) is defined to be the composition of the functions \(\sigma\) and \(\tau\). That is, \(\sigma\tau\) is the function whose rule is given by: \[\sigma\tau(x) =\sigma(\tau(x)), \quad \mbox{ for all $x \in [n]$.}\] We sometimes call \(\sigma\tau\) simply the product of \(\sigma\) and \(\tau\). Let’s look at an example to see how this works. Let \(\sigma\) and \(\tau\) be defined as follows: \[\sigma= \left ( \begin{array} {ccc} 1&2&3\\ 2&1&3 \end{array} \right ), \quad \quad \tau = \left ( \begin{array} {ccc} 1&2&3\\ 2&3&1 \end{array} \right )\] It follows that \[\begin{array} {c c c c c c c} \sigma\tau(1) &=&\sigma(\tau(1))&=&\sigma(2)&=1 \\ \sigma\tau(2) &=&\sigma(\tau(2))&=&\sigma(3)&=3\\ \sigma\tau(3) &=&\sigma(\tau(3))&=&\sigma(1)&=2 \end{array}\] Thus we have \[\sigma\tau = \left ( \begin{array} {ccc} 1&2&3\\ 1&3&2 \end{array} \right )\] One can also find products of permutations directly from the two line notation as follows: \[\mbox{First Step:} \quad \left ( \begin{array} {ccc} 1&2&3\\ 2&1&3 \end{array} \right ) \left ( \begin{array} {ccc} 1&2&3\\ 2&3&1 \end{array} \right ) = \left ( \begin{array} {ccc} 1&2&3\\ 1&-&- \end{array} \right )\] \[\mbox{Second Step:} \quad \left ( \begin{array} {ccc} 1&2&3\\ 2&1&3 \end{array} \right ) \left ( \begin{array} {ccc} 1&2&3\\ 2&3&1 \end{array} \right ) = \left ( \begin{array} {ccc} 1&2&3\\ 1&3&- \end{array} \right )\] \[\mbox{Third Step:} \quad \left ( \begin{array} {ccc} 1&2&3\\ 2&1&3 \end{array} \right ) \left ( \begin{array} {ccc} 1&2&3\\ 2&3&1 \end{array} \right ) = \left ( \begin{array} {ccc} 1&2&3\\ 1&3&2 \end{array} \right )\]

Problem 3.1 Compute the following products in \(S_4\):

\[(1) \quad \left ( \begin{array} {cccc} 1&2&3&4\\ 4&3&2&1 \end{array} \right ) \left ( \begin{array} {cccc} 1&2&3&4\\1&2&3&4 \end{array} \right )\] \[(2) \quad \left ( \begin{array} {cccc} 1&2&3&4\\1&2&3&4 \end{array} \right ) \left ( \begin{array} {cccc} 1&2&3&4\\ 4&3&2&1 \end{array} \right )\] \[(3) \quad \left ( \begin{array} {cccc} 1&2&3&4\\ 4&3&2&1 \end{array} \right ) \left ( \begin{array} {cccc} 1&2&3&4\\ 4&3&2&1 \end{array} \right )\] \[(4) \quad \left ( \begin{array} {cccc} 1&2&3&4\\ 1&4&3&2 \end{array} \right ) \left ( \begin{array} {cccc} 1&2&3&4\\ 4&1&2&3 \end{array} \right )\]

Whenever we need to prove two functions are equal, we require the following definition:

Definition 3.1:

If \(\sigma:A \to B\) and \(\tau:A\to B\) are functions then \(\sigma= \tau\) if and only if \[\sigma(x)=\tau(x), \quad \mbox{for all $x \in A$}.\] In particular, if \(\sigma\) and \(\tau\) are in \(S_n\) then \(\sigma=\tau\) if and only if \[\sigma(x)=\tau(x), \quad \mbox{for all $x \in [n]$}.\]

The identity of \(S_n\)

The identity of \(S_n\) is the so-called identity function \[\iota:[n] \to [n].\] which is defined by the rule: \[\iota(x) = x, \quad \mbox{ for all $x \in [n]$.}\] In the two line notation \(\iota\) is described by \[\iota = \left ( \begin{array} {cccc} 1&2&\cdots&n\\ 1&2&\cdots&n \end{array} \right )\] The function \(\iota\) is clearly one-to-one and onto and satisfies \[\iota \sigma= \sigma\quad \mbox{and } \quad \sigma\iota = \sigma, \qquad \mbox{ for all $\sigma\in S_n$}.\] So \(\iota\) is the identity of \(S_n\) with respect to the binary operation of composition.

The inverse of an element \(\sigma \in S_n\):

If \(\sigma\in S_n\), then by definition \(\sigma:[n] \to [n]\) is one-to-one and onto. Hence the rule \[\sigma^{-1}(y) = x \quad \mbox{ if and only if } \quad \sigma(x) = y\] defines a function \(\sigma^{-1}: [n] \to [n]\). The function \(\sigma^{-1}\) is also one-to-one and onto (check this!) and satisfies \[\sigma\sigma^{-1}= \iota \qquad \mbox{ and } \qquad \sigma^{-1}\sigma= \iota,\] so it is the inverse of \(\sigma\) in the group sense also.

In terms of the two line description of a permutation, if \[\sigma= \left ( \begin{array} {ccc} \cdots&x&\cdots\\ \cdots&y&\cdots \end{array} \right)\] then \[\sigma^{-1} = \left ( \begin{array} {ccc} \cdots&y&\cdots\\ \cdots&x&\cdots \end{array} \right)\]

The inverse of a permutation in the two line notation may be obtained by interchanging the two lines and then reordering the columns so that the numbers on the top line are in numerical order. Here’s an example: \[\sigma= \left ( \begin{array} {ccc} 1&2&3\\ 2&3&1 \end{array} \right )\] Interchanging the two lines we have: \[\left ( \begin{array} {ccc} 2&3&1 \\ 1&2&3 \end{array} \right ).\] Reordering the columns we obtain \[\sigma^{-1} = \left ( \begin{array} {ccc} 1&2&3 \\ 3&1&2 \end{array} \right ).\]

Problem 3.2 Find the inverses of each of the following permutations in two line notation. Check in each case that \(\sigma\sigma^{-1} = \iota\) and \(\sigma^{-1}\sigma= \iota\).

\({\displaystyle \sigma= \left ( \begin{array} {cccc} 1&2&3&4\\ 2&3&1&4 \end{array} \right )}\)

\({\displaystyle \sigma= \left ( \begin{array} {ccccc} 1&2&3&4&5\\ 2&3&4&5&1 \end{array} \right )}\)

Theorem \(\PageIndex{1}\)

For any three functions \[\alpha:A \to B, \quad \beta: B \to C, \quad \gamma: C \to D\] we have \[(\gamma \beta)\alpha = \gamma(\beta \alpha).\]

Proof Let \(x \in A\). Then \[(\gamma \beta)\alpha(x)=\gamma \beta(\alpha(x)) = \gamma(\beta(\alpha(x))).\] and \[\gamma (\beta\alpha)(x)=\gamma ( \beta \alpha(x) ) = \gamma(\beta(\alpha(x))).\] It follows that \[(\gamma \beta) \alpha(x) = \gamma (\beta \alpha)(x) \quad \mbox{ for all $x \in A$}.\] Hence \((\gamma \beta)\alpha = \gamma(\beta \alpha)\).

Corollary 3.2 The binary operation of composition on \(S_n\) is associative.

With this corollary, we complete the proof that \(S_n\) under the binary operation of composition is a group.

The Cycle Diagram of a Permutation

An important way to visualize an element \(\sigma\) of \(S_n\) is as follows. Arrange \(n\) dots in the plane. Number the dots 1 through \(n\). For all \(i \in [n]\), if \(\sigma(i) = j\) draw an arrow from dot number \(i\) to dot number \(j\). We call this picture the cycle diagram of \(\sigma\). To get a nice picture, it is best to use the following technique for drawing the diagram.

1. Draw a dot and number it 1. Let \(i_1 = \sigma(1)\). If \(i_1 \ne 1\) draw another dot and label it \(i_1\).
2. Draw an arrow from dot 1 to dot \(i_1\). (Note that \(i_1=1\) is possible.)
3. Assume that dots numbered \(1, i_1, i_2, \ldots, i_k\) have been drawn. Consider two cases:

   (i)

   There is an arrow leaving every dot drawn so far. In this case let \(i_{k+1}\) be the smallest number in \([n]\) not yet labeling a dot. If there are no such then stop, you have completed the diagram, otherwise draw a new dot and label it \(i_{k+1}\)

   (ii)

   There is a dot numbered \(j\) with no arrow leaving it. In this case let \(i_{k+1} = \sigma(j)\). If there is no dot labeled \(i_{k+1}\) draw a new dot and label it \(i_{k+1}\). Draw an arrow from dot \(j\) to dot \(i_{k+1}\).

4. Now repeat step 3 with \(k+1\) replacing \(k\).

Example 3.1: The cycle diagram of the following permutation is given in Figure 3.1. \[\alpha = \left ( \begin{array} {ccccccccccccccc} 1&2&3&4&5&6&7&8&9&10&11&12&13&14&15 \\ 13&11&7&6&5&4&3&10&2&12&14&1&15&9&8 \end{array} \right ).\]

Notice that the diagram consists of five “cycles”: one “6-cycle”, one “4-cycle”, two “2-cycles” and one “1-cycle”. Every cycle diagram will look something like this. That’s why we call it the cycle diagram.

[diagram goes here]

The cycle diagram of \(\alpha\) from Exercise 3.1

Problem 3.3 Draw the cycle diagrams for all 24 elements of \(S_4\). You will need a systematic way to list the elements \(S_4\) to make sure you have not missed any.

We now give a more precise definition of a “cycle”.

Definition 3.2:

Let \(i_1, i_2, \ldots, i_k\) be a list of \(k\) distinct elements from \([n]\). Define a permuation \(\sigma\) in \(S_n\) as follows: \[\begin{array} {rcl} \sigma(i_1) &=& i_2 \\ \sigma(i_2) &=& i_3 \\ \sigma(i_3) &=& i_4 \\ \vdots & \vdots & \vdots \\ \sigma(i_{k-1}) & =& i_k \\ \sigma(i_k)& =& i_1 \end{array}\] and if \(x \notin \{ i_1, i_2, \ldots, i_k \}\) then \[\sigma(x) \ = \ x\] Such a permutation is called a cycle or a \(k\)-cycle and is denoted by \[(i_1 \ i_2 \ \cdots \ i_k).\] If \(k=1\) then the cycle \(\sigma=(i_1)\) is just the identity function, i.e., \(\sigma= \iota\).

For example, let \(\sigma\) be the 3-cycle defined by \(\sigma= ( 3 \ 2 \ 1)\). \(\sigma\) may be considered as an element of \(S_3\) in which case in two line notation we have \[\sigma= \left ( \begin{array} {ccc} 1&2&3\\ 3&1&2 \end{array} \right ).\] Notice that according to the definition if \(x \notin \{ 3, 2, 1\}\) then \(\sigma(x) = x\). So we could also consider \((3 \ 2 \ 1)\) as an element of \(S_4\). In which case we would have: \[\sigma= \left ( \begin{array} {cccc} 1&2&3&4\\ 3&1&2&4 \end{array} \right ).\] Or we could consider \((3 \ 2 \ 1)\) as an element of \(S_5\). In which case we would have: \[\sigma= \left ( \begin{array} {ccccc} 1&2&3&4&5\\ 3&1&2&4&5 \end{array} \right ).\] Similarly, \((3 \ 2 \ 1)\) could be an element of \(S_n\) for any \(n \ge 3\). Note also that we could specify the same permutation by any of the following \[\sigma= ( 3 \ 2 \ 1), \quad \sigma= ( 2 \ 1 \ 3), \quad \sigma= ( 1 \ 3 \ 2).\] In this case, there are three numbers 1, 2, 3 in the cycle, and we can begin the cycle with any one of these. In general, there are \(k\) different ways to write a \(k\)-cycle. One can start with any number in the cycle.

Problem 3.4 Below are listed 5 different cycles in \(S_5\).
(a) Describe each of the given cycles in two line notation.
(b) Draw the cycle diagram of each cycle.

1. (4)
2. (3 4)
3. (4 1 5)
4. (1 3 5 4)
5. (1 3 5 4 2)

Definition 3.3:

Two cycles \((i_1 \ i_2 \ \cdots \ i_k)\) and \((j_1 \ j_2 \ \cdots \ j_{\ell})\) are said to be disjoint if the sets \(\{i_1, i_2, \ldots, i_k\}\) and \(\{j_1, j_2, \ldots, j_{\ell}\}\) are disjoint.

So, for example, the cycles \((1 \ 2 \ 3)\) and \((4 \ 5 \ 8)\) are disjoint, but the cycles \(( 1 \ 2 \ 3)\) and \((4 \ 2 \ 8)\) are not disjoint.

Theorem \(\PageIndex{3}\)

If \(\sigma\) and \(\tau\) are disjoint cycles, then \(\sigma\tau = \tau\sigma\).

Proof Let \(\sigma= (a_1 \cdots a_k)\) and \(\tau = (b_1 \cdots b_{\ell})\). Let \(\{c_1, \cdots, c_m \}\) be the elements of \([n]\) that are in neither \(\{a_1, \dots, a_k \}\) nor \(\{ b_1, \cdots, b_{\ell} \}\). Thus \[[n] = \{a_1, \dots, a_k \} \cup \{ b_1, \cdots, b_{\ell} \} \cup \{c_1, \cdots, c_m \}.\] We want to show \(\sigma\tau(x) = \tau \sigma(x)\) for all \(x \in [n]\). To do this we consider first the case \(x=a_i\) for some \(i\). Then \(a_i \notin \{ b_1, \cdots , b_{\ell} \}\) so \(\tau(a_i) = a_i\). Also \(\sigma(a_i) = a_j\), where \(j=i+1\) or \(j=1\) if \(i=k\). So also \(\tau(a_j) =a_j\). Thus \[\sigma\tau(a_i) = \sigma(a_i) = a_j = \tau(a_j) = \tau(\sigma(a_i) = \tau\sigma(a_i).\] Thus, \(\sigma\tau(a_i) = \tau\sigma(a_i)\). It is left to the reader to show that \(\sigma\tau(x) = \tau\sigma(x)\) if \(x=b_i\) or \(x=c_i\), which will complete the proof.

Problem 3.5 Show by example that if two cycles are not disjoint they need not commute.

Theorem \(\PageIndex{4}\)

Every element \(\sigma\in S_n\), \(n \ge 2\), can be written as a product \[\label{eq3.1} \sigma= \sigma_1 \sigma_2 \cdots \sigma_m\] where \(\sigma_1, \sigma_2, \ldots ,\sigma_m\) are pairwise disjoint cycles, that is, for \(i \ne j\), \(\sigma_i\) and \(\sigma_j\) are disjoint. If all 1-cycles of \(\sigma\) are included, the factors are unique except for the order. \(\blacksquare\)

The factorization (3.41) is called the disjoint cycle decomposition of \(\sigma\).

To save time we omit a formal proof of this theorem. The process of finding the disjoint cycle decomposition of a permutation is quite similar to finding the cycle diagram of a permutation. Consider, for example, the permutation \(\alpha \in S_{15}\) \[\alpha = \left ( \begin{array} {ccccccccccccccc} 1&2&3&4&5&6&7&8&9&10&11&12&13&14&15 \\ 13&11&7&6&5&4&3&10&2&12&14&1&15&9&8 \end{array} \right ).\] The disjoint cycle decomposition of \(\alpha\) is \[\alpha = (1 \ 13 \ 15 \ 8 \ 10 \ 12)(2 \ 11 \ 14 \ 9)(3 \ 7)(4 \ 6) ( 5).\] Compare this with the cycle diagram given for this same permutation on page . To obtain this, one starts a cycle with 1, since \(\alpha(1) = 13\) we have the partial cycle \((1 \ 13\). Next, we observe that \(\alpha(13) = 15\). This gives the partial cycle \(( 1 \ 13 \ 15\). We continue in this way till we obtain the cycle \((1 \ 13 \ 15 \ 8 \ 10 \ 12)\). Then we pick the smallest number in \([15]\) not used so far, namely, 2. We start a new cycle with 2: Noting that \(\alpha(2) = 11\) we have the partial cycle \((2 \ 11\). Continuing we obtain the cycle \((2 \ 11 \ 14 \ 9)\). And we continue in this way till all the elements of \([15]\) are in some cycle.

Problem 3.6 Find the disjoint cycle decomposition of the following permutations in \(S_{6}\):

\( \sigma= \left ( \begin{array} {cccccc} 1&2&3&4&5&6\\ 2&3&4&1&6&5 \end{array} \right) \)

\( \sigma= \left ( \begin{array} {ccccccc} 1&2&3&4&5&6\\ 3&2&4&6&5&1 \end{array} \right )\)

\( \sigma= \left( \begin{array} {ccccccc} 1&2&3&4&5&6\\ 1&2&5&4&3&6 \end{array} \right ) \)

Problem 3.7 Find the disjoint cycle decomposition of the following permutations in \(S_{6}\): [Each permutation is given as a product of cycles. Try to do this without converting the cycle notation to the two line notation.]

(1) \((1 \ 2 \ 3)(2 \ 4 \ 5)\)
(2) \((3 \ 4 \ 5 \ 1 \ 2)( 4 \ 5 \ 6) (1 \ 2 \ 3)\)
(3) \((1 \ 3)( 1 \ 2)\)
(4) \((1 \ 4)(1 \ 3)( 1 \ 2)\)

Problem 3.8 (a) Verify that if \(a,b,c,d,e\) are distinct elements of \([n]\) then each of the following cycles can be written as a product of 2-cycles: [Hint: look at (3) and (4) in Problem 3.7.] (b) Verify that the inverse of each of these cycles is a cycle of the same size.

(1) (a b c).
(2) (a b c d)
(3) (a b c d e).

Definition 3.4:

An element of \(S_n\) is called a transposition if and only if it is a 2-cycle.

Note that the transposition \((i \ j)\) interchanges \(i\) and \(j\) and leaves the other elements of \([n]\) fixed. It transposes \(i\) and \(j\).

Definition 3.5

An integer \(n\) is even if \(n=2k\) for some integer \(k\). It is odd if \(n=2k+1\) for some integer \(k\). The parity of an integer is the property of being even or odd. Two integers have the same parity if they are both even or if they are both odd. They have different parity if one is even and the other is odd.

Theorem \(\PageIndex{4}\)

Every element of \(S_n\) can be written as a product of transpositions. The factors of such a product are not unique, however, if \(\sigma\in S_n\) can be written as a product of \(k\) transpositions and if the same \(\sigma\) can also be written as a product of \(\ell\) transpositions, then \(k\) and \(\ell\) have the same parity. \(\blacksquare\)

The first part of this theorem is easy. Generalizing Problem 3.7, we see that every cycle can be written as a product of transpositions as follows: \[(i_1 \ i_2 \ i_3 \ \cdots i_k) = (i_1 \ i_k) \cdots (i_1 \ i_3) (i_1 \ i_2).\] Then, since each permutation is a product of cycles, we can obtain each permutation as a product of transpositions. The second part is more difficult to prove and, in the interest of time, we omit the proof. A nice proof may be found in Fraleigh (, page 108.)

Problem 3.9 Write the permutation \(\alpha\) on page as a product of transpositions. Do it in more than one way. How many transpositions are in each of your products?

Problem 3.10 Give the disjoint cycle decomposition of each of the 6 elements of \(S_3\). Also write each element of \(S_3\) as a product of transpositions.

Definition 3.6:

A permutation is even if it is a product of an even number of transpositions and is odd if it is a product of an odd number of transpositions. We define the function \(\mathrm{sign}: S_n \to \{ 1,-1 \}\) by \[\mathrm{sign}(\sigma) = \left \{ \begin{array}{r l} 1 & \mbox{if $\sigma$ is even} \\ -1 & \mbox{if $\sigma$ is odd} \end{array} \right.\] If \(n=1\) then there are no transpositions. In this case to be complete we define the identity permutation \(\iota\) to be even.

Problem 3.11 Show that the function \(\mathrm{sign}\) satisfies \[\mathrm{sign}(\sigma\tau) = \mathrm{sign}(\sigma)\mathrm{sign}(\tau)\] for all \(\sigma\) and \(\tau\) in \(S_n\).

Remark

Let \(A=[a_{i j}]\) be an \(n \times n\) matrix. The determinant of \(A\) may be defined by the sum \[\det (A) = \sum_{\sigma \in S_n} \mathrm{sign}(\sigma) a_{1 \sigma(1)} a_{2 \sigma(2)} \cdots a_{n \sigma(n)}.\] For example, if \(n=2\) we have only two permutations \(\iota\) and \((1 \ 2)\). Since \(\mathrm{sign}(\iota) = 1\) and \(\mathrm{sign}((1 \ 2)) = -1\) we obtain \[\det(A) = a_{1 1}a_{2 2} - a_{ 1 2}a_{2 1}.\]

Problem 3.12 Find the sign of each element of \(S_3\) and use this information to write out the formula for \(\det (A)\) when \(n = 3\). (Note that in this case the determinant is a sum of 6 terms.)

Problem 3.13 If \(n=10\) how many terms are in the above formula for the determinant?

Definition 3.7

If \((G,*)\) is a group, the number of elements in \(G\) is called the order of \(G\). We use \(\vert G\vert\) to denote the order of \(G\).

Note that \(\vert G\vert\) may be finite or infinite. If it is finite \(\vert G\vert=n\) for some positive integer \(n\). An interesting but difficult problem is that of determining all groups of a fixed order \(n\). For small \(n\) this can be done as we shall see, but there seems to be no hope of answering the question for all values of \(n\) in spite of the efforts of many mathematicians who specialize in the study of finite groups.

Problem 3.14 Find \(\vert GL(2,\mathbb{Z}_2) \vert\) and \(\vert M_2(\mathbb{Z}_2) \vert\).

Theorem \(\PageIndex{6}\)

\(\vert S_n \vert = n!\) for all \(n \ge 1\).

Proof Let \(n\) be any positive integer. Elements of \(S_n\) have the form

\[\left ( \begin{array} {ccccc} 1&2&3&\dots&n \\ a_1&a_2&a_3&\dots &a_n \end{array} \right)\] where \(a_1, a_2, \dots , a_n\) is any rearrangement of the numbers \(1,2, \dots, n\). So the problem is how many ways can we select the \(a_1, a_2, \dots , a_n\)? Note that there are \(n\) ways to select \(a_1\). Once a choice is made for \(a_1\), there are \(n-1\) remaining possibilities for \(a_2\). Thus, there are altogether \(n(n-1)\) ways to select \(a_1a_2\). Then, for each choice of \(a_1a_2\), there are \(n-2\) remaining possibilities for \(a_3\). Thus, there are \(n(n-1)(n-2)\) ways to select \(a_1a_2a_3\). Continuing in this way, we see that there are \[n(n-1)(n-2)\cdots2\cdot 1 = n!\] ways to choose \(a_1, a_2, \dots , a_n\). \(\blacksquare\)

Problem 3.15 Show that the inverse of a \(k\)-cycle is also an \(k\)-cycle. Hint: Show that if \(a_1,a_2, \dots, a_k\) are distinct elements of \([n]\) then \[(a_1 \ a_2)^{-1} = (a_2 \ a_1)\] \[(a_1 \ a_2 \ a_3)^{-1} = (a_3 \ a_2\ a_1)\] \[(a_1 \ a_2 \ a_3 \ a_4)^{-1} =(a_4 \ a_3 \ a_2 \ a_1)\] and more generally \[(a_1 \ a_2 \ \cdots \ a_k)^{-1} =(a_k \ \cdots \ a_2 \ a_1)\] Hint: Let \(\sigma = (a_1 \ a_2 \ \cdots \ a_k)\) and \(\tau = (a_k \ \cdots \ a_2 \ a_1)\). Show that \(\tau (\sigma(a_i)) = a_i\) for all \(i\) by considering three cases: \(i \notin \{1,2,\dots, k\}\), \(i \in \{1,2,\dots, k-1\}\) and \(i=k\).

Problem 3.16 Show that if \(\sigma\) is a \(k\)-cycle then \(\mathrm{sign}(\sigma) =1\) if \(k\) is odd and \(\mathrm{sign}(\sigma) = -1\) if \(k\) is even.

Problem 3.17 [Challenge Problem] For \(\sigma \in S_n\) prove that \[\begin{aligned} \sigma \mbox{ is even } &\Longleftrightarrow& \prod_{i<k} \frac {\sigma(k) -\sigma (i)}{k-i} = 1 \\ \qquad \sigma \mbox{ is odd } \; \; &\Longleftrightarrow& \prod_{i<k} \frac {\sigma(k) -\sigma (i)}{k-i} = - 1\end{aligned}\]