§ 5 循环表示

定义 5.1 设有一个群作用

G \to \mathrm{Aut}_{\text{set}}

作用在集合 $X$ 上。固定 $g \in G$ 。我们称 $g$ 在 $X$ 上的作用 为

\langle g \rangle \to G \to \mathrm{Aut}_{\text{set}}。

其中 $\langle g \rangle \to G$ 是群同态，因为子群的包含映射是群同态。 $\langle g \rangle \to \mathrm{Aut}_{\text{set}}$ 是群同态，因为两个群同态的复合仍是群同态。

本质上， $g$ 在 $X$ 上的作用可以通过将 $g$ 分解为循环来用循环表示法表示，其中每个循环对应于 $g$ 在 $X$ 上作用的一个轨道。

§ 5.1 循环

定义 5.2 如果 $\sigma \in S_{n}$ ，且 $\sigma$ 在 $\underline{n}$ 上的作用至多有一个轨道的大小 $\geqslant 2$ ，则称 $\sigma$ 为一个 循环(cycle)。

例 5.1

$\sigma = 1_{S_{n}}$ 只有大小为 $1$ 的轨道，所以 $1_{S_{n}}$ 是一个循环。
设 $\tau: \underline{4} \to \underline{4}$ 定义为：
$\begin{aligned} 1 &\mapsto 2\\ 2 &\mapsto 1\\ 3 &\mapsto 4\\ 4 &\mapsto 3 \end{aligned}$
我们可以绘制为

这不是一个循环，因为它有两个大小 $\geqslant 2$ 的轨道： $\{1,2\}$ 和 $\{3,4\}$ 。

对于 $\tau: \underline{5} \to \underline{5}$ 定义为： $\begin{aligned} 1 &\mapsto 1\\ 2 &\mapsto 2\\ 3 &\mapsto 5\\ 4 &\mapsto 3\\ 5 &\mapsto 4 \end{aligned}$ 绘制为

这是一个循环。

定义 5.3 如果 $\sigma \in S_{n}$ 是一个循环，我们用 $\underline{\sigma} \subset \underline{n}$ 表示大小 $\geqslant 2$ 的轨道。对于 $\sigma = 1_{G}$ ，我们定义

\underline{1_{G}} := \varnothing。

§ 5.2 不相交循环

例 5.2

$\underline{\sigma}$ 是一个子集，所以元素的顺序无关紧要。例如，它不是某个集合加上一个顺序的选择。

定义 5.4 如果 $\sigma, \tau \in S_{n}$ 是循环，我们说 $\sigma$ 和 $\tau$ 是不相交的循环(disjoint cycle)，当且仅当 $\underline{\sigma}$ 和 $\underline{\tau}$ 不相交。

例 5.3

$1_{G}$ 与任何循环都是不相交的。
和不是不相交的，因为 $\{1,2\}$ 和 $\{2,3\}$ 有交集。
和是不相交的。

命题 5.1 $S_{n}$ 中不相交循环是可交换的。

证明：设 $\sigma$ 和 $\tau$ 是不相交循环，取 $k \in \underline{n} = \{1,2,\ldots,n\}$ 。则

\begin{aligned} (\sigma \circ \tau)(k) &= \begin{cases} \sigma(k) & \text{如果 } k \notin \underline{\tau}\\ \tau(k) & \text{如果 } k \in \underline{\tau} \end{cases} \\ &= \begin{cases} \sigma(k) & \text{如果 } k \in \underline{\sigma}\\ k & \text{如果 } k \notin \underline{\sigma}, \underline{\tau}\\ \tau(k) & \text{如果 } k \in \underline{\tau} \end{cases} \end{aligned}

因为

\begin{align*} k \notin \underline{\tau} &\Rightarrow \tau(k) = k \\ &\Rightarrow \sigma(\tau(k)) = \sigma(k) \\ k \in \underline{\tau} &\Rightarrow \tau(k) \in \underline{\tau} \tag*{轨道的定义} \\ &\Rightarrow \tau(k) \notin \underline{\sigma} \tag*{不相交的定义} \\ &\Rightarrow \sigma(\tau(k)) = \tau(k) \end{align*}

而

