置換の分解 まとめ

これまで、任意の置換が互換の積で表せるということを $2$ 通りの方法で示してきました。

ここでは、それぞれの証明の要旨を整理するとともに、具体的に与えられた置換を互換の積として表す方法と例をみていきます。

置換の分解（2通りの証明）#

任意の置換が互換の積として表せることは、主に次の $2$ 通りの方法により示すことができます。

（1）巡回置換への分解#

まず置換が巡回置換の積に分解できることを示し、次に巡回置換が互換の積に分解できることを示します。これを合わせて、任意の置換が互換の積に分解できることを段階的に示します。

証明の流れ#

• まず、「任意の置換が、共通の元を持たない巡回置換の積で表せる」ことを示します（ 定理 3.1（置換と巡回置換））。
  • ある置換から $1$ つの巡回置換を切り出せることを示します。
  • この切り出しの操作を繰り返すことで、最終的に、与えられた置換が共通の元を持たない巡回置換の積として表せることを示します。
• 次に、「任意の巡回置換が互換の積として表せる」ことを示します（ 定理 3.2（巡回置換と互換））。

  • 巡回置換が（例えば）次のような具体的な互換の積の形で表せることを示します。

    $$ \begin{gather*} (\, 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 \,) \end{gather*} $$

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

• 上記 $2$ つの命題を合わせて、任意の置換が互換の積として表せることが段階的に示されます。

関連する定理#

（2）数学的帰納法#

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

証明の流れ#

• $M_n = \{\, 1, 2, \cdots\, n \,\}$ 、$M_n$ 上の置換全体の集合を $S_n$ として、任意の $\sigma \in S_n$ について主張が成り立つことを示します。
• $n$ に関する数学的帰納法を使って証明します。
  • $n = 2$ の場合、 互換の定義より明らかといえます。
  • $n \gt 2$ の場合、更に数学的帰納法により、$S_{n-1}$ で主張が成り立つと仮定して $S_{n}$ の場合も主張が成り立つことを示します。

関連する定理#

2通りの証明の違いと使い分け#

数学的帰納法の利点#

（1）巡回置換への分解に比べて、 （2）数学的帰納法による証明の方が文章量も少なくシンプルな証明です。

また、 （2）数学的帰納法を採用する利点として、巡回置換という概念を用いずに証明できるという点もあります。

線型代数学において、任意の置換が互換の積として表せることを証明する主な動機は行列式を定義することです。この目的を達するためであれば、必ずしも巡回置換の概念を導入する必要はありません。実際、巡回置換についての記載がない線型代数学の教科書もあります。

したがって、単に「任意の置換が互換の積として表せる」ことを示すためには （2）数学的帰納法による証明の方が優れています。

巡回置換への分解の利点#

一方で、置換を巡回置換に分解することの利点は具体的な計算にあります。

ある置換が具体的に与えられたとき、それが互換の積として表せることが分かっていたとしても、実際にどのような互換の積の形に分解できるかは一見して明らかではありません（下記の 例題を参照）。

そこで （1）巡回置換への分解の流れに沿った手順が有用になってきます。すなわち、まず置換を巡回置換の積に分解し、さらに巡回置換を互換の積に分解するという手順により、具体的に与えられた置換に等しい互換の積を得ることができます。

（1）巡回置換への分解の手順に則れば、どんな置換も互換の積の形に分解できるというわけですから、極めて強力な手順を得たことになります。 （1）巡回置換への分解の証明の利点は、この点にあります。

具体的に与えられた置換を互換の積に分解する手順については、以下の 例に示す通りです。

置換の分解（例）#

具体的に与えられた置換を互換の積として表します。

例題（置換の分解）#

次の $\sigma \in S_9$ を互換の積として表せ。

解答（分解の手順）#

巡回置換への分解#

まず、 定理 3.1（置換と巡回置換）を用いて $\sigma$ を巡回置換の積として表します。

• $1$ つの文字、例えば $1$ をとり、それが $\sigma$ によりどのように移っていくかを見ます。この場合、$1 \rightarrow 5 \rightarrow 7 \rightarrow 1$ となり巡回しました。
• 次に、残りの文字について、同様に $\sigma$ によりどのように移っていくかを見ますと、$2 \rightarrow 3 \rightarrow 9 \rightarrow 6 \rightarrow 2$、$4 \rightarrow 8 \rightarrow 4$ となります。
• これで文字はすべてなので、$\sigma$ は、$3$ つの巡回置換 $(\, 1 \; 5 \; 7 \,), \; (\, 2 \; 3 \; 9 \; 6 \,), \; (\, 4 \; 8 \,)$ の積として表せることがわかりました。
  $$ \begin{split} \sigma &= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 5 & 3 & 9 & 8 & 7 & 2 & 1 & 4 & 6 \\ \end{pmatrix} \\ &= \begin{pmatrix} 1 & 5 & 7 \end{pmatrix} \begin{pmatrix} 2 & 3 & 9 & 6 \end{pmatrix} \begin{pmatrix} 4 & 8 \end{pmatrix} \end{split} $$

