earth
湘南 理工学舎

 楽しく学ぶ…線形代数

 置換・互換

(permutation・transposition)

 --目 次--

1.置換
2.恒等置換
3.互換
4.巡回置換
5.置換の積
6.逆置換
7.偶置換と奇置換
8.置換の符号
9.その他

 置換はこれから学ぶ行列式、余因子、逆行列などをはじめ、いろんな場面で使われています。

また置換に関係したことがら(用語)が多くあります。混乱しないようにして下さい。

1.置 換 

 まずは置換 σ の例を示します。

\(σ=\begin{pmatrix} 1 & \underline{2} & \underline{3} & \underline{4} \\ 1 & \underline{3} & \underline{4} & \underline{2} \end{pmatrix}\)

上段の1 から4 までの自然数に対して下段に置き換えた(並び換えた)ものを置換という。

置き換えの操作のことも置換という。

上の例は「1➝1」、「2→3」、「3➝4」、「4→2」という置き換わりです。

重複は許さないので、置き換り方は(並び替え方)は順列になる。

(上の例 n = 4, 置き換り方はn! = 4! = 24通りです)

置き換えを \(σ\) とすると上の置換は:

\(σ(1)=1,\ σ(2)=3,\ σ(3)=4\) 

などと表す。 

また次がいえます。
\(\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} =\begin{pmatrix} 2 & 1 & 3 \\ 3 & 2 & 1 \end{pmatrix}\)

置換は上段と下段の数の対応なので列を入れ換えても同じである。

上段は左に向かって昇順が見易い。


2.恒等置換(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}\)

のように数の入れ替えのないものを恒等置換という。(単位置換ともいう)

すなわち 1,2…n の任意の数 i について:

\(σ(i)=i \) である置換が恒等置換である。


3.互 換 

次のように下段の2つだけを置き換えた置換のことを互換という。(他の数はそのまま)

\( σ=\begin{pmatrix} \underline{1} & 2 & 3 & \underline{4} \\ \underline{4} & 3 & 2 & \underline{1} \end{pmatrix}\)

この互換は単に(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」、「3→4」、「4→2」の最後「4→2」は「2」に戻っている。

上記を置換記号で表すと:
\(σ(2)=3, σ(3)=4, σ(4)=2 \)

 この置換を巡回置換といい、(2,3,4) と書く。

・巡回する個数が3個以上が巡回置換

・巡回する個数が2個のときは互換


5.置換の積(product of permutation) 

先に置換の積の性質を述べておきます。

置換の積 \(σ_2 σ_1\) の場合

(1)積の操作はあとに表した\(σ_1\)を先に置換し、次に\(σ_2\)の置換を行う。

この逆、すなわち交換法則は成り立たない。

(2)結合法則は成り立ちます。

\(σ_3 (σ_2 σ_1)\)=\((σ_3 σ_2) σ_1\)


【例題1】置換の積(1)
\(σ_2 σ_1\)と\(σ_1 σ_2\)の2通りを求め、交換法則がきかないことを確認しましょう。

\(σ_1=\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 \end{pmatrix}\)

\(σ_2=\begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \end{pmatrix}\)


(1)積\( \underline{ σ_2 σ_1 = σ_2 (σ_1)} \):
1行目だけ説明すると:
\(σ_1\)の1が2に置き換り、2は\(σ_2\)によって1に置き換わる。
\(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)積\( \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}\)

従って \( σ_2 σ_1 = σ_2 (σ_1) \neq σ_1 σ_2 = σ_1 (σ_2) \)

となり、置換の積は交換法則は成り立たないことが確認できました。

【例題2】置換の積(2)

(2,3)(2,5)の置換の積を求めよ。

これは2つ置換(互換)の積を表しています。

どんな操作するか説明します。

まず、この互換にない数はそのまま(置換なし)、また最大値が5 なので5次の置換です。

\(σ_2=(2,3), \quad σ_1=(2,5)\)とします。

①「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」になる。
この結果をまとめると:
\( σ=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 5 & 2 & 4 & 3 \end{pmatrix} \)


6.逆置換(inverse permutation) 

置換σの上段と下段を入れ換えた置換を逆置換という。

\(σ^{-1}\)で表す。

\( σ=\begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 3 & 2 & 4 \end{pmatrix} \)

\( σ^{-1}=\begin{pmatrix} 1 & 3 & 2 & 4 \\ 1 & 2 & 3 & 4 \end{pmatrix} \)…分かり易く⇒
\(\quad ⇒ \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 3 & 2 & 4 \end{pmatrix} \) …と表記してよい。


•互換\(\ τ\ \)の逆置換\( \ τ^{-1} \ \)は元\( \ τ\ \)に戻る

これを確認しましょう。

\(τ=(1,4) = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 2 & 2 & 1 \end{pmatrix}\)

\(τ^{-1}=(4,1)=(1,4)=τ\) となることを確認すればよいのです。

\(τ=(1,4) = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 2 & 2 & 1 \end{pmatrix}\)

\(τ^{-1} = \begin{pmatrix} 4 & 2 & 3 & 1 \\ 1 & 2 & 2 & 4 \end{pmatrix} \)

