巡回置換と互換

この節では、任意の置換が互換の積として表せることを示します。

その準備として、ここでは巡回置換と互換を定義します。巡回置換と互換は、ともに置換の特別な場合といえます。また、互換は長さ $2$ の巡回置換であるといえます。

巡回置換の定義#

定義 3.5（巡回置換）#

$M_n$ を $n$ 個の文字からなる集合 $M_n = \{ 1, 2, \cdots, n \}$ とする。それぞれ異なる $M_n$ の元 $i_1, \cdots, i_m \; (\, 2 \leqslant m \leqslant n \,)$ について $\sigma(i_1) = i_2, \; \sigma(i_2) = i_3, \; \cdots, \; \sigma(i_{m-1}) = i_m, \; \sigma(i_m) = i_1$ であり、他の $M_n$ の元 $j$ について $\sigma(j) = j$ である置換を、長さ $m$ の巡回置換（$\text{cyclic permutation}$）といい、次のように表す。

解説#

巡回置換により移される元#

巡回置換とは、$M_n$ の元のうち $m$ 個の元（ $i_1, \cdots, i_m$ ）を $i_1 \rightarrow i_2 \rightarrow i_3 \rightarrow \cdots \rightarrow i_m \rightarrow i_1$ のように巡回的（$\text{cyclic}$）に移し、他の元は動かさないような置換です。

$\sigma$ によって移される元は、$i_1 \rightarrow i_2, \; i_2 \rightarrow i_3, \; \cdots, \; i_{m-1} \rightarrow i_m$ と順々に移され、最後に $i_m \rightarrow i_1$ と戻ってきます。

巡回置換の条件（$2 \leqslant m \leqslant n$）#

細かい点ですが、巡回置換の定義には $(\, 2 \leqslant m \leqslant n \,)$ という条件がある点に注意が必要です。すなわち、元を巡回的に移していくために $m$ は $2$ 以上である必要があるということです。

$m = 2$ の場合、巡回置換は、特に $2$ つの元を入れ替え、他の元を動かさないような置換となります。これは、次に定義する互換に他なりません。すなわち、長さ $2$ の巡回置換は互換と同じといえます。

$m = n$ の場合、巡回置換は、すべての $M_n$ の元が数珠繋ぎのように巡回的に移します。

巡回置換と恒等置換（$m = 1$ の場合）#

上の定義において、$m = 1$ の場合を巡回置換の定義から外しています。$m = 1$ の場合、すなわち長さ $1$ の巡回置換は、$M_n$ のすべての元をどこへも移さない（恒等置換と同じになる）からです。

便宜的に $m = 1$ の場合を定義に含め、長さ $1$ の巡回置換は恒等置換と同等であるとしている教科書もあります。仮に、上の定義において $m = 1$ の場合を含めても、整合性という点では問題ないです。

したがって、どちらの定義を採っても大きな違いはありませんが、ここでは表記のわかりやすさの観点から、$m = 1$ の場合を含まない定義を採用します。例えば、長さ $1$ の巡回置換を示す $(1)$ や $(i)$ という表記は誤解を招きやすい（括弧に括られた文字（$1$）や（$i$）と見分けがつかない）ですし、恒等置換を表すには $\epsilon$ で事足ります。

置換としての表記#

定義の通り、巡回置換は $\sigma = (\, i_1 \; i_2 \; \cdots \; i_m \,)$ のように表されます。これは、次のように置換として表すことができます。

（$\text{i}$）行目は、巡回置換の定義に則った表記であり、$M_n$ の元のうち $i_1 \rightarrow i_2 \rightarrow i_3 \rightarrow \cdots \rightarrow i_{m-1} \rightarrow i_m \rightarrow i_1$ と巡回する元のみを並べたものです。

（$\text{ii}$）行目は、巡回置換をあくまで置換として表したものです。巡回置換 $( \, i_1 \; i_2 \; \cdots \; i_m \, )$ と同値な置換ともいえます。すなわち、$i_1, \cdots, i_m \in M_n$ については $i_1 \rightarrow i_2, \; i_2 \rightarrow i_3, \; \cdots, \; i_{m-1} \rightarrow i_m, \; i_m \rightarrow i_1$ と巡回的に移し、他の $j_1, \cdots, j_{n-m} \in M_n$ については動かさない、という対応を明示的に示したものです。

