7.5.zy1, 证明任一置换都可以唯一地写为两两不相交轮换之积.
证明: 这里主要证明唯一性. 若置换 $\sigma$ 是单位元恒等变换, 则显然可得结论, 虽然这里 $\sigma=(1)=(2)=\cdots=(n)$, 但其实 $(1),(2)\dots$ 这些 1 轮换都是相同的映射. 现在考虑置换不是恒等变换情况, 则存在 $i_1, \sigma(i_1) \ne i_1$, 则易证无论将 $\sigma$ 分解为哪种不相交轮换之积, 这些不相交轮换中必存在轮换 $(i_1, \sigma(i_1), \sigma^{k_1 - 1}(i_1))$. 现在考虑 $N_1 = n \setminus {i_1, \sigma(i_1), \sigma^{k_1 - 1}(i_1)}$, 若 $\sigma$ 在 $N_1$ 上均是恒等变换, 则证明结束. 若不是, 则 $\exists i_2 \in N_1, \sigma(i_2)\ne i_2$, 即轮换分解中必存在轮换 $(i_2, \sigma(i_2), \sigma^{k_2 - 1}(i_2))$, …
定义 7.9, 这里我好奇 $\sum_{i=1}^n i\lambda_i = n$ 的解 $(\lambda_1, \cdots, \lambda_n)$ 都对应着一个置换么?
解: 是的, 可以按照解 $(\lambda_1, \cdots, \lambda_n)$ 的指示得到一组不相交轮换乘积:
- 首先从 $N={1, \cdots, n}$ 中取前 $\lambda_1$ 个元素, 得到一组轮换 $(1),(2), \cdots, (\lambda_1)$. 并将这些元素从 N 中移除.
-
从 N 中任意元素再取前 $\lambda_1 * 2$ 个元素, 又可得到一组轮换 $(\lambda_1+1, \lambda_1+2), (\lambda_1+3, \lambda_1+4), \cdots$
- 则这些轮换乘积便对应着一个置换, 且该置换的型恰是 $(\lambda_1, \cdots, \lambda_n)$.
7.11.zy1, 命题 7.11 描述的共轭关系是群上的一个等价关系.
证明: 对于群 G 中任意元素 a, 可知 $a = 1a1^{-1}$, 这里 1 是 G 中的单位元, 即 $a \sim a$. 对于任意 $a, b, \exists T \in G, a = TbT^{-1}$, 则 $b = T^{-1}aT$, 即 b 与 a 也共轭. 对于任意 $a, b, c, \exists R, S, a = RbR^{-1}, b = ScS^{-1}$, 则 $a = RSc(RS)^{-1}$, 即 a 与 c 也共轭.
P.S. 从证明过程可以看到任意群都有共轭这一等价关系.
7.12, 略作补充
-
k 轮换可以写为 k - 1 个对换的乘积. 这里分解就不是唯一的了. 以 (abc) 为例其可以写为 (ac)(ab); (abc)=(bca) 也可以写为 (ba)(bc).
-
恒等变换可以写作 (12)(12).
奇置换, 偶置换; 原文这块有点不太严谨, 以定理 7.15 为例, 在 $\varepsilon(\sigma) = (-1)^i$ 中, 这里 $\sigma$ 是 i 个对换的乘积, 但原文尚未证明过任一置换分解为对换之后, 对换的个数是固定的; 甚至这一命题都是不成立的; 以 (123) 为例, 其可以分解为 (13)(12), 也可以分解为 (12)(12)(13)(12). 即对于一个置换 $\sigma$, 其可能会有多个 i 与之对应, 自然 $\varepsilon(\sigma)$ 就不算是一个定义良好的映射了. 所以这块我重新梳理一下.
逆序对, 即定义 7.18; 对于一个特定置换 $\sigma$, 若 $i < j, \sigma(i) > \sigma(j)$ 成立, 则 (i, j) 被称作是一个逆序对. 置换中逆序的个数被称为逆序数(交错数) $n(\sigma) = \sum_{i=1}^n|{j | \sigma(j) \gt i, j \lt \sigma^{-1}(i)}|$; 从下面置换 $\sigma$ 的两行式表达中可以清晰地看到 $\sigma(j) \gt i, j \lt \sigma^{-1}(i)$ 条件成立时 $(j, \sigma^{-1}(i))$ 确实一个逆序对, 以此易见原文公式 7.5 也是成立.
| 1 | 2 | … | j | … | $\sigma^{-1}(i)$ | … | n |
|---|---|---|---|---|---|---|---|
| $\sigma(1)$ | $\sigma(2)$ | … | $\sigma(j)$ | … | i | … | $\sigma(n)$ |
7.15.zy1, 置换 $\sigma$ 与其逆置换 $\sigma^{-1}$ 总是具有相同的逆序对.
证明: 易证 (i, j) 是 $\sigma$ 中逆序对当且仅当 $(\sigma(j), \sigma(i))$ 是 $\sigma^{-1}$ 中逆序对.
P.S. 老觉得如下两个集合有点相似.
\[\begin{align} n(\sigma) &= \sum_{i=1}^n\|\{j \| \sigma(j) \gt i, j \lt \sigma^{-1}(i)\}\| \\ n(\sigma^{-1}) &= \sum_{i=1}^n\|\{j \| \sigma^{-1}(j) \gt i, j \lt \sigma(i)\}\| \end{align}\]7.15.zy2, 令 f 为置换; $\sigma$ 为相邻对换, 即形如 (i, i+1) 这种相邻的对换; 则 $f\sigma$ 或 $\sigma f$ 中的交错数总是比 f 多一个或者少一个.
证明: 如下是 1 到 n 中所有的有序对, 在置换 f 中, 这些有序对有的是逆的, 有的不是.
...(1, i)(1, i+1)(1, i+2)...(1,n)
...(2, i)(2, i+1)(2, i+2)...(2,n)
...
... (i, i+1)(i, i+2)...(i,n)
... (i+1, i+2)...(i+1,n)
...
... (n-1,n)
$f\sigma$ 可能会使某些有序对从逆变为不逆, 使某些不逆的变为逆序. 这里我们分类研究下.
- 若有序对 (k, l) 不涉及到 (i, i+1), 即 k, l 均既不为 i 也不为 i + 1. 则易见这些有序对逆序属性保持不变.
- 对于形如 (k, i), (k, i+1) 有序对. 此时 (k, i) 在置换 $f\sigma$ 下的逆序属性等同于 (k, i+1) 在置换 f 下的逆序属性. (k, i+1) 在置换 $f\sigma$ 下的逆序属性等同于 (k, i) 在置换 f 下的逆序属性.
- (i, i+1), 逆序属性发生变化.
- 对于形如 (i, l), (i+1, l) 有序对, 同分类 2, (i, l) 在置换 $f\sigma$ 下的逆序属性等同于 (i+1, l) 在置换 f 下的逆序属性.
所以易证 $f\sigma$ 中的交错数总是比 f 多一个或者少一个. 之后对于 $\sigma f$, 由 7.15.zy1 可知 $n(\sigma f) = n(f^{-1}\sigma^{-1})$. 这里 $n(f^{-1}\sigma^{-1}) = n(f^{-1}) \pm 1 = n(f) \pm 1$.
7.15.zy3, 每一个对换 $(i, i+d)$ 总可以写为 $2d-1$ 个相邻对换乘积.
证明: 当 d = 1 时显然成立, 即对于对换 (k, l), 当 l - k = 1, 其能分解出 2(k-l)-1 个相邻对换乘积. 现在假设当 l - k = d 时能分解出 2d - 1 个相邻对换乘积; 考虑 l - k = d + 1 情况, 即 (i, i+d+1); 考虑到 (i, i+d+1) = (i, i+1)(i+1, i+d+1)(i, i+1), 且已知 (i+1, i+d+1) 可以分解为 2d - 1 个相邻对换乘积. 所以 (i, i+d+1) 可以分解为 2d - 1 + 2 个相邻对换乘积.
P.S. 这种分解可能不是唯一的, 但我没细思考, 后面不依赖这个分解唯一性.
7.15.zy4, 令 f 为一置换, 如上可知可以将 f 分解为 k 个对换; 这里分解并不唯一. 但 k 的奇偶性是唯一确定的.
证明: 假设 f 可以分解为 $f = T_1’ T_2’ \cdots T_{k’}’ = Q_1’ Q_2’ \cdots Q_{m’}’$, 这里 $T’, Q’$ 均为对换, 我们要证明 $k’, m’$ 具有相同的奇偶性. 我们对这里的 $T’, Q’$ 都作 7.15.zy3 那种分解, $f = T_1 T_2 \cdots T_k = Q_1 Q_2 \cdots Q_m$, T, Q 都是相邻对换, 易见 $T^{-1}=T, Q^{-1}=Q$. 即 $f T_k^{-1} T_{k-1}^{-1} \cdots T_2^{-1} T_1^{-1} = fQ_m^{-1} \cdots Q_1^{-1}=1$. 即:
\[\begin{align} n(f) \underbrace{\pm 1 \pm 1 \pm \cdots \pm 1}_{k} = 0 \\ n(f) \underbrace{\pm 1 \pm \cdots \pm 1}_{m} = 0 \end{align}\]设在 k 中有 $k_1$ 个 $+1$, $k_2$ 个 $-1$, 即 $n(f) + k_1 - k_2 = 0$, 同理 m 也可以分为 $m_1, m_2$:
\[\begin{align} k_1 + k_2 &= k \\ k_2 - k_1 &= n(f) \\ m_1 + m_2 &= m \\ m_2 - m_1 &= n(f) \\ k_2 - m_1 - (k_1 - m_2) &= 2n(f) \\ k - m &= k_2 - m_1 + k_1 - m_2 = 2n(f) + 2(k_1 - m_2) \\ k &\equiv m \mod 2 \end{align}\]接下来证 $k’ \equiv k \mod 2, k = \sum_{i=1}^{k’}(2d_i - 1) = (2\sum_{i=1}^{k’}d_i) - k’$, 这里假设 $T_i’ = (t_i, t_i + d_i)$. 由 $k + k’$ 为偶数易证 $k - k’$ 也是偶数. 即 $k’ \equiv k \mod 2$. 同理 $m’ \equiv m \mod 2$. 所以 $k’ \equiv m’ \mod 2$.
P.S. 写到这里才发现该定理证明依赖 7.15.zy3 中一个对换不能分解为偶数个相邻对换乘积.
证明: 假设 7.15.zy3 中一个对换 f 可以分为偶数个相邻对换乘积 $f = 1 g_1 \cdots g_k$, 这里 k 为偶数. 则由 7.15.zy2 可知:
\[0 \underbrace{\pm 1 \pm 1 \pm \cdots \pm 1}_{k} = n(f) = 1\]易证此时 k 一定为奇数!
定理 7.15, 略作补充.
-
经过上面探讨可以知晓, 虽然这里 $\sigma$ 是 i 个对换的乘积, i 取值并不唯一, 但 i 奇偶性是唯一的. 所以 $\varepsilon(\sigma) = (-1)^i$ 对于任一置换将得到唯一的值, 所以 $\varepsilon$ 是一个定义良好的映射.
-
对所有对换有 $\tau \Delta = -\Delta$, 这个结论可以仿照 7.15.zy2 证明过程一样处理.
-
唯一性证明, 假设存在 $\varepsilon_1, \varepsilon_2$, 对所有对换 $\tau$ 有 $\varepsilon_1(\tau) = -1, \varepsilon_2(\tau) = -1$; 则由于所有置换都可以写为对换乘积且奇偶性确定. 即此时易证 $\forall \sigma, \varepsilon_1(\sigma) = \varepsilon_2(\sigma)$, 即 $\varepsilon_1, \varepsilon_2$ 相同.
-
$f = gh$, 这里 g 为奇置换, h 为偶置换; 则 f 也为奇置换.
证明: $\varepsilon(f) = \varepsilon(g)\varepsilon(h) = -1$, 假设 f 为偶置换, 则 $\varepsilon(f) = 1$, 矛盾. 所以 f 一定是奇置换.
命题 7.17, 略作补充
证明: 由 7.12 可知, k 轮换可以写作 k - 1 个对换乘积, 虽然这里分解并不是唯一的. 由 7.15.zy4 可知, k 为奇数时, k 轮换为偶置换; k 为偶数时, k 轮换为奇置换.
若某一置换 f 由 $\lambda$ 个 k 轮换组成, 则易证 f 奇偶性取决于 $\lambda(k-1)$ 的奇偶性; 可以分别令 $\lambda, k$ 以此为奇偶, 奇奇, 偶偶, 偶奇来分类证明. 若某一置换 g 由 k 轮换, l 轮换乘积组成, 易证 g 奇偶性等同于 (k-1) + (l-1) 奇偶性. 据此可证得结论.
