2022-12-18

表現論ゼミ活動報告

Wathematicaで行っている表現論ゼミの紹介をします！

ゼミの概要

発表担当をあらかじめ決めておいて発表する、輪講形式のゼミを行っています。雑談時間などを除くと平均3時間ほどで毎回のゼミをしています。ゼミ中の様子はこんな感じです。

<表現論ゼミ第21回>
リー群とリー代数の表現について、直和・テンソル積・双対空間の表現を構成しました。 pic.twitter.com/SFxa8LQKjd
— 理工系学術サークルWathematica (@wathematica) 2022年10月15日

基本情報

メンバー：数学科・応用数理学科のB3, B4　現在は4人
使用教科書：途中で教科書を変更しました。*1以下、[F-H], [Hall]と略記します。
- [F-H] William Fulton, Joe Harris "Representation Theory: A First Course"
- [Hall] Brian C. Hall "Lie Groups, Lie Algebras, and Representation Theory"
開始時期：2022年1月末
活動頻度：週1回、夏休みや試験前は休み
活動場所：大学内のホワイトボードがある部屋 or 黒板のある教室

内容について

表現論とは？

代数的な対象（e.g. 群、代数）が線型空間に対してどのように作用するかを記述するのが表現論です。「群などの代数的対象を直接調べるのは難しいから表現によって扱いやすい線型空間の理論によって解決する」「線型空間の対称性を記述する」などが表現論が重要である理由らしいです。内容に関する詳しい話はここではしませんが、有限群の表現は化学への応用・リー群の表現は量子力学をはじめとする物理学への応用があるそうです。

自分は「代数的組合せ論」を専門にしようと考えているのですが、そこでは当たり前のように表現論が使われているので自分で使えるようになりたいと思って勉強をしています。他のゼミメンバーは皆幾何学が専門で、幾何学的な具体例をたくさん扱うために表現論へのモチベーションがある、と話していました。

必要な予備知識、勉強方法

表現論は線型空間を扱っているので、線型代数の知識が非常にたくさん要求されます。さらに、リー群やリー代数の重要な具体例は多くが行列からなるものであるので、そこでも線型代数の知識がたくさん要求されます。*2逆に、線型代数を勉強したのでそれの応用を見たいという人はぜひ表現論を勉強してみてほしいです。

おすすは下の池田先生の本です！（B1の線型代数のみを仮定して表現論に必要な線型代数を最初に準備してくれます）

テンソル代数と表現論: 線型代数続論 | 池田岳 |本 | 通販 | Amazon

このゼミから受けた恩恵

モチベーションの維持と向上、これが一番です。以下、少し詳しく書きます。

誤った理解の防止

一人で本を読んでいるときは大丈夫だと思ったこともゼミで発表するとギャップに気づく、ということがあります。話すことで自分で気づく場合や人から言われて気づく場合がありますが、どちらにせよこれは一人で勉強しているだけでは得られないことなのでとてもありがたいことです。発表時に詰められるのはつらいですが…それも発表準備のモチベーションになるのでヨシ！

定期的な勉強の機会

自分はあまりいろいろなことが長続きしないのですが、ゼミ形式で勉強することによって長期的・計画的な勉強をすることができます。

必要な予備知識の補助

（これを期待して人に頼りきりでゼミをするのは良くないとは思いますが…）

このゼミでは他のメンバーが幾何学専攻なのでリー群・リー代数を扱うときの多様体、微分幾何に関して足りない知識を教えてもらっています。また、線型代数の勉強不足な部分についても助けてもらうことが多々あります。自分も他のゼミメンバーの役に立ちたい！とはいつも思っているのですが、残念ながら今のところは特にできていないのでたくさん勉強したいです。

線型代数力の向上

ゼミを始めたころに比べて、線型代数パワーがかなりあがりました。（e.g. 双対空間、テンソル代数、同時対角化、非退化双線型形式）まあ、まだまだ足りないですけど。

最後に

このゼミの今後の予定

しばらくは、Root systemやDynkin diagramが何なのか、それによって何がわかるのかなどを目標として進めていく予定です。余裕があれば、Kac-Moody algebraも少し触れたい…… あと個人的には、新潟に帰省するときに上越新幹線のE7系に乗りながらルート系のE_7について勉強したいと思っています。

過去の活動記録

せっかくの機会なので、今までのゼミ記録をここにまとめておきます。

第1回：1/28 [F-H] §1.1, 1.2
- 有限群の表現の基本
- Schurの補題、Machukeの定理
第2回：2/4 [F-H] §1.3, 2.1, 2.2
- S_3の表現
- 指標の導入と直交性
第3回：2/18 [F-H] §2.3, 2.4
- S_4, A_4の指標、射影公式
第4回：2/25 [F-H] §3.1
- S_5, A_5の指標
第5回：3/5 [F-H] §3.2, 3.3
- S_dの標準表現から得られる表現
- 誘導表現の存在と一意性
第6回：3/11 [F-H] §3.3
- Frobeniusの指標公式
第7回：3/25 [F-H] §3.4
- 群環
第8回：4/1 [F-H] §3.5
- 係数拡大と表現
第9回：4/8 [F-H] §3.5
- 双線型形式による特徴づけ
第10回：4/22 [F-H] §4.1
- S_dの表現について成立することを確認
第11回：5/6 [F-H] §4.2
- Young図形から既約表現の構成
第12回：5/13 [F-H] §4.3
- Frobenius Formulaの証明

