置換群

数学において、置換群とは、与えられた集合 Mの置換を要素とし、その群演算がG内の置換の合成である群 G のことである(置換は集合Mからそれ自身への全単射関数とみなされる)。集合Mのすべての置換の群は、 Mの対称群であり、しばしば Sym( M ) と表記される。^{[ 1 ]}したがって、置換群という用語は、対称群の部分群を意味する。M = {1, 2, ..., n }の場合、 Sym( M ) は通常 S _nと表記され、n 文字の対称群と呼ばれることがある。

ケイリーの定理によれば、すべての群は何らかの置換群と同型である。

置換群の要素が集合の要素を置換する方法を群作用と呼びます。群作用は、対称性、組み合わせ論、その他多くの数学、物理学、化学の分野で応用されています。

置換群は対称群の部分群です。つまり、その要素は与えられた集合の置換です。したがって、置換の合成に関して閉じており、恒等置換を含み、各要素の逆置換を含む対称群の部分集合です。 ^{[ 2 ]}有限群の一般的な性質から、対称群の有限の空でない部分集合が置換群であるのは、置換の合成に関して閉じている場合に限ることがわかります。^{[ 3 ]}

有限集合の順列群の次数は、その集合の要素の数です。群（任意の種類）の位数は、その群の要素の数（濃度）です。ラグランジュの定理によれば、次数nの任意の有限順列群の位数はn !を割り切る必要があります。なぜなら、nの階乗は対称群S _nの位数だからです。

順列は集合の全単射であるため、コーシーの2行記法で表すことができます。^{[ 4 ]}この記法では、1行目にMの各要素を列挙し、2行目に各要素について、その下の順列による像を列挙します。${\displaystyle \sigma }$は集合の順列である${\displaystyle M=\{x_{1},x_{2},\ldots ,x_{n}\}}$それから、

${\displaystyle \sigma ={\begin{pmatrix}x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\sigma (x_{1})&\sigma (x_{2})&\sigma (x_{3})&\cdots &\sigma (x_{n})\end{pmatrix}}.}$

例えば、集合 {1, 2, 3, 4, 5} の特定の順列は次のように書くことができます。

${\displaystyle \sigma ={\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}};}$

これは、σ がσ (1) = 2、σ (2) = 5、σ (3) = 4、σ (4) = 3、σ (5) = 1 を満たすことを意味します。M の要素は最初の行に特別な順序で現れる必要はないため、同じ順列は次のように書くこともできます。

${\displaystyle \sigma ={\begin{pmatrix}3&2&5&1&4\\4&5&1&2&3\end{pmatrix}}.}$

順列は、サイクル表記（巡回形式）^{[ 5 ]}でもよく表記されます。例えば、集合M = {1, 2, 3, 4}に対して、 g (1) = 2、g (2) = 4、g (4) = 1、 g (3) = 3 となるMの順列gは、(1, 2, 4)(3) と表記されます。より一般的には、3 は変更されないため、(1, 2, 4) と表記されます。対象が単一の文字または数字で表される場合、コンマやスペースも省略でき、(124) のような表記になります。上記の 2 行表記で書かれた順列は、サイクル表記では次のように表記されます。${\displaystyle \sigma =(125)(34).}$

2 つの順列の積は、関数としてのそれらの合成として定義されるので、${\displaystyle \sigma \cdot \pi }$は、集合の任意の要素xを にマッピングする関数です。${\displaystyle \sigma (\pi (x))}$. 関数合成の書き方により、最も右側の順列が最初に引数に適用されることに注意してください。^{[ 6 ] [ 7 ]}一部の著者は、最も左側の因子が最初に作用することを好みますが、そのためには順列を引数の右側に、多くの場合上付き文字として記述する必要があります。したがって、順列は${\displaystyle \sigma }$要素に作用する${\displaystyle x}$画像の結果${\displaystyle x^{\sigma }}$この慣例では、積は次のように表されます。$${\displaystyle x^{\sigma \cdot \pi }=(x^{\sigma })^{\pi }}$$^{[ 8 ] [ 9 ] [ 10 ]}ただし、これは順列の乗算に関する異なる規則を与えます。この慣例は順列群の文献でよく使われますが、この記事では右端の順列を最初に適用する慣例を使用します。

