If $X$ is a set, the set $\operatorname{Bij} (X)$ of bijective mappings $X \longrightarrow X$ has a group structure, in which the multiplication is composition. Thus the identity map $1_X : X \longrightarrow X$ (defined by $1_X (x) = x$) is the unit element in the group $\operatorname{Bij} (X)$, and if $f, g \in \operatorname{Bij} (X)$ then the composition $(f \circ g) (x) = f (g (x))$ is the product of $f$ and $g$ in this group. Inverse maps are inverse elements.

If $X$ and $Y$ have the same cardinality, then $\operatorname{Bij} (X)$ and $\operatorname{Bij} (Y)$ are isomorphic groups. Indeed, since $X$ and $Y$ have the same cardinality, there is a bijection $\phi : X \longrightarrow Y$. Now if $f \in \operatorname{Bij} (X)$ then $H (f) = \phi \circ f \circ \phi^{- 1} \in \operatorname{Bij} (Y)$.

**Exercise 1.4.1:***
Prove that $H : \operatorname{Bij} (X) \longrightarrow \operatorname{Bij}
(Y)$ is a group isomorphism.
*

It follows that for many purposes in discussing $\operatorname{Bij} (X)$ we may take
$X$ to be some standard set. For example, if $X$ is finite, and has
cardinality we may replace $X$ by $\{1, 2, 3, \cdots, n\}$ where $n = |X|$ is
the cardinality of $X$; this does not change the isomorphism class of the
group. If
\[ X = \left\{ 1, 2, 3, \cdots, n \right\} \]
then we will denote $\operatorname{Bij} (X)$ by $S_n$, the *symmetric group on
$n$ letters*. Elements of $S_n$ are called *permutations*. More
generally (particularly if $X$ is finite) an element of $\operatorname{Bij} (X)$ is
called a *permutation* of $X$.

We will introduce two notations for permutations. First, we may write the set $X$ above and below with $f (x)$ below $X$. Thus

\[ \label{samplecycle} \sigma = \left( \begin{array}{lllll} 1 & 2 & 3 & 4 & 5\\ 5 & 4 & 2 & 1 & 3 \end{array} \right) \] | (1.4.1) |

Another notation, *cycle notation* is more succinct and in some ways
more information. We will denote (1.4.1) in cycle notation by $(1,
5, 3, 2, 4)$, meaning that it has the effect.
\[ 1 \longrightarrow 5 \longrightarrow 3 \longrightarrow 2 \longrightarrow 4
\longrightarrow 1 \; . \]
We could just as easily denote this $(5, 3, 2, 4, 1)$. And since no confusion
is likely to result, we could eliminate the commas and write $\sigma = (15324)
= (53241)$.

More generally, if $X$ is a set, let $x_1, \cdots, x_r$ be distinct elements
of $X$. We will denote by $\sigma = (x_1, \cdots, x_r)$ the permutation of $X$
such that $\sigma (x_1) = x_2$, $\sigma (x_2) = x_3, \cdots, \sigma (x_{r -
1}) = x_r$ and $\sigma (x_r) = x_1$. If $x \in X$ is not one if $x_1, \cdots,
x_r$, then $\sigma (x) = x$. A permutation of this sort is called a
$r$-*cycle*.

If $\sigma \in \operatorname{Bij} (X)$, the *support* of $\sigma$ is
$\operatorname{supp} (\sigma) = \left\{ x \in X| \sigma (x) \neq x\} \right.$. We
think of $\operatorname{supp} (\sigma)$ as being the set of "points'' that are
"moved'' by $\sigma$. If $\operatorname{supp} (\sigma)$ and $\operatorname{supp} (\tau)$ are
disjoint, we say that the permutations $\sigma$ and $\tau$ are
*disjoint*.

A $1$-cycle is a special case. Strictly speaking, a 1-cycle is the identity map, since it obviously affects nothing.

**Exercise 1.4.2:***
If $x \in \operatorname{supp} (\sigma)$ prove that $\sigma (x) \in
\operatorname{supp} (\sigma) .$
*

**Proposition 1.4.1:***
If $\sigma$ and $\tau$ are disjoint permutations of
$X$, then $\sigma \tau = \tau \sigma$.
*

**Proof. **(Click to Expand/Collapse)

Let $x \in X$. If $x \notin \operatorname{supp} (\sigma)$ and $x \notin \operatorname{supp}
(\tau)$ then $\sigma \tau (x) = \sigma (x) = x$, and likewise $\tau \sigma
(x) = \tau (x) = x$.

If $x \in \operatorname{supp} (\sigma)$ then since the supports of $\sigma$ and $\tau$ are disjoint, so $x \notin \operatorname{supp} (\tau)$. We have $\sigma \tau (x) = \sigma (x)$. On the other hand $\sigma (x) \in \operatorname{supp} (\sigma)$ by Exercise 1.4.2, so $\sigma (x) \notin \operatorname{supp} (\tau)$. Thus $\tau \sigma (x) = \sigma (x)$.

Finally the case $x \in \operatorname{supp} (\tau)$ is similar to the case just considered.

