置換行列についてのメモ

桂田祐史

2011 年 12 月 9 日, 10 日

σ が n 次の置換であるとは、 σ が {1, 2, …, n} から {1, 2, …, n} への全単射であることをいう。 n 次の置換全体を n 次対称群と呼び、 S_{n} と書く。

二つの置換の積を写像としての積として定める:

τσ := τ ∘ σ, i.e. (τσ)(i) = τ(σ(i)) (i ∈ {1, …, n}).

(これとは反対に (τσ)(i) = σ(τ(i)) と定義する流儀もあるようだ。必要がない場合、どちらで定義するか書かない、という日和見な (?) 流儀もあるようだ。いずれにせよ、本質的な違いがあるわけではない。 )

σ ∈ S_{n}, A = (a_{1}, …, a_{n}) ∈ M(n; 𝕂) に対して、 A_{σ} を

A_{σ} := (a_{σ(1)}, …, a_{σ(n)}) (i.e., A_{σ} の (i, j) 成分= a_{iσ(j)})

で定める (列ベクトルの置換)。

e_{i} を第 i 成分のみが 1 で、他の成分は 0 である n 次元ベクトルとする。 n 次単位行列を I とすると、 I = (e_{1}, …, e_{n}) である。

[figure]

{命題 0.1 (I_{σ} は右からかけると列ベクトルを置換する)σ ∈ S_{n}, A ∈ M(n; 𝕂) に対して、 \atop AI_{σ} = A_{σ}.}

[figure]

証明 A = (a_{1}, …, a_{n}) とする。 ∀k ∈ {1, …, n} に対して、

Ae_{k} = a_{k}

が成り立つことは高校以来おなじみであろう。

AI_{σ} = A (e_{σ(1)}, …, e_{σ(n)}) = (Ae_{σ(1)}, …, Ae_{σ(n)}) = (a_{σ(1)}, …, a_{σ(n)}) = A_{σ}.

[figure]

命題 0.2 ∀σ ∈ S_{n} に対して、 I_{σ} は実直交行列である (すなわち I_{σ}^{−1} = I_{σ}^{T})。

[figure]

証明 i ≠ j ⇔ σ(i) ≠ σ(j) であることに注意すると、一般に (e_{σ(i)}, e_{σ(j)}) = δ_{σ(i)σ(j)} = δ_{ij} が成り立つことが分かる。ゆえに {e_{σ(i)}}_{i=1}^{n} は正規直交系であるから、 I_{σ} は直交行列である。

[figure] 命題 0.3 I_{τ}I_{σ} = I_{τσ}. 特に I_{σ^{−1}} = I_{σ}^{−1}. [figure]

証明 A = I_{τ} = (e_{τ(1)}, …, e_{τ(n)}) とするとき、 a_{k} = e_{τ(k)} (k = 1, …, n) であって、

I_{τ}I_{σ} = AI_{σ} = A_{σ} = (a_{σ(1)}, …, a_{σ(n)}) = (e_{τ(σ(1))}, …, e_{τ(σ(n))}) = I_{τσ}.

σ ∈ S_{n}, A = (b_{1}^{T} ; ⋮ ; b_{n}^{T} ) ∈ M(n; 𝕂) に対して、^{σ}A を

σA := (b_{σ(1)}^{T} ; ⋮ ; b_{σ(n)}^{T}) (i.e., ^{σ}A の (i, j) 成分 = a_{σ(i)j})

で定める。

[figure]

{命題 0.4 A ∈ M(n, 𝕂), σ ∈ S_{n} とするとき、 \atop (I_{σ})^{T} A = I_{σ}^{−1}A = ^{σ}A.}

[figure]

証明 A = (b_{1}^{T} ; ⋮ ; b_{n}^{T} ) とおくとき、

(I_{σ})^{T} A = (I_{σ})^{T} (A^{T})^{T} = (A^{T} I_{σ})^{T} = ((b_{1}, …, b_{n}) I_{σ})^{T} = (b_{σ(1)}, …, b_{σ(n)})^{T} = (b_{σ(1)}^{T} ; ⋮ ; b_{σ(n)}^{T}) = ^{σ}A.

昨日 (2011 年 12 月 9 日) 問題となった置換行列は、

P = (e_{1}, e_{N+1}, e_{2}, e_{N+2}, ⋯, e_{N}, e_{2N})

である。 σ ∈ S_{n} を

σ(1) = 1, σ(2) = N + 1,
σ(3) = 2, σ(4) = N + 2,
⋯,
σ(2j − 1) = j, σ(2j) = N + j,
⋯,
σ(2N − 1) = N, σ(2N) = 2N

で定めるとき、 P = I_{σ}.

A = (a_{ij}), σ ∈ S_{n} に対して、

I_{σ}^{−1}AI_{σ} = (a_{σ(i)σ(j)}) .