（有限群の表現終了、リー群とリー代数の表現へ。）

第13回：5/20 [F-H] §7.1, 7.2
- Lie群の導入と具体例
第14回：5/27 [F-H] §7.2
- Lie群の具体例
第15回：6/10 [F-H] §8.1, 8.2
- Lie代数の導入と具体例
第16回：6/17 [F-H] §8.2, 8.3
- Lie代数の具体例と指数写像
第17回：6/23 [F-H] §8.2, 7.3
- 被覆空間とSecond Principle

（以降、[Hall]に変更。）

第18回：7/2 [Hall] §3.1 ~ 3.4
- Lie代数の可解性と冪零性
- 行列Lie群のLie代数
第19回：7/15 [Hall] §3.4 ~ 3.8
- 随伴表現の定義、SO(3)とSU(2)の関係
第20回：10/7 [Hall] §4.1, 4.2
- 表現の定義と複素化との関係
- SU(2)の既約表現の構成
第21回：10/14 [Hall] §4.3
- 表現の直和、テンソル積、双対
第22回：10/21 [Hall] §4.4
- ユニタリ表現、コンパクトLie群の完全可約性
第23回：10/28 [Hall] §4.6
- sl(2, C)の表現
第24回：11/11 [Hall] §4.7, 4.8
- so(3)とSO(3)の表現の関係
- 行列Lie群でないLie群の例
第25回：11/25 [Hall] §6.1~ 6.4
- sl(3, C)の表現：Highest weightを用いた分類
第26回：12/2 [Hall] §6.5, 6.6
- Highest weight (1, 1)の表現
- Weyl群によるweightの見直し
第27回：12/9 [Hall] §6.7, 6.8
- Weight Diagramに関する性質
第28回：12/16 [Hall] §7.1
- Lie代数のコンパクト実形から得られる諸性質

以上です！お読みいただきありがとうございました。

参考文献

William Fulton, Joe Harris "Representation Theory: A First Course"
Brian C. Hall "Lie Groups, Lie Algebras, and Representation Theory"
池田岳, テンソル代数と表現論
佐武一郎, 線型代数学

*1:Fulton, Harrisの本は非常に難しかったので諦めました。現在はHallの本を読んでいますが具体例が豊富でとても楽しく読み進められています。

*2:「表現論は線型代数！」「リー代数は線型代数！」と言っている人がよくいます

2022-06-29

四元数とその行列

〇Wathematicaというサークルで行われているアドベントカレンダー企画（アドベントするものは無し）の一環として書いた記事です。

はじめに

「四元数」というものを聞いたことがありますか？物理やプログラミングなどへの応用もあるようですが、今回は四元数自体の構造と各成分が四元数であるような行列について書きました。四元数は複素数の拡張のようなもので、加減乗除ができる構造をもちますが積についての交換法則が成り立ちません。そのため、扱う際に注意が必要となります。この記事の目標は、交換法則が成り立たないことによる不便さを感じて交換法則へのありがたさを実感すること・それ以外の性質（特に結合法則）が生きてくること・不便さの解消、などです。

はじめに
四元数の定義
- 具体的な計算
基本的な性質
- 演算構造
- 基本性質
四元数上のベクトル空間
- スカラー倍は右から
- 四元数のベクトル空間上の内積*
四元数の行列
- 行列と線型写像
- 行列のなす群*
四元数の複素数表示
おわりに
参考文献

*がついた項目は少しの群論やB1後期に扱うような線形代数の内容を前提としています。

四元数の定義

四元数の定義からはじめます。まず集合としては以下のようなものを考えます。

$\mathbb{H} := \{a + ib + jc + kd | a, b, c, d \in \mathbb{R} \}$

これは $4$ 次の実ベクトル空間とみることができます。ここで、 $i, j, k$ について以下の条件：

$i^2 = j^2 = k^2 = ijk = -1 \\ ij = -ji = k, jk = -kj = i, ki = -ik = j$

の下で、分配法則が成り立つように積を定めます（具体的な計算については次節で）。このようにして積を定義すると、結合法則が成り立つことが分かります（証明略）。しかし、交換法則については成立しません。実際、定義より明らかに

$ij = k \neq -k = ji$

となります。

具体的な計算

例えば、次のようにして積を計算します。

$(2 + 4j)( i + 3k) = 2i + 6k + 4ji + 12jk = 2i + 6k - 4k + 12i = 14i + 2k$

