順列行列

数学、特に行列理論において、置換行列（かんけいちょうせん、英: permutation matrix）は、各行に 1 つの要素が含まれ、各列のその他の要素は 0 である正方 2 進行列である。[ ^{1] : 26} n × nの置換行列は、 n要素の置換を表すことができる。 n行行列Mに置換行列Pを乗算してPMを形成すると、 Mの行が置換され、 n列行列Mに乗算してMP ​​を形成すると、 Mの列が置換される。

あらゆる順列行列Pは直交行列であり、その逆行列はその転置行列に等しい。^{[1] : 26}実際、順列行列は、その要素がすべて非負である直交行列として特徴付ける ことができる。^[2]${\displaystyle P^{-1}=P^{\mathsf {T}}}$

順列と順列行列の間には 2 つの自然な 1 対 1 の対応関係があり、1 つは行列の行に沿って機能し、もう 1 つは行列の列に沿って機能します。次に、左上の 2 行形式の 順列πから始まる例を示します。

${\displaystyle {\begin{matrix}\pi \colon {\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}&\longleftrightarrow &R_{\pi }\colon {\begin{pmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{pmatrix}}\\[5pt]{\Big \updownarrow }&&{\Big \updownarrow }\\[5pt]C_{\pi }\colon {\begin{pmatrix}0&0&0&1\\0&1&0&0\\1&0&0&0\\0&0&1&0\end{pmatrix}}&\longleftrightarrow &\pi ^{-1}\colon {\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}}\end{matrix}}}$

行ベースの対応は、右上の行列への置換π を取得します。 の最初の行は、の 3 番目の列に 1 を持ちます。これは のためです。より一般的には、のときはであり、それ以外の場合はとなります。 ${\displaystyle R_{\pi}}$${\displaystyle R_{\pi}}$${\displaystyle \pi (1)=3}$${\displaystyle R_{\pi }=(r_{ij})}$${\displaystyle r_{ij}=1}$${\displaystyle j=\pi (i)}$${\displaystyle r_{ij}=0}$

列ベースの対応は、π を左下の行列にとります。 の最初の列は、 のため、3行目に 1 を持ちます。より一般的には、のときは 1 で、それ以外のときは 0 となるため、次が得られます。2 つのレシピはiとj を入れ替えただけなので、行列はの転置です。また、は順列行列なので、 となります。大きな正方形の他の 2 辺をたどると、 およびとなります。^[3]${\displaystyle C_{\pi}}$${\displaystyle C_{\pi}}$${\displaystyle \pi (1)=3}$${\displaystyle C_{\pi }=(c_{ij})}$${\displaystyle c_{ij}}$${\displaystyle i=\pi (j)}$${\displaystyle C_{\pi}}$${\displaystyle R_{\pi}}$${\displaystyle R_{\pi}}$${\displaystyle C_{\pi }=R_{\pi }^{\mathsf {T}}=R_{\pi }^{-1}}$${\displaystyle R_{\pi ^{-1}}=C_{\pi }=R_{\pi }^{-1}}$${\displaystyle C_{\pi ^{-1}}=R_{\pi }}$

行列Mの左側または右側に またはを乗算すると、 Mの行または列がπまたはπ ⁻¹だけ入れ替わります。詳細は少し複雑です。 ${\displaystyle R_{\pi}}$${\displaystyle C_{\pi}}$

まず、ベクトルの要素を何らかの順列πで並べ替えると、入力ベクトルの要素が出力ベクトルのスロットに移動します。すると、どの要素が、たとえば出力の最初のスロットに配置されますか? 答え: の要素は であり、したがって です。各スロットについて同様に議論すると、出力ベクトルは次のようになります。 ${\displaystyle (v_{1},\ldots ,v_{n})}$${\displaystyle i^{\text{th}}}$${\displaystyle v_{i}}$${\displaystyle \pi (i)^{\text{th}}}$${\displaystyle v_{j}}$${\displaystyle \pi (j)=1}$${\displaystyle j=\pi ^{-1}(1)}$

