置換の符号

http://upload.wikimedia.org/wikipedia/commons/thumb/6/6d/Symmetric_group_4%3B_permutation_list_with_matrices.svg/1000px-Symmetric_group_4%3B_permutation_list_with_matrices.svg.png Permutations of 4 elements

Odd permutations have a green or orange background. The numbers in the right column are the inversion numbers オンライン整数列大辞典の数列 A034968, which have the same parity as the permutation.

数学において、少なくとも二元を含む有限集合 X の置換（X から X への全単射）は大きく二つのクラス（偶置換と奇置換）に分けられる。X の任意の全順序を固定して、X の置換 σ の偶奇性（パリティ; 対性）は σ の転倒数、すなわち X の元の対 (x, y) で x < y かつ σ(x) > σ(y) なるものの数、の偶奇性によって定義することができる。

置換 σ の符号 (sign) あるいは符号数 (signature) sgn(σ) は、σ が偶置換ならば +1, 奇置換ならば −1 を割り当てる。置換の符号函数 sgn は対称群 Sn の交代指標と呼ばれる群指標を定義する。置換の符号に対する別の記法として、より一般のレヴィ–チヴィタ記号によって与えられる εσ がある。これは X から X への全単射とは限らない任意の写像に対して定義され、全単射でない写像に対しては 0 を割り当てる。

置換の符号は inv(σ) を σ の転倒数とすれば

sgn(σ) = (−1)inv(σ)

と明示的に書くことができる。（転倒数は置換 σ を積として表すのに必要となる隣接互換の最小数とも一致する。）

あるいは、置換の符号を置換の互換の積への分解によって定義することもできる。すなわち、置換 σ の互換の積への分解に現れる互換の数を m とするとき、

sgn(σ) = (−1)m

とおくのである。置換のこのような互換の積への分解は一意ではないけれども、分解に現れる互換の総数の偶奇は置換ごとに一定しているので、この方法で置換の符号は矛盾なく定まる[1]。

さらに置換 σ ∈ Sn の符号を定義する他の方法としては差積 Δ(x1, …, xn) への自然な作用を介して

sgn ⁡ ( σ ) = ∏ i < j x σ ( i ) − x σ ( j ) ∏ i < j x i − x j {\displaystyle \operatorname {sgn}(\sigma )={\frac {\prod _{i<j}x_{\sigma (i)}-x_{\sigma (j)}}{\prod _{i<j}x_{i}-x_{j}}}}

によって定義することもできる。類似した符号の表示としては

sgn ⁡ ( σ ) = ∏ i < j σ ( i ) − σ ( j ) ∏ i < j i − j {\displaystyle \operatorname {sgn}(\sigma )={\frac {\prod _{i<j}\sigma (i)-\sigma (j)}{\prod _{i<j}i-j}}}

もある[2]。

（実際に置換 σ ∈ Sn の符号 sgn(σ) を得るには、σ が互いに素な q 個の巡回置換の積へ分解されているとき、 (−1)n − q を計算するのが効率的である[3]。ここで n − q は置換 σ を積として表すのに必要となる互換の最小数と一致する[4]。）

一般化

置換の偶奇性の概念はコクセター群に対するものへ一般化することができる。対称群の場合に、各置換を隣接互換（英語版）の積に書いたように、コクセター群の各元 v を（選択した）生成元の積に表したときに、その積に現れる元の個数の最小値によって長さ函数（英語版） l(v) を定義すれば、一般化された符号函数は v ↦ (−1)l(v) として与えられる。

関連項目

  • 15パズル：古典的応用（ただし実際上は亜群に関する話題）
  • Zolotarev's lemma
  • 行列式： det A = ∑ σ ∈ S n ( sgn ⁡ σ ∏ i = 1 n a i , σ ( i ) ) {\displaystyle \det A=\textstyle \sum \limits _{\sigma \in S_{n}}\left(\operatorname {sgn} \sigma \prod \limits _{i=1}^{n}a_{i,\sigma (i)}\right)}

注

  1. ^ Jacobson (2009), p.50.
  2. ^ Joyner, David『群論の味わい』共立出版、2010年、50頁。ISBN 978-4-320-01941-6。 
  3. ^ Nijenhuis, Albert; Wilf, Herbert S. (1978). Combinatorial Algorithms: For Computers and Calculators (Second ed.). Academic Press. p. 144. ISBN 0-12-519260-6 
  4. ^ Hazewinkel, Michiel, ed. (2001), “Permutation of a set”, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=Permutation_of_a_set 

参考文献

  • Weisstein, Eric W. "Even Permutation". mathworld.wolfram.com (英語).
  • Jacobson, Nathan (2009). Basic algebra. 1 (2nd ed.). Dover. ISBN 978-0-486-47189-1 
  • Rotman, J.J. (1995). An introduction to the theory of groups. Graduate texts in mathematics. Springer-Verlag. ISBN 978-0-387-94285-8 
  • Goodman, Frederick M.. Algebra: Abstract and Concrete. ISBN 978-0-9799142-0-1 
  • Meijer, Paul Herman Ernst; Bauer, Edmond (2004). Group theory: the application to quantum mechanics. Dover classics of science and mathematics. Dover Publications. ISBN 978-0-486-43798-9 

外部リンク

  • 『差積の意味と置換の符号が定義できることの証明』 - 高校数学の美しい物語
  • Hazewinkel, Michiel, ed. (2001), “Signature (permutation)”, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=Signature_(permutation)