Coxeter element: a computational approach

2013-10-11

\(E_8\) 的结构
Coxeter 元
Coxeter 平面
进一步改进

虽然本文起了个英文标题，但内容完全是中文的，原因是我没有想到合适的中文标题。

如果你对李代数有所了解的话，相信很大概率你会见过下面的图案：（参考维基百科的 Lie algebra 词条）

它展示的是李代数 \(E_8\) 的根系图，李代数 \(E_8\) 的根系由八维欧式空间 \(\mathbb{R}^8\) 中的 240 个向量组成，每个向量恰好有 56 个与其距离最近的邻居。将这 240 个向量投影到一个特殊的二维平面（叫做 Coxeter 平面）就会呈现一个旋转对称的图案，你可以看到上图中的图案中，240 个投影点分布在 8 个圆周上，每个圆周包含 30 个均匀分布的顶点，所以它在角度为 \(\frac{2\pi}{30}\) 的旋转下是不变的。\(h=30\) 叫做 \(E_8\) 的 Coxeter 数。

这个现象并不是 \(E_8\) 独有的，对任何有限 Coxeter 群都有类似的结论成立，比如下图显示的是将 5 维超立方体的 32 个顶点和它们的边投影到其 Coxeter 平面后得到的图案：

有两个顶点被同时投影到了原点，其余 30 个顶点分布在 3 个圆周上，每个圆周包含 10 个均匀分布的顶点，所以其 Coxeter 数 \(h=10\)。

本文下面以 \(E_8\) 为例子，通过具体的计算来解释背后的数学。我会不加证明地引用 Humphrey 的教材《Reflection groups and Coxeter groups》中的结论（主要来自 3.16 小节）。

本文的代码在 Github 上。

David Madore 也有一个很棒的交互式网页可以绘制 \(E_8\) 的多种不同风格的图案。

\(E_8\) 的结构

我们知道 \(E_8\) 的 Dynkin 图为

其一组单根系为 \[\Delta=\begin{bmatrix}1&-1&0&0&0&0&0&0\\0&1&-1&0&0&0&0&0\\0&0&1&-1&0&0&0&0\\0&0&0&1&-1&0&0&0\\0&0&0&0&1&-1&0&0\\0&0&0&0&0&1&1&0\\-\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}\\0&0&0&0&0&1&-1&0\end{bmatrix}.\] 其中 Dynkin 图中编号为 \(i\) 的顶点对应的单根 \(\alpha_i\) 是矩阵的第 \(i\) 行。注意每个单根的长度是 \(\sqrt{2}\)，并不是单位向量，这样主要是为了书写方便。

其 Cartan 矩阵为 \[C=\left((\alpha_i,\alpha_j)\right)_{1\leq i,j\leq 8}=\begin{pmatrix}2&-1&0&0&0&0&0&0\\-1&2&-1&0&0&0&0&0\\0&-1&2&-1&0&0&0&0\\0&0&-1&2&-1&0&0&0\\0&0&0&-1&2&-1&0&-1\\0&0&0&0&-1&2&-1&0\\0&0&0&0&0&-1&2&0\\0&0&0&0&-1&0&0&2\end{pmatrix}.\]

每个单根 \(\alpha_i\) 对应一个单反射 \(s_i\)： \[s_i(v) = v - \frac{2(v,\alpha_i)}{(\alpha_i, \alpha_i)}\alpha_i = v-(v,\alpha_i)\alpha_i,\quad 1\leq i\leq 8.\] 这里 \((\,,\,)\) 是标准欧式内积。从这个表达式中你就可以看出让每个单根 \(\alpha_i\) 的长度是 \(\sqrt{2}\) 的好处了：\(\alpha_i\) 和它的余根 \(\frac{2\alpha_i}{(\alpha_i,\alpha_i)}\) 是相等的，所以关于 \(\alpha_i\) 的反射有上述简单的形式。

用代码来写的话，就是

import numpy as np

# A set of simple roots listed by rows of 'delta'
delta = np.array([
    [1, -1, 0, 0, 0, 0, 0, 0],
    [0, 1, -1, 0, 0, 0, 0, 0],
    [0, 0, 1, -1, 0, 0, 0, 0],
    [0, 0, 0, 1, -1, 0, 0, 0],
    [0, 0, 0, 0, 1, -1, 0, 0],
    [0, 0, 0, 0, 0, 1, 1, 0],
    [-0.5, -0.5, -0.5, -0.5, -0.5, -0.5, -0.5, -0.5],
    [0, 0, 0, 0, 0, 1, -1, 0]
])

# The cartan matrix:
cartan = np.dot(delta, delta.transpose())

所有单反射 \(\{s_i\}\) 生成的群 \(W\) 叫做 \(E_8\) 的 Weyl 群，这个群包含 696729600 个元素。单根系在 Weyl 群的作用下生成的集合 \(\Phi = \{w\cdot\alpha\,|\, w\in W, \alpha\in\Delta\}\) 叫做 \(E_8\) 的根系，\(\Phi\) 中包含 240 个不同的向量，\(W\) 在 \(\Phi\) 上的作用置换 \(\Phi\) 中的向量。

\(\Phi\) 中的向量从形式上看分为两类：

第一类包含 \((\pm1,\pm1,0,0,0,0,0,0)\) 的所有置换，即有两个分量是 \(+1\) 或者 \(-1\)，其余６个分量都是 0 的向量。这样的向量有 112 个。
第二类包含所有形如 \(1/2\times(\pm1,\pm1,\cdots,\pm1)\) 的向量，其中 \(-1\) 的个数是偶数。这样的向量有 128 个。

为了编程方便，我们可以把所有根都乘以 2，使得它们都是整数向量。于是生成根系 \(\Phi\) 的代码可以这样写：

import itertools

roots = []

# Roots of the form (+-1, +-1, 0, 0, 0, 0, 0, 0),
# signs can be chosen independently and the two non-zeros can be anywhere.
for i, j in combinations(range(8), 2):
    for x, y in product([-2, 2], repeat=2):
        v = np.zeros(8)
        v[i] = x
        v[j] = y
        roots.append(v)

# Roots of the form 1/2 * (+-1, +-1, ..., +-1), signs can be chosen
# indenpendently except that there must be an even numer of -1s.
for v in product([-1, 1], repeat=8):
    if sum(v) % 4 == 0:
        roots.append(v)
roots = np.array(roots).astype(int)

# Connect a root to its nearest neighbors,
# two roots are connected if and only if they form an angle of pi/3.
edges = []
for i, r in enumerate(roots):
    for j, s in enumerate(roots[i + 1 :], i + 1):
        if np.sum((r - s) ** 2) == 8:
            edges.append([i, j])

Coxeter 元

定义：将单反射 \(s_1,\ldots,s_8\) 按照任意顺序排列然后相乘得到的元素 \(\gamma\in W\) 叫做 Coxeter 元。

Coxeter 元不是唯一的，但它们互相都是共轭的 ¹。所以它们有相同的阶、特征多项式、和特征值。

定义：任一 Coxeter 元的阶叫做 \(W\) 的 Coxeter 数，记作 \(h\)。

由于 \(\gamma\) 是有限群 \(W\) 中的元素，所以 \(\gamma\) 的 8 个特征都形如 \[\{\zeta^{m_1},\ldots,\zeta^{m_8},0\leq m_i<h\}.\] 其中 \(\zeta\) 是本原 \(h\)- 次单位根。Humphreys 书中 3.16 小节证明了 \(\gamma\) 的特征值不可能是 1，所以每个 \(1\leq m_i<h\)。\(\gamma\) 如果有实特征值的话只有可能是 \(-1\)（对应 \(\zeta^{h/2}\)）。\(\gamma\) 的复特征值成对共轭出现，形如 \(\{\zeta^{m_i},\zeta^{h-m_i}\}\)。

一种经典的选择 Coxeter 元的方式是这样的：注意到 \(E_8\) 的 Dynkin 图的八个顶点可以分为 \(\{1, 3, 5, 7\}\) 和 \(\{2, 4, 6, 8\}\) 两组，同组中的顶点互不相邻，所以对应的单反射两两交换。记 \[x=s_1s_3s_5s_7,\quad y=s_2s_4s_6s_8.\] 则 \(\gamma=xy\) 是一个 Coxeter 元。

Coxeter 平面

现在来考察 Cartan 矩阵 \(C\)。我们断言 \(C\) 有一个特征向量 \({\bf c}\)，其所有分量都是正数，并且重数是 1。注意到 \(C\) 的对角线上都是 2，非对角线上的元素都非正，所以 \(2I-C\) 是一个非负矩阵。又由于 \(E_8\) 是不可约根系，所以 \(C\)，以及 \(2I-C\) 都是不可约矩阵。根据 Frobenius-Perron 定理，\(2I-C\) 的极大特征值重数是 1，并且它对应的特征向量 \({\bf c}\) 的分量都是正的。\({\bf c}\) 当然就是 \(C\) 的极小特征值对应的特征向量。

我们可以用 numpy.linalg.eigh 求出 Cartan 矩阵 \(C\) 的特征值和特征向量。

1 2	`eigenvals, eigenvecs = np.linalg.eigh(cartan) c = eigenvecs[:, 0]`

