置換の分解（1）

任意の置換は互換の積で表せることを導きます。導出の方法は主に $2$ つあり、この項と次項では $1$ つ目の方法（置換を巡回置換の積で表し、更に巡回置換を互換の積に分解する方法）について示します。まず、ここでは、任意の置換が巡回置換の積として表せることを示します。

巡回置換への分解#

まず、任意の置換が巡回置換の積として表せることを示します。

定理 3.1（置換と巡回置換）#

任意の置換は、共通の元を持たない巡回置換の積として表せる。

証明#

$M_n = \{\, 1, \cdots, n \,\}$ として、$\sigma$ を $M_n$ 上の置換とする。$M_n$ は有限なので、$i_1 \in M_n$ に対して $\sigma^{l} (i_1)= i_1$ となる正の整数 $l$ が存在する。このような正の整数のうち、最も小さいものを $r$ とする。すなわち、$\sigma^{r} (i_1)= i_1$ とする。このとき、$i_2 = \sigma (i_1), \; i_3 = \sigma^{2} (i_1), \; \cdots, \; i_r = \sigma^{r-1} (i_1)$ とおくと $\{ i_1, \cdots, i_r \}$ はすべて異なる元を持つ集合となる。仮に、$i_{p} = i_{q}$ となる $p, \, q \; (\, 1 \leqslant p \lt q \leqslant r \, )$ が存在するとすると、$\sigma^{p-1} (i_1) = i_p, \; \sigma^{q-1} (i_1) = i_q$ であるから $\sigma^{q-p} (i_1) = i_1$ となり、$r$ のとり方に矛盾する。よって、$M_n$ 上の長さ $r$ の巡回置換 $\sigma_{1} = (\, i_1 \; \cdots \; i_r)$ が定まる。同様にして、$j_1 \in M_n \backslash \{ i_1, \cdots, i_r \}$ に対して巡回置換が定まり、これを $\sigma_{2} = (\, j_1 \; \cdots \; j_s)$ とすると、$\sigma_{1}$ と $\sigma_{2}$ は共通の元を持たない。仮に、$\sigma_{1}$ と $\sigma_{2}$ に共通の元があり、これを $k$ とすると、$\sigma(i_u) = k, \sigma(j_v) = k$ を満たす $i_u, j_v \in M_n$ が存在することになるが、これは $\sigma$ が単射であることに矛盾する。この操作を繰り返すことで、共通の元を持たない巡回置換が次々に得られるが、$M_n$ は有限なので、得られる巡回置換も有限である。よって、任意の置換は共通の元を持たない巡回置換の積で表せる。$\quad \square$

証明の骨子#

数学的帰納法を使って考えます。

• まず、ある置換 $\sigma$ から1つの巡回置換が切出せることを示します。

  • $M_n$ から1つの元 $i_1$ をとって、$\sigma$ によってどのように移っていくかを見ますと、$i_1 \rightarrow \sigma(i_1) \rightarrow \sigma^{2} (i_1) \rightarrow \sigma^{3} (i_1) \rightarrow \cdots \rightarrow i_1$ のように、$i_1$ から始まった遷移は必ず $i_1$ に戻って閉じることに気付きます。

    • $M_n$ は有限なので、$\sigma$ による遷移 $i_1 \rightarrow \sigma(i_1) \rightarrow \sigma^{2} (i_1) \rightarrow \sigma^{3} (i_1) \rightarrow \cdots$ が無限に続くことは無いです。よって、この遷移はどこかで必ず閉じるといえます。
    • 遷移が閉じる箇所が $i_1$ ではないとすると、例えば $\sigma(i_{k_1-1}) = i_{k_1}, \sigma(i_{k_2}) = i_{k_1}$ となるような $i_{k_1} \neq i_{1}, i_{k_2}$ が存在するということになりますが、これは $\sigma$ が単射であることに矛盾します。下の図を書くとイメージしやすいかと思います。
      
    
    
    
    • よって、$i_1$ から始まった遷移が必ず $i_1$ に戻って閉じるといえます。

  • このことを、文字を使って表現すると $\sigma^{l} (i_1)= i_1$ となる正の整数 $l$ が存在する、と表すことができます。何周か回って $i_1$ に戻ってくる場合もあるので $l$ がとり得る値は複数考えられますが、そのうち最も小さいものを $r$ とします。
    

  
  
  

