周期

置换的一个简单例子可以通过以下方式获得：在 $1$ 和 $k$ 之间选择任意两个不同的整数，设为 $p$ 和 $q$ ，并写出 $当且时$ 如此定义的置换 $τ$ 记作 $(p, q)$ ；这种形式的每个置换都称为对换。如果 $τ$ 是一个对换，那么 $τ^{2} = ϵ$ 。

另一种构造例子的有用方法是在 $1$ 和 $k$ 之间选择 $p$ 个不同的整数，设为 $i_{1}, \dots, i_{p}$ ，并写出 $当时当时$ 如此定义的置换 $σ$ 记作 $(i_{1}, \dots, i_{p})$ 。如果 $p = 1$ ，那么 $σ = ϵ$ ；如果 $p = 2$ ，那么 $σ$ 是一个对换。对于满足 $1 < p \leq k$ 的任何 $p$ ，形如 $(i_{1}, \dots, i_{p})$ 的每个置换都称为 p-循环，或简称为循环； $2$ -循环恰好就是对换。警告：并不假定 $i_{1} < \dots < i_{p}$ 。例如，如果 $k = 5$ 且 $p = 3$ ，那么存在二十个不同的循环。还需注意，循环的表示方法不是唯一的；符号 $(1, 2, 3)$ 、 $(2, 3, 1)$ 和 $(3, 1, 2)$ 都表示同一个置换。如果所有 $i$ 中没有一个等于任何 $j$ ，则称两个循环 $(i_{1}, \dots, i_{p})$ 和 $(j_{1}, \dots, j_{q})$ 是不相交的。如果 $σ$ 和 $τ$ 是不相交的循环，那么 $σ τ = τ σ$ ，或者换句话说， $σ$ 和 $τ$ 对易。

定理 1. 每个置换都是两两不相交循环的乘积。

证明. 设 $π$ 是一个置换，且 $i$ 满足 $π (i) \neq i$ （暂且假定 $π \neq ϵ$ ），构造序列 $(i, π (i), π^{2} (i), \dots)$ 。由于在 $1$ 和 $k$ 之间只有有限个不同的整数，因此必然存在指数 $p$ 和 $q$ $(0 \leq p < q)$ 使得 $π^{p} (i) = π^{q} (i)$ 。 $π$ 的单射性质意味着 $π^{q - p} (i) = i$ ，或者，通过明显地改变记号，我们所证明的是，必然存在一个严格正的指数 $p$ 使得 $π^{p} (i) = i$ 。如果选择 $p$ 为具有该性质的最小指数，那么整数 $i, \dots, π^{p - 1} (i)$ 两两不同。（事实上，如果 $0 \leq q < r < p$ 且 $π^{r} (i) = π^{q} (i)$ ，那么 $π^{r - q} (i) = i$ ，这与 $p$ 的最小性矛盾。）由此可知 $(i, \dots, π^{p - 1} (i))$ 是一个 $p$ -循环。如果在 $1$ 和 $k$ 之间存在一个不同于 $i, \dots, π^{p - 1} (i)$ 中的每一个且不同于 $π (j)$ 的 $j$ ，我们用 $j$ 代替 $i$ ，重复引导我们得到该循环的步骤。只要在每一步之后我们仍能找到一个不被 $π$ 映射到自身的新的整数，我们就继续以这种方式构造循环；这样构造的不相交循环的乘积就是 $π$ 。对于 $π = ϵ$ 的情况，可以通过一个相当自然的约定来涵盖，即没有因子的乘积（“空乘积”）应被解释为恒等置换。 ◻

定理 2. 每个循环都是对换的乘积。

证明. 假设 $σ$ 是一个 $p$ -循环；为了记号上的简便，我们将在 $p = 5$ 的特殊情况下给出证明，该证明具有完全的普适性。证明本身只有一行： $(i_{1}, i_{2}, i_{3}, i_{4}, i_{5}) = (i_{1}, i_{5}) (i_{1}, i_{4}) (i_{1}, i_{3}) (i_{1}, i_{2}) .$ 补充几句解释可能会有所帮助。根据置换乘积的定义，上式右侧对 $1$ 和 $k$ 之间的每个整数的作用是从内向外，或者也许更直观地，从右向左。因此，例如，将 $(i_{1}, i_{5}) (i_{1}, i_{4}) (i_{1}, i_{3}) (i_{1}, i_{2})$ 作用于 $i_{3}$ 的结果计算如下： $(i_{1}, i_{2}) (i_{3}) = i_{3}$ ， $(i_{1}, i_{3}) (i_{3}) = i_{1}$ ， $(i_{1}, i_{4}) (i_{1}) = i_{4}$ ， $(i_{1}, i_{5}) (i_{4}) = i_{4}$ ，从而有 $(i_{1}, i_{5}) (i_{1}, i_{4}) (i_{1}, i_{3}) (i_{1}, i_{2}) (i_{3}) = i_{4}$ 。 ◻

为了便于引用，我们记录下前两个定理的以下直接推论。

定理 3. 每个置换都是对换的乘积。

注意，定理 2 和定理 3 中的对换并未声明是不相交的；通常它们不是不相交的。

练习

练习 1.

在 $𝒮_{k}$ 中有多少个置换？
在 $𝒮_{k}$ 中有多少个不同的 $p$ -循环（ $1 \leq p \leq k$ ）？

练习 2. 如果 $σ$ 和 $τ$ 是置换（在 $𝒮_{k}$ 中），那么 $(σ τ)^{- 1} = τ^{- 1} σ^{- 1}$ 。

练习 3.

如果 $σ$ 和 $τ$ 是置换（在 $𝒮_{k}$ 中），那么存在唯一的置换 $π$ 使得 $σ π = τ$ 。
如果 $π$ 、 $σ$ 和 $τ$ 是置换且满足 $π σ = π τ$ ，那么 $σ = τ$ 。

练习 4. 举出一个不是不相交对换乘积的置换的例子。

练习 5. 证明 $𝒮_{k}$ 中的每个置换都是形如 $(j, j + 1)$ 的对换的乘积，其中 $1 \leq j < k$ 。这种因式分解是唯一的吗？

练习 6. 循环的逆也是循环吗？

练习 7. 证明将置换表示为不相交循环的乘积的形式是唯一的，至多因子的顺序可能不同。

练习 8. 置换 $π$ 的阶是使得 $π^{p} = ϵ$ 的最小整数 $p$ （ $> 0$ ）。

每个置换都有一个阶。
$p$ -循环的阶是多少？
如果 $σ$ 是一个 $p$ -循环， $τ$ 是一个 $q$ -循环，且 $σ$ 和 $τ$ 是不相交的，那么 $σ τ$ 的阶是多少？
举一个例子说明不相交的假设在 (c) 中是必不可少的。
如果 $π$ 是一个 $p$ 阶置换，且满足 $π^{q} = ϵ$ ，那么 $q$ 能被 $p$ 整除。

练习 9. $𝒮_{k}$ （ $k > 1$ ）中的每个置换都可以写成乘积的形式，其中每个因子都是对换 $(1, 2), (1, 3), (1, 4), \dots, (1, k)$ 之一。

练习 10. 如果存在一个置换 $π$ 使得 $σ π = π τ$ ，则称两个置换 $σ$ 和 $τ$ 是共轭的。证明 $σ$ 和 $τ$ 共轭当且仅当它们具有相同的循环结构。（这意味着在将 $σ$ 表示为不相交循环的乘积时，对于每个 $p$ ， $p$ -循环的个数与 $τ$ 的对应个数相同。）