1. 第 9 节 轨道、循环和交错群

这段话的核心思想是，一个排列（可以想象成一种打乱顺序的规则）可以将一个集合分成若干个互不相交的小组，这些小组被称为“单元”或更正式地称为“轨道”。

想象一个班级的学生排队，排列 $\sigma$ 就是一个指令，告诉每个位置上的学生应该去哪个新的位置。比如，原来在第1位的学生跑到第3位，第3位的学生跑到第6位，第6位的学生又跑回第1位。这三个学生（1, 3, 6）就形成了一个封闭的小圈子，他们无论怎么按这个规则换位置，都只会在这三个位置之间打转，永远不会跑到别的位置去。这个小圈子就是一个“单元”。

为了用数学语言精确地描述这个“同属一个圈子”的概念，我们引入了一个关系，用符号 ~ 表示。我们说两个元素 $a$ 和 $b$ 是相关的（记作 $a \sim b$），如果我们可以从 $a$ 出发，通过反复应用这个排列规则 $\sigma$（或者它的逆规则 $\sigma^{-1}$），最终能够到达 $b$。

这里的 $\sigma^{n}(a)$ 就代表对元素 $a$ 应用 $n$ 次排列规则 $\sigma$。

• 如果 $n$ 是正整数，比如 $n=2$，那么 $\sigma^{2}(a) = \sigma(\sigma(a))$，就是连续应用两次规则。
• 如果 $n=0$，那么 $\sigma^{0}(a) = a$，就是什么都不做，元素在原地。
• 如果 $n$ 是负整数，比如 $n=-1$，那么 $\sigma^{-1}(a)$ 就是应用一次逆规则，即找到那个被 $\sigma$ 映射到 $a$ 的元素。

所以，$b=\sigma^{n}(a)$ 意味着 $b$ 和 $a$ 在同一个运动轨迹上，可以相互抵达。这个关系 ~ 将被证明是一个等价关系，而等价关系的一个重要性质就是它能将集合划分成互不相交的等价类，这里的每个等价类就是一个轨道。

为了证明 ~ 是一个等价关系，我们需要验证它满足三个基本性质：自反性、对称性和传递性。

1. 自反性 (Reflexivity): 任何元素都与它自身相关。
   • 原文证明: $a \sim a$ 是因为我们可以取 $n=0$。$\sigma^0(a)$ 定义为 $a$ 本身（即恒等排列 $\iota$ 作用于 $a$），所以 $a = \sigma^0(a)$。这完全符合 $a \sim b \iff b=\sigma^n(a)$ 的定义（这里 $b$ 就是 $a$，$n$ 就是 0）。
   • 通俗解释: 我能从我自己出发到达我自己吗？当然可以，一步都不走就行了（对应 $n=0$）。
2. 对称性 (Symmetry): 如果 $a$ 与 $b$ 相关，那么 $b$ 也必须与 $a$ 相关。
   • 原文证明: 我们假设 $a \sim b$。根据定义，这意味着存在一个整数 $n$ 使得 $b = \sigma^n(a)$。这是一个等式，我们可以对两边同时作用 $\sigma$ 的逆运算 $\sigma^{-n}$。于是，$\sigma^{-n}(b) = \sigma^{-n}(\sigma^n(a))$。根据函数复合的性质，$\sigma^{-n}(\sigma^n(a)) = \sigma^{-n+n}(a) = \sigma^0(a) = a$。所以我们得到 $a = \sigma^{-n}(b)$。因为 $n$ 是整数，所以 $-n$ 也是整数。这就满足了 $b \sim a$ 的定义（这里角色互换，从 $b$ 出发，作用 $-n$ 次 $\sigma$，得到了 $a$）。
   • 通俗解释: 如果我能从 A 镇走到 B 镇（比如沿着公路走 $n$ 公里），那么我也一定能从 B 镇走回 A 镇（沿着同一条公路往回走 $n$ 公里，相当于方向相反，即 $-n$）。
3. 传递性 (Transitivity): 如果 $a$ 与 $b$ 相关，且 $b$ 与 $c$ 相关，那么 $a$ 也必须与 $c$ 相关。
   • 原文证明: 我们假设 $a \sim b$ 并且 $b \sim c$。
   • 从 $a \sim b$，我们知道存在一个整数 $n$ 使得 $b = \sigma^n(a)$。
   • 从 $b \sim c$，我们知道存在一个整数 $m$ 使得 $c = \sigma^m(b)$。
   • 通俗解释: 如果我能从 A 镇走到 B 镇，又能从 B 镇走到 C 镇，那我当然就能从 A 镇一路走到 C 镇。总的路程就是两段路程的叠加。

因为 ~ 满足了这三个性质，所以它是一个合法的等价关系。

定义 9.1:

这里正式给出了轨道的定义。在证明了 ~ 是等价关系后，我们知道它会把集合 $A$ 分割成若干个等价类。一个等价类就是由所有相互关联的元素组成的子集。这个定义直接将“轨道”这个名字赋予了这些等价类。

换句话说，$\sigma$ 的一个轨道是一个子集 $O \subseteq A$，满足两个条件：

1. 对于任何 $a, b \in O$，都有 $a \sim b$。
2. 对于任何 $a \in O$ 和 $c \notin O$，都有 $a \not\sim c$。

这个轨道就是由一个元素以及所有能通过 $\sigma$ 的反复作用（正向或逆向）从它到达的元素所组成的集合。

例子 9.2:

• 排列: 恒等排列 $\iota$，它作用在集合 $A$ 上，效果是 $\iota(a)=a$ 对所有 $a \in A$ 成立。
• 分析: 我们来找一个元素 $a$ 的轨道。这个轨道是所有与 $a$ 相关的元素的集合。一个元素 $b$ 与 $a$ 相关，意味着 $b = \iota^n(a)$ 对某个整数 $n$ 成立。但无论 $n$ 是多少，$\iota^n(a) = a$。所以唯一能与 $a$ 相关的元素就是 $a$ 自己。
• 结论: 每个元素的轨道里只包含它自己。因此，$\iota$ 的轨道就是一系列的单元素子集，如 $\{a_1\}, \{a_2\}, \ldots$。这些子集共同构成了对 $A$ 的划分。

例子 9.3:

• 排列: $\sigma = \left(\begin{array}{llllllll} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 3 & 8 & 6 & 7 & 4 & 1 & 5 & 2 \end{array}\right)$ on $S_8$ (集合是 $\{1, 2, ..., 8\}$)。
• 寻找轨道的过程:

1. 从任意一个元素开始。我们选择 1。
2. 追踪它的路径。
   • $\sigma(1) = 3$
   • $\sigma(3) = 6$
   • $\sigma(6) = 1$
3. 确定第一个轨道。所有在这个环上的元素 $\{1, 3, 6\}$ 构成了第一个轨道。因为它们可以通过 $\sigma$ 的幂次相互到达。例如，$6 = \sigma^2(1)$，$1 = \sigma^{-1}(3)$。
4. 检查是否所有元素都已找到轨道。集合是 $\{1, ..., 8\}$，我们已经处理了 $\{1, 3, 6\}$。还剩下 $\{2, 4, 5, 7, 8\}$。
5. 从剩下的元素中再选一个。我们选择 2。
6. 追踪它的路径。
   • $\sigma(2) = 8$
   • $\sigma(8) = 2$
7. 确定第二个轨道。这个轨道是 $\{2, 8\}$。
8. 再次检查。现在处理过的元素是 $\{1, 3, 6\} \cup \{2, 8\} = \{1, 2, 3, 6, 8\}$。还剩下 $\{4, 5, 7\}$。
9. 从剩下的元素中再选一个。我们选择 4。
10. 追踪它的路径。
    • $\sigma(4) = 7$
    • $\sigma(7) = 5$
    • $\sigma(5) = 4$
11. 确定第三个轨道。这个轨道是 $\{4, 5, 7\}$。
12. 最终检查。所有处理过的元素是 $\{1, 3, 6\} \cup \{2, 8\} \cup \{4, 5, 7\} = \{1, 2, 3, 4, 5, 6, 7, 8\}$。所有元素都已经被分到某个轨道里了。
    • 结论: 该排列 $\sigma$ 的轨道集合是 $\{\{1,3,6\}, \{2,8\}, \{4,5,7\}\}$。这是一个对集合 $\{1, ..., 8\}$ 的划分。

这段话首先设定了讨论的范围：我们现在只关注有限集合上的排列，并且为了方便，直接使用集合 $\{1, 2, ..., n\}$，其上的所有排列构成了对称群 $S_n$。

然后，它重提了例子 9.3 中的排列 $\sigma$，并引入了一种非常直观的可视化方法——轨道图（如图9.4）。

在例子 9.3 中，我们找到了三个轨道：$\{1,3,6\}, \{2,8\}, \{4,5,7\}$。图9.4就是把这三个轨道分别画成了三个圆圈。

• 第一个圆圈: 上面有 1, 3, 6。箭头指示了排列 $\sigma$ 的作用方向：$1 \to 3$, $3 \to 6$, $6 \to 1$。这清晰地展示了轨道 $\{1,3,6\}$ 的内部运作方式。
• 第二个圆圈: 上面有 2, 8。箭头指示 $2 \to 8$, $8 \to 2$。
• 第三个圆圈: 上面有 4, 5, 7。箭头指示 $4 \to 7$, $7 \to 5$, $5 \to 4$。

这种图的优点是它把一个看起来杂乱无章的排列（如双行表示法）的内在结构——即它是由几个独立的、互不干扰的“旋转”组成的——清晰地展现了出来。整个排列 $\sigma$ 的作用，可以被理解成同时在三个独立的转盘上各自进行一次旋转。

图9.5展示了恒等排列中一个元素的轨道图，比如元素1。它只包含一个点，箭头从1指向自己，表示 $\sigma(1)=1$。这是一个只有一个元素的“圆圈”。

这段文字是一个铺垫，它通过可视化的方式，引导我们去关注构成排列的这些基本“建筑模块”——即每个轨道所对应的排列动作。下一个概念“循环”就是对这种单个“旋转”或单个“圆圈”的正式命名和描述。

从轨道到循环排列:

上一段我们将 $\sigma$ 分解成了三个独立的圈。现在我们把目光聚焦到其中一个圈上，比如 $\{1,3,6\}$。我们可以定义一个新的排列，我们称之为 $\mu$，它只执行这一个圈的旋转，而让其他所有元素都保持原地不动。

• $\mu$ 的规则是：$1 \to 3$, $3 \to 6$, $6 \to 1$。
• 对于不在 $\{1,3,6\}$ 里的元素，如 2, 4, 5, 7, 8，规则是 $\mu(x)=x$（保持不动）。
• 用双行表示法写出来，就是公式(3)中的 $\mu$。

循环的定义 (Definition 9.6):

• 一个排列如果能被画成最多只有一个“大圈”（包含多个元素的圈），而其他所有圈都是“小点”（单元素圈/不动点），那么这个排列就被称为一个循环。
• 像上面我们构造的 $\mu$，它的轨道是 $\{1,3,6\}, \{2\}, \{4\}, \{5\}, \{7\}, \{8\}$。只有一个轨道 $\{1,3,6\}$ 包含多于一个元素，所以 $\mu$ 是一个循环。
• 恒等排列 $\iota$ 的所有轨道都是单元素的，它没有包含多于一个元素的轨道（“至多有一个”中的“零个”情况），所以它也是一个循环。
• 循环的长度: 就是那个“大圈”里元素的个数。$\mu$ 的长度是 3。恒等排列的长度是 1。

循环表示法 (Cycle Notation):

双行表示法对于循环来说太啰嗦了，因为它需要把所有不动点也写出来。为此，我们引入一种更简洁的单行表示法。

• 对于上面例子中的循环 $\mu$，我们只写下那个“大圈”里的元素，并按照它们被映射的顺序排列在圆括号里：$(1,3,6)$。
• 解读规则:

1. 括号里的第一个元素 1 映射到第二个元素 3。
2. 第二个元素 3 映射到第三个元素 6。
3. ...以此类推，直到最后一个元素 6，它被映射回第一个元素 1，形成闭环。
4. 任何没有出现在这个括号里的元素，都默认是不动点（即 $\mu(x)=x$）。
   • 这种表示法简洁明了，直接抓住了循环的核心——那个非平凡的轨道。但使用时必须知道我们是在哪个对称群 $S_n$ 中讨论，才能确定哪些元素是默认不动的。

例子 9.7:

• 第一部分: 这部分是将一个循环表示法转换为双行表示法的具体操作。
• 循环: $(1,3,5,4)$ in $S_5$.
• 解读:
• $1 \to 3$
• $3 \to 5$
• $5 \to 4$
• $4 \to 1$
• 数字 2 没有出现，所以 $2 \to 2$ (不动点)。
• 转换为双行表示:
• 上排写出所有元素: $1, 2, 3, 4, 5$。
• 下排写出它们各自的像: $\sigma(1)=3, \sigma(2)=2, \sigma(3)=5, \sigma(4)=1, \sigma(5)=4$。
• 组合起来就是原文中的双行表示。