2 つの全単射の合成は常に別の全単射を与えるため、2 つの順列の積は再び順列になります。2 行表記では、2 つの順列の積は、2 番目の (左端) 順列の列を並べ替えて、その最初の行が最初の (右端) 順列の 2 行目と同一になるようにすることによって得られます。積は、最初の順列の最初の行を修正された 2 番目の順列の 2 行目の上に記述できます。たとえば、順列が与えられた場合、

${\displaystyle P={\begin{pmatrix}1&2&3&4&5\\2&4&1&3&5\end{pmatrix}}\quad {\text{ および }}\quad Q={\begin{pmatrix}1&2&3&4&5\\5&4&3&2&1\end{pmatrix}},}$

製品QPは以下のとおりです。

${\displaystyle QP={\begin{pmatrix}1&2&3&4&5\\5&4&3&2&1\end{pmatrix}}{\begin{pmatrix}1&2&3&4&5\\2&4&1&3&5\end{pmatrix}}={\begin{pmatrix}2&4&1&3&5\\4&2&5&3&1\end{pmatrix}}{\begin{pmatrix}1&2&3&4&5\\2&4&1&3&5\end{pmatrix}}={\begin{pmatrix}1&2&3&4&5\\4&2&5&3&1\end{pmatrix}}.}$

順列をサイクル表記で表した場合、その合成は2つの順列を並べ（2番目の順列を左側に書く）、必要に応じて互いに素なサイクル形式に簡略化することによって得られます。したがって、上記の積は次のように表されます。

${\displaystyle Q\cdot P=(15)(24)\cdot (1243)=(1435).}$

関数の合成は結合法則を満たすため、順列に対する積演算も結合法則を満たす。${\displaystyle (\sigma \cdot \pi )\cdot \rho =\sigma \cdot (\pi \cdot \rho )}$したがって、2つ以上の順列の積は、通常、グループ化を表す括弧を追加せずに記述されます。また、通常、乗算を示すドットやその他の記号も追加せずに記述されます（前の例のドットは強調のために追加されたものであり、単純に次のように記述されます）。${\displaystyle \sigma \pi \rho }$)

集合のすべての要素をそれ自身に写像する恒等置換は、この積のニュートラル要素です。2行表記では、恒等置換は

${\displaystyle {\begin{pmatrix}1&2&3&\cdots &n\\1&2&3&\cdots &n\end{pmatrix}}.}$

サイクル表記では、e = (1)(2)(3)...( n ) であり、慣例として単に (1) または () と表記されることもあります。^{[ 11 ]}

全単射には逆元が存在するため、順列にも逆元が存在し、 σの逆元σ ⁻¹もまた順列です。具体的には、σ ( x )= yの場合には必ずσ ⁻¹ ( y )= x も成り立ちます。2 行表記では、逆元は 2 行を入れ替えることで得られます (最初の行を特定の順序にしたい場合は列をソートします)。例えば、

${\displaystyle {\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}^{-1}={\begin{pmatrix}2&5&4&3&1\\1&2&3&4&5\end{pmatrix}}={\begin{pmatrix}1&2&3&4&5\\5&1&4&3&2\end{pmatrix}}.}$

1 つのサイクルの逆を取得するには、その要素の順序を逆にします。したがって、

${\displaystyle (125)^{-1}=(521)=(152).}$

サイクルの積の逆数を得るには、まずサイクルの順序を逆にして、次に上記のようにそれぞれの逆数を取ります。したがって、

${\displaystyle [(125)(34)]^{-1}=(34)^{-1}(125)^{-1}=(43)(521)=(34)(152)。}$

結合法則を満たす積、単位元、およびすべての要素の逆元を持つことで、Mのすべての順列の集合は群Sym( M )となり、順列群となります。

集合M = {1, 2, 3, 4}の順列の集合G _{1 を}以下のように考えます。

• e = (1)(2)(3)(4) = (1)
  • これは恒等式であり、各要素を固定する自明な置換である。
• a = (1 2)(3)(4) = (1 2)
  • この順列は1と2を入れ替え、3と4を固定する。
• b = (1)(2)(3 4) = (3 4)
  • 前回と同様だが、3と4を入れ替えて、他の部分を修正する。
