置換の定義と基本的な性質

置換とは

置換 というのは、順番のついた文字の並べ替え変換のことです。

例えば、\((1, 2, 3)\) という三つの文字(数字)を、\((3, 1, 2)\) に並べ替えるとします。

\[ (1, 2, 3) \ \xrightarrow{\text{(3,1,2)の順に並べ替える}} \ (3, 1, 2) \]

これも「置換」のひとつで、記号シグマ \(\sigma\) を使って、次のように書きます。

\[ \sigma = \begin{pmatrix} 1 & 2 & 3\\ 3 & 1 & 2 \end{pmatrix} \]

これは、縦に数字を読みます。上の行の \(1\) の下に \(3\) が書いてあるのは、「元々 \(1\) だったところが \(3\) に置き換わる」、ということを表しています。 同様に \(2\) の下に \(1\) が書いてあるので、「元々 \(2\) だったところが \(1\) になる」ことを表す、という具合です。

上の行は、必ずしも \(1, 2, \cdots, n\) と順番に並べる必要はありません。上の行の文字(数字)と、その真下の数字との対応関係に意味があります。したがって、

\[ \sigma = \begin{pmatrix} 1 & 2 & 3\\ 3 & 1 & 2 \end{pmatrix} = \begin{pmatrix} 2 & 3 & 1\\ 1 & 2 & 3 \end{pmatrix} = \cdots \]

という風に、同じ置換変換でも、表し方はひとつとは限りません。でも、ぐちゃぐちゃに並べても、わかりにくいだけでしょうから、ここでは、上の行はいつも、\(1, 2, \cdots\) と順序よく並べることにします。

この置換 \(\sigma\) では、\(1\) が \(3\) に、\(2\) が \(1\) に、\(3\) が \(2\) に変換されています。このことを、

\[ \begin{aligned} \sigma(1) &= 3\\ \sigma(2) &= 1\\ \sigma(3) &= 2 \end{aligned} \]

と書き表します。

置換は順列の並べ替えですから、\(n\) 文字(数字)の置換は \(n!\) 個あります。

例えば、\((1,2)\) の 2 文字 (数字) の置換は \(n=2\) で、

\[ \begin{pmatrix} 1 & 2\\ 1 & 2 \end{pmatrix}, \ \begin{pmatrix} 1 & 2\\ 2 & 1 \end{pmatrix} \]

の \(2 (= 2!)\) 個。

\((1, 2, 3)\) の 3 文字の置換は、

\[ \begin{array}{cc} \begin{pmatrix} 1 & 2 & 3\\ 1 & 2 & 3 \end{pmatrix},& \begin{pmatrix} 1 & 2 & 3\\ 1 & 3 & 2 \end{pmatrix},\\[1.2em] \begin{pmatrix} 1 & 2 & 3\\ 2 & 1 & 3 \end{pmatrix},& \begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{pmatrix},\\[1.2em] \begin{pmatrix} 1 & 2 & 3\\ 3 & 1 & 2 \end{pmatrix},& \begin{pmatrix} 1 & 2 & 3\\ 3 & 2 & 1 \end{pmatrix} \end{array} \]

の \(6 \ (= 3!)\) 個です。

恒等置換

置換のうち、\(n\) 個の文字(数字)が全て、\(\sigma(i) = i \ \ (n=1,2,\cdots,n)\) のときの置換を特に、恒等置換 といい、\(1_n\) で表します。

例えば、\(n=3\) のときの恒等置換は、

\[ \sigma = \begin{pmatrix} 1 & 2 & 3\\ 1 & 2 & 3 \end{pmatrix} \]

です。

互換

二つの文字(数字)を入れ替えるだけの置換のことを特に、互換といいます。

例えば、次の置換 \(\sigma\) では、 \(1\) はそのままで、\(2\) と \(3\) が入れ替わっています。

\[ \sigma = \begin{pmatrix} 1 & 2 & 3\\ 1 & 3 & 2 \end{pmatrix} \]

したがって、これは互換である、といえます。

置換の積

置換を連続して行うことを考えましょう。

例えば、置換 \(\sigma_{1}\) として、

\[ \sigma_1 = \begin{pmatrix} 1 & 2 & 3\\ 1 & 3 & 2 \end{pmatrix} \]

として、置換 \(\sigma_2\) として

\[ \sigma_2 = \begin{pmatrix} 1 & 2 & 3\\ 3 & 1 & 2 \end{pmatrix} \]

とします。

