置換の分解（3）

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

互換への分解#

前項まで、任意の置換が巡回置換の積で表すことができ、任意の巡回置換は互換の積として表せるというように、任意の置換が互換の積として表せることを $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 \,\}$ として、$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$ について考えていきます。
  • $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$ を考えます。すなわち $\tau = (\, n \; k \,)$ です。この互換 $\tau$ と、$n$ 文字の置換である $\sigma$ との積を考えると、$\tau \sigma (n) = n$ となります。これは、$n$ が、まず $\sigma$ によって $k$ に移り、$\tau$ によって $n$ に戻るということと理解できます。
    • $\tau$ を掛けることによって、$\sigma (n) = n$ の場合と同じ形に帰着できました。つまり、$\tau \sigma (n) = n$ となることより $\tau \sigma (n)$ は $(n-1)$ 文字の置換と捉えることができ、帰納法の仮定より、$\tau \sigma \in S_{n-1}$ は互換の積として表せるということです。具体的に $\tau \sigma = \eta_{1} \cdots \eta_{s}$ として、逆置換 $\tau^{-1}$ を作用させることで $\sigma = \tau^{-1} \eta_{1} \cdots \eta_{s} = \tau \eta_{1} \cdots \eta_{s}$ と変形できます。これは、$\sigma \in S_n$ が、$M_n$ 上の互換 $\tau$ と $M_{n-1}$ 上の互換 $\eta_{1} \cdots \eta_{s}$ の積として表せることを示しています。
      • ここで、互換の定義の項に示したように、互換の逆置換はその互換自身に等しく、$\tau^{-1} = \tau$ であることを用いています。
  • 以上から、$\sigma \in S_n$ についても、定理の主張が成り立つことが示されたといえます。

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

まとめ#

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

参考文献#