置換行列

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

定義

$m$ 文字の置換:

\pi \colon \lbrace 1,\ldots ,m\rbrace \to \lbrace 1,\ldots ,m\rbrace

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

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

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

P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (m)}\end{bmatrix}}

で与えられる $m \times m$ -行列 $P π$ を言う^[1]。これは、各 $i$ について $(i, π (i))$ -成分のみが例外的に $1$ で、ほかの成分は全て $0$ になる。

性質

$m$ 文字の置換 $π, σ$ が与えられたとき、対応する（列ベクトルに作用する）置換行列 $P π, P σ$ の積は、置換の合成に対応する置換行列に等しい。つまり

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

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

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

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

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

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

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

\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}}

ゆえに、ふたたび $(h P σ) P π = h P π\circσ$ が確認される。

注意

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

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

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

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

写像 $S n \to A \subset GL(n, Z 2)$ は忠実表現であり、従って $| A | = n!$ が成り立つ。

置換行列のトレースは、対応する置換の不動点の数に等しい。実際、置換 $π$ が不動点を持てば、巡回置換分解 $π = (a 1)(a 2)\dots(a k) σ$ で $σ$ が不動点を持たないようなものが取れて、そのとき $e a 1, e a 2, \dots, e a k$ は対応する置換行列の固有ベクトル。

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

参考文献

^ Brualdi (2006) p.2
^ Brualdi (2006) p.19

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

[Bru2-1] Brualdi (2006) p.2

[Bru19-2] Brualdi (2006) p.19

[1]

[2]

定義

性質

注意

関連項目

参考文献