サイト内検索

あらゆるワードの関連記事を検索できます!

おぐえもん
大学に通う理系学生です♪Webサイトやチラシ、冊子などのデザインや、システム開発などの経験があります。音楽が好きで、渋谷系サウンドが好物です!
たぶん今すぐ使えるテクニックから、きっと全く使えない豆知識まで。

【行列式編】置換と巡回置換

行列式の定義に必要な「置換」という概念についてねっとり説明していきます!!

おぐえもん

本カテゴリ
線形代数解説の定番サイト。大学1年生どころか再履のアホでも分かる丁寧な説明が特長。1年生前期〜後期の授業で学ぶ範囲を扱います。

こんにちは、おぐえもん(@oguemon_com)です。

今回は行列式の定義に使用する「置換」という概念について説明します。今回の記事で「置換」を学んで、次の記事で「互換」と「置換の符号」を学ぶことで、行列式の定義を理解することができるようになります!

互換や、置換の符号について知りたい方へ

互換や、置換の符号は以下の記事で解説しています!
【行列式編】互換と置換の符号

それでは頑張っていきましょう!!

目次(クリックで該当箇所へ移動)

置換とは

置換とは、ある数列のアナグラムのことを言います。

例えば、「1,2,3,4,5」という数列を、「4,3,2,5,1」と並び替え、両者の数字をそれぞれ左から順に「1と4」「2と3」「3と2」「4と5」「5と1」と対応づけると、この対応を5文字の置換と呼ぶわけです。

「1と4」みたいな対応関係を「\(\sigma(1)=4\)」と表し、さらには、この対応を
$$\sigma=\left(
\begin{array}{ccccc}
1&2&3&4&5 \\
4&3&2&5&1
\end{array}
\right)$$とまとめます。上の段が先ほどの「1,2,3,4,5」で、下の段がその並び替えの「4,3,2,5,1」であることが分かりますよね?

ある列の上下の数字をペアとして捉えることがこの表記を扱う上の基本です。例えば、3列目は「\(\sigma(3)=2\)」を表します。そして、上下の数字の組み合わせさえ合っているならば、列を好きに入れ替えても問題ありません。

ちなみに、行列っぽい見た目ですが、行列とは別物です!!

置換について抽象的にまとめると以下のようになります。

置換

\(n\)個の要素\(1,2,\cdots,n\)を適当な順番に並べた\(p_1,p_2,\cdots,p_n\)について、\(i\)と\(p_i\)の対応づけを\(\sigma(i)=p_i \ (i=1,2,\cdots,n)\)と表し、これらをまとめて
$$\sigma=\left(
\begin{array}{cccc}
1&2&\cdots&n \\
p_1&p_2&\cdots&p_n
\end{array}
\right)$$と表す。

\(n\)文字の置換は全部で\(n!\)パターンあることは、高校生以上の方なら分かるはずですよね!?(だって置換の総数は、並び替えの総パターン数ですから)

また、ある列に同じ数字が並ぶこと(同じ数字が上下に対応すること)がありますが、そのような列は基本的に省略して記します。

【例】\(1,2,3,4 \rightarrow 2,4,3,1\)のとき
$$\sigma=\left(
\begin{array}{cccc}
1&2&\underline{3}&4 \\
2&4&\underline{3}&1
\end{array}
\right)=\left(
\begin{array}{ccc}
1&2&4 \\
2&4&1
\end{array}
\right)$$

置換の積

置換の積とは

\(n\)文字の2つの置換\(\sigma,\tau\)が手元にあるとします。このとき、置換\(\sigma\)における\(\sigma(i)\)の値を置換\(\tau\)にそのまま与えることで、「\(i\)と\(\tau(\sigma(i))\)」の対応を考えることができます。

簡単に言えば、2つの置換の対応関係(「A→B」と「B→C」)を3段論法的な感じで1つにギュッとまとめる(「A→C」)感じですね。

さて、「\(i\)と\(\tau(\sigma(i))\)」の対応をまとめたものを、置換\(\sigma\)と置換\(\tau\)の積と言います。記号では\(\tau\sigma\)と書きます。

置換の積

\(i\)と\(\tau(\sigma(i))\)の対応づけを置換\(\sigma\)と置換\(\tau\)の積と言い、両者の積を\(\tau\sigma\)と表す。
$$
\begin{eqnarray}
\tau\sigma&=&\left(
\begin{array}{cccc}
1&2&\cdots&n \\
\tau(1)&\tau(2)&\cdots&\tau(n)
\end{array}
\right)
\left(
\begin{array}{cccc}
1&2&\cdots&n \\
\sigma(1)&\sigma(2)&\cdots&\sigma(n)
\end{array}
\right)\\
&=&\left(
\begin{array}{cccc}
1&2&\cdots&n \\
\tau(\sigma(1))&\tau(\sigma(2))&\cdots&\tau(\sigma(n))
\end{array}
\right)
\end{eqnarray}
$$

置換の積の例