\begin{aligned} (\tau \circ \sigma)(k) &= \begin{cases} \tau(k) & \text{如果 } k \notin \underline{\sigma}\\ \sigma(k) & \text{如果 } k \in \underline{\sigma} \end{cases} \\ &= \begin{cases} \tau(k) & \text{如果 } k \in \underline{\tau}\\ k & \text{如果 } k \notin \underline{\sigma}, \underline{\tau}\\ \sigma(k) & \text{如果 } k \in \underline{\sigma} \end{cases} \end{aligned}

因此 $\sigma \circ \tau = \tau \circ \sigma$ 。

~\tag*{$\square$}

§ 5.3 循环表示

定义 5.5 设 $\sigma$ 是一个循环。 $\sigma$ 的循环表示（cycle notation） 是表达式

(a~\sigma(a)~\sigma^{2}(a)~\cdots~\sigma^{|\sigma|-1}(a))

其中 $a \in \underline{\sigma}$ 。

例 5.4 如果 $\sigma \in S_{5}$ 如图所示：

则以下都是 $\sigma$ 的循环表示：

\begin{array}{cccc} (1~2~3~5), & (2~3~5~1), & (5~1~2~3), & (3~5~1~2). \\ a=1 & a=2 & a=5 & a=3 \end{array}

例 5.5 如果 $\tau \in S_{5}$ 如图所示：

$\underline{\tau} = \underline{\sigma}$ ，但 $\tau$ 的任何循环表示法都不是 $\sigma$ 的循环表示法。

(1~2~5~3), (2~5~3~1), (5~3~1~2), (3~1~2~5)。

隐含地，我们在对 $\sigma$ 的各种循环表示法进行辨认。

定理 5.2 每个元素

\sigma \in S_{n}

都可以写成不相交循环的乘积，且除了顺序外是唯一的。

证明：对于 $\sigma \in S_{n}$ ，设 $\{\mathcal{O}_{a}\}$ 是 $\sigma$ 在 $\underline{n}$ 上作用的轨道集合。对于每个 $\mathcal{O}_{a} \in \underline{n}/\langle \sigma \rangle$ ，选择 $a \in \mathcal{O}_{a}$ ，并设

\sigma_{a} = (a~\sigma(a)~\cdots~\sigma^{|\mathcal{O}_{a}|-1}(a))

作为一个循环。则根据定义，

\sigma = \prod_{\mathcal{O}_{a}} \sigma_{a}

因为

\prod_{\mathcal{O}_{a}} \sigma_{a}(k) = \sigma(k)

根据定义。此外，我们写成

\prod_{\mathcal{O}_{a}} \sigma_{a} = \sigma_{a} \cdot \sigma_{b} \cdot \cdots \cdot \sigma_{z}

而没有指定顺序，这是因为每个 $\sigma_{a}$ 和 $\sigma_{b}$ 是不相交的（由于轨道的不相交性），因此是可交换的（即顺序无关）。

关于唯一性：如果另一个人写成

\sigma = \prod \tau_{i} = \tau_{1} \cdot \tau_{2} \cdots \tau_{k}

其中 $\{\tau_{i}\}$ 是一组不相交的循环，那么注意到

\{\tau_{i}\} = \underline{n}/\langle \sigma \rangle。

因此，对于每个 $i$ ，存在唯一的 $\sigma_{a}$ ，使得 $\underline{\sigma_{a}} = \underline{\tau_{i}}$ 。写 $\tau_{i} = (b_{0}~b_{1}~\cdots~b_{|\tau_{i}|-1})$ ，我们看到 $\sigma(b_{i}) = b_{i+1}$ ，因此证明完毕。

~\tag*{$\square$}

例 5.6 令 $\sigma \in S_{8}$ 定义为

则

\begin{aligned} \sigma &= (7~8~4) \circ (1~2~6) \circ (3~5) \\ &= (1~2~6)(7~8~4)(3~5) \\ &= (1~2~6)(3~5)(7~8~4) \quad \text{等等} \end{aligned}

我们可以将 $(1~2~6)$ 作为 $S_{8}$ 中的循环及其循环表示。 $(1~2~6)$ 是 $S_{8}$ 中的元素，其图示为

在第二个等式中，为了简洁，我们省略了组合符号 “ $\circ$ ”。

