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,\dots ,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$. $■$

Remark 8.3 (Non-commutativity)

For $n\ge 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,\dots ,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{array}{ll}1& \text{if }\sigma (j)=i,\\ 0& \text{otherwise.}\end{array}$ 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 =\left(\begin{array}{cccc}1& 2& 3& 4\\ 1& 2& 3& 4\end{array}\right)=\iota$, the identity.

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

So $\tau \sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 1& 2& 3& 4\end{array}\right)=\iota$ also.

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

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

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

So $\alpha \beta =\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 1& 3& 4\end{array}\right)$.

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

So $\beta \alpha =\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 2& 1& 4\end{array}\right)$.

Since $\alpha \beta \ne \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,\dots ,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 $(135)$ 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: $(13)$.

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

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

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

Therefore $\sigma =(13)(25)(46)$.

Verification: $(13)(25)(46)$ 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. $✓$

Example 8.11. Convert to cycle notation:

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

Therefore $\tau =(14)(35)$.

§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,\dots ,a_j\}\cap \{b_1,\dots ,b_k\}=\varnothing$; 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

$${\mathrm{Orb}}_{\sigma }(x)=\{x,\sigma (x),{\sigma }^2(x),\dots \}.$$

Since $\{1,\dots ,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),\dots ,{\sigma }^{m-1}(x)\}$$

for some $m\ge 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,\dots ,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,\dots ,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. $■$

§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\le i\le k$):

• $\tau$ sends $a_i$ to the element preceding $a_i$ in the sequence $a_k,a_{k-1},\dots ,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$. $■$

Example 8.15. $(1352{)}^{-1}=(2531)=(1253)$ (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)$. $■$

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\mathrm{mod}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$. $■$

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,\dots ,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 $\mathrm{lcm}(m_1,\dots ,m_r)$. $■$

Example 8.19. The permutation $\sigma =(123)(45)(6789)\in S_9$ has disjoint cycle lengths $3,2,4$. Therefore

Example 8.20. The permutation $\tau =(12)(34567)\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\ne a_1$ and $a_2$ does not appear as the second entry of any of the remaining transpositions $(a_1{a}_3),\dots ,(a_1{a}_k)$ (each of these only moves $a_1$ and one other element $a_j$ with $j\ge 3$), all remaining transpositions fix $a_2$. So $\rho (a_1)=a_2=\sigma (a_1)$. $✓$

On $a_i$ for $2\le i\le k-1$: The rightmost transposition $(a_1{a}_2)$ fixes $a_i$ (since $i\ge 2$ and $a_i\ne a_1$). Similarly, $(a_1{a}_3),\dots ,(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}),\dots ,(a_1{a}_k)$ all fix $a_{i+1}$. So $\rho (a_i)=a_{i+1}=\sigma (a_i)$. $✓$

On $a_k$: The transpositions $(a_1{a}_2),\dots ,(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)$. $✓$

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

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

Corollary 8.22

Every permutation in $S_n$ ($n\ge 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. $■$

Example 8.23. Express $(13524)$ 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, $(123)=(13)(12)=(23)(13)$. 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)\le S_G$. If $|G|=n$, we can label the elements of $G$ as $\{1,\dots ,n\}$ to realize $\Phi (G)\le S_n$. $■$

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

So $\Phi ({\mathbb{Z}}_3)=\{\iota ,(012),(021)\}\le S_3$, and indeed ${\mathbb{Z}}_3\cong ⟨(012)⟩$.

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

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

Let $\alpha =(123)$ and $\beta =(24)$ in $S_4$.

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

So $\alpha \beta =(1243)$.

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

So $\beta \alpha =(1423)$.

Observations:

• $\alpha \beta \ne \beta \alpha$, confirming non-commutativity.
• $\mathrm{ord}(\alpha \beta )=4$ (it is a $4$-cycle).
• $\mathrm{ord}(\beta \alpha )=4$ (also a $4$-cycle).
• $(\alpha \beta {)}^{-1}=(3421)=(1342)$.

Computation 8.27 (Inverse in $S_5$)

Let $\sigma =(135)(24)\in S_5$.

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

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

Wait — we must be careful. $\sigma =(135)(24)$ means apply $(24)$ first, then $(135)$. So ${\sigma }^{-1}=(24{)}^{-1}(135{)}^{-1}=(24)(153)$.

But since $(135)$ and $(24)$ are disjoint, they commute. So

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

Computation 8.28 (A longer example in $S_5$)

Let $\sigma =(124)$ and $\tau =(13)(25)$ in $S_5$.

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

So $\sigma \tau =(13254)$, a $5$-cycle.

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

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

