Cayley定理

一、群同态与群同构

1.1 群同态的定义

之前研究的是单个群的性质，现在开始研究不同群之间的关系。

定义：设 $(G, \cdot)$ 和 $(H, *)$ 是两个群，$f: G \to H$ 是一个映射。若对任意的 $a, b \in G$，都有

\[f(a \cdot b) = f(a) * f(b)\]

即先在 $G$ 中做运算再用 $f$ 映过去，等于先分别用 $f$ 映过去再在 $H$ 中做运算，则称 $f$ 是 $G$ 到 $H$ 的一个群同态（group homomorphism）。

群同态是代数中的核心概念。通过同态来衡量不同群之间的关系：集合可能不同，运算可能不同，但它们可以用这样的映射联系起来。

1.2 群同构的定义

定义：若群同态 $f: G \to H$ 还是一个双射（一一对应），则称 $f$ 是 $G$ 到 $H$ 的一个群同构（group isomorphism），记作 $G \cong H$。

双射 = 单射 + 满射：不同元素映到不同元素，且 $H$ 中每个元素都在 $f$ 的像中。

若两个群之间存在群同构，就认为这两个群虽然集合可能不一样、运算可能不一样，但本质上是一样的。

在同构意义下对群做分类，是群论中一个核心问题，但直到现在仍远未完全解决。即使限制在有限群上，例如研究阶为 $2^k$ 的群在同构意义下有多少个，目前也只在 $k$ 较小（约十几）的时候才完全解决，$k = 30$ 这样的情形仍远远没有解决。

1.3 与线性代数的联系

群同态并非全新的概念。回忆线性代数中的线性映射：设 $V, W$ 是实数域上的线性空间，$f: V \to W$ 是线性映射，则

$f(u + v) = f(u) + f(v)$（保持加法）
$f(\lambda v) = \lambda f(v)$（保持数乘）

一个线性空间在加法下构成一个群，因此条件 1 正是说 $f$ 是关于加法群的群同态。群同态只需要保持一种运算（群运算），而线性映射还需要额外保持数乘，这是因为线性空间的结构比群更丰富。

典型例子：$\mathbb{R}^n$ 上的线性映射都可以通过某个矩阵 $A$ 来表示，即 $f(\mathbf{x}) = \mathbf{x} A$（行向量右乘矩阵）。

1.4 例子：对数函数

考虑对数函数 $\ln: (\mathbb{R}^+, \times) \to (\mathbb{R}, +)$，其中 $\mathbb{R}^+ = {x \in \mathbb{R} \mid x > 0}$。

$(\mathbb{R}^+, \times)$ 是正实数在乘法下构成的群（封闭，每个元素的倒数仍在其中）。
$(\mathbb{R}, +)$ 是实数在加法下构成的群。

由对数的基本性质：

\[\ln(ab) = \ln a + \ln b\]

左边是 $(\mathbb{R}^+, \times)$ 中的乘法运算，右边是 $(\mathbb{R}, +)$ 中的加法运算。因此 $\ln$ 是一个群同态。

进一步，$\ln$ 还是一个双射（其逆映射为指数函数 $\exp$），因此 $\ln$ 实际上是一个群同构：

\[(\mathbb{R}^+, \times) \cong (\mathbb{R}, +)\]

反过来，指数函数 $\exp: (\mathbb{R}, +) \to (\mathbb{R}^+, \times)$ 也是群同态，因为 $e^{x+y} = e^x \cdot e^y$。

从代数角度看，这两个群虽然集合完全不同、运算完全不同，但作为群是同构的。在微积分中不太强调这个同构，因为研究实数时通常同时考虑加法和乘法，而不是单独研究某一个。

1.5 例子：行列式

设 $GL_2(\mathbb{R})$ 为二阶可逆实矩阵全体，在矩阵乘法下构成一个群。定义行列式映射：

\[\det: GL_2(\mathbb{R}) \to (\mathbb{R} \setminus \{0\}, \times)\] \[\det \begin{pmatrix} a & b \\ c & d \end{pmatrix} = ad - bc\]

矩阵可逆当且仅当行列式不为零（对 $n$ 阶矩阵都成立），因此像确实落在 $\mathbb{R} \setminus {0}$ 中。

由行列式的乘法性质：

