置換
置換
N個の元からなる集合を1対1に並び替える事を置換という(並び替えは$N!$ パターン)
\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
$$
と 同義
単位置換(恒等置換)
置換前後で順番が変わらない変換
\begin{eqnarray}
1_n = \left(
\begin{array}{cccc}
1 & 2 & \ldots & n \\
1 & 2 & \ldots & n
\end{array}
\right)
\end{eqnarray}
逆置換
置換前の並び順に戻る置換
\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}$
積の別表現
イメージしやすい様に
\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文字 に対して下記を満たす置換を互換という
・2つの文字だけを交換
・他の N -2 文字は動かさない
即ち、置換は何回かの互換で表現できる(但し、その表現方法は1種類ではない)
互換に関する重要な定理として
定理
任意の置換が何個かの互換の積で表現される時、その回数の偶奇は、元の置換の表現によって決まる
というのがある。
これは、例えば
置換$\sigma$ が、2回の互換の表現されるならば、2N回(N:自然数)の互換で表現できるが、 2N+1回(奇数)では表現できない
という事を言っている。
証明の準備として、差積の概念を導入する。
差積
N個の変数の全てのペアの差の積を差積という
(但し変数の位置インデックスに対して $i<j$ )
定義
\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個の変数から2つ取る組み合わせなので
\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)
$$
\begin{align}
積の数 = {}_3 \mathrm{ C }_2 = \frac{{}_3\mathrm{ P }_2}{2!} = \frac{3 \cdot (3-1)}{2} = 3
\end{align}
交代式
任意の2つの変数を交換しても式が -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)}$$
因みに、任意の2つの変数を交換しても元と変わらない多項式は対称式と呼ばれる
差積は交代式?
$ 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$
\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$ が2通りの互換
$$
\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 $ で表現し
\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$)
- $\phi(x,y) \in A $
- $\phi(x,I) = x $ となる $I$ が存在
- $\phi(x,x^{-1} ) = I $ となる $x^{-1}$ が存在
例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 $
参照
Author And Source
この問題について(置換), 我々は、より多くの情報をここで見つけました https://qiita.com/sukapontan/items/410ca17efdc7527588c2著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .