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.)

Remark6.2.2

Throughout this course, if we are discussing a group $S_n\text{,}$ you should assume $n\in \Z^+\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.

Remark6.2.6

Given a $k$ -cycle $\sigma=(a_1 a_2\cdots a_k)\text{,}$ there are $k$ different expressions for $\sigma\text{.}$ Indeed, we have

$\begin{equation*} \sigma=(a_1 a_2\cdots a_k)=(a_2 a_3 \cdots a_k a_1)=(a_3 a_4 \cdots a_k a_1 a_2)=\cdots = (a_k a_1 \cdots a_{k-1}). \end{equation*}$

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.)

Remark6.2.9

Note that if cycles $\sigma$ and $\tau$ are disjoint, then $\sigma$ and $\tau$ commute; that is, $\sigma \tau=\tau \sigma\text{.}$

Warning6.2.10

If cycles $\sigma$ and $\tau$ are not disjoint then they may not commute. For instance, see Example 6.2.3, where $\sigma\tau \neq \tau \sigma\text{.}$

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.

Remark6.2.12

Note that if $\sigma$ in $S_n$ is written in cycle notation and the number $a\in \{1,2,\ldots, n\}$ appears nowhere in $\sigma$ 's representation, this means that $\sigma$ fixes $a\text{.}$ The only permutation that we cannot really write in cycle notation is the identity element of $S_n\text{,}$ which we henceforth denote by $e\text{.}$

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.

Warning6.2.18

Permutation $\sigma$ must be in disjoint cycle notation for the above formula to hold. For instance, let $\sigma=(12)(23)$ in $S_3\text{.}$ The transpositions $(12)$ and $(23)$ both have order $2\text{,}$ but $o(\sigma)\neq \lcm(2,2)=2\text{.}$ Rather, $o(\sigma)=3\text{,}$ since in disjoint cycle notation $\sigma$ can be written as $\sigma=(123)\text{.}$ You must write a permutation using disjoint cycle notation before attempting to use this method to compute its order!

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{.}$