其中 eigenvecs 的列向量就是 \(C\) 的全部特征向量，它们是按照特征值递增的顺序排列的，所以第一列就是最小的特征值对应的特征向量，也就是我们要找的 \({\bf c}\)。

下面是 Humphreys 书中 77 页采用的记号：

设 \(\{\omega_i,1\leq i\leq 8\}\) 是 \(\Delta\) 的对偶基，即 \[(\alpha_i,\omega_j)=\delta_{ij}.\]

并设 \({\bf c}=(c_1,c_2,\ldots,c_8)\)，记 \[\lambda = \sum_{i\in I}c_i\omega_i,\quad \mu= \sum_{j\in J}c_j\omega_j.\] Humphreys 的书中论证了二维平面 \(P={\rm span}\{\lambda,\mu\}\) 在 \(x,y\) 的作用下都是不变的。实际上 \(x,y\) 作用在 \(P\) 上都是反射，从而 \(\gamma=xy\) 在 \(P\) 上的作用是一个旋转。这个旋转的阶就是 \(\gamma\) 的阶 \(h\)。由于 \(\gamma\) 置换根系 \(\Phi\)，所以如果我们把 \(\Phi\) 投影到平面 \(P\) 上，理论上应该会看到一个具有 \(h\) 阶旋转对称性的图案。（事实上就是本文开头的图片）

直接使用上面 \(\lambda,\mu\) 的定义来计算 \(\Phi\) 在 \(P\) 上的投影是很不方便的，因为其中涉及了对偶基 \(\{\omega_i\}\)。我们可以绕开对偶基的计算，这一点其实隐藏在 Humphreys 书中 78 页中：

