Chapter 08 - Groups of Permutations

Permutation groups are where the course becomes computationally exact. A permutation is not an abstract symbol with a declared product; it is a concrete bijection, and its multiplication is composition of functions. This chapter matters because it makes group calculations explicit, and because Cayley’s theorem shows that every group can be realized inside a symmetric group. Everything here should feel operational: you should be able to carry out these computations by hand, quickly and without error.

§8.1 Permutations and the symmetric group

Definition 8.1 (Permutation)

A permutation of a set $A$ is a bijection $\sigma : A \to A$. The set of all permutations of $A$, equipped with composition, is denoted $S_A$ and is called the symmetric group on $A$.

When $A = \{1, 2, \ldots, n\}$, we write $S_n$ and call it the symmetric group on $n$ letters. We have $|S_n| = n!$.

Theorem 8.2. $S_A$ is a group under composition.

Proof

We verify the group axioms.

Closure. If $\sigma, \tau : A \to A$ are bijections, then $\sigma \circ \tau : A \to A$ is also a bijection (composition of bijections is a bijection).

Associativity. Composition of functions is always associative: for all $x \in A$,

$$((\sigma \circ \tau) \circ \mu)(x) = (\sigma \circ \tau)(\mu(x)) = \sigma(\tau(\mu(x))) = \sigma((\tau \circ \mu)(x)) = (\sigma \circ (\tau \circ \mu))(x).$$

Identity. The identity function $\iota : A \to A$ defined by $\iota(x) = x$ satisfies $\sigma \circ \iota = \iota \circ \sigma = \sigma$ for all $\sigma$.

Inverses. Since $\sigma$ is a bijection, it has an inverse function $\sigma^{-1}$ which is also a bijection, and $\sigma \circ \sigma^{-1} = \sigma^{-1} \circ \sigma = \iota$. $\blacksquare$

Remark 8.3 (Non-commutativity)

For $n \geq 3$, the group $S_n$ is non-abelian. This will be demonstrated explicitly in the worked examples below. The failure of commutativity is not pathological; it is the generic situation for permutation groups.

Convention (Composition order)

Throughout these notes, as in Fraleigh and most algebra texts, we compose right to left:

This means: apply $\tau$ first, then $\sigma$. When computing $\sigma\tau$, trace what happens to each element by feeding it through $\tau$ and then through $\sigma$.

§8.2 Two-line notation

Definition 8.4 (Two-line notation)

A permutation $\sigma \in S_n$ can be written as a $2 \times n$ array

where the top row lists the elements of $\{1, \ldots, n\}$ and the bottom row lists their images under $\sigma$.

Intuition: why does a permutation look like a matrix?

A permutation $\sigma$ is a function, and any function on a finite set is determined by listing its values. The two-line notation is nothing more than a lookup table: each column pairs an input (top) with its output (bottom), so column $k$ says ”$k \mapsto \sigma(k)$.” We arrange the inputs in order purely for convenience — it makes reading off $\sigma(k)$ instant.

The resemblance to a matrix is not accidental. Every $\sigma \in S_n$ defines an honest $n \times n$ permutation matrix $P_\sigma$ by placing a single $1$ in each row and column: $(P_\sigma)_{ij} = \begin{cases} 1 & \text{if } \sigma(j) = i, \\ 0 & \text{otherwise.}\end{cases}$ The two-line array is a compressed encoding of $P_\sigma$: instead of writing $n^2$ entries (mostly zeros), we record only the $n$ positions of the $1$‘s. And just as matrix multiplication encodes composition of linear maps, composing permutation matrices corresponds to composing permutations — so the algebraic structure carries over exactly.

Example 8.5. The permutation $\sigma \in S_4$ defined by

means $\sigma(1) = 3$, $\sigma(2) = 1$, $\sigma(3) = 4$, $\sigma(4) = 2$.

Composing permutations in two-line notation

To compute $\sigma\tau$, remember: apply $\tau$ first, then $\sigma$.

