置換的奇偶性
在數學中,當X是一個至少有兩個元素的有限集合時,X的置換(即從X到X的雙射)可分為大小相同的兩類:奇置換與偶置換。如果X固定了任何一個全序,X的一個置換的奇偶性可以定義為中反向對個數的奇偶性。所謂反向對即X中二元組使得且。這裏為置換中第位的元素。
一個置換的符號(sign或signature)記作sgn(σ):如果是偶數則定義為 +1,如果是奇數則定義為 -1。符號定義了對稱群Sn的交錯特徵。置換的符號另一個更一般的符號為列維-奇維塔符號(),定義在X到X的所有映射上,而在非雙射映射上取值為0。
置換的符號可以清晰地表達為
這裏是中反向對的個數。或者,置換的符號也可通過對換分解定義為
這裏m是分解中對換的個數。儘管這樣一個分解不是惟一的,所有分解中對換個數的奇偶性是相同的,蘊含着置換的符號是良定義的。
例子
考慮集合{1,2,3,4,5}的置換σ,它將初始排列12345變為34521。可以通過三個對換得到:首先交換1和3的位置,然後交換2和4,最後交換1和5。這證明了給定的置換σ是奇的。利用置換一文中的記號,我們可寫成 。
有無窮種方式將σ寫成換位的複合,例如
但是不可能將其寫為偶數個換位的複合。
性質
恆同置換是偶置換。一個偶置換可以由恆同置換通過偶數次兩個元素互換(稱為對換)得到,而一個奇置換可由奇數次對換得到。
由整數加法相應的法則馬上得到下列性質:
- 兩個偶置換的複合是偶的
- 兩個奇置換的複合是偶的
- 一個奇置換與偶置換的複合是奇的
由此得到
- 任何偶置換的逆是偶的
- 任何奇置換的逆是奇的
考慮集合{1,...,n}的所有置換之對稱群Sn,我們可總結為映射
將每個置換映為其符號是一個群同態。
進一步,我們見到偶置換組成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(σ)是奇數。這與首先給出的定義相同,但現在清晰地看到每個置換不是偶的就是奇的。
證明二
另一個證明利用多項式
例如在n = 3的情形,我們有
現在對{1,...,n}的一個給定置換σ,我們定義
- 。
因為多項式 與 除了符號之外它們的因子相同,從而sgn(σ)不是 +1就是−1。從而如果σ與τ是兩個置換,我們有
有此定義之後,顯然任何兩個相鄰元素的對換有符號−1,這樣我們事實上重新得到了早先定義的符號。
證明三
第三個證明利用群Sn一個呈示,使用生成元為 ,關係為
- 對所有i,
- 對所有i < n − 1,
- 如果 |i − j| ≥ 2。
這裏生成元 表示對換 (i, i + 1)。所有的關係將一個詞的長度保持或改變2。從一個偶數長詞開始使用這些關係後總得到偶數長詞,對奇數長詞也類似。從而可以毫無歧義地稱Sn中由偶數長詞表示的元素是偶的,由奇數長詞表示的元素是奇的。