【線型代数学入門】置換 - ベイジアン研究所

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$ 文字の置換という。整数１の対応先を $i_1$ 、整数２の対応先を $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_m$ が $S_n$ の重複のない全ての置換とすると、 $\sigma_1^{-1},\dots,\sigma_m^{-1}$ も $S_n$ の重複のない全ての置換である。
(2) $\tau$ を固定された一つの $n$ 文字の置換とする。 $\sigma_1,\dots,\sigma_m$ が $S_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$ 文字を動かさないような置換のことを、互換と呼ぶことにする。入れ替えられる文字を $i$ と $j$ とすると、この互換を２文字のみで、 $(i,j)$ と書くことができる。例えば、４文字の置換に対して、

$\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$ 以下の時成立すると仮定して、 $\sigma$ を $n+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$ の時、 $\sigma$ は $n$ 文字の置換であり、これは帰納法の仮定より、互換の積として表すことができる。 $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 — 図１差積

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

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

$\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}$