• ab = (1 2)(3 4)
  • この順列は、前の2つの順列を組み合わせたもので、1と2、そして3と4を同時に交換する。

G _{1 は}aa = bb = e、ba = ab、abab = eであるため、群を形成します。この置換群は、抽象群としてクライン群V ₄です。

別の例として、正方形の対称群を考えてみましょう。正方形の頂点を 1、2、3、4 とします (左上隅の 1 から始めて、正方形の周りを反時計回りに)。対称性は頂点の像によって決定され、それはさらに置換によって記述できます。正方形の中心を中心とした 90° (反時計回り) の回転は、置換 (1234) で記述されます。180° と 270° の回転は、それぞれ (13)(24) と (1432) で与えられます。中心を通る水平線に関する反射は (12)(34) で与えられ、対応する垂直線に関する反射は (14)(23) です。1、3 の対角線に関する反射は (24) で、2、4 の対角線に関する反射は (13) です。残りの対称性は恒等 (1)(2)(3)(4) のみです。この置換群は、抽象群としては位数8の二面体群として知られている。

上記の正方形の対称群の例では、置換は対称群によって誘導される正方形の頂点の動きを「記述」します。これらの群要素が正方形の頂点の集合に「作用」していると言うのが一般的です。この考え方は、群作用を形式的に定義することでより正確にすることができます。^{[ 12 ]}

Gを群、M を空でない集合とする。GのMへの作用とは、以下の関数f : G × M → Mのことである。

• f (1, x ) = x、すべてのx ∈ Mに対して(1 は群Gの単位元 (中立元) である)、
• f ( g , f ( h , x )) = f ( gh , x ) 、すべてのg , h ∈ Gおよびすべてのx ∈ Mに対して。

この2つの条件は、その作用がGからSym ( M )への群準同型を誘導するという意味で表現することもできます。 ^{[ 12 ]}このような準同型は、 M上のGの（置換）表現と呼ばれます。

任意の置換群に対して、( g , x ) → g ( x )を送る作用は、 Mに対するGの自然作用と呼ばれます。特に断りのない限り、この作用が想定されます。^{[ 12 ]}正方形の対称群の例では、頂点の集合に対する群の作用が自然作用です。ただし、この群は正方形内の 4 つの三角形の集合 ( t ₁ = 234、t ₂ = 134、t ₃ = 124、t ₄ = 123) にも作用します。また、2 つの対角線 ( d ₁ = 13、d ₂ = 24) にも作用します。

集合Mに対する群Gの作用は、 Mの任意の 2 つの要素s、tに対して、 g ( s ) = tとなるような群要素gが存在する場合に推移的であると言われます。同等に、集合M はGの作用の下で単一の軌道を形成します。^{[ 13 ]}上記の 例のうち、{1, 2, 3, 4} の順列の群 {e, (1 2), (3 4), (1 2)(3 4)} は推移的ではありません (どの群要素も 1 から 3 に対応しません) が、正方形の対称群は頂点に関して推移的です。

任意の群G は、自身 (群の要素を集合Mと考える) に対して様々な方法で作用することができます。特に、群内では (左) 乗法によって与えられる正則な作用があります 。つまり、すべてのgとx ∈ Gに対してf ( g , x ) = gx が成り立ちます。固定された各gに対して、関数f _g ( x ) = gxはG上の全単射であり、したがってGの要素の集合の置換となります。このようにして、 Gの各要素は置換と考えることができ、したがってGは置換群と同型です。これがケイリーの定理の内容です。

例えば、上記の集合 {1, 2, 3, 4} に作用する群G _{1を考えてみましょう。この群の要素を}e、a、bと表し、 c = ab = baとします。ケイリーの定理で説明されているG ₁自身への作用は、次の置換表現を与えます。

f _e ↦ ( e )( a )( b )( c )

f _a ↦ ( ea )( bc )

f _b ↦ ( eb )( ac )

f _c ↦ ( ec )( ab ) 。

GとH がそれぞれ作用f ₁とf ₂を持つ集合XとY上の 2 つの置換群である場合、全単射写像λ : X → Yと群同型ψ : G → Hが存在し、  

λ ( f ₁ ( g , x )) = f ₂ ( ψ ( g ), λ ( x )) は、すべてのg ∈ Gおよびx ∈ Xに対して成り立つ。^{[ 14 ]}