• 第二部分: 这部分展示了循环表示法的一个重要性质：表示不唯一。
• 观察: $(1,3,5,4), (3,5,4,1), (5,4,1,3), (4,1,3,5)$ 这四个看起来不同的写法，实际上描述的是同一个排列。
• 原因: 循环代表一个“圈”，你可以从圈上的任何一个点开始沿着同一个方向走，最终都会遍历整个圈。
• $(1,3,5,4)$ 从 1 开始：$1 \to 3 \to 5 \to 4 \to 1$。
• $(3,5,4,1)$ 从 3 开始：$3 \to 5 \to 4 \to 1 \to 3$。
• $(5,4,1,3)$ 从 5 开始：$5 \to 4 \to 1 \to 3 \to 5$。
• $(4,1,3,5)$ 从 4 开始：$4 \to 1 \to 3 \to 5 \to 4$。
• 这四个写法定义的对每个元素的映射规则是完全一样的。例如，对于元素1，四个写法都蕴含了 $\sigma(1)=3$。

循环的乘法:

• 核心思想: 循环本身也是排列，而排列之间可以进行函数复合（即乘法）。所以循环之间当然也可以相乘。
• 重要提醒: 两个循环相乘的结果，可能不再是一个循环。回顾循环的定义：至多有一个大于1的轨道。如果两个循环相乘后，产生了两个或更多的大于1的轨道，那么结果就不是一个循环了。下面的例子会展示这一点。

从轨道到循环分解:

我们回到最初的例子 $\sigma = \left(\begin{array}{llllllll} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 3 & 8 & 6 & 7 & 4 & 1 & 5 & 2 \end{array}\right)$。

我们已经知道它的轨道是 $\{1,3,6\}, \{2,8\}, \{4,5,7\}$。

现在，我们为每个轨道写出对应的循环：

• 轨道 $\{1,3,6\}$ 对应循环 $\mu_1 = (1,3,6)$。
• 轨道 $\{2,8\}$ 对应循环 $\mu_2 = (2,8)$。
• 轨道 $\{4,5,7\}$ 对应循环 $\mu_3 = (4,7,5)$。（注意顺序是 $4\to7\to5\to4$）

原文的关键发现是：原始的排列 $\sigma$ 竟然就等于这三个循环的乘积！

$\sigma = \mu_1 \mu_2 \mu_3 = (1,3,6)(2,8)(4,7,5)$。

验证这个等式:

让我们来计算乘积 $(1,3,6)(2,8)(4,7,5)$ 对任意一个元素的作用。

• 作用于 1:
• 先用最右边的 $(4,7,5)$，它不动 1。结果是 1。
• 再用中间的 $(2,8)$，它不动 1。结果是 1。
• 最后用最左边的 $(1,3,6)$，它把 1 映到 3。最终结果是 3。
• 这和 $\sigma(1)=3$ 一致。
• 作用于 2:
• $(4,7,5)$ 不动 2。
• $(2,8)$ 把 2 映到 8。
• $(1,3,6)$ 不动 8。最终结果是 8。
• 这和 $\sigma(2)=8$ 一致。
• 作用于 4:
• $(4,7,5)$ 把 4 映到 7。
• $(2,8)$ 不动 7。
• $(1,3,6)$ 不动 7。最终结果是 7。
• 这和 $\sigma(4)=7$ 一致。

对所有8个元素进行验证，都会发现结果与 $\sigma$ 完全相同。

不相交循环 (Disjoint Cycles):

• 定义: 像 $(1,3,6), (2,8), (4,7,5)$ 这样的一组循环被称为不相交的，因为它们的括号里没有任何共同的数字。换句话说，任何一个元素最多只被其中一个循环“移动”（即不是不动点）。
• 重要性质: 不相交循环的乘法是可交换的。$(1,3,6)(2,8)$ 和 $(2,8)(1,3,6)$ 的结果是完全一样的。这是因为它们作用于完全不同的元素集合，互不干扰。

定理 9.8:

这是本节的第一个核心定理。它将我们从一个例子中观察到的现象，提升到了一个普遍规律：

任何一个有限集上的排列，都可以被唯一地（除了循环的顺序和写法）写成一堆互不相交的循环的乘积。

这个过程，称为排列的循环分解。

直观理解: 这个定理说的是，我们之前把一个复杂机器（排列）拆成几个独立小马达（轨道）的比喻是完全正确的。而这个机器的全部功能，就等于把这几个小马达的功能简单地“并列”在一起。分解一个排列，就是在找这些独立的小马达。

定理9.8的证明:

这个证明思路非常直白，它本质上是将我们之前通过例子归纳出的方法给形式化了。

1. 分解基础: 排列 $\sigma$ 将集合 $A$ 划分成一堆互不相交的轨道 $B_1, B_2, \ldots, B_r$。这是我们之前证明过的。
2. 构造循环: 对每一个轨道 $B_i$，我们构造一个对应的循环 $\mu_i$。这个循环 $\mu_i$ 的规则是：
   • 如果一个元素 $x$ 在轨道 $B_i$ 里面，那么 $\mu_i$ 对它的作用就和原来的 $\sigma$ 一模一样，即 $\mu_i(x) = \sigma(x)$。
   • 如果一个元素 $x$ 不在轨道 $B_i$ 里面，那么 $\mu_i$ 就让它保持不动，即 $\mu_i(x) = x$。
3. 验证乘积: 现在我们来验证 $\sigma$ 是否等于这些循环的乘积 $\mu_1 \mu_2 \cdots \mu_r$。
   • 我们取任意一个元素 $x \in A$。由于轨道是划分，所以 $x$ 必然属于且仅属于某一个轨道，我们称之为 $B_k$。
   • 我们来计算乘积 $(\mu_1 \mu_2 \cdots \mu_r)$ 对 $x$ 的作用。乘法是从右到左的。
   • 当我们计算 $\mu_j(x)$ 时，只要 $j \neq k$，由于 $x \notin B_j$，根据 $\mu_j$ 的定义，$\mu_j(x)=x$。
   • 所以，在这一长串乘积中，只有 $\mu_k$ 会真正“移动” $x$。
   • 计算过程如下：
   • 现在考虑新的元素 $\sigma(x)$。由于 $x \in B_k$，而轨道在 $\sigma$ 作用下是封闭的，所以 $\sigma(x)$ 也必然在 $B_k$ 中。
   • 因此，$\sigma(x)$ 不在任何其他的 $B_j$ ($j \neq k$)中。
   • 所以，当 $\mu_1, \ldots, \mu_{k-1}$ 作用于 $\sigma(x)$ 时，它们也都不会移动它。
   • 最终结果就是 $\sigma(x)$。
   • 我们证明了对于任何 $x$，$(\mu_1 \mu_2 \cdots \mu_r)(x) = \sigma(x)$。所以 $\sigma = \mu_1 \mu_2 \cdots \mu_r$。
4. 不相交性: 因为轨道 $B_i$ 和 $B_j$ (当 $i \neq j$) 是互不相交的集合，所以循环 $\mu_i$ 和 $\mu_j$ 所移动的元素集合也是互不相交的。因此，这些循环是不相交的。证明完毕。

唯一性与交换性:

• 不相交循环的可交换性: 如果有两个不相交的循环 $\alpha$ 和 $\beta$，它们移动的元素集合分别是 $S_\alpha$ 和 $S_\beta$，且 $S_\alpha \cap S_\beta = \emptyset$。
• 考虑 $\alpha\beta(x)$。
• 若 $x \in S_\alpha$，则 $\beta(x)=x$，所以 $\alpha\beta(x)=\alpha(x)$。
• 若 $x \in S_\beta$，则 $\beta(x) \in S_\beta$，所以 $\alpha(\beta(x)) = \beta(x)$。
• 若 $x$ 都不在里面，则 $\alpha\beta(x)=x$。
• 考虑 $\beta\alpha(x)$。
• 若 $x \in S_\alpha$，则 $\alpha(x) \in S_\alpha$，所以 $\beta(\alpha(x)) = \alpha(x)$。
• 若 $x \in S_\beta$，则 $\alpha(x)=x$，所以 $\beta\alpha(x)=\beta(x)$。
• 若 $x$ 都不在里面，则 $\beta\alpha(x)=x$。
• 比较两种顺序的结果，发现对任何 $x$ 都相同。所以 $\alpha\beta = \beta\alpha$。
• 分解的唯一性:
• 一个排列的轨道是由这个排列本身唯一确定的。
• 每个轨道（长度大于1的）唯一地对应一个不相交循环因子。
• 因此，构成这个乘积的这组循环是唯一的。
• 唯一需要注意的是“因子的顺序除外”。因为它们是不相交的，所以可以任意交换顺序，例如 $(1,2)(3,4) = (3,4)(1,2)$。所以我们说这个分解在“除掉顺序影响”的意义下是唯一的。
• （同时，每个循环的写法也不是唯一的，如 $(1,2,3)=(2,3,1)$，但这通常被认为是同一个循环）。

例子 9.9:

这是一个将双行表示的排列分解为不相交循环乘积的完整练习。

• 排列: $\sigma = \left(\begin{array}{llllll} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 5 & 2 & 4 & 3 & 1 \end{array}\right)$。
• 分解步骤:

1. 从1开始: $\sigma(1)=6$, $\sigma(6)=1$。形成一个闭环。得到第一个循环 $(1,6)$。
2. 从未使用的最小数字开始: 2还没用过。$\sigma(2)=5$, $\sigma(5)=3$, $\sigma(3)=2$。形成一个闭环。得到第二个循环 $(2,5,3)$。
3. 从未使用的最小数字开始: 3, 5, 2, 1, 6都用过了。剩下4。$\sigma(4)=4$。这是一个不动点。它对应的循环是 $(4)$，长度为1，通常省略不写。
4. 组合结果: 将找到的所有长度大于1的不相交循环乘在一起，得到 $\sigma = (1,6)(2,5,3)$。
   • 可交换性: 因为 $(1,6)$ 和 $(2,5,3)$ 是不相交的（它们没有共同的数字），所以乘法顺序可以交换：$(1,6)(2,5,3) = (2,5,3)(1,6)$。

例子 9.10:

这是一个计算相交循环乘积的例子，目的是为了展示：

1. 如何计算。
2. 乘积结果可能不是循环。
3. 相交循环的乘法通常不满足交换律。

• 计算第一个乘积: $\sigma_1 = (1,4,5,6)(2,1,5)$。在 $S_6$ 中。

我们逐个计算每个元素的像，牢记乘法从右到左。

• 1: $(2,1,5)$ 把 1 映到 5。然后 $(1,4,5,6)$ 把 5 映到 6。所以 $1 \to 6$。
• 2: $(2,1,5)$ 把 2 映到 1。然后 $(1,4,5,6)$ 把 1 映到 4。所以 $2 \to 4$。
• 3: $(2,1,5)$ 不动 3。然后 $(1,4,5,6)$ 也不动 3。所以 $3 \to 3$。
• 4: $(2,1,5)$ 不动 4。然后 $(1,4,5,6)$ 把 4 映到 5。所以 $4 \to 5$。
• 5: $(2,1,5)$ 把 5 映到 2。然后 $(1,4,5,6)$ 不动 2。所以 $5 \to 2$。
• 6: $(2,1,5)$ 不动 6。然后 $(1,4,5,6)$ 把 6 映到 1。所以 $6 \to 1$。
• 结果: 组合起来就是 $\left(\begin{array}{llllll} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 4 & 3 & 5 & 2 & 1 \end{array}\right)$。
• 我们来分解这个结果：$1 \to 6 \to 1$ (循环 (1,6))；$2 \to 4 \to 5 \to 2$ (循环 (2,4,5))；3是不动点。所以 $\sigma_1 = (1,6)(2,4,5)$。它有两个非平凡轨道，所以不是一个循环。

• 计算第二个乘积（交换顺序）: $\sigma_2 = (2,1,5)(1,4,5,6)$。
• 1: $(1,4,5,6)$ 把 1 映到 4。然后 $(2,1,5)$ 不动 4。所以 $1 \to 4$。
• 2: $(1,4,5,6)$ 不动 2。然后 $(2,1,5)$ 把 2 映到 1。所以 $2 \to 1$。
• 3: 都不动 3。所以 $3 \to 3$。
• 4: $(1,4,5,6)$ 把 4 映到 5。然后 $(2,1,5)$ 把 5 映到 2。所以 $4 \to 2$。
• 5: $(1,4,5,6)$ 把 5 映到 6。然后 $(2,1,5)$ 不动 6。所以 $5 \to 6$。
• 6: $(1,4,5,6)$ 把 6 映到 1。然后 $(2,1,5)$ 把 1 映到 5。所以 $6 \to 5$。
• 结果: 组合起来就是 $\left(\begin{array}{llllll} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 2 & 6 & 5 \end{array}\right)$。
• 我们来分解这个结果：$1 \to 4 \to 2 \to 1$ (循环 (1,4,2))；$5 \to 6 \to 5$ (循环 (5,6))。所以 $\sigma_2 = (1,4,2)(5,6)$。它也不是一个循环。

