置換

# 置換
N個の元からなる集合を１対１に並び替える事を置換という（並び替えは$N!$ パターン）

<img width="624" alt="置換の例" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/569644/616cd4d6-4e82-c6e5-9b41-8662e900cead.png">

<img width="654" alt="置換の一般形" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/569644/787faa41-57f1-0a49-1729-d4eaa619e8ad.png">


```math
\begin{eqnarray}
\sigma = \left(
  \begin{array}{cccc}
    1 & 2 & \ldots & n \\
    i_{ 1 } & i_{ 2 } & \ldots & i_{ n }
  \end{array}
\right)
\end{eqnarray}
```

$$
 \sigma(1) = i_1 \quad \sigma(2) = i_2 \quad \cdots \quad \sigma(n) = i_n 
$$ 
と 同義

## 単位置換（恒等置換）
置換前後で順番が変わらない変換

```math
\begin{eqnarray}
1_n = \left(
  \begin{array}{cccc}
    1 & 2 & \ldots & n \\
    1 & 2 & \ldots & n
  \end{array}
\right)
\end{eqnarray}
```

## 逆置換
置換前の並び順に戻る置換

```math
\begin{eqnarray}
\sigma^{-1} & = \left(
  \begin{array}{cccc}
    i_{ 1 } & i_{ 2 } & \ldots & i_{ n } \\
    1 & 2 & \ldots & n
  \end{array}
\right)
& = \left(
  \begin{array}{cccc}
    \sigma_{(1)} & \sigma_{(2)} & \ldots & \sigma_{(n)} \\
    1 & 2 & \ldots & n
  \end{array}
\right)
\end{eqnarray}
```

## 置換の性質

$\large{ (\sigma \cdot \tau) \cdot \rho ＝ \sigma \cdot (\tau \cdot  \rho )}$
$\large{ (1_n \cdot \sigma) ＝ \sigma \cdot 1_n }$
$\large{ \sigma \cdot \sigma^{-1} ＝ \sigma^{-1} \cdot \sigma}$

