置換行列

数学の特に行列論における置換行列（ちかんぎょうれつ、英: permutation matrix）は、各行各列にちょうど一つだけ 1 の要素を持ち、それ以外は全て 0 となるような二値（英語版）正方行列を言う。そのような m-次正方行列の各々は、特定の m 文字の置換を表現するもので、右または左からの行列の積によって列または行の置換を引き起こす。

定義

m 文字の置換:

${\displaystyle \pi \colon \lbrace 1,\ldots ,m\rbrace \to \lbrace 1,\ldots ,m\rbrace }$

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

${\displaystyle {\begin{bmatrix}1&2&\cdots &m\\\pi (1)&\pi (2)&\cdots &\pi (m)\end{bmatrix}}}$

が与えられたとき、対応する置換行列（m-次元列ベクトルに作用するもの）は、e_j を j-番目の成分が 1, それ以外の成分が 0 の行ベクトルと定義して

${\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_σ の積は、置換の合成に対応する置換行列に等しい。つまり

${\displaystyle P_{\sigma }P_{\pi }=P_{\sigma \circ \pi }}$

が成り立つ。ただし、置換行列との対応を行ベクトルに対する作用に関して定める（つまり、P_π ≔ (δ_i,π(j))）ならば、積の規則は反変的に、つまり

${\displaystyle P_{\sigma }P_{\pi }=P_{\pi \circ \sigma }}$

になる。置換行列は直交行列、つまり P_πP_π^⊤ = I ゆえ、逆行列は

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

で得られる。P_π を列ベクトル g に左から掛けるとベクトルに対する行の置換を引き起こす:

${\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_π を右から掛けるとベクトルに対する列の置換を引き起こす:

${\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_π∘σ が確認される。

注意

対称群 S_n, すなわち {1, 2, …, n} 上の置換群は、n! 個の置換を含むから、置換行列も同じだけある。上で見たことから、置換行列の全体は行列の積に関して単位行列を単位元とする群を成すことがわかる。恒等置換を (1) と書けば、P₍₁₎ は単位行列 I である。

置換 σ に対する置換行列を、単位行列 I の行置換 σ と看做すこともできるし、I の列置換 σ⁻¹ と見ることもできる。

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

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

写像 S_n → A ⊂ GL(n, Z₂) は忠実表現であり、従って |A| = n! が成り立つ。

置換行列のトレースは、対応する置換の不動点の数に等しい。実際、置換 π が不動点を持てば、巡回置換分解 π = (a₁)(a₂)⋯(a_k)σ で σ が不動点を持たないようなものが取れて、そのとき e_a1, e_a2, …, e_ak は対応する置換行列の固有ベクトル。

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

関連項目

• 交代符号行列（英語版）
• 一般化置換行列

参考文献

• Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. 108. Cambridge: Cambridge University Press. ISBN 0-521-86565-4. Zbl 1106.05001 

表 話 編 歴 線型代数学・行列解析
連立一次方程式	ガウスの消去法 クラメルの公式 ガウス＝ザイデル法 ヤコビ法
ベクトル	線型独立 線型結合 基底 双対基底
ベクトル空間	双対空間 核空間 固有空間 広義固有空間 線型包 行空間 列空間 次元
計量ベクトル空間	ドット積 コーシー＝シュワルツの不等式 直交 正規直交系 正規直交基底 グラム・シュミットの正規直交化法 直交補空間
行列・線型写像	演算・操作 乗法 転置 逆行列 サラスの方法 基本変形 対角化 分解 LU QR コレスキー シューア 特異値 固有値 不変量 行列式 跡 階数 固有値と固有ベクトル 固有多項式 最小多項式 単因子 階数標準形 スミス標準形 ジョルダン標準形 有理標準形 小行列式 クラス 正則 基本 対称 エルミート 正規 直交 回転 ユニタリ 冪零 射影 正定値 ユニモジュラー 置換 区分
行列式	余因子展開 余因子行列 ヴァンデルモンドの行列式 終結式 コーシー・ビネの公式
多重線型代数	外積 外積代数 対称代数 テンソル代数
数値線形代数	基本的な概念 浮動小数点 数値的安定性 疎行列 Z-行列 M行列 条件数 ゲルシュゴリンの定理 クリロフ部分空間 ソフトウェア MATLAB 数値解析ソフトの比較/一覧 ライブラリ Armadillo Basic Linear Algebra Subprograms (BLAS) INTLAB Intel oneAPI Math Kernel Library LAPACK NumPy OpenBLAS 線型代数学ライブラリの比較 反復法・技法 SOR法 共役勾配法 GMRES法 固有値問題の数値解法 ランチョス法 QR法 べき乗法 逆べき乗法 ヤコビ法 (固有値問題) シュトラッセンのアルゴリズム ハウスホルダー変換 ギブンス回転 人物 ジェームズ・H・ウィルキンソン クリーブ・モラー ニコラス・ハイアム ジーン・ゴラブ リチャード・バルガ
行列値関数	行列指数関数 行列の対数 行列の平方根
その他	スカラー ケイリー・ハミルトンの定理 ペロン＝フロベニウスの定理 シューア補行列 シルヴェスターの慣性法則
カテゴリ