${\displaystyle {\big (}v_{\pi ^{-1}(1)},v_{\pi ^{-1}(2)},\ldots ,v_{\pi ^{-1}(n)}{\big )},}$

たとえ で並べ替えているのがであって、 ではないとしてもです。したがって、 でエントリを並べ替えるには、インデックスを で並べ替える必要があります。^{[1] : 25} （ でエントリを並べ替えることは、アリバイの観点 を取ると呼ばれることもあり、 でインデックスを並べ替えることは、エイリアスの観点を取ることになります。^[4]） ${\displaystyle \pi }$${\displaystyle \pi ^{-1}}$${\displaystyle \pi }$${\displaystyle \pi ^{-1}}$${\displaystyle \pi }$${\displaystyle \pi }$

ここで、 n行の行列に置換行列を乗算するとします。行列の乗算の規則により、積の要素は次のようになります。 ${\displaystyle M=(m_{i,j})}$${\displaystyle C_{\pi }}$${\displaystyle (i,j)^{\text{th}}}$${\displaystyle C_{\pi }M}$

$${\displaystyle \sum _{k=1}^{n}c_{i,k}m_{k,j},}$$

ここで は のときを除いて 0 です。ただし のときは 1 です。したがって、和で残る項は の項のみであり、和は に簡約されます。行インデックスを だけ入れ替えたので、 Mの行自体をπだけ入れ替えています。^{[1] : 25}同様の議論から、 n列行列Mに を 後置乗算すると、その列がπだけ入れ替えられることがわかります。 ${\displaystyle c_{i,k}}$${\displaystyle i=\pi (k)}$${\displaystyle k=\pi ^{-1}(i)}$${\displaystyle m_{\pi ^{-1}(i),j}}$${\displaystyle \pi ^{-1}}$${\displaystyle R_{\pi }}$

他の 2 つのオプションは、 を事前に乗算するか、 を後で乗算することであり、それぞれ行または列をπではなくπ ⁻¹ずつ並べ替えます。 ${\displaystyle R_{\pi }}$${\displaystyle C_{\pi }}$

関連する議論は、上で主張したように、任意の置換行列Pの転置は逆行列としても機能し、Pが可逆であることを証明しています。(Artin はその証明を演習問題として残しており、^{[1] : 26 で}それを解きます。) の場合、その転置の要素は です。積の要素は ${\displaystyle P=(p_{i,j})}$${\displaystyle (i,j)^{\text{th}}}$${\displaystyle P^{\mathsf {T}}}$${\displaystyle p_{j,i}}$${\displaystyle (i,j)^{\text{th}}}$${\displaystyle PP^{\mathsf {T}}}$

$${\displaystyle \sum _{k=1}^{n}p_{i,k}p_{j,k}.}$$

のときはいつでも、この和の項はPの列にある 2 つの異なる要素の積です。したがって、すべての項は 0 で、和は 0 です。 のときは、 Pの行にある要素の平方を合計しているので、和は 1 です。したがって、積は単位行列です。対称的な議論は についても同じことを示し、Pは で逆行列可能であることを意味します。 ${\displaystyle i\neq j}$${\displaystyle k^{\text{th}}}$${\displaystyle k^{\text{th}}}$${\displaystyle i=j}$${\displaystyle i^{\text{th}}}$${\displaystyle PP^{\mathsf {T}}}$${\displaystyle P^{\mathsf {T}}P}$${\displaystyle P^{-1}=P^{\mathsf {T}}}$

n要素の 𝜎 と 𝜏の 2 つの順列が与えられた場合、対応する列ベースの順列行列C _σとC _τの積は次のように与えられます。^{[1] : 25}予想どおり、次のように表されます。ここで、 合成順列は、右から左に向かって、最初に 𝜏 に適用され、次に 𝜎 に適用されます。 これは、何らかの行列にC _τを事前に乗算し、次に結果の積にC _σを事前に乗算すると、結合された を 1 回だけ事前に乗算するのと同じ結果になるためです。 $${\displaystyle C_{\sigma }C_{\tau }=C_{\sigma \,\circ \,\tau },}$$${\displaystyle \sigma \circ \tau }$$${\displaystyle (\sigma \circ \tau )(k)=\sigma \left(\tau (k)\right).}$$${\displaystyle C_{\sigma \,\circ \,\tau }}$

