総合科目II(第2回) part II

part Iに引き続き、後半ではグラフ理論をやっていきます。

グラフ理論

いくつかの頂点と、それを結ぶ辺からなる図形をグラフといいます。

このような図形は、５つの頂点と５つの辺からなるグラフとなります。
平面上に書いたときに、辺同士が交わってもかまいません。
ただし、必ず辺は２つの頂点(同じでもよい)を結ぶものでないといけません。

グラフ理論を始めるにあたり、いくつかの定義があるので紹介します。

次数：頂点から出る辺の数。通常、頂点に従って変わる。
完全グラフ：任意の異なる頂点に対して、ただ一つのみ辺が定まっているもの。
特に、各頂点の次数は等しく $n-1$。ここで、$n$ は頂点の数。このとき、$K_n$ と書く。
正則グラフ：各頂点で次数が等しくなるグラフのこと。特に完全グラフは正則グラフになる。
二部グラフ：頂点の集合 $V$ が2つ集合 $A$ と $B$ からなっており(つまり、 $V=A\cup B$ のような２つの集合の和集合となっており、$A\cap B=\emptyset$ を満たし、辺は必ず、$A$ の頂点と $B$ の頂点を結ぶ。例として以下のグラフがある。

完全二部グラフ：$A$ と $B$ の頂点の個数をそれぞれ、$n,m$ とすると、$A$ の各点は辺によって、必ず、$B$ のすべての頂点とただ一つの辺にのみ結ばれるもの。$K_{n,m}$ と書く。
歩道：$v_1,v_2,\cdots, v_n$ をいくつかの頂点とし、$v_i$ と $v_{i+1}$ がある辺によって、結ばれているとき、この頂点と辺の和集合を歩道という。
多重辺：ある２つの頂点に対して、それらを結ぶ辺が２個以上あるとき、その辺のこと。
ループ：一つの頂点から出発して、同じ頂点に戻ってくる辺のこと。
サイクル：歩道のうち、最初と最後の頂点が一致しているもの。
内周：すべてのループのうち、最短のサイクルのこと。
同型なグラフ：２つのグラフ $G_1, G_2$ が同型であるとは、頂点の集合を $V_1,V_2$ とすると、$V_1$ と $V_2$ の間に一対一対応 $f$ (全単射)があり、$v,w\in V_1$ が結ばれていることと、$f(v),f(w)\in V_2$ が結ばれていることは同値であるものをいう。
平面グラフ：平面上に、辺の交わりなく描くことができるグラフ。

グラフ理論の公式
ここで、グラフ理論における簡単な公式を紹介しておきます。

正則グラフの公式
長点数 $n$, 次数 $d$ 辺の数 $m$ のグラフは

$nd=2m$

を満たす。完全グラフならば、$m=\frac{n(n-1)}{2}$ である。

オイラーの公式

$G$ を平面グラフとし、$G$ を平面に描いたときにできる図形

の頂点の数を $v$ 辺の数を $e$ 領域の数を $f$ としたとき、

$v-e+f=2$

が成り立つ。

例えば、

のような平面グラフであるとすると、頂点数が5で、辺の数が7で、領域の数が4

となります。

ここで、領域とは、このグラフの外部の部分も含めます。

このとき、

5-7+4=2

となり、確かに成り立っています。

プラトングラフとは、正多面体の頂点と辺の関係からなるグラフですが、

これは平面グラフです。

レポートにその理由をかけという問題を出しました。

多くの学生は、上のオイラーの公式を満たしているから平面グラフと書いていましたがそうではないです。

上の公式は、平面グラフであるならば、オイラーの公式を満たすといったのみです。

平面グラフであるための十分条件を与えたわけではありません。

そもそも平面グラフであるかどうかわからないのに領域の数はわかりません。

正しい答えは、以下のようになります。

正多面体を風船のように膨らませてやると、一般に、球上に描かれた頂点と辺からなる

プラントングラフが得られる。この風船の一点を取り除き、平面に

押し付けてやることで、プラトングラフを平面に描くことができる。

よってプラトングラフは平面グラフであることがわかる。

となります。

平面グラフかどうかは実際描いて見せないといけません。

また、最後の一点を取りのぞいて平面に押し付けるという操作は

立体射影と呼ばれておりここ(リンク)を見てみてください。

ここで、完全グラフ $K_5$ が平面グラフでないことを示したいと思います。

この証明ではオイラーの公式を用います。

定理

$K_5$ は平面グラフではない。

(証明)

もしグラフを平面に描いたとき、その領域の数を $f$ とすると、

$f=n_1+n_2+n_3+n_4+\cdots$

となります。ここで、$n_r$ は、グラフを平面に置いたとき分割されて得られる

平面上の $r$ 角形の数とします。

ここで、$r$ 角形とは、長さ $r$ のサイクルで、平面においてその内部に

頂点も辺も含まないものをいいます。

今、完全グラフ $K_5$ を描いたとします。

そうすると、多重辺やループは存在しないので、$n_1=n_2=0$ 

となります。よって、上の式は、

$f=n_3+n_4+\cdots$

となります。

また、各 $r$ 角形の辺の総数を数えると、辺の数の２倍になっているので

$3n_3+4n_4+5n_5+\cdots=2m$

が成り立ちます。ここで、

$3n_3+4n_4+5n_5+\cdots\ge 3(n_3+n_4+n_5\cdots)=3f$

という不等式を用いると、

$2m\ge 3f$

が得られます。しかし、

今、$K_5$ は、オイラーの公式から、$m=10$ かつ $f=7$ であるから、

矛盾します。

つまり、$K_5$ は平面的ではないということになります。

おなじように、$K_{3,3}$ が平面的ではないことを示す問題を出しました。

この場合、２部グラフであるので、もし平面に描けるとして

描いたとき、3角形も存在しません。

なので、$2m\ge 4f$ が成り立ちます。

今、$m=9$ であり、オイラーの公式から、$f=2-6+9=5$ ですから、これも

矛盾します。

ムーアグラフ

ムーアグラフは、去年の数学外書輪講で扱いましたので

そのページをリンク(ここ)しておきます。

定義をします。

定義

頂点数 $n$ 次数 $d$ 内周 $2g+1$ の正則グラフをムーアグラフという。

内周は必ず奇数をとります。

ムーアグラフは、

$n=1+\sum_{i=1}^gd(d-1)^i$   $(\ast)$ 

を満たします。

この式は、上のように、一つの頂点 $v$ から始めて、その点から延びる $d$ 個の

辺の先の頂点 $v_0,v_1\cdots v_{d-1}$ を考えます。

$g\ge 1$ であれば、この $d+1$ 個の頂点は

条件から同じものはありません。

$g=1$ の場合は、この頂点を結んで得られるグラフがムーアグラフになります。

頂点数は $1+d$ です。

$g\ge 2$ とすると、$v_i$ から辺がそれぞれ、$d-1$ 本延びており、その先の頂点を

$v_{ij}$ とすると、内周が5以上ですから、これらはすべて異なる頂点になります。

もちろん、$v_i$ や $v$ とも異なる頂点です。

$g=2$ のムーアグラフは、この $v_{ij}$ たちを適切に結んでできるグラフです。

頂点数は、$1+d+d(d-1)$ となります。

このようにして、ムーアグラフは辺を枝のように伸ばしていくことで得られます。

これを式にしたのが、$(\ast)$ ということになります。

$g=1$ の場合を見ると、$d=2, d=3,d=4$とすると、下のようになります。

同じように、$d=5$ 以上も増やしていくことが出来ます。

この絵で観察できるように、$d\le 3$ では辺どうしがぶつからない絵を描くこと

はできますが、$n=5$ になると、辺同士の頂点が生じています。

実際、$d\ge 4$ において、必ずこのような交点が生じてしまいます。

つまり、平面グラフであるのは、$d=2,3$  の時のみです。

これを証明せよという問題もレポートで出しました。

手法は上の方法と同じです。

次に、$g=2$ の場合を考えます。

頂点数は　$n=d^2+1$ となります。

このとき、次のことが知られています。

定理

内周が5、次数が $d$ のムーアグラフが存在するとすると、$d=2,3,7,57$ のみである。

この証明はMatousek(33-miniatures)の本に書いてありますが、

昨年の外書輪講のリンク(ここ)を張っておきます。

証明は線形代数を使います。

$d=2$ と $d=3$ の場合は、

のグラフが構成できます。

左は５角形ですが、右の方は、ピーターセングラフといいます。

$d=7$ のものを構成します。これは、ホフマンシングルトングラフといいます。

このグラフの構成がこの２回の講義の終着地点です。

まず、頂点 $v$ を一つ選び、7本の辺を伸ばします。

その先の頂点を $v_0,v_1,v_2,v_3,v_4,v_5,v_6$ とします。

さらに、$v_i$ からそれぞれ 6本ずつ辺を伸ばして、$v_{ij}$ を作ります。

ここで、$j=1,\cdots 6$ です。

このとき、$v_{0j}$を $v_{ij}$ と結びます。

左下の頂点を $v_{0i}$ とし、右下の頂点を $v_{ij}$ とします。

これは、内周が5より小さくならないようにに同じ頂点に行かないように

結んでいます。また、今のところ各 $i$ に対して 

$v_{ij}$ は $j$ に個性はありませんので、

素直に、順番通りに結んでいるだけです。

こうして、$v_{0i}$ についてはすべて結び終わりました

のこりは、$v_{1j}$ から $v_{6j}$ までの36個の頂点を結ぶことが出来れば

グラフが構成できます。

下の絵は、 $v_i$ と $v_j$ から６個の辺がそれぞれ伸びている様子です。

$v_{ik}$ を $v_{jm}$ のどれかと結びます。

もし、 $v_{ik}$ と $v_{il}$  がもし同じ $v_{jm}$ と結ぶとすると、

内周が４以下になってしまいます。

なので、$v_{ik}$ と $v_{il}$ は異なる　$v_{j1},\cdots v_{j6}$ のどれかに行かなければ

なりません。

つまり、どちらも同数ずつあるので、これは全単射です。

よって、この $v_i$ と $v_j$ を選ぶごとに、何か、$S_6$ の元を対応させることに

なります。

つまり、

$(i,j)\mapsto f((i,j))$ 

ですがこの写像こそ、前回最後にやった、外部自己同型です。

$n=6$ のときのみ、外部自己同型が使えたのです。

どうしてここで外部自己同型が出てきたのかという疑問が残ります。

いくつかうまくいっている部分を確かめる必要が

あるのですが、一つだけコメントしておきます。

この外部自己同型は、互換を互換の３つの積に写していました。

実は、$f(i,j)$ の先は、どうしてもすべての数字を動かさなければなりません。

どうしてかというと、$v_{ik}$ が $v_{jk}$ にグラフで結ばれたとすると、

実は、$v_{0k}$ は、$v_{ik}$ と $v_{jk}$ と既に結んでいましたから、

このとき、内周は３以下になってしまいます。

なので、$v_{i1},\cdots, v_{i6}$ と $v_{j1},\cdots v_{j6}$ を辺で結ぶ場合、

必ず、違う数字どうし結ぶ必要があります。

このように$S_6$ の外部自己同型を用いることで $n=50$, $d=7$, 内周5 の

グラフが作られました。

残すのは、$d=57$ の場合（$n=3250$,  内周5） のみですが、

$S_{56}$ には外部自己同型が存在しないから、

ムーアグラフも存在しないと結論づけるのは早計です。

外部自己同型ではない、別のアイデアでグラフが構成できるかもしれないからです。

というわけで、今のところ、内周 5, 次数 57, 頂点数 2350のグラフが存在するかどうかは未解決です。

総合科目II(第2回)part I

4/22に行った総合科目II(数学との出会い)

についての内容をまとめておきます。

第２回はグラフ理論をやるつもりでしたが、

前半はもう少し対称性についての話をしておこうと思いました。

そこで、

最初に出した、図形の対称性の話を使って復習をします。

鏡映群

鏡映とは線対称のことです。

なので、鏡映変換とは、線対称変換のことです。

つまり、例えば、平面上の曲線に沿った線対称のことです。

下のような正三角形があります。

正三角形には、対称軸となるものが３本あります。

下の図のように、その対称軸を　$A,B,C$ とおくことにします。

また、頂点には、下のように番号を振っておきます。

このとき、この軸に沿って線対称変換によって、三角形を写してやっても

正三角形自体変わりません。よって、第一回目の最初の方でやった

結論を考慮すると、この３つの対称軸は、正三角形の対称性ということになります。

これは対称性の復習です。

ここでやりたいことは、この対称性によって、三角形がどのように写されるかということです。それぞれの軸によって、三角形は、下のようになります。

このとき、頂点がどのように動いたかを記録しておくと、

$A\mapsto \begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}$