$(a + ib + jc + kd)j = ja + (ij)b + j^2c + (kj)d = aj + kb - b - id$

基本的な性質

演算構造

先ほど述べたとおり、もともとの $\mathbb{R}$ 線形空間としての和と上で定めた積について、結合法則・分配法則が成立して環*1になります。また、 $\mathbb{H} \ni q = a + ib + jc + kd$ に対して、 $q$ の共役 $\bar{q}$ を

$\bar{q} := a - ib - jc - kd$

と定めます。すると、頑張って計算することで $q \bar{q} = a^2 + b^2 + c^2 + d^2$ が得られます。 $q \neq 0$ のときこの値は常に正なので、複素数と同様に絶対値が定義でき、また

$\bar{q}^{-1} = \frac{1}{a^2 + b^2 + c^2 + d^2} \bar{q}$

により積についての逆元が存在します。よって、 $\mathbb{H}$ は斜体（加除環）*2になります。

基本性質

四元数は積について交換法則が成り立たないために様々な不都合が生じます。例えば、 $p, q \in \mathbb{H}$ について、 $\overline{pq} = \bar{p}\bar{q}$ は成り立ちません。その代わりに以下が成り立ちます。

$p, q \in \mathbb{H}$ について、 $\overline{pq} = \bar{q}\bar{p}$
$c \in \mathbb{C}$ について、 $jc = \bar{c}j$

これらは今後よく使います。ここでは証明は省略します（大変なので）。

四元数上のベクトル空間

スカラー倍は右から

実数・複素数の時と同様に、 $\mathbb{H}^n$ に対して $\mathbb{H}$ ベクトル空間としての構造を入れることを考えます。和は各成分ごとの和で定め、スカラー倍については後で行列を定義することで分かるある理由があって右からかけることを考えます。すなわち、

$\displaystyle \begin{pmatrix} v_1 \\ \vdots \\ v_n \end{pmatrix}\cdot q = \begin{pmatrix} v_1 q \\ \vdots \\ v_n q \end{pmatrix}$

としてスカラー倍を定めます。一般のベクトル空間についても同様にして定義します。

四元数のベクトル空間上の内積*

複素ベクトル空間 $V$ におけるエルミート内積とは、写像 $H: V \times V \rightarrow \mathbb{C}$ であって条件：

第一成分について共役線型　 $\forall \alpha, \beta \in \mathbb{C}, \forall v_1, v_2, w \in V, H(\alpha v_1 + \beta v_2, w) = \bar{\alpha} H(v_1, w) + \bar{\beta} H(v_2, w)$
第二成分について線型　 $\forall \alpha, \beta \in \mathbb{C}, \forall v, w_2, w_2 \in V, H(v, \alpha w_1 + \beta w_2) = \alpha H(v, w_1) + \beta H(v, w_2)$ 　
共役対称　 $\forall v, w \in V, H(v, w) = \overline{H(w, v)}$
正定値　 $\forall v \in V\setminus \{0\}, H(v, v) > 0$

を満たすもののことでした。最も基本的なものとして、 $\mathbb{C}^n$ における標準エルミート内積 $(\cdot , \cdot ) : \mathbb{C}^n \times \mathbb{C}^n \rightarrow \mathbb{C}$ が以下のように与えられます：

$\displaystyle v, w \in \mathbb{C}^n, (v, w) := {}^t\bar{v}w = \sum_{i = 1}^n \bar{v_i}w_i$

これは実際に内積の定義を満たすことが容易にわかります。これと同様にして、四元数上のベクトル空間にも四元内積を定めます。まず、定義としては複素数のときと同様の条件1 ~ 4を満たす写像とします。ただし、共役は四元数上でとります。また、 $\mathbb{H}^n$ における標準四元内積も同様にして定めます。すると同様にこれが内積の定義を満たすことが確認できるのですが、この確認には少し注意が必要です。ここでは3を確認します。

$\displaystyle \overline{(w, v)} = \overline{ \sum_{i = 0}^n \bar{v_i}w_i } = \sum_{i = 0}^n \overline{\bar{v_i}w_i} = \sum_{i = 0}^n \bar{w_i}\bar{\bar{v_i}} = \sum_{i = 0}^n \bar{w_i}v_i = (w, v)$

四元数の行列

行列と線型写像

実数と複素数のときと同様に、各成分が四元数の行列（四元行列）を考えます。簡単のため、以下では正方行列のみを考えます。ここで、行列の積は実数や複素数のときと同じように定めてスカラー倍については先ほどと同様に右から作用させます。 $\mathbb{R}$ や $\mathbb{C}$ のときと同様に、行列は線型写像を与えるものであってほしいです。そこで、これを確認してみます。和を保つことは複素数のときと同様なのでスカラー倍を保つことを確認します。 $A$ を $n$ 次正方行列、 $v \in \mathbb{H}^n, q \in \mathbb{H}$ について、

