置換 - データサイエンス関連+αのメモ

（結合法則）任意の $\sigma, \tau, \rho \in S_n$ に対して $(\rho \tau) \sigma=\rho(\tau \sigma)$
（単位元の存在）任意の $\sigma \in S_n$ に対して $\sigma \varepsilon=\varepsilon \sigma=\sigma$ ( $\varepsilon$ は単位置換)
（逆元の存在）任意の $\sigma \in S_n$ に対して $\sigma^{-1} \sigma=\sigma \sigma^{-1}=\varepsilon$

巡回置換¶

$M_n = \{ 1, 2, \cdots, n \}$ のうち $i_1, i_2, \cdots, i_m$ のみを

i_1 \rightarrow i_2, \quad i_2 \rightarrow i_3, \quad \cdots, \quad i_m \rightarrow i_1

(15)

のように一巡させる置換

\sigma=\left(\begin{array}{ccccccc} i_1 & i_2 & \cdots & i_m & i_{m+1} & \cdots & i_n \\ i_2 & i_3 & \cdots & i_1 & i_{m+1} & \cdots & i_n \end{array}\right)

(16)

を 巡回置換 といい、

\sigma=\left(\begin{array}{llll} i_1 & i_2 & \cdots & i_m \end{array}\right)

(17)

と書く。

例：

\sigma=\left(\begin{array}{lll} 1 & 2 & 3\\ 3 & 2 & 1 \end{array}\right)

(18)

は $1 \to 3, 3 \to 1$ であり、2は動かさないので $\sigma=\left(\begin{array}{lll} 1 & 3 \end{array}\right)$ と書ける

証明

例えば1からはじめて $1\to j_1 \to j_2 \to \cdots \to j_{k-1} \to j_{k}$ のように値の移り変わりを見ることにする。

$M_n$ は有限なので、いつかは今まで登場した数が再び登場する。

もし仮に、再び登場するのが1でない（ $j_k \neq 1$ ）とすると、その値に到達する別のルート $j_m \to j_k$ が $j_{k-1} \to j_k$ 以外にあるということになるので、この写像は単射ではなくなり、置換の定義と合わなくなる。

置換は単射なので、1から始めてもどってくる最初の数は1になる。

このことから巡回置換 $(\begin{array}{lllll} 1 & j_1 & j_2 & \cdots & j_{k-1} \end{array})$ は1つに定まる。

残りの数においても同様に巡回置換が得られ、この操作は有限回で終わるので、 $\sigma$ は巡回置換の積で表される。

例：

\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 3 & 4 & 5 & 2 & 1 \end{pmatrix}

(19)

は例えば1から始めると $1 \to 3 \to 5 \to 1$ と戻って来るので $\begin{pmatrix} 1 & 3 & 5 \end{pmatrix}$

残りの2,4についても $2 \to 4 \to 2$ になるので $\begin{pmatrix} 2 & 4 \end{pmatrix}$

なので

\sigma = \begin{pmatrix} 1 & 3 & 5 \end{pmatrix} \begin{pmatrix} 2 & 4 \end{pmatrix}

(20)

互換¶

巡回置換のうち、特に2文字の巡回置換 $(i \ j)$ を互換という

例：

\left(\begin{array}{llll} 1 & 3 & 4 & 5 \end{array}\right)=\left(\begin{array}{lll} 1 & 5 \end{array}\right)\left(\begin{array}{lll} 1 & 4 \end{array}\right)\left(\begin{array}{ll} 1 & 3 \end{array}\right)

(22)

置換の符号¶

置換 $\sigma$ が $m$ 個の互換の積であらわされるとき

\text{sgn}(\sigma) = (-1)^m

(23)

とおき、 $\sigma$ の符号という

例：

\left(\begin{array}{lll} 1 & 2 & 3 \\ 3 & 1 & 2 \end{array}\right)=\left(\begin{array}{lll} 1 & 3 & 2 \end{array}\right) = \left(\begin{array}{lll} 1 & 2 \end{array}\right) \left(\begin{array}{lll} 1 & 3 \end{array}\right)

(24)

ゆえに

\operatorname{sgn}\left(\begin{array}{lll} 1 & 2 & 3 \\ 3 & 1 & 2 \end{array}\right)=(-1)^2=1

(25)

例：

\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 5 & 4 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \end{pmatrix} \begin{pmatrix} 4 & 5 \end{pmatrix} = \begin{pmatrix} 1 & 3 \end{pmatrix} \begin{pmatrix} 1 & 2 \end{pmatrix} \begin{pmatrix} 4 & 5 \end{pmatrix}

(26)

なので $m=3$ 、よって

\text{sgn} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 5 & 4 \end{pmatrix} =(-1)^3 = -1

(27)

符号の定義の無矛盾性¶

置換を互換の積として表す方法は1通りではない

例：

\sigma = \left(\begin{array}{lll} 1 & 2 & 3 \\ 3 & 1 & 2 \end{array}\right)

(28)

1から始めた場合

\sigma =\begin{pmatrix} 1 & 3 & 2 \end{pmatrix} =\begin{pmatrix} 1 & 2 \end{pmatrix} \begin{pmatrix} 1 & 3 \end{pmatrix}

(29)

置換の符号が矛盾なく定義されることを理解するためには

置換による多項式の変換
差積

というコンセプトを理解する必要がある

置換による多項式の変換¶

$n$ 変数 $x_1, x_2, \cdots, x_n$ の多項式 $P(x_1, x_2, \cdots, x_n)$ と置換 $\sigma \in S_n$ が与えられたとき、変数 $x_1, x_2, \cdots, x_n$ をそれぞれ $x_{\sigma(1)}, x_{\sigma(2)}, \cdots, x_{\sigma(n)}$ でおきかえて得られる多項式を、置換 $\sigma$ による多項式 $P$ の変換といい， $\sigma P$ で表わす。