\( \quad = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 2 & 2 & 1 \end{pmatrix}\)


7.偶置換と奇置換(even permutation and odd permutation)  

ここで偶置換と奇置換の本題に入る前の準備をします。


互換の積の表現

2つ互換(1,4)(1,2)の積は以下のように操作して演算できる。

\((1,4)(1,2)=σ_2 σ_1 \)とする。
\(σ_1\)の1がに2 に置き換り、2は\(σ_2\)によって2のまま。
(\(σ_2\)に2の表記がないのは置換がないので2-2の対応である)
同様にして演算は以下のとおり。
\(1 -σ_2\to 2 -σ_1\to 2\)

\(2 -σ_2\to 1 -σ_1\to 4\)

\(3 -σ_2\to 3 -σ_1\to 3\)

\(4 -σ_2\to 4 -σ_1\to 1\)

\(σ_2 σ_1 = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 \end{pmatrix}\)

2つの互換の積が次のように巡回置換なりました。

(1,2,4)=(1,4)(1,2)

3つの組の巡回置換が2つの互換置換の積になった。


任意の置換は巡回置換の積で表せる。

\(σ_= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 5 & 6 & 4 & 2 & 1 \end{pmatrix}\)

この置換の中に(1,3,6) と (2,5) の2つの巡回置換があります。

この2つの積(1,3,6)(2,5) は上記の互換の積と同様に行います。

結論は\((1,3,6)(2,5)=σ_2 σ_1 = σ\)となります。

置換の中にある巡回置換の積は元の置換になったわけです。

 巡回置換の互換の積の一般化は以下の通りになる。

\( (c_1, c_2,\cdots ,c_h)=(c_1,c_h)(c_1,c_2,\cdots,c_{h-1}) \)

\( =(c_1,c_h)(c_1,c_{h-1})\cdots(c_1,c_3)(c_1,c_2) \)

巡回置換の対は \(h\) 個、互換の数は \(h-1\) となる。


一般に次のことがいえます。

置換はその中のあるいくつかの巡回置換の積で表せる。

巡回置換 \( (c_1, c_2,\cdots ,c_h)\) は\(h-1\) の互換の積で表せる。

•以上より置換はいくつかの互換の積で表せる。


偶置換と奇置換

 置換の「互換の積」の表し方は一意ではないが(互換の表し方、互換の数が一意でない)

置換を互換の積で表すときに、その積の互換の数が偶数か奇数かは置換によって一意(一通り)に決まる。

互換の数が偶数か奇数によって:

•偶数のとき:偶置換いう。

•奇数のとき:奇置換いう。

上の例として:

\( \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} =(1,2)(1,3) \cdots2コ \)

\(=(1,2)(2,3)(1,3)(1,2)\cdots4コ \)

積の中に互換の数は2 と4 で異なるが、いずれも偶数である。


\( \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix} =(1,3) \cdots1コ \)

\(=(1,2)(2,3)(1,3)\cdots3コ \)

積の中に互換の数は1 と3 で異なるが、いずれも奇数である。


8.置換の符号(+/-)(sign of permutation)  

置換の符号sgnの定義は

置換 \(σ= \begin{pmatrix} 1 & 2 & \cdots & n \\ c_1 & c_2 & \cdots & c_n \end{pmatrix} \)

とすると、次が置換の符号sgnです。

sgnは置換に(+/-)の符号を割りあてている。

\(\begin{eqnarray} \left\{ \begin{array}{l} 偶置換のとき sgn(σ)=+1\\ 奇置換のとき sgn(σ)=-1 \end{array} \right. \end{eqnarray} \)

注:恒等置換は積の互換の数はゼロです。(ゼロは偶数)

ここで次回の講義(3次の正方行列の行列式)のためにも n=3 の置換の符号を求めます。

\(σ_1= \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} ,\) \(σ_2= \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix} \)

\(σ_3= \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix} ,\) \(σ_4= \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} \)

\(σ_5= \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} ,\) \(σ_6= \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix} \)

\(sgn(σ_1)=1\) (\(σ_1\) は恒等置換)

\(sgn(σ_2)=sgn((2,3))=-1 \)

\(sgn(σ_3)=sgn((1,2))=-1 \)

\(sgn(σ_4)=sgn((1,2,3))=+1 \) (互換数(3-1)=2) 

\(sgn(σ_5)=sgn((1,3,2))=+1 \) (互換数(3-1)=2) 

\(sgn(σ_6)=sgn((1,3))=-1 \)


9.その他 

 上記においてn=3 の置換の符号を求めました。

置換は上段の数(または対象)に対し、下段の並び換えた数の「1対1の組」の対応です。

上段が自然数「\((1,2,\cdots n)\)」として、「\( (1, 2, 3)\)」は、\(n=3\)の場合です。

この置換は \( σ_1,σ_2, \cdots,σ_6\) の6通りあり、1つの集合です。

この集合を \( S_3\) といい、n=2 のときは、\( S_2\)といいます。

coffe

[コーヒーブレイク/閑話]…お疲れさまでした