置換

置換#

一般の $n$ 次正方行列の行列式を定義するためには、置換を定義する必要がある。

$n$ 個の文字 $1, 2, \dots, n$ からなる集合を

M_{n} = {1, 2, \dots, n}

とする。写像 $σ : M_{n} \to M_{n}$ が全単射であるとき， $σ$ を $M_{n}$ の置換という。

置換 $σ$ による対応が

1 \mapsto i_{1}, 2 \mapsto i_{2}, \dots, n \mapsto i_{n}

つまり

σ (1) = i_{1}, σ (2) = i_{2}, \dots, σ (n) = i_{n}

であるとする。このとき $σ$ を

\begin{array}{r} σ = (\begin{array}{cccc} 1 & 2 & \dots & n \\ i_{1} & i_{2} & \dots & i_{n} \end{array}) \end{array}

と表す。

置換についての注意点#

1. 順番は入れ替えても問題ない

上下の組（対応関係）が変わらなけば順番は変えて書いても問題ない。つまり

\begin{array}{r} (\begin{array}{ccc} 1 & 2 & 3 \\ i_{1} & i_{2} & i_{3} \end{array}) = (\begin{array}{ccc} 2 & 1 & 3 \\ i_{2} & i_{1} & i_{3} \end{array}) \end{array}

である

2. 重複する組は省略できる

\begin{array}{r} (\begin{array}{ccc} 1 & 2 & 2 \\ i_{1} & i_{2} & i_{2} \end{array}) = (\begin{array}{ccc} 1 & 2 \\ i_{1} & i_{2} \end{array}) \end{array}

置換の積#

集合 $M_{n}$ の置換からなる集合を $S_{n}$ とする。 $σ, τ \in S_{n}$ に対して、 $σ$ と $τ$ の合成写像

τ \circ σ : M_{n} ⟶ M_{n}

も全単射であり、 $τ \circ σ \in S_{n}$ である。簡単のため $τ \circ σ$ は $τ σ$ と書くことが多い。

\begin{array}{r} σ = (\begin{array}{cccc} 1 & 2 & \dots & n \\ i_{1} & i_{2} & \dots & i_{n} \end{array}), τ = (\begin{array}{cccc} 1 & 2 & \dots & n \\ j_{1} & j_{2} & \dots & j_{n} \end{array}) \end{array}

のとき

\begin{array}{r} \begin{aligned} τ σ = (\begin{array}{cccc} 1 & 2 & \dots & n \\ τ (1) & τ (2) & \dots & τ (n) \end{array}) (\begin{array}{cccc} 1 & 2 & \dots & n \\ σ (1) & σ (2) & \dots & σ (n) \end{array}) \\ = (\begin{array}{cccc} σ (1) & σ (2) & \dots & σ (n) \\ τ (σ (1)) & τ (σ (2)) & \dots & τ (σ (n)) \end{array}) (\begin{array}{cccc} 1 & 2 & \dots & n \\ σ (1) & σ (2) & \dots & σ (n) \end{array}) \\ = (\begin{array}{cccc} 1 & 2 & \dots & n \\ τ (σ (1))) & τ (σ (2)) & \dots & τ (σ (n)) \end{array}) \end{aligned} \end{array}

例：

\begin{array}{r} σ = (\begin{array}{llll} 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1 \end{array}), τ = (\begin{array}{llll} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{array}) \end{array}

\begin{array}{r} \begin{aligned} τ (σ (1)) & = τ (3) = 4, & τ (σ (2)) = τ (2) = 1 \\ τ (σ (3)) & = τ (4) = 3, & τ (σ (4)) = τ (1) = 2 \end{aligned} \end{array}

\begin{array}{r} τ σ = (\begin{array}{llll} 1 & 2 & 3 & 4 \\ 4 & 1 & 3 & 2 \end{array}) \end{array}

単位置換#

すべての文字を動かさない置換

\begin{array}{r} ε = (\begin{array}{llll} 1 & 2 & \dots & n \\ 1 & 2 & \dots & n \end{array}) \end{array}

を 単位置換 あるいは 恒等置換 という

逆置換#

任意の置換 $σ = (\begin{array}{cccc} 1 & 2 & \dots & n \\ i_{1} & i_{2} & \dots & i_{n} \end{array})$ に対して,

\begin{array}{r} σ^{- 1} = (\begin{array}{cccc} i_{1} & i_{2} & \dots & i_{n} \\ 1 & 2 & \dots & n \end{array}) \end{array}

を $σ$ の 逆置換 という。

置換の積の演算#

置換の積について、以下が成立する

（結合法則）任意の $σ, τ, ρ \in S_{n}$ に対して $(ρ τ) σ = ρ (τ σ)$
（単位元の存在）任意の $σ \in S_{n}$ に対して $σ ε = ε σ = σ$ ( $ε$ は単位置換)
（逆元の存在）任意の $σ \in S_{n}$ に対して $σ^{- 1} σ = σ σ^{- 1} = ε$

置換全体は「群」になる

上記の定理1,2,3を満たす演算が与えられた集合を群という。

