01.1.偶置換・奇置換

Proposition

偶置換・奇置換の一意性

Statement

1. すべての置換は巡回置換の積で表される.(順番を除き一意)
2. すべての置換は互換の積で表される.(一意ではない)
3. 置換が偶置換か奇置換かは一意に定まる

Proof

1.
$\sigma \in S_n$
$\forall i \in \{1 \cdots n\}, \sigma(i) \in \{1 \cdots n\}$
$(\because \sigma:\{1 \cdots n\} \rightarrow \{1 \cdots n\})$
$\exists j \in \{1 \cdots n\} \text{ such that } \sigma^j (i) = i$
$\sigma|_{\{i,\sigma(i),\cdots,\sigma^{j-1}(i)\}}$ is a cycle.
for $\sigma' = \sigma|_{\{1 \cdots n\} - \{i,\sigma(i),\cdots,\sigma^{j-1}(i)\}}$,
you can repeat same action.
finally $\sigma$ consists of cycles.
2.
$\sigma \in S_n$
let $\sigma_1 = (1, \sigma(1)) \cdot \sigma$
then $\sigma_1(1) = 1$
let $\sigma_2 = (2, \sigma_1(2)) \cdot \sigma_1$
then
$\sigma_2(1) = 1 \because \sigma_1(1) \neq 2, \sigma_1(2)$
$\sigma_2(2) = 2$
let $\sigma_n = (n, \sigma_{n-1}(n)) \cdot \sigma_{n-1}$
then
$\sigma_n(i) = i \quad (i \in \{1 \cdots n\})$
$\therefore \sigma_n = e$
then
$(1,\sigma(1))(2,\sigma_1(2))\cdots(n,\sigma_{n-1}(n)) = \sigma$
3.証明1
Let
$\Delta(x_1, \cdots, x_n) = \prod_{1 \le i \lt j \le n} (x_i - x_j)$ $\sigma \in S_n, \sigma \Delta(x_1,\cdots,x_n) = \Delta(x_{\sigma(1)}, \cdots, x_{\sigma(n)})$
then
if $\tau \in S_n$ is a Transposition, then
$\tau \Delta(x_1, \cdots, x_n) = -\Delta(x_1, \cdots, x_n)$
$\because$ Let $\tau = (i \ j)$
then
$\tau (x_i - x_j) = -(x_i - x_j)$
for $i \lt a \lt j$
$\tau (x_i - x_a)(x_a - x_j) = (x_i - x_a)(x_a - x_j)$
for $a \lt i \lt j$
$\tau (x_a - x_i)(x_a - x_j) = (x_a - x_i)(x_a - x_j)$
for $i \lt j \lt a$
$\tau (x_i - x_a)(x_j - x_a) = (x_i - x_a)(x_j - x_a)$
.

$\tau\rho \Delta(x_1, \cdots, x_n) = \tau \Delta(x_{\rho(1)}, \cdots, x_{\rho(n)}) = \Delta(x_{\tau\rho(1)}, \cdots, x_{\tau\rho(n)})$

$\therefore$
Suppose $\sigma = \tau_1 \tau_2 \cdots \tau_l = \rho_1 \rho_2 \cdots \rho_n$
$\sigma \Delta(x_1, \cdots, x_n) = (-1)^l \Delta(x_1, \cdots, x_n) = (-1)^m \Delta(x_1, \cdots, x_n)$
$\therefore (-1)^l = (-1)^m$
$\therefore l = m \quad (\text{mod } 2)$
3.証明2
$\sigma \in S_n$
Suppose $\sigma = a_1 a_2 \cdots a_l = b_1 b_2 \cdots b_m \quad (a_i, b_j:\text{Transposition})$
then
$a_1 a_2 \cdots a_l b_m b_{m-1} \cdots b_2 b_1 = id \quad (\text{identical})$
$l + m = 0 \quad (\text{mod } 2)$ を言えば十分.
任意の互換 $(i \ j) \quad (i \lt j)$ に対して
$(i \ j) = (i \ i+1)(i+1 \ i+2)\cdots(j-1 \ j)(j-2 \ j-1)(j-3 \ j-2)\cdots(i+1 \ i+2)(i \ i+1)$
このとき互換の数は $2(j-i) - 1$ で奇数.
従って任意の $a_i, b_j$ を上記のような形で隣り合う数字の互換に書き換えたとしても 互換の数の偶奇は変わらない.
このように
$a_1 a_2 \cdots a_l b_m b_{m-1} \cdots b_2 b_1 = id$
を
$\{(1 \ 2) \cdots (n-1 \ n) \}$
で置き換えたものを
$c = c_p c_{p-1} \cdots c_2 c_1 \quad(c = id)$ とおく
$c(x) = x \quad (1 \le \forall x \le n)$ であり
$c(x) = c_p(c_{p-1}(\cdots c_2(c_1(x)))) = c_p\dots c_2 \cdot c_1 (x)$ の中で
$x$の置換に関与する互換のみを
$c_{1}^{(x)},\cdots c_{q_x}^{(x)}$
とすると
$c|_x(x) = c_{q_x}^{(x)} \cdots c_{1}^{(x)} (x)$
と表せる. このとき
$\forall i, \exists j, c_i^{(x)} = c_j^{(x)} \quad (1 \le i, j \le q_x, i \neq j)$
すなわち $c_i^{(x)} = (\alpha \ \alpha + 1) \quad (1 \le i \le q_x)$ だとすると 対応する $c_j^{(x)} = (\alpha + 1 \ \alpha) \quad (1 \le j \le q_x)$ を見つけて、 ペアを作ることができる ---(＊)
一方、互換の定義より
$\forall c_i^{(x)}, \exists c_j^{(y)}, c_i^{(x)} = c_j^{(y)} \quad (1 \le x, y \le n, x \neq y)$
とできる ---(＊＊)
$1 \le x \le n$ のすべての $x$ について $c_i^{(x)} \quad (1 \le i \le q_x)$ を列挙して、 改めて $D = \{d_1 \cdots d_{2p}\}$ とすると