$B\mapsto \begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}$

$C\mapsto \begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}$

のように写されます。

まるで、右側は、対称群の元のように書いてあります。(わざとですが...)

どういういう意味かというと、1,2,3という点が、動いた先は、元々

どのような点の位置だったかを読み取っています。

そして、この右辺を対称群の元の積と $\sigma_i$ を用いて書いてやると、

$A\mapsto \sigma_2$

$B\mapsto \sigma_1\sigma_2\sigma_1$

$C\mapsto \sigma_1$

となります。また、$A,B,C$ 正三角形の対称軸を表していましたが、

その対称軸による対称変換と同一視しておけば、$A,B,C$ の間にも積が

定義できます。つまり、$B\cdot A$ として $A$ による対称変換を

した後に、$B$ による対称変換をするという具合にします。

そうすると、$B\cdot A$ に対応すると、

頂点がどこに行ったかを追っていくと、

となります。つまり、置換の書き方をすれば、$\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}=\sigma_2\sigma_1$

となります。

この置換は、$\sigma_2\sigma_1=\sigma_2\sigma_1\sigma_2\sigma_2$

と書き直すことができて、

$B\mapsto \sigma_2\sigma_1\sigma_2$

かつ、

$A\mapsto \sigma_2$

であるから、軸による積の関係と対称群としての積の関係がちょうど関係していることが分かります。