\[\det(AB) = \det(A) \cdot \det(B)\]

左边是矩阵乘法，右边是数的乘法，因此 $\det$ 是一个群同态。

同态的进一步性质（如同态的核、像等）放到下周讲。

二、对称群（置换群）

2.1 定义

历史上最早研究的群就是置换群，它比抽象群的概念出现得更早。

定义：设 $X$ 是一个集合，$X$ 上的对称群定义为

\[S(X) = \{\sigma: X \to X \mid \sigma \text{ 是双射}\}\]

即 $X$ 上全体双射的集合，在映射的复合运算下构成一个群。

验证 $S(X)$ 构成群：

封闭性：两个双射的复合仍是双射
结合律：映射的复合满足结合律
单位元：恒等映射 $\mathrm{id}_X$
逆元：双射的逆映射仍是双射

2.2 有限对称群 $S_n$

多数时候考虑有限集合 $X = {1, 2, \ldots, n}$，此时记

\[S_n = S(\{1, 2, \ldots, n\})\]

$S_n$ 称为 $n$ 次对称群。

$S_n$ 的阶：$

S_n

= n!$

原因：构造一个 ${1, \ldots, n}$ 到自身的双射时，1 有 $n$ 种选择；因为要求单射，2 只有 $n-1$ 种选择；3 有 $n-2$ 种选择；依此类推。这就是全排列，共 $n!$ 种。

2.3 置换的二行表示

$S_n$ 中的元素 $\sigma$ 用二行表表示：

\[\sigma = \begin{pmatrix} 1 & 2 & \cdots & n \\ \sigma(1) & \sigma(2) & \cdots & \sigma(n) \end{pmatrix}\]

第一行是定义域中的 $n$ 个元素，第二行是它们的像。下面一行一定是 $1$ 到 $n$ 的一个全排列（不重不漏）。

2.4 小阶对称群的枚举

$S_1$：只有一个元素，即恒等映射。

$S_2$：有两个元素：

\[e = \begin{pmatrix} 1 & 2 \\ 1 & 2 \end{pmatrix}, \quad \tau = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}\]

$S_3$：有六个元素。设 $\sigma_1, \ldots, \sigma_6$ 分别为：

\[\sigma_1 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}, \quad \sigma_2 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}, \quad \sigma_3 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}\] \[\sigma_4 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}, \quad \sigma_5 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}, \quad \sigma_6 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}\]

$S_3$ 在有限群中非常重要，因为它是最小的非交换群。阶不超过 5 的群都是交换群，而 $S_3$（阶为 6）是第一个出现不满足交换律的群。

例如，取 $\sigma_4$ 和 $\sigma_3$，可以验证 $\sigma_4 \circ \sigma_3 \neq \sigma_3 \circ \sigma_4$，即映射复合的顺序不同会导致不同的结果。

$S_4$ 有 $4! = 24$ 个元素，就不一一列举了。

三、Cayley 定理

3.1 左乘映射

引理：设 $(G, \cdot)$ 是一个群。对任意 $a \in G$，定义左乘映射

\[L_a: G \to G, \quad L_a(x) = a \cdot x\]

则 $L_a$ 是 $G$ 到自身的双射。

证明：

单射：设 $L_a(x) = L_a(y)$，即 $ax = ay$。由群的消去律（两边左乘 $a^{-1}$），得 $x = y$。

满射：任取 $y \in G$，令 $x = a^{-1}y$（$x \in G$），则

\[L_a(x) = a \cdot (a^{-1}y) = (a \cdot a^{-1}) \cdot y = e \cdot y = y\]

因此 $y$ 在 $L_a$ 的像中，且其原像 $x = a^{-1}y$ 可以明确写出。$\blacksquare$

3.2 左乘映射的复合

断言：对任意 $a, b \in G$，有

\[L_{ab} = L_a \circ L_b\]

即元素 $ab$ 诱导的左乘映射，等于先做 $L_b$ 再做 $L_a$ 的复合。

证明：任取 $x \in G$，

左边：$L_{ab}(x) = (ab)x$
右边：$(L_a \circ L_b)(x) = L_a(L_b(x)) = L_a(bx) = a(bx)$

由结合律，$(ab)x = a(bx)$，故左边等于右边。$\blacksquare$

这个证明本质上只用了群的结合律。