---(＊)の性質よるペアリングによる全単射
$f:D \rightarrow D$
---(＊＊)の性質よるペアリングによる全単射
$g:D \rightarrow D$
を定義することができる.
(注意:$\forall d_i, f(f(d_i)) = d_i, g(g(d_i)) = d_i)$)

$D$ から任意の $d_i$ を選択して
$d_\alpha^{(1)} = d_i$
$d_\beta^{(1)} = f(d_i)$
$d_\gamma^{(1)} = g(d_\alpha^{(1)}) \quad (= g(d_i))$
$d_\delta^{(1)} = g(d_\beta^{(1)}) \quad (= g(f(d_i)))$
とおく.
$D_1 = D - \{d_\alpha^{(1)}, d_\beta^{(1)}, d_\gamma^{(1)}, d_\delta^{(1)} \}$
とすると
$|D_1| = |D| - 4 = 2p - 4$
(注意：互換としては $d_\alpha^{(1)} = d_\beta^{(1)} = d_\gamma^{(1)} = d_\delta^{(1)}$ であるが、$D$ の要素として考えるとこれら４つはすべて異なる)
このとき $D$ の要素として
$f(d_\gamma^{(1)}) = d_\delta^{(1)}$ になる場合と
$f(d_\gamma^{(1)}) \neq d_\delta^{(1)}$ になる場合が考えられる.
$f(d_\gamma^{(1)}) = d_\delta^{(1)}$ の場合は
$D_1$ から任意の $d$ を選択して、
$d_\alpha^{(2)} = d$
$d_\beta^{(2)} = f(d)$
$f(d_\gamma^{(1)}) \neq d_\delta^{(1)}$ の場合は
$d_\alpha^{(2)} = f(d_\gamma^{(1)})$
$d_\beta^{(2)} = f(d_\delta^{(1)})$
とすると、
$d_\gamma^{(2)} = g(d_\alpha^{(2)})$
$d_\delta^{(2)} = g(d_\beta^{(2)})$
と定義することで
$f,g$ の性質から
$|\{d_\alpha^{(2)}, d_\beta^{(2)}, d_\gamma^{(2)}, d_\delta^{(2)}\}| = 4$ (すなわち全て異なる)
$\{d_\alpha^{(2)}, d_\beta^{(2)}, d_\gamma^{(2)}, d_\delta^{(2)}\} \subset D_1$
$D_2 = D_1 - \{d_\alpha^{(2)}, d_\beta^{(2)}, d_\gamma^{(2)}, d_\delta^{(2)}\}$
$|D_2| = |D_1| - 4 = 2p - 4 * 2$
とすることができる.
$D_i \subset D$ が以下の性質(＊＊＊)を持っていると仮定する
$\forall x \in D - D_i, g(x) \in D - D_i$ すなわち $\forall x \in D_i, g(x) \in D_i$
$\forall x \in (D - D_i) - \{d_\gamma^{(i)}, d_\delta^{(i)} \}, f(x) \in D - D_i$
このとき
$f(d_\gamma^{(i)}) = d_\delta^{(i)}$ ならば
$D_i$ から任意の元 $d$ を選択して
$d_\alpha^{(i+1)} = d$
$d_\beta^{(i+1)} = f(d)$
$f(d_\gamma^{(i)}) \neq d_\delta^{(i)}$ ならば
$d_\alpha^{(i+1)} = f(d_\gamma^{(i)})$
$d_\beta^{(i+1)} = f(d_\delta^{(i)})$
とし $d_\gamma^{(i+1)} = g(d_\alpha^{(i+1)})$
$d_\delta^{(i+1)} = g(d_\beta^{(i+1)})$
と定義すると
$D_{i+1}$ も性質(＊＊＊)をもつ.
したがってこの操作は繰り返すことが可能である.
$\exists k, D_k = \emptyset$
すなわち
$|D_k| = |D| - 4 * k = 0$
$\therefore |D| = 2p = 4 * k$
$\therefore p = 2 * k$
$p$ と $l + m$ の偶奇は一致するから $l + m$ も偶数
QED