ビジュアルプログラミング(26) - エレファント・コンピューティング調査報告

偶置換・奇置換(3)

置換の全体を $S_n$ 、互換(2つの要素を交換する互換)の全体を $T_n$ 、基本互換(隣接する2つの要素を交換する互換)の全体を $F_n$ とおきます。

転倒数 $i: S_n \to \mathbb{N}$

( $\mathbb{N}$ は自然数全体の集合)を定義することができます。バブルソートの交換回数は転倒数と一致するのでバブルソートは終了し

バブルソート $s: S_n \to [ F_n ]$

を定義することができます。 $[ X ]$ は $X$ の元の有限個の列の全体を表します。 $\overline{\tau} \in [ S_n ]$ に対して $\prod \overline{\tau}$ は $\overline{\tau}$ のすべての要素の合成とします。任意の $\sigma \in S_n$ に対して $\sigma = \prod s(\sigma)$ が成り立ちます。

$\overline{\tau} \in [ T_n ]$ に対して列の長さ(要素の個数)を $l(\overline{\tau})$ で表します( $l: [ T_n ] \to \mathbb{N}$ )。

バブルソートの交換回数 $l \circ s: S_n \to \mathbb{N}$

を定義することができます。 $i = l \circ s$ が成り立ちます。パリティー $p: \mathbb{N} \to \mathbb{Z}_2$ ( $\mathbb{Z}_2$ は $2$ を法とする剰余類全体の集合、 $k$ が偶数のとき $p(k) = 0$ 、 $k$ が奇数のとき $p(k) = 1$ )と合成すると

転倒数のパリティー $p \circ i: S_n \to \mathbb{Z}_2$
バブルソートの交換回数のパリティー $p \circ l \circ s: S_n \to \mathbb{Z}_2$
互換の個数のパリティー $p \circ l: [ T_n ] \to \mathbb{Z}_2$

を定義することができます。 $p \circ i = p \circ l \circ s$ が成り立ちます。

$E_n = (p \circ i)^{-1}(0) = (p \circ l \circ s)^{-1}(0)$ の元を偶置換
$O_n = (p \circ i)^{-1}(0) = (p \circ l \circ s)^{-1}(1)$ の元を奇置換

と呼びます。

置換は互換の合成で表すことができる ( $S_n = \langle T_n \rangle$ )

[証明] $\sigma \in S_n$ をとります。 $\sigma = \prod s(\sigma) \in \langle F_n \rangle \subseteq \langle T_n \rangle$ が成り立ちます。[証明終わり]

任意の $\tau \in T_n$ に対して $(p \circ i)(\tau) = 1$

[証明] $\tau$ を $a$ と $b$ の位置の要素をを入れ替える互換とします( $a < b$ )。 $\tau(a) = b$ 、 $\tau(b) = a$ 、それ以外の $x$ については $\tau(x) = x$ となります。 $x < y$ かつ $\tau(x) > \tau(y)$ である組 $(x, y)$ は、
$(a, a+1), (a, a+2), \cdots, (a, b), (a+1, b), (a+2, b), \cdots, (b-1, b)$
の $2(b-a-1)+1$ 個となるので $(p \circ i)(\tau) = 1$ が成り立ちます。[証明終わり]

$\sigma \in S_n$ 、 $\mu \in F_n$ のとき $(p \circ i)(\sigma\mu) = (p \circ i)(\sigma) + 1$

[証明] $\mu$ を $a$ と $a+1$ の位置の要素をを入れ替える互換とします。 $\mu(a) = a+1$ 、 $\mu(a+1) = a$ 、それ以外の $x$ については $\mu(x) = x$ となります。
$\begin{cases} (\sigma\mu)(a) & = & \sigma(a+1) \\ (\sigma\mu)(a+1) & = & \sigma(a) \\ (\sigma\mu)(x) & = & \sigma(x) & (それ以外の \ x) \end{cases}$
となります。よって
$\begin{cases} i(\sigma\mu) & = & i(\sigma) + 1 & (\sigma(a) < \sigma(a+1) \ のとき) \\ i(\sigma\mu) & = & i(\sigma) - 1 & (\sigma(a) > \sigma(a+1) \ のとき) \\ \end{cases}$
となります。よって $(p \circ i)(\sigma\mu) = (p \circ i)(\sigma) + 1$ となります。[証明終わり]

任意の $\tau \in T_n$ に対して $\tau = \mu_1 \mu_2 \cdots \mu_m$ を満たす $\tau = \mu_1, \mu_2, \cdots, \mu_m \in F_n$ ( $m$ は奇数)が存在する

