置換の分解（2）

任意の置換は互換の積で表せることを導きます。導出の方法は主に $2$ つあり、前項とこの項では $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 \,)$ のような互換を考えると、$i_1, \, i_2, \, \cdots, \, i_m$ について次が成り立つ。

すなわち、任意の $i \in \{ i_1, \, \cdots, \, i_m \}$ について $\sigma(i) = \tau_{m-1} \, \cdots \, \tau_{1} (i)$ であるから、次が成り立つ。

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

証明の骨子#

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

• 巡回置換 $\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} = (\, 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$ は（$1$ 度 $i_1$ に移った後）$i_3$ に、$i_3$ は $i_1$ に移ることが確かめられます。

      $$ \begin{array} {ccl} \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{array} $$

    • したがって、巡回置換 $(\, 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)$ 個の互換の積に等しいと考えられます。

• 上の考察から、$\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)$ を考えます。まず、$\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)$ を考えます。まず、$\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, \; i_4, \; \cdots$ についても、同様になると考えられます。最後に、$i_{m-1}, \; i_{m}$ の場合について見てみます。
    • $i_{m-1}$ について、$\tau_{m-1} \; \cdots \; \tau_{1} (i_{m-1})$ を考えます。まず、$\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})$ を考えます。まず、$\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)$ となることがわかります。
• 巡回置換による行き先と、（3.2.5）式の互換の積による行き先が一致していますので、巡回置換が互換の積として表せることが示されたといえます。

実は、巡回置換 $(\, 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 \,)$ だけではありません。例えば、$(\, i_{m-1} \; i_m \,) \, (\, i_{m-2} \; i_m \,) \; \cdots \; (\, i_2 \; i_m \,) \, (\, i_1 \; i_m \,)$ も、上の巡回置換と同じ行き先を持ちます。これも、上の証明と同様に計算により確かめられます。また、ここで挙げた $2$ つの互換の積は必要最小限である $(m-1)$ 個の互換の積ですが、もっと冗長な積の形は際限なく考えられます。つまり、任意の巡回置換は互換の積で表せるが、その表し方は一意的ではないということです。

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

まとめ#

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

参考文献#