置換の分解（3）

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

導出方法は主に $2$ つあり、ここでは $2$ つ目の方法（巡回置換の積を経由せず、数学的帰納法により示す方法）について示します。

互換への分解#

これまで、任意の置換が互換の積として表せることを $2$ 段階に分けて示してきました。

• 定理 3.1（置換と巡回置換）
• 定理 3.2（巡回置換と互換）

すなわち、まず置換を巡回置換の積に分解し、次に巡回置換を互換の積に分解するというような手順により、結果として、任意の置換が互換の積に分解できることを示しました。

これに対して、本項では、任意の置換がただちに（巡回置換の積を経由せず）互換の積に分解できることを、数学的帰納法を使って示します。

定理 3.3（置換の分解）#

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

証明#

$M_n = \{\, 1, 2, \cdots\, n \,\}$ として、$M_n$ 上の置換全体の集合を $S_n$ とする。

$n = 2$ のとき、$S_2 = \{ (\, 1 \; 2 \,), (\, 2 \; 1 \,) \}$ であるが $(\, 1 \; 2 \,), (\, 2 \; 1 \,)$ は互換に他ならない。よって、定理の主張が成り立つ。

$n \gt 2$ のとき、$S_{n-1}$ について命題の主張が成り立つと仮定する。ある置換 $\sigma \in S_n$ について、$\sigma(n) = n$ であれば、$\sigma \in S_{n-1}$ となり、帰納法の仮定より $\sigma$ は互換の積として表せる。また、$\sigma(n) = k \; (\neq n)$ であれば、$\tau = (\, n \; k \,)$ に対して $\tau \sigma (n) = n$ が成り立つ。このとき、$\tau \sigma \in S_{n-1}$ となることから、帰納法の仮定より $\tau \sigma$ は互換の積で表せる。これを $\tau \sigma = \eta_{1} \cdots \eta_{s}$ とすると、$\sigma = \tau^{-1} \eta_{1} \cdots \eta_{s}$ であり、$\tau^{-1} = \tau$ であることから、$\sigma = \tau \eta_{1} \cdots \eta_{s}$ が成り立つ。したがって、この場合も $\sigma$ は互換の積として表せる。 $\quad \square$

証明の考え方#

$M_n = \{\, 1, 2, \cdots\, n \,\}$ として、$M_n$ 上の置換について考えます。

$n$ に関する数学的帰納法を使って証明します。$n = 2$ の場合は、互換の定義より明らかといえます。$n \gt 2$ の場合、更に数学的帰納法により、$S_{n-1}$ で主張が成り立つと仮定して $S_{n}$ の場合も主張が成り立つことを示します。

$n = 2$ の場合の証明#

• 互換の定義より明らかといえます。
  • 互換とは $M_n$ の $2$ つの元を入れ替え、他の元は動かさないような置換です。
• $n = 2$ の場合、$M_2 = \{\, 1, 2 \,\}$ であるので、$M_2$ 上の置換全体の集合 $S_2$ は $\{\, (\, 1 \; 2 \,), (\, 2 \; 1 \,) \,\}$ となりますが、$(\, 1 \; 2 \,), (\, 2 \; 1 \,)$ はともに互換です。
• したがって、$n = 2$ の場合、任意の置換は互換の積として表せるといえます。

$n \gt 2$ の場合の証明#

• 数学的帰納法により、$S_{n-1}$ で主張が成り立つと仮定し、$S_{n}$ の場合も主張が成り立つことを示します。
  • 帰納法の仮定は、$M_{n-1} = \{ 1, 2, \cdots, (n-1) \}$ 上の任意の置換が互換の積として表せる、ということです。
  • すなわち、任意の $\sigma \in S_{n-1}$ について定理の主張が成立し、$\sigma = \eta_{1} \cdots \eta_{s}$ のように表せるということを仮定しています。
  • ここで、$\eta_i \; (1 \leqslant i \leqslant s)$ は $M_{n-1}$ 上の互換を表しています。
  • このような仮定の下、$\sigma \in S_n$ について考えていきます。
