§ 5 Cycle Notation

Definition 5.1 Suppose we have a group action

G \to \mathrm{Aut}_{\text{set}}

on a set $X$ . Fix $g \in G$ . We call the action

\langle g \rangle \to G \to \mathrm{Aut}_{\text{set}}

the action of $g$ on $X$ .

Here $\langle g \rangle \to G$ is a group homomorphism because the inclusion map of a subgroup is a group homomorphism. The map $\langle g \rangle \to \mathrm{Aut}_{\text{set}}$ is a group homomorphism because the composition of two group homomorphisms is again a group homomorphism.

Essentially, the action of $g$ on $X$ can be expressed using cycle notation by decomposing $g$ into cycles, where each cycle corresponds to an orbit of the action of $g$ on $X$ .

§ 5.1 Cycles

Definition 5.2 If $\sigma \in S_n$ , and the action of $\sigma$ on $\underline{n}$ has at most one orbit of size $\geqslant 2$ , then $\sigma$ is called a cycle.

Example 5.1

$\sigma=1_{S_n}$ has only orbits of size $1$ , so $1_{S_n}$ is a cycle.
Let $\tau:\underline{4}\to\underline{4}$ be defined by

\begin{aligned} 1 &\mapsto 2\\ 2 &\mapsto 1\\ 3 &\mapsto 4\\ 4 &\mapsto 3 \end{aligned}

which we may draw as

This is not a cycle because it has two orbits of size $\geqslant2$ : ${1,2}$ and ${3,4}$ .

Let $\tau:\underline{5}\to\underline{5}$ be defined by

\begin{aligned} 1 &\mapsto 1\\ 2 &\mapsto 2\\ 3 &\mapsto 5\\ 4 &\mapsto 3\\ 5 &\mapsto 4 \end{aligned}

which may be drawn as

This is a cycle.

Definition 5.3 If $\sigma\in S_n$ is a cycle, we use $\underline{\sigma}\subset\underline{n}$ to denote the orbit of size $\geqslant2$ . For $\sigma=1_G$ , we define

\underline{1_G}:=\varnothing.

§ 5.2 Disjoint Cycles

Example 5.2

$\underline{\sigma}$ is a subset, so the order of its elements does not matter. In particular, it is not a set together with a choice of ordering.

Definition 5.4 If $\sigma,\tau\in S_n$ are cycles, we say that $\sigma$ and $\tau$ are disjoint cycles if and only if $\underline{\sigma}$ and $\underline{\tau}$ are disjoint.

Example 5.3

$1_G$ is disjoint from every cycle.
and are not disjoint because ${1,2}$ and ${2,3}$ intersect.
and are disjoint.

Proposition 5.1 Disjoint cycles in $S_n$ commute.

Proof: Let $\sigma$ and $\tau$ be disjoint cycles and take $k\in\underline{n}={1,2,\ldots,n}$ . Then

\begin{aligned} (\sigma \circ \tau)(k) &= \begin{cases} \sigma(k) & \text{if } k \notin \underline{\tau}\\ \tau(k) & \text{if } k \in \underline{\tau} \end{cases}\\ &= \begin{cases} \sigma(k) & \text{if } k \in \underline{\sigma}\\ k & \text{if } k \notin \underline{\sigma}, \underline{\tau}\\ \tau(k) & \text{if } k \in \underline{\tau} \end{cases}. \end{aligned}

This follows because

\begin{align*} k \notin \underline{\tau} &\Rightarrow \tau(k)=k\\ &\Rightarrow \sigma(\tau(k))=\sigma(k),\\ k \in \underline{\tau} &\Rightarrow \tau(k)\in\underline{\tau} \tag*{definition of an orbit}\\ &\Rightarrow \tau(k)\notin\underline{\sigma} \tag*{definition of disjointness}\\ &\Rightarrow \sigma(\tau(k))=\tau(k). \end{align*}

On the other hand,

