置換の分解（2）

任意の置換は互換の積として表すことができます。

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

巡回置換の互換への分解#

前項では、任意の置換が巡回置換の積として表せることを示しました（定理 3.1（置換と巡回置換））。

ここでは、任意の巡回置換が互換の積として表せることを示します。これらを合わせて、任意の置換が互換の積として表せることが示されるというわけです。

定理 3.2（巡回置換と互換）#

任意の巡回置換は互換の積として表せる。

証明#

巡回置換 $\sigma = (\, i_1 \; i_2 \; \cdots \; i_m \,)$ に対して、$\tau_{1} = (\, i_1 \; i_2 \,), \;\tau_{2} = (\, i_1 \; i_3 \,), \; \cdots, \; \tau_{m-1} = (\, i_1 \; i_m \,)$ のような互換を考える。これらの互換の積 $\tau_{m-1} \, \cdots \, \tau_{1}$ により、$i_1, \, i_2, \, \cdots, \, i_m$ はそれぞれ次のように移される。

すなわち、任意の $i \in \{ i_1, \, \cdots, \, i_m \}$ について $\sigma(i) = \tau_{m-1} \, \cdots \, \tau_{1} (i)$ が成り立つ。このとき、巡回置換 $\sigma$ は次のように互換の積として表すことができる。

したがって、任意の巡回置換は互換の積として表せる。$\quad \square$

証明の考え方#

巡回置換が（$\star$）式のような具体的な互換の積の形で表せることを示します。

$m = 3$ の場合など、長さの小さい巡回置換を互換の積として表す方法を考えて、これを一般化します。

巡回置換の分解（$m = 3$ の場合）#

• 巡回置換 $\sigma = (\, i_1 \; i_2 \; \cdots \; i_m \,)$ は、$i_1 \rightarrow i_2 \rightarrow i_3 \rightarrow \cdots \rightarrow i_m \rightarrow i_1$ のように、$\{\, i_1, i_2, \cdots, i_m \,\}$ の元をそれぞれ $1$ つ隣の元に移します。

• いま、巡回置換が $m$ 個の元を持つとすると、$m$ 個の元を順次 $1$ つずつ隣に移していくためには、$2$ つの元を入替える操作を少なくとも $(m-1)$ 回繰り返す必要があると考えられます。

• このことは、$m = 3$ の場合などの小さい巡回置換について考えるとよくわかります。

  • $m = 3$ として、巡回置換 $\sigma = (\, i_1 \; i_2 \; i_3 \,)$ について考えると、$\sigma$ により $i_1$ は $i_2$ に、$i_2$ は $i_3$ に、$i_3$ は $i_1$ に移ります。言い換えると、$\sigma$ は次のように置換と同じです（巡回置換の定義）。

    $$ \begin{align*} (\, i_1 \; i_2 \; i_3 \,) = \begin{pmatrix} i_1 & i_2 & i_3 \\ i_2 & i_3 & i_1 \end{pmatrix} \end{align*} $$

  • この置換は、次のような $2$ つの互換 $\tau_{1}, \tau_{2}$ の積により代替できます。すなわち、まず互換 $\tau_{1} = (\, i_1 \; i_2 \,)$ により $i_1$ と $i_2$ を入れ替え、次に互換 $\tau_{2} = (\, i_1 \; i_3 \,)$ により $i_1$ と $i_3$ を入れ替えます。この $2$ つの操作により $i_1$ は $i_2$ に、$i_2$ は（まず $i_1$ に移った後）$i_3$ に、$i_3$ は $i_1$ に移ることが確かめられます。

    $$ \begin{align*} \tau_{2} \; \tau_{1} (i_1) = \tau_{2} (i_2) = i_2 & \; \; \cdots \; \; i_1 \to i_2 \\ \tau_{2} \; \tau_{1} (i_2) = \tau_{2} (i_1) = i_3 & \; \; \cdots \; \; i_2 \to i_1 \to i_3 \\ \tau_{2} \; \tau_{1} (i_3) = \tau_{2} (i_3) = i_1 & \; \; \cdots \; \; i_3 \to i_1 \\ \end{align*} $$

  • したがって、巡回置換 $(\, i_1 \; i_2 \; i_3 \,)$ と $2$ つの互換の積 $(\, i_1 \; i_3 \,) (\, i_1 \; i_2 \,)$ は同じであることがわかります。

    $$ (\, i_1 \; i_2 \; i_3 \,) = (\, i_1 \; i_3 \,) (\, i_1 \; i_2 \,) $$

• 以上から、$m$ 個の要素の巡回置換は $(m-1)$ 個の互換の積として表すことができると考えられます。

巡回置換の分解（一般の場合）#

• 上記の考察から、長さ $m$ の巡回置換 $\sigma = (\, i_1 \; i_2 \; \cdots \; i_m \,)$ に相当する互換の積として $(\, i_1 \; i_m \,) \, (\, i_1 \; i_{m-1} \,) \; \cdots \; (\, i_1 \; i_3 \,) \, (\, i_1 \; i_2 \,)$ が考えられます。この互換の積による各要素の行き先が、巡回置換による行き先と一致していることを確かめます。
• $(m-1)$ 個の互換を $\tau_{1} = (\, i_1 \; i_2 \,), \;\tau_{2} = (\, i_1 \; i_3 \,), \; \cdots, \; \tau_{m-1} = (\, i_1 \; i_m \,)$ として、互換の積による $i_1, \; i_2, \; \cdots, \; i_m$ の像（行き先）をみていきます。

互換の積による $i_1$ の像#

