置换的奇偶性

维基百科,自由的百科全书
跳转至: 导航搜索

数学中,当 X 是一个至少有两个元素的有限集合时,X置换(即从 XX双射)可分为大小相同的两类:奇置换偶置换。如果 X 固定了任何一个全序X 的一个置换 \sigma 的奇偶性可以定义为 \sigma 中反向对个数的奇偶性。所谓反向对即 X 中二元组 x,y 使得 x<y\sigma(x)>\sigma(y)。这里 \sigma(x) 为置换 \sigma 中第 x 位的元素。

一个置换 \sigma符号sign 或 signature)记作 sgn(σ):如果 \sigma 是偶数则定义为 +1,如果 \sigma 是奇数则定义为 -1。符号定义了对称群 Sn交错特征。置换的符号另一个更一般的符号为列维-奇维塔符号\epsilon_\sigma),定义在 XX 的所有映射上,而在非双射映射上取值为 0。

置换的符号可以清晰地表达为

\sgn(\sigma)=(-1)^{N(\sigma)}

这里 N(\sigma)\sigma 中反向对的个数。或者,置换 \sigma 的符号也可通过对换分解定义为

\sgn(\sigma)=(-1)^m

这里 m 是分解中对换的个数。尽管这样一个分解不是惟一的,所有分解中对换个数的奇偶性是相同的,蕴含着置换的符号是良定义的。

例子[编辑]

考虑集合 {1,2,3,4,5} 的置换 σ,它将初始排列 12345 变为 34521。可以通过三个对换得到:首先交换1和3的位置,然后交换2和4,最后交换1和5。这证明了给定的置换 σ 是奇的。利用置换一文中的记号,我们可写成 \sigma=\begin{pmatrix}1&2&3&4&5\\
3&4&5&2&1\end{pmatrix} = \begin{pmatrix}1&3&5\end{pmatrix} \begin{pmatrix}2&4\end{pmatrix} = \begin{pmatrix}1&5\end{pmatrix} \begin{pmatrix}1&3\end{pmatrix} \begin{pmatrix}2&4\end{pmatrix}.

有无穷种方式将 σ 写成换位的复合,例如

\sigma=(2 3) (1 2) (2 4) (3 5) (4 5),\;

但是不可能将其写为偶数个换位的复合。

性质[编辑]

恒同置换是偶置换。一个偶置换可以由恒同置换通过偶数次两个元素互换(称为对换)得到,而一个奇置换可由奇数次对换得到。

由整数加法相应的法则马上得到下列性质:

  • 两个偶置换的复合是偶的
  • 两个奇置换的复合是偶的
  • 一个奇置换与偶置换的复合是奇的

由此得到

  • 任何偶置换的逆是偶的
  • 任何奇置换的逆是奇的

考虑集合 {1,...,n} 的所有置换之对称群 Sn,我们可总结为映射

\operatorname{sgn} : S_n \to \{-1,1\}

将每个置换映为其符号是一个群同态

进一步,我们见到偶置换组成 Sn 的一个子群。这就是 n 个字母上的交错群,记作 An。它是符号同态的。奇置换不能组成一个子群,因为两个奇置换的复合是偶置换,但它们是 An (在 Sn中)的一个陪集

如果 n>1,则 Sn 中偶置换与奇置换一样多;从而 An 包含 n!/2 个置换。(原因:如果 σ 是偶的,则 (12)σ 是奇的;如果 σ 是奇的,则 (12)σ 是偶的;这两个映射互逆。)

一个轮换是偶的当且仅当它的长度是奇的。这得自如下类似公式

(a b c d e) = (a e) (b e) (c e) (d e)

特别地,为了确定给定的置换是偶的还是奇的,将它写成不交轮换的乘积。这个置换是奇的当且仅当这个分解包含奇数个偶长度的轮换。

每个奇数置换必须是偶的;反之一般不成立。

两个定义的等价性[编辑]

证明一[编辑]

任意置换可以由一列对换产生:对第一个对换我们将置换的第一个元素放到它恰当的位置,第二个对换放第二个元素,等等。给定一个置换 σ,我们可用无数种方式将其写成对换之积。我们要证明所有这样一个分解,要么都有偶数个对换,要么有奇数个对换。