[参考：群](https://qiita.com/sukapontan/private/410ca17efdc7527588c2#%E5%8F%82%E8%80%83%E7%BE%A4)
### 積の別表現
イメージしやすい様に

```math
\large{ 
\begin{eqnarray}
\tau\sigma & = & \left(
  \begin{array}{cccc}
    1 & 2 & \ldots & n \\
    \tau_{(1)} & \tau_{(2)} & \ldots & \tau_{(n)}
  \end{array}
\right)
\left(
  \begin{array}{cccc}
    1 & 2 & \ldots & n \\
    \sigma_{(1)} & \sigma_{(2)} & \ldots & \sigma_{(n)}
  \end{array}
\right) \\\\

& = & \left(
  \begin{array}{cccc}
    1 & 2 & \ldots & n \\
    \tau_{(\sigma_{(1)})} & \tau_{(\sigma_{(2)})} & \ldots & \tau_{(\sigma_{(n)})}
  \end{array}
\right)
\end{eqnarray}
}
```

# 互換
N文字 に対して下記を満たす置換を互換という
・２つの文字だけを交換
・他の N -2 文字は動かさない

即ち、置換は何回かの互換で表現できる（但し、その表現方法は１種類ではない）
互換に関する重要な定理として

```
定理
任意の置換が何個かの互換の積で表現される時、その回数の偶奇は、元の置換の表現によって決まる
```
というのがある。
これは、例えば
置換$\sigma$ が、２回の互換の表現されるならば、2N回（N：自然数）の互換で表現できるが、 2N+1回（奇数）では表現できない

という事を言っている。
証明の準備として、差積の概念を導入する。

# 差積
N個の変数の全てのペアの差の積を差積という
（但し変数の位置インデックスに対して $i<j$ ） 

## 定義
```math
\begin{align}
 \varDelta (x_1, x_2, \cdots, x_n) & = \displaystyle \prod_{ i < j }(x_j -x_i) \\

& = (x_n -x_{n-1})(x_n -x_{n-1}) \cdots \cdots (x_n -x_2)(x_n -x_1) \\
& \hspace{ 45pt }(x_{n-1} -x_{n-2}) \cdots  (x_{n-1} -x_2)(x_{n-1} -x_1) \\
& \hspace{ 130pt } \vdots \\
& \hspace{ 115pt }(x_3 -x_2)(x_2 -x_1) \\
& \hspace{ 147pt }(x_2 -x_1) 
\end{align}
```

積の数はN個の変数から２つ取る組み合わせなので

```math
\begin{align} 
{}_n \mathrm{ C }_2 =  \frac{{}_n\mathrm{ P }_2}{2!} = \frac{n \cdot (n-1)}{2}
\end{align}
```

### 例） n=3 の場合
$$
\varDelta (x_1, x_2, x_3) = (x_3 - x_2) (x_3 - x_1) (x_2 - x_1) 
$$

```math
\begin{align} 
積の数 = {}_3 \mathrm{ C }_2 =  \frac{{}_3\mathrm{ P }_2}{2!} = \frac{3 \cdot (3-1)}{2} = 3
\end{align}
```

## 交代式
任意の２つの変数を交換しても式が -1 倍される多項式
$$ \large{ f(x_1, x_2, \cdots ,x_{\color{red}{i}},\cdots , x_{\color{red}{j}} \cdots ,  x_n) = - f(x_1, x_2, \cdots ,x_{\color{red}{j}},\cdots , x_{\color{red}{i}} \cdots ,  x_n)}$$

因みに、任意の２つの変数を交換しても元と変わらない多項式は対称式と呼ばれる

### 差積は交代式？
$ x_a $ と $ x_b \ (a < b) $ を交換した時、差積は-1倍される事を確認する

ア）$ (x_a - x_b) \rightarrow (x_b - x_a) = -(x_a - x_b) $ となり、元の差積は -1 倍される
イ）$ a < c < b $ となる c に対して $ (x_{\color{red}{b}} - x_c)(x_c - x_{\color{red}{a}}) \rightarrow (x_{\color{red}{a}} - x_c)(x_c - x_{\color{red}{b}}) $ となり、元の差積は $(-1)^2 = 1$ 倍される
ウ）$ c < a < b $ となる c に対して $ (x_{\color{red}{a}} - x_c)(x_{\color{red}{b}} - x_c) \rightarrow (x_{\color{red}{b}} - x_c)(x_{\color{red}{a}} - x_c)=(x_{\color{red}{a}} - x_c)(x_{\color{red}{b}} - x_c)$ となり、符号に変更はない
エ）$ a < b < c $ となる c に対して $ (x_c - x_{\color{red}{b}})(x_c - x_{\color{red}{a}}) \rightarrow (x_c - x_{\color{red}{a}})(x_c - x_{\color{red}{b}})= (x_c - x_{\color{red}{b}})(x_c - x_{\color{red}{a}})$ となり、符号に変更はない

ア）〜 エ）により、差積は交換式である事が証明された

# 置換における互換の回数の偶奇性について
長くなったが、いよいよ

```
定理
任意の置換が何個かの互換の積で表現される時、その回数の偶奇は、元の置換の表現によって決まる
```
を証明する
$n$ 文字に対する置換 $\sigma$

```math
\begin{eqnarray}
\sigma = \left(
  \begin{array}{cccc}
    1 & 2 & \ldots & n \\
    x_{ 1 } & x_{ 2 } & \ldots & x_{ n }
  \end{array}
\right)
\end{eqnarray}
```
を行なった後に $n$ 変数多項式 $f(x_1, x_2, \cdots, x_n)$ による変換を行う式を
$$
\large{
f(x_{\sigma_{(1)}}, x_{\sigma_{(2)}}, \cdots, x_{\sigma_{(n)}})=f^\sigma(x_1, x_2, \cdots, x_n)
}
$$
と定義する。
今、$f$を差積$\varDelta$とすると、

$$
\large{
f^\sigma(x_1, x_2, \cdots, x_n) = \varDelta \sigma(x_1, x_2, \cdots, x_n) \\\
\hspace{ 80pt } = \pm \varDelta(x_1,x_2, \cdots,x_n)
}
$$ 

となる。
一方、置換 $\sigma$ が２通りの互換 

$$
\large{
\sigma  = \tau_1\ \tau_2 \cdots \ \tau_{k-1} \ \tau_k \\\
\hspace{ 10pt }  = \rho_1\ \rho_2 \cdots \ \rho_{l-1} \ \rho_l \\
}
$$ 

で表現されるならば、置換 $\sigma$ が互換 $\tau$ である場合

$$
\large{
\varDelta \tau(x_1, x_2, \cdots, x_n) = - \varDelta(x_1,x_2, \cdots,x_n)
}
$$ 

なので

$$
\large{
 \varDelta\sigma(x_1, x_2, \cdots, x_n)  =  \varDelta \tau_1\ \tau_2 \cdots \ \tau_{k-1} \ \tau_k \ (x_1,x_2, \cdots,x_n) \\\
 \hspace{ 30pt } =  (-1)^\color{red}{k} \varDelta (x_1,x_2, \cdots, x_k) \\\
\hspace{ 85pt }  =  \varDelta \rho_1\ \rho_2 \cdots \ \rho_{l-1} \ \rho_l \ (x_1,x_2, \cdots,x_n) \\\
\hspace{ 30pt }  =  (-1)^\color{red}{l} \varDelta (x_1,x_2, \cdots, x_k)
}
$$ 

となり、$k$ と $l$ の偶奇性は一致しなければいけない（証明　終了）

## sgn について
置換 $\sigma$ が偶数個の互換の積である場合、偶置換
置換 $\sigma$ が奇数個の互換の積である場合、奇置換
と言う
この時、状態を記号 $ sgn \ \sigma $ で表現し

```math
\begin{eqnarray}
sgn \ \sigma
 =
  \begin{cases}
    +1 & ( \sigma \ 偶置換 ) \\
    -1 & ( \sigma \ 奇置換 )
  \end{cases}
\end{eqnarray} 
```
と定義し、$ sgn $ を置換$ \sigma $の符号と呼ぶ 

# 参考：群
$\phi$:写像 
$A$：集合
$x, y$：Aの要素（$x,y\in A$）

1. $\phi(x,y) \in A $ 
2. $\phi(x,I) = x $ となる $I$ が存在
3. $\phi(x,x^{-1} ) = I $ となる $x^{-1}$ が存在

例１）$A \in \mathbb{R} \quad \phi(x,y) = x \cdot y$
1. $ x \cdot y \in \mathbb{ R } $ 
2. $ x \cdot 1 = x $ 
3. $ x \cdot \frac{1}{x} = 1 $ 

<!-- 
例２）$ A,B : n \times n $ 行列
1. $ A \cdot B = \displaystyle \sum_{i=1}^{n} a_{ij}b_{ij} $
2. $ x \cdot 1 = x $ 
3. $ x \cdot \frac{1}{x} = 1 $ 
-->


# 参照
[線形代数入門(斎藤　正彦 著)](http://www.utp.or.jp/book/b302039.html)
[高校数学の美しい物語 - 差積の意味と置換の符号が定義できることの証明](https://mathtrain.jp/saseki)