ベイジアン研究所

プログラミング言語(アルゴリズム的な話が中心)やガジェットの紹介をしています。時々心理学の話も。

【線型代数学入門】置換

1. 記事の目的
以下の記事で連立方程式の解法について述べた。本記事では、連立方程式のその他の解法である、クラメルの解法や、行列式と呼ばれるもので重要となる置換に関して述べる。置換は、現代数学のあらゆる重要な部分で出現し(ワイル理論、写像類群など)、深い内容のものである。ここではその定義と、簡単な性質に関して述べる。

camelsan.hatenablog.com

2. 置換の定義
「1,2」という二つの整数を、「1,2」の二つの整数に対応づけることを考える(一つの数字を使用したら、同じ数字は使わないこととする)。この方法は次の二つある。


    \begin{split}
        &1\leftrightarrow 1 \\
        &2\leftrightarrow 2
    \end{split}


    \begin{split}
        &1\leftrightarrow 2\\
        &2\leftrightarrow 1
    \end{split}

である。三つ以上の整数同士でも、同様の対応を考えることができる。一般的に述べると、n個の整数「1,2,\dots,n」をn個の整数「1,2,\dots,n」に対応させる方法をn文字の置換という。整数1の対応先をi_1、整数2の対応先をi_2、・・・、整数nの対応先をi_nとおくと、この対応方法を


    \begin{pmatrix}
        1&2&\dots&n \\
        i_1&i_2&\dots&i_n
    \end{pmatrix}

と書く(上の数字を下の数字に対応させる)。記号\sigmaを使用してi_1=\sigma(1)i_2=\sigma(2)、・・・、i_n=\sigma(n)と書くと、

\sigma=
    \begin{pmatrix}
        1&2&\dots&n \\
        i_1&i_2&\dots&i_n
    \end{pmatrix}

と書ける。ここで、上の行は、1,2,\dots,nと並んでなくても良い(上下の対応関係があっていれば同じ置換となる)。例えば、


    \begin{pmatrix}
        1&2&3 \\
        2&3&1
    \end{pmatrix}
    =
    \begin{pmatrix}
        1&3&2 \\
        2&1&3
    \end{pmatrix}

である。

どの文字を動かさない置換、


    \begin{pmatrix}
        1&2&\dots&n \\
        1&2&\dots&n
    \end{pmatrix}

を口頭置換といい、1_nと表す。置換\sigmaの逆対応(下の数字を上の数字に対応させる)を逆置換といい、\sigma^{-1}で表す。例えば、

\sigma=
    \begin{pmatrix}
        1&2&3 \\
        2&3&1
    \end{pmatrix}

ならば、

\sigma^{-1}=
    \begin{pmatrix}
        2&3&1 \\
        1&2&3
    \end{pmatrix}
    =
    \begin{pmatrix}
        1&2&3 \\
        3&1&2
    \end{pmatrix}

となる。

二つの置換\sigma\tauの積\sigma\tauは、\tauの置換を適用後、\sigmaの置換を行うことで定義する(\sigmaから実施しないことに注意。但し、積の順番通り、\sigmaから実施する流儀もある)。例えば、

\sigma=
    \begin{pmatrix}
        1&2&3 \\
        2&3&1
    \end{pmatrix}
    ,
    \tau=
    \begin{pmatrix}
        1&2&3 \\
        1&3&2
    \end{pmatrix}

とすると、


    \begin{split}
        &\sigma\tau(1)=\sigma(1)=2 \\
        &\sigma\tau(2)=\sigma(3)=1 \\
        &\sigma\tau(3)=\sigma(2)=3 
    \end{split}

より、

\sigma\tau=
    \begin{pmatrix}
        1&2&3 \\
        2&1&3
    \end{pmatrix}

1,2,\dots,n」から「1,2,\dots,n」の置換全てを集めたものをS_nと書く(集合論の言葉で、S_nを置換の集合という)。例えば、S_2は、


    \begin{pmatrix}
        1&2 \\
        1&2
    \end{pmatrix}
    ,
    \begin{pmatrix}
        1&2 \\
        2&1
    \end{pmatrix}

の二つの置換からなる。

2. 置換の性質
置換の集まりS_nに関して次の定理が成り立つ。