巡回置換を改めて置換として表す（$\text{ii}$）行目のような表記は一見冗長ではありますが、ときに便利です。例えば、巡回置換どうしの積や巡回置換と別の置換の積を計算する際など、丁寧に計算を進められますので、このような表現の置き換えを知っておくと便利です。

巡回置換の例#

置換を巡回置換として表す#

巡回置換の具体的な例をみます。いま、次のような置換が与えられたとして、これを巡回置換として表すことを考えます。

この置換は、例えば $1$ から始めて $1 \rightarrow 5 \rightarrow 3 \rightarrow 1$ と巡回しており、$2, 4$ は動かないことがわかります。よって、これは巡回置換であり、$\sigma = (\, 1, \; 5,\; 3 \,)$ と表すことができます。

同じ循環置換の異なる表記#

他の文字から始めても同等の巡回置換が得られるはずです。例えば、$3$ から始めれば $\sigma = (\, 3, \; 1,\; 5 \,)$ であり、$5$ から始めれば $\sigma = (\, 5, \; 3,\; 1 \,)$ となります。つまり、

が成り立ちます。このことからも、巡回置換は、文字が巡回する順序が変わらない限り、どの文字から始めても表記上問題ないことが分かります。

異なる循環置換の表記#

一方で、同じ文字の循環置換でも、文字が巡回する順序が異なる場合、まったく異なる巡回置換になります。例えば、同じ文字 $1, 3, 5$ についての巡回置換であっても、次のように、異なる巡回置換が得られます。

このことは、それぞれの巡回置換を置換の形で表し直してみるとよくわかります。

互換の定義#

定義 3.6（互換）#

$M_n$ を $n$ 個の文字からなる集合 $M_n = \{ 1, 2, \cdots, n \}$ とする。それぞれ異なる $M_n$ の元 $i, j$ について $\sigma(i) = j, \; \sigma(j) = i$ であり、他の $M_n$ の元 $k$ について $\sigma(k) = k$ である置換を、互換（$\text{transposition}$）といい、次のように表す。

解説#

互換は長さ $2$ の巡回置換#

互換とは、$M_n$ の元のうち $i$ と $j$ だけを入れ替えて、他の元はそのまま動かさない置換です。

また、$\sigma$ により $i \rightarrow j \rightarrow i$ のように移されると捉えれば、互換は長さ $2$ の巡回置換であるといえます。

置換としての表記#

定義の通り、互換は $\sigma = (\, i \; j \,)$ のように表されます。これは、次のように置換として表すことができます。

巡回置換と同様に、（$\text{i}$）行目のように $M_n$ のうち入れ替わる元である $i$ $j$ のみを使って互換を表すことができますが、（$\text{ii}$）行目のように、あくまで置換としてこれを表すこともできます。

（$\text{ii}$）行目の表記は、$i$ と $j$ を入れ替え、他の元は動かさない、という対応を明示的に示したものです。

同じ互換の異なる表記#

互換により入れ替わる元は $2$ つしかありませんので、明らかに次が成り立ちます。

互換を表す際は、入替る文字のどちらから並べて表記しても問題ありません。

また、この式は、互換について $\sigma = \sigma^{-1}$ が成り立つことを示しているとも理解できます。$\sigma^{-1}$ は対称群の定義において導入した逆置換であり、任意の互換の逆置換は、その互換自身に等しいということができます。

まとめ#

• $M_n = \{ 1, 2, \cdots, n \}$ とする。

  • $M_n$ の元のうち $m$ 個の元を $i_1 \rightarrow i_2 \rightarrow i_3 \rightarrow \cdots \rightarrow i_m \rightarrow i_1$ のように巡回的に移し、他の元は動かさないような置換を巡回置換といい、次のように表す。

    $$ \begin{align*} \sigma = ( \, i_1 \; \cdots \; i_m \, ) \end{align*} $$

  • $M_n$ の元のうち $i$ と $j$ だけを入れ替えて、他の元はそのまま動かさない置換を互換といい、次のように表す。

    $$ \begin{align*} \sigma = (\, i \; j \,) \end{align*} $$

  • 長さ $2$ の巡回置換は互換に等しい。

参考文献#