以下の2つの置換
$$\tau=\left(
\begin{array}{ccc}
1&2&3 \\
2&3&1
\end{array}
\right),\sigma=\left(
\begin{array}{ccc}
1&2&3 \\
3&2&1
\end{array}
\right)$$の積\(\tau\sigma\)を考えます。
まず、\(\sigma\)では、1が3に対応しています(\(\sigma(1)=3\))。そして、\(\tau\)では3が1に対応している(\(\tau(3)=1\))ので、積\(\tau\sigma\)では1が\(\tau(\sigma(1))=\tau(3)=1\)と対応することになります。
同様にすると、
$$2 \rightarrow \tau(\sigma(2))=\tau(2)=3\\
3 \rightarrow \tau(\sigma(3))=\tau(1)=2$$となるので、
$$
\begin{eqnarray}
\tau\sigma&=&\left(
\begin{array}{ccc}
1&2&3 \\
2&3&1
\end{array}
\right)
\left(
\begin{array}{ccc}
1&2&3 \\
3&2&1
\end{array}
\right)\\
&=&\left(
\begin{array}{ccc}
1&2&3 \\
1&3&2
\end{array}
\right)\\
&=&\left(
\begin{array}{cc}
2&3 \\
3&2
\end{array}
\right)
\end{eqnarray}
$$となります。簡単に言えば、右の置換の上段から数字を辿って、最終的に行き着く左の置換の下段の数字が、積における対応になります。

置換の積の注意点

置換の積では、行列と同じく、掛け合わせる順序を逆にすれば基本的に答えが変わります

一般に$$\tau\sigma \neq \sigma\tau$$が成立する。(ただし、組み合わせ次第では\(\tau\sigma = \sigma\tau\)のときもある)

先ほどの例で、\(\tau\)と\(\sigma\)の順序を逆にしてみます。
$$
\begin{eqnarray}
\sigma\tau&=&
\left(
\begin{array}{ccc}
1&2&3 \\
3&2&1
\end{array}
\right)
\left(
\begin{array}{ccc}
1&2&3 \\
2&3&1
\end{array}
\right)\\
&=&\left(
\begin{array}{ccc}
1&2&3 \\
2&1&3
\end{array}
\right)\\
&=&\left(
\begin{array}{cc}
1&2 \\
2&1
\end{array}
\right)
\end{eqnarray}
$$先ほどと答えが異なることがわかります。

単位置換と逆置換

まず、同じ数字同士の対応付けしかない置換を単位置換と言います。

単位置換

以下のような置換を単位置換と言う。$$\epsilon=\left(
\begin{array}{cccc}
1&2&\cdots&n \\
1&2&\cdots&n
\end{array}
\right)
$$単位行列は、他の置換と掛けても、積に変化を及ぼしません。$$\epsilon\sigma = \sigma\epsilon = \sigma$$

次に、ある置換の上段と下段を入れ替えた置換を逆置換と言います。

逆置換

以下のような置換を逆置換と言い、\(\sigma^{-1}\)で表す。$$\sigma^{-1}=\left(
\begin{array}{cccc}
\sigma(1)&\sigma(2)&\cdots&\sigma(n) \\
1&2&\cdots&n
\end{array}
\right)
$$逆置換\(\sigma^{-1}\)は、\(\sigma\)と掛け合わせることで単位置換になります。\(\sigma^{-1}\sigma = \sigma\sigma^{-1} = \epsilon\)

巡回置換

ある1つの置換について考えたとき、対応する数字を追っていくと最終的に元の数字にたどり着くことがあります。
例えば、以下の置換$$
\left(
\begin{array}{cccccc}
1&2&3&4&5&6\\
3&5&6&1&2&4
\end{array}
\right)
$$について、
「1と3」「3と6」「6と4」「4と1」という4つの対応関係から「\(1 \rightarrow 3 \rightarrow 6 \rightarrow 4 \rightarrow 1\)」という輪っかが生まれます。
同様にして「\(2 \rightarrow 5 \rightarrow 2\)」という輪っかも見つけられると思います。

このように、同じ置換で対応関係を追うことで\(i\)文字を一巡する置換を、長さ\(i\)の巡回置換と言います。

巡回置換

ある置換\(\sigma\)について、
$$\sigma(i_1)=i_2, \ \sigma(i_2)=i_3 \ \cdots \ \sigma(p_m)=i_1$$という風に対応関係が一巡する置換を長さ\(i\)の巡回置換と言い、
$$(i_1 \ i_2 \ \cdots \ i_m)$$で表す。

先ほどの例で言えば、\((1 \ 3 \ 6 \ 4)\)と\((2 \ 5)\)の2つの巡回置換が置換の中に含まれていたことになります。
またまた新しい記法が登場しちゃいましたが、これは先ほどの記法を1行にしたものと同じです。

$$(1 \ 3 \ 6 \ 4) = \left(
\begin{array}{cccccc}
1&3&6&4 \\
3&6&4&1
\end{array}
\right)$$

1つの置換が複数の巡回置換で構成されているなら、その置換は巡回置換の積で表せられます。
$$\left(
\begin{array}{cccccc}
1&2&3&4&5&6\\
3&5&6&1&2&4
\end{array}
\right)=(1 \ 3 \ 6 \ 4)(2 \ 5)$$

このとき、積として与えられている2つの巡回置換は、構成されている要素が全く異なるので、掛け合わせる順番を逆にしても同じ結果が導かれます。

$$(2 \ 5)(1 \ 3 \ 6 \ 4)=(1 \ 3 \ 6 \ 4)(2 \ 5)$$

ちなみに、どんな置換も、巡回置換の積を用いて表現できることが知られています。

おわりに

今回は、置換の概念について説明し、その中でも重要な「巡回置換」というものを紹介しました。
次の記事では、これに加え「互換」と「置換の符号」というものを説明し、行列式の定義に必要な知識をコンプリートします!!

互換の求め方と置換の符号>>