互換への分解#

次に、 定理 3.2（巡回置換と互換）を用いて、巡回置換を互換の積の形に分解します。

• 上記 $3$ つの巡回置換それぞれに対して次の式を適用し、互換の積の形にします（ 定理 3.2）。

  $$ (\, 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 \,) $$

• $3$ つの巡回置換は、それぞれ次のようになります。$(\, 4 \; 8 \,)$ はもともと長さ $2$ の巡回置換（すなわち互換）であるため、そのままにします。

  $$ \begin{align*} (\, 1 \; 5 \; 7 \,) &= (\, 1 \; 7 \,) \, (\, 1 \; 5 \,), \\ (\, 2 \; 3 \; 9 \; 6 \,) &= (\, 2 \; 6 \,) \, (\, 2 \; 9 \,) \, (\, 2 \; 3 \,), \\ (\, 4 \; 8 \,) &= (\, 4 \; 8 \,) \end{align*} $$

• 式を整理すると、次のようになります。

  $$ \begin{split} \sigma &= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 5 & 3 & 9 & 8 & 7 & 2 & 1 & 4 & 6 \\ \end{pmatrix} \\ &= \begin{pmatrix} 1 & 5 & 7 \end{pmatrix} \begin{pmatrix} 2 & 3 & 9 & 6 \end{pmatrix} \begin{pmatrix} 4 & 8 \end{pmatrix} \\ &= \begin{pmatrix} 1 & 7 \end{pmatrix} \begin{pmatrix} 1 & 5 \end{pmatrix} \begin{pmatrix} 2 & 6 \end{pmatrix} \begin{pmatrix} 2 & 9 \end{pmatrix} \begin{pmatrix} 2 & 3 \end{pmatrix} \begin{pmatrix} 4 & 8 \end{pmatrix} \\ \end{split} $$

以上から、もとの置換 $\sigma$ が互換の積の形に分解できました。

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

定理 3.1（置換と巡回置換）と 定理 3.2（巡回置換と互換）の証明にも付記したとおり、巡回置換の積は積の順序を除いて一意的に定まりますが、互換の積は一意的に定まりません。

例えば、上記の例題において、巡回置換を互換に分解する際に次の式を適用した場合、

$3$ つの巡回置換は次のようになります。

すなわち、上記の例題には、次のような別解があります。

まとめ#

• 任意の置換が互換の積として表せることは、主に次の $2$ 通りの方法により示すことができる。
  • （$1$）置換を巡回置換の積で表し、更に巡回置換を互換の積に分解する方法。
  • （$2$）巡回置換の積を経由せず、数学的帰納法により示す方法。
• （$1$）は具体的な計算手順として便利、（$2$）は証明としてシンプル。

参考文献

[1] 齋藤正彦. 線型代数入門. 東京大学出版会. 1966.
[2] 永田雅宣 他. 理系のための線型代数の基礎. 紀伊國屋書店. 1986.
[3] 川久保勝夫. 線形代数学 [新装版]. 日本評論社. 2010.
[4] 松坂和夫. 線型代数入門 [新装版]. 岩波書店. 2018.
[5] 三宅敏恒. 線形代数学 初歩からジョルダン標準形へ. 培風館. 2008.
[6] S. Lang. Linear Algebra Third Edition. Springer. 1987.
[7] T. Miyake. Linear Algebra From the Beginnings to the Jordan Normal. Springer. 2022.
[8] 雪江明彦. 代数学 $1$ 群論入門. 日本評論社. 2010.
[9] 雪江明彦. 代数学 $2$ 環と体とガロア理論. 日本評論社. 2010.
[10] 桂利行. 代数学 $\text{I}$ 群と環. 東京大学出版会. 2004.
[11] 松坂和夫. 代数系入門. 岩波書店. 1976.
[12] 高木貞治. 代数学講義 [改訂新版]. 共立出版. 1965.
[13] S. Lang. Algebra Revised Third Edition. Springer. 2002.
[14] M. Artin. Algebra Second Edition. Pearson Education Limited. 2014.
[15] 青本和彦 他. 数学入門辞典. 岩波書店. 2005.