\begin{aligned} (\tau \circ \sigma)(k) &= \begin{cases} \tau(k) & \text{if } k \notin \underline{\sigma}\\ \sigma(k) & \text{if } k \in \underline{\sigma} \end{cases}\\ &= \begin{cases} \tau(k) & \text{if } k \in \underline{\tau}\\ k & \text{if } k \notin \underline{\sigma}, \underline{\tau}\\ \sigma(k) & \text{if } k \in \underline{\sigma}. \end{cases} \end{aligned}

Therefore,

\sigma\circ\tau=\tau\circ\sigma.

~\tag*{$\square$}

§ 5.3 Cycle Notation

Definition 5.5 Let $\sigma$ be a cycle. The cycle notation of $\sigma$ is an expression

(a~\sigma(a)~\sigma^{2}(a)~\cdots~ \sigma^{|\sigma|-1}(a))

where $a\in\underline{\sigma}$ .

Example 5.4 If $\sigma\in S_5$ is as shown below:

then all of the following are cycle notations for $\sigma$ :

\begin{array}{cccc} (1~2~3~5), & (2~3~5~1), & (5~1~2~3), & (3~5~1~2). \\ a=1 & a=2 & a=5 & a=3 \end{array}

Example 5.5 If $\tau\in S_5$ is as shown below:

then

\underline{\tau}=\underline{\sigma},

but no cycle notation of $\tau$ is a cycle notation of $\sigma$ :

(1~2~5~3),\quad (2~5~3~1),\quad (5~3~1~2),\quad (3~1~2~5).

Implicitly, we identify the various cycle notations representing the same $\sigma$ .

Theorem 5.2 Every element

\sigma\in S_n

can be written as a product of disjoint cycles, uniquely up to order.

Proof: For $\sigma\in S_n$ , let ${\mathcal{O}_a}$ be the set of orbits of the action of $\sigma$ on $\underline{n}$ .

For each

\mathcal{O}_a\in\underline{n}/\langle\sigma\rangle,

choose $a\in\mathcal{O}_a$ and define

\sigma_a = (a~\sigma(a)~\cdots~ \sigma^{|\mathcal{O}_a|-1}(a))

as a cycle.

Then, by definition,

\sigma = \prod_{\mathcal{O}_a}\sigma_a

because

\prod_{\mathcal{O}_a}\sigma_a(k)=\sigma(k).

Moreover, when we write

\prod_{\mathcal{O}_a}\sigma_a = \sigma_a\cdot\sigma_b\cdots\sigma_z

without specifying an order, this is justified because every pair $\sigma_a,\sigma_b$ is disjoint, since distinct orbits are disjoint. Therefore these cycles commute, and the order does not matter.

For uniqueness, suppose someone else writes

\sigma = \prod\tau_i = \tau_1\cdot\tau_2\cdots\tau_k

where ${\tau_i}$ is a collection of disjoint cycles.

Notice that

\{\tau_i\} = \underline{n}/\langle\sigma\rangle.

Thus, for each $i$ , there exists a unique $\sigma_a$ such that

\underline{\sigma_a} = \underline{\tau_i}.

Write

\tau_i = (b_0~b_1~\cdots~b_{|\tau_i|-1}).

Then

\sigma(b_i)=b_{i+1},

which proves the result.

~\tag*{$\square$}

Example 5.6 Let $\sigma\in S_8$ be defined as follows:

Then

\begin{aligned} \sigma &= (7~8~4)\circ(1~2~6)\circ(3~5)\\ &= (1~2~6)(7~8~4)(3~5)\\ &= (1~2~6)(3~5)(7~8~4) \quad\text{etc.} \end{aligned}

We may regard $(1~2~6)$ both as a cycle in $S_8$ and as its cycle notation. The element $(1~2~6)\in S_8$ is represented by

In the second equality, we omit the composition symbol “ $\circ$ ” for brevity.

Definition 5.6 For $\sigma\in S_n$ , a cycle notation for $\sigma$ is an expression