• 次に、切出される巡回置換に同じ元が含まれないことを示します。

  • 上に示した「$i_1$ から始まった遷移が必ず $i_1$ に戻って閉じること」と同じ考え方ですが、今度は $r$ のとり方との矛盾を導くことで示せます。
    • 仮に $\{\, i_1, \cdots i_r \,\}$ の中に同じ元が含まれるとすると、$i_{p} = i_{q}$ となる $p, \, q \; (\, 1 \leqslant p \lt q \leqslant r \, )$ が存在することになります。
    • このとき、$i_p, \, i_q$ の置き方から $\sigma^{p-1} (i_1) = i_p, \; \sigma^{q-1} (i_1) = i_q$ であるので、$\sigma^{q-p} (i_1) = i_1$ が成り立つといえます。これは、$\sigma^{p-1} (i_1) = \sigma^{q-1} (i_1)$ において、左辺 $\sigma^{p-1} (i_1)$ の $(p-1)$ 個前の要素 $i_1$ と、右辺 $\sigma^{q-1} (i_1)$ の $(p-1)$ 個前の要素 $\sigma^{(q-1)-(p-1)} (i_1)$ が等しいということを表しています。よって、$\sigma^{q-p} (i_1) = i_1$ となる $q-p \lt r$ が存在することになりますが、これは $r$ のとり方に矛盾します。
    • したがって、$\{\, i_1, \cdots i_r \,\}$ の中に同じ元は含まれないといえます。
    • このことは、$\sigma$ による遷移 $i_1 \rightarrow i_2 \rightarrow i_3 \rightarrow \cdots \rightarrow i_m \rightarrow i_1$ が描く環が途中に交点を持たないものであるということとしてイメージできます。
  • ここまでで、$i_1 \in M_n$ と $\sigma$ から1つの巡回置換が得られることが分かりました。

• 上の操作の繰り返しにより、共通元を持たない巡回置換が次々に得られることを示します。

  • 上の操作は、$M_n$ の1つの元 $i_1$ と $M_n$ 上の置換 $\sigma$ により、1つの巡回置換 $\sigma_{1}$ が得られることを示しています。また、$M_n$ の元のうち $\{ i_1, \cdots, i_r \}$ に含まれる元は巡回置換 $\sigma_{1}$ により切出されました。よって、残った元の集合、すなわち$M_n \backslash \{ i_1, \cdots, i_r \}$ について同様の操作を行うことで、また1つの巡回置換 $\sigma_{2}$ が得られることが分かります。
  • $\sigma_{1}$ と $\sigma_{2}$ が共通の元を持たないことを示します。
    • これは、厳密には $\sigma_{1}$ と $\sigma_{2}$ の巡回域 $\{ i_1, \cdots, i_r \}$ と $\{ j_1, \cdots, j_s \}$ に共通の元がないことを指していますが、命題に「$\cdots$ 共通の元を持たない巡回置換の $\cdots$」とあることから、巡回置換が元を持つという表現をしています。
    • これも背理法により示せます。仮に、$\sigma_{1}$ と $\sigma_{2}$ が共通の元を持つとすると、$\sigma_{1}$ による $i_1 \rightarrow i_2 \rightarrow \cdots$ という遷移と、$\sigma_{2}$ による $j_1 \rightarrow j_2 \rightarrow \cdots$ という遷移がどこかで交わることになりますが、これは $\sigma$ が単射であることに矛盾します。
    • よって、$\sigma_{1}$ と $\sigma_{2}$ は共通の元を持たないといえます。

• $\sigma$ が共通の元を持たない巡回置換の積で表せることを示します。

  • ここまで、$M_n$ の元と置換 $\sigma$ により共通元を持たない巡回置換が次々に得られることが分かりましたが、$M_n$ は有限ですので、上記の操作も有限回しか繰り返されません。これは、切出された巡回置換の長さを足していけば、いつか必ず $n$ に達するとも理解できます。すなわち、$r + s + \cdots = n$ となります。
  • 有限回の操作が終わったとき、$M_n$ のすべての元に対してある巡回置換により行き先が与えられることになりますので、$M_n$ 上の置換 $\sigma$ が有限個の巡回置換の積で表せる（置き換えられる）ことが分かります。
  • また、命題において明示的に言及されてはいませんが、$M_n$ 上の置換 $\sigma$ から得られる巡回置換の組 $\sigma_{1}, \sigma_{2}, \cdots$ は、元となる $\sigma$ のみによって定まるため、積の順序を除いて一意的であるといえます。

まとめ#

• 任意の置換は、共通の元を持たない巡回置換の積として表せる。
  
• この表し方は積の順序を除いて一意的に定まる。
  

参考文献#