すると、置換 \(\sigma_1\) を行ってから、置換 \(\sigma_2\) を連続して行った合成変換の結果は、 元の \(1\) が \(3\) になり、\(2\) は \(2\) のまま、 \(3\) が \(1\) になります。

\[ \def\arraystretch{1.5} \begin{array}{c:c:c:c} & 1 & 2 & 3 \\ \hline \sigma_1 \text{の結果} & 1 & 3 & 2 \\ \hline \sigma_2 \text{の結果} & 3 & 2 & 1 \end{array} \]

これを、

\[ \sigma_2 \sigma_1 = \begin{pmatrix} 1 & 2 & 3\\ 3 & 2 & 1 \end{pmatrix} \]

と書き、この合成変換 (置換) を置換 \(\sigma_1\) と置換 \(\sigma_2\) の積といいます。

一般に、積 \(\sigma_2 \sigma_1 \ne \sigma_1 \sigma_2\) です。上の例では、

\[ \def\arraystretch{1.5} \begin{array}{c:c:c:c} & 1 & 2 & 3 \\ \hline \sigma_2 \text{の結果} & 3 & 1 & 2 \\ \hline \sigma_1 \text{の結果} & 2 & 1 & 3 \end{array} \]

ですから、積 \(\sigma_1 \sigma_2\) は

\[ \sigma_1 \sigma_2 = \begin{pmatrix} 1 & 2 & 3\\ 2 & 1 & 3 \end{pmatrix} \]

ですから、\(\sigma_2 \sigma_1 \ne \sigma_1 \sigma_2\) であることがわかります。

任意の置換はいくつかの互換の積で表される

証明は割愛しますが、次の定理は重要です。

上で説明したように、「互換」というのは、「二つの文字（数字）を入れ替えるだけ」の置換のことです。 つまり、この定理は、どんな置換でも、互換 (二つずつ入れ替える置換) をいくつか合成すれば、同等の置換を行うことができる、ということです。

例えば、次の置換 \(\sigma\) は

\[ \sigma = \begin{pmatrix} 1 & 2 & 3\\ 3 & 1 & 2 \end{pmatrix} \]

は

\[ \sigma_1 = \begin{pmatrix} 1 & 2 & 3\\ 1 & 3 & 2 \end{pmatrix} \ \ \text{と} \ \ \sigma_2 = \begin{pmatrix} 1 & 2 & 3\\ 3 & 2 & 1 \end{pmatrix} \]

の積 (合成変換) \(\sigma_2 \sigma_1\) として、表すことができます。

\[ \def\arraystretch{1.5} \begin{array}{c:c:c:c} & 1 & 2 & 3 \\ \hline \sigma_1 \text{の結果} & 1 & 3 & 2 \\ \hline \sigma_2 \text{の結果} & 3 & 1 & 2 \end{array} \]

\[ \sigma = \begin{pmatrix} 1 & 2 & 3\\ 3 & 1 & 2 \end{pmatrix} = \sigma_2 \sigma_1 \]

偶置換と奇置換

偶数個の互換で表される置換を 偶置換、 奇数個の互換で表される置換を 奇置換 といいます。

上の例では、置換 \(\sigma\) は２個の互換の積 \(\sigma_2 \sigma_1\) として表されたので、\(\sigma\) は偶置換です。

さらに、次の定理が成り立つことが知られています。

つまり、どの置換も「偶置換である」か「奇置換である」か、決まっているということです。

置換の符号

次を置換 \(\sigma\) の符号として、定義します。

逆置換

置換 \(\sigma\) の逆変換を \(\sigma\) の逆置換 といい、\(\sigma^{-1}\) で表します。

\[ \sigma = \begin{pmatrix} 1 & 2 & 3\\ 3 & 1 & 2 \end{pmatrix} \]

であるとき

\[ \sigma^{-1} = \begin{pmatrix} 3 & 1 & 2\\ 1 & 2 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{pmatrix} \]

です。当然ながら \(\sigma\sigma^{-1} = \sigma^{-1}\sigma = 1_n\) (逆置換と置換の積は恒等置換) が成り立ちます。

\(n\) 個の置換全体の集合 (\(n\) 次の対称群) を \(S_n\) としたとき、\(n\) 個の逆置換全体の集合は \(S_n\) と一致します。

また、符号は元の置換と一致します。

\[\text{sgn}(\sigma) = \text{sgn}(\sigma^{-1})\]

以上、ここでは置換の定義と基本的な性質について、説明しました。