つまり、$R_3$ を正三角形の鏡映全体とその積を取ったもの全体とすると、

$f:R_3\to S_3$

のような写像が

$f_3(X\cdot Y)=f_3(X)\cdot f_3(Y)$

を満たしているのです。

上では、$X=B$, $Y=A$ の場合を確かめたのみですが、ほかの場合を確かめるレポートを出しました。

$f_3$ の中の $\cdot$ は、対称変換の

合成ですが、$f_3$ の外の $\cdot$ は、あみだくじの積からくる対称群の積ということになります。

この２つの積が $f_3$ という操作によって対応していると見ることもできます

ここで、よく見てみると、上の $B\cdot A$ は、120°の回転をしています。

つまり、鏡映を2つ合成すると、回転が生まれます。

よく考えたら、120°回転というのは、正三角形を不変にします。

つまり、回転も対称変換の仲間に入れるべきなのです。

ある変換が図形を変えないように動かすのなら、その合成(積)

も図形を変えないように動かします。

よって、$R_3$ というのは、鏡映全体の積を取ったものというより、

正三角形の対称変換全体ということができます。

ここで、$R_3$ がどれほどあるか数えましょう。

正三角形の一つの頂点1がまず対称変換によってどこに写るかを考えると、

そのパターンは全部で3種類あります。

