置換行列

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索
三文字の置換を記述する行列。
二つの置換行列のもまた置換行列である。

六種類それぞれの同じ型の行列が以下のような位置に存在している:
三次対称群の乗積表
(これらもまた置換行列)

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

定義[編集]

m 文字の置換:

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

が与えられたとき、対応する置換行列(m-次元列ベクトルに作用するもの)は、ejj-番目の位置に 1, それ以外が 0 の行ベクトルとして

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

性質[編集]

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

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

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

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

行ベクトル hPπ を右から掛けるとベクトルに対する列の置換を引き起こす:

ゆえに、ふたたび (hPσ)Pπ = hPπ∘σ が確認される。

注意[編集]

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

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

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

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

写像 SnA ⊂ GL(n, Z2)忠実表現であり、従って |A| = n! が成り立つ。

置換行列のトレースは、対応する置換の不動点の数に等しい。実際、置換 π が不動点を持てば、巡回置換分解 π = (a1)(a2)⋯(ak)σσ が不動点を持たないようなものが取れて、そのとき ea1, ea2, …, eak は対応する置換行列の固有ベクトル

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

関連項目[編集]

参考文献[編集]

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