置換行列のソースを表示

[[File:Symmetric group 3; Cayley table; matrices.svg|thumb|320px|三文字の置換を記述する行列。<br /> 二つの置換行列の[[行列の積|積]]もまた置換行列である。<br /><br />六種類それぞれの同じ型の行列が以下のような位置に存在している:<br>[[File:Symmetric group 3; Cayley table; positions.svg|310px|三次対称群の乗積表]]<br />(これらもまた置換行列)]]
[[数学]]の特に[[線型代数学|行列論]]における'''置換行列'''（ちかんぎょうれつ、{{lang-en-short|''permutation matrix''}}）は、各行各列にちょうど一つだけ {{math|1}} の要素を持ち、それ以外は全て {{math|0}} となるような{{仮リンク|二値行列|en|binary matrix|label=二値}}[[正方行列]]を言う。そのような {{mvar|m}}-次正方行列の各々は、特定の {{mvar|m}} 文字の置換を表現するもので、右または左からの行列の積によって列または行の置換を引き起こす。

== 定義 ==
{{mvar|m}} 文字の置換:
: <math>\pi\colon \lbrace 1, \ldots, m \rbrace \to \lbrace 1, \ldots, m \rbrace</math>
あるいは二行記法で書けば 
: <math>\begin{bmatrix} 1 & 2 & \cdots & m \\ \pi(1) & \pi(2) & \cdots & \pi(m) \end{bmatrix}</math>
が与えられたとき、対応する置換行列（{{mvar|m}}-次元列ベクトルに作用するもの）は、{{math|'''e'''{{ind|''j''}}}} を {{mvar|j}}-番目の成分が {{math|1}}, それ以外の成分が {{math|0}} の行ベクトルと定義して 
: <math>P_\pi = \begin{bmatrix} \mathbf e_{\pi(1)} \\ \mathbf e_{\pi(2)} \\ \vdots \\ \mathbf e_{\pi(m)} \end{bmatrix}</math>
で与えられる {{math|{{gaps|''m''|×|''m''}}}}-行列 {{mvar|P{{msub|π}}}} を言う<ref name=Bru2>Brualdi (2006) p.2</ref>。これは、各 {{mvar|i}} について {{math|(''i'', ''π''(''i''))}}-成分のみが例外的に {{math|1}} で、ほかの成分は全て {{math|0}} になる。

== 性質 ==
{{mvar|m}} 文字の置換 {{mvar|π, σ}} が与えられたとき、対応する（列ベクトルに作用する）置換行列 {{mvar|P{{msub|π}}, P{{msub|σ}}}} の積は、置換の合成に対応する置換行列に等しい。つまり
: <math>P_{\sigma} P_{\pi}  = P_{\sigma\circ\pi}</math>
が成り立つ。ただし、置換行列との対応を行ベクトルに対する作用に関して定める（つまり、{{math|1=''P''{{msub|π}} {{coloneqq}} (''δ''{{msub|''i'',''π''(''j'')}})}}）ならば、積の規則は反変的に、つまり
: <math> P_{\sigma} P_{\pi}  = P_{\pi\circ\sigma}</math>
になる。置換行列は[[直交行列]]、つまり {{math|1=''P{{msub|π}}P{{msub|π}}''{{msup|⊤}} = ''I''}} ゆえ、逆行列は
: <math>P_{\pi}^{-1} = P_{\pi^{-1}} = P_{\pi}^{\top}</math>
で得られる。{{mvar|P{{msub|π}}}} を[[列ベクトル]] {{math|'''g'''}} に左から掛けるとベクトルに対する行の置換を引き起こす:
:<math>P_\pi \mathbf{g}= \begin{bmatrix}\mathbf{e}_{\pi(1)} \\\mathbf{e}_{\pi(2)} \\\vdots \\\mathbf{e}_{\pi(n)}\end{bmatrix}\begin{bmatrix}g_1 \\g_2 \\\vdots \\g_n\end{bmatrix}= \begin{bmatrix}g_{\pi(1)} \\g_{\pi(2)} \\\vdots \\g_{\pi(n)}\end{bmatrix} </math>