また、1の隣の2は、その対称変換によって1の右隣に行くか、

左隣にいくかによって2種類あります。

もし、そのどちらかを決めれば、3の場所は、自動的に決まるので、

正三角形の対称変換は全部で、$3\times 2=6$ 種類となります。

つまり、$R_3$ の中には、6個の対称変換が含まれています。

また、

$f_3:R_3\to S_3$

は同型です。

結論として以下のことが成り立ったことになります。

結論

三角形の対称性のなす群と、あみだくじのなす群は同じものである。

ここで、同じものというのは、同型という意味です。

群を用いたことで、まったく違う出どころの

対象が群を用いて結びつけることができるようになります。

また、同じように、$R_n$ を正 $n$ 角形の対称変換とすると、1,2の行き先を決めれば、

自動的にそのほかの頂点の場所は決まるので、$R_n$ は全部で $2n$ 個の対称変換を含みます。

同じように、写像

$f_n:R_n\to S_n$ 

を定義することが出来ますが、これは、$R_n$ と $S_n$ に含まれる元の個数は

それぞれ、$2n$ と $n!$ ですので、両者の個数を比べてみても $n>3$ の場合は

全単射にはなりません。

総合科目II(第1回)

4/15に行った総合科目II(数学との出会い)
についての内容をまとめておきます。