Example 8.6. Let

Computing $\sigma\tau$: For each $x$, compute $\sigma(\tau(x))$.

So $\sigma\tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 \end{pmatrix} = \iota$, the identity.

Computing $\tau\sigma$: For each $x$, compute $\tau(\sigma(x))$.

So $\tau\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 \end{pmatrix} = \iota$ also.

In this particular example $\sigma\tau = \tau\sigma = \iota$, so $\tau = \sigma^{-1}$. This is a special case; in general $\sigma\tau \neq \tau\sigma$.

Example 8.7. Let $\alpha, \beta \in S_4$ be given by

$\alpha\beta$: Apply $\beta$ first, then $\alpha$.

So $\alpha\beta = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 3 & 4 \end{pmatrix}$.

$\beta\alpha$: Apply $\alpha$ first, then $\beta$.

So $\beta\alpha = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 1 & 4 \end{pmatrix}$.

Since $\alpha\beta \neq \beta\alpha$, this confirms $S_4$ is non-abelian.

§8.3 Cycle notation

Definition 8.8 (Cycle)

A $k$-cycle (or cycle of length $k$) is a permutation $\sigma$ for which there exist distinct elements $a_1, a_2, \ldots, a_k$ such that

and $\sigma$ fixes all other elements. We write this cycle as

A $2$-cycle is called a transposition. A $1$-cycle $(a)$ is the identity on $\{a\}$ and is usually omitted.

Example 8.9. In $S_5$, the cycle $(1 \; 3 \; 5)$ is the permutation

In two-line notation:

Converting from two-line notation to cycle notation

Start with the smallest element. Follow its orbit under $\sigma$ until you return to the start. Record this as a cycle. Then take the smallest element not yet accounted for and repeat.

Example 8.10. Convert the following to cycle notation:

• Start with $1$: $1 \to 3 \to 1$. Cycle: $(1\;3)$.

  Wait — let us trace more carefully. $\sigma(1)=3$, $\sigma(3)=1$. So $1 \to 3 \to 1$. This gives the cycle $(1\;3)$.

• Smallest unused: $2$. $\sigma(2)=5$, $\sigma(5)=2$. Cycle: $(2\;5)$.

• Smallest unused: $4$. $\sigma(4)=6$, $\sigma(6)=4$. Cycle: $(4\;6)$.

Therefore $\sigma = (1\;3)(2\;5)(4\;6)$.

Verification: $(1\;3)(2\;5)(4\;6)$ sends $1\to 3$, $2\to 5$, $3\to 1$, $4\to 6$, $5\to 2$, $6\to 4$. This matches the two-line notation. $\checkmark$

Example 8.11. Convert to cycle notation:

• Start with $1$: $1 \to 4 \to 1$. Cycle: $(1\;4)$.
• Smallest unused: $2$. $\sigma(2) = 2$, so $2$ is a fixed point (omit).
• Smallest unused: $3$. $3 \to 5 \to 3$. Cycle: $(3\;5)$.

Therefore $\tau = (1\;4)(3\;5)$.

§8.4 Disjoint cycle decomposition

Definition 8.12 (Disjoint cycles)

Two cycles $(a_1\;\cdots\;a_j)$ and $(b_1\;\cdots\;b_k)$ are disjoint if $\{a_1,\ldots,a_j\} \cap \{b_1,\ldots,b_k\} = \emptyset$; that is, no element appears in both cycles.

Theorem 8.13 (Disjoint cycle decomposition)

Every permutation $\sigma \in S_n$ can be written as a product of disjoint cycles. This decomposition is unique up to the order in which the cycles are listed (and up to omission of $1$-cycles).

Proof

Existence. Let $\sigma \in S_n$. Define the orbit of $x$ under $\sigma$ to be

$$\operatorname{Orb}_\sigma(x) = \{x, \sigma(x), \sigma^2(x), \ldots\}.$$