行ベースの行列の場合、ひねりがあります。R _σとR _{τの積は次のように表さ}れます。

${\displaystyle R_{\sigma }R_{\tau }=R_{\tau \,\circ \,\sigma },}$

合成順列では、 𝜎 が 𝜏 の前に適用されます。これは、行ベースのオプションでは反転を避けるために後置乗算を行う必要があるため、最初にR _{σで後置乗算し、次に}R _τで後置乗算を行うためです。

関数を引数に適用する場合、関数を引数の前ではなく、引数の後に記述する（後置記法）人もいます。線型代数を行うときは、行ベクトルの線形空間を扱い、マップの行列を使用して引数の行ベクトルを後置乗算することで、線形マップを引数に適用します。左から右への合成演算子がよく使用されますが、ここではセミコロンを使用して表します。したがって、合成は次のように定義されます 。${\displaystyle \sigma \,;\,\tau }$

${\displaystyle (\sigma \,;\,\tau )(k)=\tau \left(\sigma (k)\right),}$

あるいは、もっとエレガントに言えば、

${\displaystyle (k)(\sigma \,;\,\tau )=\left((k)\sigma \right)\tau ,}$

𝜎 を最初に適用します。この表記により、行ベースの順列行列を乗算するためのより簡単な規則が得られます。

${\displaystyle R_{\sigma }R_{\tau }=R_{\sigma \,;\,\tau }.}$

π が恒等置換で、すべてのiに対して となるとき、C _πとR _{π は}両方とも恒等行列です。 ${\displaystyle \pi (i)=i}$

n !個の順列があり、写像は順列と順列行列の間に 1 対 1 の対応関係にあるため、n! 個の順列行列が存在します。(写像は、そのような対応関係の 1 つです。) 上記の公式により、これらのn × n順列行列は、単位行列を単位元として、行列乗算の下でn !個の位数の群を形成します。この群を と表記します。この群は、実数の可逆なn × n行列の一般線型群のサブグループです。実際、任意の体Fについて、群は 、行列要素がFに属する群 のサブグループでもあります。(すべての体にはおよびとともに 0 と 1 が含まれ、これが順列行列の乗算に必要なすべてです。異なる体では かどうかは一致しませんが、その和は生じません。) ${\displaystyle C\colon \pi \mapsto C_{\pi }}$${\displaystyle R}$${\displaystyle {\mathcal {P}}_{n}}$${\displaystyle {\mathcal {P}}_{n}}$ ${\displaystyle GL_{n}(\mathbb {R} )}$ ${\displaystyle {\mathcal {P}}_{n}}$${\displaystyle GL_{n}(F)}$${\displaystyle 0+0=0,}$ ${\displaystyle 0+1=1,}$ ${\displaystyle 0*0=0,}$ ${\displaystyle 0*1=0,}$${\displaystyle 1*1=1;}$${\displaystyle 1+1=0}$

を{1,2,..., n }上の対称群、または順列群 と表します。ここで、群演算は標準の右から左への合成 " " です。また、を反対の群と表します。これは左から右への合成 " "を使用します。πをその列ベースの行列に写像することは忠実な表現であり、πを に写像することについても同様です。 ${\displaystyle S_{n}^{\leftarrow }}$${\displaystyle \circ }$${\displaystyle S_{n}^{\rightarrow }}$${\displaystyle \,;\,}$${\displaystyle C\colon S_{n}^{\leftarrow }\to GL_{n}(\mathbb {R} )}$${\displaystyle C_{\pi }}$${\displaystyle R\colon S_{n}^{\rightarrow }\to GL_{n}(\mathbb {R} )}$${\displaystyle R_{\pi }}$