\sigma=\sigma_1\cdots\sigma_k

where each $\sigma_i$ is a cycle, and every pair $\sigma_i,\sigma_j$ with $i\neq j$ is disjoint.

Example 5.7 If $\sigma\in S_5$ is as shown below:

then the following are cycle notations for $\sigma$ :

\begin{array}{cc} (1~2~4)(3~5) & (3~5)(1~2~4) \\ (1~2~4)(5~3) & (5~3)(1~2~4) \\ (4~1~2)(3~5) & (3~5)(4~1~2) \\ (4~1~2)(5~3) & (5~3)(4~1~2) \\ (2~4~1)(3~5) & (3~5)(2~4~1) \\ (2~4~1)(5~3) & (5~3)(2~4~1) \end{array}

All of these represent the same $\sigma$ .

Example 5.8 Let

\begin{aligned} \sigma&=(1~2)(3~4),\\ \tau&=(1~2~3). \end{aligned}

The inverse of a cycle is obtained by reading the cycle backwards:

\begin{aligned} \tau^{-1}&=(3~2~1),\\ \sigma^{-1}&=(2~1)(4~3)=\sigma. \end{aligned}

We can compute

\begin{aligned} \tau\sigma\tau^{-1} &= (1~2~3)\circ(1~2)(3~4)\circ(3~2~1)\\ &=(1~4)(2~3),\\ \sigma\tau\sigma^{-1} &= (1~2)(3~4)\circ(1~2~3)\circ(1~2)(3~4)\\ &=(3)(4~2~1)\\ &=(4~2~1). \end{aligned}

Notice that

(\text{some element})\sigma(\text{some element})^{-1}

has the same cycle shape as $\sigma$ . This will help us classify the conjugacy classes of $S_n$ .

§ 5.4 Conjugacy Classes in $S_n$

Cycle notation gives us some beautiful results.

Proposition 5.3

(1) Suppose $\sigma\in S_n$ is a cycle, so

\sigma=(a_1~\cdots~a_k),

where

a_{i+1}=\sigma(a_i).

Then

\sigma^{-1} = (a_k~\cdots~a_1).

That is,

\sigma^{-1} = (b_1~\cdots~b_k),

where $b_i=\sigma(b_{i+1})$ and $b_k=a_1$ .

(2) More generally, if

\sigma = \sigma_1\sigma_2\cdots\sigma_k

where the $\sigma_i$ are disjoint cycles, then

\sigma^{-1} = \sigma_1^{-1}\cdots\sigma_k^{-1}.

(3) Let $\sigma,\tau\in S_n$ and $a,b\in\underline{n}$ . If

\sigma(a)=b,

then $\tau\sigma\tau^{-1}$ maps $\tau(a)$ to $\tau(b)$ .

Proof:

(1) We need to prove that for every $b\in\underline{n}$ ,

(a_k~\cdots~a_1) \circ (a_1~\cdots~a_k): b\mapsto b

and

(a_1~\cdots~a_k) \circ (a_k~\cdots~a_1): b\mapsto b.

We prove the first composition; the second is similar.

If $b\notin{a_1,\ldots,a_k}$ , then $b$ is fixed by $\sigma$ and therefore also fixed by $(a_k~\cdots~a_1)$ . Hence

(a_k~\cdots~a_1)\circ\sigma(b)=b.\textcolor{red}{\checkmark}

If $b\in{a_1,\ldots,a_k}$ , then $b=a_i$ for some $i\in{1,\ldots,k}$ . Thus

\sigma(b)=a_{i+1}

by the definition of cycle notation. Hence $(a_k~\cdots~a_1)$ maps $\sigma(b)$ back to $b$ . $\textcolor{red}{\checkmark}$

(2) In general, if $g_1,\ldots,g_l\in G$ , then

(g_1\cdots g_l)^{-1} = g_l^{-1}\cdots g_1^{-1}.

Indeed,

