利用者:１３２人目/cover

出典: フリー百科事典『ウィキペディア（Wikipedia）』

< 利用者:１３２人目

置換群（ちかんぐん、permutation group）とは、集合 A に対し A から A 自身への全単射を与える置換という操作を元とする群のことである。

[編集] 概要

置換とは、n 個のものの並べ替えを表す操作である。例えば、A = {1,2,3,4} という 4つの数の集合で、(1,2,3,4) という順列を (2,3,1,4) に変える置換を

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

と書く。

この σ を、式 F(x₁,x₂,x₃,x₄) に作用させると

F(x₁,x₂,x₃,x₄)^σ = F(x₂,x₃,x₁,x₄)

となる。

F(x₁,x₂,x₃,x₄) = x₁ x₂³ + x₄

であれば

F(x₁,x₂,x₃,x₄)^σ = x₂ x₃³ + x₄

となるし

F(x₁,x₂,x₃,x₄) = x₁² x₂² x₃² + x₄

であれば

F(x₁,x₂,x₃,x₄)^σ = x₂² x₃² x₁² + x₄ = F(x₁,x₂,x₃,x₄)

となる。このように、数式に置換を作用させることで別の数式になることもあれば、変わらないこともある。このような置換の性質の違いは、特に一変数の代数方程式の根の公式に関する研究おいて、ラグランジュによって注目された。そして、ラグランジュの考えを推し進めたルフィニが、不十分な点はあるものの、5次以上の代数方程式は、代数的には解けないことの証明を試みた。このルフィニの証明には賛否両論があり、ラグランジュも不十分であるとした。しかし、コーシーはルフィニの証明は正しいとし、自らも置換の研究を行い、ルフィニの結果の拡張や置換の記号化を推し進めた。

日本語では、順列を他の順列へとうつす操作を置換と呼び、順列(permutation) と置換(substitution)という言葉を区別している。このような区別もコーシーによるものであるが、元々 permutation には並べ替えという意味も含まれていたため、欧米では、順列も置換も同じ語 permutation やそれに類する語を用いる事が多い。

このようにして整備された置換の理論を元に、アーベルによって、5次以上の代数方程式は代数的には解けないことの証明が完成させられる。さらにガロア以後、これらの研究が抽象化され、群という概念が生まれた。

このような経緯から、ラグランジュの定理のように、群論の基礎的な定理のいくつかには、群論が始まる前の時代の数学者の名前が、置換の理論に対する業績によって用いられたりもしている。

σ とは別の置換

$\tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1\end{pmatrix}$

を与えると

F(x₁,x₂,x₃,x₄)^{σ τ} = {F(x₁,x₂,x₃,x₄) σ}^τ = F(x₂,x₃,x₁,x₄)^τ = F(x₂,x₄,x₃,x₁)

のように、σ τ という積を定めることができ、このような積によって置換を元とする群を構成することができ、このような群を置換群という。 A は、A = {x₁, x₂, x₃} のような変数の集合でもいいし、A = {机, 椅子, 本} のような物の集合でもいいが、上の説明のように数の集合で表現されることが多い。ある集合 A に対して、A の要素の置換の全てを含む置換群の事を対称群（たいしょうぐん）という。すなわち、置換群は対称群の部分群であるが、置換群という言葉で対称群を意味する場合もある。

[編集] 定義

[編集] 置換

集合 A に対して定まる全単射

σ : A → A

の事を（A 上の）置換（ちかん、permutation）という。 σ が恒等写像の時、σ の事を恒等置換（こうとうちかん、identity permutation）、あるいは、単位置換（たんいちかん）という。

A が、n 個の元を持つ有限集合であれば元に番号を付けることによって、 A = {1,2,3,…,n} と同一視できる。

A の要素でできた順列 (a₁,a₂,a₃,…,a_n) を (b₁,b₂,b₃,…,b_n) に変える置換を

$\sigma = \begin{pmatrix} a_1 & a_2 & \cdots & a_n \\ b_1 & b_2 & \cdots & b_n \end{pmatrix}$

と書く。この時、a_k と b_k の対応だけが重要であるため、列の順序は好きなように変えてもよい。たとえば

$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 3 & 1 & 6 & 5 & 4 \end{pmatrix} = \begin{pmatrix} 3 & 4 & 5 & 1 & 6 & 2 \\ 1 & 6 & 5 & 2 & 4 & 3 \end{pmatrix}$

である。

r 個の要素を 1つずつずらし、他の要素は全く変えない置換

$\begin{pmatrix} a_1 & a_2 & \cdots & a_{r-1} & a_r & a_{r+1} & \cdots a_n \\ a_2 & a_3 & \cdots & a_r & a_1 & a_{r+1} & \cdots a_n \end{pmatrix}$

