巡回置換

数学、特に群論では、巡回置換とは、単一のサイクルからなる置換のことである。 ^{[ 1 ] [ 2 ]}場合によっては、巡回置換はサイクルと呼ばれる。^{[ 3 ]}巡回置換がk個の要素を持つ場合、 kサイクルと呼ばれることがある。一部の著者は、この定義を拡張して、最大で 1 つの非自明なサイクルに加えて、固定点を持つ置換も含むようにしている。^{[ 3 ] [ 4 ]}サイクル記法では、巡回置換は、置換された順序で括弧で囲まれた要素のリストで表される。

例えば、1 を 3、3 を 2、2 を 4、4 を 1 に置き換える置換 (1 3 2 4) は 4 サイクルであり、1 を 3、3 を 2、2 を 1、4 を 4 に置き換える置換 (1 3 2)(4) は、一部の著者によって 3 サイクルとみなされています。一方、1 を 3、3 を 1、2 を 4、4 を 2 に置き換える置換 (1 3)(2 4) は、{1, 3} と {2, 4} のペアを別々に置換するため、巡回置換ではありません。

固定点を許容する巡回置換のより広い定義では、これらの固定点はそれぞれ置換の自明な軌道を構成し、残りのすべての点を含む単一の非自明な軌道が存在する。これは定義として使用できる。巡回置換（固定点を許容）とは、単一の非自明な軌道を持つ置換である。有限個の要素上のすべての置換は、非自明な軌道が互いに素である巡回置換に分解できる。^{[ 5 ]}

順列の個々の循環部分はサイクルとも呼ばれ、したがって2番目の例は3サイクルと1サイクル（または不動点）で構成され、3番目の例は2つの2サイクルで構成されています。

巡回置換の正確な定義については広く合意が得られていない。一部の著者は、集合Xの置換σが巡回であると定義するのは、「連続適用によって、置換された集合の各オブジェクトが他のすべてのオブジェクトの位置を順に通過する」場合である^{[ 1 ]}または同等に、サイクル表記での表現が単一のサイクルで構成される場合である^{[ 2 ]}としている。他の著者は、固定点を許容する、より寛容な定義を提供している^{[ 3 ] [ 4 ] 。}

Xの空でない部分集合Sはサイクルである${\displaystyle \sigma }$制限がある場合${\displaystyle \sigma }$Sへの はSの巡回置換である。X が有限である場合、そのサイクルは互いに素であり、それらの和集合はXである。つまり、それらは分割を形成し、これを のサイクル分解と呼ぶ。${\displaystyle \sigma .}$したがって、より寛容な定義によれば、 Xの順列が巡回的であるのは、 Xがその唯一の巡回である場合に限る。

例えば、順列は、サイクル表記と2行表記（2つの方法）で次のように表されます。

${\displaystyle {\begin{aligned}(1\ 4\ 6\ &8\ 3\ 7)(2)(5)\\&={\begin{pmatrix}1&2&3&4&5&6&7&8\\4&2&7&6&5&8&1&3\end{pmatrix}}\\&={\begin{pmatrix}1&4&6&8&3&7&2&5\\4&6&8&3&7&1&2&5\end{pmatrix}}\end{aligned}}}$

1つの6サイクルと2つの1サイクルを持つ。そのサイクル図は右に示すとおりである。この順列を巡回的と考える著者もいれば、そうでない著者もいる。

定義を拡大すると、単一のサイクルで構成されない循環順列も存在する。

より厳密には、拡張された定義では、順列${\displaystyle \sigma }$集合Xの、全単射関数として見た場合${\displaystyle \sigma :X\to X}$は、によって生成される部分群のXに対する作用がサイクルと呼ばれる。${\displaystyle \sigma }$は、複数の要素を持つ軌道を最大で 1 つ持つ。^{[ 6 ]}この概念は、X が有限集合である場合に最も一般的に使用される。この場合、最大の軌道Sも有限である。$s0$Sの任意の要素とし、$\displaystyle s_{i}=\sigma ^{i}(s_{0})}$いかなる場合でも${\displaystyle i\in \mathbf {Z} }$Sが有限であれば、最小数が存在する。${\displaystyle k\geq 1}$そのために$\displaystyle s_{k}=s_{0}}$。 それから${\displaystyle S=\{s_{0},s_{1},\ldots ,s_{k-1}\}}$、 そして${\displaystyle \sigma }$は、

$\displaystyle \sigma (s_{i})=s_{i+1}}$0 ≤ i < kの場合

そして${\displaystyle \sigma (x)=x}$のどの要素に対しても${\displaystyle X\setminus S}$固定されていない要素${\displaystyle \sigma }$次のようにイメージできる

$\displaystyle s_{0}\mapsto s_{1}\mapsto s_{2}\mapsto \cdots \mapsto s_{k-1}\mapsto s_{k}=s_{0}}$。

巡回置換は、簡潔なサイクル表記を用いて記述することができる。${\displaystyle \sigma =(s_{0}~s_{1}~\dots ~s_{k-1})}$（この表記では、 kタプルとの混同を避けるため、要素間にコンマは使用しません。）サイクルの長さは、その最大の軌道の要素数です。長さkのサイクルは、 kサイクルとも呼ばれます。

1サイクルの軌道は置換の固定点と呼ばれますが、置換としてはすべての1サイクルは恒等置換です。^{[ 7 ]}サイクル表記を使用する場合、混乱が生じない場合は1サイクルは省略されることがよくあります。^{[ 8 ]}

対称群に関する基本的な結果の 1 つは、任意の置換は互いに素なサイクル (より正確には、互いに素な軌道を持つサイクル) の積として表現できるということです。このようなサイクルは互いに可換であり、置換の表現はサイクルの位数を除いて一意です。^{[ a ]}この表現におけるサイクルの長さの多重集合(サイクル型) は、置換によって一意に決定され、対称群における置換の符号と共役類の両方がそれによって決定されます。^{[ 9 ]}

対称群S _nにおけるkサイクルの数は、${\displaystyle 1\leq k\leq n}$以下の等価な式によって表されます。 $${\displaystyle {\binom {n}{k}}(k-1)!={\frac {n(n-1)\cdots (n-k+1)}{k}}={\frac {n!}{(nk)!k}}.}$$

kサイクルはシグネチャ(−1) ^{k − 1}を持つ。  

サイクルの逆${\displaystyle \sigma =(s_{0}~s_{1}~\dots ~s_{k-1})}$エントリの順序を逆にすることで得られます。${\displaystyle \sigma ^{-1}=(s_{k-1}~\dots ~s_{1}~s_{0})}$特に、${\displaystyle (a~b)=(b~a)}$2つのサイクルはそれぞれ自身の逆元である。互いに素なサイクルは可換であるため、互いに素なサイクルの積の逆元は、それぞれのサイクルを個別に反転させた結果となる。

2 つの要素のみを持つサイクルは転置と呼ばれます。たとえば、順列${\displaystyle \pi ={\begin{pmatrix}1&2&3&4\\1&4&3&2\end{pmatrix}}}$これは2と4を入れ替える。2サイクルなので、次のように書ける。${\displaystyle \pi =(2\ 4)}$。

• サイクルソート– ソート対象の順列をサイクルに分解し、各サイクルを個別に回転させることでソート結果を得るという考えに基づいたソートアルゴリズム。
• サイクルと固定点
• 整数の巡回置換
• サイクル表記
• タンパク質における環状置換
• フィッシャー・イェーツ・シャッフル

この記事は、PlanetMathの cycle の資料を組み込んでおり、Creative Commons Attribution-Share-Alike Licenseの下でライセンスされています。