数学の特に行列論における置換行列(ちかんぎょうれつ、英: permutation matrix)は、各行各列にちょうど一つだけ 1 の要素を持ち、それ以外は全て 0 となるような二値(英語版)正方行列を言う。そのような m-次正方行列の各々は、特定の m 文字の置換を表現するもので、右または左からの行列の積によって列または行の置換を引き起こす。 m 文字の置換: π : { 1 , … , m } → { 1 , … , m } {\displaystyle \pi \colon \lbrace 1,\ldots ,m\rbrace \to \lbrace 1,\ldots ,m\rbrace } あるいは二行記法で書けば [ 1 2 ⋯ m π ( 1 ) π ( 2 ) ⋯ π ( m ) ] {\displaystyle {\begin{bmatrix}1&2&\cdots &m\\\pi (1)&\pi (2)&\cdots &\pi (m)\end{bmatrix}}} が与えられたとき、対応する置換行列(m-次元列ベクトルに作用するもの)は、ej を j-番目の成分が 1, それ以外の成分が 0 の行ベクトルと定義して P π = [ e π ( 1 ) e π ( 2 ) ⋮ e π ( m ) ] {\displaystyle P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (m)}\end{bmatrix}}} で与えられる m×m-行列 Pπ を言う[1]。これは、各 i について (i, π(i))-成分のみが例外的に 1 で、ほかの成分は全て 0 になる。 m 文字の置換 π, σ が与えられたとき、対応する(列ベクトルに作用する)置換行列 Pπ, Pσ の積は、置換の合成に対応する置換行列に等しい。つまり P σ P π = P σ ∘ π {\displaystyle P_{\sigma }P_{\pi }=P_{\sigma \circ \pi }} が成り立つ。ただし、置換行列との対応を行ベクトルに対する作用に関して定める(つまり、Pπ ? (δi,π(j)))ならば、積の規則は反変的に、つまり P σ P π = P π ∘ σ {\displaystyle P_{\sigma }P_{\pi }=P_{\pi \circ \sigma }} になる。置換行列は直交行列、つまり PπPπ? = I ゆえ、逆行列は P π − 1 = P π − 1 = P π ⊤ {\displaystyle P_{\pi }^{-1}=P_{\pi ^{-1}}=P_{\pi }^{\top }} で得られる。Pπ を列ベクトル g に左から掛けるとベクトルに対する行の置換を引き起こす: P π g = [ e π ( 1 ) e π ( 2 ) ⋮ e π ( n ) ] [ g 1 g 2 ⋮ g n ] = [ g π ( 1 ) g π ( 2 ) ⋮ g π ( n ) ] {\displaystyle 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}}} 行ベクトル h にPπ を右から掛けるとベクトルに対する列の置換を引き起こす: h P π = [ h 1 h 2 … h n ] [ e π ( 1 ) e π ( 2 ) ⋮ e π ( n ) ] = [ h π − 1 ( 1 ) h π − 1 ( 2 ) … h π − 1 ( n ) ] {\displaystyle \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}}} ゆえに、ふたたび (hPσ)Pπ = hPπ?σ が確認される。 対称群 Sn, すなわち {1, 2, …, n} 上の置換群は、n! 個の置換を含むから、置換行列も同じだけある。上で見たことから、置換行列の全体は行列の積に関して単位行列を単位元とする群を成すことがわかる。恒等置換を (1) と書けば、P(1) は単位行列 I である。 置換 σ に対する置換行列を、単位行列 I の行置換 σ と看做すこともできるし、I の列置換 σ−1 と見ることもできる。 置換行列は二重確率行列である。バーコフ–フォンノイマンの定理の述べるところによれば、任意の二重確率実行列が同じサイズの置換行列の凸結合に書け、また置換行列は二重確率行列全体の成す集合の極点にちょうどなっている。つまり、バーコフ多面体 行列 M に対する置換行列 P の左乗 PM は、M の行を置換する(つまり、第 i-行は第 π(i)-行へ写る)。同様に右乗 MP は M の列を置換する。 写像 Sn → A ⊂ GL(n, Z2) は忠実表現であり、従って |A| = n! が成り立つ。 置換行列のトレースは、対応する置換の不動点の数に等しい。実際、置換 π が不動点を持てば、巡回置換分解 π = (a1)(a2)?(ak)σ で σ が不動点を持たないようなものが取れて、そのとき ea1, ea2, …, eak は対応する置換行列の固有ベクトル。
定義
性質
注意