3.3 不同元素诱导不同的左乘映射

断言：若 $a \neq b$，则 $L_a \neq L_b$。

证明：若 $L_a = L_b$，则对所有 $x \in G$ 有 $L_a(x) = L_b(x)$。特别地，取 $x = e$（单位元），得 $ae = be$，即 $a = b$，矛盾。$\blacksquare$

3.4 Cayley 定理

定理（Cayley）：设 $(G, \cdot)$ 是群，定义映射

\[\varphi: G \to S(G), \quad \varphi(a) = L_a\]

其中 $S(G)$ 是 $G$（作为集合）上的对称群。则 $\varphi$ 是一个单同态（单射的群同态）。

证明：综合以上三步分析：

由第一步，对任意 $a \in G$，$\varphi(a) = L_a$ 是 $G$ 到自身的双射，因此 $\varphi$ 确实是 $G$ 到 $S(G)$ 的映射。
由第二步，$L_{ab} = L_a \circ L_b$，即 $\varphi(ab) = \varphi(a) \circ \varphi(b)$，因此 $\varphi$ 保持运算，是群同态。
由第三步，$a \neq b \implies L_a \neq L_b$，即 $\varphi(a) \neq \varphi(b)$，因此 $\varphi$ 是单射。$\blacksquare$

推论：任何群都同构于某个对称群的子群。

注意：群 $G$ 的定义中，结合律、单位元、逆元全都用到了。没有逆元就很难证明满射；没有结合律就无法保证复合关系成立。

3.5 关于 Cayley 定理的讨论

虽然 Cayley 定理意义重大（说明对称群具有足够的一般性），但在实际使用中不一定方便。

若 $G$ 是有限群，$

= n$，则 Cayley 定理将 $G$ 嵌入 $S_n$，而 $

S_n

= n!$。阶乘的增长速度远超指数，因此一个 $n$ 阶群被嵌入了一个 $n!$ 阶的群中，这往往太大了。

由此引出一个自然的问题：

问题：对给定的群 $G$，是否存在单同态 $G \hookrightarrow S(X)$，使得 $

$ 尽可能小？

这是群论中一个重要但困难的问题（称为忠实置换表示的最小次数问题），目前对一般的群尚未完全解决。

四、置换矩阵

4.1 定义

$S_n$ 中的每个元素可以用一个 $n$ 阶置换矩阵来表示。置换矩阵是每行每列恰好有一个 1、其余全为 0 的矩阵。

定义：对 $\sigma \in S_n$，定义 $n$ 阶矩阵 $P_\sigma = (a_{ij})$，其中

\[a_{ij} = \begin{cases} 1, & \text{若 } i = \sigma(j) \\ 0, & \text{若 } i \neq \sigma(j) \end{cases}\]

给定 $j$，只有 $i = \sigma(j)$ 时该列为 1，其余为 0，因此每列恰好一个 1。又因为 $\sigma$ 是单射，不同的 $j$ 对应不同的 $\sigma(j)$，因此每行也恰好一个 1。

4.2 小阶情形的例子

$S_2$ 的置换矩阵：

\[e \leftrightarrow \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \quad (1\ 2) \leftrightarrow \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\]

$S_3$ 的置换矩阵（与 2.4 节中六个元素按顺序对应）：

\[\sigma_1 \leftrightarrow \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \quad \sigma_2 \leftrightarrow \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}, \quad \sigma_3 \leftrightarrow \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}\] \[\sigma_4 \leftrightarrow \begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}, \quad \sigma_5 \leftrightarrow \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}, \quad \sigma_6 \leftrightarrow \begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix}\]

所有这些矩阵都可以从单位矩阵出发，通过交换行（或列）得到。

对 $S_4$，对应 24 个四阶置换矩阵，与 $S_4$ 的元素一一对应。

4.3 置换矩阵给出群同态

命题：映射 $P: S_n \to GL_n(\mathbb{R})$，$\sigma \mapsto P_\sigma$ 是一个单同态（单射的群同态）。即

\[P_{\tau \circ \sigma} = P_\tau \cdot P_\sigma\]

其中左边是映射复合对应的置换矩阵，右边是矩阵乘法。

证明：

设 $A = P_\sigma$，$B = P_\tau$，$C = P_{\tau \circ \sigma}$。需证 $C = BA$（矩阵乘法）。

