置換の分解（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$

証明の考え方#

帰納的に考えます。ある置換から $1$ つの巡回置換を切り出せることを示し、この切り出しの操作を繰り返すことで、最終的に与えられた置換が巡回置換の積として表せることを示します。

置換から巡回置換を切り出す#

• まず、ある置換 $\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$ から始まった遷移は必ず $i_1$ に戻って閉じるといえます。
  • 遷移が閉じる箇所が $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$ が単射であること（置換の定義）に矛盾します。

• このことを、文字を使って表現すると $\sigma^{l} (i_1)= i_1$ となる正の整数 $l$ が存在する、と表すことができます。
• 何周か回って $i_1$ に戻ってくる場合もあるので $l$ がとり得る値は複数考えられますが、そのうち最も小さいものを $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)$ として、左辺の $(p-1)$ 個前の要素 $i_1$ と、右辺の $(p-1)$ 個前の要素 $\sigma^{(q-1)-(p-1)} (i_1)$ が等しいくなることから $i_1 = \sigma^{q-p} (i_1)$ が導かれます。
  • よって、$\sigma^{q-p} (i_1) = i_1$ となる $q-p \lt r$ が存在することになりますが、これは $r$ のとり方に矛盾します。
  • したがって、$\{\, i_1, \cdots i_r \,\}$ の中に同じ元は含まれないといえます。
• 以上から、$\sigma$ から $1$ つの巡回置換が切り出されることが分かりました。

巡回置換の切り出しを繰り返す#

• 上記の操作を繰り返すことで、新たに $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 \}$ に共通の元がないことを意味していますが、定理3.1に「$\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$ が有限個の巡回置換の積で表せる（置き換えられる）ことが分かります。
  • また、定理3.1において明示的に言及されてはいませんが、$M_n$ 上の置換 $\sigma$ から得られる巡回置換の組 $\sigma_{1}, \sigma_{2}, \cdots$ は、元となる $\sigma$ のみによって定まるため、積の順序を除いて一意的であるといえます。

まとめ#

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

参考文献#