还没有笔记
选中页面文字后点击「高亮」按钮添加
回忆一下，给定一个集合 $X$，所有从 $X$ 到自身的双射（或更简洁地说，特别是当 $X$ 是有限集时，X 的置换）的集合 $S_{X}$ 在函数复合下构成一个群。特别地，对于每个 $n \in \mathbb{N}$，对称群 $S_{n}$ 是集合 $\{1, \ldots, n\}$ 的置换群，群运算等于函数复合。因此 $S_{n}$ 是一个包含 $n!$ 个元素的群，当 $n \geq 3$ 时它不是阿贝尔群。如果 $X$ 是一个包含 $\#(X)=n$ 个元素的有限集，那么将 $X$ 的元素标记为 $x_{1}, \ldots, x_{n}$ 即可定义一个从 $S_{X}$ 到 $S_{n}$ 的同构 $F$。具体来说，给定 $f \in S_{X}$，对于每个 $i, f\left(x_{i}\right)=x_{j}=x_{\sigma(i)}$，其中 $j$ 是某个值，$\sigma \in S_{n}$ 是一个唯一的元素，我们定义 $F(f)(i)=j$，即 $F(f)=\sigma$。
我们将用希腊字母 $\sigma, \tau, \rho, \ldots$ 来表示 $S_{n}$ 的元素，用 1 表示恒等函数，并使用并置（或偶尔使用乘法符号 ⋅ ）来表示复合（而不是符号 ∘）。然而请记住函数是从右向左作用的：因此 $\sigma \tau(i)= \sigma(\tau(i))$，换句话说，先计算 $\tau$ 在 $i$ 上的值，然后再计算 $\sigma$ 在这个值上的作用。
定义 2.1.1. 我们说 $\sigma$ 移动 $i$ 如果 $\sigma(i) \neq i$，并且 $\sigma$ 固定 $i$ 如果 $\sigma(i)=i$。$\sigma$ 的支持集 $\operatorname{Supp} \sigma$ 是集合
即 $\sigma$ 作用下 $\{1, \ldots, n\}$ 中被移动的子集。因此 $\operatorname{Supp} \sigma=\emptyset \Longleftrightarrow \sigma=1$。
$S_{n}$ 中有许多有趣的子群。例如，通过
定义的子集 $H_{n}$ 很容易验证是 $S_{n}$ 的一个子群，且同构于 $S_{n-1}$。事实上，对于所有 $i$，我们可以定义 $H_{i}=\left\{\sigma \in S_{n}: \sigma(i)=i\right\}$。它也同构于 $S_{n-1}$，因为它可以被看作是集合 $X=\{1, \ldots, n\}-\{i\}$ 的置换集，该集合有 $n-1$ 个元素。如果 $n=n_{1}+n_{2}$ 对于两个正整数 $n_{1}, n_{2}$ 成立，那么子集
也是 $S_{n}$ 的一个子群。注意，如果 $\sigma \in H_{n_{1}, n_{2}}$，那么自动地
而且事实上很容易验证 $H_{n_{1}, n_{2}}$ 同构于 $S_{n_{1}} \times S_{n_{2}}$。$S_{n}$ 中还有许多其他子群。例如，如果 $\sigma \in S_{n}$ 被定义为 $\sigma(i)=i+1$ 对于 $i \leq n-1$，且 $\sigma(n)=1$，那么很容易验证 $\sigma$ 的阶为 $n$，因此 $\langle\sigma\rangle$ 是 $S_{n}$ 的一个子群，同构于 $\mathbb{Z} / n \mathbb{Z}$。二面体群 $D_{n}$，即平面中正 $n$-边形的对称群，通过考察 $n$-边形顶点的置换，它是 $S_{n}$ 的一个子群（或同构于）。注意 $\#\left(D_{n}\right)=2 n$，因此如果 $n \geq 4$，则 $D_{n}$ 是 $S_{n}$ 的一个真子群。我们将会看到（凯莱定理），如果 $G$ 是一个有限群，那么存在一个 $n$ 使得 $G$ 同构于 $S_{n}$ 的一个子群（事实上可以取 $n=\#(G)$）。因此群 $S_{n}$ 相当复杂，因为它们包含所有可能的有限群作为子群，直到同构。
为了描述函数 $\sigma:\{1, \ldots, n\} \rightarrow\{1, \ldots, n\}$，不一定是置换，我们可以给出一个值表，记录 $i$ 和 $\sigma(i)$，如下所示：
| $i$ | 1 | 2 | $\ldots$ | $n$ |
|---|---|---|---|---|
| $\sigma(i)$ | $\sigma(1)$ | $\sigma(2)$ | $\ldots$ | $\sigma(n)$ |
当然，我们可以用一个 $2 \times n$ 矩阵来描述相同的信息：
$\sigma$ 是置换的条件是整数 $1, \ldots, n$ 在矩阵的第二行中恰好出现一次。当然，第一行是多余的，$\sigma$ 也可以
用有序 $n$-元组 $(\sigma(1), \sigma(2), \ldots, \sigma(n))$ 来描述。（但请务必不要与我们下面描述的循环表示法混淆。）
例如，如果 $\sigma$ 由矩阵给出
则 $\sigma(1)=2$ 且 $\sigma(5)=5$。
然而这种表示法繁琐且不适合计算。我们描述一种更有效的方法来写出 $S_{n}$ 的元素，首先写出一些特殊的元素，称为循环，然后证明 $S_{n}$ 的每个元素都可以分解成循环的乘积，如果我们小心的话，这种分解在本质上是唯一的。
定义 2.1.2. 设 $\left\{a_{1}, \ldots, a_{k}\right\}$ 是 $\{1, \ldots, n\}$ 的一个恰好包含 $k$ 个元素的子集；等价地，$a_{1}, \ldots, a_{k}$ 是不同的。在对 $a_{i}$ 进行排序后，我们得到一个包含 $k$ 个不同分量的有序 $k$-元组 $(a_{1}, \ldots, a_{k})$。我们用 $\left(a_{1}, \ldots, a_{k}\right)$（与 $k$-元组相同的表示法）表示 $S_{n}$ 的以下元素：
我们称 $\left(a_{1}, \ldots, a_{k}\right)$ 为 $k$-循环或长度为 $k$ 的循环。（有时我们会省略逗号。）对于 $k>1$，$\operatorname{Supp}\left(a_{1}, \ldots, a_{k}\right)$ 的支持集是 $\left\{a_{1}, \ldots, a_{k}\right\}$；因此，对于 $k>1$， $k$-循环 $(a_{1}, \ldots, a_{k})$ 移动 $i \Longleftrightarrow i \in \operatorname{Supp}\left(a_{1}, \ldots, a_{k}\right)$。两个循环 $\left(a_{1}, \ldots, a_{k}\right)$ 和 $\left(b_{1}, \ldots, b_{\ell}\right)$ 是不相交的，如果
即集合 $\left\{a_{1}, \ldots, a_{k}\right\}$ 和 $\left\{b_{1}, \ldots, b_{\ell}\right\}$ 是不相交的。
注 2.1.3. (1) 1-循环 $(a_{1})$ 是恒等函数 1，无论 $a_{1}$ 是什么。因此，我们通常只考虑长度至少为 2 的循环。如果 $\sigma=\left(a_{1}, \ldots, a_{k}\right)$ 且 $k \geq 2$，那么 $\sigma$ 绝不是恒等元，因为 $\sigma\left(a_{1}\right)=a_{2} \neq a_{1}$。
(2) 2-循环 $(a_{1}, a_{2})$ 也称为对换。它是 $\{1, \ldots, n\}$ 中唯一的置换，它交换 $a_{1}$ 和 $a_{2}$，并使所有其他元素保持不变。
(3) 从 (2) 中的描述可以清楚地看出 $\left(a_{1}, a_{2}\right)=\left(a_{2}, a_{1}\right)$。但对于 $k \geq 3$，元素 $a_{1}, \ldots, a_{k}$ 的顺序很重要：例如 $\sigma_{1}=(1,3,2) \neq \sigma_{2}=(1,2,3)$，因为 $\sigma_{1}(1)=3$ 但 $\sigma_{2}(1)=2$。
(4) 然而，有一些方法可以在不改变 $S_{n}$ 元素的情况下改变顺序：显然
换句话说，你可以在任何地方开始循环，例如 $a_{i}$，但你必须按顺序排列元素：下一个必须是 $a_{i+1}$，依此类推，理解一旦你到达 $a_{k}$，下一个必须是 $a_{1}$，然后是 $a_{2}$，然后是直到 $a_{i-1}$。显然，这是你改变顺序的唯一方法。（有时这被称为 $a_{1}, a_{2}, \ldots, a_{k}$ 的循环排序。）按照惯例，我们通常（但并非总是）从最小的 $a_{i}$ 开始。当然，在此之后，对循环中连续成员的大小没有限制。
(5) 很容易看出逆元 $\left(a_{1}, a_{2}, \ldots, a_{k}\right)^{-1}=\left(a_{k}, a_{k-1}, \ldots, a_{1}\right)$。换句话说， $k$-循环 $(a_{1}, a_{2}, \ldots, a_{k})$ 的逆元是元素按相反顺序书写的 $k$-循环。特别地，对于对换 $(a_{1}, a_{2})$， $(a_{1}, a_{2})^{-1}=\left(a_{2}, a_{1}\right)=\left(a_{1}, a_{2}\right)$，即对换的阶为 2。
(6) 泛化 (5) 的最后一行，很容易看出 $k$-循环 $\sigma=\left(a_{1}, a_{2}, \ldots, a_{k}\right)$ 的阶恰好是 $k$。事实上，$\sigma\left(a_{i}\right)=a_{i+1}$，因此 $\sigma^{r}\left(a_{i}\right)=a_{i+r}$，其中加法 $i+r$ 应在模 $k$ 意义下进行，但使用 $1, \ldots, k$ 作为模 $k$ 加法的代表元，而不是（本课程中）更常用的 $0, \ldots, k-1$。特别地，我们看到 $\sigma^{r}\left(a_{i}\right)=a_{i}$ 对于所有 $i \Longleftrightarrow r$ 是 $k$ 的倍数，并且由于 $\sigma^{r}(j)=j$ 对于 $j \neq a_{i}$ 和所有 $r$，我们看到 $k$ 是最小的正整数 $r$ 使得 $\sigma^{r}=1$。
然而请注意，如果 $\sigma$ 是一个 $k$-循环，它的幂 $\sigma^{r}$ 不一定是 $k$-循环。例如，
且 $(1,3)(2,4)$ 不是任何 $k$ 的 $k$-循环。
(7) 假设 $\sigma_{1}=\left(a_{1}, \ldots, a_{k}\right)$ 和 $\sigma_{2}=\left(b_{1}, \ldots, b_{\ell}\right)$ 是两个不相交的循环。那么很容易看出 $\sigma_{1} \sigma_{2}=\sigma_{2} \sigma_{1}$，即“不相交的循环可交换”。为了验证这一点，我们必须检查对于所有 $j \in\{1, \ldots, n\}$， $\sigma_{1} \sigma_{2}(j)=\sigma_{2} \sigma_{1}(j)$。首先，如果 $j=a_{i}$ 对于某个 $i$，那么 $\sigma_{1}\left(a_{i}\right)=a_{i+1}$（按我们通常的模 $k$ 加法约定），但 $\sigma_{2}\left(a_{i}\right)=a_{i}$ 因为 $a_{i} \neq b_{r}$ 对于任何 $r$。出于同样的原因， $\sigma_{2}\left(a_{i+1}\right)=a_{i+1}$。因此，对于所有 $i$ 且 $1 \leq i \leq k$，
而
类似地，$\sigma_{1} \sigma_{2}\left(b_{r}\right)=b_{r+1}=\sigma_{2} \sigma_{1}\left(b_{r}\right)$ 对于所有 $r, 1 \leq r \leq \ell$。最后，如果 $j$ 既不是 $a_{i}$ 也不是 $b_{r}$ 对于任何 $i, r$，那么
类似地 $\sigma_{2} \sigma_{1}(j)=j$。因此，对于所有可能的 $j \in\{1, \ldots, n\}$，$\sigma_{1} \sigma_{2}(j)=\sigma_{2} \sigma_{1}(j)$，从而 $\sigma_{1} \sigma_{2}= \sigma_{2} \sigma_{1}$。
注意，不相交的循环可能可交换也可能不可交换。例如，
而
(8) 最后，我们有一个美丽的公式：如果 $\sigma \in S_{n}$ 是一个任意元素（不一定是 $k$-循环），且 $\left(a_{1}, \ldots, a_{k}\right)$ 是一个 $k$-循环，那么
换句话说，$\sigma \cdot\left(a_{1}, \ldots, a_{k}\right) \cdot \sigma^{-1}$ 仍然是一个 $k$-循环，但它是一个由 $\sigma$ “重新命名”了元素 $a_{1}, \ldots, a_{k}$ 的 $k$-循环。
为了证明这个公式，我们只需检查
对于每个 $j \in\{1, \ldots, n\}$。首先，如果 $j$ 是 $\sigma\left(a_{i}\right)$ 的形式，对于某个 $i$，那么根据定义
其中，如果 $i=k$，我们照常将 $k+1$ 解释为 $1$。另一方面，
因此，如果 $j=\sigma\left(a_{i}\right)$ 对于某个 $i$，则两边相等。另一方面，如果 $j \neq \sigma\left(a_{i}\right)$ 对于任何 $i$，那么 $\left(\sigma\left(a_{1}\right), \ldots, \sigma\left(a_{k}\right)\right)(j)=j$。但 $j \neq \sigma\left(a_{i}\right) \Longleftrightarrow \sigma^{-1}(j) \neq a_{i}$，所以
因此 $\sigma \cdot\left(a_{1}, \ldots, a_{k}\right) \cdot \sigma^{-1}(j)=\left(\sigma\left(a_{1}\right), \ldots, \sigma\left(a_{k}\right)\right)(j)$ 对于每个 $j \in\{1, \ldots, n\}$，证明了该公式。
在上面的讨论中，我们已经看到了许多循环的计算，特别是两个循环的乘积有时是循环，有时不是循环的例子。更一般地，我们有关于 $S_{n}$ 元素的以下分解结果：
定理 2.1.4. 设 $\sigma \in S_{n}, \sigma \neq 1$。那么 $\sigma$ 是长度至少为 2 的不相交循环的乘积。此外，乘积中的项（循环）的顺序是唯一的。
注 2.1.5. (1) 就像将自然数分解成素数一样，单个循环是循环的“乘积”（它是一个循环的乘积）。
(2) 我们也可以在这个框架中允许 1，约定 1 是空积，即没有循环的“乘积”。
(3) 由于不相交的循环可交换，我们总是可以改变不相交循环的乘积中的顺序，结果将是相同的。然而，定理说这是唯一可能的歧义。
例子 2.1.6. 对于群 $S_{4}$，不相交循环的乘积只有以下几种可能性：(1) 恒等元 1；(2) 对换，即 2-循环；(3) 3-循环；(4) 4-循环；(5) 两个不相交的 2-循环的乘积。恒等元 1 只有一个。对换的数量是 $\binom{4}{2}=6$。对于 3-循环 $(a_{1}, a_{2}, a_{3})$，有 4 种选择 $a_{1}$，然后 3 种选择 $a_{2}$，然后 2 种选择 $a_{3}$，总共有 $4 \cdot 3 \cdot 2=24$ 种选择有序三元组 $(a_{1}, a_{2}, a_{3})$。然而，作为 $S_{4}$ 的元素，$(a_{1}, a_{2}, a_{3})=\left(a_{2}, a_{3}, a_{1}\right)=\left(a_{3}, a_{1}, a_{2}\right)$，因此作为 $S_{4}$ 元素的不同 3-循环的总数是 $24/3=8$。同样，作为 $S_{4}$ 元素的 4-循环的总数是 $4 \cdot 3 \cdot 2 \cdot 1 / 4=6$。最后，为了计算两个不相交的 2-循环的乘积 $(a, b)(c, d)$ 的数量，注意，如上所述， $(a, b)$ 有 6 种选择。 $(a, b)$ 的选择决定了 $c$ 和 $d$，因为 $\{c, d\}=\{1,2,3,4\}-\{a, b\}$。但由于 $(a, b)(c, d)=(c, d)(a, b)$，我们应该将总数除以 2，得到 $6 / 2=3$ 个 $S_{4}$ 元素，它们可以写成两个不相交的 2-循环的乘积。作为检查，将各种可能性加起来得到 $1+6+8+6+3=24$，符合预期。
在这个表示法中，$D_{4}$ 是 $S_{4}$ 的子群，由以下给出
定理的证明给出了一种方法，这种方法在实践中比抽象解释更容易理解和实现。例如，假设我们给定一个与 $2 \times n$ 矩阵对应的具体置换，例如
这是将 $\sigma$ 写成长度至少为 2 的不相交循环的乘积的方法：从 1 开始，我们看到 $\sigma(1)=3, \sigma(3)=5, \sigma(5)=1$，所以我们回到了起点。写下循环 $(1,3,5)$。搜索不在 $(1,3,5)$ 支持集中的元素，我们看到第一个是 2。然后 $\sigma(2)=6, \sigma(6)=4, \sigma(4)=7, \sigma(7)=9, \sigma(9)=2$，所以我们又回到了起点。写下循环 $(2,6,4,7,9)$。再次搜索不在 $(1,3,5)$ 或 $(2,6,4,7,9)$ 支持集中的元素。唯一剩下的元素是 8，且 $\sigma(8)=8$。由于我们省略 1-循环，我们得到分解
为了普遍描述这个过程，我们引入一个新概念。
定义 2.1.7. 设 $\sigma \in S_{n}$。我们定义 $\{1, \ldots, n\}$ 上的一个关系 $\sim_{\sigma}$ 如下：对于 $i, j \in \{1, \ldots, n\}$，$i \sim_{\sigma} j$ 如果存在一个 $a \in \mathbb{Z}$ 使得 $\sigma^{a}(i)=j$。$i$ 在 $\sigma$ 下的轨道是集合
显然，对于每个 $i$，$\sigma\left(O_{\sigma}(i)\right)=O_{\sigma}(i)$，因此 $\sigma$ 定义了一个双射 $O_{\sigma}(i) \rightarrow O_{\sigma}(i)$。
请注意以下几点：
命题 2.1.8. 关系 $\sim_{\sigma}$ 是一个等价关系，并且 $i$ 在 $\sim_{\sigma}$ 下的等价类 $[i]$ 是轨道 $O_{\sigma}(i)$。
证明. 显然 $i=\sigma^{0}(i)$，所以 $i \sim_{\sigma} i$。因此 $\sim_{\sigma}$ 是自反的。如果 $i \sim_{\sigma} j$，那么根据定义存在一个 $r \in \mathbb{Z}$ 使得 $\sigma^{a}(i)=j$。因此 $i=\sigma^{-a}(j)$，所以 $j \sim_{\sigma} i$ 且 $\sim_{\sigma}$ 是对称的。为了看出它是传递的，假设 $i \sim_{\sigma} j$ 且 $j \sim_{\sigma} k$。因此存在 $a, b \in \mathbb{Z}$ 使得 $\sigma^{a}(i)=j$ 且 $\sigma^{b}(j)=k$。那么 $\sigma^{a+b}(i)=\sigma^{b}\left(\sigma^{a}(i)\right)=\sigma^{b}(j)=k$。因此 $i \sim_{\sigma} k$，所以 $\sim_{\sigma}$ 是传递的，因此是一个等价关系。根据定义，等价类 $[i]$ 是 $O_{\sigma}(i)$。
根据等价关系的一般事实，轨道 $O_{\sigma}(i)$ 将 $\{1, \ldots, n\}$ 分割成不相交的子集，即每个整数 $j \in\{1, \ldots, n\}$ 恰好在一个轨道 $O_{\sigma}(i)$ 中。注意 $O_{\sigma}(i)=\{i\} \Longleftrightarrow \sigma$ 固定 $i$。例如，恒等置换有 $n$ 个轨道 $\{1\},\{2\}, \ldots,\{n\}$。一个 $k$-循环 $\left(a_{1}, \ldots, a_{k}\right)$ 且 $k \geq 2$ 有一个轨道 $\left\{a_{1}, \ldots, a_{k}\right\}$ 包含 $k$ 个元素，其余轨道是对于 $i \in\{1, \ldots, n\}$ 且 $i \neq a_{r}$ 对于任何 $r$ 的单元素轨道 $\{i\}$。因此有 $n-k$ 个单元素轨道和一个包含 $k$ 个元素的轨道，总共有 $n-k+1$ 个轨道。再举一个例子，给定上面描述的 $\sigma \in S_{9}$， $\sigma=(1,3,5)(2,6,4,7,9)$，$\sigma$ 的轨道是 $\{1,3,5\}$、 $\{2,4,6,7,9\}$ 和 $\{8\}$。
更一般地，如果 $\sigma=\gamma_{1} \cdots \gamma_{M}$ 是长度至少为 2 的不相交循环的乘积，那么轨道 $O_{\sigma}(i)$ 必须是 $\operatorname{Supp} \gamma_{r}=O_{r}$ 的形式，以及单元素轨道 $\{i\}$，其中 $i \notin \operatorname{Supp} \gamma_{r}$ 对于任何 $r$。换句话说，$\sigma$ 的轨道等于 $O_{1}, \ldots, O_{M}, \ldots O_{N}$，其中 $O_{r}=\operatorname{Supp} \gamma_{r}$ 对于 $r \leq M$，且 $O_{r}$ 是单元素轨道对于 $r>M$。此外，我们必须有 $\sigma\left|O_{r}=\gamma_{r}\right| O_{r}$ 对于所有 $r \leq M$。
注意，虽然 $\sigma$ 决定了轨道，但轨道并不能完全决定 $\sigma$。例如，$\sigma^{\prime}=(1,5,3)(2,9,7,6,4)$ 与 $\sigma=(1,3,5)(2,6,4,7,9)$ 具有相同的轨道集，但 $\sigma^{\prime} \neq \sigma$。另一方面，轨道确实决定了 $\sigma$ 的“形状”，换句话说，它们在此情况下告诉我们上面给出的 $\sigma$ 是一个不相交的 3-循环和一个 5-循环的乘积，并且它们告诉我们 3-循环的支持集是 $\{1,3,5\}$，5-循环的支持集是 $\{2,4,6,7,9\}$。
让我们对上面的等价关系 $\sim_{\sigma}$ 做一些说明。首先，由于 $S_{n}$ 是有限的，每个元素 $\sigma$ 都有有限阶，例如 $\sigma^{d}=1$ 且 $d>0$。那么 $\sigma^{d-1}=\sigma^{-1}$，所以我们可以将 $\sigma$ 的每个负幂也写成正幂。因此
换句话说，给定 $i \in\{1, \ldots, n\}$， $i$ 的轨道是集合 $\left\{i, \sigma(i), \sigma^{2}(i), \ldots\right\}$。归纳地，设 $a_{1}=i$ 并定义 $a_{t+1}=\sigma\left(a_{t}\right)$，因此 $a_{t}=\sigma^{t-1}\left(a_{1}\right)$ 对于 $t \geq 1$。因此轨道 $O_{\sigma}\left(a_{1}\right)$ 就是 $\left\{a_{1}, a_{2}, \ldots\right\}$，其中 $\sigma\left(a_{t}\right)=a_{t+1}$。注意集合 $\left\{a_{1}, a_{2}, \ldots\right\}$ 是有限的，所以一定存在 $s, t \geq 1$ 且 $s \neq t$ 使得 $a_{s}=a_{t}$。设 $k \in \mathbb{N}$ 是最小的整数 $\geq 1$ 使得 $a_{k+1}=\sigma^{k}\left(a_{1}\right)=\sigma^{\ell}\left(a_{1}\right)$ 对于某个 $\ell$ 且 $0 \leq \ell \leq k-1$，即 $a_{k+1}$ 是序列中第一个等于前一项的项。等价地，$k$ 是最大的正整数使得 $a_{1}, \ldots, a_{k}$ 都不同。
引理 2.1.9. 在上述表示法中，$\sigma^{k}\left(a_{1}\right)=a_{1}$。换句话说，序列只有当我们回到起点 $a_{1}$ 时才开始重复。
证明. 假设 $\sigma^{k}\left(a_{1}\right)=\sigma^{\ell}\left(a_{1}\right)$ 对于某个 $\ell$ 且 $0 \leq \ell \leq k-1$，并且 $k$ 是具有此性质的最小正整数。那么 $\sigma^{k-\ell}\left(a_{1}\right)=a_{1}=\sigma^{0}\left(a_{1}\right)$。由于 $0 \leq \ell \leq k-1$， $0<k-\ell \leq k$。根据 $k$ 的定义，我们必须有 $k-\ell=k$，因此 $\ell=0$。这意味着 $\sigma^{k}\left(a_{1}\right)=\sigma^{0}\left(a_{1}\right)=a_{1}$。
我们已经看到 $O_{\sigma}(i)=\left\{\sigma^{t}\left(a_{1}\right): t \geq 0\right\}$。如果 $t \geq 0$，写 $t=k q+\ell$，其中 $0 \leq \ell \leq k-1$ 且 $q \geq 0$，由此可得
其中 $1 \leq \ell+1 \leq k$。这里
因此 $O_{\sigma}\left(a_{1}\right)=\left\{a_{1}, \ldots, a_{k}\right\}$。另请注意 $\sigma\left(O_{\sigma}\left(a_{1}\right)\right)=O_{\sigma}\left(a_{1}\right)$ 并且
然而，如果 $j \notin\left\{a_{1}, \ldots, a_{k}\right\}$，那么 $\left(a_{1}, \ldots, a_{k}\right)(j)=\{j\}$，但当然 $\sigma(j)$ 不一定等于 $j$。
定理 2.1.4 的证明. 利用上述内容，让我们展示一个任意的 $\sigma \in S_{n}$ 可以分解成不相交的循环的乘积，如定理 2.1.4 的陈述。首先，给定 $i \in \{1, \ldots, n\}$，要么 $\sigma(i)=i$，这发生在 $\Longleftrightarrow O_{\sigma}(i)=\{i\}$，要么 $O_{\sigma}(i)$ 至少有两个元素。在第二种情况下，写 $O_{\sigma}(i)=\left\{a_{1}, \ldots, a_{k}\right\}$ 如上，其中 $k=\#\left(O_{\sigma}(i)\right)$ 且 $\sigma\left(a_{r}\right)=a_{r+1}$ 对于 $1 \leq r \leq k-1$ 且 $\sigma\left(a_{k}\right)=a_{1}$。因此，如果 $\gamma$ 是 $k$-循环 $(a_{1}, \ldots, a_{k})$，那么 $\gamma\left(a_{r}\right)=a_{r+1}=\sigma\left(a_{r}\right)$ 对于所有 $a_{r}$，且 $\gamma(j)=j$ 如果 $j \notin\left\{a_{1}, \ldots, a_{k}\right\}=O_{\sigma}(i)=\operatorname{Supp} \gamma$。
现在将 $\sigma$ 的轨道列为 $O_{1}, \ldots, O_{N}$，例如，其中 $O_{1}, \ldots, O_{M}$ 是至少包含两个元素的轨道，而 $O_{M+1}, \ldots, O_{N}$ 是单元素轨道。我们已经看到 $\sigma\left(O_{r}\right)=O_{r}$ 对于每个 $r$。对于每个 $r \leq M$ 的轨道 $O_{r}$，我们找到了一个长度至少为 2 的循环 $\gamma_{r}$，其支持集 $\operatorname{Supp} \gamma_{r}=O_{r}$ 且
换句话说，$\gamma_{r}\left|O_{r}=\sigma\right| O_{r}$ 且 $\gamma_{r} \mid\{1, \ldots, n\}-O_{r}$ 是恒等元。循环 $\gamma_{1}, \ldots, \gamma_{M}$ 两两不相交，因为轨道 $O_{r}$ 两两不相交。通过检查，$\gamma_{1} \cdots \gamma_{M}(j)=\gamma_{r}(j)=\sigma(j)$ 如果 $j \in O_{r}$ 对于某个 $r \leq M$，且 $\gamma_{1} \cdots \gamma_{M}(j)=\sigma(j)=j$ 如果 $j \notin O_{r}$ 对于每个 $r \leq M$。因此 $\sigma=\gamma_{1} \cdots \gamma_{M}$，特别地，$\sigma$ 是长度至少为 2 的不相交循环的乘积。
为了查看唯一性，反之，假设 $\sigma=\gamma_{1} \cdots \gamma_{M}$ 是长度至少为 2 的不相交循环的乘积。我们已经看到 $\sigma$ 的轨道是 $O_{r}=\operatorname{Supp} \gamma_{r}$ 的形式，以及单元素轨道，并且 $\gamma_{r}\left|O_{r}=\sigma\right| O_{r}$。这表明 $\gamma_{r}$ 是如上构造的，从而确立了唯一性。
证明显示以下内容：
推论 2.1.10. 设 $\sigma \in S_{n}$，并假设 $\sigma$ 的轨道是 $O_{1}, \ldots, O_{N}$，其中 $\#\left(O_{r}\right)=k_{r} \geq 2$ 如果 $r \leq M$，且 $\#\left(O_{r}\right)=1$ 如果 $r>M$。那么
其中每个 $\gamma_{r}$ 是一个 $k_{r}$-循环，$\operatorname{Supp} \gamma_{r}=O_{r}$，因此，如果 $r \neq s$，$\gamma_{r}$ 和 $\gamma_{s}$ 是不相交的循环。
我们现在寻找进一步分解 $S_{n}$ 元素的方法，这通常不是唯一的。首先，我们注意到 $k$-循环 $(1, \ldots, k)$ 是对换的乘积：
因为右边将 1 映射到 2，将 2 映射到 1 然后到 3，将 3 映射到 1 然后到 4，依此类推，最后将 $k$ 映射到 1。选择循环 $(1, \ldots, k)$ 并没有什么特别之处：如果 $a_{1}, \ldots, a_{k}$ 是 $\{1, \ldots, n\}$ 的 $k$ 个不同元素，那么
因此，每个 $k$-循环是 $k-1$ 个对换的乘积。由于每个置换 $\sigma \in S_{n}$ 是 $k$-循环的乘积，且每个 $k$-循环是对换的乘积，我们得出结论：
定理 2.2.1. $S_{n}$ 的每个元素 $\sigma$ 是对换的乘积。
直观上，为了置换一个包含 $n$ 个元素的集合，只需相继交换两个元素即可。这意味着 $\binom{n}{2}$ 个对换 $(i, j)$ 且 $i<j$ 生成了群 $S_{n}$。事实上，如习题 3.23 所示，$S_{n}$ 可以由 2 个元素生成，尽管在许多方面，最自然的生成集由 $n-1$ 个元素 $(1,2),(2,3), \ldots,(n-1, n)$ 给出。
很容易看出，通常没有办法唯一地将一个置换写成对换的乘积。例如，我们总是可以插入恒等元，它是一个对换与其自身的乘积 $(i, j)(i, j)$。再举一个例子，对应于 $(1,2,3)=(2,3,1)= (3,1,2)$ 和上面将 3-循环写成对换乘积的方法，我们有
如果这个乘积发生在 $S_{n}, n \geq 5$ 中，那么我们有更多方法将 $(1,2,3)$ 写成对换的乘积，例如 $(1,2,3)=(4,5)(1,3)(2,4)(2,4)(1,2)(4,5)$。
尽管缺乏唯一性，但所有将置换写成对换的乘积的方式有一个共同的特点：
定理 2.2.2. 设 $\sigma \in S_{n}$，并假设 $\sigma=\tau_{1} \cdots \tau_{k}=\rho_{1} \cdots \rho_{\ell}$，其中 $\tau_{i}$ 和 $\rho_{j}$ 都是对换。那么 $k \equiv \ell(\bmod 2)$。换句话说，$S_{n}$ 的给定元素 $\sigma$ 可以写成偶数个对换的乘积或奇数个对换的乘积，但不能同时是两者。
因此 $S_{n}$ 的每个元素都有一个明确定义的奇偶性，即是偶置换还是奇置换，这取决于它是否可以写成偶数个对换的乘积或奇数个对换的乘积。
我们将在后面给出定理 2.2.2 的证明（事实上，概述三种不同的证明）。
定义 2.3.1. 我们定义 $\sigma$ 为偶置换，如果 $\sigma$ 是偶数个对换的乘积；如果 $\sigma$ 是奇数个对换的乘积，则为奇置换。前面定理的内容是偶置换和奇置换是明确定义的，或者更准确地说，一个置换不能同时是偶置换和奇置换。最后我们定义 $A_{n}=\left\{\sigma \in S_{n}: \sigma \text{ 是偶置换} \right\}$。因此 $S_{n}-A_{n}=\left\{\sigma \in S_{n} \text{ 是奇置换} \right\}$。
例子 2.3.2. 我们已经看到，如果 $k \geq 1$（且 1-循环是两个对换的乘积），则 $k$-循环是 $k-1$ 个对换的乘积。因此，如果 $k$ 是奇数，则 $k$-循环是偶置换；如果 $k$ 是偶数，则为奇置换。
引理 2.3.3. 设 $\sigma_{1}$ 和 $\sigma_{2}$ 是 $S_{n}$ 的元素。如果 $\sigma_{1}$ 和 $\sigma_{2}$ 都是偶置换或都是奇置换，那么乘积 $\sigma_{1} \sigma_{2}$ 是偶置换。如果 $\sigma_{1}, \sigma_{2}$ 中一个偶置换另一个奇置换，那么乘积 $\sigma_{1} \sigma_{2}$ 是奇置换。
证明. 假设 $\sigma_{1}$ 可以写成 $k$ 个对换的乘积 $\tau_{1} \cdots \tau_{k}$，且 $\sigma_{2}$ 可以写成 $\ell$ 个对换的乘积 $\rho_{1} \cdots \rho_{\ell}$。那么 $\sigma_{1} \sigma_{2}=\tau_{1} \cdots \tau_{k} \rho_{1} \cdots \rho_{\ell}$ 是 $k+\ell$ 个对换的乘积。（令人困惑的是，对于乘积 $\sigma_{1} \sigma_{2}$，我们取对换数量的和。）由此，引理的证明是清楚的：如果 $k$ 和 $\ell$ 都是偶数或都是奇数，那么 $k+\ell$ 是偶数；如果 $k, \ell$ 中一个偶数另一个奇数，那么 $k+\ell$ 是奇数。
定义 2.3.4. 如果 $\sigma \in S_{n}$，我们定义 $\varepsilon(\sigma)=1$，如果 $\sigma$ 是偶数个对换的乘积，且 $\varepsilon(\sigma)=-1$，如果 $\sigma$ 是奇数个对换的乘积。因此 $\varepsilon: S_{n} \rightarrow \{ \pm 1\}$，其中 $A_{n}=\varepsilon^{-1}(1)$。引理 2.3.3 可以改写为 $\varepsilon\left(\sigma_{1} \sigma_{2}\right)=\varepsilon\left(\sigma_{1}\right) \varepsilon\left(\sigma_{2}\right)$。
推论 2.3.5. $A_{n}$ 是 $S_{n}$ 的一个子群，即交错群。
证明. 如果 $\sigma_{1}, \sigma_{2} \in A_{n}$，那么 $\sigma_{1}$ 和 $\sigma_{2}$ 都是偶置换，因此 $\sigma_{1} \sigma_{2}$ 是偶置换，所以 $\sigma_{1} \sigma_{2} \in A_{n}$。因此 $A_{n}$ 对乘积封闭。元素 1 是偶置换，即 $1 \in A_{n}$，无论是形式上（1 是 0 个对换的乘积，而 0 是偶数）还是通过写成 $1=(a, b)(a, b)$，只要 $n \geq 2$ 即可。最后，如果 $\sigma \in A_{n}$，那么 $\sigma=\tau_{1} \cdots \tau_{k}$ 是 $k$ 个对换的乘积，其中 $k$ 是偶数。那么
即 $\sigma^{-1}$ 是对换 $\tau_{1}, \ldots, \tau_{k}$ 按相反顺序的乘积。（这里，我们使用了 $\tau_{i}^{-1}=\tau_{i}$ 这一事实，但我们只需要 $\tau_{i}^{-1}$ 仍然是对换。）特别地，$\sigma^{-1}$ 是偶数个对换的乘积（等价地，证明表明 $\varepsilon\left(\sigma^{-1}\right)=\varepsilon(\sigma)$），因此 $\sigma^{-1} \in A_{n}$。因此 $A_{n}$ 是 $S_{n}$ 的一个子群。
例子 2.3.6. 首先注意，正如我们已经看到的，如果 $k$ 是奇数，则 $k$-循环是偶置换；如果 $k$ 是偶数，则为奇置换。因此我们可以确定任何循环乘积的奇偶性（无论它们是否不相交）。这给出了小 $n$ 值子群 $A_{n}$ 的以下描述： $A_{1}=S_{1}=\{1\}$。$A_{2}=\{1\}$。$A_{3}$ 由 1 以及 $S_{3}$ 中的两个不同的 3-循环组成： $A_{3}=\{1,(1,2,3),(1,3,2)\}$。$A_{4}$ 由 1、8 个 3-循环和 3 个两个不相交的 2-循环的乘积组成。因此 $\#\left(A_{4}\right)=12= \frac{1}{2} \#\left(S_{4}\right)$，事后看来我们也看到 $\#\left(A_{2}\right)=1=\frac{1}{2} \#\left(S_{2}\right)$ 且 $\#\left(A_{3}\right)=3=\frac{1}{2} \#\left(S_{3}\right)$。这并非巧合：
命题 2.3.7. 对于 $n \geq 2, \#\left(A_{n}\right)=\frac{1}{2} \#\left(S_{n}\right)=n!/ 2$。
证明. 由于 $S_{n}$ 的每个元素要么是偶置换要么是奇置换，$S_{n}$ 是偶置换集合 $A_{n}$ 和奇置换集合 $S_{n}-A_{n}$ 的不相交并集。我们将找到一个从 $A_{n}$ 到 $S_{n}-A_{n}$ 的双射。这将意味着 $\#\left(A_{n}\right)=\#\left(S_{n}-A_{n}\right)$，因此
因此 $\#\left(A_{n}\right)=\frac{1}{2} \#\left(S_{n}\right)$。
为了找到一个从 $A_{n}$ 到 $S_{n}-A_{n}$ 的双射，选择一个奇置换 $\tau$。例如，我们可以取 $\tau=(1,2)$。注意这只有当 $n \geq 2$ 时才可能，因为对于 $n=1, S_{1}=\{1\}$ 且每个置换都是平凡的偶置换。然后定义一个函数 $f: A_{n} \rightarrow S_{n}-A_{n}$，规则如下：
即 $\sigma$ 与固定的奇置换 $\tau$ 的乘积。注意，如果 $\sigma \in A_{n}$，那么 $\sigma$ 是偶置换，因此 $\tau \sigma$ 是奇置换，所以 $f$ 确实是一个从 $A_{n}$ 到 $S_{n}-A_{n}$ 的函数。为了证明 $f$ 是一个双射，只需找到一个逆函数，即一个函数 $g: S_{n}-A_{n} \rightarrow A_{n}$ 使得 $f \circ g$ 和 $g \circ f$ 都是恒等函数（在其各自的定义域上）。定义 $g: S_{n}-A_{n} \rightarrow A_{n}$，规则如下：
例如，如果我们选择了 $\tau=(1,2)$，那么 $\tau^{-1}=(1,2)$ 也是。如果 $\tau$ 是奇置换，那么 $\tau^{-1}$ 是奇置换，因此，如果 $\rho$ 也是奇置换，那么 $\tau^{-1} \rho$ 是偶置换。因此 $g$ 确实是一个从 $S_{n}-A_{n}$ 到 $A_{n}$ 的函数。如果 $\sigma \in A_{n}$，
那么 $g \circ f(\sigma)=\tau^{-1} \tau \sigma=\sigma$；如果 $\rho \in S_{n}-A_{n}$，那么 $f \circ g(\rho)=\tau \tau^{-1} \rho=\rho$。因此 $f \circ g=\operatorname{Id}_{S_{n}-A_{n}}$ 且 $g \circ f=\operatorname{Id}_{A_{n}}$，所以 $g=f^{-1}$ 且 $f$ 是一个双射。
注 2.3.8. 设 $\ell_{\tau}: S_{n} \rightarrow S_{n}$ 是 $\tau$ 的左乘：对于所有 $\sigma \in S_{n}, \ell_{\tau}(\sigma)=\tau \sigma$。我们已经看到 $\ell_{\tau}$ 是一个双射，其逆元为 $\ell_{\tau^{-1}}$。上面的证明表明，如果 $\tau$ 是奇置换，则 $\ell_{\tau}\left(A_{n}\right)= S_{n}-A_{n}$ 且 $\ell_{\tau}\left(S_{n}-A_{n}\right)=A_{n}$。然而，如果 $\tau$ 是偶置换，则 $\ell_{\tau}\left(A_{n}\right)=A_{n}$ 且 $\ell_{\tau}\left(S_{n}-A_{n}\right)=S_{n}-A_{n}$。
群 $A_{n}$ 是一个具有根本重要性的群，原因将逐渐显现，并且在第二部分中也将发挥重要作用。特别是，$A_{5}$ 是一个非常特殊的群。
我们将描述定理 2.2.2 的三种不同证明；每一种都具有启发性。
第一个证明. 考虑正整数
它是 1 和 $n$ 之间所有不同正整数对的差的乘积，其中我们总是取正差。这里 $N_{n}$ 的确切值不重要（练习：证明 $N_{n}=(n-1)!(n-2)!\cdots 2!1!$）；显然，$N_{n}$ 是某个大的正整数，关键是它非零，因为没有因子是零。给定 $\sigma \in S_{n}$，考虑当我们考虑乘积 $\prod_{1 \leq i<j \leq n}(\sigma(j)-\sigma(i))$ 时会发生什么。这仍然是 1 和 $n$ 之间所有不同正整数对的差的乘积，但由于 $\sigma$ 混淆了顺序，我们不总是用较大的减去较小的。因此，存在一个符号，即存在一个元素 $\varepsilon(\sigma) \in\{ \pm 1\}$，使得
注意 $\varepsilon(\sigma)$ 只取决于 $\sigma$，而不取决于 $\sigma$ 如何表示为对换的乘积。事实上， $\varepsilon(\sigma)=(-1)^{a}$，其中 $a$ 是满足 $i<j$ 且 $\sigma(i)>\sigma(j)$ 的对 $(i, j)$ 的数量。
关于 $\varepsilon(\sigma)$ 我们需要的两个主要事实是
(1) 对于所有 $\sigma_{1}, \sigma_{2} \in S_{n}, \varepsilon\left(\sigma_{1} \sigma_{2}\right)=\varepsilon\left(\sigma_{1}\right) \varepsilon\left(\sigma_{2}\right)$（即 $\varepsilon$ 是乘法的）；和
(2) 如果 $\tau=(a, b)$ 是一个对换，那么 $\varepsilon(\tau)=-1$。
假设 (1) 和 (2) 成立，让我们完成证明。如果 $\sigma=\tau_{1} \cdots \tau_{k}$ 是对换的乘积，那么反复使用 (1)，然后使用 (2)，我们看到
因此，如果 $\sigma$ 是偶数个对换的乘积，则 $\varepsilon(\sigma)=1$；如果 $\sigma$ 是偶数个对换的乘积，则 $\varepsilon(\sigma)=-1$。特别地，如果 $\sigma=\rho_{1} \cdots \rho_{\ell}$ 且 $\rho_{i}$ 是对换，那么 $\varepsilon(\sigma)=(-1)^{\ell}=(-1)^{k}$，因此 $k \equiv \ell(\bmod 2)$。
(1) 的证明. 首先注意，根据定义，
此外，每个单独的因子 $\frac{\sigma(j)-\sigma(i)}{j-i}$ 只取决于无序对 $\{i, j\}$，而不取决于 $i<j$ 的选择，因为
根据定义，
右边的项是 $\varepsilon\left(\sigma_{2}\right)$。至于另一项，乘积中的每一项都是 $\frac{\sigma_{1}\left(\sigma_{2}(j)\right)-\sigma_{1}\left(\sigma_{2}(i)\right)}{\sigma_{2}(j)-\sigma_{2}(i)}$。置换 $\sigma_{2}$ 诱导一个从 $\{1, \ldots, n\}$ 的两元素子集到自身的双射。正如我们在 (1) 的证明开头所指出的，项 $\frac{\sigma_{1}\left(\sigma_{2}(j)\right)-\sigma_{1}\left(\sigma_{2}(i)\right)}{\sigma_{2}(j)-\sigma_{2}(i)}$ 不取决于 $\sigma_{2}(i)<\sigma_{2}(j)$ 是否成立。因此上面的第一项就是 $\varepsilon\left(\sigma_{1}\right)$。结合起来，我们看到 $\varepsilon\left(\sigma_{1} \sigma_{2}\right)=\varepsilon\left(\sigma_{1}\right) \varepsilon\left(\sigma_{2}\right)$。
(2) 的证明. 假设 $\tau=(a, b)$ 是一个对换，我们可以假设 $a<b$。我们检查对于哪些对 $i<j, 1 \leq i<j \leq n$，差值 $\tau(j)-\tau(i)$ 是负数。注意，如果 $i$ 和 $j$ 都不等于 $a$ 或 $b$，那么 $\tau(j)-\tau(i)=j-i>0$。因此我们可以假设 $i, j$ 中至少有一个是 $a$ 或 $b$。如果 $j=a$，那么 $i<a$，因此 $i<b$，且
因此对 $a-i$ 的差仍然是正数。类似地，如果 $i=b$ 且 $j>b$，那么 $\tau(j)-\tau(b)= j-a>j-b>0$。暂时，我们也假设 $(i, j) \neq(a, b)$，即要么 $j=b$ 要么 $i=a$，但不能同时是。所以唯一可能的符号变化来自：要么 $i=a$，因此 $j-i=j-a$，且 $j>a$，要么 $j=b$，因此 $j-i=b-i$，且 $i<b$。首先考虑 $j-a$ 的情况。如果 $j>b$，那么 $\tau(j)-\tau(a)=j-b>0$。如果 $b>j>a$，那么 $\tau(j)-\tau(a)=j-b<0$，且有 $b-a-1$ 个这样的 $j$，所以这些贡献了一个因子 $(-1)^{b-a-1}$。同样，当我们看差值 $b-i$ 时，那么 $\tau(b)-\tau(i)=a-i$。如果 $i<a$，符号保持不变，但如果 $a<i<b$，则变为负数。同样，有 $b-a-1$ 个这样的 $i$，所以这些贡献了另一个因子 $(-1)^{b-a-1}$，它抵消了第一个因子 $(-1)^{b-a-1}$。我们尚未考虑的唯一剩下的整数对是 $i=a$ 和 $j=b$ 的对。这里 $\tau(b)-\tau(a)=a-b=-(b-a)$，所以还有一个未被抵消的因子 $-1$。因此，符号变化的总数是
最后，我们注意到一个在现代代数II中有用的事实：我们选择了 1 和 $n$ 之间的整数并观察它们的差值并没有关系。我们可以从任何序列 $t_{1}, \ldots, t_{n}$ 开始，例如，所有都不同的实数，或者独立变量，并观察乘积 $\prod_{1 \leq i<j \leq n}\left(t_{i}-t_{j}\right)$。将这个乘积与我们置换对后的乘积进行比较，即 $\prod_{1 \leq i<j \leq n}\left(t_{\sigma(i)}-t_{\sigma(j)}\right)$，上述分析表明
其中 $\varepsilon(\sigma) \in\{ \pm 1\}$ 是上面引入的符号因子。
第二个证明. 这个证明使用行列式的基本性质，行列式与置换和符号密切相关，因此必须小心不要进行循环论证。特别是，我们必须小心，我们定义行列式并证明了其基本性质，而没有提及置换和置换的符号。例如，可以通过沿第一行展开来归纳地定义行列式。对于 $\sigma \in S_{n}$，我们将定义 $\varepsilon(\sigma) \in\{ \pm 1\}$，它具有第一个证明中的性质 (1) 和 (2)，从而表明，如果 $\sigma=\tau_{1} \cdots \tau_{k}$ 是 $k$ 个对换的乘积，那么 $\varepsilon(\sigma)=(-1)^{k}$；然后论证的结论与第一个证明相同。为了定义 $\varepsilon(\sigma)$，我们首先将 $\sigma$ 与一个 $n \times n$ 矩阵 $P(\sigma)$ 相关联。从线性代数中回忆，一个 $n \times n$ 矩阵 $P(\sigma)$ 与一个线性映射 $\mathbb{R}^{n} \rightarrow \mathbb{R}^{n}$ 是相同的，我们也用 $P(\sigma)$ 表示，并且这样的线性映射由其在标准基 $\mathbf{e}_{1}, \ldots, \mathbf{e}_{n}$ 上的值指定；事实上，值 $P(\sigma)\left(\mathbf{e}_{i}\right)$，写成列向量，是 $P(\sigma)$ 的第 $i$ 列。因此定义 $P(\sigma)\left(\mathbf{e}_{i}\right)=\mathbf{e}_{\sigma(i)}$。那么 $P(\sigma)$ 是一个置换矩阵：每行和每列都具有除了一个元素外，所有元素都为 0，并且非零元素为 1 的性质。显然 $P(1)=I$。计算表明
因此 $P\left(\sigma_{1} \sigma_{2}\right)$ 和 $P\left(\sigma_{1}\right) P\left(\sigma_{2}\right)$ 在每个基向量上的值相同，因此在所有向量上值也相同，从而 $P\left(\sigma_{1} \sigma_{2}\right)=P\left(\sigma_{1}\right) P\left(\sigma_{2}\right)$。现在，为了将矩阵 $P(\sigma)$ 转换为一个数，我们使用行列式 $\det$。定义 $\varepsilon(\sigma)=\operatorname{det} P(\sigma)$。就目前而言， $\varepsilon(\sigma)$ 只是一个实数。使用行列式的乘法性质，对于所有 $\sigma_{1}, \sigma_{2} \in S_{n}$，我们有
显然 $\varepsilon(1)=\operatorname{det} I=1$。此外，如果 $\tau=(i, j)$ 是一个对换，那么 $P(\tau)$ 是通过交换 $I$ 的第 $i$ 列和第 $j$ 列得到的。行列式的另一个众所周知的性质是，在这种情况下，$\operatorname{det} P(\tau)=-\operatorname{det} I=-1$。综合起来，我们看到，如果 $\sigma=\tau_{1} \cdots \tau_{k}$ 是对换的乘积，那么，如第一个证明所示，
因此 $k$ 总是偶数或总是奇数。
注 2.4.1. 如果 $A \in \mathbb{M}_{n}(\mathbb{R})$，$\operatorname{det} A$ 关于 $\varepsilon$ 的显式公式如下：写 $A=\left(a_{i j}\right)$，
例如，当 $n=2$ 时，$S_{2}=\{1,(1,2)\}$，其中 $\varepsilon(1)=1$ 且 $\varepsilon((1,2))=-1$。因此 $\operatorname{det} A= a_{11} a_{22}-a_{12} a_{21}$。然而，这个公式不适合计算。
第三个证明. 在这个证明中，我们不直接定义函数 $\varepsilon$，而只是使用关于 $\sigma$ 的轨道的信息来查看 $\sigma$ 不能同时是偶数个对换和奇数个对换的乘积。对于任何 $\sigma \in S_{n}$，定义 $N(\sigma)$ 为 $\sigma$ 的轨道数，包括单元素轨道。例如，正如我们之前看到的，如果 $\sigma$ 是一个 $r$-循环，那么 $N(\sigma)=n-r+1$。第三个证明的关键是：
断言 2.4.2. 如果 $\sigma \in S_{n}$ 是 $k$ 个对换的乘积，即 $\sigma=\tau_{1} \cdots \tau_{k}$，其中每个 $\tau_{i}$ 是一个对换，那么
为了看出断言 2.4.2 暗示了定理，假设 $\sigma=\tau_{1} \cdots \tau_{k}=\rho_{1} \cdots \rho_{\ell}$，其中 $\tau_{i}$ 和 $\rho_{j}$ 是对换。那么我们既有 $N(\sigma) \equiv n-k(\bmod 2)$ 又有 $N(\sigma) \equiv n-\ell (\bmod 2)$，因此 $k \equiv \ell(\bmod 2)$。
断言 2.4.2 的证明. 我们用归纳法证明断言 2.4.2。注意，如果 $k=0$，那么根据约定 $\sigma$ 是空积，因此是恒等元 1，它有 $n$ 个轨道 $\{1\},\{2\}, \ldots,\{n\}$，且 $N(1)=n=n-0$。如果 $k=1$，那么 $\sigma$ 是一个对换，因此是一个 2-循环，因此 $N(\sigma)=n-2+1=n-1$（根据断言陈述前的讨论），所以断言中的同余实际上是一个等式。通过归纳，假设断言对于所有 $k \geq 1$ 个对换的乘积都成立，并考虑 $k+1$ 个对换的乘积，例如 $\sigma=\tau_{1} \tau_{2} \cdots \tau_{k} \tau_{k+1}$。如果我们设 $\rho=\tau_{2} \cdots \tau_{k+1}$，那么根据归纳假设 $N(\rho) \equiv n-k(\bmod 2)$，我们必须证明 $N\left(\tau_{1} \rho\right) \equiv n-k-1(\bmod 2) \equiv N(\rho)-1(\bmod 2)$。由于 $1 \equiv -1(\bmod 2)$，只需证明以下内容：
断言 2.4.3. 如果 $\rho \in S_{n}$ 且 $\tau \in S_{n}$ 是一个对换，那么
事实上，$N(\tau \rho)=N(\rho) \pm 1$。
断言 2.4.3 的证明. 由于 $\tau$ 是一个对换，我们可以写 $\tau=(a, b)$ 对于某个 $a, b \in\{1, \ldots, n\}$，$a \neq b$。注意 $a$ 和 $b$ 各自恰好在 $\rho$ 的一个轨道中（可能是同一个轨道）。设 $O=O_{\rho}\left(a_{1}\right)$ 是 $\rho$ 的一个轨道。如果 $a$ 和 $b$ 都不在 $O$ 中，将 $O$ 的元素写为 $a_{1}, \rho\left(a_{1}\right)=a_{2}, \ldots, \rho\left(a_{r-1}\right)=a_{r}, \rho\left(a_{r}\right)=a_{1}$。由于对于所有 $i, a_{i} \neq a, b, \tau\left(a_{i}\right)=a_{i}$。因此 $(\tau \rho)\left(a_{i}\right)=\rho\left(a_{i}\right)=a_{i+1}$，对于 $i<k$，且 $(\tau \rho)\left(a_{r}\right)=a_{1}$。因此 $O=O_{\tau \rho}\left(a_{1}\right)$ 也是 $\tau \rho$ 的一个轨道。现在让我们考虑包含 $a, b$ 或两者的轨道。有两种情况：
情况 I. 存在 $\rho$ 的一个轨道 $O$ 使得 $a$ 和 $b$ 都在 $O$ 中。在这种情况下，我们断言 $N(\tau \rho)=N(\rho)+1$。如上所述，我们可以将 $O$ 写为 $\left\{a_{1}, a_{2}, \ldots, a_{r}\right\}$，其中 $\rho\left(a_{i}\right)=a_{i+1}$ 对于 $i<r$ 且 $\rho\left(a_{r}\right)=a_{1}$。我们不妨假设 $a_{1}=a$；因此，$b=a_{t}$ 对于某个 $t>1$。那么，对于 $i<t-1$， $(\tau \rho)\left(a_{i}\right)=\tau\left(a_{i+1}\right)=a_{i+1}$。然而，对于 $i=t-1$，
因此 $\left\{a_{1}, \ldots, a_{t-1}\right\}$ 是 $\tau \rho$ 的一个完整轨道 $O^{\prime}=O_{\tau \rho}(a)$。现在考虑 $b$ 在 $\tau \rho$ 下的轨道 $O^{\prime \prime}=O_{\tau \rho}(b)$。如果 $t \leq i<r,(\tau \rho)\left(a_{i}\right)=\tau\left(a_{i+1}\right)=a_{i+1}$。但对于 $i=r$，
因此 $\left\{a_{t}, \ldots, a_{r}\right\}$ 仍然是 $\tau \rho$ 的一个完整轨道 $O^{\prime \prime}=O_{\tau \rho}(b)$。因此 $\rho$ 的轨道 $O$ 分裂成 $\tau \rho$ 的两个轨道 $O^{\prime}$ 和 $O^{\prime \prime}$，而所有其他轨道保持不变。因此 $N(\tau \rho)=N(\rho)+1$。
情况 II. 存在 $\rho$ 的两个不相交的轨道 $O_{1}=O_{\rho}(a)$ 和 $O_{2}=O_{\rho}(b)$，使得 $a \in O_{1}$ 且 $b \in O_{2}$。如上所述，我们可以将 $O_{1}$ 的元素写为 $\left\{a_{1}, a_{2}, \ldots, a_{r}\right\}$，其中 $\rho\left(a_{i}\right)=a_{i+1}$ 对于 $i<k, \rho\left(a_{r}\right)=a_{1}$，且 $a_{1}=a$。同样，我们可以将 $O_{2}$ 的元素写为 $\left\{b_{1}, b_{2}, \ldots, b_{s}\right\}$，其中 $\rho\left(b_{j}\right)=b_{j+1}$ 对于 $i<s, \rho\left(b_{s}\right)=b_{1}$，且 $b_{1}=b$。那么，对于 $i<r,(\tau \rho)\left(a_{i}\right)=\tau\left(a_{i+1}\right)=a_{i+1}$。对于 $i=r$，
对于 $j<s,(\tau \rho)\left(b_{j}\right)=\tau\left(b_{j+1}\right)=b_{j+1}$。对于 $j=s$，
因此 $O=\left\{a_{1}, a_{2}, \ldots, a_{r}, b_{1}, b_{2}, \ldots, b_{s}\right\}$ 是 $\tau \rho$ 的一个单轨道 $O_{\tau \rho}(a)$。换句话说，$\rho$ 的两个轨道 $O_{1}$ 和 $O_{2}$ 变成了 $\tau \rho$ 的一个轨道，而所有其他轨道保持不变。因此 $N(\tau \rho)=N(\rho)-1$。这完成了断言 2.4.3 的证明，从而也完成了定理 2.2.2 的证明。
习题 3.1. 通过因式分解，9 和 16 的最大公约数是 1。通过试错法（或者如果你以前见过欧几里得算法，则使用更系统的方法），找到整数 $n$ 和 $m$ 使得 $9 n+16 m=1$。