対称性について
今回は群についての話です。

高校までに習った線対称・点対称を習いますが、
それは数学のどのようなメカニズムによって表されているのでしょうか。
また、いくつかの図形があるときにその対称性をどのように比べることが
できるでしょうか？

例えば、トランプのスートでは、ハート、クローバー、スペードの対称性は
ダイヤの対称性となんとなく異なる対称性があるように思えます。
このような対称性の違いについても群を用いていい表すことができます。

"群論"というのはそのような記述が出来たり比較できたりする
数学の言葉ですが、ここでは、群論自体はやらず、
そのいくつかの例についてやります。

ここで、対称性についての簡単な結論について書いておきます。

結論
ある図形の対称性とはその図形の変換ある数学的対象(図形)のにを表すものである。

あみだくじ
まず、あみだくじを考えます。
なぜ、突然あみだくじを考えたかというと、
あみだくじは、群論の群というものを身近に感じられる対称だからです。
あみだくじから作られる対称群(置換群)というものを使って
さまざまな対称性を記述することができるので、
その基礎として扱います。
対称性がどこに行ったのか、一旦忘れます。

通常あみだくじとは、下のような方法で、$n$ 本の線分に横に何本かの横線を
入れたものです。このとき、上に、1から$n$ までの番号をつけておきます。
下は $n=4$ の場合です。

上の番号からたどって、横線に出会ったら必ず横線をたどるという
法則で下まで行くことで、番号の対応関係を付けます。
上のようなあみだくじだと、$1$ は $4$ に行くことになります。
他も同じようにやると、$2$ は $2$ に行き、$3$ は $3$ に行きます。

このとき、対応関係をまとめると、
$$\begin{pmatrix} 1&2&3&4\\ 4&2&3&1 \end{pmatrix} \ \ \ \ (\ast)$$
となります。
上の数字の下に、その数字が向かう数字が書いてあります。

このとき、違う数字は必ず違う数字に向かっていることがわかります。
これを単射と言います。
また、すべての数字に対して、そこに向かって来る数字が存在します。
これを全射といいます。
単射かつ全射の対応を全単射といいます。
つまり、全単射とは、一対一の関係をいいます。

つまり、数字 $\{1,2,\cdots, n\}$ に対して、$\{1,2,\cdots, n\}\to \{1,2,\cdots, n\}$
という写像が全単射であるとは、$1,2,\cdots n$ の各数字に対して、
$1,2\cdots, n$ のどれかがただ一つ存在し、他と重ならないようになっている
ものをいうのです。上の対応関係やこのあみだくじの対応関係は
全単射になっています。

