可交换图的一些注记.pdf

浙江大学学报（理学版）Journal of Zhejiang University（Science Edition）http：/ 51 卷第 2 期2024 年 3月Vol.51 No.2Mar.2024 可交换图的一些注记吴寒1，2，刘奋进1*，尚凡琦1，3，周艳红1，阮昊桐1（1.长安大学 理学院，陕西 西安 710064；2.南京大学 数学系，江苏 南京 210093；3.哈尔滨工程大学 青岛创新发展基地，山东 青岛 266000）摘要：如果存在一种顶点标号，使得 2 个简单图的邻接矩阵可交换，则称 2 个简单图可交换。首先，从图的Perron 向量、主特征值数量、正则性三方面给出了可交换图的必要条件。然后，借助矩阵的克罗内克积、图的笛卡尔积及循环矩阵，构造了新的可交换图。最后，将一个邻接矩阵表示为另一个特征值互异的邻接矩阵的矩阵多项式，给出了 2 种算法，并比较了二者的优劣。可交换图存在公共的特征向量，对图谱理论研究具有重要意义。关键词：可交换图；正则图；循环图；克罗内克积；笛卡尔积中图分类号：O 157.5 文献标志码：A 文章编号：10089497（2024）0217206WU Han1,2,LIU Fenjin1,SHANG Fanqi1,3,ZHOU Yanhong1,RUAN Haotong1（1.School of Science，Changan University，Xian 710064，China；2.Department of Mathematics，Nanjing University，Nanjing 210093，China；3.Qingdao Innovation and Development Base of Harbin Engineering University，Qingdao 266000，Shandong Province，China）A note on commutative graphs.Journal of Zhejiang University(Science Edition),2024,51(2):172177Abstract:Two simple graphs are commutative if there exists a labelling of their vertices such that their adjacency matrices can commute.This paper gives three necessary conditions ensuring the commutativity of certain graphs from Perron vectors,the number of main eigenvalues,the regularity of graphs.Then we construct new commutative graphs by graph Kronecker product,Cartesian product and circulant matrix.Finally,for two commutative graphs,we provide two algorithms that can express one adjacency matrix as the matrix polynomial of another adjacency matrix with distinct eigenvalues,and compare their merits.Commutative graphs sharing common eigenvectors are essential to the study of spectral graph theory.Key Words:commutative graph;regular graph;circulant graph;Kronecker product;Cartesian product设G=(V，E)为n阶 简 单 图，V=v1，v2，vn为其顶点集，A(G)=aij为其邻接矩阵，如果vivj E，则aij=1，否则aij=0。将G的特征值与特征向量分别定义为A(G)的特征值与特征向量。如果 G 的特征子空间V=x|Ax=x 与全 1向量j=(1，1，1)T不正交，即至少存在 1个特征向量x V，使得xTj 0，则称G的特征值为主特征值1。G的谱Spec(G)定义为A(G)的特征值的多重集。如果Spec(G)=Spec(H)，则称图G与图H同谱。关于同谱图的构造及其性质，已有大量研究成果2-4。那么，具有相同特征向量的图有哪些？HORN等1给出了方阵可交换的充要条件：2个可对角化的方阵可交换当且仅当它们存在一组公共的特征向DOI：10.3785/j.issn.1008-9497.2024.02.005收稿日期：20220509；修回日期：20230630；接受日期：20230710；出版日期：20240325.基金项目：陕西省自然科学基础研究计划项目（2021JM-149）；长安大学 2020年大学生创新创业训练计划项目（S202010710247）.作者简介：吴寒（2000），ORCID：https：/orcid.org/0000-0002-4668-970X，女，本科生，主要从事图论及计算数学研究.*通信作者，ORCID：https：/orcid.org/0000-0001-8759-7695，E-mail：.吴寒，等：可交换图的一些注记第 2期量。由于图的邻接矩阵为实对称矩阵，所以 2 个公共特征向量的图其邻接矩阵可交换。如果存在一个置 换 矩 阵P，使 得A(G)PTA(H)P=PTA(H)P A(G)，则称图G与图H可交换。有关可交换图的研究成果不多。HEINZE5提出了可交换图的定义，并给出了可交换图的简单性质。BEEZER6通过研究n个顶点的路Pn的邻接矩阵A(Pn)的矩阵多项式的(0，1)位置特征，确定了所有与Pn可交换的图。AKBARI 等7找到了所有可使完全二部图Kn，n分解为可交换的完美匹配或哈密顿圈的整数n。COLLINS 等8研究了具有相同主特征向量的图的道矩阵（walk matrix）之间的关系。本文研究简单图邻接矩阵的可交换性，首先，从图的 Perron 向量、主特征值数量、正则性三方面给出可交换图的必要条件。然后，枚举所有具有 6 个点且主特征值数量不超过 2 的可交换图，并利用阶数较小的可交换图，通过矩阵的克罗内克积与图的笛卡尔积，构造新的阶数较大的可交换图，证明所有n阶循环图是可交换的。最后，将一个邻接矩阵表示为另一个特征值互异的邻接矩阵的矩阵多项式，给出了 2种算法，并比较其优劣。下文将要用到的定义和符号。设G=(V，E)是一个简单图，其补图为G=(V，E)，其中v1v2 E当且仅 当v1v2 E。给 定 2 个 图G1=(V1，E1)与G2=(V2，E2)，则G1与G2的笛卡尔积记为G=G1G2，其顶 点 集 为V(G)=(u，v)|u V1，v V2，顶 点(u1，v1)和(u2，v2)相连当且仅当u1=u2，v1v2 E2或u1u2 E1，v1=v2。设A是一个m n矩阵，B是一个p q矩阵，则矩阵A与B的克罗内克积A B为mp nq的分块矩阵，表示为A B=a11Ba1nBam1BamnB。I，J分别表示n阶单位矩阵与全1矩阵，j为n维全1向量。其他图论概念和符号可参见文献 9-11。1预备知识引理 11 设A，B是 2 个可对角化的n阶方阵，则以下命题等价：（1）AB=BA；（2）A，B可同时对角化；（3）A，B存在一组公共特征向量。引理 25 若是图G的q重主特征值，则的特征子空间存在一组标准正交基，使得其中只有一个特征向量与j不正交，其余q-1个特征向量均与j正交。引理 3（Perron-Frobenius定理）1 设A是n阶非负不可约方阵（n 2），(A)为其谱半径，则（1）(A)0；（2）(A)是A的最大特征值且代数重数为1；（3）存 在 唯 一 的 正 向 量x=xi，使 得Ax=(A)x且x1+x2+xn=1，则 称x为A的Perron向量。引理 410 设A，B分别为m阶图G与n阶图H的邻接矩阵（m可以与n相等），则G与H的笛卡尔积的邻接矩阵为A(GH)=Im B+A In。引理 51，12 设A是n阶方阵且有n个不同的特征值，若AB=BA，则存在唯一次数小于n的多项式f(x)=i=0n-1aixi，使得B=f(A)。引理 613 图G恰有 1 个主特征值当且仅当G是正则图。2可交换图的必要条件定理 1 设G与H是可交换图，则（1）若G与H连通，则(A(G)的 Perron 向量与(A(H)的相同；（2）若G和H的主特征值都是单根，则它们的主特征值数量相同。证明（1）不妨设 A(G)A(H)=A(H)A(G)，由引理 1（3），知A(G)与A(H)存在一组公共特征向量x1，x2，xn，使得ni=1span(xi)=Rn。因为G与H连通，A(G)和A(H)是非负不可约方阵，由Perron-Frobenius 定理，可知A(G)和A(H)的谱半径(G)和(H)都是单根且对应的特征向量均为正向量，不妨设x1，x2，xn中的唯一正特征向量为x1，因此可以调整x1的模长使其为(G)与(H)的Perron向量。（2）反证法，不妨设G与H的主特征值、不同特征值数量分别为r1，r2；S1，S2且r1 r2。记Vi=|A(G)=i，Vi=|A(H)=i 为特征值i(i)的特征子空间。因为Rn=V1Vr1Vs1，（1）结合引理 2，可知x1，x2，xn中恰有r1个特征向量173浙 江 大 学 学 报（理学版）第 51 卷与j不正交。又因为Rn=V1Vr2Vs2，（2）所以x1，x2，xn中恰有r2个特征向量与j不正交，矛盾。注1 定理1中“图G和H的主特征值都是单根”条件不可去除，否则存在反例，如图 1所示，其中可交换图K2，4和3K2的主特征值数量分别为 2和 1。定理 2 设图G的补图为G，则A(G)A(G)=A(G)A(G)当且仅当G为正则图。证明 因为A(G)=J-I-A(G)，设G的度序列为A(G)j=d1，d2，dnT，又A(G)J-I-A(G)=A(G)J-A(G)I-A(G)2，J-I-A(G)A(G)=JA(G)-IA(G)-A(G)2，所以A(G)J=JA(G)，即 d1d1d1d2d2d2dndndn=d1d2dnd1d2dnd1d2dn。因此d1=d2=dn，即G为正则图。反之，若G为k正则图，则A(G)J=kkkk=JA(G)，于是A(G)J-I-A(G)=J-I-A(G)A(G)。注 2 在定理 2中，若只要求图G与其补图G可交换，则G不一定是正则图，如图 2所示。定理 3 图G1与正则图G2可交换当且仅当G1与G2可交换。证明 必要性。不妨设A(G1)A(G2)=A(G2)A(G1)，则A(G1)A(G2)=J-I-A(G1)A(G2)=JA(G2)-A(G2)-A(G1)A(G2)=A(G2)J-A(G2)-A(G2)A(G1)=A(G2)J-I-A(G1)=A(G2)A(G1)。充分性。用G1替换G1即可证得。推论 1 完全图Kn与任意n阶正则图可交换。证明 在定理 3 中，令G1=nK1，因为A(nK1)=On n与任意邻接矩阵可交换，所以图G1与任意正则图G2的邻接矩阵可交换。由定理 3，知G2与G1=Kn可交换。经编程计算，枚举了所有主特征值数量小于 3的连通图及与其可交换的连通图，如图 3 所示。其中，G1G5为主特征值数量为 1的六阶连通图，且均为循环图。图 1主特征值数量不同的可交换图Fig.1Commutative graphs with different number of main eigenvalues图 2非正则可交换图G与GFig.2Non-regular commutative graphs G and G图 3主特征值数量小于 3的六阶连通图Fig.3Connected graphs with 6 vertices and the number of main eigenvalues less than 3174吴寒，等：可交换图的一些注记第 2期表 1列出了主特征值数量为 2的 18个六阶连通图及与其对应的可交换连通图。3可交换图的构造通过矩阵的克罗内克积、图的笛卡尔积及循环矩阵，构造可交换图。3.1矩阵的克罗内克积定理 4 设A，C均为m阶方阵，B，D均为n阶方阵。若AC=CA，BD=DB，则(A B)(C D)=(C D)(A B)。证明(A B)(C D)的(i，j)元素为()a11Ba1mBam1BammBc11Dc1mDcm1DcmmDij=k=1maikckjBD=(AC)ij(BD)，(C D)(A B)的(i，j)元素为()c11Dc1mDcm1DcmmDa11Ba1mBam1BammBij=k=1mcikakjDB=(CA)ij(DB)。因为AC=CA，BD=DB，(AC)ijBD=(CA)ijDB，所以 (A B)(C D)=(C D)(A B)。将定理 4应用于(0，1)方阵，构造可交换图。推论 2 设A1，A2为 2 个m阶图的邻接矩阵，B1，B2为 2个n阶(0，1)方阵（主对角线元素可为 1）。若A1A2=A2A1，B1B2=B2B1，则A1 B1，A2 B2所对应的图可交换。3.2图的笛卡尔积定理 5 设A，C均为m阶图1，2的邻接矩阵，B，D均为n阶图3，4的邻接矩阵。若AC=CA，BD=DB，则图13与图24可交换。证明 根据引理 4，可得(AB)(CD)=(Im B+A In)(Im D+C In)=(Im B)(Im D)+(Im B)(C In)+(A In)(Im D)+(A In)(C In)=(Im BD)+(C B)+(A D)+(AC In)=(Im DB)+(A D)+(C B)+(CA In)=(Im D)(Im B)+(Im D)(A In)+(C In)(Im B)+(C In)(A In)=(Im D+C In)(Im B+A In)=(CD)(AB)。3.3循环矩阵循环矩阵是一种特殊的方阵，将上一行各元素依次右移一个位置得到下一行元素，上一行最后一个元素为下一行第一个元素。定理 6 任意 2个n阶循环矩阵可交换。证明 不妨设A=a1a2anana1an-1a2a3a1，B=b1b2bnbnb1bn-1b2b3b1。令P为循环矩阵，则表 1主特征值数量为 2的六阶连通图及与其对应的可交换连通图Table 1Connected graphs with six vertices two main eigenvalues and their commutative graphs图的序号G6G7G8G9G10G11G12G13G14G15G16G17G18G19G20G21G22G23可交换图的序号G6G7，G13G8G9，G17，G19，G20G10，G16G11G12G7，G13G14G15G10，G16G9，G17，G19，G20G18G9，G17，G19G9，G17，G20G21G22G23175浙 江 大 学 学 报（理学版）第 51 卷P=0100000100000000000110000：=en，e1，e2，en-2，en-1，其中，ei表示第i个分量为 1，其余分量均为 0 的n维列向量。由矩阵分块乘法，可得Pi=en-i+1，en-i+2，en-i+3，en-i-1，en-i，其中，Pi的列向量下标模n取余，于是A=a1P0+a2P+anPn-1，B=b1P0+b2P+bnPn-1。因为A，B均为P的矩阵多项式，故AB=BA。若一个图的邻接矩阵为循环矩阵，则称该图为循环图，从而有推论 3 任意同阶循环图的邻接矩阵可交换。4可交换图的矩阵多项式设A1是n阶图G1的邻接矩阵，A1有n个不同的特征值，由引理 5，任何一个与A1可交换的图G2的邻接矩阵A2均能表示为A1的次数小于n的多项式f(x)=i=0n-1cixi的矩阵多项式，即A2=i=1nciA1i。下面给出矩阵多项式f(x)的 2 种求解法，并比较其优劣。4.1线性方程组法输入 n阶图G1，G2的邻接矩阵A1，A2。Step 1 约 定A01=In，依 次 求A1的 各 次 幂Ak1(k=0，1，n-1)。Step 2 构造线性方程组Ax=B的系数矩阵A，则第k+1列为Ak1(k=0，1，n-1)按列压平而成的n2维列向量。Step 3 令B为A2按 列 压 平 而 成 的n2维 列向量。Step 4 对Ax=B两边左乘A的左逆A-1left，求解超定线性方程组的解x=A-1leftB。输出 x=(c0，c1，cn-1)T。4.2拉格朗日插值法输入 n阶图G1，G2的邻接矩阵A1，A2。Step 1 求A1，A2的谱：Spec(A1)=1 2 n，Spec(A2)=m11，m22，mss，其中，上标mi表示A2的特征值i(1 i s)的重数且满足i=1smi=n。计算矩阵V1，其中V1的列向量为A1的全部标准正交特征向量。Step 2 计算A2V1=A2x1，A2x2，A2xn=i1x1，i2x2，inxn=x1，x2，xn i1i2in。Step 3 计算iV1(1 i s)，并与A2V1比较，找出所有相同的列，将其在A2V1中的列标号记为j1，j2，jk，即j1，j2，jk与i对 应，其 中 j1，j2，jk Spec(A1)。Step 4 对得到的n组对应特征值(i，j)(1 i n，1 j s)，采用拉格朗日插值法，得到多项式f(x)。输出 f(x)=c0+c1x+cn-1xn-1。4.3算例设A为图1的邻接矩阵，B为路P10的邻接矩阵，如图 4所示。容易验证AB=BA，A的谱为Spec(A)=(3.513 0，1.204 0，0.763 5，0.594 4，0.521 1)，特征值互不相同，从而矩阵B可表示为A的多项式f(A)。分别采用线性方程组法和拉格朗日插值法，图 4一对可互相表示为其邻接矩阵的矩阵多项式的可交换图Fig.4A pair of commutative graphs that can be expressed as matrix polynomial of their adjacency matrices176吴寒，等：可交换图的一些注记第 2期可得f(x)=-48x+267x3-431x5+206x7-14x9，2种方法所用时间分别为 0.005 7 s和 0.111 2 s。4.42种方法的对比理论上，采用线性方程组法可获得精确解，且与矩阵规模n无关，但在实际计算中，由于受舍入误差、机器误差的影响，当图的顶点较多时，在计算矩阵伪逆时可能会产生较大的误差，因此对算例的选取有一定要求，本文算例使用了 50 个顶点的路的图，可得到准确结果。拉格朗日插值法是一种数值近似方法，在计算无理特征值时会产生一定舍入误差。当算例较简单，即顶点较少（小于等于 10 个）时，可得到准确的插值多项式，但当顶点数超过 10 时，会产生较大误差，无法得到准确的数值解。在计算时间上，如只计算矩阵的伪逆与拉格朗日插值多项式，当顶点较多时，拉格朗日插值法更快，但在实际计算过程中，拉格朗日插值法需先通过2 个循环得到一一对应的特征值，再进行拉格朗日插值求解，而线性方程组法只需计算矩阵乘法与伪逆，所以线性方程组法更快。参考文献（References）：1HORN R A，JOHNSON C R.Matrix Analysis M.2nd ed.Cambridge/New York：Cambridge University Press，2012.2GODSIL C D，MCKAY B D.Constructing cospectral graphsJ.Aequationes Mathematicae，1982，25（1）：257-268.DOI：10.1007/BF021896213LIU F J，WANG W，YU T，et al.Generalized cospectral graphs with and without Hamiltonian cycles J.Linear Algebra and Its Applications，2020，585：199-208.DOI：10.1016/j.laa.2019.10.0014JI Y Z，GONG S C，WANG W.Constructing cospectral bipartite graphsJ.Discrete Mathematics，2020，343（10）：112020.DOI：10.1016/j.disc.2020.1120205HEINZE A.Applications of Schur Rings in Algebraic Combinatorics：Graphs，Partial Difference Sets and Cyclotomic Schemes D.Oldenburg：Universitt Oldenburg，2001.6BEEZER R A.On the polynomial of a pathJ.Linear Algebra and Its Applications，1984，63：221-225.DOI：10.1016/0024-3795（84）90144-77AKBARI S，MOAZAMI F，MOHAMMADIAN A.Commutativity of the adjacency matrices of graphs J.Discrete Mathematics，2009，309（3）：595-600.DOI：10.1016/j.disc.2008.09.0068COLLINS L，SCIRIHA I.The walks and CDC of graphs with the same main eigenspace J.Discussiones Mathematicae Graph Theory，2023，43（2）：507-532.DOI：10.7151/dmgt.23869GODSIL C，ROYLE G.Algebraic Graph Theory M.New York：Springer，2001.10CVETKOVI D M，ROWLINSON P.An Introduction to the Theory of Graph Spectra：48 M.Cambridge：Cambridge University Press，2010.11高随祥.图论与网络流理论 M.北京：高等教育出版社，2009.GAO S X.Graph Theory and Network Flow Theory M.Beijing：Higher Education Press，2009.12丘维声.高等代数（下册）M.北京：清华大学出版社，2019.QIU W S.Higher Algebra（Vol 2）M.Beijing：Tsinghua University Press，2019.13DRAZIN M P.Some generalizations of matrix commutativity J.Proceedings of the London Mathematical Society，1951，s3-1（1）：222-231.DOI：10.1112/plms/s3-1.1.222177