$(Av) \cdot q = \begin{pmatrix} \sum_{i = 1}^n a_{1i} v_i \\ \vdots \\ \sum_{i = 1}^n a_{ni} v_i \end{pmatrix} \cdot q = \begin{pmatrix} \sum_{i = 1}^n ( a_{1i} v_i ) \cdot q \\ \vdots \\ \sum_{i = 1}^n ( a_{ni} v_i ) \cdot q \end{pmatrix} = \begin{pmatrix} \sum_{i = 1}^n a_{1i} ( v_i q ) \\ \vdots \\ \sum_{i = 1}^n a_{ni} ( v_i q) \end{pmatrix} = A (v \cdot q)$

となるので、スカラー倍を保つことが分かります。（結合法則えらい！！！）ここで、 $\mathbb{H}$ 上のベクトル空間に対するスカラー倍を右から作用させたことが生きています。行列は左からかけたいため、それと干渉しないようにスカラー倍は右から作用させたのです。また、四元行列に対する転置は実行列・複素行列と同様に、共役は各成分について共役をとった行列、というように定めます。

行列のなす群*

実数や複素数成分の正則行列全体は、行列の積について $\mathrm{GL}_n (\mathbb{R}), \mathrm{GL}_n (\mathbb{C})$ という群をなすのでした。これと同様にして $\mathrm{GL}_n (\mathbb{H} )$ を「各成分が四元数の正則行列全体」と定義します。注意点として、 $\mathbb{H}$ の非可換性から行列式による特徴づけ（行列式が非零と正則性が同値）はうまくできません。（その代わりにどうするかについては参考文献[3]に載っています。）

また、実行列において標準内積を保つ行列（直交行列）全体のなす直交群 $\mathrm{O}(n)$ ・複素行列において標準エルミート内積を保つ行列（ユニタリ行列）全体のなすユニタリ群 $\mathrm{U}(n)$ があったのと同様に、四元行列において標準四元内積を保つ行列全体にも群構造が定まります。これをシンプレクティック群といい、 $\mathrm{Sp}(n)$ と表します。 $n$ 次正方四元行列 $A$ が標準四元内積を保つとは、

$\displaystyle \forall v, w \in \mathbb{H}^n, (Av, Aw) = (v, w)$

が成り立つことなので、

$\displaystyle \forall v, w \in \mathbb{H}^n, {}^t(\overline{Av})Aw ={}^t \bar{v} {}^t \bar{A} Aw = {}^t \bar{v} = w \iff {}^t A A = E_n$

となります。*3 よって、

$\displaystyle \mathrm{Sp}(n) = \{ A \in \mathrm{GL}_n | {}^t\bar{A}A = E_n \}$

と表せます。これが群をなすことは $\mathrm{O}(n), \mathrm{U}(n)$ と同様にして確認できます。これは、よく知られている実シンプレクティック群・複素シンプレクティック群とは別物ですが、後者の複素シンプレクティック群とは関係があります。それについては次の章で述べます。

四元数の複素数表示

表示方法の設定

今までみてきたように、四元数における積は非可換であるため非常に扱いづらいです。そこで、複素数を用いて表すことを考えます。四元数の演算法則に注意すると、 $q \in \mathbb{H}$ は $q = a + ib + jc + kd = (a + ib) + j(c - id)$ と表せます。ここで、 $a + ib, c - id \in \mathbb{C}$ であることから、四元数の各元は $u + jv, u, v \in \mathbb{C}$ と表すことができると分かります。この表示方法をみて、 $q = a + ib + jc + kd = (a + ib) + (c + id)j$ というように表したほうが分かりやすいじゃないか！と思った方がいるかと思います。（自分もそう思いました）しかし、これには理由があります。それは、「 $\mathbb{C}$ 上のベクトル空間としてみたときに $\mathbb{H}$ が $\mathbb{C}^2$ と自然に同型になってほしいから」です。ここでいう「自然な同型」とは、複素数表示したときの二つの元を対応させる写像によって同型になる、という意味です。まず、先に述べた良い定義で考えてみます。 $\mathbb{H}$ から $\mathbb{C}^2$ への写像を、 $\mathbb{H} \ni q = u + jv \mapsto (u, v)$ と定めます。これは全単射になります（証明略）。また、 $\mathbb{C}$ 線形写像になっていることが確認できます。実際、

$(u + jv) \cdot c = uc + jvc \mapsto (uc, vc) = (u, v) \cdot c$

となっています。（スカラー倍は右から作用させていることに注意）一方、だめな定義の方で考えると、

$(u + vj) \cdot c = uc + vjc = uc + j\bar{v} c \mapsto (uc, \bar{v}c) \neq (u, v) \cdot c$

となってしまいます。

四元行列の複素数表示*