• $\sigma \in S_n$ は $M_n$ 上の置換ですので、帰納法の仮定が成り立つ $M_{n-1} = \{ 1, 2, \cdots, (n-1) \}$ に $n$ を追加した集合の上の置換と捉え、追加した文字 $n$ の行き先により、場合分けをします。

$\sigma(n) = n$ となる場合#

• この場合、追加した文字 $n$ は自分自身に移ることになります。
• つまり、$n$ 文字の置換として導入した $\sigma \in S_n$ は、実は $(n-1)$ 文字の置換 $\sigma \in S_{n-1}$ であるということになります。
• 帰納法の仮定より、$(n-1)$ 文字の置換において定理の主張が成り立ちますので、$\sigma \in S_n$ についても定理の主張が成り立つといえます。

$\sigma(n) = k \; (\neq n)$ となる場合#

• この場合、追加した文字 $n$ は $k \; (\neq n)$ に移ります。

• ここで、$n$ とその行き先である $k$ を入れ替える互換 $\tau = (\, n \; k \,)$ を考えます。

• $\tau$ と $\sigma$ との積について、$\tau \sigma (n) = n$ が成り立ちます。すなわち、文字 $n$ は、まず $\sigma$ によって $k$ に移り、$\tau$ によって $n$ に戻るということです。

  $$\begin{split} \tau \sigma (n) &\overset{(\text{i})}{=} \tau (k) \\ &\overset{(\text{ii})}{=} n \\ \end{split}$$
  • （$\text{i}$）文字 $n$ は $\sigma$ によって $k$ に移ります（ $\sigma(n) = k$ ）。
  • （$\text{ii}$）文字 $k$ は $\tau = (\, n \; k \,)$ によって $n$ に移ります。

• $\tau \sigma (n) = n$ が成り立つことより、$\tau \sigma (n)$ は $(n-1)$ 文字の置換であると捉えることができ、帰納法の仮定より、$\tau \sigma \in S_{n-1}$ は互換の積として表せることがわかります。（$\sigma (n) = n$ の場合と同じ形に帰着しました。）
• $\tau \sigma$ を具体的な互換の積として表し、$\sigma$ も互換の積として表せることを導きます。

  • いま、$\tau \sigma$ を $s$ 個の互換の積として、次のように表せたとします。

    $$\begin{equation*} \tau \sigma = \eta_{1} \cdots \eta_{s} \end{equation*}$$

  • このとき、$\tau \sigma$ と $\tau^{-1}$（$\tau$ の逆置換）の積は、次のようになります。

    $$\begin{split} \tau^{-1} \tau \sigma &\overset{(\text{i})}{=} \tau^{-1} \eta_{1} \cdots \eta_{s} \\ \sigma &\overset{(\text{ii})}{=} \tau^{-1} \eta_{1} \cdots \eta_{s} \\ &\overset{(\text{iii})}{=} \tau \eta_{1} \cdots \eta_{s} \end{split}$$
    • （$\text{i}$）上記の $\tau \sigma$ の式に左から $\tau^{-1}$ を掛けます。
    • （$\text{ii}$）$\tau^{-1} \tau = \epsilon$ であることによります（$\epsilon$ は恒等置換）。
    • （$\text{iii}$）$\tau^{-1} = \tau$ であることによります。任意の互換の逆置換は、その互換自身に等しくなります（互換の定義）。

  • これは、$\sigma \in S_n$ が（$M_n$ 上の）互換 $\tau$ と（$M_{n-1}$ 上の）互換 $\eta_{1} \cdots \eta_{s}$ の積として表せることを示しています。

• 以上から、$\sigma \in S_n$ についても、定理の主張が成り立つことが示されたといえます。

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

前項に示した通り、置換を互換の積として表す方法は一意的ではないという点に注意が必要です。

上記の $n \gt 2$ の場合の証明からもわかる通り、置換 $\sigma$ に対して互換 $\tau$ のとり方（選び方）は任意です。

まとめ#

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

参考文献#