X = Yの場合、これはGとH がSym( X ) の部分群として共役であることと同等である。^{[ 15 ]} G = Hでψ が恒等写像である特殊なケースは、群の同値作用の概念を生み出す。 ^{[ 16 ]}

上記の正方形の対称性の例では、集合 {1,2,3,4} に対する自然作用は、三角形に対する作用と等価です。集合間の全単射λはi ↦ t _iで与えられます。上記の群G ₁の自然作用と、それ自身に対する作用 (左乗法による) は、自然作用には固定点があり、2 番目の作用には固定点がないため、等価ではありません。

グループGが集合Sに作用する場合、その作用は S の要素の n 組からなるデカルト積 S n に自然に拡張できます。要素gがn組( ^s 1 , ... , _s n )_に作用する場合、次のようになります。

g ( s ₁ , ..., s _n ) = ( g ( s ₁ ), ..., g ( s _n ))。

群Gは、 S ⁿ上の作用がすべての正の整数nに対して有限個の軌道しか持たない場合に、オリゴモルフィックであると言われる。^{[ 17 ] [ 18 ]} （ Sが有限の 場合はこれは自動的に成り立つので、この用語は通常、 Sが無限の場合に興味がある。）

オリゴモルフィック群への関心は、例えば可算圏論における自己同型を考える場合など、モデル理論への応用に基づいている部分もある。^{[ 19 ]}

群の研究はもともと置換群の理解から発展した。^{[ 20 ]}置換自体は、1770年にラグランジュが多項式方程式の代数的解法に関する研究の中で集中的に研究していた。この分野は発展し、19世紀半ばには、カミーユ・ジョルダンが1870年に著した『置換と代数方程式論』で体系化した、よく発達した置換群の理論が存在した。ジョルダンの著書は、1832年にエヴァリスト・ガロアが残した論文に基づいていた。

ケイリーが抽象群の概念を導入したとき、それが既知の置換群（現代の定義とは異なる定義を持っていた）よりも大きな対象の集合であるかどうかはすぐには明らかではなかった。ケイリーはケイリーの定理で、この2つの概念が同等であることを証明した。^{[ 21 ]}

置換群に関する章がいくつか含まれている別の古典的なテキストは、バーンサイドの1911年の『有限位数の群の理論』である。 ^{[ 22 ]} 20世紀前半は群論全般の研究が停滞していた時期であったが、置換群への関心は1950年代にH.ヴィーラントによって復活し、彼のドイツ語の講義ノートは1964年に『有限置換群』として再版された。^{[ 23 ]}

• 2-推移群
• ランク3の順列群
• マチューグループ

• マイケル・アーティン(1991)、代数、プレンティス・ホール、ISBN 0-13-004763-5
• キャメロン、ピーター・J. (1994)『組み合わせ論：トピック、テクニック、アルゴリズム』ケンブリッジ大学出版局、ISBN 0-521-45761-0
• ディクソン、ジョン・D.、モーティマー、ブライアン（1996）、『順列群』、大学院数学テキスト163、シュプリンガー・フェルラーク、ISBN 0-387-94599-7
• ロットマン、ジョセフ・J. (2006)、『応用を伴う抽象代数学入門』（第3 版）、ピアソン・プレンティス・ホール、ISBN 0-13-186267-7

• アコス・セレス著『順列群アルゴリズム』ケンブリッジ数学論文集152巻、ケンブリッジ大学出版局、ケンブリッジ、2003年。
• Meenaxi Bhattacharjee、Dugald Macpherson、Rögnvaldur G. Möller、Peter M. Neumann。「無限置換群に関するノート」。数学講義ノート第1698巻。Springer-Verlag、1998年。
• Peter J. Cameron著。『順列群』。LMS学生用テキスト45。ケンブリッジ大学出版局、ケンブリッジ、1999年。
• ピーター・J・キャメロン著『オリゴモルフィック置換群』ケンブリッジ大学出版局、ケンブリッジ、1990年。

• 「置換群」、数学百科事典、EMS Press、2001年 [1994年]
• Alexander Hulpke。GAPデータライブラリ「推移的置換群」Wayback Machineに2021年1月19日にアーカイブされました。