このような、$1$ から $n$ までの全単射全体を置換といいます。
このような全単射全体は、すべて数え上げると $n!$ 個あります。
これは、$(\ast)$ のように、$1$ から $n$ の並び替え全体と等しいからです。

この $n!$ 個の　$1,2,\cdots, n$ の並び替え、もしくは $1,2,\cdots, n$ から
$1,2,\cdots, n$ への全単射全体を $n$ 次対称群、もしくは置換群といい、
$S_n$ と書くことにします。

置換の積
置換のもっとも重要な性質は、置換同士の積が存在するということです。
つまり、$x,y\in S_n$ に対して、$x\cdot y\in S_n$ が定義できます。
$x$ に対するあみだくじの上に $y$ に対するあみだくじを重ねることによって
得られるあみだくじに対する置換を $x\cdot y$ と定義すればよいです。
このドット $\cdot$ は省略されますが、わかりにくければ、適宜補って
読んでください。$n=3$の 場合に考えると

のようになります。

上の積は、
$y=\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}$
$x=\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}$
であるから、

$x\cdot y=\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}\cdot \begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}=\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}$

となります。この計算は、$y$ の置換をたどって、$x$ の置換をたどることでも
得られます。
つまり、$1\to 2\to 1$、$2\to 3\to 3$、$3\to 1\to 2$ から上のような積が得られます。

また、この積は可換ではありません。
つまり、$xy=yx$ は一般には成り立ちません。

上の例でいえば、$xy=\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}$ であったが、

$yx=\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}\cdot \begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}=\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}$
となり、確かに異なっています。

注意として、可換ではないということは、どんな $x,y$ に対しても $xy= yx$ が
成り立たないということではなく、$xy\neq yx$ となる $x,y$ が少なくとも一つある
ということです。
なので、逆に、可換であるとは、どんな $x,y$ に対しても、$xy=yx$ が成り立たないと
いけません。

恒等置換の存在
置換群の中で最も重要な置換は、単位元です。
つまり、上の書き方でかけば、$\begin{pmatrix}1&2&\cdots &n\\1&2&\cdots& n\end{pmatrix}$
です。これは、$1,2,\cdots, n$ を並び替えたものが置換だったのですが、
元と同じように並び替える(むしろ並び替えない)方法です。
これも、置換と認めます。
何も置き換えを行わない置換ということです。
その置換は恒等置換といい、$e$ で表すことにします。


逆置換の存在
置換 $x\in S_n$  があれば、そのあみだくじを逆さにしたものを $y$ とすると、
$x\cdot y=e$ となります。
どうしてそうなるか、自分で考えてみてください。
このように、$x\in S_n$ に対して必ず、かけることで、恒等置換を産む元 $y$ が
存在するのです。
このとき、順番を入れ替えた $y\cdot  x=e$ も成り立ちます。

このような $x$ に対して $xy=e$ となる元 $y$ のことを逆置換(逆元)と言いい、
$x^{-1}$ と書き表します。

置換の記述方法と関係式
次に置換群の元を表示する方法を考えます。
あみあくじに帰ると、
全てのあみだくじからあらゆる置換を作れることは上で見た通りです。

あみだくじとは $n$ 本の縦線に対して、いくつかの横線を描いて得られていました。

つまり、$\sigma_i$ を $i$ 番目の縦線と $i+1$ 番目の縦線の間の
横線1本分の置換とします。ただし、$i=1,\cdots, n-1$です。下の例は $n=4$ の場合です。

全てのあみだくじは、この横線のパターンをいくつか組み合わせてできていますので、例えば、

としたとき、この置換は、$\sigma_i$ と積表示を用いて、

$\sigma_3\cdot \sigma_2\cdot \sigma_1\cdot \sigma_2\cdot \sigma_3\cdot \sigma_3\cdot \sigma_1\cdot \sigma_2\cdot \sigma_1$

とかけます。