Since $\{1,\ldots,n\}$ is finite and $\sigma$ is injective, repeated application of $\sigma$ starting from $x$ must eventually revisit a value. The first repeated value must be $x$ itself: if $\sigma^i(x) = \sigma^j(x)$ with $i < j$, then injectivity gives $x = \sigma^{j-i}(x)$. So the orbit of $x$ is

$$\{x, \sigma(x), \sigma^2(x), \ldots, \sigma^{m-1}(x)\}$$

for some $m \geq 1$, and $\sigma$ acts on this set as the cycle $(x\;\sigma(x)\;\sigma^2(x)\;\cdots\;\sigma^{m-1}(x))$.

The orbits of $\sigma$ partition $\{1,\ldots,n\}$ (this is a general fact about equivalence relations: define $x \sim y$ iff $y = \sigma^k(x)$ for some integer $k$). On each orbit, $\sigma$ acts as a cycle. Multiplying these cycles together (in any order — they are disjoint) recovers $\sigma$.

Uniqueness. Suppose $\sigma = \gamma_1 \gamma_2 \cdots \gamma_r = \delta_1 \delta_2 \cdots \delta_s$ are two disjoint cycle decompositions. For any $a \in \{1,\ldots,n\}$, the cycle containing $a$ on the left side must produce the same orbit as the cycle containing $a$ on the right side (since both sides equal $\sigma$, they agree on every element). So the cycles are determined by the orbits of $\sigma$, which are determined by $\sigma$ itself. The two decompositions consist of the same cycles, possibly listed in different order. $\blacksquare$

§8.5 Algebra of cycles

Theorem 8.14 (Inverse of a cycle)

If $\sigma = (a_1\;a_2\;\cdots\;a_k)$, then

Proof

Let $\tau = (a_k\;a_{k-1}\;\cdots\;a_1)$. We must show $\sigma\tau = \iota$. For any $a_i$ in the cycle (where $1 \leq i \leq k$):

• $\tau$ sends $a_i$ to the element preceding $a_i$ in the sequence $a_k, a_{k-1}, \ldots, a_1$. The element following $a_i$ in $(a_k\;a_{k-1}\;\cdots\;a_1)$ is $a_{i-1}$ (indices mod $k$, with the convention $a_0 = a_k$). So $\tau(a_i) = a_{i-1}$.
• Then $\sigma(a_{i-1}) = a_i$.

So $(\sigma\tau)(a_i) = \sigma(\tau(a_i)) = \sigma(a_{i-1}) = a_i$.

For elements not in the cycle, both $\sigma$ and $\tau$ fix them. So $\sigma\tau = \iota$. $\blacksquare$

Example 8.15. $(1\;3\;5\;2)^{-1} = (2\;5\;3\;1) = (1\;2\;5\;3)$ (same cycle, different starting point).

Theorem 8.16 (Disjoint cycles commute)

If $\alpha$ and $\beta$ are disjoint cycles, then $\alpha\beta = \beta\alpha$.

Proof

Let $\alpha = (a_1\;\cdots\;a_j)$ and $\beta = (b_1\;\cdots\;b_k)$ be disjoint. We check $(\alpha\beta)(x) = (\beta\alpha)(x)$ for every $x$.

Case 1: $x = a_i$ for some $i$ (i.e., $x$ is in $\alpha$‘s cycle). Since $\alpha$ and $\beta$ are disjoint, $\beta$ fixes $a_i$, so $\beta(a_i) = a_i$. Also, $\alpha(a_i) = a_{i+1}$ (indices mod $j$), and $\beta$ fixes $a_{i+1}$ too. Then:

$$(\alpha\beta)(a_i) = \alpha(\beta(a_i)) = \alpha(a_i) = a_{i+1},$$ $$(\beta\alpha)(a_i) = \beta(\alpha(a_i)) = \beta(a_{i+1}) = a_{i+1}.$$

Case 2: $x = b_i$ for some $i$ (symmetric argument). Both sides give $b_{i+1}$.

