巡回置換 | 二つの置換の型が一致することと共役であることは同値
![巡回置換-表紙](https://iwai-math-blog.com/wp-content/uploads/2023/08/junnkaichikannbunnkai-hyousi.jpg)
「 巡回置換 」について、二つの置換の型が一致することと、二つの元が共役であることは同値です。
このことを証明するために、まず、n 次対称群の任意の置換が巡回置換の積で表されることを示します。
その後で、型が同じであることの必要十分条件が、共役であることを示します。
最後に、巡回置換が互換の積として表せることも証明しています。
※ 目次の項目を選択すると該当箇所へ移動します。
巡回置換 :任意の置換は巡回置換の積となる
n 次対称群は、異なる n 個の元から成る集合 X から、集合 X への全単射全体で、写像の合成を積として群となっています。
この記事では、X を異なる n 個の元から成る集合で、
X = {x1, x2, … , xn} とします。
X についての対称群を S(X) と表すことにします。
この n 次対称群 S(X) の元のことを、X の置換といいます。
S(X) の任意の元(置換)は、巡回置換の積として表すことができます。この巡回置換の積として表すことを、巡回置換分解といいます。
では、S(X) のどの置換も、巡回置換の積として表せることを写像の定義に基づいて証明します。
巡回置換分解の証明
σ∈S(X) が、巡回置換の積として表されることを示します。
x1 = σ0(x1) とし、
σ(x1) = σ1(x1), σ2(x1), … と順に移します。
σ は 有限集合 X から X への全単射なので、ある自然数の組 i, j が存在して、
i < j で、σi(x1) = σj(x1) となります。
X には有限個しか元がないため、
σ0(x1), σ1(x1), σ2(x1), … と移していくと、有限回の操作で、二つが一致するということが起こります。
i, j となる非負整数の組の個数も有限個なので、j の方が最小となるものが存在します。
その最小の j を r と置きます。
ここで、i = 0 であることを背理法で示します。
もし、i ≧ 1 と仮定すると、
σi(x1) = σr(x1) だから、
σ0(x1) = x1 = σr-i(x1) となります。
i ≧ 1, i < r なので、r-i < r です。
これは、r が最小であったことに矛盾します。
よって、i = 0 ということが分かります。
このことから、
σ0(x1), σ1(x1), … , σr-1(x1) で止まることになります。
σr(x1) = σ0(x1) = x0 と巡回します。
(σ0(x1), σ1(x1), … , σr-1(x1)) という長さ r の巡回置換に現れていない X の元が存在しなければ、σ が巡回置換ということで、巡回置換分解が成立です。
そこで、
(σ0(x1), σ1(x1), … , σr-1(x1)) という長さ r の巡回置換に現れていない X の元 y が存在した場合を考えます。
y = σ0(y) とし、
σ(y) = σ1(y), σ2(y), … と同様に順に移します。
同じ議論で、ある自然数 s が存在し、
σ0(y), σ1(y), … , σs-1(y) で止まり、
σs(y) = σ0(y) = y です。
(σ0(y), σ1(y), … , σs-1(y)) という長さ s の巡回置換が見つかりました。
ここで、
(σ0(x1), σ1(x1), … , σr-1(x1)) に現れる X の元は、
(σ0(y), σ1(y), … , σs-1(y)) に現れる X の元と重複していないことを示します。
y は {σ0(x1), σ1(x1), … , σr-1(x1)} に含まれていない X の元でした。
そのため、任意の整数 p について、
p を r で割った余りが s のとき、
y ≠ σs(x1)∈{σ0(x1), σ1(x1), … , σr-1(x1)} となります。
もし、σ(y) = σ1(y) が、
{σ0(x1), σ1(x1), … , σr-1(x1)} に含まれたとすると、ある非負整数 k が存在し、
σ1(y) = σk(x1) となります。
つまり、y = σk-1(x1) です。
k-1 を r で割った余りを s’ とすると、
y = σs’(x1)∈{σ0(x1), σ1(x1), … , σr-1(x1)} となり矛盾します。
そのため、σ(y) = σ1(y) は、
{σ0(x1), σ1(x1), … , σr-1(x1)} に含まれないということになります。
y として σ(y) を考えると、
σ(σ(y)) = σ2(y) も、同様にして、
{σ0(x1), σ1(x1), … , σr-1(x1)} に含まれないということになります。
この議論を繰り返して、
σ0(y), σ1(y), … , σs-1(y) は、
どれも {σ0(x1), σ1(x1), … , σr-1(x1)} に含まれないということになります。
よって、
(σ0(x1), σ1(x1), … , σr-1(x1)) に現れる X の元は、
(σ0(y), σ1(y), … , σs-1(y)) に現れる X の元と重複していないことを示すことができました。
これらの操作を有限回繰り返すと、X が有限集合であることから、σ が巡回置換の積に分解します。 ■
(σ0(x1), … , σr-1(x1))(σ0(y), … , σs-1(y))… と、σ を巡回置換の積に分解したときに、それぞれの巡回置換に現れている X の元たちは、すべて相異なるということを、先ほどの証明の最後の部分で示しました。
一般の n について述べると、このように複雑になります。4 次対称群を例に、具体的に巡回置換分解を観察してみます。
4次で巡回置換分解の例
X = {x1, x2, x3, x4} として、
4 次対称群 S(X) の元で、巡回置換分解を観察してみます。
σ∈S(X) の対応を次とします。
σ(x1) = x3, σ(x2) = x1,
σ(x3) = x4, σ(x4) = x2 とします。
確かに σ は X から X への全単射となっています。
先ほどの巡回置換分解の証明の通りに考えます。
x1 = σ0(x1) とし、
σ(x1) = σ1(x1), σ2(x1), … と順に移します。
σ1(x1) = σ(x1) = x3 です。
σ2(x1) = σ(σ1(x1)) = σ(x3) = x4 と分かります。
σ3(x1) = σ(σ2(x1)) = σ(x4) = x2 です。
σ4(x1) = σ(σ3(x1)) = σ(x2) = x1
ここで、σ4(x1) = x1 = σ0(x1) と巡回しました。
これで、
σ = (x1, x3, x4, x2) と巡回置換分解ができました。
(x1, x3, x4, x2) という巡回置換が、先ほどと同様にして分かります。
ここで、{x1, x3, x4, x2} に含まれていない元を任意に取ります。
x6 を取ったとします。
σ-1 という σ の逆写像(逆元)についての逆対応を考えると、
(x2, x4, x3, x1) となることが分かります。
つまり、σ-1(x2) = x4, σ-2(x2) = x3,
σ-3(x2) = x1, σ-4(x2) = x4 となります。
そのため、どんな整数 p についても、
σp(x1)∈{x1, x3, x4, x2} です。
全単射であることから、
σ(x6) は {x1, x3, x4, x2} には含まれません。
σ の対応が具体的に示されていないときには、このように抽象的な考察をします。
実際、σ の対応の定義を見てみると、
σ(x6) = x5, σ2(x6) = x6 です。
そのため、
(x1, x3, x4, x2)(x6, x5) が σ の巡回置換分解です。
確かに、巡回置換に現れた X の元は、すべて相異なっています。
【巡回置換が二つ出る例】
今度は、巡回置換が二つ出てくる例を 6 次対称群で観察します。
σ(x1) = x3, σ(x2) = x1,
σ(x3) = x4, σ(x4) = x2,
σ(x5) = x6, σ(x6) = x5とします。
この例では、σ は長さ 4 の巡回置換でしたが、
(x1, x3, x2)(x4) というような長さ 3 と長さ 1 の巡回置換の積というようなものもあります。
巡回置換 :置換の型
先ほど n 次対称群の元は、巡回置換の積に分解できることを証明しました。ここで、置換の型という用語を決めておきます。
8 次対称群の置換が次のように巡回置換だけの積となっていたとします。
(x1, x3, x4, x2)(x6, x5)(x7)(x8) という巡回置換の積だけの置換について、型というものを次のように考えます。
長さ 1 の巡回置換が 2 個で、長さ 2 の巡回置換が 1 個、長さ 4 の巡回置換が 1 個で積をとっています。
このとき、型 122141 といいます。
長さを表す数字が大きい方から順に、
4×1+2×1+1×2 = 8 です。
これは、置換で入れ替えられる有限集合 X に含まれている元の個数 n を置換の型を使って分割できるということを意味しています。
(x1, x3, x4)(x2, x6, x5)(x7, x8) だと、
型 2132 です。
長さ 2 の巡回置換 1 個と長さ 3 の巡回置換 2 個の積ということです。
使われていない長さを敢えて示すときには、
型 102132 と 0 を指数の部分に使う表し方もあります。
8 = 3×2+2×1+1×0 で、やはり 8 の分割となっています。
この置換の型ですが、群の共役作用を用いた同値な書き換えがあります。
【群の共役作用】
群 G の元 g から、G の元 h への共役作用は、
hg = ghg-1 です。
h∈G に対して、ghg-1∈G を対応させるのが、g の作用です。
※ 共役類という記事で、類等式などの基本的な内容を解説しています。
そして、h1, h2 ∈ G について、ある G の元 g が存在し、
gh1g-1 = h2 となるとき、
h1 と h2 は共役であるといいます。
群 G として、対称群 S(X) の場合を考えているのが、この記事の内容です。
置換の型と共役
【定理】
n 次対称群 S(X) の元 σ と ρ が共役であることと、σ と ρ を巡回置換分解したときの型が同じであることは同値である。
<証明>
まず、σ と ρ が S(X) において共役であると仮定し、このときに σ と ρ の巡回置換分解の型が同じであることを示します。
共役の定義から、ある S(X) の元 g が存在して、
ρ = gσg-1 となっています。
S(X) の乗法について、
ρg = gσ です。
また、S(X) の乗法が写像(関数)の合成で定義していたので、
任意の x∈X に対して、
ρ(g(x)) = (ρg)(x)
= (gσg-1g)(x)
= (gσ)(x) = g(σ(x)) です。
つまり、任意の x∈X に対して、
ρ(g(x)) = g(σ(x)) となっています。
この関係から、σ の巡回置換分解の型と ρ の巡回置換分解の型が一致することを示します。
σ の巡回置換分解が、
(i1, … , ir)(ir+1, … , ir+r’)… だとします。
ρ(g(i1)) = g(σ(i1)) = g(i2),
ρ2(g(i1)) = ρ(ρ(g(i1)))
= ρ(g(σ(i1)))
= g(σ(σ(i1))) = g(σ2(i1))
= g(σ(i3))です。
p3(g(i1)) = ρ(ρ2(g(i1)))
= ρ(g(σ2(i1)))
= g(σ(σ2(i1))) = g(σ3(i1))
= g(σ(i4))です。
繰り返すと、
pr-1(g(i1)) = g(σr-1(i1)) = g(ir) となります。
pr(g(i1)) = g(σr(i1)) = g(i1) で元へと巡回します。
(g(i1), … , g(ir)) という長さが同じ r の巡回置換が ρ の巡回置換分解に現れることが分かります。
次の σ に現れる長さ r’ の巡回置換についても、同様の結果を得ます。
(ir+1, … , ir+r’) については、
pr’-1(g(ir+1)) = g(σr’-1(ir+1)) = g(ir+r’),
pr’(g(ir+1)) = g(σr’(ir+1)) = g(i1+r’) で元へと巡回します。
これらのことから、
(i1, … , ir)(ir+1, … , ir+r’)… が σ の巡回置換分解のとき、ρ の巡回置換分解は、次のようになります。
(g(i1), … , g(ir))(g(ir+1), … , g(ir+r’))… が ρ の巡回置換分解で、型が σ の型と一致しています。
今後は、逆を示します。
逆の証明
![置換の型-共役](https://iwai-math-blog.com/wp-content/uploads/2023/08/junnkaitikannbunnkainokata-kyouyaku-512x288.jpg)
σ と ρ の置換の型が一致しているときに、共役となっていることを詳しく示します。
巡回置換分解から、集合 X に含まれている元の個数 n の分割を得られるため、上のように定めた g は、X から X への全単射となっています。
つまり、g∈X です。
次に、gσg-1 = ρ となることを示します。
二つの全単射(写像)が等しいということは、定義域である X のどの元についても、対応させる元が等しいということです。
この二つの写像が等しいという相当関係を確認します。
巡回置換分解は、n の分割を与えているので、
1 ≦ t ≦ n について、
gσg-1(kt) = ρ(kt) となることを確認することになります。
g の定め方から、
g(it) = kt なので、逆写像について、
g-1(kt) = it です。
ゆえに、kt∈{k1, … , kr-1} の場合、
gσg-1(kt) = g(σ(it))
= g(it+1) = kt+1 = ρ(kt) となります。
kt = kr の場合は、
gσg-1(kt) = gσg-1(kr)
= g(σ(ir)) = g(i1)
= k1 = ρ(kr) = ρ(kt) です。
よって、kt∈{k1, … , kr-1, kr} について、
gσg-1(kt) = ρ(kt) です。
同様に、次の巡回置換に現れる各元について、
kt∈{kr+1, … , kr+r’} に対して、
gσg-1(kt) = ρ(kt) となります。
このように、それぞれの巡回置換に現れる元の集まりで区切って、対応する元が一致していることを確認します。
そうすると、
1 ≦ t ≦ n について、
gσg-1(kt) = ρ(kt) ということになります。
したがって、gσg-1 = ρ です。 ■
これで、「n 次対称群 S(X) の元 σ と ρ が共役であること」と、「σ と ρ を巡回置換分解したときの型が同じであること」が同値だと分かりました。
最後に、巡回置換が、互換という長さ 2 の置換の積に分解することを示します。
巡回置換 :さらに互換の積に分解
【命題】
(i1, i2, … ir-1, ir) は、
(i1, ir)(i1, ir-1)…(i1, i3)(i1, i2) と等しい。
<証明>
f = (i1, i2, … ir-1, ir),
h = (i1, ir)(i1, ir-1)…(i1, i3)(i1, i2) と置きます。
2 ≦ t ≦ r-1 の場合を考えます。
f(it) = it+1 です。
互換の積となっている h において、
it が現れている互換は、
(i1, it) のみです。
そのため、
(i1, it-1)…(i1, i2)(it)
= it だから、
h(it) は、
(i1, ir)(i1, ir-1)…(i1, it+1)(i1, it)(it) となります。
ゆえに、
h(it) =
(i1, ir)(i1, ir-1)…(i1, it+1)(i1, it)(it)
= (i1, ir)(i1, ir-1)…(i1, it+1)(i1)
= (i1, ir)(i1, ir-1)…(i1, it+2)(it+1)
= it+1 = f(it) です。
次に、t = 1 の場合を考えます。
f(it) = f(i1) = i2 です。
h(it) = h(i1)
= (i1, ir)(i1, ir-1)…(i1, i3)(i1, i2)(i1)
= (i1, ir)(i1, ir-1)…(i1, i3)(i2)
= i2 = f(i1) = f(it) です。
最後に、t = r の場合を考えます。
f(it) = f(ir) = i1 です。
h(it) = h(ir)
= (i1, ir)(i1, ir-1)…(i1, i3)(i1, i2)(ir)
= (i1, ir)(ir)
= i1 = f(ir) = f(it) です。
以上より、1 ≦ t ≦ r に対して、
f(it) = h(it) だから、
f = h です。 ■
この証明を、より正確に述べると、
X-{i1, i2, … ir-1, ir} という差集合の任意の元 x についても、f と h が等しいことを示す必要があります。
しかし、f の巡回置換には、x が現れていません。
巡回置換の対応の定め方から、
f(x) = x となります。
h についても、同様に、
h(x) = x です。
これで、X の任意の元 y について、
f(y) = h(y) ということが示せたので、
対称群 S(X) の元として、
f = h です。
巡回置換は、互換の積として表すことができるということの証明が完了しました。
ただ、巡回置換を互換の積として表す方法は、一意的ではありません。
しかし、巡回置換 σ を互換の積として表したときに用いる互換の個数が偶数個であるか、奇数個であるかは、確定します。
※ この証明は、偶置換 奇置換という記事で述べています。
このことから、置換について符号(sgn) が定義でき、行列式の定義に使われています。
この巡回置換分解の内容は、5 次以上の交代群が単純群であることを証明するときに役立ちます。
それについては n次交代群という記事で解説をしています。
それでは、これで今回の記事を終了します。
読んで頂き、ありがとうございました。