[[行ベクトル]] {{math|'''h'''}} に{{mvar|P{{msub|π}}}} を右から掛けるとベクトルに対する列の置換を引き起こす:
: <math>\mathbf{h}P_\pi= \begin{bmatrix} h_1 & h_2 & \ldots & h_n \end{bmatrix}\begin{bmatrix}\mathbf{e}_{\pi(1)} \\\mathbf{e}_{\pi(2)} \\\vdots \\\mathbf{e}_{\pi(n)}\end{bmatrix}=\begin{bmatrix} h_{\pi^{-1}(1)} & h_{\pi^{-1}(2)} & \ldots & h_{\pi^{-1}(n)} \end{bmatrix} </math>
ゆえに、ふたたび {{math|1=('''h'''''P{{msub|σ}}'')''P{{msub|π}}'' = '''h'''''P{{msub|π∘σ}}''}} が確認される。

== 注意 ==
[[対称群]] {{mvar|S{{msub|n}}}}, すなわち {{math|{{mset|1, 2, …, ''n''}}}} 上の置換群は、{{math|''n''!}} 個の置換を含むから、置換行列も同じだけある。上で見たことから、置換行列の全体は行列の積に関して[[単位行列]]を単位元とする[[群 (数学)|群]]を成すことがわかる。恒等置換を {{math|(1)}} と書けば、{{math|''P''{{msub|(1)}}}} は[[単位行列]] {{mvar|I}} である。

置換 {{mvar|σ}} に対する置換行列を、単位行列 {{mvar|I}} の行置換 {{mvar|σ}} と看做すこともできるし、{{mvar|I}} の列置換 {{math|''σ''{{exp|&minus;1}}}} と見ることもできる。

置換行列は[[二重確率行列]]である。バーコフ&ndash;フォンノイマンの定理の述べるところによれば、任意の二重確率実行列が同じサイズの置換行列の[[凸結合]]に書け、また置換行列は二重確率行列全体の成す集合の[[極点]]にちょうどなっている。つまり、{{仮リンク|バーコフ多面体|en|Birkhoff polytope}}（二重確率行列全体の成す集合）は置換行列全体の成す集合の[[凸包]]である<ref name=Bru19>Brualdi (2006) p.19</ref>。

行列 {{mvar|M}} に対する置換行列 {{mvar|P}} の左乗 {{mvar|PM}} は、{{mvar|M}} の行を置換する（つまり、第 {{mvar|i}}-行は第 {{math|''π''(''i'')}}-行へ写る）。同様に右乗 {{mvar|MP}} は {{mvar|M}} の列を置換する。

写像 {{math|''S{{msub|n}}'' &rarr; ''A'' &sub; GL(''n'', '''Z'''{{msub|2}})}} は[[忠実表現]]であり、従って {{math|1={{abs|''A''}} = ''n''!}} が成り立つ。

置換行列の[[跡 (線型代数学)|トレース]]は、対応する置換の不動点の数に等しい。実際、置換 {{mvar|π}} が不動点を持てば、巡回置換分解 {{math|1=''π'' = (''a''{{ind|1}})(''a''{{ind|2}})⋯(''a{{ind|k}}'')''σ''}} で {{mvar|σ}} が不動点を持たないようなものが取れて、そのとき {{math|'''e'''{{msub|''a''{{ind|1}}}}, '''e'''{{msub|''a''{{ind|2}}}}, …, '''e'''{{msub|''a{{ind|k}}''}}}} は対応する置換行列の[[固有ベクトル]]。

[[群論]]で知られた事実として、任意の置換は[[互換 (数学)|互換]]の積に書けるから、従って任意の置換行列は二つの行を入れ替える[[基本行列]]（何れも行列式 {{math|&minus;1}} を持つ）の積に書くことができる。ゆえに、置換行列の行列式は対応する置換の[[置換の符号|符号]]に等しい。

== 関連項目 ==
* {{仮リンク|交代符号行列|en|Alternating sign matrix}}
* [[一般化置換行列]]

== 参考文献 ==
{{reflist}}
* {{cite book | last=Brualdi | first=Richard A. | title=Combinatorial matrix classes | series=Encyclopedia of Mathematics and Its Applications | volume=108 | location=Cambridge | publisher=[[Cambridge University Press]] | year=2006 | isbn=0-521-86565-4 | zbl=1106.05001 }}

{{Linear algebra}}

{{Normdaten}}
{{DEFAULTSORT:ちかんきようれつ}}
[[Category:行列]]
[[Category:置換]]
[[Category:数学に関する記事]]