を、長さ r の巡回置換（じゅんかいちかん、cyclic permutation）といい、 (a₁, a₂, a₃, …, a_r) と略記する。特に長さ 2 の巡回置換を、互換（ごかん、transposition）という。

[編集] 置換群

集合 A に対し、A 上の置換の全体は写像の合成によって群になる。一般にこの積は非可換である。この群の事を対称群（たいしょうぐん、symmetric group）といい、 S_A とか Sym(A) などと書く。

つまり A から A への全単射の全体が対称群である。

特に A が n 個の要素よりなる有限集合の時は、n の事を次数（じすう、degree）といい n 次の対称群と呼ばれ S_n と書く。 S_n の元となる置換は、n 個のものの順列に対応するため S_n の位数は n! となる。

対称群の部分群の事を置換群（ちかんぐん）という。次数は対称群と同じで n 次の対称群の部分群であれば、n次の置換群という。

[編集] 置換の積

置換の積の表記については注意しなければならないことがある。

1815年にコーシーが導入した記法では、集合 A の要素で書かれた式、F(x) への σ の作用を F(x)^σ と表す。 2つの置換 σ₁, σ₂ に対し積 σ₁ σ₂ の A の要素で書かれた任意の式 F(x) への作用を

F(x) ^{(σ₁ σ₂)} = {F(x)^σ₁}^σ₂

で定める。

要は、F(x) に、σ₁ と σ₂ をこの順に作用させただけであり、σ₁ σ₂ という合成は、一つの置換を表す事になる。この積は一般には非可換、すなわち σ₁ σ₂ ≠ σ₂ σ₁ である。

1852年にベッティは、置換を

$\sigma = \begin{pmatrix} a_1 & a_2 & \cdots & a_n \\ \sigma(a_1) & \sigma(a_2) & \cdots & \sigma(a_n) \end{pmatrix}$

のように関数としてとらえた。 a_k ∈ A に対し、A 上の置換 σ₁ と σ₂ を作用させると、関数を合成するときの記法によれば

$\sigma_2 (\sigma_1 (a_k)) = \sigma_2 \circ \sigma_1 (a_k)$

である。

コーシーの記法とベッティの記法では、 σ₁ と σ₂ の順序が逆になり、また、置換の積は、一般には非可換であるため、計算を行う時は、どちらの記法で書かれているかを意識する必要がある。

特に断らない限り、この項目内ではコーシーの記法を用いる。例えば

$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1\end{pmatrix} \begin{pmatrix} 3 & 2 & 4 & 1 \\ 1 & 4 & 3 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 4 & 3 & 2\end{pmatrix}$

である。

ある特定の置換 σ を、m 回かけ合わせたものは、冪乗と同じように σ の m 乗といい、 σ^m と書く。例えば長さ 5 の巡回置換 σ = (1 2 3 4 5) に対して

$\sigma^2 = (1 2 3 4 5) (1 2 3 4 5) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 4 & 5 & 1 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 4 & 5 & 1 \end{pmatrix}$

$= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 1 & 2 \end{pmatrix} = (1 3 5 2 4)$

である。

σ⁰ は、単位置換 e とする。置換群の元として σ の逆元にあたる置換を逆置換（ぎゃくちかん、inverse permutation）といい σ⁻¹ と書く。すなわち

$\sigma = \begin{pmatrix} a_1 & a_2 & \cdots & a_n \\ b_1 & b_2 & \cdots & b_n \end{pmatrix}$

に対して

$\sigma^{-1} = \begin{pmatrix} b_1 & b_2 & \cdots & b_n \\ a_1 & a_2 & \cdots & a_n \end{pmatrix}$

であり、

σ σ⁻¹ = σ⁻¹ σ = e

を満たす。 σ⁻¹ の m 乗も同様に σ^−m と書く。

σ が、長さ r の巡回置換であれば、その r 乗は単位置換 e になる。

σ^r = e

したがって、この σ の逆置換は

σ⁻¹ = σ^r−1

となる。特に r = 2 すなわち、 σ が互換であれば、 σ⁻¹ = σ である。

S_n の位数は n! であることから、同様に任意の置換 σ ∈ S_n に対し、適当な正の整数 m ≤ n! が存在して、m 乗が単位置換 e になる。

σ^m = e

このような性質を持つ m のうち最小の正の整数を、置換 σ の位数（いすう、order）という。位数 m の置換 σ は、位数 m の巡回群 <σ> = {σ^k | 0 ≤ k < m} を生成し、ラグランジュの定理より m は、n! の約数となる。

群の元の数を表す位数と、置換という 1 つの元の性質を表す位数は、異なる用語であることに注意する。

[編集] 置換の分解

単位置換でない任意の置換 σ ∈ S_n は、いくつかの共通の要素を持たない巡回置換の積に分解される。例えば

