置换的奇偶性

在數學中，當 _X_ 是一個至少有兩個元素的有限集合時，_X_ 的置換（即從 _X_ 到 _X_ 的雙射）可分為大小相同的兩類：**奇置換**與**偶置換**。如果 _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。符號定義了對稱群 _S_n 的**交錯特徵**。置換的符號另一個更一般的符號為列維 - 奇維塔符號（ $\epsilon _{\sigma }$ ），定義在 _X_ 到 _X_ 的所有映射上，而在非雙射映射上取值為 0。

置換的符號可以清晰地表達為

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

這裡 $N(\sigma )$ 是 $\sigma $ 中反向對的個數。或者，置換 $\sigma $ 的符號也可通過對換分解定義為

　
: $\operatorname {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}2&4\end{pmatrix}}{\begin{pmatrix}1&3\end{pmatrix}}$ 。

有無窮種方式將 σ 寫成換位的複合，例如

　
: $\sigma =(23)(12)(24)(35)(45),\;$

但是不可能將其寫為偶數個換位的複合。

## 性質

恆同置換是偶置換。一個偶置換可以由恆同置換通過偶數次兩個元素互換（稱為對換）得到，而一個奇置換可由奇數次對換得到。

由整數加法相應的法則馬上得到下列性質：

* 兩個偶置換的複合是偶的
* 兩個奇置換的複合是偶的
* 一個奇置換與偶置換的複合是奇的

由此得到

* 任何偶置換的逆是偶的
* 任何奇置換的逆是奇的

考慮集合 {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

這裡所有 _T_1..._Tk_ _Q_1..._Qk_ 是相鄰對換，_k_ − _k_' 是偶數，_m_ − _m_' 是偶數。

現在將 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_(σ) 是奇數。這與首先給出的定義相同，但現在清晰地看到每個置換不是偶的就是奇的。

### 證明二

另一個證明利用多項式

　
: $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_ 中由偶數長詞表示的元素是偶的，由奇數長詞表示的元素是奇的。

## 相關條目

* 魔方的每一步的轉動都是偶置換，故盲擰有時會出現奇偶校驗的情況。
* 數字推盤遊戲是一個經典應用，事實上它涉及一個群胚。
* 佐洛塔列夫引理（Zolotarev's lemma）