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