順列行列

数学、特に行列理論において、置換行列（かんけいぎょうぎ、英: 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つの順列/行列対応

順列と順列行列の間には、自然な一対一対応が2つあります。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が可逆であることを意味することを証明する。（アルティンはこの証明を演習問題として残しており、^{[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 と が含まれ、これが順列行列の乗算に必要なすべてです。異なる体では かどうかについては意見が一致しませんが、その和は生じません。) ${\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つの要素が存在する順列行列

参照

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

参考文献

1. アーティン、マイケル(1991).代数。プレンティス・ホール。ページ 24–26、118、259、322。ISBN​​ 0-13-004763-5. OCLC  24364036。
2. Zavlanos, Michael M.; Pappas, George J. (2008年11月). 「重み付きグラフマッチングへの動的システムアプローチ」. Automatica . 44 (11): 2817– 2824. CiteSeerX 10.1.1.128.6870 . doi :10.1016/j.automatica.2008.04.009. S2CID  834305 . 2022年8月21日閲覧.直交行列の集合を、要素ごとの非負行列の集合を とします。すると、となり、は順列行列の集合となります。 ${\displaystyle O_{n}}$ ${\displaystyle n\times n}$ ${\displaystyle N_{n}}$ ${\displaystyle n\times n}$ ${\displaystyle P_{n}=O_{n}\cap N_{n}}$ ${\displaystyle P_{n}}$ ${\displaystyle n\times n}$
3. この用語は標準的ではありません。ほとんどの著者は、他の慣習との整合性を考慮して、2つの対応のうちどちらか一方のみを使用します。例えば、Artinは列ベースの対応を使用しています。ここでは、両方の選択肢について議論するために、2つの名称を考案しました。
4. コンウェイ、ジョン・H.、バーギエル、ハイディ、グッドマン＝ストラウス、チャイム(2008). 『事物の対称性』 AKピーターズ/CRCプレス. p. 179. doi :10.1201/b21368. ISBN 978-0-429-06306-0OCLC  946786108。例えば、複数の人の名前の順列は、名前または人のいずれかを移動させるものと考えることができます。別名の観点では、順列は各人に新しい名前または別名を割り当てるものとみなされます（ラテン語の「alias = 別の場所」に由来）。一方、アリバイの観点では、人々を新しい名前に対応する場所に移動します（ラテン語の「alibi = 別の場所」に由来）。
5. ブルアルディ 2006、19ページ
6. ナジュヌデルとニケバリ 2013、p. 4

• Brualdi, Richard A. (2006).組み合わせ行列クラス. 数学とその応用百科事典. 第108巻. ケンブリッジ:ケンブリッジ大学出版局. ISBN 0-521-86565-4. Zbl  1106.05001。
• ナジュヌデル、ジョセフ。Nikeghbali、Ashkan (2013) [2010]、「ランダム化置換行列の固有値の分布」、Annales de l'Institut Fourier、63 (3): 773–838、arXiv : 1005.0402、Bibcode :2010arXiv1005.0402N、doi :10.5802/aif.2777