\begin{aligned} (g_1\cdots g_l)(g_l^{-1}\cdots g_1^{-1}) &= g_1\cdots g_{l-1} \underbrace{g_lg_l^{-1}}_{\text{cancel}} g_{l-1}^{-1}\cdots g_1^{-1}\\ &= g_1\cdots \underbrace{g_{l-1}g_{l-1}^{-1}}_{\text{cancel}} \cdots g_1^{-1}\\ &\quad\vdots\\ &=g_1g_1^{-1}\\ &=1_G. \end{aligned}

Therefore,

(\sigma_1\cdots\sigma_l)^{-1} = \sigma_l^{-1}\cdots\sigma_1^{-1}.

But disjoint cycles commute, so

\sigma_l^{-1}\cdots\sigma_1^{-1} = \sigma_1^{-1}\cdots\sigma_l^{-1}.

(3)

\begin{aligned} \tau\sigma\tau^{-1}(\tau(a)) &= \tau\sigma\tau^{-1}\circ\tau(a)\\ &= \tau\sigma(a)\\ &= \tau(b). \end{aligned}

~\tag*{$\square$}

Remark Conjugation is analogous to a change of basis. If $v_1,\ldots,v_k$ is a basis of $\mathbb{R}^k$ , then there exists an invertible matrix $T$ whose $i$ th column is $v_i$ .

If a linear transformation $A$ sends $\vec a$ to $\vec b$ , then

TAT^{-1}

sends $T\vec a$ to $T\vec b$ .

Thus the permutation $\tau$ above may be regarded as a kind of “new basis” for $\underline{n}$ .

Corollary 5.4 Let $\sigma,\sigma'\in S_n$ . If there exists $\tau\in S_n$ such that

\sigma' = \tau\sigma\tau^{-1},

then we can construct a cycle notation for $\sigma'$ from a cycle notation for $\sigma$ and from $\tau$ .

Proof: If $\sigma$ is a cycle,

\sigma=(a_1~\cdots~a_l),

then

\tau\sigma\tau^{-1} = (\tau(a_1)~\cdots~\tau(a_l)).

Part (3) of the proposition tells us that $\tau(a_i)$ is mapped by $\tau\sigma\tau^{-1}$ to $\tau(a_{i+1})$ .

It also tells us that if $\sigma(a)=a$ , then $\tau\sigma\tau^{-1}$ fixes $\tau(a)$ . Therefore, $\tau\sigma\tau^{-1}$ is another cycle whose nontrivial orbit is given by ${\tau(a_i)}$ .

If $\sigma$ is a product of disjoint cycles,

\sigma = \sigma_1\cdots\sigma_l,

then

\tau\sigma\tau^{-1} = (\tau\sigma_1\tau^{-1}) (\tau\sigma_2\tau^{-1}) \cdots (\tau\sigma_l\tau^{-1})

because conjugation is a group homomorphism.

Thus, if

\sigma = (a_1~\cdots~a_{k_1}) (a_{k_1+1}~\cdots~a_{k_1+k_2}) \cdots (a_{k_1+\cdots+k_{l-1}+1} ~\cdots~ a_{k_1+\cdots+k_l})

is a cycle notation for $\sigma$ , then

\tau\sigma\tau^{-1} = (\tau(a_1)~\cdots~\tau(a_{k_1})) (\tau(a_{k_1+1})~\cdots~\tau(a_{k_1+k_2})) \cdots (\tau(a_{k_1+\cdots+k_{l-1}+1}) ~\cdots~ \tau(a_{k_1+\cdots+k_l}))

is a cycle notation for $\tau\sigma\tau^{-1}$ .

~\tag*{$\square$}

Let $\sigma\in S_n$ .

Write $\sigma$ as a product of disjoint cycles

\sigma = \sigma_1\cdots\sigma_k

and consider

|\sigma_i|, \qquad \forall i.

These are the sizes of the orbits associated with the cycles $\sigma_i$ . In this way we obtain a collection of numbers. Since the $\sigma_i$ can be reordered, it is most convenient to regard this collection as unordered.