定理
(1) \sigma_1,\dots,\sigma_mS_nの重複のない全ての置換とすると、\sigma_1^{-1},\dots,\sigma_m^{-1}S_nの重複のない全ての置換である。
(2) \tauを固定された一つのn文字の置換とする。\sigma_1,\dots,\sigma_mS_nの重複のない全ての置換とすると、\tau\sigma_1^{-1},\dots,\tau\sigma_m^{-1}S_nの重複のない全ての置換である。
(1)の証明S_nの置換の個数を数える。1を他の整数に対応させる候補は、n通りある。2を他の整数に対応させる候補は、1に対応させた整数以外のn-1通りある。3を対応させる候補数は、n-2通り、・・・、nを対応させる候補数は、1通りなので、置換の個数は、1\times 2\times \dots \times n=n!個である。即ち、定理の主張のmは実は、m=n!である。
\sigma_1^{-1}=\sigma_2^{-1}ならば、両辺に右から\sigma_1、左から\sigma_2を掛けると、\sigma_1=\sigma_2である。対偶を取ると、\sigma_1\neq\sigma_2ならば\sigma_1^{-1}\neq\sigma_2^{-1}である。従って、\sigma_1^{-1},\dots,\sigma_m^{-1}の個数もn!個で、重複がないので、S_nの全ての置換である。
(2)の証明
\tau\sigma_1=\tau\sigma_2の両辺に、\tau^{-1}を掛けると、\sigma_1=\sigma_2である。対偶をとって、\sigma_1\neq\sigma_2ならば、\tau\sigma_1\neq\tau\sigma_2である。即ち、\tau\sigma_1^{-1},\dots,\tau\sigma_m^{-1}S_nの全ての置換である。

特殊な置換に名前をつける。n文字の置換で2つの文字のみを入れ替え、他のn-2文字を動かさないような置換のことを、互換と呼ぶことにする。入れ替えられる文字をijとすると、この互換を2文字のみで、(i,j)と書くことができる。例えば、4文字の置換に対して、


    \begin{pmatrix}
        1&2&3&4 \\
        2&1&3&4
    \end{pmatrix}

は互換であり、


    \begin{pmatrix}
        1&2
    \end{pmatrix}
    =
    \begin{pmatrix}
        1&2&3&4 \\
        2&1&3&4
    \end{pmatrix}

と書ける。

置換は、互換のいくつかの積で表せるという性質がある。即ち次の定理が成り立つ。

定理
任意の置換は、何個かの互換の積として表される。この時、互換の個数が偶数であるか、奇数であるかは、この互換の積で与えられている置換のみにより決まり、互換の積として表す表し方にはよらない。
証明:最初に、置換が互換のいくつかの積として表せることを証明する。文字数の帰納法で証明する。n=2の時、


    \begin{split}
    &\begin{pmatrix}
        1 & 2 \\
        1 & 2
    \end{pmatrix}
    =
    \begin{pmatrix}
        1 & 2 \\
        2 & 1
    \end{pmatrix}
    \begin{pmatrix}
        1 & 2 \\
        2 & 1
    \end{pmatrix} \\
    &\begin{pmatrix}
        1 & 2 \\
        2 & 1
    \end{pmatrix}
    \end{split}

より、S_2に関しては、全ての置換が互換の積として表されている。n以下の時成立すると仮定して、\sigman+1文字の置換とする。


    \begin{pmatrix}
        1&2&\dots&n&n+1 \\
        i_1&i_2&\dots&i_n&i_{n+1}
    \end{pmatrix}

i_{n+1}=n+1の時、\sigman文字の置換であり、これは帰納法の仮定より、互換の積として表すことができる。i_{n+1} \lt n+1の時、


    \begin{pmatrix}
        1&2&\dots&n&n+1 \\
        i_1&i_2&\dots&i_n&i_{n+1}
    \end{pmatrix} 
    =
    \begin{pmatrix}
        i_{n+1}-1 & i_{n+1}
    \end{pmatrix}
    \dots 
    \begin{pmatrix}
        n & n+1
    \end{pmatrix} 
    \begin{pmatrix}
        1&2&\dots&n&n+1 \\
        i_1&i_2&\dots&i_n&{n+1}
    \end{pmatrix}

だが、右辺の最後の項は、n文字の置換なので、帰納法の仮定から互換の積で表すことができる。よってn+1のときも成立するので、帰納法より置換は互換の積で表せることが証明された。

次に互換の個数が偶数か奇数であるかは、積の表示の仕方によらないことを証明する。


    \Delta(x_1,x_2,\dots,x_n) = \displaystyle\prod_{1\le i\lt j \le n}(x_j-x_i)