次に、四元行列についても複素数表示を考えてみましょう。便利のため、 $n$ 次正方複素行列全体を $\mathrm{M}_n (\mathbb{C} )$ 、 $n$ 次正方四元行列全体を $\mathrm{M}_n (\mathbb{H} )$ と表します。各 $A \in \mathrm{M}_n (\mathbb{H} )$ は、 $X, Y \in \mathrm{M}_n (\mathbb{C})$ を用いて $A = X + jY$ と一意的に表せることに注意して、写像 $\psi_n : \mathrm{M}_n (\mathbb{H} ) \rightarrow \mathrm{M}_{2n} (\mathbb{C})$ を、

$\displaystyle \psi_n (X + jY ) = \begin{pmatrix} X & -\bar{Y} \\ Y & \bar{X} \end{pmatrix}$

と定めます。すると、単純な計算によりこれが単射環準同型を与えることが分かります。*4そこで、 $A \in \mathrm{M}_n(\mathbb{H})$ に対して $\psi_n (A)$ を $A$ の複素数表示といいます。一般に、「環準同型の乗法群への制限は乗法群から乗法群への群準同型を与える」*5ことが示せるので、 $\psi_n$ の $\mathrm{GL}_n(\mathbb{H})$ への制限を考えることによって、

$\psi_n |_{\mathrm{GL}_n(\mathbb{H})}: \mathrm{GL}_n (\mathbb{H}) \rightarrow \mathrm{GL}_{2n} (\mathbb{C})$

という単射群準同型が得られます。

シンプレクティック群再考*