Example 5.9 Let

\sigma = (1~2~3)(6~9)\in S_9.

Notice that, for brevity, we do not write $(8)$ . Then the numbers associated with $\sigma$ are

3,\ 2,\ 3.

Definition 5.7 We call these numbers ${a_i}$ the cycle shape of $\sigma$ .

Example 5.10 Let

\sigma' = (3~4~5)(8~7~9)(2~6).

Then $\sigma'$ has the associated numbers

3,\ 3,\ 2.

Up to order, this is the same collection as the one associated with $\sigma$ . We say that $\sigma$ and $\sigma'$ have the same cycle shape.

Proposition 5.5 Two elements $\sigma,\sigma'\in S_n$ are conjugate, meaning that there exists $\tau$ such that

\sigma = \tau\sigma'\tau^{-1},

if and only if they have the same cycle shape.

Proof: Suppose $\sigma$ and $\sigma'$ have the same cycle shape. Then we may reorder any cycle notations for $\sigma$ and $\sigma'$ so that

\begin{aligned} \sigma &= \sigma_1\circ\cdots\circ\sigma_k,\\ \sigma' &= \sigma_1'\circ\cdots\circ\sigma_k' \end{aligned} \quad \text{are both products of disjoint cycles,}

with

|\sigma_i| = |\sigma_i'|

for every $i$ .

Choose any $i$ and a number $a$ appearing in the cycle notation of $\sigma_i$ :

\sigma_i = (\cdots~a~\cdots).

Choose any number $a'$ appearing in $\sigma_i'$ :

\sigma_i' = (\cdots~a'~\cdots).

Define a bijection by

