順列の偶奇性

数学では、X が少なくとも 2 つの要素を持つ有限集合である場合、 Xの順列(つまり、XからXへの全単射関数) は、偶順列と奇順列という、同じサイズの 2 つのクラスに分類されます。Xの任意の全順序が固定されている場合、順列のパリティ(奇数性または偶数性) は、${\displaystyle \sigma }$Xのσの反転の数の偶奇性、つまり、 x < yかつσ ( x ) > σ ( y )となるXの要素x、 yのペアの数の偶奇性として定義できます。 

置換σの符号、署名、または符号はsgn( σ ) と表記され、σが偶数の場合は +1、σが奇数の場合は− 1と定義されます。署名は、対称群S _nの交代性を定義します。置換の符号の別の表記法は、より一般的なレヴィ・チヴィタ記号( ε _σ ) で与えられ、これはXからXへのすべての写像に対して定義され、非全単射写像の場合はゼロの値をとります。 

順列の符号は、明示的に次のように表すことができます。

sgn( σ ) = (−1) ^{N ( σ )}

ここで、N ( σ )はσにおける反転の数である。 

あるいは、置換σの符号は、それを転置の積に分解することによって次のように定義できる。 

sgn( σ ) = (−1) ^m

ここで、mは分解における転置の数である。このような分解は一意ではないが、すべての分解における転置の数の偶奇性は同じであり、これは置換の符号が明確に定義されていることを意味する。^{[ 1 ]}

集合{1, 2, 3, 4, 5}の順列σを次のように定義する。${\displaystyle \sigma (1)=3,}$${\displaystyle \sigma (2)=4,}$${\displaystyle \sigma (3)=5,}$${\displaystyle \sigma (4)=2,}$そして${\displaystyle \sigma (5)=1.}$一行表記 では、この順列は 34521 と表記されます。これは、恒等順列12345 から 3 つの転置によって得られます。まず、2 と 4 を交換し、次に 3 と 5 を交換し、最後に 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&3\end{pmatrix}}{\begin{pmatrix}3&5\end{pmatrix}}{\begin{pmatrix}2&4\end{pmatrix}}.}$

σを転置の合成として表す方法は他にもたくさんあります。例えば

σ = (1 5)(3 4)(2 4)(1 2)(2 3)、

しかし、それを偶数回の転置の積として表すことは不可能である。

恒等置換は偶数置換である。^{[ 1 ]}偶数置換は、2 つの要素の偶数個(偶数個のみ) の交換 (転置と呼ばれる) の合成として得られるが、奇数置換は (のみ) 奇数個の転置によって得られる。

以下の規則は、整数の加算に関する対応する規則から直接導き出されます。^{[ 1 ]}

• 2つの偶順列の合成は偶数です
• 2つの奇順列の合成は偶数である
• 奇順列と偶順列の合成は奇数である

これらから次のことが導かれる。

• すべての偶順列の逆順列は偶数である
• すべての奇順列の逆順列は奇数である

集合 {1, ..., n } のすべての順列の対称群S _{n を}考慮すると、写像は次の結論を導き出すことができる。

sgn: S _n → {−1, 1}

すべての順列にその符号を割り当てるのは群準同型写像である。^{[ 2 ]}

さらに、偶数順列はS _nの部分群を形成することがわかります。^{[ 1 ]}これはn文字の交代群であり、A _nと表記されます。^{[ 3 ]}これは準同型 sgn の核です。 ^{[ 4 ]}奇数順列は、2 つの奇数順列の合成が偶数であるため、部分群を形成することはできませんが、 A _{n (S n}内) の剰余類を形成します。^{[ 5 ]}

n > 1 の場合、S _nには偶数順列と奇数順列が同数存在します。 ^{[ 3 ]}その結果、A _nにはn ! /2 個の順列が含まれます。（理由は、σが偶数の場合(1 2) σは奇数であり、σが奇数の場合(1 2) σは偶数であり、これら 2 つの写像は互いに逆であるためです。）^{[ 3 ]}

サイクルが偶数であるのは、その長さが奇数である場合に限る。これは次のような公式から導かれる。

${\displaystyle (a\ b\ c\ d\ e)=(d\ e)(c\ e)(b\ e)(a\ e){\text{ または }}(a\ b)(b\ c)(c\ d)(d\ e).}$

実際には、与えられた順列が偶数順列か奇数順列かを判定するために、その順列を互いに素なサイクルの積として表します。順列が奇数順列であるのは、この因数分解において偶数長のサイクルが奇数個含まれる場合に限ります。

与えられた順列が偶数か奇数かを判定するもう一つの方法は、対応する順列行列を作成し、その行列式を計算することです。行列式の値は、順列の偶奇性と同じです。

奇数位の順列はすべて偶数位でなければならない。A ₄の順列(1 2)(3 4)は、一般に逆が成り立たないことを示している。

このセクションでは、置換σの偶奇性を2つの同等な方法で定義できることを証明します。

• σにおける反転の数の偶奇性（任意の順序付けの下で）として。または
• σを分解できる転置の数の偶奇性として（どのように分解するかは我々の選択による）。

証明3

3つ目のアプローチでは、群 S _nを生成元τ ₁、 ...、τ _{n − 1}と関係式を用いて表現します。

