置換


置換

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$)

  1. $\phi(x,y) \in A $
  2. $\phi(x,I) = x $ となる $I$ が存在
  3. $\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 $

参照

線形代数入門(斎藤 正彦 著)
高校数学の美しい物語 - 差積の意味と置換の符号が定義できることの証明