置換行列

三文字の置換を記述する行列。
二つの置換行列の積もまた置換行列である。

六種類それぞれの同じ型の行列が以下のような位置に存在している:

(これらもまた置換行列)

数学の特に行列論における置換行列（ちかんぎょうれつ、テンプレート:Lang-en-short）は、各行各列にちょうど一つだけ テンプレート:Math の要素を持ち、それ以外は全て テンプレート:Math となるようなテンプレート:仮リンク正方行列を言う。そのような テンプレート:Mvar-次正方行列の各々は、特定の テンプレート:Mvar 文字の置換を表現するもので、右または左からの行列の積によって列または行の置換を引き起こす。

定義

テンプレート:Mvar 文字の置換:

$\pi :\{1,\dots ,m\}\to \{1,\dots ,m\}$

あるいは二行記法で書けば

$\left[\begin{array}{cccc}1& 2& \cdots & m\\ \pi (1)& \pi (2)& \cdots & \pi (m)\end{array}\right]$

が与えられたとき、対応する置換行列（テンプレート:Mvar-次元列ベクトルに作用するもの）は、テンプレート:Math を テンプレート:Mvar-番目の成分が テンプレート:Math, それ以外の成分が テンプレート:Math の行ベクトルと定義して

$P_{\pi }=\left[\begin{array}{c}{𝐞}_{\pi (1)}\\ {𝐞}_{\pi (2)}\\ ⋮\\ {𝐞}_{\pi (m)}\end{array}\right]$

で与えられる テンプレート:Math-行列 テンプレート:Mvar を言う。これは、各 テンプレート:Mvar について テンプレート:Math-成分のみが例外的に テンプレート:Math で、ほかの成分は全て テンプレート:Math になる。

性質

テンプレート:Mvar 文字の置換 テンプレート:Mvar が与えられたとき、対応する（列ベクトルに作用する）置換行列 テンプレート:Mvar の積は、置換の合成に対応する置換行列に等しい。つまり

$P_{\sigma }{P}_{\pi }=P_{\sigma \circ \pi }$

が成り立つ。ただし、置換行列との対応を行ベクトルに対する作用に関して定める（つまり、テンプレート:Math）ならば、積の規則は反変的に、つまり

$P_{\sigma }{P}_{\pi }=P_{\pi \circ \sigma }$

になる。置換行列は直交行列、つまり テンプレート:Math ゆえ、逆行列は

$P_{\pi }^{-1}=P_{{\pi }^{-1}}=P_{\pi }^{\mathrm{\top }}$

で得られる。テンプレート:Mvar を列ベクトル テンプレート:Math に左から掛けるとベクトルに対する行の置換を引き起こす:

$P_{\pi }𝐠=\left[\begin{array}{c}{𝐞}_{\pi (1)}\\ {𝐞}_{\pi (2)}\\ ⋮\\ {𝐞}_{\pi (n)}\end{array}\right]\left[\begin{array}{c}{g}_1\\ g_2\\ ⋮\\ g_n\end{array}\right]=\left[\begin{array}{c}{g}_{\pi (1)}\\ g_{\pi (2)}\\ ⋮\\ g_{\pi (n)}\end{array}\right]$

行ベクトル テンプレート:Math にテンプレート:Mvar を右から掛けるとベクトルに対する列の置換を引き起こす:

$𝐡P_{\pi }=\left[\begin{array}{cccc}{h}_1& h_2& \dots & h_n\end{array}\right]\left[\begin{array}{c}{𝐞}_{\pi (1)}\\ {𝐞}_{\pi (2)}\\ ⋮\\ {𝐞}_{\pi (n)}\end{array}\right]=\left[\begin{array}{cccc}{h}_{{\pi }^{-1}(1)}& h_{{\pi }^{-1}(2)}& \dots & h_{{\pi }^{-1}(n)}\end{array}\right]$

ゆえに、ふたたび テンプレート:Math が確認される。

注意

対称群 テンプレート:Mvar, すなわち テンプレート:Math 上の置換群は、テンプレート:Math 個の置換を含むから、置換行列も同じだけある。上で見たことから、置換行列の全体は行列の積に関して単位行列を単位元とする群を成すことがわかる。恒等置換を テンプレート:Math と書けば、テンプレート:Math は単位行列 テンプレート:Mvar である。

置換 テンプレート:Mvar に対する置換行列を、単位行列 テンプレート:Mvar の行置換 テンプレート:Mvar と看做すこともできるし、テンプレート:Mvar の列置換 テンプレート:Math と見ることもできる。

置換行列は二重確率行列である。バーコフ–フォンノイマンの定理の述べるところによれば、任意の二重確率実行列が同じサイズの置換行列の凸結合に書け、また置換行列は二重確率行列全体の成す集合の極点にちょうどなっている。つまり、テンプレート:仮リンク（二重確率行列全体の成す集合）は置換行列全体の成す集合の凸包である。

行列 テンプレート:Mvar に対する置換行列 テンプレート:Mvar の左乗 テンプレート:Mvar は、テンプレート:Mvar の行を置換する（つまり、第 テンプレート:Mvar-行は第 テンプレート:Math-行へ写る）。同様に右乗 テンプレート:Mvar は テンプレート:Mvar の列を置換する。

写像 テンプレート:Math は忠実表現であり、従って テンプレート:Math が成り立つ。

置換行列のトレースは、対応する置換の不動点の数に等しい。実際、置換 テンプレート:Mvar が不動点を持てば、巡回置換分解 テンプレート:Math で テンプレート:Mvar が不動点を持たないようなものが取れて、そのとき テンプレート:Math は対応する置換行列の固有ベクトル。

群論で知られた事実として、任意の置換は互換の積に書けるから、従って任意の置換行列は二つの行を入れ替える基本行列（何れも行列式 テンプレート:Math を持つ）の積に書くことができる。ゆえに、置換行列の行列式は対応する置換の符号に等しい。

関連項目

• テンプレート:仮リンク
• 一般化置換行列

参考文献

• テンプレート:Cite book