• 结论:
• $\sigma_1 \neq \sigma_2$。这表明相交循环（这里它们都含有1和5）的乘法不满足交换律。
• 两个乘积结果都不是循环。

基本思想:

开篇的直觉是，任何复杂的排序（比如洗牌），本质上都可以通过一步一步、一次只交换两张牌的位置来完成。本节的目标就是把这个直觉数学化。

对换的定义 (Definition 9.11):

• 对换 (Transposition) 是一个最简单的非平凡循环，其长度为2。
• 例如，$(1,2)$ 是一个对换。它表示 1 和 2 交换位置，其他所有元素都保持不动。
• 在 $S_4$ 中，$(1,2)$ 就是 $\left(\begin{array}{llll} 1 & 2 & 3 & 4 \\ 2 & 1 & 3 & 4 \end{array}\right)$。

将循环分解为对换:

这是一个惊人的发现：任何一个循环，无论多长，都可以被写成一串对换的乘积。原文给出了一个具体的公式：

• 一个长度为 $n$ 的循环 $(a_1, a_2, \ldots, a_n)$ 可以被分解为 $n-1$ 个对换的乘积：$(a_1, a_n)(a_1, a_{n-1})\cdots(a_1, a_3)(a_1, a_2)$。
• 注意: 这个公式里的对换是相交的，它们都含有元素 $a_1$。因此，乘法的顺序非常重要，不能随意交换。

验证这个公式:

我们来验证 $(a_1, a_2, a_3, a_4) = (a_1, a_4)(a_1, a_3)(a_1, a_2)$。

• 作用于 $a_1$:
• 最右边的 $(a_1, a_2)$ 把 $a_1 \to a_2$。
• 中间的 $(a_1, a_3)$ 不动 $a_2$。
• 最左边的 $(a_1, a_4)$ 不动 $a_2$。
• 最终结果是 $a_1 \to a_2$。正确。
• 作用于 $a_2$:
• $(a_1, a_2)$ 把 $a_2 \to a_1$。
• $(a_1, a_3)$ 把 $a_1 \to a_3$。
• $(a_1, a_4)$ 不动 $a_3$。
• 最终结果是 $a_2 \to a_3$。正确。
• 作用于 $a_3$:
• $(a_1, a_2)$ 不动 $a_3$。
• $(a_1, a_3)$ 把 $a_3 \to a_1$。
• $(a_1, a_4)$ 把 $a_1 \to a_4$。
• 最终结果是 $a_3 \to a_4$。正确。
• 作用于 $a_4$:
• $(a_1, a_2)$ 不动 $a_4$。
• $(a_1, a_3)$ 不动 $a_4$。
• $(a_1, a_4)$ 把 $a_4 \to a_1$。
• 最终结果是 $a_4 \to a_1$。正确。

公式是有效的。

推论 9.12:

这是一个逻辑上的层层递进：

1. 定理 9.8: 任何排列都可以分解为不相交循环的乘积。
2. 本节公式: 任何循环都可以分解为对换的乘积。
3. 结论 (推论 9.12): 将 1 和 2 结合起来，任何排列都可以分解为对换的乘积。
   • 过程: 给定一个排列 $\sigma$。
   • 第一步：将其分解为不相交循环 $\sigma = \mu_1 \mu_2 \cdots \mu_k$。
   • 第二步：将每个循环 $\mu_i$ 再分解为一串对换。
   • 最终，$\sigma$ 就变成了一长串对换的乘积。

直观解释: 这个推论为本节开头的直觉提供了严格的数学证明。任何复杂的重新排序，确实都可以通过一系列两两交换的操作来完成。对换是排列世界里的最基本“原子”操作。

例子 9.13:

这个例子是上一节推导的具体化。

• 排列: $\sigma = (1,6)(2,5,3)$。
• 分解:
• 因子 $(1,6)$ 已经是一个对换，不用再分。
• 因子 $(2,5,3)$ 是一个长度为3的循环。根据公式 $(a_1,a_2,a_3) = (a_1,a_3)(a_1,a_2)$，我们得到 $(2,5,3) = (2,3)(2,5)$。
• 把它们放在一起，$\sigma = (1,6)(2,3)(2,5)$。
• 结论: 这个排列可以表示为 3 个对换的乘积。

例子 9.14:

这个例子展示了如何表示最简单的排列——恒等排列 $\iota$。

• 恒等排列 $\iota$ 的作用是让所有元素保持不动。
• 对换分解: 我们可以用任何一个对换和它自己相乘来得到恒等排列。例如 $(1,2)(1,2)$。
• 验证: 先用右边的 $(1,2)$，它交换1和2。再用左边的 $(1,2)$，它又把1和2交换回来。最终所有元素都回到了原位。
• 推广: 任何对换 $\tau$ 都有 $\tau^2 = \iota$。所以 $\iota = \tau \tau$。
• 结论: 恒等排列可以表示为 2 个对换的乘积。

奇偶性的引出:

这段文字是本节，乃至本章的一个关键转折点。

• 事实1: 分解不唯一: 我们已经知道，一个排列的对换分解方式不是唯一的。比如：
• $\iota = (1,2)(1,2)$ (2个对换)
• $\iota = (1,3)(1,3)$ (2个对换)
• $\iota = (1,2)(1,2)(3,4)(3,4)$ (4个对换)
• 事实2: 关键的不变量: 尽管分解方式和对换的数量不唯一，但作者断言，数量的奇偶性 (parity) 是唯一确定的，是一个不变量。
• 对于恒等排列 $\iota$，我们上面给出的分解都用了偶数个（2个，4个）对换。作者断言，你永远不可能把 $\iota$ 写成奇数个对换的乘积。
• 对于例子9.13中的 $\sigma$，我们找到了一个含3个对换的分解。作者断言，虽然它可能有其他分解方式，但那些分解的对换个数必然是5个、7个、1个... 始终是奇数。
• 重要性: 这个“奇偶性守恒”的事实非常重要，它允许我们对排列进行一种深刻的二元分类：
• 偶排列: 可以写成偶数个对换乘积的排列。
• 奇排列: 可以写成奇数个对换乘积的排列。

接下来的定理9.15将要严格证明这个断言。

定理 9.15:

这是本节的中心定理。它用严格的语言陈述了上一段的断言：一个排列的“奇偶性”是其内在的、明确的属性。不可能存在一个排列 $\sigma$，它既能被写成 4 个对换的乘积，又能被写成 5 个对换的乘积。

证明 1 (线性代数方法):

这是一个非常巧妙的“借用外力”的证明，它利用了线性代数中行列式的性质。

1. 切换视角: 我们不直接研究数字 $\{1, \ldots, n\}$ 的排列，而是研究 $n \times n$ 单位矩阵 $I_n$ 的行向量的排列。这两个问题是同构的（结构完全一样）。
   • 单位矩阵 $I_n$:
2. 引入不变量: 我们使用的“不变量”或“检测器”是行列式 (determinant)。我们知道单位矩阵的行列式是 $\det(I_n) = 1$。
3. 核心性质: 线性代数有一个基本定理：交换一个矩阵的任意两行，其行列式的值会变号（乘以 -1）。
4. 建立联系:
   • 一个作用于 $\{1, \ldots, n\}$ 的排列 $\sigma$，可以对应一个作用于 $I_n$ 行向量的排列操作。这个操作会产生一个新的排列矩阵 $C$。例如，如果 $\sigma=(1,2)$，那么 $C$ 就是交换 $I_n$ 的第一行和第二行得到的矩阵。
   • 排列中的一个对换，就对应于对矩阵做一次行交换。
5. 逻辑推导:
   • 假设存在一个排列 $\sigma$ 既可以表示为偶数个（比如 $2k$ 个）对换的乘积，又可以表示为奇数个（比如 $2m+1$ 个）对换的乘积。
   • 这意味着排列矩阵 $C$ 既可以通过对 $I_n$ 进行 $2k$ 次行交换得到，也可以通过 $2m+1$ 次行交换得到。
   • 从偶数次交换来看: $\det(C) = \det(I_n) \times (-1)^{2k} = 1 \times 1 = 1$。
   • 从奇数次交换来看: $\det(C) = \det(I_n) \times (-1)^{2m+1} = 1 \times (-1) = -1$。
   • 于是我们得出了一个矛盾的结论：$\det(C)$ 必须同时等于 1 和 -1。这是绝对不可能的。
6. 结论: 既然假设导致了矛盾，那么假设本身就是错误的。因此，任何排列不可能既是偶数个对换的积，又是奇数个对换的积。定理得证。

这个证明完全在群论内部，不依赖其他学科。其核心思想是研究一个排列左乘一个对换后，其轨道数量会发生什么变化。

核心论断: 令 $\sigma$ 是一个排列，$\tau$ 是一个对换。那么新排列 $\tau\sigma$ 的轨道数，与旧排列 $\sigma$ 的轨道数，恰好相差 1（要么多1，要么少1）。

为了证明这个论断，分两种情况讨论对换 $\tau=(i,j)$ 中的两个元素 $i$ 和 $j$ 在排列 $\sigma$ 中的位置关系。

情况 1: $i$ 和 $j$ 在 $\sigma$ 的不同轨道中

• 想象 $\sigma$ 的轨道图是几个不相交的圈。$i$ 在一个圈上，$j$ 在另一个圈上。
• 我们可以把 $\sigma$ 写成不相交循环的乘积，形式为 $\sigma = \cdots (a, i, \ldots) \cdots (b, j, \ldots) \cdots$。其中 $\sigma(a)=i$ 且 $\sigma(b)=j$（这里原文的写法 $(b,j,...)(a,i,...)$ 意味着 $\sigma(i)$ 是 $i$ 在循环中的后继，$\sigma^{-1}(i) = a$。我们按原文的循环写法 $(a, i, \dots)$ 来理解，意为 $\dots \to a \to i \to \dots$）。让我们按更常规的写法来分析，$\sigma$ 的一部分是 $(..., a, i, ...)$ 和 $(..., b, j, ...)$。
• 计算 $\tau\sigma = (i,j)\sigma$ 的效果：
• 在 $\sigma$ 中，$a \to i$ 且 $b \to j$。
• 在 $\tau\sigma$ 中：
• $a$ 的像: $(i,j)\sigma(a) = (i,j)(i) = j$。所以 $a \to j$。
• $b$ 的像: $(i,j)\sigma(b) = (i,j)(j) = i$。所以 $b \to i$。
• 效果: 原来从 $a$ 出发的链条 $... \to a \to i \to ...$ 和从 $b$ 出发的链条 $... \to b \to j \to ...$ 被“嫁接”了：现在 $a \to j$ 连接到了第二条链，而 $b \to i$ 连接到了第一条链。
• 结果: 如图9.16所示，两个独立的圈被合并成了一个更大的圈。轨道数量减 1。
• 原文的计算:

$(i, j)(b, j, \dots, c)(a, i, \dots, d) = (a, j, \dots, c, b, i, \dots, d)$ (这里我补全了循环的尾部方便理解)。

• 验证:
• $a \to i$ (被右循环) $\to j$ (被左对换)。
• $j \to \dots \to c$ (被中循环) $\to c$ (被左对换)。
• $c \to b$ (被中循环) $\to b$ (被左对换)。
• $b \to j$ (被中循环) $\to i$ (被左对换)。
• $i \to \dots \to d$ (被右循环) $\to d$ (被左对换)。
• $d \to a$ (被右循环) $\to a$ (被左对换)。
• 这形成了一个新的大循环，证明了合并。

情况 2: $i$ 和 $j$ 在 $\sigma$ 的同一个轨道中

• 想象 $i$ 和 $j$ 在同一个圈上。
• $\sigma$ 的一部分可以写成一个长循环 $(..., a, i, ..., b, j, ...)$，其中 $\sigma(a)=i, \sigma(b)=j$。
• 计算 $\tau\sigma = (i,j)\sigma$ 的效果：
• 在 $\sigma$ 中，$a \to i$ 且 $b \to j$。
• 在 $\tau\sigma$ 中：
• $a$ 的像: $(i,j)\sigma(a) = (i,j)(i) = j$。所以现在是 $a \to j$。
• $b$ 的像: $(i,j)\sigma(b) = (i,j)(j) = i$。所以现在是 $b \to i$。
• 效果: 原来的大圈在 $i$ 和 $j$ 之间被“剪开”，并重新“接线”。从 $a$ 出发的链条 $... \to a$ 现在连接到了 $j$ ( $a \to j$)，而 $j$ 原来的后继现在独立了。从 $b$ 出发的链条 $... \to b$ 现在连接到了 $i$ ($b \to i$)。
• 结果: 如图9.17所示，一个大圈分裂成了两个较小的圈。轨道数量加 1。
• 原文的计算:

$(i, j)(a, i, \dots, b, j, \dots, c) = (a, j, \dots, c)(b, i, \dots)$。

