前回の記事では正方行列の行列式の直感的なイメージを説明し
- $A$が正則行列であること
- $|A|\neq0$をみたすこと
が同値となりそうなことをみました(このことはのちの記事で証明します).
前回の記事では2次正方行列に対してのみ行列式をきちんと定義しましたが,一般の$n$次正方行列の行列式を定義には置換を用います.
置換を用いない定義もありますが,多くの教科書では置換により行列式が定義されています.
この記事では
- 置換の定義
- 重要な置換
を順に説明します.
「線形代数学の基本」の一連の記事
- 行列と列ベクトル
- 行列式
- $\R^n$の部分空間と基底
置換
この記事では,$n$を2以上の整数,$M_{n}$を集合$\{1,2,\dots,n\}$とします.
具体例
まずはざっくりと具体例から置換の考え方を理解しましょう.
置換とは平たく言えば「並べ替える操作」のことをいい,例えば$1,2,3,4$を
と並べ替える操作も置換のひとつで,この並べ替えを$\pmat{1&2&3&4\\2&3&4&1}$と表します.
他にも$1,2,3,4,5$を
と並べ替える操作は$\pmat{1&2&3&4&5\\2&1&4&3&5}$と表します.この置換では$5$が不変ですが,このようなものも置換といいます.
一般に$\{1,2,\dots,n\}$を並べ替える操作を$\{1,2,\dots,n\}$の置換といいます.
置換はギリシャ文字の小文字$\sigma$, $\tau$を用いて表されることが多いです.
置換の定義
いま具体例でみた置換を一般に定義するなら,次のように全単射という言葉を用いることになりますが,直感的には上のような並べ替えとして理解していればこの一連の記事では大きな問題ありません.
$M_n=\{1,2,\dots,n\}$とする.全単射$\sigma:M_n\to M_n$を$M_{n}$上の置換 (permutation)といい,
と表し,$M_{n}$上の置換全体の集合を$S_{n}$と表す.
例えば,$\sigma\in S_3$, $\tau\in S_4$を$\sigma=\pmat{1&2&3\\2&3&1}$, $\tau=\pmat{1&2&3&4\\4&3&2&1}$で定めると,
というわけですね.
また,恒等写像$M_n\to M_n$を単位置換や恒等置換などといいます.
例えば単位置換$\epsilon\in S_5$は$\epsilon=\pmat{1&2&3&4&5\\1&2&3&4&5}$と表せますね.
置換の積
$\sigma,\tau\in S_{n}$に対して,写像の合成$\sigma\circ\tau$を$\sigma$と$\tau$の積 (product)といい,$\sigma\cdot\tau$や$\cdot$を省略して$\sigma\tau$と表す.
$\sigma,\tau\in S_3$を$\sigma=\pmat{1&2&3\\2&1&3}$, $\tau=\pmat{1&2&3\\3&1&2}$で定めると,
なので$\sigma\tau=\pmat{1&2&3\\3&2&1}$であり,
なので$\tau\sigma=\pmat{1&2&3\\1&3&2}$ですね.
この例からも分かるように,一般に置換の積は可換とは限りません.
$\sigma\in S_{n}$に対して$\sigma$の逆写像を逆置換 (inverse permutation)といい$\sigma^{-1}$で表す.
例えば,$\sigma=\pmat{1&2&3\\2&3&1}\in S_{3}$, $\tau=\pmat{1&2&3&4\\4&3&2&1}\in S_{4}$に対して,
ですね.
以上より$S_n$は非可換群となります.この群は群論でも重要な群で$n$次対称群と呼ばれます.群については以下の記事を参照してください.
重要な置換
次に置換の中でも重要な置換を説明していきます.
巡回置換
例えば,置換$\pmat{1&2&3&4\\2&3&1&4}$は$1\to2\to3\to1$と$\{1,2,3\}$を巡回させ,$4$を動かさない置換となっています.
このような一部だけを巡回させる置換を巡回置換といいます.
$S_{n}$の元のうち
の形の置換を巡回置換 (cyclic permutation)といい,$(k_1,k_2,\dots,k_r)$と表す.
例えば,巡回置換$\sigma=(1,2,4)\in S_{6}$は,
です.つまり,$\sigma=(1,2,4)$は$1,2,4$をこの順に1つずつずらし,$3,5,6$を変えない置換ですね.
巡回置換$\sigma,\tau\in S_{n}$が同じものを巡回させないとき,$\sigma\tau=\tau\sigma$が成り立つ.
もう少しきちんと書くと,「巡回置換$\sigma=(m_{1},\dots,m_{k}),\tau=(m_{1}’,\dots,m_{\ell}’)\in S_{n}$に対して,$\{m_{1},\dots,m_{k}\}\cap\{m_{1}’,\dots,m_{\ell}’\}=\emptyset$なら$\sigma\tau=\tau\sigma$が成り立つ」ということですね.
一般に集合$X$を定義域とする写像$f$, $g$が等しいとは,任意の$x\in X$に対して$f(x)=g(x)$が成り立つことをいうのでした.
置換も写像でしたから,$\sigma\tau=\tau\sigma$が成り立つとは,任意の$m\in M_n$に対して$\sigma\tau(m)=\tau\sigma(m)$が成り立つということですね.
$\sigma=(m_{1},\dots,m_{k})$, $\tau=(m_{1}’,\dots,m_{\ell}’)$とする.
任意の$m\in M_{n}$に対して,
- $m\in\{m_{1},\dots,m_{k}\}$のとき,条件から$\tau$は$m$, $\sigma(m)$を巡回させないから
- $m\in\{m_{1}’,\dots,m_{\ell}’\}$のとき,同様に$\sigma\tau(m)=\tau\sigma(m)$
- $m\notin\{m_{1},\dots,m_{k},m_{1}’,\dots,m_{\ell}’\}$のとき
が成り立つ.よって,任意の$m\in M_{n}$に対して$\sigma\tau(m)=\tau\sigma(m)$が成り立つから,$\sigma\tau=\tau\sigma$が従う.
例えば,$\sigma\in S_{8}$を
で定めます.この$\sigma$は以下のように巡回置換の積で表すことができます.
- まず1に繰り返し$\sigma$を施すと,$1\to3\to4\to1$と巡回する.
- $1,3,4$でない$M_{8}$の元,例えば$2$に繰り返し$\sigma$を施すと,$2\to6\to5\to2$と巡回する.
- $1,3,4,2,5,6$でない$M_{8}$の元,例えば$7$に繰り返し$\sigma$を施すと,$7\to8\to7$と巡回する.
このように考えれば,$\sigma=(1,3,4)(2,5,6)(7,8)$として巡回置換の積で表されます.
また,上の命題より$\sigma$をなす巡回置換$(1,3,4)$, $(2,5,6)$, $(7,8)$は入れ替えても等しいですね:
この例から次の定理が成り立つことが分かりますね.
任意の$\sigma\in S_{n}$は同じものを巡回させない巡回置換の積で表せる.
互換
ちょうど2つの元を巡回させる巡回置換を互換 (transposition)という.
$i,j$を入れ替える互換は,$i,j$を巡回させる巡回置換なので$(i,j)$と表せますね.
次は巡回置換と互換の積を結び付ける重要な命題です.
$S_{n}$の任意の巡回置換は$S_{n}$の互換の積で表せる.
任意の巡回置換$\sigma=(m_{1},\dots,m_{k})\in S_{n}$を考える.
このとき,$\sigma$が互換$\tau_{i}:=(m_{1},m_{i})$ $(i=2,3,\dots,k)$の積で$\sigma=\tau_{k}\dots\tau_{3}\tau_{2}$と表せることを以下で示す.
任意の$m\in\{1,\dots,k\}$に対して,
- $i\in\{1,\dots,k-1\}$のとき
- $i=k$のとき
- $i\notin\{1,\dots,k\}$のとき
が成り立つ.
よって,任意の$m\in M_{n}$に対して$\sigma(m)=\tau_{k}\dots\tau_{3}\tau_{2}(m)$が成り立つから,$\sigma=\tau_{k}\dots\tau_{3}\tau_{2}$が従う.
例えば,巡回置換$\sigma=(1,2,3,4)$は互換の積として,
などと表せますね.
ここまでで
- 全ての置換は巡回置換の積で表せる
- 巡回置換は互換の積で表せる
が成り立つことが分かりましたから次が従いますね.
$S_{n}$の任意の置換は$S_{n}$の互換の積で表せる.
コメント