编辑推荐:
研究人员研究Cayley图(Cayley graph)的邻接矩阵(adjacency matrix)何时可分解为同一群上两个Cayley图邻接矩阵的乘积。令G为有限群,U?G?{e}为对称集;记A(G;U)为Cay(G;U)的邻接矩阵。研究证明:对于对称子集S
研究人员研究Cayley图(Cayley graph)的邻接矩阵(adjacency matrix)何时可分解为同一群上两个Cayley图邻接矩阵的乘积。令G为有限群,U?G?{e}为对称集;记A(G;U)为Cay(G;U)的邻接矩阵。研究证明:对于对称子集S,T,U?G?{e},A(G;U)=A(G;S)A(G;T)当且仅当U=ST,且每个u∈U具有唯一表示u=st(s∈S,t∈T)。等价地,在群代数(group algebra)中有(∑s∈Ss)(∑t∈Tt)=∑u∈Uu。研究人员还用群卷积(group convolution)表述该问题:唯一乘积条件等价于S?1S∩TT?1={e}。对于循环群(cyclic group),研究人员借助掩码多项式(mask polynomial)重新表述可分解性,并对乘积形式子集给出中国剩余定理(Chinese Remainder Theorem, CRT)约化。最后,研究人员分析二面体群(dihedral group)D2n,给出非穷尽的因子分解三元组族,并通过Pêcher映射将D2n的强对称因子分解与Z2n的对称因子分解联系起来。
本文研究Cayley图(Cayley graph,以群元素为顶点、由连接集决定邻接关系的图)邻接矩阵(adjacency matrix)的矩阵乘积分解。图论中已有关于笛卡尔(Cartesian)、张量(tensor)等图乘积及一般矩阵乘积图的研究,但一般简单图的矩阵乘积即使得到Cayley图,其因子也未必是同一群上的Cayley图;因此需要把因子限制为同一有限群G上的Cayley图。核心问题是:对有限群G及对称连接集U?G?{e},A(G;U)=A(G;S)A(G;T)何时成立。该限制使问题具有刚性的群代数(group algebra)结构,并与近因子分解(near-factorization,即G?{e}可由S与T唯一乘积覆盖且e不在乘积中)、群卷积(group convolution)、循环群掩码多项式(mask polynomial)及二面体群(dihedral group)结构相联系。
研究人员证明,对对称S,T,U?G?{e},A(G;U)=A(G;S)A(G;T)当且仅当U=ST且每个u∈U有唯一表示u=st(s∈S,t∈T),等价于群代数中(∑
s∈Ss)(∑
t∈Tt)=∑
u∈Uu;群卷积形式等价于S
?1S∩TT
?1={e}。研究还给出一般群中不可分解与可分解连接集的构造,对循环群用掩码多项式和中国剩余定理(Chinese Remainder Theorem, CRT)约化,对二面体群D
2n给出因子分解族并通过Pêcher映射联系Z
2n的对称分解。意义在于把图的矩阵乘积分解转化为群代数唯一乘积与Sidon型条件,连接近因子分解、循环图与二面体群组合结构。
关键技术方法(≤250字):研究主要采用图论与群代数/表示论方法:用右正则表示(right-regular representation,由右乘置换矩阵给出的表示)及矩阵R(g)线性无关,将邻接矩阵乘积等式转化为群代数系数与唯一表示条件;用群卷积计数N
S,T(u)刻画乘积重数,并用S
?1S∩TT
?1={e}表述Sidon对(Sidon pair,任意乘积st具有唯一表示的二集对);对循环群采用掩码多项式模X
n?1与中国剩余定理约化;对二面体群采用旋转/反射分解及Pêcher映射;另用直积坐标计数和反证构造无分解例子。原文未涉及样本队列。
研究结果:2. 一般有限群的Cayley因子分解:通过右正则表示证明等价定理,并推出U=G?{e}时等价于近因子分解;对共轭类并集给出特征标条件;证明存在无分解的对称U,且阶至少4的有限群存在可分解的对称U。3. 有限群中的卷积与Sidon对:证明A(G;S)A(G;T)的元素由1
S?1
T给出,因子分解当且仅当1
U=1
S?1
T;Sidon对等价于S
?1S∩TT
?1={e},并给出d
?(G)≤?√n?及直积下界。4. 循环群的Cayley因子分解:用掩码多项式F
U(X)≡F
S(X)F
T(X) mod X
n?1刻画,给出CRT约化(乘积形式子集)及若干非穷尽构造。5. 二面体群的Cayley因子分解:按旋转R与反射M分解U
R、U
M的乘积来源;给出非穷尽可分解三元组族及连通性判据;证明Pêcher映射在对称子集与强对称子集间双射并保持可分解性,恢复强对称近因子分解情形。6. 直积与非乘积型例子:证明乘积形式直积的坐标化判定;并用C
15例子说明可分解三元组不必来自CRT分量乘积形式。7. 进一步研究:提出关联方案(association scheme)内分解、ε-因子分解(ε-factorization)、超图(hypergraph)邻接矩阵λ(J?I)分解、Sidon对阈值及无限群Cayley图等开放问题。
讨论与结论翻译:讨论部分未另设结论段,其研究方向指向关联方案中的关系矩阵分解、容错ε-因子分解、k-均匀超图的λ(J?I)分解、唯一乘积子集大小阈值以及无限群情形。研究结论可翻译为:同一群上Cayley图邻接矩阵的乘积分解由唯一乘积条件完全刻画;群卷积表述等价于S
?1S∩TT
?1={e};循环群可用掩码多项式及CRT约化;D
2n的强对称因子分解经Pêcher映射与Z
2n的对称因子分解对应。该结论为Cayley图矩阵分解、近因子分解和群组合结构之间建立了统一框架。