• 验证:
• $a \to i$ (被长循环) $\to j$ (被对换)。
• $j \to \dots \to c$ (被长循环) $\to c$ (被对换)。
• $c \to a$ (被长循环) $\to a$ (被对换)。形成第一个循环 $(a, j, \dots, c)$。
• $b \to j$ (被长循环) $\to i$ (被对换)。
• $i \to \dots$ (被长循环) $\to \dots$ (被对换)。形成第二个循环 $(b, i, \dots)$。
• 这证明了分裂。

完成证明:

1. 我们证明了每左乘一个对换，排列的轨道数就会改变1（+1或-1）。这意味着，轨道数的奇偶性会反转。
2. 考虑恒等排列 $\iota$。它有 $n$ 个轨道（每个元素自成一轨）。
3. 一个排列 $\sigma$ 可以写成 $m$ 个对换的乘积：$\sigma = \tau_m \cdots \tau_2 \tau_1 \iota$。
4. 从 $\iota$ 开始，它有 $n$ 个轨道。
   • 乘以 $\tau_1$ 后，得到 $\tau_1 \iota$，轨道数变为 $n \pm 1$。
   • 乘以 $\tau_2$ 后，得到 $\tau_2\tau_1\iota$，轨道数变为 $n \pm 1 \pm 1$。
   • ...
   • 乘以 $\tau_m$ 后，得到 $\sigma$，其轨道数 $N(\sigma)$ 为 $n$ 经过 $m$ 次加一或减一。
5. 所以 $N(\sigma) \equiv n - m \pmod{2}$。这意味着 $m \equiv n - N(\sigma) \pmod{2}$。
6. 对于一个给定的排列 $\sigma$，它的轨道数 $N(\sigma)$ 是唯一确定的。$n$ 也是固定的。因此，$n-N(\sigma)$ 的值是确定的。
7. 这意味着 $m$ 的奇偶性是由 $\sigma$ 唯一决定的。它不可能既是偶数又是奇数。证明完毕。

定义 9.18:

在证明了奇偶性唯一（定理9.15）之后，我们现在可以放心地给排列贴上“偶”或“奇”的标签了。

• 偶排列 (Even Permutation): 如果一个排列可以被写成偶数个对换的乘积，它就是偶排列。
• 奇排列 (Odd Permutation): 如果一个排列可以被写成奇数个对换的乘积，它就是奇排列。

定理9.15保证了这个定义是明确的（well-defined），一个排列不可能既是偶排列又是奇排列。

例子 9.19:

这个例子给出了判断奇偶性的具体应用。

• 恒等排列 $\iota$:
• 在 $S_n$ ($n \ge 2$) 中，$\iota$ 可以写成 $(1,2)(1,2)$，这是 2 个对换的乘积。2 是偶数，所以 $\iota$ 是偶排列。
• 这是一个普遍规律：$\iota$ 总是偶排列。（也可以认为它由0个对换组成，0是偶数）。
• 边界情况 $n=1$：$S_1$ 只包含恒等排列。这时无法写出 $(1,2)(1,2)$。在这种情况下，我们通过定义规定 $\iota$ 是偶排列，以保持理论的统一性。
• 排列 $(1,4,5,6)(2,1,5)$:
• 这是一个在例子9.10中出现过的相交循环的乘积。要判断它的奇偶性，我们不能直接看它由几个循环组成，而是要把它彻底分解为对换。
• 分解步骤:

1. 分解第一个循环 $(1,4,5,6)$。这是长度为4的循环，根据公式 $(a_1,a_4)(a_1,a_3)(a_1,a_2)$，它分解为 $(1,6)(1,5)(1,4)$。这是 3 个对换。
2. 分解第二个循环 $(2,1,5)$。这是长度为3的循环，分解为 $(2,5)(2,1)$。这是 2 个对换。
3. 将所有对换组合在一起，得到 $(1,6)(1,5)(1,4)(2,5)(2,1)$。
   • 计数: 总共有 $3+2=5$ 个对换。
   • 结论: 5 是奇数，所以这个排列是奇排列。

一个更快的判断方法:

一个长度为 $k$ 的循环可以分解为 $k-1$ 个对换。

• 如果 $k$ 是奇数，那么 $k-1$ 是偶数。所以奇数长度的循环是偶排列。例如 $(1,2,3)$ 是偶排列。
• 如果 $k$ 是偶数，那么 $k-1$ 是奇数。所以偶数长度的循环是奇排列。例如 $(1,2,3,4)$ 是奇排列。

对于一个分解为不相交循环的排列 $\sigma = \mu_1 \mu_2 \cdots \mu_r$，其中 $\mu_i$ 的长度是 $k_i$。

$\sigma$ 的对换总数是 $(k_1-1) + (k_2-1) + \cdots + (k_r-1)$。

$\sigma$ 是偶排列 $\iff \sum (k_i-1)$ 是偶数。

$\sigma$ 是奇排列 $\iff \sum (k_i-1)$ 是奇数。

让我们用这个快速方法重新判断例子中的排列 $\sigma = (1,4,5,6)(2,1,5)$。

注意！这个方法只适用于不相交循环的乘积。而例子中的循环是相交的。所以我们必须先算出乘积的不相交循环形式。

在例子9.10中，我们已经算出 $(1,4,5,6)(2,1,5) = (1,6)(2,4,5)$。

现在应用快速方法：

• 循环 $(1,6)$ 的长度是 2 (偶数)，所以它是奇排列 (2-1=1个对换)。
• 循环 $(2,4,5)$ 的长度是 3 (奇数)，所以它是偶排列 (3-1=2个对换)。
• 整个排列的奇偶性是 "奇" + "偶" = "奇"。
• 总对换数是 $1+2=3$ 个。3是奇数，所以是奇排列。

这与原文通过直接分解得到的结论（5个对换，奇排列）一致。尽管具体数量不同（3 vs 5），但奇偶性是相同的。

核心论点: 在一个排列群 $S_n$ (当 $n \ge 2$) 中，偶排列和奇排列各占一半。总的排列数是 $n!$，所以偶、奇排列各有 $n!/2$ 个。

证明策略:

为了证明两个有限集合 $A_n$ (偶排列集) 和 $B_n$ (奇排列集) 的大小相等，最经典的方法是构造一个从 $A_n$ 到 $B_n$ 的双射（即一一对应的函数）。一个函数是双射，当且仅当它既是单射（一对一）又是满射。

证明步骤:

1. 定义集合:
   • $A_n = \{\sigma \in S_n \mid \sigma \text{ 是偶排列}\}$
   • $B_n = \{\sigma \in S_n \mid \sigma \text{ 是奇排列}\}$
   • 我们知道 $S_n = A_n \cup B_n$ 且 $A_n \cap B_n = \emptyset$。
2. 构造函数:
   • 我们需要一个能把偶排列变成奇排列的“转换器”。最简单的这种转换器就是左乘一个对换（一个奇排列）。
   • 我们选择一个固定的对换，比如 $\tau=(1,2)$（因为 $n \ge 2$，所以这样的对换一定存在）。
   • 定义函数 $\lambda_\tau: A_n \to B_n$ 为 $\lambda_\tau(\sigma) = \tau\sigma$。
3. 验证函数的目标域 (Codomain):
   • 我们需要确保这个函数确实把 $A_n$ 中的元素映到了 $B_n$ 中。
   • 如果 $\sigma \in A_n$，意味着 $\sigma$ 是偶数个对换的积。
   • 那么 $\tau\sigma = (1,2)\sigma$ 就是 (1个对换) + (偶数个对换) = 奇数个对换的积。
   • 所以 $\tau\sigma$ 确实是一个奇排列，即 $\tau\sigma \in B_n$。函数定义合理。
4. 证明单射性 (Injectivity / One-to-one):
   • 假设 $\lambda_\tau(\sigma_1) = \lambda_\tau(\sigma_2)$ 对于 $\sigma_1, \sigma_2 \in A_n$。
   • 根据定义，这意味着 $\tau\sigma_1 = \tau\sigma_2$。
   • 因为 $S_n$ 是一个群，满足左消去律。我们可以在等式两边同时左乘 $\tau^{-1}$。
   • $\tau^{-1}(\tau\sigma_1) = \tau^{-1}(\tau\sigma_2) \implies (\tau^{-1}\tau)\sigma_1 = (\tau^{-1}\tau)\sigma_2 \implies \iota\sigma_1 = \iota\sigma_2 \implies \sigma_1 = \sigma_2$。
   • 这证明了如果像相同，那么原像也必定相同。所以 $\lambda_\tau$ 是单射。
5. 证明满射性 (Surjectivity / Onto):
   • 我们需要证明对于 $B_n$ 中的任意一个奇排列 $\rho$，都能在 $A_n$ 中找到一个偶排列 $\sigma$，使得 $\lambda_\tau(\sigma) = \rho$。
   • 也就是要解方程 $\tau\sigma = \rho$。
   • 同样，在等式两边左乘 $\tau^{-1}$，得到 $\sigma = \tau^{-1}\rho$。
   • 现在需要验证这个“解” $\sigma = \tau^{-1}\rho$ 是否真的在定义域 $A_n$ 中。
   • $\rho$ 是奇排列。
   • $\tau=(1,2)$ 是一个对换，所以 $\tau^{-1}=(1,2)$ 也是一个对换（奇排列）。
   • $\sigma = \tau^{-1}\rho$ 的奇偶性是 ("奇") + ("奇") = "偶"。
   • 所以 $\sigma = \tau^{-1}\rho$ 确实是一个偶排列，它在 $A_n$ 中。
   • 我们找到了原像！即对于任何 $\rho \in B_n$，它的原像是 $\tau^{-1}\rho \in A_n$。
   • 这证明了 $\lambda_\tau$ 是满射。
6. 结论:
   • 因为 $\lambda_\tau$ 既是单射又是满射，所以它是一个双射。
   • 存在一个从 $A_n$ 到 $B_n$ 的一一对应关系，这意味着这两个集合的元素数量必须相等。
   • $|A_n| = |B_n|$。
   • 又因为 $|A_n| + |B_n| = |S_n| = n!$，所以 $|A_n| = |B_n| = n!/2$。

证明偶排列集合构成子群:

为了证明偶排列的集合 $A_n$ 是对称群 $S_n$ 的一个子群，我们需要根据子群的定义（或等价的子群判别法，如定理5.14）验证三个条件：

1. 封闭性 (Closure):
   • 取任意两个偶排列 $\sigma_1, \sigma_2 \in A_n$。
   • $\sigma_1$ 可以写成偶数个（比如 $2k$ 个）对换的积。
   • $\sigma_2$ 可以写成偶数个（比如 $2m$ 个）对换的积。
   • 它们的乘积 $\sigma_1\sigma_2$ 就是 $(2k \text{个对换}) \times (2m \text{个对换}) = (2k+2m)$ 个对换的积。
   • 因为 $2k+2m = 2(k+m)$ 是一个偶数，所以 $\sigma_1\sigma_2$ 也是一个偶排列。
   • 因此，偶排列的集合在排列乘法下是封闭的。
2. 单位元 (Identity):
   • 群 $S_n$ 的单位元是恒等排列 $\iota$。
   • 我们需要验证 $\iota$ 是否在 $A_n$ 中。
   • 正如例子9.19所示，对于 $n \ge 2$，$\iota = (1,2)(1,2)$。它由 2 个对换组成，2是偶数。
   • 所以 $\iota$ 是一个偶排列，$\iota \in A_n$。
3. 逆元 (Inverse):
   • 取任意一个偶排列 $\sigma \in A_n$。我们需要证明它的逆元 $\sigma^{-1}$ 也在 $A_n$ 中。
   • 假设 $\sigma = \tau_1 \tau_2 \cdots \tau_{2k}$，其中 $\tau_i$ 是对换，$2k$ 是偶数。
   • 我们知道乘积的逆等于逆的倒序乘积：
   • 因为每个 $\tau_i$ 都是对换，所以它的逆就是它自己：$\tau_i^{-1} = \tau_i$。
   • 所以 $\sigma^{-1} = \tau_{2k} \cdots \tau_2 \tau_1$。
   • 这表明 $\sigma^{-1}$ 也是由同样 $2k$ 个对换（只是顺序相反）构成的。因为 $2k$ 是偶数，所以 $\sigma^{-1}$ 也是一个偶排列。
   • 因此，任何偶排列的逆元也是偶排列。

定理 9.20:

综合以上三点（封闭性、单位元、逆元），根据子群的定义，我们得出结论：所有偶排列组成的集合 $A_n$ 确实是 $S_n$ 的一个子群。

我们上一节已经证明了这个集合的大小（阶）是 $n!/2$。

所以这个定理是前面所有讨论的顶峰。

定义 9.21:

这个子群非常重要，所以我们给它一个专门的名字：交错群 (Alternating Group)，记作 $A_n$。

重要性:

最后一段文字点出了 $A_n$ 和 $S_n$ 在数学中的核心地位。