最後に、上で得られた単射群準同型によるシンプレクティック群 $\mathrm{Sp}(n)$ の像を考えてみましょう。その前に、まずは全体の像 $\psi_n (\mathrm{M}_n(\mathbb{H})$ を考えてみます。頑張って計算することにより、

$\displaystyle J_n := \begin{pmatrix} 0 & E_n \\ -E_n & 0 \end{pmatrix}$

として、

$\displaystyle \psi_n ( \mathrm{M}_n(\mathbb{H} ) = \{ A \in \mathrm{M}_{2n} (\mathbb{C}) | J_n A = \bar{A} J_n \}$

であることが分かります。*6 $\mathrm{GL}_n(\mathbb{H})$ への制限による像も同じように記述できます。同じように、頑張って計算することにより、

$\displaystyle \psi_n (\mathrm{Sp}(n) ) = \{ A \in \mathrm{GL}_{2n} (\mathbb{C}) | J_n A = \bar{A} J_n, {}^t\bar{A}A = E_{2n} \}$

と分かります。*7ここで、一つ目の条件式に対して両辺に左から ${}^t A$ をかけることにより、二つ目の条件式を用いることで、

${}^t A J_n A = {}^t A \bar{A} J_n$

さらに二つ目の条件式を用いることで右辺は、

${}^t A \bar{A} J_n = {}^t \bar{\bar{A}} \bar{A} J_n = J_n$

と変形できます。以上より、

$\displaystyle \psi_n (\mathrm{Sp}(n) ) = \{ A \in \mathrm{GL}_{2n} (\mathbb{C}) | {}^t A J_n A = J_n, {}^t\bar{A}A = E_{2n} \}$

と表せます。複素シンプレクティック群 $\mathrm{Sp}(2n, \mathrm{C} )$ が、

$\displaystyle \mathrm{Sp}(2n, \mathrm{C} ) := \{ A \in \mathrm{GL}_{2n} (\mathbb{C} | {}^t A J_n A = J_n \}$

と定義されていたこと、ユニタリ群 $\mathrm{U}(2n)$ が、

$\displaystyle \mathrm{U}(2n) = \{ A \in \mathrm{GL}_{2n} (\mathbb{C}) | {}^t \bar{A} A = E_{2n} \}$

と表せたことを思い出すと、

$\displaystyle \psi_n (\mathrm{Sp}(n)) = \mathrm{Sp}(2n, \mathbb{C}) \cap \mathrm{U} (2n)$

が得られます。これが四元数によるシンプレクティック群と複素シンプレクティック群の関係です。（実シンプレクティック群・複素シンプレクティック群については、「交代非退化双線形形式を保存する変換」として特徴づけることができます。このあたりの話についてもいつか書きたいと思っています。）

おわりに

かなり雑でよくわからない記事になってしまいました。可換性がなくなると、いつも当たり前にできていることが成り立たなくなってしまうことがあります。四元数を扱っていると、可換性のありがたさを感じます。また、それを解消するための工夫（右からの作用・複素数表示）なども面白いと思います。はじめに述べたように、四元数には様々な応用があるようなのでそれについても勉強してみたいです。長い文章となってしまいましたが、読んでいただきありがとうございました！！

参考文献

[1] William Fulton, Joe Harris "Representation Theory A First Course" この記事の内容は、この本でゼミをしているときに分からなかったことを他の本で調べて自分でまとめたものがもとになっています。

[2] Lowing W. Tu "トゥー多様体" この本の付録に四元数の話が載っています。

[3] 井ノ口順一 "はじめて学ぶリー群" とても分かりやすい。

[4] 雪江明彦 "代数学1 群論入門"

*1:簡潔にいうと、足し算・引き算・掛け算ができる集合

*2:足し算・引き算・掛け算・割り算ができるが掛け算について交換法則が成り立たない集合

*3: ${}^t(AB) \neq {}^t B {}^t A$ ですが、 ${}^t(\overline{AB}) = {}^t \bar{B} {}^t \bar{A}$ は成立します。

*4:本当は $\mathbb{C}$ 代数の凖同型になってほしいんですけど、うまくいきません。どなたかいい方法をご存じでしたら教えてください。

*5: $f: A \rightarrow B$ を環準同型とすると、 $f|_{A^\times}$ が乗法を保つことは明らかなので、 $\forall a \in A^{\times}, f(a) \in B$ であることを言えばよい。 $f(a)f(a^{-1}) = f(1) = 1, f(a^{-1})f(a) = f(1) = 1$ より $f(a)^{-1} = f(a^{-1})$ なのでOK。

*6:ブロックに分けて計算する。 $(\supset )$ の方が大変。

*7:それぞれ元をとって計算すれば比較的簡単に示せる。

2021-12-15

Burnside の補題を用いた数え上げ【Wathematicaアドベントカレンダー】

はじめましての方ははじめまして。Wathematica2年のchimakiと申します。Wathematica Advent Calender 2021 の12/16日の記事になります。個人的に好きなBurnsideの補題について書こうと思います。

（もくじ）

問題設定
Burnsideの補題
問題を解く
おまけ
最後に
参考資料

問題設定

問題１

立方体を $n$ 色以下で塗る場合の数は何通りあるか。ただし、回転などにより重なるものは同じとみなす。

　この問題について考えていきます。高校数学では、異なる6色で塗分ける場合の数や同じ色が隣り合わないよう異なる5色で塗る場合の数を求める問題を円順列や数珠順列の考え方を応用することで解くことができましたが、この問題においては「同じ色は隣り合わない」という制約が外れており、難しくなっています。例えば、次の2つの図のような塗り方を同じとみなす必要があります。（雑な図でごめんなさい）

f:id:chimaki_yama821:20211215172936p:plain — これらは同じ

それではこの問題について考えてみましょう。

　こういう問題は小さいnについて考察してみると何か見えてくることが多いです。しかし、n＝2の場合でもどの塗り方が回転で重なり合うのか見つけるのは容易ではありません。（ちなみn＝2の場合は10通り、n＝3の場合は57通りになります。気になる人は頑張って試してみてください、おすすめはしません）

Burnsideの補題

そこで本稿の主題であるBurnsideの補題を使うことを考えます！まずはBurnsideの補題の主張をみていきましょう。

命題の主張と解釈

　Burnsideの補題の主張は以下の通りです。

Burnsideの補題

有限群 $G$ が集合 $X$ に作用するとする。また、 $g \in G$ に対いて $g$ によって固定されるすべての $X$ の元からなる集合を $\mathrm{fix}(g)$ とする。このとき、軌道の数は $\frac{1}{|G|} \sum_{g \in G} | \mathrm{fix} (g) |$ である。

…………。何言ってるかさっぱりわかりませんね。。。

まず「群」ってなんだよ！って感じだし「作用」も分からないし、「軌道」も意味が分からない。本当にこの命題がさっきのような問題解決につながるの？って感じです。

（群論に詳しい方はこの定理を最初の問題にどう使うか考えてみてください）

具体例：正方形の頂点塗り分け

　そこで、具体的な問題を通してこの定理を解釈していきましょう。具体例を考えると分かりやすいのですが最初から立方体の面の塗分けを考えるのは難しいので次のような問題を考えてみます。

問題２

正方形の各頂点を青か黄色で塗り分ける方法は何通りあるか。ただし、回転させて同じものは同じとみなす。
（ここでは簡単のため裏返しは考えないこととします。つまり、裏返したときに同じ塗り方になっても別とみなします。）

　この問題にBurnsideの補題を応用するために適切に群 $G$ や集合 $X$ を定める必要がありますが、そこはなんとなくノリをつかめればOKです！

　まず、群 $G$ が集合 $X$ に作用しているとは、「集合 $X$ には $G$ という群によってあらわされるような対称性がある」ということです。そして結論部分である「軌道の数」とは、「群 $G$ による対称性によって同じものを同一視したときの場合の数」になります！求める場合の数がこの「軌道の数」に一致するように $G$ と $X$ を定めていきます。（要するに「群」ってやつが対称性をあらわすんだな～ってことです）

　これを上の問題2で考えましょう。正方形は $90^{\circ}, 180^{\circ}, 270^{\circ}$ 回転させてもまた同じ形になります。また、当然ですが $0^{\circ}$ 回転させる（つまり何もしない）という操作に対しても形は保たれます。

　このことから、平面上の正方形には「 $0^{\circ}, 90^{\circ}, 180^{\circ}, 270^{\circ}$ 回転」に対する対称性があるといえます。この4つの回転こそがこの問題における群 $G$ です。

　そして、今回の問題では集合 $X$ は以下の図のようなものとしましょう。

f:id:chimaki_yama821:20211212205047p:plain — 集合X　16個からなる

つまり、対称性を無視して全ての塗り方を考慮した集合を $X$ と定めるのです。このとき、例えば下の図のような $G$ から $X$ への作用があります。

f:id:chimaki_yama821:20211215172738p:plain — 作用の図

　さて、これで「有限群 $G$ が集合 $X$ に作用するとする」の部分は分かりました。では次に「 $g \in G$ に対して $g$ によって固定されるすべての $X$ の元からなる集合」という部分を見てみましょう。 $G$ は対称性を表すものなので、今回の問題では上の考察から $g \in G$ は、 $0^{\circ}$ 回転・ $90^{\circ}$ 回転・ $180^{\circ}$ 回転・ $270^{\circ}$ 回転のいずれかとなります。

　まず、「 $g = 90^{\circ}$ 回転」として考えてみます。すると、先ほどの図で定めた $X$ の元のうち、 $90^{\circ}$ 回転させても変わらないものは以下の2つになります。 $270^{\circ}$ 回転の場合も同じです。

f:id:chimaki_yama821:20211215173533p:plain — 90°、270°回転で不変な塗り方

　次に、「 $g = 180^{\circ}$ 回転」として考えてみます。これによって固定される $X$ の元は以下の4通りです。

f:id:chimaki_yama821:20211215173617p:plain — 180°回転で不変な塗り方

　最後に、 $0^{\circ}$ 回転に対して不変なものは $X$ の元全てであることに注意しておきましょう。

　以上によって、「各 $g \in G$ に対して $g$ によって固定されるすべての $X$ の元からなる集合」が分かりました。

　ではBurnsideの補題の結論の部分の解釈です。最初に述べたとおり、「軌道の数」とは「群 $G$ による対称性によって同じものを同一視したときの場合の数」になります。つまりこの問題では「回転で重なるものを同一視したときの頂点の塗り方」（求めたかったやつ！）がこれにあたるのです！そしてBurnsideの補題の主張から、これが「各 $g \in G$ に対して不変な $X$ の部分集合の要素数の和をとり、対称性の数で割ったもの」と等しくなることが分かります。

　今述べたことを図示するとこんな感じです。

f:id:chimaki_yama821:20211215174258p:plain

よって、この問題の場合の数は

$\frac{1}{4}(2×2 + 4 + 16) = 6$ 通り

と求めることができます！

　以上の例から、Burnsideの補題は次のように応用できると分かります！！

対称性のあるものの数え上げ

対称性のあるものの数え上げは、以下のようにして求められる。
1. 対称性をとらえる
2. それぞれの対称性について不変なものを数え上げる（このときは対称性を無視して全て数える）
3. 2で数えたものを全ての対称性について和をとり、「対称性の数」で割る。

ｎ色で塗る場合

　上と同様の考え方により、頂点を $n$ 色で塗る場合の数も求めることができます！

　 $90^{\circ}, 270^{\circ}$ 回転で不変なものはどちらの場合も全ての頂点の色が同じ場合の $n$ 通りです。よって合計で $2n$ 通りとなります。

　また、 $180^{\circ}$ 回転で不変なものは対角線上の2頂点を同じ色で塗る場合の $\times n^2$ 通りです。

　そして、 $0^{\circ}$ 回転で不変なものは $n^4$ 通りです。

　以上より、求める場合の数は $\frac{1}{4} (n^4 + n^2 + 2n)$ 通りと分かります！

（余談ですが、「場合の数は必ず整数になる」ということから上の式の分母「 $n^4 + n^2 + 2n$ 」が4の倍数であることが分かります！）

問題を解く

　さて、Burnsideの補題の使い方が少しわかったところで実際に立方体の塗分けを考えていきましょう。先ほどの数え上げ方法をもう一度見直しておきます。

対称性のあるものの数え上げ

1. 立方体の対称性をとらえる

　まずは立方体の対称性について考える必要があります。これは厳密にやろうとするとむずかしいのですが、以下のように解釈できます。

立方体の対称性(A) 何もしない
(B) 向かい合う２面の中心を結ぶ直線を軸として $90^{\circ}, 180^{\circ}, 270^{\circ}$ 回転
(C) 立方体の中心とある頂点を結ぶ直線を軸として $120^{\circ}, 240^{\circ}$ 回転
(D) 立方体の中心とある辺の中点を結ぶ直線を軸として $180^{\circ}$ 回転

（分かりにくいかもしれません……この後図を使って説明するのでいったん飛ばしちゃって大丈夫です）

　これらそれぞれについて、何通りの対称軸がとれるかみてみましょう。

それぞれの操作に対する対称軸

(A) について

動かさないのは1通りしかありません。

(B) について

以下の図のように3通りあります。

f:id:chimaki_yama821:20211215175034p:plain

以下の図のように4通りあります。

f:id:chimaki_yama821:20211215175102p:plain

(D) について

6通りです。詳しくは各自で確認してみてください。

(A) ~ (D) より、対称性の数は合計で、

(A) : 1通り

(B) : 3 × 3 = 9 通り

(D) : 1 × 6 = 6 通り

であるので、1 + 9 + 8 + 6 = 24 個になります！

これで立方体の対称性が分かりました！

2. 各対称性で不変な塗り方

　次に各対称性を表す操作（回転）について不変な塗り方を数えていきましょう！

(A) について

どのような塗り方を考えても「何もしない」という操作の下では不変であるので、各面を $n$ 色で塗ることを考えることにより、 $n^6$ 通りです。

(B) について

　 $90^{\circ}, 270^{\circ}$ の場合と $180^{\circ}$ の場合で異なるので注意が必要です。

　まず、 $90^{\circ}, 270^{\circ}$ 回転によって不変になる場合を考えます。そのためには、回転軸を含む二つの面は自由に塗り、その他の4面を同じ色で塗る必要があります。よって、前者の二つの面の塗り方が $n^2$ 通り、後者の4面の塗り方が $n$ 通りなので合計 $n^3$ 通りとなります。

f:id:chimaki_yama821:20211215232755p:plain — 90°、270°回転で不変な塗り方

　次に、 $180^{\circ}$ 回転によって不変になる場合を考えます。そのためには、回転軸を含む二つの面は自由に塗り、その他の4面を向かい合う2面同士が同じ色になるように塗る必要があります。よって、前者が $n^2$ 通り、そのそれぞれに対し後者が $n^2$ 通りなので合計 $n^4$ 通りとなります。

　 $120^{\circ}, 240^{\circ}$ 回転どちらの場合でも、回転軸を上2つの頂点に対して一方の頂点側にある3面を同じ色で、他方の頂点側にある3面を同じ色で塗る必要があります。前者の選び方が $n$ 通り、そのそれぞれに対し後者が $n$ 通りなので合計 $n^2$ 通りとなります。

(D) について

　頑張ると、 $n^3$ 通りであることが分かります。（各自で考えてみてください）

以上により、各対称性を表す操作に対して不変な塗り方が求まりました！

あとはこれらに対してBurnsideの補題を適用すると答えがでます！！

3. 2で数えたものから答えを求める

　さて、仕上げです。『2で数えたものを全ての対称性について和をとり、「対称性の数」で割る。』を実際に行っていきましょう！これは以下のように求めることができます。

f:id:chimaki_yama821:20211215175700p:plain

これを整理することにより、

$\frac{1}{24}(n^6 + 3n^4 + 12n^3 + 8n^2)$ 通り

と求めることができました！！！

（なお、n = 6の場合からn = 5の場合を引くことでちょうど6色で塗る場合の数を求めることもできます）

おまけ

　いかがでしたでしょうか。Burnsideの補題が対称性のあるものの数え上げにとても役立つことが伝わったでしょうか。ちなみにこの定理は「Cauchy-Frobeniusの定理」とも呼ばれるらしいです。この定理は、「ぐ・こ・き」で知られる位数に関する定理やLagrangeの定理を使うことで証明することができます。（証明は[2], [3]に載っています。そんなに難しくないです）また、群論にある程度慣れている人だと立方体の対称性が4次対称群で表されることをご存じだと思うのですが、そのときの「置換の型」の考え方が塗り分けにおける大きな役割を果たしています。これを生かして「サイクルインデックス」というものを導入し、定理をより使いやすい形に書き直すこともできるようです。（一緒に[3]を読みましょう！）また、この定理は表現論を使って証明することもできるようです。（自分は詳しく知りません）そして、競技プログラミングの問題に応用することもあるらしいです。

最後に

　今回は前提知識なしで読めるようになるべく群論のことばを使わずに書いてみました。ですが定理の証明やより深い理解のためには群論が必須です。おすすめは参考文献[1]の本です。

　「一人では厳しい……」というそこのあなた！！！Wathematicaでこれから群論ゼミが開催されるらしいですよ！！！！！

参考資料

[1] 雪江明彦. 群論入門 / 雪江明彦著. 東京, 日本評論社, 2010

[2] Godsil, C. D. (Christopher David), Royle, Gordon. Algebraic graph theory / Chris Godsil, Gordon Royle. New York, Springer, 2001

[3] Aigner, Martin. A Course in Enumeration [electronic resource] / by Martin Aigner. 1st ed. 2007., Berlin, Heidelberg, Springer Berlin Heidelberg, 2007

[4] Liu, Chung Laung, 伊理正夫, 伊理由美. 組合せ数学入門. 1 / C.L.リウ著 ; 伊理正夫,伊理由美共訳. 東京, 共立出版, 1972.