置換の符号とは｜互換への分解・転倒数・交代群と行列式への現れ方

$2$ つの番号だけを入れかえる置換を互換といいます。どの置換も互換の積に書けるものの、書き方は一通りではない。

それでも必要な互換の個数の偶奇は置換ごとに決まっていて、これを符号と呼びます。偶なら $+1$、奇なら $-1$。

互換への分解

巡回置換は互換の積にほどける。

$$(a_1{a}_2\cdots a_k)=(a_1{a}_k)(a_1{a}_{k-1})\cdots (a_1{a}_2)$$

右から順に掛けていくと、$a_1$ が $a_2$ へ、$a_2$ が $a_3$ へと送られていく。長さ $k$ の巡回に要る互換は $k-1$ 個です。

どの置換も交わらない巡回の積なので、全体としても互換の積に書ける。

例：巡回置換を互換に分ける

$(1234)$ を分けてみます。

$$(1234)=(14)(13)(12)$$

互換は 3 個で、長さ 4 の巡回だから $4-1=3$ に合う。別の分け方もあります。

$$(1234)=(12)(23)(34)$$

こちらも 3 個。式の形はまるで違うのに、個数は変わっていない。

分け方は一通りではない

個数そのものが変わる分け方もある。

$$(12)=(12)(34)(34)$$

右の 2 つが打ち消し合うので、どちらも同じ置換。個数は 1 個と 3 個で違いますが、どちらも奇数です。

偶奇だけは動かない。ここを示すのが次の節になります。

転倒数による定義

$\sigma$ の行き先を $\sigma (1),\sigma (2),\dots ,\sigma (n)$ と一列に並べます。$i<j$ なのに $\sigma (i)>\sigma (j)$ となる組を転倒といい、その個数を転倒数という。

転倒数を $N(\sigma )$ と書くと、符号は次のように定まります。

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

$N(\sigma )$ は $\sigma$ そのものから決まる量なので、分解の仕方が入りこむ余地がない。

図にすると、上下を結んだ線の交差の本数がそのまま転倒数になる。

例：転倒数を数える

$S_3$ の 6 個を並べると、転倒数と符号の対応が見えます。恒等置換は $0$、互換は $1$ か $3$、3 次巡回は $2$。

偶置換が 3 個、奇置換が 3 個で、ちょうど半分に割れる。

互換を掛けると偶奇が変わる

まず隣どうしの互換を考えます。並びの中で隣り合う $2$ つを入れかえると、その組だけが転倒になったり転倒でなくなったりする。

ほかの組の大小関係はいっさい変わらないので、転倒数はちょうど $1$ だけ増減する。

一般の互換 $(ij)$ も、隣どうしの互換だけで作れる。$i$ と $j$ のあいだにある番号を $k$ 個とすると、$2k+1$ 回でできる。

奇数回なので、どの互換を掛けても転倒数の偶奇はかならず変わる。互換を $m$ 個掛けて $\sigma$ を作れば、$N(\sigma )$ の偶奇は $m$ の偶奇に一致します。

分解の仕方によらず $m$ の偶奇が決まる理由が、ここにある。

積の形の定義

転倒数を使わない書き方もあります。

$$\mathrm{sgn}(\sigma )=\prod _{i<j}\frac{\sigma (j)-\sigma (i)}{j-i}$$

分子と分母に現れる数は、符号を除けば同じ集まり。だから比は $+1$ か $-1$ になり、$\sigma (i)>\sigma (j)$ の組の個数だけ $-1$ が掛かる。

つまり転倒数による定義と同じものです。

符号は準同型になる

符号は $S_n$ から $\{+1,-1\}$ への準同型です。

$$\mathrm{sgn}(\sigma \tau )=\mathrm{sgn}(\sigma )\mathrm{sgn}(\tau )$$

$\sigma$ を $m$ 個、$\tau$ を $m^{\prime }$ 個の互換で書けば、$\sigma \tau$ は $m+m^{\prime }$ 個で書ける。指数の足し算がそのまま積になる、という仕組み。

