巡回置換と互換

この節では、任意の置換は互換の積で表せるということを導きます。

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

巡回置換の定義#

定義 3.5（巡回置換）#

$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$ の元のうち $i_1, \cdots, i_m \in M_n$ を $i_1 \rightarrow i_2 \rightarrow i_3 \rightarrow \cdots \rightarrow i_m \rightarrow i_1$ のように移し、他の元は動かさない置換が巡回置換であるといえます。$\sigma$ によって移される元は、$i_1 \rightarrow i_2, \; i_2 \rightarrow i_3, \; \cdots, \; i_{m-1} \rightarrow i_m$ と順々に移され、最後に $i_m \rightarrow i_1$ と戻ってくることから、巡回的（$\text{cyclic}$）な置換であるというイメージがつかめます。

細かい点ですが、$(\, 2 \leqslant m \leqslant n \,)$ という条件にも注意が必要です。元を巡回的に移していくために $m$ は $2$ 以上である必要があります。また、$m = n$ のときは、すべての $M_n$ の元が数珠繋ぎのように巡回的に移されます。次の互換の定義に述べる通り、$m = 2$ の場合、すなわち、長さ $2$ の巡回置換とは互換に他なりません。

また、便宜的に、$m = 1$ の場合、すなわち、長さ $1$ の巡回置換を定義し、これが恒等置換と同等であると説明している教科書もあります。この場合、巡回する元はありませんが、すべての元について $\sigma(j) = j$ であるので、上の定義とも整合します。したがって、恒等置換は巡回置換に含まれるといっても問題ないというわけです。つまり $(1) = \epsilon$ が成り立つということですが、長さ $1$ の巡回置換を示す $(1)$ という表記は他の表記（例えば、括弧に括られた数を表す（$1$）など）と混同しやすく誤解を招きやすいですし、恒等置換を表すには文字 $\epsilon$ を用いれば充分事足ります。したがって、長さ $1$ の巡回置換を示す $(1)$ という表記は以降なるべく使わないようにします。

表記#

定義の通り、巡回置換は $\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}$）行目のように、あくまで置換としても表せます。（$\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 = \{ 1, 2, \cdots, n \}$ とする。それぞれ異なる $M_n$ の元 $i, j$ について $\sigma(i) = j, \; \sigma(j) = i$ であり、他の $M_n$ の元 $k$ について $\sigma(k) = k$ である置換を、互換（$\text{transposition}$）といい、次のように表す。

すなわち、$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$ の元 $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$ の巡回置換といい、次のように表す。

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

  • それぞれ異なる $M_n$ の元 $i, j$ について $\sigma(i) = j, \; \sigma(j) = i$ であり、他の $M_n$ の元 $k$ について $\sigma(k) = k$ である置換を、互換といい、次のように表す。

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

  • 巡回置換と互換はともに置換の特別な場合であり、互換は長さ $2$ の巡回置換に等しい。
    

参考文献#