一、对称群 $S_n$ 的回顾
1.1 基本定义
设 $n$ 为正整数，对称群 $S_n$ 定义为：
\[S_n = \{\sigma : \{1, 2, \ldots, n\} \to \{1, 2, \ldots, n\} \mid \sigma \text{ 是双射}\}\]$S_n$ 在映射的复合运算下构成一个群。群运算即映射的复合，每个元素（双射）都有逆映射，逆元即为逆映射。
1.2 置换的表示
$S_n$ 中的元素 $\sigma$ 可以用两行排列的形式表示：
\[\sigma = \begin{pmatrix} 1 & 2 & \cdots & n \\ \sigma(1) & \sigma(2) & \cdots & \sigma(n) \end{pmatrix}\]上面一行从小到大排列，下面一行写出各元素的像。
二、轮换
2.1 轮换的定义
设 $2 \le r \le n$，$a_0, a_1, \ldots, a_{r-1}$ 是 ${1, 2, \ldots, n}$ 中 $r$ 个互不相同的元素。称 $S_n$ 中如下映射为一个长度为 $r$ 的轮换，记为 $(a_0\ a_1\ \cdots\ a_{r-1})$：
\(\sigma(a_i) = a_{i+1},\quad i = 0, 1, \ldots, r-2\) \(\sigma(a_{r-1}) = a_0\) \(\sigma(j) = j,\quad \forall j \notin \{a_0, a_1, \ldots, a_{r-1}\}\)
即 $\sigma$ 将 $a_0 \mapsto a_1 \mapsto a_2 \mapsto \cdots \mapsto a_{r-1} \mapsto a_0$ 循环映射，而不在这些元素中的数保持不动。
长度为 1 的轮换 $(a)$ 就是恒等映射（将所有元素映到自身）。长度为 2 的轮换 $(a\ b)$ 称为对换（transposition）。
2.2 轮换的阶等于其长度
性质 1：长度为 $r$ 的轮换 $(a_0\ a_1\ \cdots\ a_{r-1})$ 的阶等于 $r$。
验证思路：对于轮换 $\sigma = (a_0\ a_1\ \cdots\ a_{r-1})$，其 $s$ 次幂作用于 $a_j$ 的结果为：
\[\sigma^s(a_j) = a_{(j+s) \bmod r}\]- 当 $s = r$ 时，$(j + r) \bmod r = j$，故 $\sigma^r(a_j) = a_j$，即 $\sigma^r = e$（恒等映射）。
- 当 $1 \le s < r$ 时，取 $j = 0$，有 $\sigma^s(a_0) = a_s \ne a_0$，故 $\sigma^s \ne e$。
| 因此 $ | \sigma | = r$。 |
具体例子：
- 对换 $(a\ b)$：$\sigma(a) = b,\ \sigma(b) = a$，故 $\sigma^2(a) = \sigma(b) = a$，阶为 2。
- 三轮换 $(1\ 2\ 3)$：$\sigma(1) = 2,\ \sigma^2(1) = 3,\ \sigma^3(1) = 1$，阶为 3。
由拉格朗日定理，$S_n$ 中任意元素 $\sigma$ 的阶整除 $ S_n = n!$，但 $n!$ 的估计过于粗糙。实际上元素的阶的上界远小于 $n!$。
2.3 不相交轮换分解
定义（不相交轮换）：设 $\tau = (a_0\ a_1\ \cdots\ a_{r-1})$ 和 $\eta = (b_0\ b_1\ \cdots\ b_{q-1})$ 是 $S_n$ 中两个轮换，若
\[\{a_0, a_1, \ldots, a_{r-1}\} \cap \{b_0, b_1, \ldots, b_{q-1}\} = \varnothing\]则称 $\tau$ 与 $\eta$ 不相交。
性质 2（不相交轮换可交换）：若 $\tau$ 与 $\eta$ 不相交，则 $\tau \circ \eta = \eta \circ \tau$。
证明思路：设 $\tau = (1\ 2\ 3)$，$\eta = (4\ 5\ 6)$，验证 $\tau \circ \eta = \eta \circ \tau$：
- 对 $i \in {1, 2, 3}$：$\eta(i) = i$（因为 $i \notin {4,5,6}$），故 $\tau(\eta(i)) = \tau(i)$。另一方面，$\tau(i) \in {1,2,3}$，故 $\eta(\tau(i)) = \tau(i)$。两边相等。
- 对 $j \in {4, 5, 6}$：同理，$\tau(j) = j$，故 $\eta(\tau(j)) = \eta(j)$；而 $\eta(j) \in {4,5,6}$，故 $\tau(\eta(j)) = \eta(j)$。两边相等。
- 对 ${1,\ldots,6}$ 之外的元素：$\tau$ 和 $\eta$ 均保持不动。
一般情形类似：不相交轮换各自只变动自己的元素集合，对对方的元素集合保持不动，因此复合可交换。
注意：$S_n$（$n \ge 3$）不是交换群。但不相交的轮换之间是可以交换的。相交的轮换一般不可交换，例如 $(1\ 2) \circ (2\ 3) = (1\ 2\ 3)$，而 $(2\ 3) \circ (1\ 2) = (1\ 3\ 2)$，两者不等。
性质 3（不相交轮换分解定理）：$S_n$ 中任意元素 $\sigma$ 都可以写成若干个两两不相交的轮换的乘积（复合），且不计轮换的排列顺序时，这种分解是唯一的。
这类似于整数的素因数分解的唯一性。
2.4 不相交轮换分解的具体算法
方法：从 1 出发，依次追踪 $\sigma$ 的映射轨迹，直到回到起点，形成第一个轮换；再从未出现过的最小数出发，重复此过程，直到所有元素都被覆盖。
例 1：设 $\sigma \in S_7$，
\[\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 3 & 7 & 1 & 4 & 5 & 6 \end{pmatrix}\]从 1 出发：$1 \to 2 \to 3 \to 7 \to 6 \to 5 \to 4 \to 1$（回到起点）。
所有 7 个元素恰好在同一个轮换中，故
\[\sigma = (1\ 2\ 3\ 7\ 6\ 5\ 4)\]这是一个长度为 7 的轮换。
例 2：设 $\sigma \in S_{12}$，
\[\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 4 & 8 & 6 & 7 & 5 & 10 & 12 & 9 & 2 & 11 & 3 & 1 \end{pmatrix}\]- 从 1 出发：$1 \to 4 \to 7 \to 12 \to 1$，得轮换 $(1\ 4\ 7\ 12)$（长度 4）
- 从最小未出现的数 2 出发：$2 \to 8 \to 9 \to 2$，得轮换 $(2\ 8\ 9)$（长度 3）
- 从最小未出现的数 3 出发：$3 \to 6 \to 10 \to 11 \to 3$，得轮换 $(3\ 6\ 10\ 11)$（长度 4）
- 剩余数 5：$5 \to 5$，得轮换 $(5)$（长度 1）
因此
\[\sigma = (1\ 4\ 7\ 12)(2\ 8\ 9)(3\ 6\ 10\ 11)(5)\]长度为 1 的轮换 $(5)$ 表示 5 映到自身，写上更加规范，但有时也可省略。
2.5 不相交轮换分解与元素的阶
性质 4：设 $\sigma = \tau_1 \tau_2 \cdots \tau_s$，其中 $\tau_1, \tau_2, \ldots, \tau_s$ 是两两不相交的轮换，长度分别为 $m_1, m_2, \ldots, m_s$，则
\[|\sigma| = \operatorname{lcm}(m_1, m_2, \ldots, m_s)\]原因：由于不相交的轮换可交换，
\[\sigma^k = \tau_1^k \tau_2^k \cdots \tau_s^k\]$\sigma^k = e$ 当且仅当每个 $\tau_i^k = e$，即 $m_i \mid k$ 对所有 $i$ 成立，即 $k$ 是 $m_1, \ldots, m_s$ 的公倍数。最小的这样的 $k$ 就是最小公倍数。
不相交轮换可交换的性质在此至关重要：若 $ab = ba$，则 $(ab)^k = a^k b^k$。这是课后习题中需要验证的内容。
例 2 续：$\sigma = (1\ 4\ 7\ 12)(2\ 8\ 9)(3\ 6\ 10\ 11)(5)$，各轮换长度为 $4, 3, 4, 1$，故
\[|\sigma| = \operatorname{lcm}(4, 3, 4, 1) = 12\]2.6 元素阶的上界估计
设 $\sigma \in S_n$ 分解为长度为 $m_1, m_2, \ldots, m_s$ 的不相交轮换之积，则
\[|\sigma| = \operatorname{lcm}(m_1, \ldots, m_s) \le m_1 m_2 \cdots m_s \le e^{n/e}\]| 其中 $e$ 为自然对数的底。右边的上界只与 $n$ 有关，与 $\sigma$ 的选取无关。注意 $e^{n/e}$ 远小于 $n!$（甚至不到 $n$ 的三次方量级），因此比拉格朗日定理给出的 $ | \sigma | \mid n!$ 要精细得多。 |
最后一步估计的关键在于：在 $m_1 + m_2 + \cdots + m_s \le n$ 的约束下，乘积 $m_1 m_2 \cdots m_s$ 的最大值可用均值不等式给出。具体推导留作思考。
三、对换（transposition）
3.1 定义
对换是长度为 2 的轮换 $(i\ j)$（$i \ne j$），即将 $i$ 和 $j$ 互换，其他元素保持不动。
3.2 轮换可以分解为对换的乘积
任意长度为 $r$ 的轮换 $(a_0\ a_1\ \cdots\ a_{r-1})$ 可以写成 $r - 1$ 个对换的乘积：
\[(a_0\ a_1\ \cdots\ a_{r-1}) = (a_0\ a_1)(a_1\ a_2) \cdots (a_{r-2}\ a_{r-1})\]具体例子：
- $(1\ 2\ 3) = (1\ 2)(2\ 3)$
- $(1\ 2\ 3\ 4) = (1\ 2)(2\ 3)(3\ 4)$
- $(1\ 2\ 3\ 4\ 5) = (1\ 2)(2\ 3)(3\ 4)(4\ 5)$
验证 $(1\ 2)(2\ 3) = (1\ 2\ 3)$：（映射复合从右到左计算）
- $1$：$(2\ 3)$ 不动，$(1\ 2)$ 将 $1 \mapsto 2$，故 $1 \mapsto 2$
- $2$：$(2\ 3)$ 将 $2 \mapsto 3$，$(1\ 2)$ 不动 $3$，故 $2 \mapsto 3$
- $3$：$(2\ 3)$ 将 $3 \mapsto 2$，$(1\ 2)$ 将 $2 \mapsto 1$，故 $3 \mapsto 1$
结果为 $(1\ 2\ 3)$。
映射复合始终从右到左计算：先算右边的映射，再算左边的。包括二元关系的复合，一律如此。
3.3 任意置换可分解为对换的乘积
定理：$S_n$ 中任意元素 $\sigma$ 都可以写成若干个对换的乘积。
证明：$\sigma$ 先分解为两两不相交的轮换的乘积，再将每个轮换分解为对换的乘积。
与轮换分解不同的是，对换分解不要求两两不相交（事实上对换分解中的对换往往是相交的），分解方式也不唯一。
3.4 对换个数的奇偶性是唯一的
定理：设 $\sigma \in S_n$，若
\[\sigma = \eta_1 \eta_2 \cdots \eta_p = \mu_1 \mu_2 \cdots \mu_q\]其中 $\eta_i, \mu_j$ 均为对换，则 $p$ 与 $q$ 同奇偶。
证明（利用置换矩阵与行列式）：
回顾置换矩阵的定义。对 $\sigma \in S_n$，定义 $n \times n$ 矩阵 $T(\sigma)$，其 $(i, j)$ 位置的元素为：
\[T(\sigma)_{ij} = \begin{cases} 1, & \text{若 } i = \sigma(j) \\ 0, & \text{若 } i \ne \sigma(j) \end{cases}\]$T(\sigma)$ 是一个置换矩阵（每行每列恰有一个 1），且映射 $T: S_n \to GL_n(\mathbb{R})$ 是群同态：
\[T(\sigma \circ \tau) = T(\sigma) \cdot T(\tau)\]由 $\sigma = \eta_1 \eta_2 \cdots \eta_p$，取行列式：
\[\det T(\sigma) = \det T(\eta_1) \cdot \det T(\eta_2) \cdots \det T(\eta_p)\]关键事实：每个对换 $(i\ j)$ 对应的置换矩阵 $T((i\ j))$ 是将单位矩阵的第 $i$ 行与第 $j$ 行互换所得，故
\[\det T((i\ j)) = -1\]（互换矩阵的两行，行列式变号。）因此
\[\det T(\sigma) = (-1)^p\]同理，若 $\sigma = \mu_1 \mu_2 \cdots \mu_q$，则 $\det T(\sigma) = (-1)^q$。
由 $(-1)^p = (-1)^q$ 得 $p \equiv q \pmod{2}$，即 $p$ 与 $q$ 同奇偶。$\blacksquare$
虽然对换分解的具体方式可能不同（例如 10 个对换的乘积也可以等于 8 个对换的乘积），但绝不可能出现一种分解用奇数个对换、另一种用偶数个对换的情况。
四、奇置换、偶置换与交错群
4.1 奇偶置换的定义
由于对换个数的奇偶性是唯一确定的，可以对 $S_n$ 中的元素作如下分类：
- 若 $\sigma$ 可以写成奇数个对换的乘积，称 $\sigma$ 为奇置换。
- 若 $\sigma$ 可以写成偶数个对换的乘积，称 $\sigma$ 为偶置换。
恒等映射 $e$ 是偶置换（可视为 0 个对换的乘积，0 为偶数）。
4.2 交错群 $A_n$
定义：$S_n$ 中全体偶置换构成的集合记为 $A_n$，称为 $n$ 次交错群（alternating group）：
\[A_n = \{\sigma \in S_n \mid \sigma \text{ 是偶置换}\}\]$A_n$ 是 $S_n$ 的子群：
- 封闭性：两个偶置换的复合仍是偶置换（偶数 + 偶数 = 偶数）。
- 逆元：偶置换的逆仍是偶置换（因为每个对换的逆就是它自身，所以 $\sigma^{-1}$ 的对换个数与 $\sigma$ 相同）。
- 单位元：恒等映射是偶置换。
4.3 交错群的阶
| 定理：当 $n \ge 2$ 时，$ | A_n | = \dfrac{n!}{2}$。 |
当 $n = 1$ 时，$A_1 = S_1 = {e}$。
证明：当 $n \ge 2$ 时，取对换 $(1\ 2) \in S_n$，由于 $(1\ 2) \notin A_n$（它是奇置换），$S_n$ 可以分解为 $A_n$ 与左陪集 $(1\ 2) A_n$ 的不交并：
\[S_n = A_n \sqcup (1\ 2) A_n\]这是因为：
- 若 $\sigma$ 是偶置换，则 $\sigma \in A_n$。
- 若 $\sigma$ 是奇置换，则 $(1\ 2) \circ \sigma$ 是偶置换（奇数 + 1 = 偶数），即 $(1\ 2)\sigma \in A_n$，从而 $\sigma \in (1\ 2) A_n$。
| 由陪集分解的性质，$ | A_n | = | (1\ 2) A_n | $，故 $ | S_n | = 2 | A_n | $，即 |
当 $n = 2$ 时，$A_2 = {e}$，只有一个元素。当 $n = 3$ 时，$ A_3 = 3$，$A_3$ 是一个 3 阶循环群。一般研究 $A_n$ 的非平凡性质时，关注 $n \ge 4$ 的情况。
五、补充：逆序对与行列式的形式化定义
5.1 逆序对
设 $\sigma \in S_n$，称有序对 $(i, j)$（$1 \le i < j \le n$）为 $\sigma$ 的一个逆序对（inversion），若
\[\sigma(i) > \sigma(j)\]即”小的位置映到了大的值，大的位置映到了小的值”。用 $N(\sigma)$ 记 $\sigma$ 的逆序对个数。
例：$\sigma = \begin{pmatrix} 1 & 2 & 3 \ 1 & 3 & 2 \end{pmatrix}$（即对换 $(2\ 3)$），唯一的逆序对是 $(2, 3)$（因为 $2 < 3$ 但 $\sigma(2) = 3 > 2 = \sigma(3)$），故 $N(\sigma) = 1$。
5.2 逆序对数的奇偶性
命题：对任意 $\sigma \in S_n$ 和任意对换 $\eta$，$N(\sigma \circ \eta)$ 与 $N(\sigma)$ 的奇偶性不同。
此命题的验证纯粹是组合计数，不涉及线性代数。由此可以不依赖行列式理论，独立地证明对换分解中对换个数的奇偶性唯一。
5.3 行列式的形式化定义
利用 $S_n$ 和逆序对，$n$ 阶方阵 $A = (a_{ij})$ 的行列式可以定义为：
\[\det A = \sum_{\sigma \in S_n} (-1)^{N(\sigma)} \cdot a_{1,\sigma(1)} \cdot a_{2,\sigma(2)} \cdots a_{n,\sigma(n)}\]求和遍历 $S_n$ 中所有 $n!$ 个置换，每一项取矩阵中每行一个元素（列的选取由 $\sigma$ 决定，保证不同行取不同列），前面的符号由逆序对数的奇偶性决定。
从此定义出发，可以推导行列式的各种性质（如交换两行变号、按某行展开等），而不需要递归定义。
此定义在理论上非常重要，但不适合用于计算（因为共有 $n!$ 项）。实际计算行列式通常使用高斯消元等方法。
六、核心要点总结
- 轮换分解：给定置换的两行表示，将其写成两两不相交轮换的乘积。
- 求元素的阶：先做轮换分解，再求各轮换长度的最小公倍数。
- 对换分解：将轮换进一步分解为对换的乘积。
- 奇偶置换判定：对换分解中对换个数的奇偶性确定了置换的奇偶性。
-
交错群 $A_n$：$ A_n = n!/2$（$n \ge 2$）。