Matrix with exactly one 1 per row and column
数学 、特に 行列理論 において 、置換行列（ かんけい ぎょうぎ、英: permutation matrix） とは、各行に1つの要素が含まれ、各列のその他の要素は0である正方2値行列である。 [1] : 26 n × n 置換行列は、 n 要素 の 置換を表すことができる。n 行 行列 M に置換行列 P を前 置乗算して PM を形成すると、 M の行が置換される。一方、 n 列行列 M に後置乗算して MP を形成すると、 M の列が置換される 。
あらゆる順列行列 Pは 直交行列 であり 、その 逆行列 はその 転置行列 に等しい。 [1] : 26 実際、順列行列は、 その要素がすべて 非負である直交行列として 特徴付ける ことができる 。 [2] P − 1 = P T {\displaystyle P^{-1}=P^{\mathsf {T}}}
2つの順列/行列対応 順列と順列行列の間には、自然な一対一対応が2つあります。1つは行列の行方向、もう1つは列方向です。 左上の2行形式の
順列 πから始まる例を以下に示します。
π : ( 1 2 3 4 3 2 4 1 ) ⟷ R π : ( 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 ) ↕ ↕ C π : ( 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 ) ⟷ π − 1 : ( 1 2 3 4 4 2 1 3 ) {\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があるのは、 だからです 。より一般的には、 のときは 、の ときは となります 。 R π {\displaystyle R_{\pi }} R π {\displaystyle R_{\pi }} π ( 1 ) = 3 {\displaystyle \pi (1)=3} R π = ( r i j ) {\displaystyle R_{\pi }=(r_{ij})} r i j = 1 {\displaystyle r_{ij}=1} j = π ( i ) {\displaystyle j=\pi (i)} r i j = 0 {\displaystyle r_{ij}=0}
列ベースの対応関係は、 π を 左下の 行列にとります。 の最初の列は 、 のため、3行目に 1 を持ちます 。より一般的には、 のとき は 1 、それ以外のときは 0 となります。2つのレシピは i と j を入れ替えただけなので、 行列 は の転置行列です 。また、 は順列行列なので、 となります 。大きな正方形の他の2辺をたどると、 および となります 。 [ 3] C π {\displaystyle C_{\pi }} C π {\displaystyle C_{\pi }} π ( 1 ) = 3 {\displaystyle \pi (1)=3} C π = ( c i j ) {\displaystyle C_{\pi }=(c_{ij})} c i j {\displaystyle c_{ij}} i = π ( j ) {\displaystyle i=\pi (j)} C π {\displaystyle C_{\pi }} R π {\displaystyle R_{\pi }} R π {\displaystyle R_{\pi }} C π = R π T = R π − 1 {\displaystyle C_{\pi }=R_{\pi }^{\mathsf {T}}=R_{\pi }^{-1}} R π − 1 = C π = R π − 1 {\displaystyle R_{\pi ^{-1}}=C_{\pi }=R_{\pi }^{-1}} C π − 1 = R π {\displaystyle C_{\pi ^{-1}}=R_{\pi }}
順列行列は行または列を順列化する 行列 M に左 または 右のいずれかの行または列を乗算すると、 Mの行または列が π または π −1 だけ入れ替わります 。詳細は少し複雑です。 R π {\displaystyle R_{\pi }} C π {\displaystyle C_{\pi }}
まず、ベクトルの要素を 何らかの順列 π で置換すると、入力ベクトルの 要素が 出力ベクトルのスロットに 移動します。すると、例えば出力の最初のスロットにはどの要素が配置されるでしょうか？答え： となる要素 、つまり となる要素です 。各スロットについても同様に議論すると、出力ベクトルは次のようになります。 ( v 1 , … , v n ) {\displaystyle (v_{1},\ldots ,v_{n})} i th {\displaystyle i^{\text{th}}} v i {\displaystyle v_{i}} π ( i ) th {\displaystyle \pi (i)^{\text{th}}} v j {\displaystyle v_{j}} π ( j ) = 1 {\displaystyle \pi (j)=1} j = π − 1 ( 1 ) {\displaystyle j=\pi ^{-1}(1)}
( v π − 1 ( 1 ) , v π − 1 ( 2 ) , … , v π − 1 ( n ) ) , {\displaystyle {\big (}v_{\pi ^{-1}(1)},v_{\pi ^{-1}(2)},\ldots ,v_{\pi ^{-1}(n)}{\big )},} は、 ではなく で 並べ替えているにもかかわらずです 。したがって、 でエントリを並べ替えるには 、インデックスを で並べ替える必要があります 。 [1] : 25 （エントリを で並べ替えることは、 アリバイの観点 を 取ると呼ばれることもあります が、インデックスを で並べ替えることは、 エイリアスの観点 を 取ることになります 。 [4] ） π {\displaystyle \pi } π − 1 {\displaystyle \pi ^{-1}} π {\displaystyle \pi } π − 1 {\displaystyle \pi ^{-1}} π {\displaystyle \pi } π {\displaystyle \pi }
さて、 n 行 行列に置換行列 を前もって掛け合わせておくとします。 行列の掛け算 の規則により 、 積の要素は次のよう になります
。 M = ( m i , j ) {\displaystyle M=(m_{i,j})} C π {\displaystyle C_{\pi }} ( i , j ) th {\displaystyle (i,j)^{\text{th}}} C π M {\displaystyle C_{\pi }M}
∑ k = 1 n c i , k m k , j , {\displaystyle \sum _{k=1}^{n}c_{i,k}m_{k,j},} ここで は のときを除いて 0 です。ただし のときは 1 です。したがって、和の中で残る項は の項のみであり 、和は に簡約されます 。行インデックスを だけ入れ替えたので、 M の行 自体も π だけ入れ替えられています。 [1] : 25 同様の議論から、 n 列行列 M に を後置乗算すると、 その列が π だけ入れ替えられること がわかります 。 c i , k {\displaystyle c_{i,k}} i = π ( k ) {\displaystyle i=\pi (k)} k = π − 1 ( i ) {\displaystyle k=\pi ^{-1}(i)} m π − 1 ( i ) , j {\displaystyle m_{\pi ^{-1}(i),j}} π − 1 {\displaystyle \pi ^{-1}} R π {\displaystyle R_{\pi }}
他の 2 つのオプションは、 を前置乗算する か、 を後置乗算することであり 、それぞれ行または列を π ではなく π −1 ずつ並べ替えます。 R π {\displaystyle R_{\pi }} C π {\displaystyle C_{\pi }}
転置も逆である 関連する議論は、上で主張したように、任意の置換行列P の転置は 逆行列としても作用し、これは P が可逆であることを意味することを証明する。（アルティンはこの証明を演習問題として残しており、 [1] : 26 でそれを解く。） ならば 、 その転置行列の要素は である 。 積の要素 は である
。 P = ( p i , j ) {\displaystyle P=(p_{i,j})} ( i , j ) th {\displaystyle (i,j)^{\text{th}}} P T {\displaystyle P^{\mathsf {T}}} p j , i {\displaystyle p_{j,i}} ( i , j ) th {\displaystyle (i,j)^{\text{th}}} P P T {\displaystyle PP^{\mathsf {T}}}
∑ k = 1 n p i , k p j , k . {\displaystyle \sum _{k=1}^{n}p_{i,k}p_{j,k}.} のときは常に 、この和の項は P の列 にある2つの異なる要素の積となる ため、すべての項は0となり、和は0となります。 のときは、 P の行 にある要素の平方を足し合わせている ので、和は1となります。したがって、この積は 単位行列となります。対称的な議論は についても同様であり 、 Pは によって逆行列可能であることを意味します 。 i ≠ j {\displaystyle i\neq j} k th {\displaystyle k^{\text{th}}} k th {\displaystyle k^{\text{th}}} i = j {\displaystyle i=j} i th {\displaystyle i^{\text{th}}} P P T {\displaystyle PP^{\mathsf {T}}} P T P {\displaystyle P^{\mathsf {T}}P} P − 1 = P T {\displaystyle P^{-1}=P^{\mathsf {T}}}
順列行列の乗算 n 要素の 𝜎 と 𝜏 の 2 つの順列置換が与えられた場合 、対応する列ベースの置換行列 C σ と C τ の積は次のように与えられます。 [1] : 25 予想どおり、次のように表されます。ここで、 合成 された置換は、最初に 𝜏 に適用され、次に 𝜎 に適用され、右から左に動作します。これは、何らかの行列に C τ をあらかじめ乗算し 、結果の積に C σ をあらかじめ乗算すると、結合された を 1 回だけあらかじめ乗算した場合と同じ結果になるためです 。 C σ C τ = C σ ∘ τ , {\displaystyle C_{\sigma }C_{\tau }=C_{\sigma \,\circ \,\tau },} σ ∘ τ {\displaystyle \sigma \circ \tau } ( σ ∘ τ ) ( k ) = σ ( τ ( k ) ) . {\displaystyle (\sigma \circ \tau )(k)=\sigma \left(\tau (k)\right).} C σ ∘ τ {\displaystyle C_{\sigma \,\circ \,\tau }}
行ベースの行列の場合、ひねりがあります。R σ と R τ の積は 次 の よう に 与えられます 。
R σ R τ = R τ ∘ σ , {\displaystyle R_{\sigma }R_{\tau }=R_{\tau \,\circ \,\sigma },} 合成順列において、𝜎 は𝜏 の前に適用されます。これは、行ベースのオプションでは反転を避けるために後置乗算を行う必要があるため、最初に R σ を後置乗算し、次に R τ を後置乗算することになります。
関数を引数に適用する際に、引数の前ではなく、引数の後に関数を書く（ 後置記法 ）人もいます。線型代数を扱う際には、行ベクトルの線型空間を扱い、線型写像を引数に適用する際には、写像の行列を用いて引数の行ベクトルを後置乗算します。多くの場合、左から右への合成演算子が用いられます。ここではセミコロンを用いて表します。つまり、合成は 次のように定義されます。 σ ; τ {\displaystyle \sigma \,;\,\tau }
( σ ; τ ) ( k ) = τ ( σ ( k ) ) , {\displaystyle (\sigma \,;\,\tau )(k)=\tau \left(\sigma (k)\right),} あるいは、もっとエレガントに言えば、
( k ) ( σ ; τ ) = ( ( k ) σ ) τ , {\displaystyle (k)(\sigma \,;\,\tau )=\left((k)\sigma \right)\tau ,} 𝜎 を最初に適用します。この表記法により、行ベースの順列行列の乗算に関するより簡単な規則が得られます。
R σ R τ = R σ ; τ . {\displaystyle R_{\sigma }R_{\tau }=R_{\sigma \,;\,\tau }.}
マトリックスグループ π が恒等置換で、 すべての i に対して となる場合 、 C π と R π は 両方とも恒等行列 です 。 π ( i ) = i {\displaystyle \pi (i)=i}
n ! 個の順列があり、 写像は 順列と順列行列の間に 1 対 1 対応している ので、 n ! 個の順列行列が存在します。(写像は、そのような対応の 1 つです。) 上記の公式により、これらの n × n 順列行列は 、行列乗算において、単位行列をその 単位元として持つ n ! 位の 群 を形成します。この群を と表記します 。この群は、 実数の 可逆な n × n 行列の一般線型群 の部分群です。実際、任意の 体 F について、群は、 行列要素が F に属する群 の部分群でもあります 。(すべての体には および とともに 0 と が含まれ 、 これが順列行列の乗算に必要なすべてです。異なる体では かどうかについては意見が一致しません が、その和は生じません。) C : π ↦ C π {\displaystyle C\colon \pi \mapsto C_{\pi }} R {\displaystyle R} P n {\displaystyle {\mathcal {P}}_{n}} P n {\displaystyle {\mathcal {P}}_{n}} G L n ( R ) {\displaystyle GL_{n}(\mathbb {R} )} P n {\displaystyle {\mathcal {P}}_{n}} G L n ( F ) {\displaystyle GL_{n}(F)} 0 + 0 = 0 , {\displaystyle 0+0=0,} 0 + 1 = 1 , {\displaystyle 0+1=1,} 0 ∗ 0 = 0 , {\displaystyle 0*0=0,} 0 ∗ 1 = 0 , {\displaystyle 0*1=0,} 1 ∗ 1 = 1 ; {\displaystyle 1*1=1;} 1 + 1 = 0 {\displaystyle 1+1=0}
を{1,2,..., n }上の対称群 、または 順列群 とします 。 ここで、群演算は標準的な右から左への合成「 」です 。また、を 反対の群 とします。 これは左から右への合成「 」を使用します。π を その列ベースの行列に写像 することは 忠実な表現 であり、 π を に 写像 することも同様です 。 S n ← {\displaystyle S_{n}^{\leftarrow }} ∘ {\displaystyle \circ } S n → {\displaystyle S_{n}^{\rightarrow }} ; {\displaystyle \,;\,} C : S n ← → G L n ( R ) {\displaystyle C\colon S_{n}^{\leftarrow }\to GL_{n}(\mathbb {R} )} C π {\displaystyle C_{\pi }} R : S n → → G L n ( R ) {\displaystyle R\colon S_{n}^{\rightarrow }\to GL_{n}(\mathbb {R} )} R π {\displaystyle R_{\pi }}
二重確率行列 すべての置換行列は 二重確率行列 である。すべての二重確率行列の集合は バーコフ多面体 と呼ばれ、置換行列はその多面体において特別な役割を果たす。 バーコフ・フォン・ノイマンの定理 によれば、すべての二重確率実行列は 同じ位数の置換行列の 凸結合であり、置換行列はバーコフ多面体の 端点 （頂点）と正確に一致する。したがって、バーコフ多面体は 置換行列の 凸包である。 [5]
線形代数的性質 各順列が 2 つの順列行列に関連付けられているのと同様に、各順列行列も 2 つの順列に関連付けられています。これは、右上の
行列 P から始めて、上の大きな四角の例にラベルを付け直すとわかります。
ρ P : ( 1 2 3 4 3 2 4 1 ) ⟷ P : ( 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 ) ↕ ↕ P − 1 : ( 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 ) ⟷ κ P : ( 1 2 3 4 4 2 1 3 ) {\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 } κ P {\displaystyle \kappa _{P}} ρ P = κ P − 1 {\displaystyle \rho _{P}=\kappa _{P}^{-1}}
点が によって 固定される のは、 それが によって固定されている場合のみであり、 P の トレースは その共有固定点の数である。 [1] : 322 整数 k がそのうちの 1 つである場合、 標準基底 ベクトル e k はP の 固有ベクトル である 。 [1] : 118 κ P {\displaystyle \kappa _{P}} ρ P {\displaystyle \rho _{P}}
P の 複素 固有値 を計算するには、順列を 互いに素な閉路 の合成として書き 、 とします 。(互いに素な部分集合の順列は可換なので、ここでは右から左に合成するか、左から右に合成するかは関係ありません。) について 、閉路の長さを とし 、 を の複素解の集合とし 、それらの解を 1 の根 とします。 の 多重集合の和は、すると P の固有値の多重集合になります 。 を閉路の積として書き込むと 同じ長さの閉路の数になるので、解析しても 同じ結果になります。 任意の固有値 vの 多重度は、 v を含む に対する i の数です 。 [6] (任意の順列行列は 正規行列 であり、任意の正規行列は 複素数上で 対角化可能なので、 [1] : 259 固有値 v の代数的多重度と幾何的多重度は同じです。) κ P {\displaystyle \kappa _{P}} κ P = c 1 c 2 ⋯ c t {\displaystyle \kappa _{P}=c_{1}c_{2}\cdots c_{t}} 1 ≤ i ≤ t {\displaystyle 1\leq i\leq t} c i {\displaystyle c_{i}} ℓ i {\displaystyle \ell _{i}} L i {\displaystyle L_{i}} x ℓ i = 1 {\displaystyle x^{\ell _{i}}=1} ℓ i th {\displaystyle \ell _{i}^{\,{\text{th}}}} L i {\displaystyle L_{i}} ρ P {\displaystyle \rho _{P}} ρ p {\displaystyle \rho _{p}} L i {\displaystyle L_{i}}
群論 から、任意の置換は 転置 の合成として表せることが分かっています。したがって、任意の置換行列は 、それぞれ 行列式が -1 である行交換 基本行列 の積として因数分解されます 。したがって、置換行列 P の行列式は置換 の 符号 であり 、これは の符号でもあります 。 κ P {\displaystyle \kappa _{P}} ρ P {\displaystyle \rho _{P}}
参照
参考文献 ^ abcdefghi アーティン、マイケル (1991). 代数 。プレンティス・ホール。ページ 24–26、118、259、322。ISBN 0-13-004763-5 . OCLC 24364036。 ^ 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日 閲覧 . 直交行列 の集合を、 要素ごとの非負行列 の集合を とします 。すると、 となり、は順列行列 の集合となります 。 O n {\displaystyle O_{n}} n × n {\displaystyle n\times n} N n {\displaystyle N_{n}} n × n {\displaystyle n\times n} P n = O n ∩ N n {\displaystyle P_{n}=O_{n}\cap N_{n}} P n {\displaystyle P_{n}} n × n {\displaystyle n\times n} ^ この用語は標準的ではありません。ほとんどの著者は、他の慣習との整合性を考慮して、2つの対応のうちどちらか一方のみを使用します。例えば、Artinは列ベースの対応を使用しています。ここでは、両方の選択肢について議論するために、2つの名称を考案しました。 ^ コンウェイ、ジョン・H. 、バーギエル、ハイディ、 グッドマン＝ストラウス、チャイム (2008). 『事物の対称性 』 AKピーターズ/CRCプレス. p. 179. doi :10.1201/b21368. ISBN 978-0-429-06306-0 OCLC 946786108。 例えば、複数の人の名前の順列は、名前または人のいずれかを移動させるものと考えることができます。別名の観点では、順列は各人に新しい名前または別名を割り当てるものとみなされます （ ラテン語の「alias = 別の場所」に由来 ） 。 一方、アリバイの観点では、人々を新しい名前に対応する場所に移動します（ラテン語の 「alibi = 別の場所」に由来）。 ^ ブルアルディ 2006、19ページ ^ ナジュヌデルとニケバリ 2013、p. 4
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/946618e2b33d2a42ee17069db241664df7bc4fcd)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e8a4c616677a8119ee12b531ab7a5cb284f8224)