验证在每个位置 $(i, j)$ 上两边相等。

$C$ 的 $(i,j)$ 位置：由定义，$c_{ij} = 1$ 当且仅当 $i = (\tau \circ \sigma)(j) = \tau(\sigma(j))$，否则 $c_{ij} = 0$。

$(BA)$ 的 $(i,j)$ 位置：由矩阵乘法定义，

\[(BA)_{ij} = \sum_{k=1}^{n} b_{ik} \cdot a_{kj}\]

由 $A = P_\sigma$ 的定义，$a_{kj} = 1$ 当且仅当 $k = \sigma(j)$，否则 $a_{kj} = 0$。因此求和中只有 $k = \sigma(j)$ 这一项可能非零：

\[(BA)_{ij} = b_{i, \sigma(j)}\]

再由 $B = P_\tau$ 的定义，$b_{i, \sigma(j)} = 1$ 当且仅当 $i = \tau(\sigma(j))$，否则为 0。

这与 $c_{ij}$ 完全一致，因此 $C = BA$。

单射性：若 $P_\sigma = P_\tau$，则对所有 $j$ 有 $\sigma(j) = \tau(j)$（因为矩阵第 $j$ 列中 1 的位置分别在第 $\sigma(j)$ 行和第 $\tau(j)$ 行），故 $\sigma = \tau$。$\blacksquare$

这个置换矩阵的定义方式与图的邻接矩阵、偏序关系的关联矩阵在本质上是一致的：都是将某种组合结构编码为”属于则取 1，不属于则取 0”的矩阵。将置换嵌入矩阵后，可以利用矩阵的加法、乘法、特征值等丰富的代数工具获取更多信息。例如无向图的邻接矩阵是实对称矩阵，可以对角化，其特征值能反映图的很多性质。

五、轮换（循环置换）

5.1 动机

用二行表表示置换时，如果很多元素映到自身（不动点），写出它们就显得多余。例如在 $S_7$ 中，若

\[\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 4 & 3 & 6 & 5 & 2 & 7 \end{pmatrix}\]

则 1, 3, 5, 7 都映到自身，实际发生变动的只有 $2 \mapsto 4 \mapsto 6 \mapsto 2$，形成一个循环。

5.2 轮换记号

上述置换可以简洁地记为

\[(2\ 4\ 6)\]

表示 $2 \mapsto 4$，$4 \mapsto 6$，$6 \mapsto 2$（最后一个元素映回第一个），其余元素不动。这就是轮换（cycle）记号。

使用数字时，建议将各数字之间留出间距或加逗号，以避免与多位数混淆。例如写成 $(2,\, 4,\, 6)$ 或 $(2\ 4\ 6)$，而不是 $(246)$。

5.3 轮换的一般定义

定义：设 $\sigma \in S_n$，若存在 $r$ 个两两不同的元素 $a_0, a_1, \ldots, a_{r-1} \in {1, 2, \ldots, n}$，使得

\[\sigma(a_0) = a_1, \quad \sigma(a_1) = a_2, \quad \ldots, \quad \sigma(a_{r-2}) = a_{r-1}, \quad \sigma(a_{r-1}) = a_0\]

并且对所有 $j \notin {a_0, a_1, \ldots, a_{r-1}}$ 都有 $\sigma(j) = j$，则称 $\sigma$ 是一个 $r$-轮换（$r$-cycle），记为

\[\sigma = (a_0\ a_1\ \cdots\ a_{r-1})\]

轮换记号依赖于上下文：$(2\ 4\ 6)$ 既可以表示 $S_7$ 中的元素，也可以表示 $S_8$ 中的元素（其余元素都不动）。使用时需明确是在哪个 $S_n$ 中讨论。

六、核心内容小结

本章涵盖以下核心知识点：

群同态与群同构的定义和例子（对数函数、行列式）
对称群 $S_n$ 的定义、元素枚举（$ S_n = n!$）、二行表示
$S_3$ 是最小的非交换群
Cayley 定理：任何群都同构于某个对称群的子群
置换矩阵表示及其给出的单同态 $S_n \hookrightarrow GL_n(\mathbb{R})$
轮换（循环置换）记号

群同态与Cayley定理：对称群、置换矩阵与轮换表示