すべての置換行列は二重確率行列である。すべての二重確率行列の集合はバーコフ多面体と呼ばれ、置換行列はその多面体で特別な役割を果たす。バーコフ・フォン・ノイマンの定理によれば、すべての二重確率実行列は同じ次数の置換行列の凸結合であり、置換行列はまさにバーコフ多面体の端点（頂点）である。したがって、バーコフ多面体は置換行列の凸包である。 ^[5]

各順列が 2 つの順列行列に関連付けられているのと同様に、各順列行列も 2 つの順列に関連付けられています。これは、右上の 行列Pから始めて、上の大きな四角の例にラベルを付け直すとわかります。

${\displaystyle {\begin{matrix}\rho _{P}\colon {\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}&\longleftrightarrow &P\colon {\begin{pmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{pmatrix}}\\[5pt]{\Big \updownarrow }&&{\Big \updownarrow }\\[5pt]P^{-1}\colon {\begin{pmatrix}0&0&0&1\\0&1&0&0\\1&0&0&0\\0&0&1&0\end{pmatrix}}&\longleftrightarrow &\kappa _{P}\colon {\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}}\end{matrix}}}$

したがって、ここではCの逆を 、R の逆を と表しています。すると、2つの順列とに共通するいくつかの組み合わせ特性から、Pの線型代数特性を計算できます。 ${\displaystyle \kappa }$${\displaystyle \rho }$${\displaystyle \kappa _{P}}$${\displaystyle \rho _{P}=\kappa _{P}^{-1}}$

点がによって固定されるのは、それが によって固定される場合だけであり、Pのトレースはそのような共有固定点の数です。^{[1] : 322} 整数kがそのうちの 1 つである場合、標準基底ベクトルe _{k は}Pの固有ベクトルです。^{[1] : 118}${\displaystyle \kappa _{P}}$${\displaystyle \rho _{P}}$

Pの複素固有値を計算するには、置換を互いに素なサイクルの合成として書き、 とします。(互いに素な部分集合の置換は可換なので、ここでは右から左に合成するか、左から右に合成するかは問題ではありません。) について、サイクルの長さを とし、をの複素解の集合とし、それらの解を1 の根とします。の多重集合の和は、するとPの固有値の多重集合になります。 をサイクルの積として書き込むと、同じ長さのサイクルの数が同じになるため、解析しても同じ結果になります。任意の固有値vの多重度は、 v を含むiの個数です。^[6] (任意の置換行列は正規であり、任意の正規行列は複素数上で対角化可能なので、 ^{[1] : 259}固有値vの代数的多重度と幾何的多重度は同じです。) ${\displaystyle \kappa _{P}}$${\displaystyle \kappa _{P}=c_{1}c_{2}\cdots c_{t}}$${\displaystyle 1\leq i\leq t}$${\displaystyle c_{i}}$${\displaystyle \ell _{i}}$${\displaystyle L_{i}}$${\displaystyle x^{\ell _{i}}=1}$${\displaystyle \ell _{i}^{\,{\text{th}}}}$ ${\displaystyle L_{i}}$${\displaystyle \rho _{P}}$${\displaystyle \rho _{p}}$${\displaystyle L_{i}}$

群論から、任意の順列は転置の合成として表すことができることが分かっています。したがって、任意の順列行列は、それぞれ行列式が −1 である行切り替え基本行列の積として因数分解されます。したがって、順列行列Pの行列式は、順列 の符号であり、これは の符号でもあります。 ${\displaystyle \kappa _{P}}$${\displaystyle \rho _{P}}$

• コスタス配列、エントリ間の変位ベクトルがすべて異なる順列行列
• n-クイーンズパズル、各対角要素と反対角要素に最大1つの要素が存在する順列行列

• 交互符号行列
• 交換マトリックス
• 一般化順列行列
• ルーク多項式
• 永続