形式陈述
设 E 是维数 r ≥ 1 的实内积空间 理路 内积空间 Inner product space 带正定对称双线性形式或正定 Hermitian 半双线性形式的向量空间。 ,内积记为 ( , ) 。对非零向量 α ,关于垂直超平面 α ⊥ 的反射是
(1) s α ( v ) = v − 2 ( α , v ) ( α , α ) α . 它是Householder反射 理路 Householder 反射 Householder reflection · Householder transformation 用一个向量紧凑表示酉反射,把整段向量化到单一坐标方向,并作为稳定 QR 的基本原语。 的实内积版本:在 α 方向乘以负一,在 α ⊥ 上保持恒等。这里将反射用于有限几何配置,而不是重新构造数值QR。
一个有限、约化、结晶根系 是有限集合 Φ ⊂ E ∖ { 0 } ,满足:
Φ 张成 E 。
若 α , c α ∈ Φ ,则 c ∈ { 1 , − 1 } ;这是约化性 。
对所有 α , β ∈ Φ ,数(2) a α β = 2 ( α , β ) ( α , α ) 都为整数;这是结晶性 。
每个根的反射都保持整个根集合:s α ( Φ ) = Φ 。
集合中的向量称为根,r 称为秩。由 s α ( α ) = − α ,根总成正负对。本文中的“根系”均指上述完整合同;有些教材将非约化或非结晶配置也称为根系,使用结论时须重新核范围。
固定内积后,可把余根写成向量 α ∨ = 2 α / ( α , α ) ,于是 a α β = ( α ∨ , β ) 。更抽象的余根原本是线性函数 v ↦ a α v ;本页已明确用内积识别向量空间与其对偶。
正根与简单根的输出
选一个向量 h ∈ E ,要求 ( h , α ) ≠ 0 对每个根成立,称它避开全部根超平面。定义
(3) Φ + = { α ∈ Φ : ( h , α ) > 0 } , Φ − = − Φ + . 正根 α 若不能写成两个正根之和,就称为简单根 。全部简单根构成集合 Δ ,并满足:
Δ = { α 1 , … , α r } 是 E 的一组基 理路 向量空间的基 Basis of a vector space 同时线性无关并张成整个向量空间的向量组。
每个正根唯一写成 β = ∑ i c i α i ,其中 c i ∈ Z ≥ 0 ;负根的全部坐标则非正
不同简单根满足 ( α i , α j ) ≤ 0
s α i 把 α i 变成 − α i ,并置换其余所有正根
因此“简单”不是任选几根线性无关的根,而是相对于式(3)给出的唯一不可分正根集合。正负划分、简单基都依赖 h ;同一个根系可以有多组这样的基。
直觉
一面镜子只需要一个法向方向;把法向乘以非零数并不会改变反射。但根系还要保留每个法向的长度,使反射另一个根时减去的系数恰为整数。因此它同时记录镜面几何和整数结构,单纯列出反射超平面会丢掉部分信息。
选 h 相当于给每一对相反方向选择朝向。简单根是在这个朝向下不能继续拆分的根。一般有限向量集的这种不可分部分未必线性无关;根系的反射与整性限制迫使不同简单根夹角不锐,进而让它们真正成为基。
有了简单坐标,根的符号判断不需要比较一个很小的浮点内积:每个根的坐标都同号,只要查看整数坐标即可。这个结构也使反射计算、秩二Cartan分类 理路 秩二 Cartan 矩阵与根系分类 Rank-two Cartan classification · 秩二结晶根系分类 从两个简单根的整数配对完整恢复四种有限秩二模型,给精确反射矩阵、根表和群阶,并用正定边界拒绝无限模型。 和简单反射最短词 理路 Weyl 群的简单反射词长 Weyl group simple length · Weyl群根逆序数 · 简单反射约化词 用简单反射的逐根交换机制证明词长等于转负正根数,输出最短词及最长元,并把一般点归约到唯一正室代表。 拥有共同的精确输入。
例子与边界
A 2 的六根与两种简单基
在 R 3 的平面 E = { x 1 + x 2 + x 3 = 0 } 中,取
(4) Φ = { e i − e j : 1 ≤ i ≠ j ≤ 3 } . 每根长度平方为二;s e i − e j 恰交换第 i , j 个坐标,因此它置换这六根。两根的式(2)配对是普通内积,只可能为 0 , ± 1 , ± 2 ,故整性成立。每条根直线上只有一对相反根,它们也张成二维平面,四项公理全部成立。
取 h = ( 2 , 0 , − 2 ) 。正根为 e 1 − e 2 , e 2 − e 3 , e 1 − e 3 ,第三根是前两根之和,所以简单根为
α 1 = e 1 − e 2 , α 2 = e 2 − e 3 . 它们的Gram矩阵是 ( 2 − 1 − 1 2 ) 。在简单基中的六根是 ± ( 1 , 0 ) , ± ( 0 , 1 ) , ± ( 1 , 1 ) ,反射矩阵为
(5) [ s 1 ] Δ = ( − 1 1 0 1 ) , [ s 2 ] Δ = ( 1 0 1 − 1 ) . 它们对标准坐标内积未必正交,但满足 S i T G S i = G ;改变到非正交简单基后,必须同时携带Gram矩阵。
若改用 h ′ = ( 0 , 2 , − 2 ) ,正根变成 e 2 − e 1 , e 1 − e 3 , e 2 − e 3 ,简单基也变成前两根。根集合本身没有变化。若取 h ″ = ( 1 , 1 , − 2 ) ,则 ( h ″ , e 1 − e 2 ) = 0 ,无法给这一对根指定正负,式(3)的输入条件失效。
四项条件各自排除什么
集合 { ± e 1 , ± ( e 1 + e 2 ) } 有限、张成、约化,所有式(2)配对也都是整数,但 s e 1 ( e 1 + e 2 ) = − e 1 + e 2 不在其中,所以不是根系。只检验简单候选间的角度,不能代替整个集合的反射稳定。
一维集合 { ± e , ± 2 e } 反射稳定且配对为整数,却不约化。取 e 为简单正根,其反射同时把 e 和 2 e 变负;所以“简单反射只翻转一个正根”在这里失败。这也会破坏把正根逆序数当成简单词长的公式。
平面单位圆上的十个向量 ( cos ( k π / 5 ) , sin ( k π / 5 ) ) ,0 ≤ k < 10 ,给出有限约化、反射稳定配置;但相邻向量的配对为
2 cos ( π / 5 ) = 1 + 5 2 ∉ Z . 它是非结晶的 I 2 ( 5 ) 模型,不属于本文合同。有限反射群并不自动满足整数根配对。
同样的镜面仍可保留不同根长
在 R 3 中,B 3 取根 ± e i 与 ± e i ± e j ;C 3 则把前一类换成 ± 2 e i ,仍保留后一类。两者都有十八根,反射超平面和反射矩阵完全相同,但 B 3 有十二个长根、六个短根,C 3 则有六个长根、十二个短根。
取余根会将 B 3 的短根变成 ± 2 e i ,将长度平方二的根保持不变,正好得到 C 3 。所以两者互为对偶,而相同反射群不足以恢复原根的长度数据。终点会同时核两份根集合、简单基和Cartan矩阵。
推论与应用
先用两个整数约束一对根
取线性无关的根 α , β ,令 m = a α β 、n = a β α 。由Cauchy–Schwarz不等式 理路 Cauchy–Schwarz 不等式 Cauchy–Schwarz inequality · 柯西–施瓦茨不等式 内积的绝对值不超过两向量范数之积,且等号精确刻画线性相关。 的严格情形,
(6) m n = 4 ( α , β ) 2 ( α , α ) ( β , β ) = 4 cos 2 θ < 4. m , n 为同号整数,故乘积只可能是 0 , 1 , 2 , 3 。特别地,如果 ( α , β ) > 0 ,则 m , n 都为正,至少有一个等于一。若 m = 1 ,反射给 s α ( β ) = β − α ∈ Φ ;若 n = 1 ,则 s β ( α ) = α − β ∈ Φ 。结合根成正负对,两种情况都说明差 α − β 是根。
这条差根结论只使用二维内积、整性和反射公理,不预先使用秩二分类,因此后面的简单基证明没有循环依赖。
从不可分正根得到一组基
每个正根都是简单根之和。若 β 不简单,就拆成 γ + δ ,其中两者为正根,且
0 < ( h , γ ) , ( h , δ ) < ( h , β ) . 不断拆分必终止,因为 ( h , α ) 在有限根集合上只取有限多个值。由归纳,每根得到一组非负整数系数;因此简单根张成全部根,也张成 E 。
两个不同简单根的内积不能为正。否则前一节给 α − β ∈ Φ :若它为正,α = β + ( α − β ) 可拆;若它为负,β = α + ( β − α ) 可拆,两种情况都矛盾。这里不同正根若共线,约化性迫使它们相同,所以应用式(6)时确实线性无关。
最后证明线性无关 理路 线性无关 Linear independence 只有全零系数能产生零向量的向量组。 。若存在非平凡关系,按系数正负分组,可写成
z = ∑ i ∈ I c i α i = ∑ j ∈ J d j α j , I ∩ J = ∅ , c i , d j > 0. 只在一侧出现的关系不可能成立,因为与 h 配对为严格正数;所以两侧都非空,且 ( h , z ) > 0 ,从而 z ≠ 0 。但两组指标不交、跨组内积非正,给
0 < ( z , z ) = ∑ i ∈ I , j ∈ J c i d j ( α i , α j ) ≤ 0 , 矛盾。故简单根确为一组基。坐标唯一性随之成立;负根取正根的相反数,得到全部坐标非正。
一个简单反射只翻转一个正根
设 β = ∑ j c j α j ∈ Φ + 且 β ≠ α i 。约化性保证至少有一个 j ≠ i 满足 c j > 0 ,否则 β 会是 α i 的另一正标量倍。反射
s i β = β − a α i β α i 只改变第 i 个简单坐标;刚才那个正的第 j 坐标保持不变。输出仍是根,而每个根的坐标同号,所以它不可能是负根,必为正根。反射是自身的逆,故它实际上置换 Φ + ∖ { α i } ,只把 α i 变负。
由简单根恢复全部根
若正根 β = ∑ i c i α i 不是简单根,则
( β , β ) = ∑ i c i ( β , α i ) > 0 保证至少有一个 i 满足 ( β , α i ) > 0 。此时 a α i β 是正整数,且 s i β 仍为正根;它与 h 的配对严格降低。重复便在有限步后到达某个简单根。倒转这些反射,即可从简单根恢复原来的 β 。负根再加一次简单根本身的变号反射也能恢复。
因此从 Δ 出发,反复施加全部简单反射直到不再增加向量,就会得到整个 Φ 。终止依据是已经给定的有限根系合同;任意整数反射矩阵不保证这个闭包过程停机,秩二边界 理路 秩二 Cartan 矩阵与根系分类 Rank-two Cartan classification · 秩二结晶根系分类 从两个简单根的整数配对完整恢复四种有限秩二模型,给精确反射矩阵、根表和群阶,并用正定边界拒绝无限模型。 会给一个明确的无限例子。
精确数据怎样检查
若根向量和Gram矩阵以有理数给出,可以依次检查非零性、张成维数、共线约化性、所有配对的整性,以及每个反射后的向量是否仍在输入集合中。随后检查 h 避开全部超平面,逐对正根测试和是否为另一正根,即可识别不可分根,再解线性方程核所有简单坐标。
将有理向量约成统一表示并用字典存放,全部根对的反射与成员检验需要 O ( N 2 r ) 次坐标域运算,其中 N = | Φ | ;这里假设内积矩阵为单位阵或已预计算全部内积,另计该预计算和精确整数位成本。这是一份检查已给有限配置的证书,不是对任意生成向量必停的有限根系识别器。
参考资料