定义 5.6 对于 $\sigma \in S_{n}$ ， $\sigma$ 的循环表示法是表达式

\sigma = \sigma_{1} \cdots \sigma_{k}

其中每个 $\sigma_{i}$ 是一个循环，且当 $i \neq j$ 时，每对 $\sigma_{i}$ 和 $\sigma_{j}$ 是不相交的。

例 5.7 如果 $\sigma \in S_{5}$ 如图所示：

则以下是 $\sigma$ 的循环表示：

\begin{array}{cc} (1~2~4)(3~5) & (3~5)(1~2~4) \\ (1~2~4)(5~3) & (5~3)(1~2~4) \\ (4~1~2)(3~5) & (3~5)(4~1~2) \\ (4~1~2)(5~3) & (5~3)(4~1~2) \\ (2~4~1)(3~5) & (3~5)(2~4~1) \\ (2~4~1)(5~3) & (5~3)(2~4~1) \end{array}

所有这些都表示相同的 $\sigma$ 。

例 5.8 令

\begin{aligned} \sigma &= (1~2)(3~4) \\ \tau &= (1~2~3) \end{aligned}

则循环的逆就是将循环反向读取：

\begin{aligned} \tau^{-1} &= (3~2~1) \\ \sigma^{-1} &= (2~1)(4~3) = \sigma \end{aligned}

我们可以计算

\begin{aligned} \tau \sigma \tau^{-1} &= (1~2~3) \circ (1~2)(3~4) \circ (3~2~1) \\ &= (1~4)(2~3) \\ \sigma \tau \sigma^{-1} &= (1~2)(3~4) \circ (1~2~3) \circ (1~2)(3~4) \\ &= (3)(4~2~1) \\ &= (4~2~1) \end{aligned}

注意 $(\text{某元素})\sigma(\text{某元素})^{-1}$ 与 $\sigma$ 具有相同的循环形状。这将有助于我们分类 $S_{n}$ 的共轭类。

§ 5.4 $S_{n}$ 中的共轭类

循环表示给我们带来一些美妙的结果。

命题 5.3 (1) 设 $\sigma \in S_{n}$ 是一个循环，所以

\sigma = (a_{1}~\cdots~a_{k})

其中 $a_{i+1} = \sigma(a_{i})$ 。则

\sigma^{-1} = (a_{k}~\cdots~a_{1})

即， $\sigma^{-1} = (b_{1}~\cdots~b_{k})$ ，其中 $b_{i} = \sigma(b_{i+1})$ ，且 $b_{k} = a_{1}$ 。

(2) 更一般地，如果

\sigma = \sigma_{1} \sigma_{2} \cdots \sigma_{k}

其中 $\sigma_{i}$ 是不相交的循环，则

\sigma^{-1} = \sigma_{1}^{-1} \cdots \sigma_{k}^{-1}

(3) 设 $\sigma, \tau \in S_{n}$ 且 $a, b \in \underline{n}$ 。如果 $\sigma(a) = b$ ，则 $\tau \sigma \tau^{-1}$ 将 $\tau(a)$ 映射到 $\tau(b)$ 。

证明：(1) 需要证明对于所有 $b \in \underline{n}$ ，有

(a_{k}~\cdots~a_{1}) \circ (a_{1}~\cdots~a_{k}): b \mapsto b

且

(a_{1}~\cdots~a_{k}) \circ (a_{k}~\cdots~a_{1}): b \mapsto b

我们将做第一个组合，第二个类似。注意

如果 $b \notin \{a_{1}, \ldots, a_{k}\}$ ，则 $b$ 被 $\sigma$ 固定，因此被 $(a_{k}~\cdots~a_{1})$ 固定。因此 $(a_{k}~\cdots~a_{1}) \circ \sigma(b) = b$ 。 $\textcolor{red}{\checkmark}$
如果 $b \in \{a_{1}, \ldots, a_{k}\}$ ，则 $b = a_{i}$ ，其中 $i \in \{1, \ldots, k\}$ 。因此 $\sigma(b) = a_{i+1}$ （循环表示法的定义）。因此 $(a_{k}~\cdots~a_{1})$ 将 $\sigma(b)$ 映射回 $b$ 。 $\textcolor{red}{\checkmark}$

(2) 一般地，如果 $g_{1}, \ldots, g_{l} \in G$ ，