$n\ge 2$ なら互換が存在するので、この準同型は全射になる。

巡回型から符号を読む

長さ $k$ の巡回の符号は $(-1{)}^{k-1}$ です。互換は奇、3 次巡回は偶、4 次巡回は奇、5 次巡回は偶と交互になる。

固定点まで数えた巡回の個数を $c$ とすると、符号はまとめて書けます。

$$\mathrm{sgn}(\sigma )=(-1{)}^{n-c}$$

長さが偶数の巡回が奇数個あるときだけ奇置換になる、と言いかえてもよい。

交代群

符号の核が交代群 $A_n$ です。核なので、$S_n$ の正規部分群になる。

$n\ge 2$ なら符号は全射なので、指数は $2$ で位数は $n!/2$。$n=1$ のときは奇置換がなく、$A_1=S_1$ になります。

An は 3 次巡回で生成される

$n\ge 3$ なら、$A_n$ は 3 次巡回だけで作れます。偶置換は互換を偶数個並べた形なので、前から 2 つずつ組にする。

組の中身は 3 通りに分かれる。同じ互換が 2 つ並ぶなら積は恒等置換で、$e=(123)(132)$ と書ける。

番号を 1 つ共有するときは、3 次巡回の 2 乗になる。

$$(ab)(ac)=(acb)=(abc{)}^2$$

番号を共有しないときは、3 次巡回 2 つの積。

$$(ab)(cd)=(abc)(bcd)$$

どの場合も 3 次巡回だけで書けるので、$A_n$ が 3 次巡回で生成されると言えます。

例：A3 と A4

$A_3$ は $e$、$(123)$、$(132)$ の 3 個です。位数 3 の巡回群で、$\mathbb{Z}/3\mathbb{Z}$ と同型になる。

$A_4$ は位数 12。二重互換 3 つと単位元がクラインの四元群 $V$ をなし、これが $A_4$ の正規部分群になります。

$A_4$ には位数 6 の部分群がない。位数が約数でも部分群があるとは限らない、という有名な例です。

$A_4$ の中では $(123)$ と $(132)$ が共役になりません。$n\ge 5$ になると、すべての 3 次巡回が $A_n$ の中で共役になる。

商は位数 2 の群

$S_n$ を $A_n$ で割ると、位数 2 の群になります。

$$S_n/A_n\cong \{+1,-1\}$$

剰余類は $A_n$ と $\tau A_n$ の 2 つで、$\tau$ はどの奇置換でもよい。奇置換の全体は部分群にならない。

単位元が偶置換なので、そもそも部分群の条件から外れています。

行列式に現れる符号

行列式の定義に、符号がそのまま出てきます。

$$\det A=\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )\prod _{i=1}^n{a}_{i\sigma (i)}$$

$n!$ 個の項に符号が付き、足し合わせる形。置換行列 $P_{\sigma }$ の行列式も $\mathrm{sgn}(\sigma )$ になる。

行を 2 つ入れかえると行列式の符号が変わるのは、互換を 1 つ掛けたことに対応します。

15 パズルが解けない理由

$4\times 4$ の盤に $1$ から $15$ までのタイルと、空きマスが 1 つあります。正しい並びから $14$ と $15$ だけを入れかえた配置を考える。

この配置には、どうやってもたどり着けません。タイルを 1 枚動かす操作は、そのタイルと空きマスの互換にあたる。

だから 1 手ごとに置換の符号が変わります。同時に、空きマスの行と列の和の偶奇も 1 手ごとに変わる。

2 つの偶奇の組み合わせが動かないので、そこが不変量になります。$14$ と $15$ の入れかえは互換 1 つで、符号だけが変わり空きマスは元の位置。

だから届かない。到達できる配置は全体の半分で、$16!/2$ 通りです。

Sam Loyd がこの配置に $1000$ ドルの懸賞を出しましたが、賞金は誰のものにもなりませんでした。不可能であることは、懸賞が出る 10 年以上前に示されている。

よくある誤り

参考文献