対称群
出典: フリー百科事典『ウィキペディア（Wikipedia）』
数学における対称群（たいしょうぐん、symmetric group）とは、「ものを並べ替える」という操作を元とする群である。この場合の「ものの並べ替え」を置換（ちかん、permutation）といい、対称群のことを置換群（ちかんぐん、permutation group）と呼ぶこともある。数学の議論の様々な場面で「番号づけられて並んでいるものを入れ替える」「入れ替えの可能性すべてをしらべる」ことが問題となり、対称群はそのような議論を定式化するために用いられる。
目次 |
[編集] 定義
集合 n = {0, 1, 2, ..., n − 1} に対し、n から n への全単射全体の集合を Sn とおくと、写像の合成を積と定義することで、Sn は群になることがわかる。これはn 次の対称群と呼ばれ、Sn の元は n 次の置換とよばれる。
X を有限集合 とするとき、n の場合と同様にして X から X への全単射全体の集合を Sym(X) とおくと、写像の合成を積として Sym(X) は群になる。このとき、Sym(X) は X の対称群または置換群とよばれる。有限集合の間の単射 X → Y に対して対称群の間の単射 Sym(X) → Sym(Y) が自然に定まる。特に、X に含まれる元の個数（X の濃度）が n のとき、、集合X と集合 n は同一視でき（つまり、この集合と X とのあいだに全単射が存在する）、同一視の仕方（全単射の選び方）に応じてSym(X) と Sym(n) との間に群の同型対応が定まる。
無限集合についての対称群にあたるものとして二つの異なった概念が挙げられる。ひとつめの概念は有限集合 X に対する Sym(X) の構成をそのまま拡張し、有限とは限らない集合 Y に対しても Y から Y への全単射全体のなす群を考えることによって得られる。もう一つのより繊細な概念は、有限とは限らない集合 Y に対して、その有限部分集合全体のなす族 F を考え、有限対称群たち Sym(X) (X ∈ F) の直極限
として得られる群である。この二つの定式化は有限集合に対しては自然に同型な群を与えている。自然数の集合 N に対して二つ目の方法を適用して得られる群は S∞ と書かれ、無限対称群と呼ばれる。これは Sn たちすべての合併と見なすことができる。
[編集] 諸概念
[編集] 互換
置換のうち、特に 2 つの元のみを入れ替えて他の元は変えないものを互換という。任意の置換は互換の積として表される。そのような表し方は一通りとはかぎらないが、表示にあらわれる互換の数が偶数であるか奇数であるか（偶奇性、パリティ）は表し方に依らずに決まる。偶数個の互換の積として表される置換のことを偶置換 (even permutation) といい、奇数個の互換の積として表される置換のことを奇置換 (odd permutation) という。n 次対称群の元のうち特に偶置換のみを集めると、その全体は n 次対称群の正規部分群となる。この群のことを n 次交代群 といい、An と表す。n が5以上のとき、 n 次交代群はより小さな群の合成としては表せなくなっており、このことから 5 次以上の方程式に代数的な解の公式が存在しないことが説明される（ガロア理論）。
[編集] 順列との対応
点列 (x1, x2, ..., xn) を入れ替える写像としての n 次置換 σ に対応するグラフは、組 (xk, σ(xk)) を k = 0, 1, 2, ..., n − 1 に対して集めた有限集合であり、これはしばしば
あるいは
のように記される[1]。後者の記法は番号の入れ替えとしての σ の表示を与えており、これは点列 (σ(0), σ(1), ..., σ(n − 1)) であって、順列と呼ばれる。こうして n 次の置換と n 文字の順列とを自然に同一視できるので、n 次対称群の位数は n の階乗 n! であることがわかる。また、偶置換に対応する順列は偶順列、奇置換に対応する順列は奇順列と呼ばれる。
[編集] 置換行列
n 次の対称群をベクトル空間の基底の変換として作用させることで置換を行列表示することができる。具体的に n 次元のベクトル空間 V とその基底 {e1, e2, ..., en} をひとつ固定して、置換 σ の V への作用を
- σ(ei) = eσ(i)
(1 ≤ i ≤ n) によって定める。このとき σ の表現行列を Pσ とすると
- σ(e1, e2, ..., en) = (eσ(1), eσ(2), ..., eσ(n)) = (e1, e2, ..., en)Pσ
から、クロネッカーのデルタ δ を用いて Pσ = (δiσ(j)) となる。この行列 Pσ を、置換 σ に対応する置換行列（ちかんぎょうれつ、permutation matrix）という。偶置換に対応する置換行列の定める線型変換は空間の向きを保ち、一方で奇置換に対応する線型変換は空間の向きを反転させている。
[編集] 符号
n次の置換 σ について、σ の符号 (signature) と呼ばれる ±1 の数 sgn(σ) を定めることができる。sgn(σ) の定義にはいくつかの方法がある。
- sgn(σ) = (−1)d(σ)、ただし d(σ) は n の元 iのうちで σ(i) < i となっているものの数で、σ の転倒数と呼ばれる。
- σ が偶置換のとき sgn(σ) = 1, σ が奇置換のとき sgn(σ) = −1。つまり σ が k 個の互換の積で表せるとき sgn(σ) = (−1)k。
- σ が表す置換行列を Xσ とするとき、Xσ の行列式によって sgn(σ) = det(Xσ)。
- n 変数の差積 Δ = ∏0≤i<j<n (Xi − Xj) に対して、∏0≤i< j<n (Xσ(i) − Xσ(j)) = sgn(σ)Δ。
sgn は Sn から位数 2 の群 {±1} への準同型を定めており、二つ目の定式化からも明らかなように交代群はこの符号写像の核として特徴づけられる。
[編集] 共役類
群に関する基本的な問題としてその共役類の分類が挙げられるが、対称群 Sn における共役類は Sn の n への自然な作用に関する軌道の形によって分類される。実際、σ と τ が Sn の元ならば σ と τστ−1 は同じ軌道の形を持っており、逆に σ と υ が同じ軌道の形を持つならばある τ ∈ Sn について υ = τστ−1 となっている。たとえば、n = 3 で
- σ: 0 → 1, 1 → 0, 2 → 2,
- τ: 0 → 1, 1 → 2, 2 → 0
のとき、σ の軌道は {0, 1} と {2} であり、一方 τστ−1 の軌道は {0} と {1, 2} で、どちらも一つの元からなる軌道を一つと二つの元からなる軌道を一つ持っている。
このように、軌道の形は各自然数 k に対して k 個の元を持つような軌道の数 mk がいくつかを指定することで決定される。このとき、集合 n への作用を考えているので数列 (mk)k は ∑k∈N kmk = n を満たさなければならない。このような数列は位数 n のヤング図形と一対一に対応しており、したがって Sn の共役類は位数 n のヤング図形たちによって記述されることになる。
[編集] 数学教育における置換
初等・中等教育における置換の応用問題として，カードのシャッフル，あみだくじ，平面図形の置換，15ゲームなどがあげられる。
[編集] カードのシャッフル
1982年に麻布中に出たものが初出であろう。その後しばらくは中学入試には出題されなかったが、2002年に東京大学で出題されたのち2004年から2006年にかけて出題され始めた。
[編集] あみだくじ
あみだくじの1つの横棒が1つの互換を表すので，あみだくじによって一般の置換が表現できることになる。中学入試では十余年前から出題されている。算数オリンピクの影響という説も有力である，数字や文字のならべ換えを置換のモデルとして出題するのは，1970年代のカリキュラムへの現代数学的なトピックの導入時にみられた。
[編集] 15ゲームもどき
15ゲームとは，4×4=16のスペースの中に1から15までの数が1つずつ書かれた正方形のこまをスライドさせるソリティアスライディングゲームを言う。中学入試では，その縮小版と見られる，2×2=4のスペースの中に1から3までの数が1つずつ書かれた正方形のこまをスライドさせる，あるいは3×3=9のスペースの中に1から8までの数が1つずつ書かれた正方形のこまをスライドさせるという形式で,出題される。