The three cases are exhaustive so $\tau \sigma (x) = \sigma \tau (x)$ for all $x \in X$. Thus $\sigma \tau = \tau \sigma$ as mappings.

**Exercise 1.4.3:***
Suppose that $| \operatorname{supp} (\sigma) \cap \operatorname{supp} (\tau) | = 1$. Prove
that $\sigma \tau \sigma^{- 1} \tau^{- 1}$ is a 3-cycle.
*

**Proposition 1.4.2:***
If $X$ is a finite set then any $\sigma \in
\operatorname{Bij} (X)$ may be written as a product of disjoint cycles.
*

By Proposition 1.4.1, the cycles in such a decomposition can be taken in any order, since they commute. As an example, in $S_5$ we may factor \[ \left( \begin{array}{lllll} 1 & 2 & 3 & 4 & 5\\ 3 & 5 & 1 & 4 & 2 \end{array} \right) = (1, 3) (2, 5) = (2, 5) (1, 3) . \] The disjoint cycles (2,5) and (1,3) commute by Proposition 1.4.1, so that we may write the permutations in either order. We could also have written \[ \left( \begin{array}{lllll} 1 & 2 & 3 & 4 & 5\\ 3 & 5 & 1 & 4 & 2 \end{array} \right) = (1, 3) (2, 5) (4) . \] However the $1$-cycle $(4)$ is just another notation for the identity element in $S_5$ and we may omit it.

**Exercise 1.4.4:***
Write
\[ \left( \begin{array}{lllll}
1 & 2 & 3 & 4 & 5\\
3 & 4 & 5 & 2 & 1
\end{array} \right) \]
as a product of disjoint cycles.
*

**Exercise 1.4.5:***
In $S_4$, the cycles $(1, 3, 4)$, $(2, 3)$ and $(1, 2)$ are not disjoint.
Write the product $(1, 3, 4) (2, 3) (1, 2)$ as a product of disjoint cycles.
*

We now turn to the proof of Proposition 1.4.2.

**Proof. **(Click to Expand/Collapse)

This Proposition is *obvious* once one has done an example. On the
other hand, it is a good idea, when something is obvious, to feel confident
that one could give a formal proof if pressed to do so. So we will give a
formal proof of this fact.

If $C_i$ has cardinality $1$ then $\sigma_{C_i} = 1$ and this factor may be
omitted from the decomposition, but we will leave it in for the purpose of
this explanation. Let $x \in G$ and let $y = \sigma (x)$. If $x \in G$ then
$x \in C_i$ for a unique $C_i$. We have $\sigma_{C_j} (x) = x$ for $j \neq
i$, and also $\sigma_{C_j} (y) = y$ by Exercise 1.4.2. Thus
\[ \sigma_{C_1} \cdots \sigma_{C_r} (x) = \sigma_{C_1} \cdots \sigma_{C_{j -
1}} \sigma_{C_j} (x) = \sigma_{C_1} \cdots \sigma_{C_{j - 1}} (y) = y =
\sigma (x) . \]
This shows that both sides of (1.4.2) have the same effect on an
arbitrary element of $G$, so they are equal.

Define a relation $\sim$ on $X$ by $x \sim y$ if $\sigma^r (x) = y$ for some $r \in \mathbb{Z}$. Let us check that this is an equivalence relation. First, $\sigma^0 (x) = x$, so $x \sim x$. Next, if $x \sim y$ then for some $r$ we have $\sigma^r (x) = y$. Therefore $\sigma^{- r} (y) = x$ and so $y \sim x$. Finally, if $x \sim y$ and $y \sim z$ then there exist $r$ and $s$ such that $\sigma^r (x) = y$ and $\sigma^s (y) = z$. Then $\sigma^{r + s} (x) = \sigma^s (y) = z$ so $x \sim z$.