$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 3 & 1 & 2 & 8 & 7 & 5 & 10 & 4 & 9 & 6 \end{pmatrix} = (1 \ 3 \ 2) (4 \ 8) (5 \ 7 \ 10 \ 6)$

である。要素に重なりがないため、ここに現れた巡回置換同士は、積において、互いに影響しあったりせず、可換になる。

このような分解は、それぞれの要素に置換 σ を次々に作用させることで探すことができる。例えば 1 から始めると σ(1) = 3, σ²(1) = σ(3) = 2, σ³(1) = σ(2) = 1 と戻ってくるので、σ によって 1 → 3 → 2 → 1 という循環が起きている事が分かり、 (1 3 2) という巡回置換が見つかる。

置換 σ が、互いの要素に重なりがない置換 σ₁, σ₂, …, σ_k を用いて

σ = σ₁ σ₂ … σ_k

のような積に分解されるとき、 σ の位数は σ₁, σ₂, …, σ_k の位数の最小公倍数である。

巡回置換は

(a₁, a₂, a₃, …, a_r) = (a₁, a₂) (a₁, a₃) … (a₁, a_r)

のように、互換の積に分解することができる。したがって、任意の置換は互換だけを用いた積で表せることがわかる。

置換の分解は、必ずしも位数の小さい置換の積とは限らず

(1 2 3) = (1 3 2 4 5) (1 5 4 3 2)

(2 3) = (1 2) (1 3) (1 2)

のように位数の大きい、あるいは、等しい置換への分解も考えられ、置換の互換への分解は一意的には定まらない。しかし、置換を互換に分解したとき、現れる互換の個数が偶数か奇数かは定まり、その偶奇によって、置換を特徴付けることはできる。互換の個数が偶数であるような置換を偶置換（ぐうちかん、even permutation）といい、奇数であるような置換を奇置換（きちかん、odd permutation）という。

置換 σ が偶置換のとき sgn(σ) = +1, 置換 σ が奇置換のとき sgn(σ) = −1 となるように定められた関数

sgn : S_n → {1,−1}

は群の準同型となる。

{1,−1} は、普通の整数の積で群になっている。

この sgn(σ) を σ の符号（ふごう、sign）という。 sgn の核すなわち、偶置換の全体を、n 次の交代群（こうたいぐん、alternating group）といい A_n と書く。A_n は S_n の正規部分群である。

一方で、2つの奇置換の積は偶置換となるため、奇置換の全体は演算が閉じてすらいない。

[編集] 推移群

集合 A と、A 上の置換群 G が与えられたとする。任意の x, y ∈ A に対して適当な置換 σ ∈ G が存在して y σ = x となるとき、G を推移置換群（すいいちかんぐん、transitive permutation group）あるいは可移置換群（かいちかんぐん）という。単に推移群あるいは可移群ともいう。必ずしも存在しないとき、G を非推移置換群（ひすいいちかんぐん、intransitive permutation group）あるいは非推移群という。

σ に課される条件は、 y σ = x だけであり、 σ によって他の元がどのように写されているかは問わない。定義により、対称群は推移群である。

A 上の推移群 G に対し、A の部分集合で位数が 2 以上の適当な真部分集合 M が存在して、任意の σ ∈ G に対し、 M ∩ σ(M) が M または空集合となる時、推移群 G は非原始的（ひげんしてき、imprimitive）であるという。このような M をブロック(block) と呼ぶ。

推移群 G が非原始的ではないとき、G は原始的（げんしてき、primitive）であるという。

このような置換群の分類は、本質的にはルフィニに始まる。

例えば、

A = {1,2,3,4}

G = {e,(1 2), (3 4),(1 2)(3 4), (1 3)(2 4), (1 4)(2 3), (1 3 2 4), (1 4 2 3)}

のとき、1 を、2,3,4 それぞれに移す置換、2 を 1,3,4 それぞれに移す置換 … があるので、G は推移群である。また、 M = {1,2} ⊂ A は、任意の σ ∈ G によって、M = {1,2} か、{3,4} に移されるため、G は、非原始的な推移群ということになる。

[編集] 関連項目

マシュー群

"http://ja.wikipedia.org../../../%EF%BC%91/%EF%BC%93/%EF%BC%92/%E5%88%A9%E7%94%A8%E8%80%85%7E%EF%BC%91%EF%BC%93%EF%BC%92%E4%BA%BA%E7%9B%AE_cover_eb5e.html" より作成

利用者:１３２人目/cover

出典: フリー百科事典『ウィキペディア（Wikipedia）』

目次

[編集] 概要

[編集] 定義

[編集] 置換

[編集] 置換群

[編集] 置換の積

[編集] 置換の分解

[編集] 推移群

[編集] 関連項目

Views

ナビゲーション

ヘルプ

検索

他の言語