置換 (数学)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/05/01 00:16 UTC 版)
群論的取扱い
群論においてある集合上の置換は、その集合からその集合自身の上への全単射を言う[2]。任意に与えられた集合の上の置換全体の成す集合は、写像の合成を積として、恒等変換を単位元とする群を成し、これを S の対称群と呼ぶ[4]。対称群は、同型を除いてその集合の濃度のみに依存して決まり、S の元の具体的な特徴がどうであるかは群構造に影響を与えない[5]。対称群は有限集合上のものを考えることがほとんどで、この場合には適当な自然数 n に対して S = {1, 2, …,n} であるとして一般性を失わない。こうして n 次の対称群 Σn が定まる。
対称群の任意の部分群を置換群と呼ぶ[6]。ケイリーの定理により、実は任意の群が何らかの置換群に同型であり[7]、特に有限群は何らかの有限対称群の部分群に同型であることがわかる。しかし置換群は、抽象群よりも多くの構造を持つものであり、たとえば置換群の任意の元には巡回置換型を定義することができるが、置換群として実現されたのではない群がこれと同値な付加構造をもつことは必ずしも求められない。例えば、Σ3 は自然に置換群となり、その任意の互換は巡回型が (2,1) となるが、ケイリーの定理の証明に従って Σ3 を Σ6 の部分群として(つまり、Σ3 自身に属する全 6 個の元の置換として)実現すれば、この置換群での互換の巡回置換型は (2, 2, 2) になる。つまり、ケイリーの定理の成立にも拘らず、置換群の研究は抽象群の研究とは異なる部分を持っているということになる。
記法について
有限集合 S の置換に対して、その記法は大きく三種類が存在する。1815年、コーシーによって導入された[8]二行記法[訳語疑問点]は一行目に S の元を書き、その各元の下に置換による像を書いて二行目とするものである。例えば、集合 {1, 2, 3, 4, 5} のある置換は
第三の記法として置換の巡回置換表現[10]は、置換を続けて施す効果に焦点を当てたものになっている。これは、置換を(少なくとも二つの元を持つ)軌道に対応する巡回置換の積として表す方法である。相異なる軌道は互いに素(交わりを持たない)から、感覚的には「互いに素な巡回置換に分解する」方法とも言える。このような記法を得るには、以下のようにする。まず S の元 x を σ(x) ≠ x なるようにとり、σ を繰り返し施して得られる像の列 (x σ(x) σ(σ(x)) …) を、像として x が現れるまで続ける。こうして書き下された値の集合は σ に関して x の属する軌道であり、得られた列はこの軌道に対応する σ の巡回置換成分の括弧書き記法になる。この後、既に書き下された軌道に属さない S の元 y があればそれを取って σ(y) ≠ y であるならば、同様にして対応する巡回置換成分が得られるから、以下これを繰り返して、S の任意の元が何れかの巡回置換に属するかさもなくば σ の不動点となるまで続ける。この手続きにおいて、新しい巡回置換を作るための始点とする元の取り方は一通りとは限らないから、一つの置換に対する巡回置換表示は、一般には複数存在する。例えば、やはり先と同じ例で言えば
置換の乗法を置換の巡回置換表現のもとで書くための平易なパターンというものは存在せず、積の巡回置換表示に現れる巡回置換は、積を取る個々の置換に現れる巡回置換とは全く異なるものになってしまう。しかし、置換 σ に対して別の置換 π による共軛変換を取る、つまり積 πσπ−1 を作る特別の場合においては、巡回置換構造が保たれる。共軛変換で得られた置換の巡回置換表示は、σ の巡回置換表示に現れる各成分に π を施したものとして与えられる[13]。
集合 {1, 2, …, n} 上の置換を n 次正方行列として表すこともできる。これを行うのに自然な方法は二種類あるが、行列の積が置換の積に同じ順番で対応するのはそのうちの一方だけである。このとき、置換 σ には i = σ(j) のとき mi j = 1 でそれ以外のとき mi j = 0 となるような行列 M = [mi j ] が対応し、σ に対応する置換行列と呼ばれる。
- ^ N. L. Biggs, The roots of combinatorics, Historia Math. 6 (1979) 109−136
- ^ a b 鈴木 1977, p. 53, 定義 7.1.
- ^ Bóna 2012, p. 1, Definition 0.1.
- ^ 鈴木 1977, p. 54.
- ^ 鈴木 1977, p. 54, (7.2).
- ^ 鈴木 1977, p. 55, 定義 7.3.
- ^ 鈴木 1977, p. 55, (7.4).
- ^ Kleiner 1986, p. 202.
- ^ 成嶋 2003, p. 88.
- ^ 成嶋 2003, p. 145.
- ^ 鈴木 1977, pp. 284–285, 定義 2.5.
- ^ a b 鈴木 1977, p. 285, (2.6).
- ^ Humphreys 1996, p. 84.
- ^ Bóna 2004, p. 3.
- ^ Bóna 2012, pp. 4f.
- ^ Bóna 2012, p. 53, Definition 2.1.
- ^ Bóna 2004, pp. 43ff.