置換行列

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 になる。

Summarize Timeline Top Qs Fact Check

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