Skip to main content

Section 8.1 Pre-read

We can permute any collection of objects.

For example, we can permute the collection of numbers \(\{1, 2, 3, 4, 5\}\text{:}\)

\begin{align*} 1 \amp\mapsto 3, \amp 3 \amp\mapsto 5, \amp 5 \amp\mapsto 1, \amp 2 \amp\mapsto 4, \amp 4 \amp\mapsto 2 \text{.} \end{align*}

In cycle notation, this permutation can be expressed as

\begin{equation*} \threecycle{1}{3}{5} \twocycle{2}{4} \text{.} \end{equation*}

We can permute the first five letters of the alphabet:

\begin{align*} \letter{a} \amp\mapsto \letter{c}, \amp \letter{c} \amp\mapsto \letter{e}, \amp \letter{e} \amp\mapsto \letter{a}, \amp \letter{b} \amp\mapsto \letter{d}, \amp \letter{d} \amp\mapsto \letter{b} \text{.} \end{align*}

We can also use cycle notation to represent this permutation as

\begin{equation*} \threecycle{\letter{a}}{\letter{c}}{\letter{e}} \twocycle{\letter{b}}{\letter{d}} \text{.} \end{equation*}

We can also permute the first five letters of the Greek alphabet:

\begin{align*} \alpha \amp\mapsto \gamma, \amp \gamma \amp\mapsto \epsilon, \amp \epsilon \amp\mapsto \alpha, \amp \beta \amp\mapsto \delta, \amp \delta \amp\mapsto \beta \text{.} \end{align*}

We can also use cycle notation to represent this permutation as

\begin{equation*} \threecycle{\alpha}{\gamma}{\epsilon} \twocycle{\beta}{\delta} \text{.} \end{equation*}

And so on.

Remark 8.1.2.

We will consider a permutation as a function, so that the correspondence is unidirectional instead of bidirectional. (But we can always recover the bidirectional nature of a bijective correspondence using the inverse function.)

Warning 8.1.3.

A permutation is (usually) not an isomorphism, as

  • the collection being permuted is not necessarily a group, and

  • even if the collection being permuted is a group, there is no requirement that the permutation be Operation-preserving map.

As described at the beginning of Chapter 6 of the textbook, given a collection \(X\) we write \(S_X\) to denote the group of all permutations of \(X\text{,}\) where the group operation is function composition as usual. In the case that the collection being permuted is the \(\{1, 2, 3, \dotsc, n\} \) we write \(S_n\) instead.

In any case, when \(X\) is a finite collection containing \(n\) objects, we can obtain an isomorphism between \(S_X\) and \(S_n\) by choosing a labelling of the objects in \(X\) by the numbers \(1, 2, \dotsc, n\text{.}\)

Example 8.1.4. Converting a permutation of letters into a permutation of numbers.

Consider \(X = \{ \letter{a}, \letter{b}, \letter{c}, \letter{d}, \letter{e} \}\text{.}\) Let us relabel the elements of \(X\) as

\begin{align*} x_1 \amp = \letter{a}, \amp x_2 \amp = \letter{b}, \amp x_3 \amp = \letter{c}, \amp x_4 \amp = \letter{d}, \amp x_5 \amp = \letter{e}. \end{align*}

At the beginning of this Pre-read section, we consider the permutation

\begin{equation*} \threecycle{\letter{a}}{\letter{c}}{\letter{e}} \twocycle{\letter{b}}{\letter{d}} \end{equation*}

of \(X\text{.}\) With our relabelling, we can write this element of the group \(S_X\) as

\begin{equation*} \threecycle{x_1}{x_3}{x_5} \twocycle{x_2}{x_4} \text{,} \end{equation*}

which is clearly essentially the same as the permutation

\begin{equation*} \threecycle{1}{3}{5} \twocycle{2}{4} \end{equation*}

in the group \(S_5\text{.}\)

Remark 8.1.5.

What is really going on in Example 8.1.4 is that there are two bijective correspondences involved. First, the relabelling sets up a bijective correspondence between the collection of letters \(X\) and the collection of numbers \(\{1,2,3,4,5\}\text{.}\) Then the isomorphism (a special kind of bijective correspondence) between \(S_X\) and \(S_5\) is obtained by using the relabelling bijective correspondence to reinterpret a permutation of letters (i.e. a group element of \(S_X\)) as a permutation of numbers (i.e. a group element of \(S_5\)).

Warning 8.1.6.

This isomorphic relationship \(S_X \leftrightarrow S_n\) doesn't work if \(X\) is not finite.

Example 8.1.7. A permutation of an infinite collection.

The function \(\funcdef{f}{\Z}{\Z}\) defined by \(f(m) = -m\) is a bijective correspondence of \(\Z\) with itself that matches every integer with its negative. (And so \(0\) is matched with itself.) But there is no way to interpret this permutation of \(\Z\) as a product of disjoint cycles in some \(S_n\) permutation group, no matter how large \(n\) is taken to be.