置換はこれから学ぶ行列式、余因子、逆行列などをはじめ、いろんな場面で使われています。
また置換に関係した用語が多くあります。混乱しないようにして下さい。
1.置 換
まずは置換 σ の例を示します。
\(σ=\begin{pmatrix}
1 & \underline{2} & \underline{3} & \underline{4} \\
1 & \underline{3} & \underline{4} & \underline{2}
\end{pmatrix}\) \(=(2\ 3\ 4)\)
注:行列と同じように書いていますが行列ではありません。
集合の概念でいうと:
・上段:\((\{1,\ \ 2,\ \ 3,\ \ 4\ \})\)
写 像 \(\quad \downarrow \searrow \)\(\ \swarrow \downarrow\)
・下段:\((\{a_1,a_2,a_3,a_4\})\)
\(a_1,a_2,a_3,a_4\)は\(1,2,3,4\)に置換される。
具体的にいうと:
上段の1 から4 までの自然数に対して下段に置き換えた(並び換えた)ものを
置換という。
置き換えの操作のことも
置換という。
上の例は「1➝1」、「2➝3」、「3➝4」、「4→2」という置き換わりです。
・「1➝1」は置換がないから、明記しなくてもよい、上記では\((2\ 3\ 4)\)で表している。(これは後述する巡回置換です。)
重複は許さないので、置き換り方は(並び替え方)は順列になる。
(上の例 n = 4, 置き換り方はn! = 4! = 24通りです)
置換σ によりi がk に置き換えられるとき
置換を記号 \(σ(i)=k\) で表わす
\(i:\)上段の数 \(k:\)下段の数
次の3列目の置換(3➝1)は:
\(σ(i)=k\)\(\ \Rightarrow\ \)\(\color{blue}{σ(3)=1}\)
具体的に書くと:
\(σ=\)
\(\begin{pmatrix}
1 & 2 & 3 & \\
\color{blue}{σ(1)} & \color{blue}{σ(2)} & \color{blue}{σ(3)}
\end{pmatrix}\)
\(=\begin{pmatrix}
1 & 2 & 3 & \\
\color{blue}{3} & \color{blue}{2} & \color{blue}{1}
\end{pmatrix}\)
の置換だから
\( \quad \quad \quad \downarrow\)
\(\underline{ \color{blue}{σ(1)=3,\ σ(2)=2,\ σ(3)=1} }\)
と書ける。
また以下の置換は等しい
\(\begin{pmatrix}
2 & 1 & 3 \\
3 & 2 & 1
\end{pmatrix}\)
\(=\begin{pmatrix}
1 & 3 & 2 \\
2 & 1 & 3
\end{pmatrix}\)
置換は上段と下段の数の対応なので列を入れ換えても同じである。
上段は左に向かって昇順(1,2…n)が見易い。
2.恒等置換I(identity permutation)
一般的な表記で表すと:
\(\begin{pmatrix}
1 & 2 & \cdots & n \\
c_1 & c_2 & \cdots & c_n
\end{pmatrix}\)
に対し
\(\begin{pmatrix}
1 & 2 & \cdots & n \\
1 & 2 & \cdots & n
\end{pmatrix}=I\)
のように数の
入れ替えのないものを
恒等置換という。(単位置換ともいう)
すなわち 1,2…n の任意の数 i について:
\(\color{blue}{σ(i)=i}\) である置換が恒等置換である。
3.互 換
次のように2つだけを置き換えた置換のことを
互換という。(他の数はそのまま)
\( σ=
\underbrace{
\begin{pmatrix}
\underline{1} & 2 & 3 & \underline{4} \\
\underline{4} & 3 & 2 & \underline{1}
\end{pmatrix}
}_{全置換表記}
\)
\(=\underbrace{\color{red}{(1,4)}=\color{red}{(4,1)}}_{簡易表記}\)
この互換は単に(1,4)と書く。((4,1)でも同じ)
ここでは左側の表記を「
全置換表記」、右側を「
簡易表記」ということにします。
4.巡回置換(cyclic permutation)
\( σ=\begin{pmatrix}
1 & \underline{2} & \underline{3} & \underline{4} \\
1 & \underline{3} & \underline{4} & \underline{2}
\end{pmatrix}\)
\(=(2,3,4)\)
「2→3」、「3→4」、「4→2」の最後「4→2」は「2」に戻っている。
上記を置換記号で表すと:
\(σ(2)=3, σ(3)=4, σ(4)=2 \)
この置換を巡回置換といい、(2,3,4)= (3,4,2) と書いてもよい。
・巡回置換から右まわりで読む/書く。
・置換の数が
3個以上で元に戻る置換を巡回置換
(別表現:巡回する数が3個以上)
・
互換は置換の数が2個で元に戻る
巡回置換でもある。
5.置換の積(product of permutation)
一般の「掛け算の操作」ではなく、2つの置換の積とは「置換を2回行う操作」である。
先に置換の積の性質を述べておきます。
置換の積
\(σ_2 \color{red}{σ_1}\) の場合
(1)積の操作は
右側の\(σ_1\)を先に置換し、次に左側の\(σ_2\)の置換を行う。
この逆、すなわち交換法則は成り立たない。
\(σ_2 σ_1 \ne σ_1 σ_2\)
(2)結合法則は成り立ちます。
\(σ_3 (σ_2 σ_1)\)=\((σ_3 σ_2) σ_1\)
【例題】置換の積
積の演習も兼ねて
\(σ_2 σ_1\)と\(σ_1 σ_2\)の2通りを求め、交換法則がきかないことを確認しましょう。
\(σ_2=\begin{pmatrix}
1 & 2 & 3 & 4 \\
4 & 1 & 2 & 3
\end{pmatrix}\)
\(σ_1=\begin{pmatrix}
1 & 2 & 3 & 4 \\
2 & 4 & 3 & 1
\end{pmatrix}\)
1)積\( \underline{ σ_2 σ_1 = σ_2 (σ_1)} \):
次の1行目だけ説明すると:
\(σ_1\)の1 が2 に置き換り、2 は\(σ_2\)によって1に置き換わる。
\(\color{red}{1 -σ_1\to 2 -σ_2\to 1}\)
\(2 -σ_1\to 4 -σ_2\to 3\)
\(3 -σ_1\to 3 -σ_2\to 2\)
\(4 -σ_1\to 1 -σ_2\to 4\)
\(σ_2 σ_1\)=\(σ_2 (σ_1) \)
\(=\begin{pmatrix}
1 & 2 & 3 & 4 \\
1 & 3 & 2 & 4
\end{pmatrix}\)\(=(2,3)\)
1)の別解:積の記号 \(σ(i)=k\) により求める
\(\color{blue}{σ_2 (σ_1(1))}\)を説明しよう
・まず\(σ_1(1):\)\(-σ_1 \to\)\(σ_1(1)=2\)
\(\quad σ_2 (σ_1(1))=σ_2(2)\)
・積\(σ_2(2):\)\(-σ_2 \to σ_2(2)=1\)
\(\therefore \color{blue}{σ_2 (σ_1(\u{1)})=\u{1} }\)
同様にして:
・\(σ_2 (σ_1(\u{2}))=σ_2 (4)=\u{3}\) ・\(σ_2 (σ_1(\u{3}))=σ_2 (3)=\u{2}\) ・\(σ_2 (σ_1(\u{4}))=σ_2 (1)=\u{4}\)
これらをまとめて書けば、同じ結果が得られる。
2)積\( \underline{ σ_1 σ_2 = σ_1 (σ_2)} \):
\(1 -σ_2\to 4 -σ_1\to 1\)
\(2 -σ_2\to 1 -σ_1\to 2\)
\(3 -σ_2\to 2 -σ_1\to 4\)
\(4 -σ_2\to 3 -σ_1\to 3\)
\(σ_1 σ_2\)=\(σ_1 (σ_2) \)
\(=\begin{pmatrix}
1 & 2 & 3 & 4 \\
1 & 2 & 4 & 3
\end{pmatrix}\)\(=(3,4)\)
従って
\( σ_2 σ_1 = σ_2 (σ_1) \neq σ_1 σ_2 = σ_1 (σ_2) \)
となり
•置換の積に交換法則は成り立ちません。
6.互換の積
さっそく、
(2,3)(2,5)の互換の積を求めてみましょう
互換の積では「簡易表記」して計算操作するのが一般的です。
どんな操作するか説明します。
まず、この互換にない数はそのまま(置換なし)、また今回は最大値が5 なので5次の置換です。
\(σ_2=(2,3), \quad σ_1=(\underline{2},5)\)とおくと:
初めに右側の\(σ_1\)の「2」から始める
❶\(2 \xrightarrow{σ_1 により} 5 \xrightarrow{σ_2 により}5\)
❷\(5 \xrightarrow{σ_1 により} 2 \xrightarrow{σ_2 により}3\)
❸\(3 \xrightarrow{σ_1 により} 3 \xrightarrow{σ_2 により}2\)
置換のない数は省略しています、
詳細は下記
(※1)を参照
この結果をまとめると:
\(
σ=\begin{pmatrix}
1 & \u{2} & \u{3} & 4 & \u{5} \\
1 & \u{5} & \u{2} & 4 & \u{3}
\end{pmatrix}
\) \(=(2,5,3)\)
巡回置換
すなわち、互換の積が巡回置換になる。
\(σ_2 σ_1=(2,3)(2,5)=(2,5,3)\)
これを一般化すると:
\((a_1,a_2,a_3)=(a_1,a_3)(a_1,a_2)\)\(\ :❶\)
(※1)詳細説明
\(σ_1\)と\(σ_2\)に表記がない数は置換がないからそのままである。
①「1」は\(σ_1\)により,そのまま「1」、その「1」は\(σ_2\)により,そのまま「1」。
②「2」は\(σ_1\)により,「5」、「5」は\(σ_2\)により,そのまま「5」。
③「3」は\(σ_1\)により,そのまま「3」、その「3」は\(σ_2\)により,「2」。
④「4」は\(σ_1\)により,そのまま「4」、その「4」は\(σ_2\)により,そのまま「4」。
⑤「5」は\(σ_1\)により,「2」に、「2」は\(σ_2\)により,「3」。
➁と④は置換のない数だから、上では省略してます。
7.置換の積と結合法則
置換の積には交換法則は成り立たないが、
結合法則は成り立ちます。
まず計算して確認しましょう。
次の互換の積を求める。
\(σ_3 σ_2 σ_1=(1,2)(1,4)(1,5)\)とする。
\(σ_3(σ_2 σ_1)\)
と
\((σ_3σ_2)σ_1\)
の2通りで求める。
注:括弧()が異なるが、右側の置換からはじまるのは変わらない。
この2つが等しければ結合法則が適用できることになる。
(結合法則とは
\(a \x (b \x c)=(a \x b) \x c\) のこと。)
1)\( σ_3(σ_2 σ_1)=(1,2)\color{red}{ ((1,4)(1,5))} \)
\( \color{red}{(1,4)(1,5)=(1,5,4)}\)
\(
=\begin{pmatrix}
\u{1} & 2 & 3 & \u{4} & \u{5} \\
\u{5} & 2 & 3 & \u{1} & \u{4}
\end{pmatrix}
\)
\((1,2)\color{red}{(1,5,4)}\)
\(=(1,2)
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
5 & 2 & 3 & 1 & 4
\end{pmatrix}
\)
\(
=\begin{pmatrix}
\u{1} & \u{2} & 3 & \u{4} & \u{5} \\
\u{5} & \u{1} & 3 & \u{2} & \u{4}
\end{pmatrix}
\)
\(=(1,5,4,2)\)
\((1,5,4,2)=(1,2)(1,5,4)\)\(=(1,2)(1,4)(1,5)\) \( ⓐ \)
2)\( (σ_3σ_2)σ_1=\color{red}{(1,2)(1,4))}(1,5)\)
\( \color{red}{(1,2)(1,4)=(1,4,2)}\)
\(
=\begin{pmatrix}
\u{1} & \u{2} & 3 & \u{4} & 5 \\
\u{4} & \u{1} & 3 & \u{2} & 5
\end{pmatrix}
\)
\(\color{red}{(1,4,2)}(1,5)\)
\(=
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
4 & 1 & 3 & 2 & 5
\end{pmatrix}
\) \((1,5)\)
\(
=\begin{pmatrix}
\u{1} & \u{2} & 3 & \u{4} & \u{5} \\
\u{5} & \u{1} & 3 & \u{2} & \u{4}
\end{pmatrix}
\)
\(=(1,5,4,2)\)
\((1,5,4,2)=(1,4,2)(1,5)=(1,2)(1,4)(1,5)\)
1)と2)の結果より
•置換の積に結合法則が成り立ちます。
8.巡回置換と互換の積
以下に\(n\)個の数の巡回置換は\(n-1\)個の互換の積になることを説明します。
上記で求めた式:
\((1,5,4,2)=(1,2)(1,5,4)=(1,2)(1,4)(1,5)\) \(\ ⓐ \)
この式を一般化すると、4個の巡回置換は:
\((a_1,a_2,a_3,a_4)=(a_1,a_4)(a_1,a_2,a_3)=(a_1,a_4)(a_1,a_3)(a_1,a_2)\) \(\ ❷ \)
また前記の式❶:
\((a_1,a_2,a_3)=(a_1,a_3)(a_1,a_2)\)\(\ :❶\)
式❶❷より
•\(n\)個の巡回置換は\(n-1\)個の互換の積になる
\((a_1,a_2,\cdots,a_n)=(a_1,a_4)(a_1,a_2,a_3)=(a_1,a_n)(a_1,a_{n-1}) \cdots (a_1,a_2)\) \(\ ❸ \)
また、
•任意の置換はいくつかの互換の積に書き換えられる
次回は置換の続きとして符号について学びます。