如果记 \[\nu=\sum_{j\in J}c_j\alpha_j.\] 则 \(\mu=(1-c)\lambda+\nu\) 且 \(\nu\perp\lambda\)。这实际上说的就是 \(\nu\) 就是 \(\mu\) 垂直于 \(\lambda\) 的分量。类似地，如果记 \[\nu'=\sum_{i\in I}c_i\alpha_i.\] 则 \(\nu'\) 就是 \(\lambda\) 垂直于 \(\mu\) 的分量。于是 \(P={\rm span}\{\nu,\nu'\}\)。而 \(\nu,\nu'\) 的表达式中只涉及 \(\{\alpha_i\}\)，这就好办了。

代码可以这样写：（用 \(u,v\) 代替 \(\nu,\nu'\)）

I = [0, 2, 4, 6]
J = [1, 3, 5, 7]
u = sum(c[i] * delta[i] for i in I)
v = sum(c[j] * delta[j] for j in J)
u /= np.linalg.norm(u)
v -= np.dot(u, v) * u
v /= np.linalg.norm(v)

其中我们对 \(u,v\) 进行了 Gram-Schimdt 正交化，得到了 \(P\) 的一组正交基。

把 \(\Phi\) 投影到 \(P\) 上这一步就很简单了，只要对根系中的每个向量，计算它在 \(u,v\) 这组基下的坐标即可：

1	`roots_2d = [(np.dot(u, x), np.dot(v, x)) for x in roots]`

剩下的就是把这些点，和它们之间的边画出来了。具体的绘图过程这俩不再赘述。

注意：这里的内积是 Cartan 矩阵 \(C\) 给出的内积，\(u,v\) 的正交化和根系投影也都是在这个内积下。由于我们把 \(u,v\) 表示为了 \(\Delta\) 这组基的组合，所以 np.dot(x, u) 计算的实际上是 \(C\) 定义的内积下的投影。

进一步改进

如果你去看 Github 代码的话，会发现那里并不是完全按上面的逻辑写的。这是怎么回事呢？

前面的计算有个美中不足之处，就是我们需要显式地指定两个集合 \(I,J\)。这一步也是可以避免的，但是需要对 Cartan 矩阵 \(C\) 和 \(\gamma\) 进行更仔细的分析。下面的结论是在 Casselman 的文章中介绍的：

命题：\(2I + \gamma + \gamma^{-1}= (2I-C)^2\)。

我们可以计算验证一下这个恒等式确实是成立的。考察 \(\gamma\) 在 \(\Delta\) 这组基下的矩阵： \[\gamma=xy=\begin{pmatrix}0&-1&1&0&0&0&0&0\\1&-1&1&0&0&0&0&0\\-1&1&-1&1&0&0&0&0\\0&0&1&-1&1&0&0&0\\0&0&1&-1&2&-1&1&-1\\0&0&0&0&1&-1&1&0\\0&0&0&0&1&-1&0&0\\0&0&0&0&1&0&0&-1\end{pmatrix}.\] 于是 \[\gamma^{-1} = yx=\begin{pmatrix}-1&1&0&0&0&0&0&0\\-1&1&-1&1&0&0&0&0\\0&1&-1&1&0&0&0&0\\0&1&-1&1&-1&1&0&1\\0&0&0&1&-1&1&0&1\\0&0&0&1&-1&1&-1&1\\0&0&0&0&0&1&-1&0\\0&0&0&1&-1&1&0&0\end{pmatrix}.\] 于是 \[2I + \gamma + \gamma^{-1} = \begin{pmatrix} 1&0&1&0&0&0&0&0\\ 0&2&0&1&0&0&0&0\\ 1&0&2&0&1&0&0&0\\ 0&1&0&2&0&1&0&1\\ 0&0&1&0&3&0&1&0\\ 0&0&0&1&0&2&0&1\\ 0&0&0&0&1&0&1&0\\ 0&0&0&1&0&1&0&1 \end{pmatrix}=(2I - C)^2.\]

这个恒等式告诉我们，如果 \(e^{\pm i\theta}\) 是 \(\gamma\) 的一对共轭的复特征值，\(v\) 是 \(e^{i\theta}\) 或者 \(e^{-i\theta}\) 对应的特征值，则 \[(2I-C)^2(v)=(2+e^{i\theta}+e^{-i\theta})v=(4\cos^2\frac{\theta}{2})v.\] 即 \(v\) 是 \((2I-C)^2\) 的特征值为 \(4\cos^2\frac{\theta}{2}\) 的特征向量。

这看起来好像可以说，\(v\) 是 \(2I-C\) 的特征值为 \(\pm 2\cos\frac{\theta}{2}\) 的特征向量？但是我们不知道 \(\pm 2\cos\frac{\theta}{2}\) 是否都会出现，以及如果都出现的话重数是不是相等。

Casselman 论证了这确实是成立的：

命题：\(2I-C\) 和 \(C-2I\) 有同样的特征多项式。

根据这个命题，\(2I-C\) 和 \(C-2I\) 的特征值为 \(\lambda\) 的特征子空间有相同的维数。而后者是 \(2I-C\) 的特征值为 \(-\lambda\) 的特征子空间，所以 \(C-2I\) 的特征值为 \(\pm\lambda\) 的特征子空间维数是相同的。

设 \(V_s,V_{\bar{s}}\) 分别是 \(\gamma\) 的一对共轭的复特征值 \(s=e^{i\theta}\) 和 \(\bar{s}=e^{-i\theta}\) 对应的特征子空间，我们已经看到 \(P=V_s\oplus V_{\bar{s}}\) 是 \((2I-C)^2\) 的特征值为 \(4\cos^2\frac{\theta}{2}\) 的特征子空间。由于 \(2I-C\) 和 \((2I-C)^2\) 交换，所以 \(P\) 也是 \(2I-C\) 的不变子空间。\(2I-C\) 在 \(P\) 上是可对角化的，从而 \(P\) 是 \(2I-C\) 的特征值为 \(\pm 2\cos\frac{\theta}{2}\) 的特征子空间的直和。从而 \(P\) 是 \(C\) 的特征值为 \(2\pm2\cos\frac{\theta}{2}\) 的特征子空间的直和。

来验证一下？打印出刚才 numpy.linalg.eigh 返回的 \(C\) 的特征值如下：

1	`[0.01095621 0.51371035 1.18652671 1.58417662 2.41582338 2.81347329 3.48628965 3.98904379]`

第一个和最后一个之和是 4，第二个和倒数第二个之和也是 4，第三个和倒数第三个之和也是 4，第四个和第五个之和也是 4，所以 \(C\) 的特征值两两之和为 4，与理论相符！

一般来说 \(P=V_s\oplus V_{\bar{s}}\) 的维数未必是 2，所以 \(P\) 未必是一个平面。但是对 \(C\) 的极小特征值我们已经知道它的重数是 1，从而其极大特征值的重数也是 1，从而 \(P\) 是二维平面。所以 \(\gamma\) 作用在 \(P\) 上是一个角度为 \(\theta_0\) 的旋转。

从上面打印的结果可以看到 \[0.01095621 \approx 2-2\cos\frac{\theta_0}{2},\quad \theta_0\approx 2\arccos0.994521895\approx\frac{2\pi}{30}.\] 所以我们验证了 \(\gamma\) 在 \(P\) 上的作用是一个 30 阶的旋转，即 \(W\) 的 Coxeter 数是 30。

于是要求 \(P\) 的一组基，只要分别求出 \(C\) 的极小极大特征值对应的特征向量 \(u,v\)， \[\alpha=\sum_{i=1}^8 u_i\alpha_i,\quad \beta=\sum_{i=1}^8 v_i\alpha_i.\] 就是 \(P\) 的一组基。

上一篇：Wilson 均匀生成树算法

下一篇：Birkhoff 遍历定理