Case 3: $x$ is in neither cycle. Both $\alpha$ and $\beta$ fix $x$, so both compositions fix $x$.

In all cases, $(\alpha\beta)(x) = (\beta\alpha)(x)$. $\blacksquare$

Theorem 8.17 (Order of a cycle)

The order of a $k$-cycle is $k$.

Proof

Let $\sigma = (a_1\;a_2\;\cdots\;a_k)$. Then $\sigma^t(a_1) = a_{1+t \bmod k}$. (Here we index cyclically: $a_{k+1} = a_1$, etc.) This equals $a_1$ if and only if $k \mid t$. The smallest positive such $t$ is $k$. $\blacksquare$

Theorem 8.18 (Order of a permutation)

If $\sigma = \gamma_1 \gamma_2 \cdots \gamma_r$ is the disjoint cycle decomposition and the cycles have lengths $m_1, m_2, \ldots, m_r$, then

Proof

Since the $\gamma_i$ are disjoint, they commute (Theorem 8.16). Therefore

$$\sigma^t = \gamma_1^t \gamma_2^t \cdots \gamma_r^t.$$

Now $\sigma^t = \iota$ if and only if $\gamma_i^t = \iota$ for each $i$ (because the cycles act on disjoint sets of elements: $\gamma_i^t$ is the identity on the support of $\gamma_i$ if and only if $\gamma_i^t = \iota$ as a permutation, and the $\gamma_i$ have disjoint supports).

By Theorem 8.17, $\gamma_i^t = \iota$ if and only if $m_i \mid t$. The smallest positive $t$ divisible by all $m_i$ is $\operatorname{lcm}(m_1, \ldots, m_r)$. $\blacksquare$

Example 8.19. The permutation $\sigma = (1\;2\;3)(4\;5)(6\;7\;8\;9) \in S_9$ has disjoint cycle lengths $3, 2, 4$. Therefore

Example 8.20. The permutation $\tau = (1\;2)(3\;4\;5\;6\;7) \in S_7$ has cycle lengths $2, 5$. So

§8.6 Every permutation is a product of transpositions

Theorem 8.21 (Transposition decomposition of a cycle)

Every $k$-cycle can be written as a product of transpositions:

Proof

We prove this by checking both sides agree on every element.

Let $\sigma = (a_1\;a_2\;\cdots\;a_k)$ and let $\rho = (a_1\;a_k)(a_1\;a_{k-1})\cdots(a_1\;a_2)$.

On $a_1$: The rightmost transposition $(a_1\;a_2)$ sends $a_1 \mapsto a_2$. Since $a_2 \neq a_1$ and $a_2$ does not appear as the second entry of any of the remaining transpositions $(a_1\;a_3), \ldots, (a_1\;a_k)$ (each of these only moves $a_1$ and one other element $a_j$ with $j \geq 3$), all remaining transpositions fix $a_2$. So $\rho(a_1) = a_2 = \sigma(a_1)$. $\checkmark$

On $a_i$ for $2 \leq i \leq k-1$: The rightmost transposition $(a_1\;a_2)$ fixes $a_i$ (since $i \geq 2$ and $a_i \neq a_1$). Similarly, $(a_1\;a_3), \ldots, (a_1\;a_{i-1})$ all fix $a_i$. Then $(a_1\;a_i)$ sends $a_i \mapsto a_1$. Then $(a_1\;a_{i+1})$ sends $a_1 \mapsto a_{i+1}$. The remaining transpositions $(a_1\;a_{i+2}), \ldots, (a_1\;a_k)$ all fix $a_{i+1}$. So $\rho(a_i) = a_{i+1} = \sigma(a_i)$. $\checkmark$

On $a_k$: The transpositions $(a_1\;a_2), \ldots, (a_1\;a_{k-1})$ all fix $a_k$. Then $(a_1\;a_k)$ sends $a_k \mapsto a_1$. There are no transpositions to the left. So $\rho(a_k) = a_1 = \sigma(a_k)$. $\checkmark$