Since $\sim$ is an equivalence relation, the set $X$ is the disjoint union of the equivalence classes. If $C$ is one of these equivalence classes, define \[ \sigma_C (x) = \left\{ \begin{array}{ll} \sigma (x) & \text{if $x \in C$;}\\ x & \text{otherwise.} \end{array} \right. \] One checks that $\sigma_C$ is a cycle. The cycles $\sigma_C$ are disjoint by construction. Now let $\{C_1, \cdots, C_k \}$ be the distinct equivalence classes. Then we will show that

\[ \sigma = \sigma_{C_1} \cdots \sigma_{C_r} . \] | (1.4.2) |

We digress to introduce *partitions*, which are fundamental objects in
combinatorics. Intuitively, a *partition* of $n$ is a way of
subdividing $n$ into positive integers. Thus $5 = 3 + 2$ is a partition of
$5$. We do not distinguish between partitions with the same parts taken in
different order, so $3 + 2$ and $2 + 3$ are the same partition of $5$. In
enumerating the partitions of $n$, we can therefore list the parts in
descending order. Thus formally, a partition of $n$ is a descending
sequence of positive integers $\lambda = (\lambda_1, \lambda_2, \cdots,
\lambda_l)$ such that $\lambda_1 \ge \lambda_2 \ge \cdots
\ge \lambda_l$ and $\sum_i \lambda_i = n$. We call $l$ the
*length* of the partition. Sometimes as a matter of notation it is
convenient to allow trailing $0$'s, but these do not change the partition; so
$(3, 2)$ and $(3, 2, 0)$ are the same partition of $5$. The notations of $5$
are
\[ (5), \hspace{1em} (4, 1), \hspace{1em} (3, 2), \hspace{1em} (3, 1, 1),
\hspace{1em} (2, 2, 1), \hspace{1em} (2, 1, 1, 1), \hspace{1em} (1, 1, 1,
1, 1) . \]
There are $7$.

**Exercise 1.4.6:***
What are the partitions of 6?
*

Now we may discuss the conjugacy of permutations in $S_n$. Here are the conjugacy classes of $S_4 = \operatorname{Bij} (\{1, 2, 3, 4\})$. We will omit commas from the cycle notation, so that $(1, 2)$ is denoted $(12)$. The second column will be explained presently.

\[ \begin{array}{|l|l|} \hline \text{conjugacy class} & \text{name (a partition)}\\ \hline \left\{ (1234), (1243), (1324), (1342), (1423), (1432)\} \right. & (4)\\ \hline \left\{ (123), (132), (124), (142), (134), (143), (234), (243)\} \right. & (3, 1)\\ \hline \left\{ (12) (34), (14) (23), (14) (23)\} \right. & (2, 2)\\ \hline \{(12), (13), (14), (23), (24), (34)\} & (2, 1, 1)\\ \hline 1 & (1, 1, 1, 1)\\ \hline \end{array} \] | (1.4.3) |

**Exercise 1.4.7:***
Explain why the $4$-cycle $(2134)$ does not appear in this table.
*

How to see the correctness of this table? It is perhaps easiest if we mix the two notations that we have for permutations. So let $a, b, c, d$ be $1, 2, 3, 4$ in any order. We have \[ \left( \begin{array}{llll} 1 & 2 & 3 & 4\\ a & b & c & d \end{array} \right) (1234) \left( \begin{array}{llll} 1 & 2 & 3 & 4\\ a & b & c & d \end{array} \right)^{- 1} = (a b c d) . \] Indeed, $\left( \begin{array}{llll} 1 & 2 & 3 & 4\\ a & b & c & d \end{array} \right)^{- 1}$ sends $a$ to $1$; $(1234)$ sends $1$ to $2$, then $\left( \begin{array}{llll} 1 & 2 & 3 & 4\\ a & b & c & d \end{array} \right)$ sends $2$ to $b$. Doing these in order, the permutation on the left-hand side sends $a$ to $b$ and (similarly) $b$ to $c$, $c$ to $d$ and $d$ to $a$. The conclusion is that the left-hand side is the $4$-cycle $(a b c d)$, and that as $a, b, c, d$ vary, the conjugate runs through the $4$-cycles. The other conjugacy classes are handled similarly.

**Exercise 1.4.8:***
Verify that
\[ \left( \begin{array}{llll}
1 & 2 & 3 & 4\\
a & b & c & d
\end{array} \right) (12) \left( \begin{array}{llll}
1 & 2 & 3 & 4\\
a & b & c & d
\end{array} \right)^{- 1} = (a b) . \]
*

**Exercise 1.4.9:***
Find the conjugacy classes of $S_3$.
*

**Exercise 1.4.10:***
Show that in the decomposition of a permutation into a product of disjoint
cycles, the cycles are unique (though their order is not, by
Proposition 1.4.1).
*

Now let $\sigma \in S_n$. We will explain how to associate with $\sigma$ a partition.

We consider its decomposition into a product of disjoint cycles. We will associate with $\sigma$ a partition $\lambda$, by writing out the lengths of the cycles that occur, padding out the representation with $1$-cycles, so that every element of $\{1, 2, \cdots, n\}$ appears exactly once in the decomposition. Thus for example in $S_7$ if $\sigma = (147) (26)$ we write it out fully as $(147) (26) (3) (5)$ even though $(3)$ and $(5)$. Now, we take the partition whose part are the lengths of the cycles in this decomposition, written out in descending order. For example, in Table 1.4.3 we have written out the partitions corresponding to the various elements of $S_4$, and it should be no surprise that these correspond exactly to the conjugacy classes.

**Proposition 1.4.3:***
Two permutations are conjugate in $S_n$ if and only if their associated
partitions are equal.
*

**Proof. **(Click to Expand/Collapse)

This should be clear after the preceding discussion. If $\sigma, \tau$ have
the same partitions, we can find a permutation $\phi$ such that applying
$\phi$ element by element to each cycle in $\sigma$ produces one of the
cycles in $\tau$; thus if $(a_1 \cdots a_r)$ and $(b_1 \cdots b_r)$ are
corresponding cycles in $\sigma$ and $\tau$, we can take $\phi$ so that
$\phi (a_i) = b_i$. Then $\phi \sigma \phi^{- 1} = \tau$.

**Exercise 1.4.11:***
Find a normal subgroup of $S_4$ of order 4.
*