しかし、置換群の積表示は、一意的には決まらなくて、同じ置換を表す異なる積表示があり得ます。

すぐわかるのは、同じ横線を続けて2回引いてやると、

それは、何もしないことと同じです。

つまり、$\sigma_i^2=e$ ということになります。

このような式を置換群の関係式と言います。

他にもこのような関係式が存在して、

以下のようになります。

定理(置換群の標準的な関係式)

置換群の関係式は以下のもので尽きる。

1. $\sigma_i^2=e$ ($i=1,\cdots n$)
2. $\sigma_i\sigma_{i+1}\sigma_i=\sigma_{i+1}\sigma_i\sigma_{i+1}$ ($i=1,\cdots, n-2)$
3. $\sigma_i\sigma_j=\sigma_j\sigma_i$  ($|i-j|\ge 2$ かつ、$1\le i,j\le n-1$)

最初のものは上で説明した通りですが、

2番目のものは、それほど明らかではありませんが、図を描いてみるとよくわかります。

一部レポート問題にもしました。

最後のものは、横線を入れるところがある程度遠かったら、どちらを先にやっても

構わないということです。これもあみだくじを描いてみると、納得します。

これによると、$n=3$ の置換を

$\{e,\sigma_1,\sigma_2,\sigma_1\sigma_2\sigma_1,\sigma_1\sigma_2,\sigma_2\sigma_1\}$

のように書き下すことができます。

巡回置換表示法

あらゆる置換は、ある数から出発すると、必ず元の数字に戻ってきます。

例えば、

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

とすると、$1\to 2\to 3\to 1$ と $4\to 5\to 4$

のように、これは、3回回っても戻るものと、2回回って戻るものが含まれています。

そのような置換を$(1,2,3)$ と $(4,5)$ のように表すことにします。

つまり置換 $(1,2,3)$ は、

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

を表し、置換 $(4,5)$ は、

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

を表します。

このように、ある数字から出発して、一周して元の数字に戻るだけの置換、

例えば、$(1,2,3)$ や $(4,5)$ を巡回置換と言います。

よって、

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

のように表すことができます。

これを、置換の巡回置換表示と言います。
また、$(4,5)$ のように、2つの数字のみ入れ替えて、ほかは入れ替えない巡回置換を
互換といいます。

また、これらの置換 $(1,2,3)$ と $(4,5)$ は互いは関係しないサイクルなので、
これらは可換です。つまり、どちらを先に書いても変わりません。
また、$(1,2,3)$ は、$(2,3,1)$ と書いても同じ巡回置換を表します。

内部自己同型

ここで、$\sigma\in S_n$ を選んで固定します。
このとき、次で定まる写像 $f_\sigma:S_n\to S_n$ を考えます。

$x\mapsto \sigma^{-1}x\sigma$

つまり、$x\in S_n$ に対して、$\sigma^{-1}\cdot x\cdot  \sigma$ を対応させる、

$S_n$ から $S_n$ への写像です。

この写像は、$S_n$ から $S_n$ への全単射になるのですが、

単射になることを示します。

$f_\sigma(x)=f_\sigma(y)$ であるとすると、$\sigma^{-1}x\sigma=\sigma^{-1}y\sigma$ が成り立ち、両辺に $\sigma$ を左からかけると、$x\sigma=y\sigma$

となり、$\sigma^{-1}$ を右からかけると、$x=y$ となります。

つまり、$f_\sigma(x)=f_\sigma(y)$ ならば、$x=y$ が成り立ったので、

$f_\sigma$ は単射であることがわかりました。

また、全射性の方はレポートに出しました。

つまり、任意の $x\in S_n$ に対して、$f_\sigma(y)=x$ となる $y\in S_n$ が

存在することを言えば良いのですが、

$y$ として、$\sigma x\sigma^{-1}$ とすると、

$f_\sigma(\sigma x\sigma^{-1})=\sigma^{-1}\sigma x\sigma^{-1}\sigma=x$

