Permutations

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)

is the permutation $\sigma : X \longrightarrow X$, where $X =\{1, 2, 3, 4, 5\}$, such that $f (1) = 5$, $f (2) = 4$, $f (3) = 2$, $f (4) = 1$ and $f (5) = 3$. This notation is good for some purposes but inefficient.

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.

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)

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.

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.