抽象代数习题(8) – 有限集的置换

《抽象代数》第八章讲了有限集合上的置换、轮换、对换的表示法,置换到轮换的分解,置换的奇偶性。


B.1 为下列情况计算 α⁻¹, α², α³, α⁴, α⁵:

  1. α = (123)
  2. α = (1234)
  3. α = (123456)

  1. α⁻¹=(132), α²=(132), α³=ε, α⁴=(123), α⁵=(132)
  2. α⁻¹=(1432), α²=(13)(24), α³=(1432), α⁴=ε, α⁵=(1234)
  3. α⁻¹=(165432), α²=(135)(246), α³=(14)(25)(36), α⁴=(153)(264), α⁵=(165432)

B.2 描述轮换 \(\alpha = (a_1a_2\cdots a_s)\) 的所有不同的幂。共有几个?密切注意它和整数模 \(s\) 的加法群的关系。

\[\alpha^k = \begin{pmatrix} a_1 & a_2 & \cdots & a_{s-k} & a_{s-k+1} & \cdots & a_s \\ a_{k+1} & a_{k+2} & \cdots & a_s & a_1 & \cdots & a_k \\ \end{pmatrix}\]

可见共有 \(s\) 个不同的幂: \(\alpha^0, \alpha^1, \ldots, \alpha^{s-1}\)。


B.3 找出 \(\alpha\) 的逆并证明 \(\alpha^{-1}=\alpha^{s-1}\)。

证明

而根据前一问的结论可知

\[\alpha^{-1} = \begin{pmatrix} a_1 & a_2 & \cdots & a_s \\ a_s & a_1 & \cdots & a_{s-1} \\ \end{pmatrix} = \alpha^{s-1}\]

证明完毕。


B.4 求证: \(\alpha^2\) 是轮换,当且仅当 \(s\) 是奇数。

证明

首先证明 \(s\) 是奇数 ⟹ \(\alpha^2\) 是轮换。 假定 \(s\) 是奇数, 则 \[\alpha^2 = (a_1\,a_3\cdots a_s\,a_2\,a_4\cdots a_{s-1})\] 是轮换。

其次证明 \(s\) 不是奇数 ⟹ \(\alpha^2\) 不是轮换。 \(s\) 不是奇数即是偶数,而 \[\alpha^2 = (a_1\,a_3\cdots a_{s-1})(a_2\,a_4\cdots a_s)\] 不是轮换(因为置换分解为轮换是唯一的)。

综上所述, \(\alpha^2\) 是轮换当且仅当 \(s\) 是奇数。


B.5 如果 \(s\) 是奇数,证明 \(\alpha\) 是某个长度为 \(s\) 的轮换的平方。

证明 因为 \(\alpha^s = \epsilon\),所以 \(\alpha = \alpha^{s+1} = \bigl(\alpha^r\bigr)^2\),这里 \(r={s+1\over2}\) 是整数。

\[\alpha^r = \begin{pmatrix} a_1 & a_2 & \cdots & a_s \\ a_r & a_{r+1} & \cdots & a_{r-1} \\ \end{pmatrix}\]

下面证明这是一个轮换。因为 \(\alpha^r(a_i) = a_{i+r-1}\),所以从 \(a_1\) 开始可以得到一个轮换 \[\beta = (a_1\,a_r\cdots a_{[(k-1)(r-1)\bmod s]+1}\cdots)\] 其中 \(1\le k \le s\)。 下面考虑这个轮换的长度。令第 \(k\) 项等于第 \(1\) 项,得同余方程 \[(k-1)(r-1) \equiv 0 \pmod s\]

根据初等数论知识,\(\gcd(r-1,s) = \gcd(r-1, 2r-1) = 1\),故可约去 \((r-1)\)。解得 \(k\equiv 1 \pmod s\)。 所以,唯一满足要求的值为 \(k=1\)。由此可知, \(\beta\) 能够遍历全部 \(s\) 个元素。这意味着 \(\alpha^r\) 是轮换。

综上所述,\(\alpha\) 是轮换 \(a^{s+1\over2}\) 的平方。


B.7 如果 \(s=kt\) 是 \(k\) 的倍数,证明 \(\alpha^k\) 是 \(k\) 个长度为 \(t\) 的轮换的复合。

证明 把 \(a_1\) 到 \(a_s\) 排在 \(t\times k\) 矩阵中:

\begin{matrix} a_1 & a_2 & \cdots & a_k \\ a_{k+1} & a_{k+2} & \cdots & a_{2k} \\ \vdots & \vdots & \ddots & \vdots \\ a_{(t-1)k+1} & a_{(t-1)k+2} & \cdots & a_{kt} \\ \end{matrix}

选择任意一列,\(\alpha^k\) 会轮换这一列的所有元素。由矩阵大小可知 \(\alpha^k\) 是 \(k\) 个长度为 \(t\) 的复合。


C.2 求证:

  1. 两个偶置换的复合是偶置换;
  2. 两个奇置换的复合是偶置换;
  3. 一个偶置换和一个奇置换的复合是奇置换。

证明

考虑置换中对换的个数。两个置换复合,对换个数相加。 根据奇偶数的运算性质:

  1. 两个偶数的和是偶数;
  2. 两个奇数的和是偶数;
  3. 一个偶数和一个奇数的和是奇数。

即可得证。


C.3 求证:

  1. 奇数长度的轮换是偶置换;
  2. 偶数长度的轮换是奇置换。

证明

根据等式 \[(a_1\,a_2\cdots a_l) = (a_la_{l-1})(a_la_{l-2})\cdots(a_la_1)\] 可知,长度为 \(l\) 的轮换可以分解为 \((l-1)\) 个对换。根据奇偶置换的定义即可得证。


分享