• ${\displaystyle \tau _{i}^{2}=1}$ 私が
• ${\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}}$ もし${\displaystyle |i-j|\geq 2.}$

[ここでジェネレーター${\displaystyle \tau _{i}}$は転置( i , i + 1)を表します。] すべての関係は、単語の長さを同じに保つか、2 だけ変更します。したがって、偶数長の単語から始めると、関係を使用した後には必ず偶数長の単語になり、奇数長の単語についても同様です。したがって、偶数長の単語で表される S _nの要素を「偶数」、奇数長の単語で表される要素を「奇数」と呼ぶことは曖昧さがありません。

証明5

転置の2つの要素に挟まれた要素を考えてみましょう。それぞれの要素は、2つの転置要素の真上、真下、または中間に位置します。

完全に上または完全に下にある要素は、転置を適用したときに反転カウントに寄与しません。中間の要素は寄与します${\displaystyle \pm 2}$。

転置自体が供給する${\displaystyle \pm 1}$反転があり、その他すべては 0 (mod 2) の反転を供給し、転置は反転の数の偶奇性を変更します。

順列のパリティ${\displaystyle n}$ポイントもそのサイクル構造にエンコードされています。

σ = ( i ₁ i ₂ ... i _{r +1} )( j ₁ j ₂ ... j _{s +1} )...( ℓ ₁ ℓ ₂ ... ℓ _{u +1 ) を、} σを互いに素なサイクルに分解した唯一の例とする。これらのサイクルは可換であるため、任意の順序で合成できる。k + 1個の点を含むサイクル( a b c ... x y z )は、 k個の転置 (2-サイクル)を合成することで常に得られる。

${\displaystyle (a\ b\ c\dots x\ y\ z)=(a\ b)(b\ c)\dots (x\ y)(y\ z),}$

そこで、k をサイクルのサイズと呼び、この定義の下では転置はサイズ 1 のサイクルであることに注意してください。m 個の互いに素なサイクルへの分解から、σをk 1 + _k 2 + _... + k _m個の転置に分解することができます。ここで、k _iはi番目のサイクルのサイズです。数N ( σ ) = k ₁ + k ₂ + ... + k _mはσの判別式と呼ばれ、次のように計算することもできます。

${\displaystyle n{\text{ minus the number of disjoint cycles in the decomposition of }}\sigma }$

σの固定点を1サイクルとして含めるように注意すれば、

置換σの後に転置 ( a b ) が適用されると仮定します。aとb がσの異なるサイクルにある場合、

${\displaystyle (a\ b)(a\ c_{1}\ c_{2}\dots c_{r})(b\ d_{1}\ d_{2}\dots d_{s})=(a\ c_{1}\ c_{2}\dots c_{r}\ b\ d_{1}\ d_{2}\dots d_{s})}$、

aとbがσの同じサイクルにある場合、

${\displaystyle (a\ b)(ac_{1}c_{2}\dots c_{r}\ b\ d_{1}\ d_{2}\dots d_{s})=(a\ c_{1}\ c_{2}\dots c_{r})(b\ d_{1}\ d_{2}\dots d_{s})}$。

いずれの場合も、 N (( a b ) σ ) = N ( σ ) ± 1 であることがわかるので、 N (( a b ) σ )のパリティはN ( σ )のパリティとは異なることになります。

σ = t ₁ t ₂ ... t _rは、置換σをr個の転置を適用することによって転置に任意に分解したものである。${\displaystyle t_{1}}$t ₂の後、... t _rの後、恒等式 ( Nがゼロ)の後、 N ( σ ) とr が同じパリティを持つことに注目します。σ のパリティを N ( σ ) のパリティとして定義すると、偶数長の分解を持つ置換は偶数置換であり、奇数長の分解を 1 つ持つ置換は奇数置換となります。

備考

• 上記の議論を注意深く検討すると、r ≥ N ( σ )であることがわかり、σを合計サイズがrになるサイクルに分解すると、 r個の転置の合成として表現できるため、 N ( σ )は、すべてのサイクルが転置である場合を含めて、σの分解におけるサイクルのサイズの合計の最小値となります。
• この証明は、 σが作用する点の集合に（おそらく恣意的な）順序を導入するものではない。

パリティはコクセター群に一般化できます。長さ関数ℓ( v )を定義します。これは生成子の選択（対称群の場合は隣接する転置）に依存し、関数v↦ ( −1 ) ^{ℓ( v )は}一般化された符号写像を与えます。

• 15パズルは古典的な応用例です
• ゾロタレフの補題

• ワイスタイン、エリック・W. 「偶数順列」。マスワールド。
• ジェイコブソン、ネイサン（2009）。基礎代数学。第 1巻（第2 版）。ドーバー出版。ISBN 978-0-486-47189-1。
• Rotman, JJ (1995).群論入門. 数学大学院教科書. Springer-Verlag. ISBN 978-0-387-94285-8。
• グッドマン、フレデリック・M.代数学：抽象と具体。ISBN 978-0-9799142-0-1。
• Meijer, Paul Herman Ernst; Bauer, Edmond (2004).群論：量子力学への応用. Dover Classics of Science and Mathematical Series. Dover Publications. ISBN 978-0-486-43798-9。