查看“︁置换的奇偶性”︁的源代码

[[File:Symmetric group 4; permutation list.svg|thumb|[[File:Loupe light.svg|15px|link=https://web.archive.org/web/20150218175745/http://upload.wikimedia.org/wikipedia/commons/thumb/6/6d/Symmetric_group_4%3B_permutation_list_with_matrices.svg/1000px-Symmetric_group_4%3B_permutation_list_with_matrices.svg.png]] Permutations of 4 elements<br><br>Odd permutations have a green or orange background. The numbers in the right column are the [[Inversion (discrete mathematics)|inversion]] numbers {{OEIS|A034968}}, which have the same parity as the permutation.]]
在[[数学]]中，当''X''是一个至少有两个元素的[[有限集合]]时，''X''的[[置换]]（即从''X''到''X''的[[双射]]）可分为大小相同的两类：'''奇置换'''与'''偶置换'''。如果''X''固定了任何一个[[全序]]，''X''的一个'''置换<math>\sigma</math>的奇偶性'''可以定义为<math>\sigma</math>中反向对个数的奇偶性。所谓反向对即''X''中二元组<math>x,y</math>使得<math>x<y</math>且<math>\sigma(x)>\sigma(y)</math>。这里<math>\sigma(x)</math>为置换<math>\sigma</math>中第<math>x</math>位的元素。

一个置换<math>\sigma</math>的'''符号'''（{{lang|en|sign或signature}}）记作'''sgn(σ)'''：如果<math>\sigma</math>是偶数则定义为 +1，如果<math>\sigma</math>是奇数则定义为 -1。符号定义了[[对称群]]''S''<sub>''n''</sub>的'''交错[[特征 (数学)|特征]]'''。置换的符号另一个更一般的符号为[[列维-奇维塔符号]]（<math>\epsilon_\sigma</math>），定义在''X''到''X''的所有映射上，而在非双射映射上取值为0。

置换的符号可以清晰地表达为
:<math>\sgn(\sigma)=(-1)^{N(\sigma)}</math> 
这里<math>N(\sigma)</math>是<math>\sigma</math>中反向对的个数。或者，置换<math>\sigma</math>的符号也可通过[[对换]]分解定义为
:<math>\sgn(\sigma)=(-1)^m</math> 
这里''m''是分解中对换的个数。尽管这样一个分解不是惟一的，所有分解中对换个数的奇偶性是相同的，蕴含着置换的符号是[[良定义]]的。

== 例子 ==
考虑集合{1,2,3,4,5}的置换σ，它将初始排列12345变为34521。可以通过三个对换得到：首先交换1和3的位置，然后交换2和4，最后交换1和5。这证明了给定的置换σ是奇的。利用[[置换]]一文中的记号，我们可写成
<math>\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}2&4\end{pmatrix} \begin{pmatrix}1&3\end{pmatrix}</math>。

有无穷种方式将σ写成换位的[[函数复合|复合]]，例如

:<math>\sigma=(2 3) (1 2) (2 4) (3 5) (4 5),\;</math>

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

== 性质 ==
恒同置换是偶置换。一个偶置换可以由恒同置换通过[[偶数]]次两个元素互换（称为[[对换]]）得到，而一个奇置换可由奇数次对换得到。

由整数加法相应的法则马上得到下列性质：
* 两个偶置换的复合是偶的
* 两个奇置换的复合是偶的
* 一个奇置换与偶置换的复合是奇的
由此得到
* 任何偶置换的逆是偶的
* 任何奇置换的逆是奇的

考虑集合{1,...,''n''}的所有置换之[[对称群]]''S<sub>n</sub>''，我们可总结为映射
:<math>\operatorname{sgn} : S_n \to \{-1,1\}</math>
将每个置换映为其符号是一个[[群同态]]。

进一步，我们见到偶置换组成''S<sub>n</sub>''的一个子群。这就是''n''个字母上的[[交错群]]，记作''A<sub>n</sub>''。它是符号同态的[[核 (代数)|核]]。奇置换不能组成一个子群，因为两个奇置换的复合是偶置换，但它们是''A<sub>n</sub>''（在''S<sub>n</sub>''中）的一个[[陪集]]。

如果''n''>1，则''S<sub>n</sub>''中偶置换与奇置换一样多；从而''A<sub>n</sub>''包含[[阶乘|''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
这里所有''T''1...''Tk'' ''Q''1...''Qk''是相邻对换，''k'' − ''k''<nowiki>'</nowiki>是偶数，''m'' − ''m''<nowiki>'</nowiki>是偶数。

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

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

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

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

=== 证明二 ===

另一个证明利用[[多项式]]

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

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

:<math>P(x_1, x_2, x_3) = (x_1 - x_2)(x_2 - x_3)(x_1 - x_3).\;</math>

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

:<math>\operatorname{sgn}(\sigma)=\frac{P(x_{\sigma(1)},\ldots,x_{\sigma(n)})}{P(x_1,\ldots,x_n)}</math>。

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

:<math>\operatorname{sgn}(\sigma\tau) = \frac{P(x_{\sigma(\tau(1))},\ldots,x_{\sigma(\tau(n))})}{P(x_1,\ldots,x_n)}</math>

::::<math> = \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)})}</math>

::::<math> = \operatorname{sgn}(\sigma)\cdot\operatorname{sgn}(\tau)</math>

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

=== 证明三 ===

第三个证明利用群''S<sub>n</sub>''一个[[群的呈示|呈示]]，使用生成元为<math>\tau_1,\dots,\tau_{n-1}</math>，关系为 
* <math>\tau_i^2 = 1</math> 对所有''i''，
* <math>\tau_i\tau_{i+1}\tau_i = \tau_{i+1}\tau_i\tau_{i+1}</math>  对所有''i'' < ''n'' − 1，
* <math>\tau_i\tau_j = \tau_j\tau_i</math>  如果 |''i'' − ''j''| ≥ 2。

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

== 相关条目 ==
* [[魔方]]的每一步的转动都是偶置换，故盲拧有时会出现奇偶校验的情况。
* [[数字推盘游戏]]是一个经典应用，事实上它涉及一个[[群胚]]。
* [[佐洛塔列夫引理]]（{{lang|en|Zolotarev's lemma}}）

[[Category:群论]]
[[Category:置换]]
[[Category:奇偶性]]
[[Category:包含证明的条目]]

[[ru:Перестановка#Связанные определения]]