• 互換の積による像 $\tau_{m-1} \; \cdots \; \tau_{1} (i_1)$ を考えます。

  $$ \begin{split} \tau_{m-1} \; \cdots \; \tau_{1} (i_1) &= \tau_{m-1} \; \cdots \; \tau_{2} (i_2) \\ &= i_2 \\ \end{split} $$
  • まず、$\tau_{1}$ により $i_1$ は $i_2$ に移ります。
  • 次に、$\tau_{m-1} \; \cdots \; \tau_{2} (i_2)$ を考えますが、$\tau_{m-1} \; \cdots \; \tau_{2}$ に $i_2$ は登場しませんので、これらの互換により、$i_2$ はどこにも移りません。

• よって、$\tau_{m-1} \; \cdots \; \tau_{1} (i_1) = i_2$ となります。これは $\sigma(i_1) = i_2$ と一致します。

互換の積による $i_2$ の像#

• 同様に $\tau_{m-1} \; \cdots \; \tau_{1} (i_2)$ を考えます。

  $$ \begin{split} \tau_{m-1} \; \cdots \; \tau_{1} (i_2) &= \tau_{m-1} \; \cdots \; \tau_{2} (i_1) \\ &= \tau_{m-1} \; \cdots \; \tau_{3} (i_3) \\ &= i_3 \\ \end{split} $$
  • まず、$\tau_{1}$ により $i_2$ は $i_1$ に移ります。
  • 次に、$\tau_{2}$ により $i_1$ は $i_3$ に移ります。
  • さらに、$\tau_{m-1} \; \cdots \; \tau_{3} (i_3)$ を考えますが、$\tau_{m-1} \; \cdots \; \tau_{3}$ により $i_3$ はどこにも移りません。

• よって、$\tau_{m-1} \; \cdots \; \tau_{1} (i_2) = i_3$ となります。これは $\sigma(i_2) = i_3$ と一致します。

互換の積による $i_3 \sim i_{m-2}$ の像#

• $i_3, \; i_4, \; \cdots$ についても、同様になると考えられます。
• 最後に、$i_{m-1}, \; i_{m}$ の場合について見てみます。

互換の積による $i_{m-1}$ の像#

• $\tau_{m-1} \; \cdots \; \tau_{1} (i_{m-1})$ を考えます。

  $$ \begin{split} \tau_{m-1} \; \cdots \; \tau_{1} (i_{m-1}) &= \tau_{m-1} \; \tau_{m-2} (i_{m-1}) \\ &= \tau_{m-1} (i_{1}) \\ &= i_m \\ \end{split} $$
  • まず、$\tau_{m-3} \; \cdots \; \tau_{1}$ により $i_{m-1}$ はどこにも移りません。よって、$\tau_{m-1} \; \cdots \; \tau_{1} (i_{m-1}) = \tau_{m-1} \; \tau_{m-2} (i_{m-1})$ となります。
  • 次に、$\tau_{m-2}$ により $i_{m-1}$ は $i_1$ に移ります。さらに、$\tau_{m-1}$ により $i_1$ は $i_m$ に移ります。

• よって、$\tau_{m-1} \; \cdots \; \tau_{1} (i_{m-1}) = i_m$ となります。これは $\sigma(i_{m-1}) = i_m$ と一致します。

互換の積による $i_{m}$ の像#

• $\tau_{m-1} \; \cdots \; \tau_{1} (i_{m})$ を考えます。

  $$ \begin{split} \tau_{m-1} \; \cdots \; \tau_{1} (i_{m}) &= \tau_{m-1} (i_{m}) \\ &= i_1 \\ \end{split} $$
  • まず、$\tau_{m-2} \; \cdots \; \tau_{1}$ により $i_{m}$ はどこにも移りません。よって、$\tau_{m-1} \; \cdots \; \tau_{1} (i_{m}) = \tau_{m-1} (i_{m})$ となります。
  • 次に、$\tau_{m-1}$ により $i_{m}$ は $i_1$ に移ります。

• よって、$\tau_{m-1} \; \cdots \; \tau_{1} (i_{m}) = i_1$ となります。これは $\sigma(i_{m}) = i_1$ と一致します。

互換の積による像（まとめ）#

• 以上から、任意の $i \in \{ i_1, \; i_2, \; \cdots, \; i_m \}$ について $\sigma(i) = \tau_{m-1} \; \cdots \; \tau_{1} (i)$ が成り立つことが確かめられました。
• 巡回置換による行き先と（$\star$）式の互換の積による行き先が一致していますので、巡回置換が互換の積として表せることが示されたといえます。

互換の積への分解は一意的ではない#

実は、巡回置換 $(\, i_1 \; i_2 \; \cdots \; i_m \,)$ を互換の積として分解した形は、上記の証明に示した、次のような形だけではありません。

例えば、次のような互換の積も、上記の巡回置換 $(\, i_1 \; i_2 \; \cdots \; i_m \,)$ と同じ行き先を持ちます。（上記の証明と同様に計算により確かめられます。）

また、ここで挙げた $2$ つの互換の積は必要最小限である $(m-1)$ 個の互換の積ですが、もっと冗長な積の形は際限なく考えられます。

すなわち、任意の巡回置換は互換の積で表せるが、その表し方は一意的ではないといえます。

置換の分解の一意性#

前項で示した通り、任意の置換が巡回置換の積として表すことができ、かつ、任意の巡回置換が互換の積として表せることが示されました。これらのことから、任意の置換が互換の積として表せることが示されたことになります。

また、任意の置換を巡回置換の積として表す方法は、積の順序を除いて一意的でしたが、巡回置換を互換の積として表す方法は一意的ではありません。結果として、任意の置換は互換の積で表せるが、その表し方は一意的ではないことが分かります。

まとめ#

• 任意の巡回置換は互換の積として表せる。
• 巡回置換を互換の積として表す表し方は一意的ではない。

参考文献#