• 凯莱定理 (Cayley's Theorem): 这是抽象代数中的一个基本定理，它说任何一个有限群，无论它看起来多么抽象，都可以在一个足够大的对称群 $S_n$ 中找到一个和它结构完全一样的子群（即与一个子群同构）。这说明对称群是研究所有有限群的“万能舞台”。
• 伽罗瓦理论 (Galois Theory): 这是一个更深刻的领域，它将群论和解多项式方程联系起来。为什么二次方程有求根公式，而五次及以上的一般方程没有“根式”求根公式？答案惊人地隐藏在交错群 $A_n$ ($n \ge 5$) 的结构之中。（具体来说，是因为当 $n \ge 5$ 时，$A_n$ 是一个单群，它没有非平凡的正规子群，这导致了对应的伽罗瓦群不可解）。

这组习题要求应用本章开头学习的轨道寻找算法。对于给定的排列 $\sigma$ 和集合 $A$，轨道寻找的步骤是：

1. 从集合 $A$ 中选择一个尚未被分配到任何轨道的元素，称之为 $x$。
2. 计算 $x$ 在 $\sigma$ 下的轨迹：$x, \sigma(x), \sigma^2(x), \ldots$，直到轨迹回到一个已经出现过的元素（对于有限集，必然是回到 $x$）。
3. 这个轨迹上的所有元素构成一个轨道。
4. 重复步骤 1-3，直到集合 $A$ 中所有元素都被分配完毕。

习题4-6的特殊性：

这三道题的集合是无限集 $\mathbb{Z}$（全体整数）。这意味着轨迹可能永远不会“回到起点”。我们需要寻找在这种情况下轨道的含义。根据定义，$a \sim b$ 当且仅当 $b = \sigma^n(a)$ for some $n \in \mathbb{Z}$。

• 习题1: $A=\{1,2,3,4,5,6\}$
• 从 1 开始: $1 \to 5 \to 2 \to 1$。轨道是 $\{1, 2, 5\}$。
• 剩下的元素是 $\{3,4,6\}$。从 3 开始: $3 \to 3$。轨道是 $\{3\}$。
• 剩下的元素是 $\{4,6\}$。从 4 开始: $4 \to 6 \to 4$。轨道是 $\{4, 6\}$。
• 所有轨道是: $\{1, 2, 5\}, \{3\}, \{4, 6\}$。

• 习题2: $A=\{1,2,3,4,5,6,7,8\}$
• 从 1 开始: $1 \to 5 \to 8 \to 7 \to 1$。轨道是 $\{1, 5, 8, 7\}$。
• 从 2 开始: $2 \to 6 \to 3 \to 2$。轨道是 $\{2, 3, 6\}$。
• 从 4 开始: $4 \to 4$。轨道是 $\{4\}$。
• 所有轨道是: $\{1, 5, 8, 7\}, \{2, 3, 6\}, \{4\}$。

• 习题3: $A=\{1,2,3,4,5,6,7,8\}$
• 从 1 开始: $1 \to 2 \to 3 \to 5 \to 4 \to 1$。轨道是 $\{1, 2, 3, 4, 5\}$。
• 从 6 开始: $6 \to 6$。轨道是 $\{6\}$。
• 从 7 开始: $7 \to 8 \to 7$。轨道是 $\{7, 8\}$。
• 所有轨道是: $\{1, 2, 3, 4, 5\}, \{6\}, \{7, 8\}$。

• 习题4: $\sigma(n)=n+1$ on $\mathbb{Z}$。
• 从 0 开始: $\ldots \to -2 \to -1 \to 0 \to 1 \to 2 \to \ldots$。
• $\sigma^k(0) = k$。对于任何整数 $k$，我们都可以通过 $\sigma$ 的 $k$ 次幂从 0 到达 $k$。
• 这意味着任何整数 $m$ 和 $k$ 都是相关的，因为 $m = \sigma^{m-k}(k)$。
• 因此，所有整数都在同一个轨道里。
• 只有一个轨道: $\mathbb{Z}$。

• 习题5: $\sigma(n)=n+2$ on $\mathbb{Z}$。
• 从 0 开始: $\ldots \to -4 \to -2 \to 0 \to 2 \to 4 \to \ldots$。这个轨迹只包含所有的偶数。
• $\sigma^k(0) = 2k$。所以 0 只与所有偶数相关。
• 从 1 开始: $\ldots \to -3 \to -1 \to 1 \to 3 \to 5 \to \ldots$。这个轨迹只包含所有的奇数。
• 因此，存在两个轨道：
• $O_1 = \{\ldots, -2, 0, 2, \ldots\}$ (所有偶数)。
• $O_2 = \{\ldots, -1, 1, 3, \ldots\}$ (所有奇数)。

• 习题6: $\sigma(n)=n-3$ on $\mathbb{Z}$。
• 这和 $\sigma(n)=n+c$ 的情况类似。一个整数 $m$ 和 $k$ 相关，当且仅当 $m-k$ 是 3 的倍数。
• 这等价于模 3 同余。$m \sim k \iff m \equiv k \pmod 3$。
• 因此，有三个轨道，分别是模 3 的三个同余类：
• $O_0 = \{\ldots, -3, 0, 3, 6, \ldots\}$ (3的倍数)
• $O_1 = \{\ldots, -2, 1, 4, 7, \ldots\}$ (除以3余1)
• $O_2 = \{\ldots, -1, 2, 5, 8, \ldots\}$ (除以3余2)

这组习题要求计算循环的乘积。关键在于要记住两点：

1. 排列的乘法是函数复合，其运算顺序是从右到左。
2. 为了得到最终结果，我们需要追踪集合中每个元素的“旅程”，看它经过一连串循环的作用后最终被映射到哪里。最终结果应该写成不相交循环的乘积形式。

解题步骤:

1. 选择集合中的一个元素（通常从1开始）。
2. 将该元素从最右边的循环开始，依次向左传递，计算它在每个循环作用下的像。
3. 记录下它的最终位置。
4. 取上一步得到的“最终位置”作为新的起始元素，重复步骤2-3，直到轨迹形成一个闭环（回到最初的起始元素）。
5. 将这个闭环写成一个循环。
6. 从尚未出现在已找到循环中的最小数字开始，重复步骤1-5，直到所有元素都被追踪完毕。

习题 7: 计算 $(1,4,5)(7,8)(2,5,7)$ 在 $S_8$ 中。

• 追踪 1: $1 \xrightarrow{(2,5,7)} 1 \xrightarrow{(7,8)} 1 \xrightarrow{(1,4,5)} 4$. 所以 $1 \to 4$。
• 追踪 4: $4 \xrightarrow{(2,5,7)} 4 \xrightarrow{(7,8)} 4 \xrightarrow{(1,4,5)} 5$. 所以 $4 \to 5$。
• 追踪 5: $5 \xrightarrow{(2,5,7)} 7 \xrightarrow{(7,8)} 8 \xrightarrow{(1,4,5)} 8$. 所以 $5 \to 8$。
• 追踪 8: $8 \xrightarrow{(2,5,7)} 8 \xrightarrow{(7,8)} 7 \xrightarrow{(1,4,5)} 7$. 所以 $8 \to 7$。
• 追踪 7: $7 \xrightarrow{(2,5,7)} 2 \xrightarrow{(7,8)} 2 \xrightarrow{(1,4,5)} 2$. 所以 $7 \to 2$。
• 追踪 2: $2 \xrightarrow{(2,5,7)} 5 \xrightarrow{(7,8)} 5 \xrightarrow{(1,4,5)} 1$. 所以 $2 \to 1$。

形成了一个闭环。我们得到了第一个循环：$(1, 4, 5, 8, 7, 2)$。

• 检查剩余元素: 3 和 6。
• 追踪 3: $3 \xrightarrow{(2,5,7)} 3 \xrightarrow{(7,8)} 3 \xrightarrow{(1,4,5)} 3$. 3 是不动点。
• 追踪 6: $6 \xrightarrow{(2,5,7)} 6 \xrightarrow{(7,8)} 6 \xrightarrow{(1,4,5)} 6$. 6 是不动点。
• 最终结果: $(1, 4, 5, 8, 7, 2)$。

习题 8: 计算 $(1,3,2,7)(4,8,6)$ 在 $S_8$ 中。

• 这两个循环是不相交的，因为它们的括号内没有共同的元素。
• 不相交循环的乘积就是它们自身，并且乘法顺序是可交换的。
• 这个表达式已经是最终的、最简的不相交循环分解形式了。
• 最终结果: $(1,3,2,7)(4,8,6)$。

习题 9: 计算 $(1,2)(4,7,8)(2,1)(7,2,8,1,5)$ 在 $S_8$ 中。这是一个复杂的相交循环乘积。

• 追踪 1: $1 \xrightarrow{(7,2,8,1,5)} 5 \xrightarrow{(2,1)} 5 \xrightarrow{(4,7,8)} 5 \xrightarrow{(1,2)} 5$. 所以 $1 \to 5$。
• 追踪 5: $5 \xrightarrow{(7,2,8,1,5)} 7 \xrightarrow{(2,1)} 7 \xrightarrow{(4,7,8)} 8 \xrightarrow{(1,2)} 8$. 所以 $5 \to 8$。
• 追踪 8: $8 \xrightarrow{(7,2,8,1,5)} 1 \xrightarrow{(2,1)} 2 \xrightarrow{(4,7,8)} 2 \xrightarrow{(1,2)} 1$. 所以 $8 \to 1$。

形成闭环，得到第一个循环：$(1, 5, 8)$。

• 检查剩余元素: 2, 3, 4, 6, 7。从未使用的最小数字 2 开始。
• 追踪 2: $2 \xrightarrow{(7,2,8,1,5)} 8 \xrightarrow{(2,1)} 8 \xrightarrow{(4,7,8)} 4 \xrightarrow{(1,2)} 4$. 所以 $2 \to 4$。
• 追踪 4: $4 \xrightarrow{(7,2,8,1,5)} 4 \xrightarrow{(2,1)} 4 \xrightarrow{(4,7,8)} 7 \xrightarrow{(1,2)} 7$. 所以 $4 \to 7$。
• 追踪 7: $7 \xrightarrow{(7,2,8,1,5)} 2 \xrightarrow{(2,1)} 1 \xrightarrow{(4,7,8)} 1 \xrightarrow{(1,2)} 2$. 所以 $7 \to 2$。

形成闭环，得到第二个循环：$(2, 4, 7)$。

• 检查剩余元素: 3, 6。
• 追踪 3: 所有循环都不包含3，所以 3 是不动点。
• 追踪 6: 所有循环都不包含6，所以 6 是不动点。
• 最终结果: $(1, 5, 8)(2, 4, 7)$。

这组习题要求进行两种分解：

1. 分解为不相交循环: 这和寻找轨道是同一个过程。找到每个轨道，然后将每个轨道写成对应的循环表示法。
2. 分解为对换: 在第一步的基础上，再将每个循环分解为对换的乘积。一个长度为 $k$ 的循环 $(a_1, a_2, \ldots, a_k)$ 可以分解为 $k-1$ 个对换，一个常用的公式是 $(a_1, a_k)(a_1, a_{k-1})\cdots(a_1, a_2)$。

习题 10:

• 不相交循环分解:
• $1 \to 8 \to 1$。得到循环 $(1, 8)$。
• $2 \to 2$。不动点。
• $3 \to 6 \to 4 \to 3$。得到循环 $(3, 6, 4)$。
• $5 \to 7 \to 5$。得到循环 $(5, 7)$。
• 结果: $(1, 8)(3, 6, 4)(5, 7)$。
• 对换分解:
• $(1, 8)$ 本身是对换。
• $(3, 6, 4)$ 是长度为3的循环，分解为 $(3, 4)(3, 6)$。
• $(5, 7)$ 本身是对换。
• 结果: $(1, 8)(3, 4)(3, 6)(5, 7)$。

习题 11:

• 不相交循环分解:
• $1 \to 3 \to 4 \to 1$。得到循环 $(1, 3, 4)$。
• $2 \to 6 \to 2$。得到循环 $(2, 6)$。
• $5 \to 8 \to 7 \to 5$。得到循环 $(5, 8, 7)$。
• 结果: $(1, 3, 4)(2, 6)(5, 8, 7)$。
• 对换分解:
• $(1, 3, 4)$ 分解为 $(1, 4)(1, 3)$。
• $(2, 6)$ 本身是对换。
• $(5, 8, 7)$ 分解为 $(5, 7)(5, 8)$。
• 结果: $(1, 4)(1, 3)(2, 6)(5, 7)(5, 8)$。

习题 12:

• 不相交循环分解:
• $1 \to 3 \to 4 \to 7 \to 8 \to 6 \to 5 \to 2 \to 1$。
• 这是一个遍历所有8个元素的长循环。
• 结果: $(1, 3, 4, 7, 8, 6, 5, 2)$。
• 对换分解:
• 这是一个长度为8的循环。使用公式 $(a_1, a_8)(a_1, a_7)\cdots(a_1, a_2)$。
• 结果: $(1, 2)(1, 5)(1, 6)(1, 8)(1, 7)(1, 4)(1, 3)$。

这道题旨在探索排列的阶（order）的计算方法。一个排列 $\sigma$ 的阶是最小的正整数 $r$ 使得 $\sigma^r = \iota$（恒等排列）。

a. 循环 $(1,4,5,7)$ 的阶:

• 这是一个长度为 4 的循环。
• $\sigma^1 = (1,4,5,7)$
• $\sigma^2 = (1,5)(4,7)$
• $\sigma^3 = (1,7,5,4)$
• $\sigma^4 = \iota$
• 最小的正幂次是 4。因此，阶是 4。

b. 由(a)启发的定理:

• 定理: 一个长度为 $k$ 的循环的阶是 $k$。

c. 计算不相交循环排列的阶:

• $\sigma=(4,5)(2,3,7)$: 这是一个长度为 2 的循环和长度为 3 的循环的乘积。它们是不相交的。
• $(4,5)$ 的阶是 2。它每 2 次变回单位元。
• $(2,3,7)$ 的阶是 3。它每 3 次变回单位元。
• 要使整个排列 $\sigma$ 变回单位元，需要两个部分同时变回单位元。
• 这需要施加的幂次 $r$ 必须既是 2 的倍数，又是 3 的倍数。
• 我们要找最小的这样的正整数 $r$，这正是 2 和 3 的最小公倍数 (LCM)。
• $\text{lcm}(2, 3) = 6$。所以 $\sigma$ 的阶是 6。
• $\tau=(1,4)(3,5,7,8)$: 这是一个长度为 2 和长度为 4 的不相交循环的乘积。
• $\text{lcm}(2, 4) = 4$。所以 $\tau$ 的阶是 4。

d. 计算习题10-12中排列的阶:

• 习题 10: 分解为 $(1,8)(3,6,4)(5,7)$。循环长度分别是 2, 3, 2。
• 阶 = $\text{lcm}(2, 3, 2) = 6$。
• 习题 11: 分解为 $(1,3,4)(2,6)(5,8,7)$。循环长度分别是 3, 2, 3。
• 阶 = $\text{lcm}(3, 2, 3) = 6$。
• 习题 12: 分解为 $(1,3,4,7,8,6,5,2)$。这是一个长度为 8 的循环。
• 阶 = 8。

e. 由(c)(d)启发的定理:

• 定理: 一个排列的阶，是其不相交循环分解中所有循环长度的最小公倍数 (least common multiple)。

这组问题是上一题的延伸和应用。要找到 $S_n$ 中元素的最大阶，我们需要找到一个和为 $n$ 的正整数划分 (partition)，使得这个划分中所有部分的最小公倍数 (LCM) 最大。

直觉上，为了让 LCM 最大，我们应该选择互不包含素数因子的数，即尽可能选择互素的数或不同素数的幂。

解题策略:

将 $n$ 分解成一个或多个正整数的和：$n = k_1 + k_2 + \cdots + k_r$。我们的目标是最大化 $\text{lcm}(k_1, k_2, \ldots, k_r)$。

• 14. n=5:
• 划分5:
• 5: lcm(5) = 5
• 4+1: lcm(4,1) = 4
• 3+2: lcm(3,2) = 6
• 3+1+1: lcm(3) = 3
• 2+2+1: lcm(2,2) = 2
• 最大阶: 6。它对应一个不相交循环结构为 (长度3循环)(长度2循环) 的排列，例如 $(1,2,3)(4,5)$。

• 15. n=6:
• 划分6:
• 6: lcm(6) = 6
• 5+1: lcm(5) = 5
• 4+2: lcm(4,2) = 4
• 3+3: lcm(3) = 3
• 1+2+3: lcm(1,2,3) = 6
• 最大阶: 6。它可以由一个长度为6的循环，如 $(1,2,3,4,5,6)$，或者一个 (3,2,1) 结构的排列，如 $(1,2,3)(4,5)$ 得到。

• 16. n=7:
• 划分7:
• 7: lcm(7) = 7
• 6+1: lcm(6) = 6
• 5+2: lcm(5,2) = 10
• 4+3: lcm(4,3) = 12
• 3+2+2: lcm(3,2) = 6
• 最大阶: 12。它对应一个不相交循环结构为 (长度4循环)(长度3循环) 的排列，例如 $(1,2,3,4)(5,6,7)$。

• 17. n=10:
• 我们需要将10分解为和，使其各部分的LCM最大。我们优先考虑互素的数或不同素数的幂。
• 7+3: lcm(7,3) = 21
• 5+3+2: lcm(5,3,2) = 30
• 8+1+1 (或9+1等): lcm(8)=8, lcm(9)=9
• 6+4: lcm(6,4)=12
• 5+4+1: lcm(5,4)=20
• 最大阶: 30。对应结构 (5-cycle)(3-cycle)(2-cycle)，例如 $(1,2,3,4,5)(6,7,8)(9,10)$。

• 18. n=15:
• 划分15，寻找LCM最大值。
• 15: 15
• 11+4: lcm(11,4) = 44
• 9+5+1: lcm(9,5) = 45
• 8+7: lcm(8,7) = 56
• 7+5+3: lcm(7,5,3) = 105
• 最大阶: 105。对应结构 (7-cycle)(5-cycle)(3-cycle)，例如 $(1..7)(8..12)(13..15)$。

这道题要求我们完成一个凯莱图的标记。凯莱图是群的一种可视化表示，顶点代表群的元素，有向边代表生成元的作用。

• 群: $A_4$ (4个字母上的偶排列群)，阶为 $4!/2 = 12$。
• 生成元: $a=(1,2,3)$ (实线箭头) 和 $b=(1,2)(3,4)$ (虚线箭头)。
• 图: 顶点是群元素，从一个顶点 $\sigma$ 出发，沿实线箭头到达的顶点是 $\sigma a$，沿虚线箭头到达的顶点是 $\sigma b$。(注意：书中图的箭头可能表示左乘 $a\sigma$ 或右乘 $\sigma a$，这里我们先按右乘 $\sigma a$ 尝试，如果与图不符再换。从 $e \to a$来看，是右乘。)

标记过程:

1. 起点: 标记为 $e$ (恒等排列)。
2. 从 e 出发:
   • e 沿实线 (右乘 a): $e a = a = (1,2,3)$。
   • e 沿虚线 (右乘 b): $e b = b = (1,2)(3,4)$。
3. 从 (1,2,3) 出发:
   • (1,2,3) 沿实线: $(1,2,3)(1,2,3) = (1,3,2)$。
   • (1,2,3) 沿虚线: $(1,2,3)(1,2)(3,4) = (1,3,4)$。 [计算: 1->2->3, 3->4, 4->3->1, 2->1->2]
4. 从 (1,2)(3,4) 出发:
   • (1,2)(3,4) 沿实线: $(1,2)(3,4)(1,2,3) = (2,4,3)$。 [计算: 1->2->1, 2->3->4, 4->4->3, 3->1->2]
5. 继续填充:
   • 从 (1,3,2) (即 $a^2$) 出发:
   • 沿实线: $(1,3,2)(1,2,3) = e$。这形成了 $e, a, a^2$ 的3元环。
   • 沿虚线: $(1,3,2)(1,2)(3,4) = (2,3,4)$。 [计算: 1->2->1, 2->1->3, 3->4, 4->3->2]
   • 从 (1,3,4) (即 $ab$) 出发:
   • 沿实线: $(1,3,4)(1,2,3) = (1,2,4)$。
   • 沿虚线: $(1,3,4)(1,2)(3,4) = (1,2,3) = a$。
   • 从 (2,4,3) (即 $ba$) 出发:
   • 沿实线: $(2,4,3)(1,2,3) = (1,4)(2,3)$。
   • 沿虚线: $(2,4,3)(1,2)(3,4) = (1,3,2)=a^2$。
   • 从 (2,3,4) (即 $a^2b$) 出发:
   • 沿实线: $(2,3,4)(1,2,3)=(1,3)(2,4)$。
   • 沿虚线: $(2,3,4)(1,2)(3,4)=(1,3,2)=a^2$。
6. 最后几个顶点:
   • 从 (1,2,4) (即 $aba$) 出发:
   • 沿实线: $(1,2,4)(1,2,3) = (1,4)(2,3)$。
   • 沿虚线: $(1,2,4)(1,2)(3,4) = (1,3,2)=a^2$。
   • 从 (1,4)(2,3) 出发:
   • 沿实线: $(1,4)(2,3)(1,2,3) = (2,4,3) = ba$。
   • 沿虚线: $(1,4)(2,3)(1,2)(3,4)=(1,3,4)=ab$。
   • 从 (1,3)(2,4) 出发:
   • 沿实线: $(1,3)(2,4)(1,2,3)=(2,3,4)=a^2b$。
   • 沿虚线: $(1,3)(2,4)(1,2)(3,4)=(1,2,3)=a$。

A4的12个元素:

• $e$ (1个)
• 3个长度为2的对换的乘积: $(1,2)(3,4)$, $(1,3)(2,4)$, $(1,4)(2,3)$
• 8个长度为3的循环: $(1,2,3), (1,3,2), (1,2,4), (1,4,2), (1,3,4), (1,4,3), (2,3,4), (2,4,3)$

通过上述计算，可以把这12个元素一一对应地填写到图中的12个顶点上。

这组题考察对核心概念定义的精确理解。

20. 轨道的定义:

• 原定义: “$\sigma$ 的轨道是 $A$ 的一个非空最小子集，该子集被 $\sigma$ 映射到自身。”
• 问题: “被 $\sigma$ 映射到自身” (mapped to itself) 的数学语言是 $\sigma(S)=S$。满足这个条件的子集可能不是一个轨道。例如，对于 $\sigma = (1,2)(3,4)$，集合 $S=\{1,2,3,4\}$ 满足 $\sigma(S)=S$，但它不是一个轨道，而是两个轨道 $\{1,2\}$ 和 $\{3,4\}$ 的并集。问题出在“最小”上。一个轨道确实是满足 $\sigma(S)=S$ 的非空最小子集。所以这个定义其实是对的，但不够“建设性”。
• 更标准的定义 (来自正文): 令 $\sigma$ 是集合 $A$ 的一个排列。由等价关系 $a \sim b \iff b=\sigma^n(a)$ (对于某个 $n \in \mathbb{Z}$) 所确定的 $A$ 中的等价类是 $\sigma$ 的轨道。
• 修正: “对于集合 $A$ 上的排列 $\sigma$ 和任意元素 $a \in A$，包含 $a$ 的轨道是集合 $\{\sigma^n(a) \mid n \in \mathbb{Z}\}$。” 这个定义更具操作性。

21. 循环的定义:

• 原定义: “循环是只有一个轨道的排列。”
• 问题: 严格来说，任何在集合 $A$ 上的排列，其所有轨道的并集都是 $A$。如果一个排列只有一个轨道，那么这个轨道必须是 $A$ 本身。例如，在 $S_5$ 中，$(1,2,3,4,5)$ 是一个循环，它确实只有一个轨道 $\{1,2,3,4,5\}$。但是，$(1,2,3)$ 在 $S_5$ 中也是一个循环，但它的轨道是 $\{1,2,3\}, \{4\}, \{5\}$，共有三个轨道。
• 正文定义: 排列 $\sigma \in S_{n}$ 是一个循环，如果它至多有一个包含多于一个元素的轨道。
• 修正: 将原定义修正为：“循环是一个排列，它至多有一个长度大于1的轨道。”

22. 交错群的定义:

• 原定义: “交错群是所有偶排列的群。”
• 问题: 这个定义含糊不清。“所有偶排列” 是指哪个集合上的排列？
• 修正: “在 $n$ 个字母上的交错群 $A_n$ 是由 $n$ 个字母上所有偶排列构成的群，它是对称群 $S_n$ 的一个子群。” 这个修正明确了基础集合（“$n$个字母”），并指出了它与 $S_n$ 的关系。

a. 假。反例：$(1,2)(3,4)$ 是一个排列，但它有两个长度大于1的轨道，所以它不是一个循环。

b. 真。根据定义，循环是一种特殊类型的排列。

c. 假。偶排列和奇排列的定义依赖于一个排列的对换分解中的对换数量的奇偶性是唯一的。如果这个奇偶性不唯一（即一个排列可以既是奇数个也是偶数个对换的积），那么“偶排列”和“奇排列”的定义就是模棱两可、没有意义的。定理 9.15 正是保证了这个唯一性，所以定义必须在其后给出。

d. 假。这是一个更深入的结论。$A_n$ ($n \ge 5$) 是单群。考虑 $A_9$ 本身，它是一个 $S_9$ 的非平凡子群，它包含奇排列吗？不，它只包含偶排列。所以这个前提“包含某个奇排列”不成立。让我们找一个包含奇排列的子群。根据习题29，如果一个子群包含奇排列，那它一半是奇一半是偶。但它不一定包含一个对换。例如，在 $S_4$ 中，群 $D_4$（正方形对称群）是一个阶为8的子群，它包含奇排列如 $(1,3)$ 和 $(1,2)(3,4)$(偶)，但它也包含 $(1,2,3,4)$ (奇)。它不一定包含所有对换。这个陈述过于强烈。

e. 假。$A_5$ 是 $S_5$ 的偶排列子群。$|S_5| = 5! = 120$。$A_5$ 的阶是 $|S_5|/2 = 120/2 = 60$。

f. 真。循环群是由单个元素生成的群。如果 $n \ge 3$，$S_n$ 不是阿贝尔群（非交换群），而所有循环群都是阿贝尔群，所以 $S_n$ 不可能是循环群。对于 $n=1$, $S_1=\{\iota\}$ 是循环群。对于 $n=2$, $S_2=\{\iota, (1,2)\}$ 是循环群（由(1,2)生成）。所以题中“对于任何 $n \ge 1$” 是错误的。应该是“对于任何 $n \ge 3$”。但如果按原题意，因为 $n=1,2$ 时是循环群，所以命题为假。

g. 真。$A_3 = \{\iota, (1,2,3), (1,3,2)\}$。这是一个阶为3的群。任何阶为素数的群都是循环群，而循环群都是阿贝尔群（交换群）。

h. 真。$S_8$ 中所有保持 8 不动的元素，本质上就是在对集合 $\{1,2,3,4,5,6,7\}$ 进行排列。这个子群的结构与 $S_7$ 完全相同，因此它们是同构的。

i. 真。理由同 (h)。保持哪个具体的数字不动并不影响剩下的排列构成的群的结构。

j. 假。奇排列的集合不满足子群的封闭性（奇+奇=偶）和单位元（单位元是偶）条件。

1. 列出 $S_3$ 的所有元素:

$S_3$ 的阶为 $3! = 6$。元素如下，并判断奇偶性：

• $\iota = ()$ (0个对换): 偶
• $(1,2)$ (1个对换): 奇
• $(1,3)$ (1个对换): 奇
• $(2,3)$ (1个对换): 奇
• $(1,2,3)$ (长度3, 3-1=2个对换): 偶
• $(1,3,2)$ (长度3, 3-1=2个对换): 偶

所以 $S_3$ 中的偶排列是 $\iota, (1,2,3), (1,3,2)$。

1. 给出 $A_3$ 的群表:

$A_3 = \{\iota, (1,2,3), (1,3,2)\}$。我们令 $e=\iota, a=(1,2,3), b=(1,3,2)$。注意到 $a^2=b$ 且 $b=a^{-1}$。

群表如下 (行列都是 $e, a, b$):

计算验证:

• $a \cdot a = (1,2,3)(1,2,3) = (1,3,2) = b$
• $a \cdot b = (1,2,3)(1,3,2) = \iota = e$
• $b \cdot a = (1,3,2)(1,2,3) = \iota = e$
• $b \cdot b = (1,3,2)(1,3,2) = (1,2,3) = a$

25. 证明1概要 (线性代数法):

通过将排列与排列矩阵关联，利用“交换两行则行列式变号”的性质，证明了一个排列的对换分解其对换数量的奇偶性唯一地决定了其对应排列矩阵的行列式是+1还是-1，从而排除了奇偶性混合的可能性。

26. 证明2概要 (轨道计数法):

一个排列左乘一个对换，其轨道总数会改变1，因此轨道数的奇偶性会反转。因为任何排列的轨道数是唯一的，所以从恒等排列出发达到该排列所需的对换次数的奇偶性也必须是唯一的。

a. 至多 n-1 个对换:

• 一个排列可以分解为不相交循环的乘积。设各循环长度为 $k_1, k_2, \ldots, k_r$，则 $\sum k_i \le n$ (如果存在不动点，则小于n)。
• 每个长度为 $k_i$ 的循环可分解为 $k_i-1$ 个对换。
• 总对换数为 $\sum (k_i - 1) = (\sum k_i) - r$。
• 因为 $r \ge 1$ (至少有一个循环)，所以 $\sum (k_i - 1) < \sum k_i \le n$。
• 最坏的情况是这个排列是一个长度为 $n$ 的循环，此时 $r=1, k_1=n$，需要 $n-1$ 个对换。
• 其他任何情况，$\sum(k_i) - r < n-1$。例如，对于 $(1,2)(3,...,n)$，需要 $1 + (n-3) = n-2$ 个对换。
• 因此，任何排列最多需要 $n-1$ 个对换。

b. 不是循环的排列，至多 n-2 个对换:

• 如果一个排列不是循环，那么在它的不相交循环分解中，循环的个数 $r \ge 2$。
• 所需的对换总数为 $\sum (k_i - 1) = (\sum k_i) - r$。
• 我们知道 $\sum k_i \le n$。
• 所以对换数为 $\le n - r$。
• 因为 $r \ge 2$，所以对换数 $\le n-2$。

c. 写成特定数目的对换:

• 我们已经知道一个排列的对换分解的奇偶性是固定的，但数量不是。我们可以通过乘以恒等排列 $\iota=(1,2)(1,2)$ 来任意增加偶数个对换。
• 对于奇排列: 假设它能写成 $m$ 个对换的积，其中 $m$ 是奇数。我们要证明它能写成 $2n+3$ 个对换的积。
• $2n+3$ 也是奇数。$m$ 和 $2n+3$ 的差是偶数。
• 我们可以写 $\sigma = \sigma \cdot \iota^k = (\tau_1 \cdots \tau_m) \cdot ((1,2)(1,2))^k$。
• 这里的对换总数是 $m+2k$。我们只需令 $m+2k = 2n+3$，解出 $k = (2n+3-m)/2$。因为 $m$ 和 $2n+3$ 都是奇数，它们的差是偶数，所以 $k$ 是整数。
• 因此，总可以做到。
• 对于偶排列: 证明逻辑完全相同。假设它能写成 $m$ 个对换的积 ($m$ 为偶数)，我们要证明它能写成 $2n+8$ 个对换的积。
• $2n+8$ 也是偶数。差是偶数。
• 我们可以通过乘以 $k=(2n+8-m)/2$ 次 $\iota=(1,2)(1,2)$ 来实现。

a. $\sigma(i)=i$, i和j在不同轨道:

• $\sigma$ 的轨道中，一个是单元素轨道 $\{i\}$，另一个是包含 $j$ 的轨道 $B_j$。
• $\sigma$ 的一部分可以表示为 $(i) (j, b, c, \ldots)$。
• 计算 $\tau\sigma = (i,j)\sigma$。
• 追踪路径:
• $\sigma$ 中: $i \to i$ 且 $\ldots \to j \to b \to \ldots$。
• 在 $\tau\sigma$ 中:
• 作用于 $i$: $(\tau\sigma)(i) = \tau(\sigma(i)) = \tau(i) = j$。
• 作用于 $j$ 的前驱（设为 $k$, $\sigma(k)=j$）: $(\tau\sigma)(k) = \tau(\sigma(k)) = \tau(j) = i$。
• 效果是，原来指向 $j$ 的箭头现在指向 $i$，而 $i$ 指向了原来 $j$ 的后继 $b$ (因为 $(\tau\sigma)(j) = \tau(\sigma(j))=\tau(b)=b$ )。不对，$(\tau\sigma)(i) = j$。
• 让我们重新追踪：
• ... $k \xrightarrow{\sigma} j \xrightarrow{\tau} i$ ...
• ... $i \xrightarrow{\sigma} i \xrightarrow{\tau} j$ ...
• 原来的两个分离的路径 $\{i\}$ 和 $\{k \to j \to b \to \dots\}$ 被连接起来，形成了 $\dots k \to i \to j \to b \to \dots$。
• 两个轨道合并成了一个。轨道数减一。
• 图示: 画一个单独的点 $i$ 和一个包含 $j$ 的圆圈。左乘 $(i,j)$ 后，点 $i$ 被“吸入”圆圈，形成一个更大的圆圈。

b. $\sigma(i)=i$ 且 $\sigma(j)=j$:

• $\sigma$ 的轨道中，有两个单元素轨道 $\{i\}$ 和 $\{j\}$。
• 计算 $\tau\sigma = (i,j)\sigma$。
• 因为 $\sigma$ 在 $i,j$ 上是恒等映射，所以 $\tau\sigma = (i,j)\iota = (i,j)$。
• 新的排列是对换 $(i,j)$。它的轨道是 $\{i,j\}$ 以及其他 $\sigma$ 已有的轨道。
• 原来的两个单元素轨道 $\{i\}, \{j\}$ 合并成了一个双元素轨道 $\{i,j\}$。
• 轨道总数减一。

• 令 $H$ 是 $S_n$ 的一个子群。
• 情况 1: $H$ 中所有元素都是偶排列。
• 这种情况下，结论的前半部分成立。$A_n$ 就是一个例子。
• 情况 2: $H$ 中至少包含一个奇排列。
• 令 $H_E$ 为 $H$ 中所有偶排列的集合， $H_O$ 为 $H$ 中所有奇排列的集合。$H = H_E \cup H_O$。
• $H_E$ 是 $H$ 的一个子群。（偶+偶=偶，单位元是偶，偶的逆是偶）。
• 选择一个固定的奇排列 $\rho \in H_O$。
• 定义一个映射 $f: H_E \to H_O$ 为 $f(\sigma) = \rho\sigma$。
• 良序性: 对于任意 $\sigma \in H_E$，$\rho$是奇，$\sigma$是偶，所以 $\rho\sigma$ 是奇排列。又因为 $H$ 是群，$\rho \in H, \sigma \in H \implies \rho\sigma \in H$。所以 $\rho\sigma \in H_O$。
• 单射性: 若 $f(\sigma_1) = f(\sigma_2)$，则 $\rho\sigma_1 = \rho\sigma_2$。由群的消去律，$\sigma_1 = \sigma_2$。
• 满射性: 对于任意一个 $\pi \in H_O$，我们能否找到一个 $\sigma \in H_E$ 使得 $f(\sigma) = \pi$？
• 我们需要解 $\rho\sigma = \pi$。解为 $\sigma = \rho^{-1}\pi$。
• 因为 $\rho$ 是奇排列，其逆 $\rho^{-1}$ 也是奇排列。
• $\pi$ 是奇排列。
• $\sigma = \rho^{-1}\pi$ 的奇偶性是 "奇" + "奇" = "偶"。所以 $\sigma \in H_E$。
• 我们找到了原像。
• 因为 $f$ 是一个从 $H_E$ 到 $H_O$ 的双射，所以 $|H_E| = |H_O|$。
• 这证明了如果 $H$ 包含奇排列，那么它的奇偶排列数量必然相等，各占一半。

• 一个长度为 $n$ 的循环，根据定义，它的主轨道包含 $n$ 个元素。
• 对于这 $n$ 个元素中的任何一个 $a$，$\sigma(a)$ 是循环中的下一个元素，所以 $\sigma(a) \neq a$。
• 对于不在这个主轨道中的任何元素 $b$，根据循环的定义，$\sigma(b)=b$ (不动点)。
• 因此，一个长度为 $n$ 的循环恰好移动了 $n$ 个元素。

我们需要验证子群三条件：

1. 单位元: 单位元 $\iota$ 移动了 0 个元素。0是有限的，所以 $\iota \in H$。
2. 封闭性: 令 $\sigma_1, \sigma_2 \in H$。
   • 设 $M_1$ 是被 $\sigma_1$ 移动的元素集合， $M_2$ 是被 $\sigma_2$ 移动的元素集合。$|M_1|$ 和 $|M_2|$ 都是有限的。
   • 考虑乘积 $\sigma_1\sigma_2$。一个元素 $a$ 可能被 $\sigma_1\sigma_2$ 移动，即 $(\sigma_1\sigma_2)(a) \neq a$。
   • 如果一个元素 $a$ 既不被 $\sigma_1$ 移动也不被 $\sigma_2$ 移动 (即 $a \notin M_1$ 且 $a \notin M_2$)，那么 $\sigma_2(a)=a$, $(\sigma_1\sigma_2)(a) = \sigma_1(a) = a$。它也不被乘积移动。
   • 所以，被 $\sigma_1\sigma_2$ 移动的元素的集合必然是 $M_1 \cup M_2$ 的子集。
   • 被移动的集合 $\subseteq M_1 \cup M_2$。
   • 因为 $|M_1 \cup M_2| \le |M_1| + |M_2|$，而 $|M_1|$ 和 $|M_2|$ 都是有限的，所以 $|M_1 \cup M_2|$ 也是有限的。
   • 因此，$\sigma_1\sigma_2$ 移动的元素数量是有限的，$\sigma_1\sigma_2 \in H$。
3. 逆元: 令 $\sigma \in H$。
   • 如果 $\sigma(a) = b$ 且 $a \neq b$，那么 $\sigma^{-1}(b)=a$ 且 $b \neq a$。
   • 这意味着，如果 $\sigma$ 移动了 $a$ (把它变成了 $b$)，那么 $\sigma^{-1}$ 必然移动了 $b$ (把它变回了 $a$)。
   • 被 $\sigma^{-1}$ 移动的元素集合，就是被 $\sigma$ 移动的元素的像的集合。
   • 集合 $\{a \mid \sigma(a) \neq a\}$ 和集合 $\{b \mid \sigma^{-1}(b) \neq b\}$ 之间存在双射。它们的基数是相同的。
   • 因为 $\sigma$ 移动的元素数量是有限的，所以 $\sigma^{-1}$ 移动的元素数量也是有限的。$\sigma^{-1} \in H$。
   • 三个条件均满足，所以 $H$ 是 $S_A$ 的子群。

• 否， $K$ 不是一个子群。
• 原因: 它不满足封闭性。
• 反例:
• 设 $\sigma_1 = (1, 2)$。它移动了 2 个元素 ($2 \le 50$)，所以 $\sigma_1 \in K$。
• 设 $\sigma_2 = (3, 4, \ldots, 52)$。这是一个长度为50的循环，它移动了 50 个元素 ($50 \le 50$)，所以 $\sigma_2 \in K$。
• 考虑乘积 $\sigma = \sigma_1 \sigma_2 = (1,2)(3,4,\ldots,52)$。
• 因为 $\sigma_1$ 和 $\sigma_2$ 是不相交的，所以被 $\sigma$ 移动的元素集合是 $\{1,2\} \cup \{3,4,\ldots,52\}$。
• 这个集合的大小是 $2+50=52$。
• $\sigma$ 移动了 52 个元素，而 $52 > 50$。
• 因此 $\sigma \notin K$。
• 因为运算不封闭，所以 $K$ 不是一个子群。

• 这道题实际上是在描述陪集 (coset) 的概念。我们要证明奇排列集合 $B_n$ 等于陪集 $\sigma A_n = \{\sigma\alpha \mid \alpha \in A_n\}$。
• 证明:
• 第一步：证明 $\sigma A_n \subseteq B_n$。
• 取任意元素 $\pi \in \sigma A_n$。根据定义，$\pi = \sigma\alpha$，其中 $\alpha \in A_n$。
• $\sigma$ 是奇排列，$\alpha$ 是偶排列。
• 它们的乘积 $\pi$ 的奇偶性是 "奇" + "偶" = "奇"。
• 所以 $\pi$ 是一个奇排列，即 $\pi \in B_n$。
• 这证明了 $\sigma A_n$ 中的所有元素都在 $B_n$ 中。
• 第二步：证明 $B_n \subseteq \sigma A_n$。
• 取任意一个奇排列 $\rho \in B_n$。
• 我们需要证明 $\rho$可以被写成 $\sigma\alpha$ 的形式，其中 $\alpha \in A_n$。
• 解方程 $\rho = \sigma\alpha$ 得到 $\alpha = \sigma^{-1}\rho$。
• 我们需要验证这个 $\alpha$ 是否在 $A_n$ 中。
• $\sigma$ 是奇排列，所以 $\sigma^{-1}$ 也是奇排列。
• $\rho$ 是奇排列。
• $\alpha = \sigma^{-1}\rho$ 的奇偶性是 "奇" + "奇" = "偶"。
• 所以 $\alpha$ 确实是一个偶排列，$\alpha \in A_n$。
• 这证明了任何奇排列 $\rho$ 都可以写成 $\sigma$ 与一个偶排列 $\alpha = \sigma^{-1}\rho$ 的乘积。
• 因为 $\sigma A_n \subseteq B_n$ 且 $B_n \subseteq \sigma A_n$，所以 $B_n = \sigma A_n$。证明完毕。

• 令 $\sigma = (a_1, a_2, \ldots, a_n)$ 是一个循环，其长度 $n$ 是奇数。
• $\sigma^2$ 的作用是将每个元素 $a_i$ 映射到 $a_{i+2 \pmod n}$ (如果下标从1开始，则下标运算在 $\{1,\ldots,n\}$ 上进行)。
• 要证明 $\sigma^2$ 是一个循环，我们需要证明它的轨道只有一个长度大于1的（事实上，长度也为 $n$）。
• 这等价于证明，从任意元素 $a_1$ 出发，通过反复作用 $\sigma^2$，可以遍历所有 $a_1, \ldots, a_n$ 中的元素。
• 轨迹是 $a_1, \sigma^2(a_1)=a_3, \sigma^4(a_1)=a_5, \ldots$。
• 这个序列的下标是 $1, 1+2, 1+4, \ldots, 1+2k, \ldots \pmod n$。
• 这个轨迹能遍历所有 $n$ 个元素，当且仅当 $2$ 和 $n$ 互质，即 $\text{gcd}(2, n) = 1$。
• 因为 $n$ 是奇数，所以它不含因子 2。因此，$\text{gcd}(2, n) = 1$。
• 所以，序列 $a_1, a_3, a_5, \ldots$ 将会不重复地遍历所有 $n$ 个元素后才回到 $a_1$。
• 因此，$\sigma^2$ 将 $\sigma$ 的轨道中的所有元素保持在一个轨道中，形成一个长度为 $n$ 的循环。

• 延续上一题的思路。令 $\sigma = (a_1, \ldots, a_n)$。
• $\sigma^r$ 的作用是将 $a_i$ 映射到 $a_{i+r \pmod n}$。
• $\sigma^r$ 仍然是一个长度为 $n$ 的循环，当且仅当从 $a_1$ 出发，通过反复作用 $\sigma^r$，可以遍历所有 $n$ 个元素。
• 这个轨迹是 $a_1, a_{1+r}, a_{1+2r}, \ldots \pmod n$。
• 这个轨迹能遍历所有 $n$ 个元素，当且仅当 $r$ 在模 $n$ 的加法群 $\mathbb{Z}_n$ 中是一个生成元。
• 这又当且仅当 $r$ 与 $n$ 互质。
• 定理: 如果 $\sigma$ 是长度为 $n$ 的循环，则 $\sigma^{r}$ 也是一个（长度为n的）循环当且仅当 $\text{gcd}(n, r) = 1$。
• (注：如果 $\text{gcd}(n, r) = d > 1$，那么 $\sigma^r$ 将会分裂成 $d$ 个长度为 $n/d$ 的不相交循环。)

• 要证明 $\lambda_a$ 是集合 $G$ 的一个排列，我们需要证明它是一个从 $G$ 到 $G$ 的双射（既单射又满射）。
• 证明单射性:
• 假设 $\lambda_a(g_1) = \lambda_a(g_2)$ 对于 $g_1, g_2 \in G$。
• 根据定义，有 $ag_1 = ag_2$。
• 因为 $G$ 是一个群，它满足左消去律。在等式两边同时左乘 $a$ 的逆元 $a^{-1}$。
• $a^{-1}(ag_1) = a^{-1}(ag_2) \implies (a^{-1}a)g_1 = (a^{-1}a)g_2 \implies eg_1 = eg_2 \implies g_1 = g_2$。
• 因此 $\lambda_a$ 是单射的。
• 证明满射性:
• 对于集合 $G$ 中的任意一个元素 $h$，我们能否在定义域 $G$ 中找到一个元素 $g$ 使得 $\lambda_a(g) = h$？
• 我们需要解方程 $ag = h$。
• 在等式两边左乘 $a^{-1}$，得到 $g = a^{-1}h$。
• 因为 $a^{-1} \in G$ 且 $h \in G$，根据群的封闭性，$g = a^{-1}h$ 也在 $G$ 中。
• 我们找到了原像。因此 $\lambda_a$ 是满射的。
• 因为 $\lambda_a$ 既单射又满射，所以它是一个双射，即集合 $G$ 的一个排列。

• 这就是凯莱定理的证明核心。我们要证明 $H$ 是 $S_G$ 的一个子群。
• 封闭性:
• 取任意两个元素 $\lambda_a, \lambda_b \in H$。
• 它们的乘积 (函数复合) 是 $(\lambda_a \circ \lambda_b)$。
• 作用于任意 $g \in G$: $(\lambda_a \circ \lambda_b)(g) = \lambda_a(\lambda_b(g)) = \lambda_a(bg) = a(bg)$。
• 根据群的结合律，$a(bg) = (ab)g$。
• $(ab)g$ 正是映射 $\lambda_{ab}$ 对 $g$ 的作用。
• 所以 $\lambda_a \circ \lambda_b = \lambda_{ab}$。
• 因为 $ab \in G$，所以 $\lambda_{ab} \in H$。封闭性成立。
• 单位元:
• $S_G$ 的单位元是恒等排列 $\iota$。
• 我们需要证明 $\iota \in H$。
• 考虑 $G$ 的单位元 $e$。对应的映射是 $\lambda_e$。
• $\lambda_e(g) = eg = g$。这正是恒等排列 $\iota(g)=g$。
• 所以 $\iota = \lambda_e \in H$。
• 逆元:
• 取任意元素 $\lambda_a \in H$。它的逆映射 $(\lambda_a)^{-1}$ 是否在 $H$ 中？
• 我们知道 $\lambda_a \circ \lambda_{a^{-1}} = \lambda_{a a^{-1}} = \lambda_e = \iota$。
• 这意味着 $\lambda_{a^{-1}}$ 就是 $\lambda_a$ 的逆元。
• 因为 $a^{-1} \in G$，所以 $(\lambda_a)^{-1} = \lambda_{a^{-1}} \in H$。
• 三个条件均满足，所以 $H$ 是 $S_G$ 的一个子群。
• (注：这个证明还顺便证明了映射 $\phi: G \to H$ by $\phi(a)=\lambda_a$ 是一个群同构，这正是凯莱定理的内容)。

• 一个作用在集合 $X$ 上的排列群 $H$ 被称为是传递的 (transitive)，如果对于 $X$ 中的任意两个元素 $x, y$，都存在一个 $\sigma \in H$ 使得 $\sigma(x)=y$。
• 在我们的场景中，群 $H=\{\lambda_a \mid a \in G\}$ 作用在集合 $G$ 上。
• 我们要证明对于任意两个元素 $g_1, g_2 \in G$，存在一个 $\lambda_a \in H$ 使得 $\lambda_a(g_1) = g_2$。
• 我们需要解方程 $ag_1 = g_2$ 来找到对应的 $a$。
• 在群 $G$ 中，两边右乘 $g_1^{-1}$，得到 $a = g_2 g_1^{-1}$。
• 因为 $g_2, g_1^{-1} \in G$，所以 $a = g_2 g_1^{-1}$ 也一定在 $G$ 中。
• 这意味着我们总能找到这样一个 $a$，从而总能找到对应的映射 $\lambda_a \in H$ 来完成转换。
• 因此，群 $H$ 在集合 $G$ 上是传递的。
• 与第4节定理的联系: 第4节关于群的基本性质中可能有这样的定理：“对于群 $G$ 中的任意元素 $b, c$，方程 $xb=c$ 和 $bx=c$ 在 $G$ 中有唯一解。” 我们这里解的方程 $ag_1=g_2$ (即 $xa=b$ 型) 有解，正是这个定理的直接应用。

这是一个多步骤的证明，旨在证明仅用一个对换和一个长循环就能生成整个对称群。

令 $\alpha = (1,2,3,\ldots,n)$ 和 $\tau = (1,2)$。

• 第一步 (提示的前半部分): 证明我们可以生成相邻对换。
• 我们需要计算共轭 (conjugation): $\alpha^r \tau \alpha^{-r}$。
• 有一个共轭的通用法则：如果 $\sigma$ 是一个排列，$\mu=(a_1, \ldots, a_k)$ 是一个循环，那么 $\sigma\mu\sigma^{-1} = (\sigma(a_1), \ldots, \sigma(a_k))$。
• 我们来计算 $\alpha \tau \alpha^{-1}$。
• $\alpha(1)=2, \alpha(2)=3$。
• $\alpha \tau \alpha^{-1} = \alpha(1,2)\alpha^{-1} = (\alpha(1), \alpha(2)) = (2,3)$。
• 计算 $\alpha^2 \tau \alpha^{-2}$。
• $\alpha^2(1)=3, \alpha^2(2)=4$。
• $\alpha^2 \tau \alpha^{-2} = (\alpha^2(1), \alpha^2(2)) = (3,4)$。
• 一般地，$\alpha^{k-1} \tau \alpha^{-(k-1)} = (k, k+1)$ 对于 $k=1, \ldots, n-1$。
• 这证明了我们可以从 $\alpha$ 和 $\tau$ 生成所有相邻对换 $(1,2), (2,3), \ldots, (n-1,n)$。
• 第二步 (提示的后半部分): 证明相邻对换可以生成任何对换。
• 我们要证明任何对换 $(i,j)$ (不妨设 $i<j$) 都可以由 $(k, k+1)$ 形式的对换生成。
• 考虑生成 $(i, i+2)$：$(i, i+1)(i+1, i+2)(i, i+1) = (i, i+2)$。
• 通过这种方式，我们可以“传递”交换，从 $(i,i+1)$ 生成 $(i,j)$。具体来说：
• $(i, j) = (i, i+1)(i+1, i+2)\cdots(j-1, j) \cdots (i+1, i+2)(i, i+1)$。
• 这证明了所有对换都可以在这个生成集中生成。
• 第三步 (使用推论 9.12):
• 推论 9.12 说，任何排列都是对换的乘积。
• 既然我们已经证明了 $\{(1,2), (1,2,\ldots,n)\}$ 可以生成所有对换，而所有对换又可以生成整个 $S_n$，那么通过传递性，$\{(1,2), (1,2,\ldots,n)\}$ 就可以生成 $S_n$。证明完毕。