となり、$f_\sigma(y)=x$ が成り立つので、$f_\sigma$ が全射であることがわかりました。

全射かつ単射な写像を全単射というのだったから、$f_\sigma$ は全単射であることがわかり

ました。

また、$f_\sigma$ は全単射かつ、

$f_\sigma(x\cdot y)=f_\sigma(x)f_\sigma(y)$ が成り立ちます。

なぜなら、

$f_\sigma(x\cdot y)=\sigma^{-1}(xy)\sigma=\sigma^{-1}x\sigma\sigma^{-1}y\sigma=f_\sigma(x)f_\sigma(y)$

となるからです。

このように、$S_n$ から $S_n$ への写像で、全単射かつ $f_\sigma(x\cdot y)=f_\sigma(x)f_\sigma(y)$ が成り立つものを同型写像といいます。

この $f_\sigma$ のように、$\sigma^{-1}$ と $\sigma$ を左から、また、右から

かけて得られる同型写像のことを内部自己同型と言います。

自己というのは、写像が $S_n$ 自身に戻ってくるので、自己と言います。

また、内部自己同型の特徴として、

以下のものがあります。

定理(内部自己同型による巡回置換表示保存則)

内部自己同型 $f_\sigma$ によって、$x\in S_n$ の

巡回置換表示のタイプは変わらない。

巡回置換表示タイプとは、$x\in S_n$ を互いに交わらない巡回置換の積で書いたとき、

$(\ast, \ast ,\ast)(\ast,\ast)$ のような巡回置換の積の形をいいます。

ここで、$\ast$ には、何か数字が入り、例えば、$(1,2,3)(4,5)$ などとなります。

例えば、$n=3$ の時は、

$e$

$(\ast,\ast)$

$(\ast,\ast,\ast)$

の3種類あり、

$n=4$の場合は、

$e$
$(\ast,\ast)$
$(\ast,\ast,\ast)$
$(\ast,\ast,\ast,\ast)$
$(\ast,\ast)(\ast,\ast)$
の5種類あります。

この巡回置換の積の形が、一般の $n$ について何になるかという
問題を出しましたが、これは分割数 $p(n)$ というものになります。

最後に、置換群について深い定理を述べて終わります。

定理(外部自己同型)

$n=6$ の時に、自己同型 $S_n\to S_n$ で、
内部自己同型ではないものが存在する。

内部自己同型ではないものをここでは外部自己同型といいます。

どのようなものがそれになるかというと、
$g:S_6\to S_6$ を、
$g((1,2))=(1,2)(3,4)(5,6)$

$g((2,3))=(1,6)(2,4)(3,5)$

$g((3,4))=(1,4)(2,3)(5,6)$

$g((4,5))=(1,6)(2,5)(3,4)$

$g((5,6))=(1,3)(2,4)(5,6)$

とすることで得られます。

このように定めてやったものは、同型になることを示す必要がありますが、

これは、確かめるのは大変すぎるので一部だけを示してもらいました。

この写像が内部自己同型でないことは、上の定理からすぐにわかります。
もし、$g$ が内部自己同型であったとしたら、$(1,2)$ の行先は $(1,2)$ と同じ
タイプの巡回置換表示を持つはずです。
しかし、行先は互換３つの積としてかけているので、
$(1,2)$ とは違うタイプであることが分かります。
これは、上の、内部自己同型による巡回置換表示保存則定理と矛盾しますので、やはり、$g$ が外部自己同型であることが
わかります。

また、驚くべき事実として、

このように外部自己同型が存在するのは $n=6$ のときのみであることが知られて

おり、$n=6$ のときも、このような形のみということが証明されています。

なぜ、$n=6$ のときだけ？という疑問が残りますが、

これは置換群の深い事実だというほかありません。

置換群の外部自己同型については、以前の記事(リンク)にも

書きました。

このような外部自己同型が存在することは、たまに、応用があります。

その話題を第2回の授業で登場させます。