On elements not in the cycle: All transpositions fix such elements, so $\rho$ fixes them too. $\checkmark$

Since $\sigma$ and $\rho$ agree on all elements, $\sigma = \rho$. $\blacksquare$

Corollary 8.22

Every permutation in $S_n$ ($n \geq 2$) can be written as a product of transpositions.

Proof

Write the permutation as a product of disjoint cycles (Theorem 8.13). Apply Theorem 8.21 to each cycle. The resulting product of transpositions equals the original permutation. $\blacksquare$

Example 8.23. Express $(1\;3\;5\;2\;4)$ as a product of transpositions.

By Theorem 8.21:

Verification. Apply right to left to each element:

The transposition decomposition is not unique

The same permutation can be expressed as different products of transpositions. For instance, $(1\;2\;3) = (1\;3)(1\;2) = (2\;3)(1\;3)$. What is unique is the parity (even or odd number of transpositions). This will be developed in Chapter 9.

§8.7 Cayley’s theorem

Theorem 8.24 (Cayley’s theorem)

Every group $G$ is isomorphic to a subgroup of some symmetric group. More precisely, $G$ is isomorphic to a subgroup of $S_G$ (the group of all permutations of the underlying set of $G$). If $G$ is finite with $|G| = n$, then $G$ is isomorphic to a subgroup of $S_n$.

Proof (via the left regular representation)

For each $g \in G$, define the left multiplication map $\lambda_g : G \to G$ by

$$\lambda_g(x) = gx.$$

Step 1. $\lambda_g$ is a permutation of $G$.

Injective: If $\lambda_g(x) = \lambda_g(y)$, then $gx = gy$, so $x = y$ by left cancellation.

Surjective: For any $y \in G$, we have $\lambda_g(g^{-1}y) = g(g^{-1}y) = y$.

So $\lambda_g \in S_G$.

Step 2. Define $\Phi : G \to S_G$ by $\Phi(g) = \lambda_g$.

Step 3. $\Phi$ is a homomorphism. For all $g, h \in G$ and all $x \in G$:

$$\lambda_{gh}(x) = (gh)x = g(hx) = \lambda_g(\lambda_h(x)) = (\lambda_g \circ \lambda_h)(x).$$

Therefore $\Phi(gh) = \lambda_{gh} = \lambda_g \circ \lambda_h = \Phi(g) \circ \Phi(h)$.

Step 4. $\Phi$ is injective. Suppose $\Phi(g) = \Phi(h)$, i.e., $\lambda_g = \lambda_h$. Then for all $x \in G$, $gx = hx$. Setting $x = e$ gives $g = h$.

Conclusion. $\Phi$ is an injective homomorphism, so $G \cong \Phi(G) \leq S_G$. If $|G| = n$, we can label the elements of $G$ as $\{1, \ldots, n\}$ to realize $\Phi(G) \leq S_n$. $\blacksquare$

Example 8.25. The left regular representation of $\mathbb{Z}_3 = \{0, 1, 2\}$.

So $\Phi(\mathbb{Z}_3) = \{\iota,\;(0\;1\;2),\;(0\;2\;1)\} \leq S_3$, and indeed $\mathbb{Z}_3 \cong \langle (0\;1\;2) \rangle$.

§8.8 Worked computations in $S_4$ and $S_5$

Computation 8.26 (Products in $S_4$, both orders)

Let $\alpha = (1\;2\;3)$ and $\beta = (2\;4)$ in $S_4$.

$\alpha\beta$: Apply $\beta$ first, then $\alpha$.

So $\alpha\beta = (1\;2\;4\;3)$.

$\beta\alpha$: Apply $\alpha$ first, then $\beta$.

So $\beta\alpha = (1\;4\;2\;3)$.

Observations:

• $\alpha\beta \neq \beta\alpha$, confirming non-commutativity.
• $\operatorname{ord}(\alpha\beta) = 4$ (it is a $4$-cycle).
• $\operatorname{ord}(\beta\alpha) = 4$ (also a $4$-cycle).
• $(\alpha\beta)^{-1} = (3\;4\;2\;1) = (1\;3\;4\;2)$.

Computation 8.27 (Inverse in $S_5$)

Let $\sigma = (1\;3\;5)(2\;4) \in S_5$.

Then $\sigma^{-1} = (1\;5\;3)(2\;4)$ (reverse each cycle; the inverse of a transposition is itself).

Verification: $\sigma\sigma^{-1}$:

Wait — we must be careful. $\sigma = (1\;3\;5)(2\;4)$ means apply $(2\;4)$ first, then $(1\;3\;5)$. So $\sigma^{-1} = (2\;4)^{-1}(1\;3\;5)^{-1} = (2\;4)(1\;5\;3)$.

But since $(1\;3\;5)$ and $(2\;4)$ are disjoint, they commute. So

Order: $\operatorname{ord}(\sigma) = \operatorname{lcm}(3, 2) = 6$.

Computation 8.28 (A longer example in $S_5$)

Let $\sigma = (1\;2\;4)$ and $\tau = (1\;3)(2\;5)$ in $S_5$.

$\sigma\tau$: Apply $\tau$ first, then $\sigma$.

So $\sigma\tau = (1\;3\;2\;5\;4)$, a $5$-cycle.

$\operatorname{ord}(\sigma\tau) = 5$.

$\tau\sigma$: Apply $\sigma$ first, then $\tau$.

So $\tau\sigma = (1\;5\;2\;4\;3)$, also a $5$-cycle. Again $\operatorname{ord}(\tau\sigma) = 5$.

Computation 8.29 (Converting notations in $S_5$)

Start from the two-line form:

Convert to cycle notation:

• $1 \to 2 \to 5 \to 1$. Cycle: $(1\;2\;5)$.
• $3 \to 4 \to 3$. Cycle: $(3\;4)$.

So $\sigma = (1\;2\;5)(3\;4)$.

Order: $\operatorname{lcm}(3, 2) = 6$.

Inverse: $\sigma^{-1} = (1\;5\;2)(3\;4) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 1 & 4 & 3 & 2 \end{pmatrix}$.

§8.9 Conjugation in $S_n$

Theorem 8.30 (Conjugation relabels cycles)

For any $\tau \in S_n$ and any cycle $(a_1\;a_2\;\cdots\;a_k) \in S_n$,

Proof

Let $\sigma = (a_1\;a_2\;\cdots\;a_k)$. We must show $\tau\sigma\tau^{-1}$ and $(\tau(a_1)\;\tau(a_2)\;\cdots\;\tau(a_k))$ agree on all elements.

Case 1: $x = \tau(a_i)$ for some $1 \leq i \leq k$. Then

$$(\tau\sigma\tau^{-1})(\tau(a_i)) = \tau(\sigma(a_i)) = \tau(a_{i+1}),$$

where indices are taken mod $k$ (so $a_{k+1} = a_1$). Meanwhile,

$$(\tau(a_1)\;\cdots\;\tau(a_k)) \text{ sends } \tau(a_i) \mapsto \tau(a_{i+1}).$$

These agree. $\checkmark$

Case 2: $x \notin \{\tau(a_1), \ldots, \tau(a_k)\}$. Then $\tau^{-1}(x) \notin \{a_1, \ldots, a_k\}$ (since $\tau$ is a bijection). So $\sigma$ fixes $\tau^{-1}(x)$, and therefore

$$(\tau\sigma\tau^{-1})(x) = \tau(\sigma(\tau^{-1}(x))) = \tau(\tau^{-1}(x)) = x.$$

The cycle $(\tau(a_1)\;\cdots\;\tau(a_k))$ also fixes $x$. $\checkmark$

Since both sides agree on all $x \in \{1, \ldots, n\}$, they are equal. $\blacksquare$