を考える。ここで、\displaystyle\prod_{1\le i\lt j \le n}は、1\le i\lt j \le nを満たす添字に関して、全て積を取るという意味である。例えば、


    \begin{split}
        \Delta(x_1,x_2,x_3) &=  \displaystyle\prod_{1\le i\lt j \le 3}(x_j-x_i) \\
       &=(x_3-x_1)(x_3-x_2)(x_2-x_1) 
    \end{split}

である。\Delta(x_1,x_2,\dots,x_n)を差積という。置換\sigmaに対し、


    \Delta^{\sigma}(x_1,x_2,\dots,x_n) = \Delta(x_{\sigma(1)},x_{\sigma(2)},\dots,x_{\sigma(n)} )

と定義すると、


    \Delta^{\sigma}(x_1,x_2,\dots,x_n) = \pm\Delta(x_1,x_2,\dots,x_n)

となる。実際、\Delta(x_1,x_2,\dots,x_n)の右辺には、1,\dots,nの整数から二つとった組み合わせの添字が全てある。よって、右辺の各項の添字を入れ替えると、1,\dots,nの整数から、二つとった組み合わせ全ての添字がある。従って、\Delta^{\sigma}(x_1,x_2,\dots,x_n)の右辺は、適切に、\Delta(x_1,x_2,\dots,x_n)の各項の順番を変えたものに等しいので、


    \Delta^{\sigma}(x_1,x_2,\dots,x_n) = \pm\Delta(x_1,x_2,\dots,x_n)

である。特に、\tauが互換の時、


    \Delta^{\tau}(x_1,x_2,\dots,x_n) = -\Delta(x_1,x_2,\dots,x_n)

である。実際、\tau=(I,j),(i\lt j)とすると、\Deltaの各校の入れ替え方法は次の通りに場合分けされる。
(1) (x_i-x_j)の項で、i,jを交換すると-1倍される。
(2) i\lt k \lt jとなるkに対し、


    (x_k-x_i)(x_j-x_k)

i,jを入れ替えると、(-1)\times (-1)倍される。
(3) k\lt i\lt jとなるkに対し、


    (x_i-x_k)(x_j-x_k)

i,jを入れ替えると、そのまま。
(4) i\lt j\lt kとなるkに対し、


    (x_k-x_i)(x_k-x_j)

i,jを入れ替えると、そのまま。
(5) i,jが関係しない項は、i,jを入れ替えると、そのまま。
具体例を用いて、視覚的に説明する。n=7\tau=(3,6)の時、上の場合分けは図2の各部分に対応する。

f:id:camelsan:20210306122225p:plain
図1 差積

f:id:camelsan:20210306122304p:plain
図2 場合分けの対応

置換\sigmaが、互換の積として2通りに表されているとする。即ち


    \sigma = \tau_1\tau_2\dots\tau_k=\rho_1\rho_2\dots\rho_l

これを差積に作用させると


    \begin{split}
        \Delta^{\sigma}(x_1,x_2,\dots,x_n)&=\Delta^{\tau_1\tau_2\dots\tau_k}(x_1,x_2,\dots,x_n) \\
        &=(-1)^k\Delta(x_1,x_2,\dots,x_n) 
        \Delta^{\sigma}(x_1,x_2,\dots,x_n)&=\Delta^{\sigma_1\sigma_2\dots\sigma_k}(x_1,x_2,\dots,x_n) \\
        &=(-1)^l\Delta(x_1,x_2,\dots,x_n) 
    \end{split}

よって、 


    (-1)^k=(-1)^l

即ち、klが奇数か偶数かは一致しなくてはならない(一致しなければ、-1=1となり、矛盾)。

3. 置換の符号
行列式の定義で使用する、置換の符号を定義する。
置換\sigmaが偶数個の互換の積で表現されている時、偶置換、奇数個の互換の積として表現されている時、奇置換であるという。

置換の符号\rm{sgn}\sigmaを次のように定義する。


    \rm{sgn}\sigma=
    \begin{cases}
        1 & (\sigma \text{が偶置換}) \\
        -1 & (\sigma \text{が奇置換})
    \end{cases}

次の記事

camelsan.hatenablog.com

4. 参考文献
[1] 線型代数入門

[2] 差積

http://www2.kaiyodai.ac.jp/~yoshi-s/Lectures/LAlgebra/2015/DifferenceProduct.pdf

差積の互換の作用による符号の入れ替わりを図で説明されており、わかりやすいと思った。

[3] 差線形代数 第9回 置換

線形代数 第9回 置換

置換が互換の積で表現されることの証明で参考にした。本記事とは前から交換を実施して証明している点が異なるが、意味は同じ。但し、こちらの証明では、i=1の場合の証明が抜けている。