\begin{aligned} \tau:a_i&\mapsto b_i,\\ \sigma^j(a_i) &\mapsto (\sigma')^j(b_i). \end{aligned}

Then

\begin{aligned} \tau\sigma\tau^{-1}(b) &= \tau\sigma\tau^{-1} ((\sigma')^j(b_i))\\ &= \tau\sigma(\sigma^j(a_i))\\ &= \tau(\sigma^{j+1}(a_i))\\ &= (\sigma')^{j+1}(b_i)\\ &= \sigma'(b). \end{aligned}

Hence

\tau\sigma\tau^{-1} = \sigma'.

The converse follows from the corollary above.

~\tag*{$\square$}

Example 5.11

\begin{aligned} (1~2~3)(6~9)&=\sigma,\\ (4~5)(3~6~1)&=\sigma' \end{aligned} \in S_9

have the same cycle shape.

Likewise,

\begin{aligned} \sigma &= (1~2)(3~4)(5~6~7),\\ \sigma' &= (7~8)(5~9)(1~4~2) \end{aligned} \in S_9.

Remark The cycle shape of $\sigma$ simply says that the action of $\sigma$ divides $\underline{n}$ into $l$ orbits, with the $i$ th orbit having size $k_i$ .

If $\sigma'$ also divides $\underline{n}$ into $l$ orbits, and its orbit sizes $k_i'$ can be matched with the $k_i$ of $\sigma$ , then $\sigma$ and $\sigma'$ have the same cycle shape.

Example 5.12 How do we find $\tau$ ?

Let

\begin{aligned} \sigma &= (1~2~3)(4~6)(7~8~5),\\ \sigma' &= (1~5~7)(9~3)(6~8~4). \end{aligned}

\tau\sigma\tau^{-1} = \sigma',

then we know that a cycle

(b_1~\cdots~b_k)

in the cycle notation of $\sigma'$ must be equal to

(\tau(a_1)~\cdots~\tau(a_k))

for some cycle $(a_1~\cdots~a_k)$ in the cycle decomposition of $\sigma$ .

This is not unique, but here is one way to find such a $\tau$ .

Choose a cycle and an element appearing in it. Arbitrarily, choose

4\in(4~6).

In the cycle notation of $\sigma'$ , choose a cycle of the same length as $(4~6)$ . In this case the only possible choice is $(9~3)$ , although in general there may be several choices.

Choose an element appearing in that cycle, say $9$ .

So write

Next, look at how the cycle $\sigma_i$ acts on $9$ . In this case, it does not: $9$ is a fixed point of $\sigma$ .

So choose any fixed point of $\sigma'$ . Here our only choice is $2$ .

Now find the cycle $\sigma_i$ containing $2$ . In the corresponding cycle $\sigma_i'$ , find the matching element. In this case the corresponding element is $5$ .

So the fourth step gives

$\textcircled{\small 5}$ After seeing that $(4925)$ is a cycle of $\tau$ , choose any element that has not yet been written. Arbitrarily choose $1$ .

$\textcircled{\small 6}$ Likewise, choose $3$ .

We do not write cycles of length $1$ .

§ 5.5 The Alternating Group

Definition 5.8 The alternating group $A_n$ is defined as the kernel of the map

\begin{aligned} S_n &\to GL_n(\mathbb{R}) \xrightarrow{\det} \mathbb{R}^{\times}\\ \sigma &\mapsto B_\sigma \end{aligned}

where

B_\sigma(e_i)=e_{\sigma(i)}.

That is, $A_n$ is the set of all $\sigma$ such that

\det B_\sigma=1.

Proposition 5.6 $A_n$ is a subgroup of $S_n$ consisting of all even permutations, i.e. permutations that can be written as a product of an even number of transpositions, where a transposition exchanges two elements.

Therefore,

|A_n| = \dfrac{n!}{2}.

Proposition 5.7 $A_n$ is a normal subgroup of $S_n$ .

There are three ways to prove this.

1. Kernel of the Sign Homomorphism

Proof: Define a map

\mathrm{sgn}:S_n\to\{1,-1\}

if $\sigma$ is an even permutation,

\mathrm{sgn}(\sigma)=1;

if $\sigma$ is an odd permutation,

\mathrm{sgn}(\sigma)=-1.

This is a group homomorphism because

\mathrm{sgn}(\sigma\tau) = \mathrm{sgn}(\sigma)\cdot\mathrm{sgn}(\tau).

We call this the sign homomorphism.

The kernel of a homomorphism is the set of elements that map to the identity element of the codomain. For $\mathrm{sgn}$ , the identity element is $1$ . Therefore,

\ker(\mathrm{sgn})=A_n.

The kernel of a group homomorphism is always a normal subgroup of the domain group. Therefore,

A_n\triangleleft S_n.

~\tag*{$\square$}

2. Conjugation Preserves the Parity of a Permutation

Proof: For any $\sigma,\tau\in S_n$ , conjugation preserves the cycle structure and the parity of a permutation.

If $\sigma$ is even, then its conjugate

\tau\sigma\tau^{-1}

is also even.

A subgroup $N$ is normal if it is invariant under conjugation by elements of the group:

\tau N\tau^{-1} = N \quad \text{for all }\tau\in S_n.

Since the conjugate of an even permutation is again even,

A_n\triangleleft S_n.

~\tag*{$\square$}

3. The Index of $A_n$ in $S_n$

Proof: The index of $A_n$ in $S_n$ is

[S_n:A_n] = \dfrac{|S_n|}{|A_n|} = \dfrac{n!}{n!/2} = 2.

Since every subgroup of index $2$ in a group is normal,

A_n\triangleleft S_n.

~\tag*{$\square$}

Contents

§ 5 Cycle Notation

§ 5.1 Cycles

§ 5.2 Disjoint Cycles

§ 5.3 Cycle Notation

§ 5.4 Conjugacy Classes in SnS_nSn​

§ 5.5 The Alternating Group

1. Kernel of the Sign Homomorphism

2. Conjugation Preserves the Parity of a Permutation

3. The Index of AnA_nAn​ in SnS_nSn​

§ 5.4 Conjugacy Classes in $S_n$

3. The Index of $A_n$ in $S_n$