置換の分解 まとめ

これまで、任意の置換は互換の積で表せるということを $2$ 通りの方法で示してきました。ここでは、それぞれの証明の要旨を改めて整理するとともに、置換を互換の積として表す具体的な例を見ていきます。

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

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

• （$1$）置換を巡回置換の積で表し、更に巡回置換を互換の積に分解する方法
  • まず、定理 3.1により「任意の置換は、共通の元を持たない巡回置換の積で表せる」ことを示します。これは、$M_n$ の元 と $M_n$ 上の置換 $\sigma$ により、共通の元を持たない巡回置換が次々に切出せることにより示せます。
  • 次に、定理 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 \,)$ のように、ある巡回置換が具体的な互換の積の形で表せることを、計算により確認することで示せます。
  • 上の2つの命題により、任意の置換が互換の積として表せることが段階的に示されます。
• （$2$）巡回置換の積を経由せず、数学的帰納法により示す方法
  • 定理 3.3により $M_n$ 上の置換全体 $S_n$ について、$\sigma \in S_n$ が互換の積として表せることを数学的帰納法により示します。
    

1つ目の方法に比べて、2つ目の方法の方が証明としてシンプルです。線型代数学において、任意の置換が互換の積として表せることを証明する第一の動機は行列式を定義することですので、必ずしも巡回置換の概念を導入する必要はないともいえます。実際、巡回置換についての記載がない線型代数学の教科書もあります。

一方で、置換を巡回置換に分解することの効用は何かといえば、それは、具体的な計算にあるといえます。以下に具体例を挙げますが、ある置換が具体的に与えられたとき、それが互換の積として表せることが分かっていたとしても、どういった互換の積の形に分解できるかは一見して明らかではありません。そこで、まず置換を巡回置換の積に分解し、さらに巡回置換を互換の積に分解するという方法をとります。つまり、巡回置換を経由することで、置換を互換の積に分解する汎用的な手順が与えられるということです。この手順に則れば、どんな置換も互換の積の形に分解できるというわけですから、極めて強力な手順を得たことになります。

また、線型代数学の範囲を出ますが、巡回置換は代数学（群論）において基本的な事項でありますし、$1$ つ目の証明の考え方は、群による軌道（$\text{orbit}$）などの概念に通じます。これらの知識と結びついて、より深い理解につながる価値もあるといえます。

例（置換の分解）#

具体的に与えられた置換を、互換の積へ分解する手順を示します。ここでは例として、次のような $\sigma \in S_9$ を置換の積の形に分解することを考えます。

まず、定理3.1を用いて $\sigma$ を巡回置換の積の形に分解します。$1$ つの文字、例えば $1$ をとり、それが $\sigma$ によりどのように移っていくかを見ます。この場合、$1 \rightarrow 5 \rightarrow7 \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 \,)$ の積として表せることが分かりました。

次に、定理3.2を用いて、巡回置換を互換の積の形に分解します。$3$ つの巡回置換それぞれに対して、$(\, 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 \,)$ を適用していきますと、$(\, 1 \; 5 \; 7 \,) = (\, 1 \; 7 \,) \, (\, 1 \; 5 \,), \; (\, 2 \; 3 \; 9 \; 6 \,) = (\, 2 \; 6 \,) \, (\, 2 \; 9 \,) \, (\, 2 \; 3 \,), \; (\, 4 \; 8 \,) = (\, 4 \; 8 \,)$ となります。$(\, 4 \; 8 \,)$ は、もともと長さ $2$ の巡回置換、すなわち互換であるためそのままとします。

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

定理3.1と定理3.2の証明に付記したとおり、巡回置換の積は積の順序を除いて一意的に定まりますが、互換の積は一意的に定まりません。この例においては、例えば、$3$ つの巡回置換それぞれに対して $(\, i_1 \; i_2 \; \cdots \; i_m \,) = (\, i_{m-1} \; i_m \,) \, (\, i_{m-2} \; i_m \,) \; \cdots \; (\, i_2 \; i_m \,) \, (\, i_1 \; i_m \,)$ を適用すると、$(\, 1 \; 5 \; 7 \,) = (\, 5 \; 7 \,) \, (\, 1 \; 7 \,), \; (\, 2 \; 3 \; 9 \; 6 \,) = (\, 9 \; 6 \,) \, (\, 3 \; 6 \,) \, (\, 2 \; 6 \,), \; (\, 4 \; 8 \,) = (\, 4 \; 8 \,)$ となることから、次のような別解があります。

まとめ#

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

参考文献#