#
Section6.2Symmetric groups

#####
Definition6.2.1

When \(A=\{1,2,\ldots, n\}\) (\(n\in \Z^+\)), we call \(S_A\) the *symmetric group on \(n\) letters* and denote it by \(S_n\text{.}\)

(We can, in fact, define \(S_0\text{,}\) the set of all permutations on the empty set. One can show, using the fact that a function is a relation on a Cartesian product of sets, that \(S_0\) is the trivial group. However, this will not be relevant in this text.)

It is important for us to be able to easily describe specific elements of \(S_n\text{.}\) It would be cumbersome to describe, for instance, an element of \(S_3\) by saying it swaps \(1\) and \(2\) and fixes \(3\text{;}\) imagine how much more cumbersome it could be to describe an element of, say, \(S_{100}\text{!}\) One can somewhat concisely describe a permutation \(\sigma\) of \(S_n\) by listing out the elements \(1,2,\ldots,n\) and writing the element \(\sigma(i)\) below each \(i\) for \(i=1,2,\ldots, n\text{.}\) For instance, if \(\sigma\) sends \(1\) to \(2\text{,}\) we'd write the number \(2\) below the number \(1\text{.}\) The convention is to enclose these two rows of numbers in a single set of parentheses, as in the following example.

#####
Example6.2.3

We can denote the element \(\sigma\) of \(S_3\) that swaps \(1\) and \(2\) and fixes \(3\) by

\begin{equation*}
\sigma = \begin{pmatrix}1\amp 2\amp 3\\ 2\amp 1\amp 3
\end{pmatrix},
\end{equation*}
and the element \(\tau\) of \(S_3\) that sends \(1\) to \(3\text{,}\) \(2\) to \(1\text{,}\) and \(3\) to \(2\) by

\begin{equation*}
\tau =\begin{pmatrix}1\amp 2\amp 3\\ 3\amp 1\amp 2
\end{pmatrix}.
\end{equation*}
Then

\begin{equation*}
\sigma\tau = \begin{pmatrix}1\amp 2\amp 3\\ 3\amp 2\amp 1
\end{pmatrix}
\end{equation*}
and

\begin{equation*}
\tau\sigma = \begin{pmatrix}1\amp 2\amp 3\\ 1\amp 3\amp 2
\end{pmatrix}.
\end{equation*}
But even this notation is unnecessarily cumbersome. Instead, we use *cycle notation*.

#####
Definition6.2.4

A permutation \(\sigma\) in \(S_n\) is called a *\(k\)-cycle* or a *cycle of length \(k\)* (or, less specifically, a *cycle*) if there exist distinct elements \(a_1,
a_2,\ldots, a_k\) in \(\{1,2,\ldots,n\}\) such that

\(\sigma(a_i)=a_{i+1}\) for each \(i=1,2,\ldots, k-1\text{;}\)

\(\sigma(a_k)=a_1\text{;}\)

\(\sigma(x)=x\) for every other element of \(\{1,2,\ldots, n\}\text{.}\)

We use the *cycle notation* \(\sigma = (a_1 a_2 \cdots a_k)\) to describe such a cycle. A \(2\)-cycle is often called a *transposition*.

#####
Example6.2.5

The permutation \(\tau\) in \(S_3\) that sends \(1\) to \(3\text{,}\) \(2\) to \(1\text{,}\) and \(3\) to \(2\) is a cycle. It can be denoted by \(\tau =(132)\text{.}\) Similarly, the cycle \(\rho\) in \(S_3\) swapping \(1\) and \(3\) can be denoted by \(\rho=(13)\text{.}\) On the other hand, the permutation in \(S_4\) that swaps \(1\) with \(2\) and \(3\) with \(4\) is *not* a cycle.

#####
Example6.2.7

The permutation \(\tau\) described in Example 6.2.5 can also be written as \((321)\) and as \((213)\text{.}\)

However, by convention, we usually “start” a cycle \(\sigma\) with the smallest of the numbers that \(\sigma\) doesn't fix: e.g., we'd write \(\sigma=(213)\) as \((132)\text{.}\)

#####
Definition6.2.8

Two cycles \(\sigma=(a_1 a_2 \cdots a_k)\) and \(\tau=(b_1
b_2 \cdots b_m)\) are said to be *disjoint* if \(a_i \neq
b_j\) for all \(i\) and \(j\text{.}\) Cycles \(\sigma_1\text{,}\) \(\sigma_2\text{,}\) \(\ldots\text{,}\) \(\sigma_m\) are *disjoint* if \(\sigma_i\) and \(\sigma_j\) are disjoint for each \(i \neq j\text{.}\) (Notice: this version of disjointness is what we usually refer to as *mutual* disjointness.)

Note that any permutation of \(S_n\) is a product of disjoint cycles (where by “product” we mean the permutation resulting from permutation multiplication).

#####
Definition6.2.11

Writing a permutation in *(disjoint) cycle notation* means writing it as a product of disjoint cycles, where each cycle is written in cycle notation.

#####
Example6.2.13

The permutation

\begin{equation*}
\sigma =\begin{pmatrix}1\amp 2\amp 3\amp 4\amp 5\amp 6\\ 3\amp 1\amp 2\amp 6\amp 5\amp 4
\end{pmatrix}
\end{equation*}
is the product of disjoint cycles \((132)\) and \((46)\text{,}\) so in cycle notation we have

\begin{equation*}
\sigma=(132)(46).
\end{equation*}
Note that we could also write \(\sigma\) as \((321)(46)\text{,}\) \((213)(64)\text{,}\) \((64)(132)\text{,}\) etc.

While it is true that we also have \(\sigma=(13)(23)(46)\text{,}\) this is not a disjoint cycle representation of \(\sigma\) since both \((13)\) and \((23)\) “move” the element \(3\text{.}\)

#####
Example6.2.14

In \(S_4\text{,}\) let \(\sigma=(243)\) and \(\tau=(13)(24)\text{.}\) Then \(\sigma \tau=(123)\) and \(\tau \sigma = (134).\)

#####
Example6.2.15

In \(S_9\text{,}\) let \(\sigma=(134)\text{,}\) \(\tau=(26)(17)\text{,}\) and \(\rho=(358)(12)\text{.}\) Find the following, writing your answers using disjoint cycle notation.

\(\sigma^{-1}\)

\(\sigma^{-1}\tau\sigma\)

\(\sigma^2\)

\(\sigma^3\)

\(\rho^2\)

\(\rho^{-2}\)

\(\sigma \tau\)

\(\sigma \rho\)

#####
Example6.2.16

Explicitly express all the elements of \(S_4\) in disjoint cycle notation.

#####
Theorem6.2.17

Any \(k\)-cycle has order \(k\) in \(S_n\text{.}\) More generally, if permutation \(\sigma\) can be written in disjoint cycle notation as \(\sigma=\sigma_1 \sigma_2 \cdots \sigma_m\text{,}\) then

\begin{align*}
o(\sigma)\amp =\lcm(o(\sigma_1), o(\sigma_2),\ldots, o(\sigma_m))\\
\amp =\lcm(\mathrm{length}(\sigma_1),\mathrm{length}(\sigma_2),\ldots,\mathrm{length}(\sigma_m)),
\end{align*}
where \(\lcm\) denotes the least common multiple.

#####
Example6.2.19

Find the orders of each of the elements in Example 6.2.15, including \(\sigma\text{,}\) \(\tau\text{,}\) and \(\rho\) themselves.

Explicitly list the elements of \(\langle \sigma\rangle\text{,}\) \(\langle \tau\rangle\text{,}\) and \(\langle \rho\rangle\text{.}\)