(g_{1} \cdots g_{l})^{-1} = g_{l}^{-1} \cdots g_{1}^{-1}。

因为

\begin{aligned} (g_{1} \cdots g_{l})(g_{l}^{-1} \cdots g_{1}^{-1}) &= g_{1} \cdots g_{l-1} \underbrace{g_{l} g_{l}^{-1}}_{\text{消掉}} g_{l-1}^{-1} \cdots g_{1}^{-1} \\ &= g_{1} \cdots \underbrace{g_{l-1} g_{l-1}^{-1}}_{\text{消掉}} \cdots g_{1}^{-1} \\ &\quad \vdots \\ &= g_{1} g_{1}^{-1} \\ &= 1_{G}。 \end{aligned}

因此

(\sigma_{1} \cdots \sigma_{l})^{-1} = \sigma_{l}^{-1} \cdots \sigma_{1}^{-1}

但不相交的循环是可交换的，所以

\sigma_{l}^{-1} \cdots \sigma_{1}^{-1} = \sigma_{1}^{-1} \cdots \sigma_{l}^{-1}。

(3)

\begin{aligned} \tau \sigma \tau^{-1}(\tau(a)) &= \tau \sigma \tau^{-1} \circ \tau(a) \\ &= \tau \sigma(a) \\ &= \tau(b) \end{aligned}

~\tag*{$\square$}

注共轭类似于基变换。如果 $v_{1}, \ldots, v_{k}$ 是 $\mathbb{R}^{k}$ 的一组基，那么存在一个可逆矩阵 $T$ ，其第 $i$ 列是 $v_{i}$ 。如果线性变换 $A$ 将 $\vec{a}$ 变为 $\vec{b}$ ，则 $T A T^{-1}$ 将 $T \vec{a}$ 变为 $T \vec{b}$ 。因此，可以将上述的 $\tau$ 看作是 $\underline{n}$ 的“新基”。

推论 5.4 设 $\sigma, \sigma' \in S_{n}$ 。如果存在 $\tau \in S_{n}$ 使得 $\sigma' = \tau \sigma \tau^{-1}$ ，那么我们可以从 $\sigma$ 的循环表示和 $\tau$ 构造 $\sigma'$ 的循环表示。

证明：如果 $\sigma$ 是一个循环，

\sigma = (a_{1}~\cdots~a_{l})

则

\tau \sigma \tau^{-1} = (\tau(a_{1})~\cdots~\tau(a_{l}))。

命题 (3) 告诉我们， $\tau(a_{i})$ 被 $\tau \sigma \tau^{-1}$ 映射到 $\tau(a_{i+1})$ 。它还告诉我们，如果 $\sigma(a) = a$ ，则 $\tau \sigma \tau^{-1}$ 固定 $\tau(a)$ ；因此， $\tau \sigma \tau^{-1}$ 是另一个循环，其非平凡轨道由 $\{\tau(a_{i})\}$ 给出。

如果 $\sigma$ 是不相交循环的乘积

\sigma = \sigma_{1} \cdots \sigma_{l}

则

\tau \sigma \tau^{-1} = (\tau \sigma_{1} \tau^{-1})(\tau \sigma_{2} \tau^{-1}) \cdots (\tau \sigma_{l} \tau^{-1})

因为共轭是一个群同态。因此，如果

\sigma = (a_{1}~\cdots~a_{k_{1}})(a_{k_{1}+1}~\cdots~a_{k_{1}+k_{2}}) \cdots (a_{k_{1}+\cdots+k_{l-1}+1}~\cdots~a_{k_{1}+\cdots+k_{l}})

是 $\sigma$ 的循环表示法，则

\tau \sigma \tau^{-1} = (\tau(a_{1})~\cdots~\tau(a_{k_{1}}))(\tau(a_{k_{1}+1})~\cdots~\tau(a_{k_{1}+k_{2}})) \cdots (\tau(a_{k_{1}+\cdots+k_{l-1}+1})~\cdots~\tau(a_{k_{1}+\cdots+k_{l}}))

是 $\tau \sigma \tau^{-1}$ 的循环表示法。

~\tag*{$\square$}

令 $\sigma \in S_{n}$ 。

将 $\sigma$ 写成