假设我们有两个这样的分解:

σ = T'1 T'2 ... T'k'
σ = Q'1 Q'2 ... Q'm'

我们要证明 k' 与 m' 要么都是偶的,要么都是奇的。

每个对换可以写成奇数个相邻元素的对换之乘积,例如

(2 5) = (2 3)(3 4)(4 5)(4 3)(3 2)

如果我们将上面的 T'1...T'k' 与 Q'1...Q'm' 中每个对换作这样的分解,我们得到一个新的分解:

σ = T1 T2 ... Tk
σ = Q1 Q2 ... Qm

这里所有 T1...Tk Q1...Qk 是相邻对换,k − k' 是偶数,m − m' 是偶数。

现在将 T1 的逆与 σ 复合。T1 是两个相邻数 (i, i + 1) 的对换,所以与 σ 相比,新置换 σ(i, i + 1) 恰好少一个(若 (i,i + 1) 是 σ 的反向对)或多一个反向对(若 (i,i + 1) 不是 σ 的反向对)。然后以相同的方法应用到 T2, T3, ... Tk 的逆,“消解”了置换 σ。最后我们得到了恒同置换,它的 N 是零,这意味着首先的 N(σ) 减去 k 是偶数。

对另一个置换 Q1...Qm 我们对同样的事情,从而首先的 N(σ) 减去 m 是偶数

这样 m − k 是偶数,这就是我们要证明的。

现在我们可以定义置换 σ 是偶的,如果 N(σ) 是偶数;是奇的,如果 N(σ) 是奇数。这与首先给出的定义相同,但现在清晰地看到每个置换不是偶的就是奇的。

证明二[编辑]

另一个证明利用多项式

P(x_1,\ldots,x_n)=\prod_{i<j} (x_i - x_j).\;

例如在 n = 3 的情形,我们有

P(x_1, x_2, x_3) = (x_1 - x_2)(x_2 - x_3)(x_1 - x_3).\;

现在对 {1,...,n} 的一个给定置换 σ,我们定义

\operatorname{sgn}(\sigma)=\frac{P(x_{\sigma(1)},\ldots,x_{\sigma(n)})}{P(x_1,\ldots,x_n)}.

因为多项式 P(x_{\sigma(1)},\dots,x_{\sigma(n)})P(x_1,\dots,x_n) 除了符号之外它们的因子相同,从而 sgn(σ) 不是 +1 就是 −1。从而如果 σ 与 τ 是两个置换,我们有

\operatorname{sgn}(\sigma\tau) = \frac{P(x_{\sigma(\tau(1))},\ldots,x_{\sigma(\tau(n))})}{P(x_1,\ldots,x_n)}
 = \frac{P(x_{\sigma(1)},\ldots,x_{\sigma(n)})}{P(x_1,\ldots,x_n)} \cdot \frac{P(x_{\sigma(\tau(1))},\ldots, x_{\sigma(\tau(n))})}{P(x_{\sigma(1)},\ldots,x_{\sigma(n)})}
 = \operatorname{sgn}(\sigma)\cdot\operatorname{sgn}(\tau)

有此定义之后,显然任何两个相邻元素的对换有符号 −1,这样我们事实上重新得到了早先定义的符号。

证明三[编辑]

第三个证明利用群 Sn 一个呈示,使用生成元为 \tau_1,\dots,\tau_{n-1},关系为

  • \tau_i^2 = 1  对所有 i
  • \tau_i\tau_{i+1}\tau_i = \tau_{i+1}\tau_i\tau_{i+1}   对所有 i < n − 1,
  • \tau_i\tau_j = \tau_j\tau_i   如果 |i − j| ≥ 2。

这里生成元 \tau_i 表示对换 (i, i + 1)。所有的关系将一个词的长度保持或改变 2。从一个偶数长词开始使用这些关系后总得到偶数长词,对奇数长词也类似。从而可以毫无歧义地称 Sn 中由偶数长词表示的元素是偶的,由奇数长词表示的元素是奇的。

相关条目[编辑]