So $\tau \sigma =(15243)$, also a $5$-cycle. Again $\mathrm{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: $(125)$.
• $3\to 4\to 3$. Cycle: $(34)$.

So $\sigma =(125)(34)$.

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

Inverse: ${\sigma }^{-1}=(152)(34)=\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 5& 1& 4& 3& 2\end{array}\right)$.

§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\le i\le 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. $✓$

Case 2: $x\notin \{\tau (a_1),\dots ,\tau (a_k)\}$. Then ${\tau }^{-1}(x)\notin \{a_1,\dots ,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$. $✓$

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

Corollary 8.31 (Conjugation preserves cycle type)

If $\sigma$ has disjoint cycle decomposition $\sigma =(a_1\cdots a_{j_1})(b_1\cdots b_{j_2})\cdots$, then

In particular, $\tau \sigma {\tau }^{-1}$ has the same cycle type as $\sigma$.

Proof

Since conjugation distributes over products ($\tau ({\sigma }_1{\sigma }_2){\tau }^{-1}=(\tau {\sigma }_1{\tau }^{-1})(\tau {\sigma }_2{\tau }^{-1})$), applying Theorem 8.30 to each cycle in the decomposition yields the result. The cycle lengths are unchanged because $\tau$ is a bijection. $■$

Converse (stated without proof)

In $S_n$, two permutations are conjugate if and only if they have the same cycle type. (This converse requires a separate argument, constructing a specific $\tau$ that maps one set of cycles to the other.)

Example 8.32. In $S_5$, let $\sigma =(123)(45)$ and $\tau =(13425)$.

Compute $\tau \sigma {\tau }^{-1}$ using the relabeling theorem:

This has cycle type $(3,2)$, the same as $\sigma$. $✓$

§8.10 The dihedral group $D_n$ as a subgroup of $S_n$

Definition 8.33 (Dihedral group)

The dihedral group $D_n$ is the group of symmetries of a regular $n$-gon. It has order $2n$ and is generated by a rotation $r$ of angle $2\pi /n$ and a reflection $s$, subject to the relations

The elements of $D_n$ are $\{e,r,r^2,\dots ,r^{n-1},s,sr,s{r}^2,\dots ,s{r}^{n-1}\}$.

Embedding $D_n$ into $S_n$

Label the vertices of the regular $n$-gon as $1,2,\dots ,n$. Each symmetry of the $n$-gon permutes these vertices, giving an injective homomorphism $D_n\hookrightarrow S_n$.

Example 8.34 ($D_3\cong S_3$)

For the equilateral triangle with vertices $1,2,3$ (labeled clockwise):

These are exactly the $3!=6$ elements of $S_3$, so $D_3\cong S_3$.

Cayley table of $S_3\cong D_3$

Using the notation $e=\iota$, ${\rho }_1=(123)$, ${\rho }_2=(132)$, ${\mu }_1=(23)$, ${\mu }_2=(13)$, ${\mu }_3=(12)$:

Reading the table: Entry in row $\alpha$, column $\beta$ is $\alpha \beta$ (apply $\beta$ first).

Verification of one entry: ${\rho }_1{\mu }_1=(123)(23)$. Apply $(23)$ first: $1\to 1\to 2$, $2\to 3\to 1$, $3\to 2\to 3$. Wait: $1\stackrel{(23)}{\to }1\stackrel{(123)}{\to }2$, $2\stackrel{(23)}{\to }3\stackrel{(123)}{\to }1$, $3\stackrel{(23)}{\to }2\stackrel{(123)}{\to }3$. So ${\rho }_1{\mu }_1=(12)={\mu }_3$. $✓$

§8.11 Subgroup structure of $S_3$

$S_3$ has order $6$. By Lagrange’s theorem, subgroup orders must divide $6$, so they can be $1,2,3$, or $6$.

All subgroups of $S_3$:

Total: 6 subgroups.

Subgroup lattice

Figure: subgroup lattice of $S_3$.

The inclusion ordering is:

• $\{e\}\le A_3\le S_3$
• $\{e\}\le \{e,(12)\}\le S_3$
• $\{e\}\le \{e,(13)\}\le S_3$
• $\{e\}\le \{e,(23)\}\le S_3$

Note that $A_3$ is the unique subgroup of order $3$, and it is normal in $S_3$ (it has index $2$). The three subgroups of order $2$ are not normal (they are conjugate to each other).

§8.12 Standard traps and common mistakes

Pitfalls in permutation computations

Trap 1: Composition order. The product $\sigma \tau$ means “apply $\tau$ first, then $\sigma$.” This is the single most common source of errors. Every time you compute a product, explicitly write the chain $x\stackrel{\tau }{\to }\cdots \stackrel{\sigma }{\to }\cdots$ until it becomes reflexive.

Trap 2: Non-disjoint cycles do NOT commute. If cycles share an element, their product depends on the order. For example:

Check: $(12)(13)$: $1\stackrel{(13)}{\to }3\stackrel{(12)}{\to }3$, $3\stackrel{(13)}{\to }1\stackrel{(12)}{\to }2$, $2\stackrel{(13)}{\to }2\stackrel{(12)}{\to }1$. So $(12)(13)=(132)$. But $(13)(12)$: $1\stackrel{(12)}{\to }2\stackrel{(13)}{\to }2$, $2\stackrel{(12)}{\to }1\stackrel{(13)}{\to }3$, $3\stackrel{(12)}{\to }3\stackrel{(13)}{\to }1$. So $(13)(12)=(123)$.

Trap 3: Order is lcm, not sum. The order of $(123)(45)$ is $\mathrm{lcm}(3,2)=6$, not $3+2=5$.

Trap 4: Cycle notation is ambiguous about the ambient group. The cycle $(123)$ can live in $S_3$, $S_4$, $S_5$, etc. The ambient group matters for counting arguments (e.g., how many permutations have a given cycle type).

Trap 5: Forgetting fixed points in two-line notation. When converting to cycle notation, a common error is to list elements in the cycle that are actually fixed. Always check: does the element return to itself in one step? If so, it is a fixed point and is omitted from cycle notation.

§8.13 Lang’s structural perspective

Permutation groups as group actions

In Lang’s Algebra, the concept of a permutation group is subsumed by the general theory of group actions. A group $G$ acts on a set $X$ if there is a homomorphism $\phi :G\to S_X$. The image $\phi (G)\le S_X$ is a permutation group, and the kernel $\ker \phi$ measures how much of $G$ is “lost” in the action.

From this viewpoint:

• A permutation of $X$ is an element of $S_X$.
• The orbit of $x$ under $\sigma$ is the orbit of $x$ under the action of $⟨\sigma ⟩$ on $X$.
• Disjoint cycle decomposition is the orbit decomposition of $\{1,\dots ,n\}$ under the cyclic subgroup $⟨\sigma ⟩$.
• Conjugation in $S_n$ is the natural action of $S_n$ on itself by inner automorphisms: $\sigma \mapsto \tau \sigma {\tau }^{-1}$. The relabeling theorem (Theorem 8.30) says that this action simply relabels the entries of each cycle.

Cayley’s theorem as a faithful action

Cayley’s theorem says: every group $G$ acts faithfully (i.e., with trivial kernel) on itself by left multiplication. In Lang’s language, the left regular representation $\lambda :G\to S_G$ is a faithful group action of $G$ on the set $G$.

This perspective makes clear:

1. The representation $G\hookrightarrow S_n$ from Cayley’s theorem is usually far from efficient (a group of order $n$ embeds into a group of order $n!$). Finding small faithful representations is a separate problem.
2. The real content is that permutation representations are universal: any abstract group-theoretic statement can, in principle, be verified by computation inside a symmetric group.
3. Cycle type is a conjugacy invariant, and the conjugacy classes of $S_n$ are indexed by partitions of $n$. This connection between representation theory and combinatorics deepens significantly in later courses.

§8.15 Flashcard-ready summary

Key facts to memorize

1. $|S_n|=n!$ and $S_n$ is non-abelian for $n\ge 3$.
2. Composition convention: $(\sigma \tau )(x)=\sigma (\tau (x))$ — apply $\tau$ first.
3. Disjoint cycle decomposition exists and is unique (up to order of cycles).
4. Inverse of a cycle: $(a_1{a}_2\cdots a_k{)}^{-1}=(a_k{a}_{k-1}\cdots a_1)$.
5. Disjoint cycles commute. Overlapping cycles do NOT.
6. Order of a $k$-cycle is $k$.
7. Order of a permutation $=\mathrm{lcm}$ of disjoint cycle lengths.
8. Transposition decomposition: $(a_1\cdots a_k)=(a_1{a}_k)(a_1{a}_{k-1})\cdots (a_1{a}_2)$.
9. Cayley’s theorem: every group $G$ embeds into $S_G$ via $g\mapsto {\lambda }_g$ (left multiplication).
10. Conjugation relabels: $\tau (a_1\cdots a_k){\tau }^{-1}=(\tau (a_1)\cdots \tau (a_k))$.
11. Conjugate permutations have the same cycle type (and conversely in $S_n$).
12. $D_3\cong S_3$, $|D_n|=2n$, and $D_n\le S_n$.
13. $S_n$ is generated by $\{(12),(13),\dots ,(1n)\}$.
14. Number of $k$-cycles in $S_n$: $\frac{n!}{k(n-k)!}$.