読者です 読者をやめる 読者になる 読者になる

群の可視化に関する考察その2

前回の記事で群の可視化について考察した。その際、群の全ての元に対して、全ての元を掛けあわせたときの遷移先をグラフのエッジとして表すという方法を採った。しかし、これだと群の位数nに対してエッジ数がn2となってしまい、位数が大きい群を可視化するのには向かないというのが問題であった。そこであれこれ調べて見たところ、やはり自分が考える程度のことはすでに考えている人がいるようで、解決策を発見した。今回はそれについて述べ、いくつかの大きい群を可視化してみようと思う。

さて、今の問題はエッジの数が多すぎることであるから、これを解決するには単純にエッジの数を減らせばよい。問題は、どのエッジを残し、どのエッジを消すかである。できれば群の構造を決定付ける上で重要なエッジのみを残したい。そこで、群の生成元というものに着目し、生成元に関するエッジだけを残すようにするというのが基本的なアイディアである。

群の生成元について説明する。群Gに対してGの部分集合Sがあり、任意の元g∈Gに対してgがSの要素の積*1で表されるとき、Sに含まれる元をGの生成元と呼ぶのである。つまり生成元とは群の元素のようなものである。線形代数っぽくいえば、群の基底のようなものだとも言えよう。(私の個人的なイメージです。)平たく言えば、群Gの全ての要素は生成元の積で表されるということである。

しかし、上の説明だけだと生成元の集合Sは一意に決まらない。なぜなら、例えば4次の巡回群G={e, g1, g12, g13}の生成元はg1であるが、S={e, g1}としても上で述べたことが成り立ってしまうからである。そのため、以下では生成元の集合Sを「Gの任意の元を生成できる元の集合Sのうち最小のもの」と定義する。一般にどうなのかはよく分かっていないが、少なくともここではそうする。

話を可視化に戻そう。要するに位数の大きい群の可視化は、群の基本的な構成要素である生成元による遷移だけ表すことができれば、ある程度群の形が見えてくるというのが話の肝である。実際に、前回描いたクラインの四元群と4次の巡回群をこの方法で可視化してみよう。まず、クラインの四元群は以下のようになる。

f:id:peng225:20151122143420p:plain

クラインの四元群の生成元はS={g1, g2}である。すっきりとわかりやすくなったような気がする。次は4次の巡回群である。

f:id:peng225:20151122124501p:plain

以前に比べてエッジの数が大きく削減されたが、逆に巡回群らしさが際立ったと言えよう。

ここからが本題である。もっと大きい群をこの方法で可視化したらどうなるだろうか?ここでは個人的に興味があった2つの群について可視化を行おうと思う。まずは3次の対称群である。対称群とはものの並び替えの操作に関する群である。例えば1, 2, 3という数字を並び替える方法は全部で3!=6通りある。この6通りそれぞれを実現する並び替えの操作を群の要素と考えたものが対称群である。ここでは3つの数字の並び替えとなっているので、これは3次の対称群である。全ての要素を書き出してみると以下のようになる。

e: (1 2 3)→(1 2 3)
(1 2): (1 2 3)→(2 1 3)
(2 3): (1 2 3)→(1 3 2)
(1 3): (1 2 3)→(3 2 1)
(1 2 3): (1 2 3)→(2 3 1)
(1 3 2): (1 2 3)→(3 1 2)

ここで、コロンの左側に示したのがこの並び替えの操作を表す記号である。例えば(1 2)は1と2を入れ替えるという意味であり(この操作を互換と呼ぶ)、(1 2 3)は1→2→3と順に数字を入れ替える操作を表す。(このような数字の入れ替え方を巡回置換と呼ぶ。)

並び替えの操作というのは、一般には全て互換の積に分解することができる。3次の対称群の場合、全ての並び替え操作が互換(1 2)と(2 3)の組み合わせによって実現できるため、これらが生成元となる。σ=(1 2)、τ=(2 3)とすると、各元は以下のようになる。

e, σ, τ, στσ=(1 3), στ=(1 2 3), τσ=(1 3 2)

ちなみにτστ=στσとなるため、これは元には含めていない。また、σ-1=σ, τ-1=τなどが成り立つ。

これら6つの元に対して、生成元であるσ, τによる遷移を可視化したものを以下に示す。

f:id:peng225:20151122131641p:plain

なんとも美しい六角形が現れたではないか!満足。

ちなみに、対称群とよく似た群で交代群と呼ばれるものもある。これは、対称群の元のうち、互換の偶数個の積によって表される元のみからなる群のことである。(これが群になることの証明は割愛する。)上記の対称群の可視化において、単位元eからスタートして一個おきに要素を選べば、これが交代群の元となることは明白であろう。すなわち、交代群の元は{e, στ, τσ}となる。

次に、ビット列とXOR演算が成す群の可視化を行う。これが群(しかもアーベル群)になるというのは、数学と情報の接点が垣間見られて面白い。ここでは簡単のために長さ3のビット列を考えることにする。元の数は23=8である。以下にすべての元を示す。

{000, 001, 010, 011, 100, 101, 110, 111}

e=000であり、全ての元の逆元が自分自身となっているのが特徴である。

さて、生成元を考えてみると、S={001, 010, 100}であることが容易に分かるだろう。では、実際に可視化を行ってみよう。

f:id:peng225:20151122143519p:plain

これまた綺麗な対称形となっている。面白いことに、この群の部分群である{000, 001, 010, 011}(すなわち最上位ビットが0である元が成す群)が000の近辺に集まっている。(まあこれは描画の仕方次第ではあるが。)更にその部分群である{000, 001}も000の近辺に現れている。もっと言うと、最下位ビットが0, 1となる元がそれぞれ綺麗に二手に分かれているなど、美しい構造の数々が見て取れる。

今回は生成元に注目した群の可視化を行った。群の自分自身に対する作用を考え、各元の遷移先を可視化するというアイディアを自力で思いついたまではよかったが、やはり先人は偉大であった。こちらの方が格段にすっきりと本質を捉えることができ、ある程度大きい群に対しても可視化が可能である。

代数学は非常に面白い分野であるから、今後も何かネタを思いついたら随時書いていきたいと思う。

*1:ここでいう積とは群に与えられた演算のことを指す。群の演算は一般には非可換であるため、よく積と呼ばれる。アーベル群の場合は和と呼ぶこともある。どちらにせよ、これらの呼び方は俗に言う掛け算、足し算とは異なる抽象概念である。