置換的奇偶性

在數學中，當X是一個至少有兩個元素的有限集合時，X的置換（即從X到X的雙射）可分為大小相同的兩類：奇置換與偶置換。如果X固定了任何一個全序，X的一個置換${\displaystyle \sigma }$的奇偶性可以定義為${\displaystyle \sigma }$中反向對個數的奇偶性。所謂反向對即X中二元組${\displaystyle x,y}$使得${\displaystyle x<y}$且${\displaystyle \sigma (x)>\sigma (y)}$。這裡${\displaystyle \sigma (x)}$為置換${\displaystyle \sigma }$中第${\displaystyle x}$位的元素。

Permutations of 4 elements

Odd permutations have a green or orange background. The numbers in the right column are the inversion numbers （OEIS數列A034968）, which have the same parity as the permutation.

一個置換${\displaystyle \sigma }$的符號（sign或signature）記作sgn(σ)：如果${\displaystyle \sigma }$是偶數則定義為 +1，如果${\displaystyle \sigma }$是奇數則定義為 -1。符號定義了對稱群S_n的交錯特徵。置換的符號另一個更一般的符號為列維-奇維塔符號（${\displaystyle \epsilon _{\sigma }}$），定義在X到X的所有映射上，而在非雙射映射上取值為0。

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

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

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

${\displaystyle \operatorname {sgn}(\sigma )=(-1)^{m}}$

這裡m是分解中對換的個數。儘管這樣一個分解不是惟一的，所有分解中對換個數的奇偶性是相同的，蘊含著置換的符號是良定義的。

例子

考慮集合{1,2,3,4,5}的置換σ，它將初始排列12345變為34521。可以通過三個對換得到：首先交換1和3的位置，然後交換2和4，最後交換1和5。這證明了給定的置換σ是奇的。利用置換一文中的記號，我們可寫成 ${\displaystyle \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}}}$。

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

${\displaystyle \sigma =(23)(12)(24)(35)(45),\;}$

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

性質

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

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

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

由此得到

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

考慮集合{1,...,n}的所有置換之對稱群S_n，我們可總結為映射

${\displaystyle \operatorname {sgn} :S_{n}\to \{-1,1\}}$

將每個置換映為其符號是一個群同態。

進一步，我們見到偶置換組成S_n的一個子群。這就是n個字母上的交錯群，記作A_n。它是符號同態的核。奇置換不能組成一個子群，因為兩個奇置換的複合是偶置換，但它們是A_n（在S_n中）的一個陪集。

如果n>1，則S_n中偶置換與奇置換一樣多；從而A_n包含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(σ)是奇數。這與首先給出的定義相同，但現在清晰地看到每個置換不是偶的就是奇的。

證明二

另一個證明利用多項式

${\displaystyle P(x_{1},\ldots ,x_{n})=\prod _{i<j}(x_{i}-x_{j}).\;}$

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

${\displaystyle P(x_{1},x_{2},x_{3})=(x_{1}-x_{2})(x_{2}-x_{3})(x_{1}-x_{3}).\;}$

現在對{1,...,n}的一個給定置換σ，我們定義

${\displaystyle \operatorname {sgn} (\sigma )={\frac {P(x_{\sigma (1)},\ldots ,x_{\sigma (n)})}{P(x_{1},\ldots ,x_{n})}}}$。

因為多項式${\displaystyle P(x_{\sigma (1)},\dots ,x_{\sigma (n)})}$與${\displaystyle P(x_{1},\dots ,x_{n})}$除了符號之外它們的因子相同，從而sgn(σ)不是 +1就是−1。從而如果σ與τ是兩個置換，我們有

${\displaystyle \operatorname {sgn} (\sigma \tau )={\frac {P(x_{\sigma (\tau (1))},\ldots ,x_{\sigma (\tau (n))})}{P(x_{1},\ldots ,x_{n})}}}$

${\displaystyle ={\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)})}}}$

${\displaystyle =\operatorname {sgn} (\sigma )\cdot \operatorname {sgn} (\tau )}$

有此定義之後，顯然任何兩個相鄰元素的對換有符號−1，這樣我們事實上重新得到了早先定義的符號。

證明三

第三個證明利用群S_n一個呈示，使用生成元為${\displaystyle \tau _{1},\dots ,\tau _{n-1}}$，關係為

• ${\displaystyle \tau _{i}^{2}=1}$ 對所有i，
• ${\displaystyle \tau _{i}\tau _{i+1}\tau _{i}=\tau _{i+1}\tau _{i}\tau _{i+1}}$  對所有i < n − 1，
• ${\displaystyle \tau _{i}\tau _{j}=\tau _{j}\tau _{i}}$  如果 |i − j| ≥ 2。

這裡生成元${\displaystyle \tau _{i}}$表示對換 (i, i + 1)。所有的關係將一個詞的長度保持或改變2。從一個偶數長詞開始使用這些關係後總得到偶數長詞，對奇數長詞也類似。從而可以毫無歧義地稱S_n中由偶數長詞表示的元素是偶的，由奇數長詞表示的元素是奇的。

相關條目

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