\sigma = \sigma_{1} \cdots \sigma_{k}

的不相交循环的乘积，并考虑

|\sigma_{i}|，\quad \forall i

（这些是与每个 $\sigma_{i}$ 相关的轨道的大小。）通过这种方式，我们得到了一组数字。由于我们可以重新排列 $\sigma_{i}$ ，最方便地将其视为一个无序的集合。

例 5.9 令

\sigma = (1~2~3)(6~9) \in S_{9}

注意我们为了简洁，不写 $(8)$ 。那么我们有与 $\sigma$ 相关的数字

3, 2, 3

定义 5.7 我们称这些数字 $\{a_{i}\}$ 为 $\sigma$ 的循环形状(cycle shape)。

例 5.10 令

\sigma' = (3~4~5)(8~7~9)(2~6)

则 $\sigma'$ 有数字 $3, 3, 2$ 与之关联。

除了顺序外，这与 $\sigma$ 相关的集合相同。我们说 $\sigma$ 和 $\sigma'$ 具有相同的循环形状。

命题 5.5 两个元素 $\sigma, \sigma' \in S_{n}$ 是共轭的（即存在 $\tau$ 使得 $\sigma = \tau \sigma' \tau^{-1}$ ），当且仅当它们具有相同的循环形状。

证明：设 $\sigma$ 和 $\sigma'$ 具有相同的循环形状。然后我们可以重新排列 $\sigma$ 和 $\sigma'$ 的任何循环表示，使得

\begin{aligned} \sigma &= \sigma_{1} \circ \cdots \circ \sigma_{k} \\ \sigma' &= \sigma_{1}' \circ \cdots \circ \sigma_{k}' \end{aligned}~\text{都是不相交循环的乘积。}

其中 $|\sigma_{i}| = |\sigma_{i}'|$ ，对于所有 $i$ 。

选择任意的 $i$ 和在 $\sigma_{i}$ 的循环表示法中出现的数字 $a$ ，

\sigma_{i} = (\cdots~a~\cdots)。

在 $\sigma_{i}'$ 中，选择任意数字 $a'$ ，

\sigma_{i}' = (\cdots~a'~\cdots)。

定义一个双射如下：