したがって、 $n$ 文字の置換全体からなる集合 $S_{n}$ は群となり、 $n$ 次の 対称群 または 置換群 とよばれる

巡回置換#

$M_{n} = {1, 2, \dots, n}$ のうち $i_{1}, i_{2}, \dots, i_{m}$ のみを

i_{1} \to i_{2}, i_{2} \to i_{3}, \dots, i_{m} \to i_{1}

のように一巡させる置換

\begin{array}{r} σ = (\begin{array}{ccccccc} i_{1} & i_{2} & \dots & i_{m} & i_{m + 1} & \dots & i_{n} \\ i_{2} & i_{3} & \dots & i_{1} & i_{m + 1} & \dots & i_{n} \end{array}) \end{array}

を 巡回置換 といい、

σ = (\begin{array}{llll} i_{1} & i_{2} & \dots & i_{m} \end{array})

と書く。

例：

\begin{array}{r} σ = (\begin{array}{lll} 1 & 2 & 3 \\ 3 & 2 & 1 \end{array}) \end{array}

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

定理

任意の置換は共通の文字を含まないいくつかの巡回置換の積として表される。この表し方は積の順序を除いて一意的である。

証明

例えば1からはじめて $1 \to j_{1} \to j_{2} \to \dots \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} & \dots & j_{k - 1} \end{array})$ は1つに定まる。

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

例：

\begin{array}{r} σ = (\begin{array}{c} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 2 & 1 \end{array}) \end{array}

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

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

なので

σ = (\begin{matrix} 1 & 3 & 5 \end{matrix}) (\begin{matrix} 2 & 4 \end{matrix})

互換#

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

定理

巡回置換 $(\begin{array}{llll} i_{1} & i_{2} & \dots & i_{m} \end{array})$ は $m - 1$ 個の互換の積で表される

(\begin{array}{llll} i_{1} & i_{2} & \dots & i_{m} \end{array}) = (\begin{array}{ll} i_{1} & i_{m} \end{array}) (\begin{array}{ll} i_{1} & i_{m - 1} \end{array}) \dots (\begin{array}{ll} i_{1} & i_{3} \end{array}) (\begin{array}{ll} i_{1} & i_{2} \end{array})

例：

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

置換の符号#

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

sgn (σ) = (- 1)^{m}

とおき、 $σ$ の符号という

例：

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

ゆえに

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

例：

\begin{array}{r} (\begin{array}{c} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 5 & 4 \end{array}) = (\begin{array}{c} 1 & 2 & 3 \end{array}) (\begin{array}{c} 4 & 5 \end{array}) = (\begin{array}{c} 1 & 3 \end{array}) (\begin{array}{c} 1 & 2 \end{array}) (\begin{array}{c} 4 & 5 \end{array}) \end{array}

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

\begin{array}{r} sgn (\begin{array}{c} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 5 & 4 \end{array}) = (- 1)^{3} = - 1 \end{array}

符号の定義の無矛盾性#

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

例：

\begin{array}{r} σ = (\begin{array}{lll} 1 & 2 & 3 \\ 3 & 1 & 2 \end{array}) \end{array}

1から始めた場合

σ = (\begin{matrix} 1 & 3 & 2 \end{matrix}) = (\begin{matrix} 1 & 2 \end{matrix}) (\begin{matrix} 1 & 3 \end{matrix})

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

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

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

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

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

すなわち

σ P (x_{1}, x_{2}, \dots, x_{n}) = P (x_{σ (1)}, x_{σ (2)}, \dots, x_{σ (n)})

である

$σ, τ$ に対して

τ (σ P) = (τ σ) P

が成り立つ。

例：

\begin{array}{r} P (x_{1}, x_{2}, x_{3}) = x_{3}^{2} + x_{2} x_{1}, σ = (\begin{array}{lll} 1 & 2 & 3 \\ 3 & 1 & 2 \end{array}), τ = (\begin{array}{lll} 1 & 2 & 3 \\ 3 & 2 & 1 \end{array}) \end{array}

とすると

\begin{array}{r} τ σ = (\begin{array}{lll} 1 & 2 & 3 \\ 1 & 3 & 2 \end{array}), σ P = x_{2}^{2} + x_{1} x_{3} \end{array}

したがって

τ (σ P) = x_{2}^{2} + x_{3} x_{1}

(τ σ) P = x_{2}^{2} + x_{3} x_{1}

差積#

\begin{array}{r} \begin{aligned} Δ = Δ (x_{1}, \dots, x_{n}) = \prod_{1 \leq i < j \leq n} (x_{i} - x_{j}) \\ = (x_{1} - x_{2}) (x_{1} - x_{3}) \dots (x_{1} - x_{n}) \\ \times (x_{2} - x_{3}) \dots (x_{2} - x_{n}) \\ ⋱ ⋮ \\ \times (x_{n - 1} - x_{n}) \end{aligned} \end{array}

補題

$σ \in S_{n}$ が互換ならば

σ Δ = - Δ

定理

任意の置換 $σ$ を互換の積として表わすとき、その互換の個数が偶数個であるか奇数個であるかは、与えられた置換 $σ$ によって決まる

置換

Contents

置換#