置換行列

置換行列：定義と性質

置換行列とは、各行と各列にちょうど1つの1を持ち、それ以外の要素がすべて0である正方行列のことです。n次正方行列の場合、n個の要素からなる集合の置換を表現し、行列の積によって行または列の置換を効果的に行います。

定義

集合 {1, 2, ..., n} 上の置換 π を考えます。この置換は、集合の要素を並べ替える操作を表します。置換 π に対応する置換行列 Pπ は、以下のようになります。

(i, π(i)) 成分が 1 であり、その他の成分はすべて 0 となる n × n 行列です。言い換えれば、単位行列 I の行を置換 π に従って並べ替えた行列と考えることもできます。

例えば、n = 3 の場合、置換 π = (1 2 3) → (2 3 1) に対する置換行列は次のようになります。


0 1 0
0 0 1
1 0 0

性質

置換行列はいくつかの重要な性質を持っています。

1. 直交行列: 置換行列 Pπ は、その転置行列 Pπ⊤ との積が単位行列になるため、直交行列です。つまり、PπPπ⊤ = I が成り立ちます。

2. 逆行列: 置換行列の逆行列は、その転置行列に等しく、Pπ⁻¹ = Pπ⊤ = Pπ⁻¹ となります。これは、置換の逆置換に対応する置換行列であることを意味します。

3. 行列の積: 2つの置換 π と σ に対応する置換行列 Pπ と Pσ の積 PσPπ は、置換の合成 σ∘π に対応する置換行列 Pσ∘π となります。

4. 行と列の置換: 行ベクトル v に左から置換行列 Pπ をかけると、v の要素が行の置換 π に従って並べ替えられます。同様に、列ベクトル w に右から Pπ をかけると、w の要素が列の置換 π⁻¹ に従って並べ替えられます。

5. 行列式: 置換行列の行列式は、対応する置換の符号に一致します。偶置換の場合は 1、奇置換の場合は -1 となります。

6. トレース: 置換行列のトレース（対角成分の和）は、対応する置換における不動点の数に等しくなります。

群論との関連性

n 個の要素の置換全体の集合は、n! 個の要素を持つ対称群 Sn を形成します。置換行列全体の集合も、行列の積に関して群をなし、対称群 Sn と同型になります。単位行列は単位元に対応します。

関連事項

交代符号行列: 行列式が 1 または -1 である正方行列。置換行列は交代符号行列の一種です。
二重確率行列: 行と列の成分の和がすべて 1 である正方行列。置換行列は二重確率行列です。
* 一般化置換行列: 各行各列に高々1つの非ゼロ要素を持つ行列。置換行列は一般化置換行列の特殊な場合です。

まとめ

置換行列は、線形代数と群論を結びつける重要な概念であり、アルゴリズムや計算機科学など、様々な分野で応用されています。その性質を理解することは、行列演算やアルゴリズム設計において役立ちます。この解説が、置換行列の理解を深める一助となれば幸いです。

もう一度検索