\begin{aligned} \tau: a_{i} &\mapsto b_{i} \\ \sigma^{j}(a_{i}) &\mapsto (\sigma')^{j}(b_{i}) \end{aligned}

那么

\begin{aligned} \tau \sigma \tau^{-1}(b) &= \tau \sigma \tau^{-1}((\sigma')^{j}(b_{i})) \\ &= \tau \sigma(\sigma^{j}(a_{i})) \\ &= \tau(\sigma^{j+1}(a_{i})) \\ &= (\sigma')^{j+1}(b_{i}) \\ &= \sigma'(b)。 \end{aligned}

即 $\tau \sigma \tau^{-1} = \sigma'$ 。反之亦然，由上面的推论可知。

~\tag*{$\square$}

例 5.11

\begin{aligned} (1~2~3)(6~9) &= \sigma \\ (4~5)(3~6~1) &= \sigma' \end{aligned} \in S_{9}

具有相同的循环形状。同样，

\begin{aligned} \sigma &= (1~2)(3~4)(5~6~7) \\ \sigma' &= (7~8)(5~9)(1~4~2) \end{aligned} \in S_{9}

注 $\sigma$ 的循环形状只是说明： $\sigma$ 的作用将 $\underline{n}$ 分成 $l$ 个轨道；第 $i$ 个轨道的大小为 $k_{i}$ 。如果 $\sigma'$ 也将 $\underline{n}$ 分成 $l$ 个轨道，并且我们可以将 $k_{i}'$ 与 $\sigma$ 的 $k_{i}$ 相匹配，那么 $\sigma$ 和 $\sigma'$ 具有相同的循环形状。

例 5.12 如何找到 $\tau$ 呢？

\begin{aligned} \sigma &= (1~2~3)(4~6)(7~8~5) \\ \sigma' &= (1~5~7)(9~3)(6~8~4) \end{aligned}

好吧，如果 $\tau \sigma \tau^{-1} = \sigma'$ ，我们知道在 $\sigma'$ 的循环表示中，循环

(b_{1}~\cdots~b_{k})

等于

(\tau(a_{1})~\cdots~\tau(a_{k}))

对于 $\sigma$ 的循环分解中的某个循环 $(a_{1}~\cdots~a_{k})$ 。这不是唯一的，但以下是你可以找到它的方法：选择一个循环和一个在其循环表示法中出现的数字。随意地，我们选择

4 \in (4~6)

在 $\sigma'$ 的循环表示法中，选择与 $(4~6)$ 长度相同的循环。在这种情况下，我们只能选择 $(9~3)$ （虽然一般情况下，我们可能有很多选择）。选择在该循环中出现的一个元素，比如 $9$ 。

所以写

然后我们来看循环 $\sigma_{i}$ 如何限制 $9$ 。在这种情况下，没有—— $9$ 是 $\sigma$ 的一个不动点。

所以选择 $\sigma^{\prime}$ 的任意一个不动点——在这里，我们唯一的选择是 $2$ 。

现在找到包含 $2$ 的循环 $\sigma_{i}$ 。在 $\sigma_{i}^{\prime}$ 中，找到对应的元素。在这种情况下，对应的是 $5$ 。

所以第四个：

$\textcircled{\small 5}$ 看到 $(4925)$ 是 $\tau$ 的一个循环后，选择任何一个尚未写出的元素。我们任意选择 $1$ 。

$\textcircled{\small 6}$ 同样地，我们选择 $3$ 。

由于我们从不书写长度为 $1$ 的循环。

§ 5.5 交错群

定义 5.8 交错群(alternating group) $A_{n}$ 定义为映射

\begin{aligned} S_{n} &\to GL_{n}(\mathbb{R}) \xrightarrow{\det} \mathbb{R}^{\times} \\ \sigma &\mapsto B_{\sigma} \end{aligned}

的核，其中

B_{\sigma}(e_{i}) = e_{\sigma(i)}

即：所有使得 $B_{\sigma}$ 的行列式为 $1$ 的 $\sigma$ 的集合。

命题 5.6 $A_{n}$ 是 $S_{n}$ 的子群，包含所有偶置换，即可以表示为偶数个换位（两个元素的交换）的置换。因此 $A_{n}$ 的阶为 $\dfrac{n!}{2}$ 。

命题 5.7 $A_{n}$ 是 $S_{n}$ 的正规子群。

有三种方法来证明这一点。

符号同态的核

证明：定义一个映射 $\mathrm{sgn}: S_{n} \to \{1, -1\}$ ，其中

如果 $\sigma$ 是偶置换， $\mathrm{sgn}(\sigma) = 1$ 。
如果 $\sigma$ 是奇置换， $\mathrm{sgn}(\sigma) = -1$ 。

这是一个群同态，因为

\mathrm{sgn}(\sigma \tau) = \mathrm{sgn}(\sigma) \cdot \mathrm{sgn}(\tau)。

我们称其为符号同态。

同态的核是被映射到陪域的单位元的元素集合。对于 $\mathrm{sgn}$ ，单位元是 $1$ 。因此， $\ker(\mathrm{sgn}) = A_{n}$ 。

群同态的核总是域群的正规子群。因此， $A_{n}$ 是 $S_{n}$ 的正规子群。

~\tag*{$\square$}

共轭保持置换的奇偶性

证明：对于任何 $\sigma, \tau \in S_{n}$ ，共轭保持置换的循环结构和奇偶性。如果 $\sigma$ 是偶置换，则其共轭 $\tau \sigma \tau^{-1}$ 也是偶置换。一个子群 $N$ 是正规子群，如果它在群的元素下共轭不变：

\tau N \tau^{-1} = N \quad \text{对于所有 } \tau \in S_{n}

由于偶置换的共轭仍是偶置换， $A_{n}$ 是 $S_{n}$ 的正规子群。

~\tag*{$\square$}

$A_{n}$ 在 $S_{n}$ 中的指数

证明： $A_{n}$ 在 $S_{n}$ 中的指数为：

[S_{n}: A_{n}] = \dfrac{|S_{n}|}{|A_{n}|} = \dfrac{n!}{n!/2} = 2。

由于在群中任何指数为 $2$ 的子群都是正规的， $A_{n}$ 是 $S_{n}$ 的正规子群。

~\tag*{$\square$}