[証明] $\tau$ を $a$ と $b$ の位置の要素をを入れ替える互換とします( $a < b$ )。 $\tau(a) = b$ 、 $\tau(b) = a$ 、それ以外の $x$ については $\tau(x) = x$ となります。 $x$ と $y$ の位置の要素をを入れ替える互換を $[x,y]$ ( $x < y$ )と書くと $\tau$ は
$[a, a+1] [a+1, a+2] \cdots[b-1, b] [b-2, b-1] [b-3, b-2] \cdots [a, a+1]$
の $2(b-a-1)+1$ 個の基本互換の合成となります。[証明終わり]

任意の $\overline{\tau} \in [ T_n ]$ に対して $(p \circ l)(\overline{\tau}) = (p \circ i \circ \prod)(\overline{\tau})$

[証明] $l(\overline{\tau}) = 0$ のとき
$(p \circ l)(\overline{\tau}) = p(0) = 0$
$(p \circ i \circ \prod)(\overline{\tau}) = (p \circ i)(1) = p(0) = 0$
となって主張は成り立ちます。

$(p \circ l)(\overline{\tau}) = (p \circ i \circ \prod)(\overline{\tau})$ と仮定します。
$\overline{\tau}$ に $\mu \in T_n$ を付け加えたものを $\overline{\tau}*\mu$ とします。 $l(\overline{\tau}*\mu) = l(\overline{\tau})+1$ 、 $\prod(\overline{\tau}*\mu) = (\prod\overline{\tau})\mu$ が成り立ちます。
$(p \circ l)(\overline{\tau}*\mu) = p(l(\overline{\tau})+1) = p(l(\overline{\tau})) + 1$ 、
$\mu$ を $a$ と $b$ の位置の要素をを入れ替える互換とすると( $a < b$ )、
$(p \circ i \circ \prod)(\overline{\tau}*\mu) = (p \circ i)( (\prod\overline{\tau})\mu) = p(i(\prod\overline{\tau})+2(b-a-1)+1) = p(i(\prod\overline{\tau}) + 1$
が成り立ちます。よって
$(p \circ l)(\overline{\tau}*\mu) = (p \circ i \circ \prod)(\overline{\tau}*\mu)$
が成り立ちます。よって $l=l(\overline{\tau})$ のときに成り立てば $l=l(\overline{\tau})+1$ のときも成り立ちます。

よって $l=l(\overline{\tau})$ に関する帰納法により主張は成り立ちます。[証明終わり]

任意の $\overline{\tau}, \overline{\tau}' \in [ T_n ]$ に対して $\prod \overline{\tau} = \prod \overline{\tau}'$ ならば $(p \circ l)(\overline{\tau}) = (p \circ l)(\overline{\tau}')$

[証明] $(p \circ l)(\overline{\tau}) = (p \circ i \circ \prod)(\overline{\tau}) = (p \circ i \circ \prod)(\overline{\tau}')= (p \circ l)(\overline{\tau}')$ となるので成り立ちます。[証明終わり]

よって置換を複数の互換の合成として表したとき、互換の個数が偶数であるか奇数であるかは決まっていて、偶数のとき偶置換、奇数のとき奇置換となります。

交換子

置換のパリティーは交換子部分群と関連するので交換子についても考えてみます。

$\alpha, \beta \in S_n$ に対して $[\alpha, \beta] = \alpha \beta \alpha^{-1} \beta^{-1}$ (交換子)、 $C_n = \{[\alpha, \beta] \mid \alpha, \beta \in S_n\}$ とおきます。任意の置換は互換の合成となるので、交換子は偶数の互換の合成となります。よって $C_n \subseteq E_n$ となります。

ここでは $a$ と $b$ を入れ替える互換を $(a, b)$ と書きます。 $\alpha$ と $\beta$ の合成 $\alpha\beta$ は $\alpha$ で写したものを $\beta$ で写したものを表すとします。とくに $(a, b)$ と $(c, d)$ の合成 $(a, b)(c, d)$ は $c$ と $d$ を入れ替えたものに対して $a$ と $b$ を入れ替える置換を表すとします。 $a$ を $b$ に、 $b$ を $c$ に、 $c$ を $a$ に写し、その他の要素は変化しない置換を $(a,b,c)$ と書きます。恒等置換を $e$ と書きます。

$n \geq 2$ のとき
$(1,2)(1,2) = e \in C_n$
$n \geq 3$ のとき
$(1,2)(1,3) = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} = (1,2,3)^2 = ( (1,3)(1,2) )^2 = (1,3)(1,2)(1,3)^{-1}(1,2)^{-1} \in C_n$
$n \geq 4$ のとき
$(1,3)(2,4)(3,4) = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 2 & 1 \end{pmatrix}$
$( (1,3)(2,4)(3,4) )^2 = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{pmatrix} = (1,2)(3,4)$
$(1,2)(3,4) = ( (1,3)(2,4)(3,4) )^2 = (1,3)(2,4)(3,4)( (1,3)(2,4) )^{-1}(3,4)^{-1} \in C_n$
となります。