【doc】正则图邻接矩阵的非奇异性

【doc】正则图邻接矩阵的非奇异性 正则图邻接矩阵的非奇异性 第2卷第3期江南大学(自然科学版) 2003年9月JournalofSouthernYangtzeUniversity(NaturalScienceEdition) VO1.2 SCp. NO.3 2003 文章编号:1671—7147(2003)03—0315—05 正则图邻接矩阵的非奇异性 梁修东 (江南大学理学院,江苏无锡214064) 摘要:证明了当,k中至少有一个为偶数(0<k<),且(,k)?(6,3),(,一2)时,存在邻 接矩阵非奇异的阶k一正则简单图. 关键词:正则图;邻接矩阵;非奇异;循环矩阵 中图分类号:O157文献标识码:A Non-SingularAdjacentMatricesofRegularGraphs LIANGXiu—dong (TheScienceSchool,SouthernYangtzeUniversity,Wuxi214064,China) Abstract:Itisprovedinthispaperthatthereexistsa志一 regularsimplegraphwithorderandanon— singularadjacencymatrix,wherekisevenand0<k<r/exceptfor(,k)=(6,3),(,一2). Keywords:regulargraphs;adjacencymatrices;non—singular;circulantmatrix 1预备知识 设G为阶简单图,则G为k一正则图当且仅 当它的邻接矩阵为二元阶主对角线为0的对称方 阵,其行和与列和均为常数k.用A(,k)表示所 有这样的二元矩阵的集合,用A(,k)I1表示其中 所有可逆矩阵的集合,这里1?k?一1.类似地, 用B(,k)表示所有行和与列和都为k的阶0— 1矩阵的集合,B(,k)I1表示其中所有可逆矩阵 的集合.则A(,k)cB(,k),A(,k)I1c B(,k)_..由文献[1]得出,除B(4,2)外,B(, k)I1?.本文旨在构造邻接矩阵非奇异的正则 图.得到除A(6,3),A(,一2)外,均有A(, k)I1?.约定k,至少有一个是偶数,且1?k? 一 1. 首先考虑循环矩阵c C= 为方便起见,用Circ(a0,a1,a2,…,a一1)表示首行 数字为(a0,a1,a2,…,a一1)的循环矩阵,称= a0+a1z+a2z+…+an-Iz一为它的特征.由文 1 献[2]得,C的特征值为f(e),其中,=exp()= cos+isinZ_g ,l=0,1,2,…,一1,且循环矩阵 A,B的和,差,积,逆矩阵(如果逆矩阵存在)都是 循环矩阵,且特征值分别是:^(e)+(ef), ^(,)一(,),^(,)(,)和^-t(,f)'l=0, 1,2,…,一1.不难验证:若=(a1,a2,…,a)为 对称向量,即口=口一川,i=1,2,…,[{}],则 收稿日期:2002—11—13;修订日期:2003—02—25. 作者简介:梁修东(1962一),男,湖北十堰人,理学硕士.副教授 316江南大学(自然科学版)第2卷 Circ(O,口)为主对角线为0的对称矩阵.以下用 l,表示m×全1矩阵,用l,表示阶全1方阵, A表示阶完全图的邻接矩阵. 引理1设是次单位根且?1,若(走,)=1, 则?1(详见文献[3]). 引理2设=pls-p2s:…Pro"m,P为互不相同的素 数,为次单位根,若户-?1,则对任意整数 s?0,有-.?1. 证设e=exp(),=ez,若Iq?1,则 不能整除pls-ql,也不能整除pls,,有户-. ?1.证毕. 麦 引理3阶循环矩阵C=Circ(0,0,…,0,1,…,1, 0,…,0)可逆的充要条件是(走,)=1(详见文献 [3]). 引理4对任意A?B(,走),1?惫?一1,则A 与l,一A具有相同的秩[引. 由(2)式得A2x1=x2 代入(1)式得(A1+A2A2)x1=O,而 22==, 【::::])-3,+1为9t+3阶循环矩阵,其特征为fA, A,, =t(1+z+ … +(z)),V9t+3次单位根.若=1, ,AA,()=t(3t+1)>5t,若?1,则 fA2a'2(t=t=0 因为A1+A2A2为循环矩阵,且0?,A. ()?5t, 故A1+A2A2非奇异,可得x1=O,由(2)式x2= O,故x=O,即A非奇异.证毕. 引理7当整数m?1时,必有一个系数P,满足m <P?2m[. 引理5若A1,A4可逆,且AA3AA2无特征值2主要结论 1删fA11可逆. 证 (AA3=::)一[A]一【0JA三三;.A],\A4/【A3A4JlA4一A3AA2J IJIIA4-A3A1A2I= IA4IIJ—AA3AA2I?0.证毕. 引理6,?2为正整数,走=6i,:12t+3,A1? A(9t+3?st),A4Ak3, A= 【::::;]}3t+?,其中J=【三;],贝 A= (二,12三:)?Ac,走,若A-为非奇异的循 环矩阵,则A非奇异. 证显然A?A(,走).令AX=0,其中x= (x1,x2),x1为9t+3维列向量,x2为3t维列向 量,用?x.表示?z,?x表示?z,则 fA1x1+A2x2=0(1) IA2X1+A4X2=0(2)( 慧(3t'0?:?…l,?x1+一1)?x2='一'又A4=Ak=l,3t—I3t, 定理1对任意大于1的整数,A(,一1)-1?p. 证因为A^?A(,一1),且A^可逆. 定理2若为正偶数,则A(,一2)=p. 证对任意A?A(,一2),若=2,结论显 然成立.当?4时,由于A为主对角线为0的对称 矩阵,不妨设A的第1行中第个元素为0,则在第 行中,a1=ai=0,其余元素全为1,即第1行与第 行相同,故A奇异.证毕. 定理3A(6,3)-1=p. 证设A?A(6,3),不失一般性,设all=a12= a13=0,由对称性a21=a31=0,若a23=0,则第 1,2行相同,A奇异;设a23=1,则a32=1,不失一 般性,再设a24=0,则a42=0,a25=a26=a52= a62=1,若a35=a36=1,则第5,6列相同,A奇异; 设a34=a35=1,则a36=0,a43=a53=1,a63= 0,a45=a65=口54=a56=0,a46=a64=1,即为 不难验证,此矩阵奇异.证毕. 定理4设k为任意正整数,则除A(4,2),A(6, 3)夕},,A(2k,走)一?p. 第3期梁修东:正则图邻接矩阵的非奇异性317 0111 1011 1100 1100 1100 0011 0010 0001 ?A(8,4),且 非奇异,...A(8,4)-1?. 当k?5时,考虑矩阵Ao=Cire(0,1,0,1,0,…,1, 0,1),其特征为,A=x+x.+…+x"_.,当x? ?1时,,A=x(1+x+…+x"一)=x(1+x+ … H= (})_籍 V??1,且"=1,有,A()=0. 1)若k为素数,取A=Cire(0,0,1,1,0,1, … 0,1,0,1,1,0),其特征为 ,'^x2+x3+x5+…+n一+n一0+n一 由于7l=2k?10,x=?1不是,A的根,若有某个 re+1,且"=1,使fa()=0,贝0 ,A()一fa()=—+"一一"一=0 且口—2=n一2一n一1 由于re+1,故=",,即"一0=1,0=1,(3, k)?1矛盾,故A非奇异; 2)若k=户is-p2s2…户t,其中户1,户2,…,户为 素数,s1,s2,…,?1,不妨设户1>户2>…>, 由引理7存在素数户,满足户1<户?2p1,若户=4q +1,令2+1=户,贝0i=2q,取 A=Cire(0,1,0,1,…,0,1,1,0,0,1,…,0,1, 0,0,1,1,0,…,1,0,1) 其特征为 fa=x+x3+…+x一+x+x+3+…+ xn-i-3+Xn—f+xn-i+l+…+一3+n一1 同理?1不是,A的根,若有某个?1且"=1使 fA()=0,则 ,A()一,A()=一+"一卜一一"一=0 同理可得川=p=1,由此(户,71)?1,矛盾;若 户=4q+3,令2一1=户,贝0i=2q+2,取 A=Cire(0,1,0,1,…,0,1,0,0,1,1,0,…,0, 1,0,1,1,0,0,1,0,…,1,0,1) 同理可得A非奇异.证毕. 定理5对任意正整数k?1,3,A(2k,k+1)一?. 证若k为偶数,则k+1为奇数,(2,k+1)=1, (k,k+1)=1,...(2k,k+1)=1,由引理3知结论 成立;当k为奇数时,分3种情况证明: 1)若(3,志):1,取A:f),其中\A2A1/ A1=Circ(0,1,1,…,1),A2=Cire(0,1,0,…,0, 1),则A?A(2k,k+1),且A1非奇异, AfA2AfA2仍是循环矩阵,其特征为 = , 令12:1(3)( +…+七一)一上j, 由于k?5,且为奇数,I显然不是(3)式的根,假设 有某个?I,=I满足(3)式,'.'++…+ 一 =一 I,...(+一)=I,即+?=?I,若 +?=I,贝0++I=0,即.=一I,与k为 奇数矛盾;若+?=一I,则++I=0,即. =I,由引理I,(k,3)?I,矛盾.由上述知 AA2AfA2无特征根I;由引理5,A非奇异. 2)若(3,k)=3,但(7,k)=I,取 A= (AA1其中A1=Cire(0,志 ——一?? 1,1,1,0,…,0),A2=Cire(0,0,1,…,1,0) 贝0A?A(2k,k+1),由引理3,A1非奇异. AfA2AfA2的特征为 … +k-2 2+3+xz+4 +x2 )2 (4) 显然1不是(4)式的根.假设有某个?1.且= 1,满足(4)式,即 )=1 则(年:?1? (4—1) ? . ..;L是单位'.=,可得3=41?..是单位根,.?.=,可得.= I^一上l =一或一.=,若一.=-4即一=1,可得 =1,矛盾;若一.=,即=1,可得(7,71)? 1,矛盾..'.AfA2AfA2无特征根1,A非奇异; 3)若k=3×7×q,q为奇数,且q?1, 318江南大学(自然科学版)第2卷 取A=(竺:竺:),其中 .,,, Al=Circ(0,0,…,0,1,0,…,0,1,0,…,0), .,,, A4=Circ(0,0,…,0,1,0,…,0,1,0,…,0), A2A3Ak. 则A?A(2k,k+1),由于k为奇数,所以Al,A4 非奇异,且A.A3A.A2仍为循环矩阵,其特征为 令 (^:) lf (?:?:::?!:) (z3q+z量一3q)(z7q+z量一7q) (^) 赢(5) 1显然不是(5)式的根,'.'V?1,=1,有+ +…+.=一 1,.'.^,()^.()=(+ /~k-3q)(7q+Ak-7q)=4cosc0S2丁ln,其中1?z ?足一1,若z=3r,则^, (a)fA.()=4?s? 1;若z=3r+1,则^,()^.()= 4?s?s=一2cos??,故 不是(5)式的根,即A非奇异.证毕. 定理6若k为正偶数,=2k+3,则A(n,足)?. 证若k无因子3,则(2忌+3,k)=1,由引理3知 结论成立;设k=3ql,'.'ql为偶数,=6ql+3= 3q2,.?.q2=2ql+1,则(ql,q2)=1,以下分4种情 况证明: 1)若ql,q2都不含因子3,取 卫上上 A=Circ(0,0,…,0,1,…,1,0,…,0,1,…,1, 土—一 0,…,0,1,…,1,0,…,0), 其特征为厶=..z-qI++…+..,T2q1+1+z+…+ z +. +z4ql+2+…+z5ql+l=(zql+2+ z+x4q,*2)(1+z+...+一.) V次单位根,若=1,显然^()?0;若?1 ^(z):,+2++A41+2)=^(z)=(-+2++)学= +2(1+ jq.jq, 若一2=1,则,^()?0,若2?1,由引理2, ?1,.'.,^() 0..'.A非奇异. = +2()()? 2—1 2)若ql含因子3,则q2不含因子3.设k=3Sq, S>1,q?2且无因子3.若q三l(mod3),令 : A=Circ(0,0,…,0, 3 鬟工 1,…,1,0,0,1,…,1,0,0,…,1,…,1,0,…,0), 其中2t=3(q一2)+4,贝0A?A(2k+3,k),其 特征为,^=(z+xq+2+t+l+…+ z(3s-I)(q+2)++.)(1+z+…+zq一.) 若=1,显然,A()?0,若?1,则 fA(a)=I(1+..?-1)(') 若=1,显然,^()?0,若?1,由引理2, A3:(q'?1,则 ):At+l(睾)料?0^()=(^_)?^一1'' . ' . A非奇异; 若q三2(mod3),令 A=Circ(0, i一夏天 0,…,0,1,…,1,0,1,…,1,0,…,1,…,1,0,…,0), 2t=3(q一1)+3,则A?A(2k+3,k),其特征为 ,^=(z'.+z.'.+…+z(J1)(q.)'.)(1+ z+…+zq一.) 同上可证:对任意次单位根it,,^(it)?0, . ' . A非奇异. 3)若q2含因子3,则ql不含因子3.设= 3'q,s>1,q>1,非负整数t使3s2.<ql< 3'2',则3s2'<2ql,令 '1 ,—---,-_-, A=Circ(0,0,…,0, qll2qll2qll1 ,——— ^———,,———^———,,———^———,,———^———,,———^———,,—— —^—_-, 1,…,1,0,…,0,1,…,10,…,0),1,…,1,0,…,0), 其中2tl=3(q一2'.)一口l一1,t2=3s2'一ql, 其特征为 ,^:zfl.(1+z32'+z32)(1+z+…+zql一.), =1显然不是,^的根,若?1,则 ^()=At~+l(1'+~, 3s2t+I ); 第3期梁修东:正则图邻接矩阵的非奇异性319 若'=1, 则fA(2)?0,232'?1,由引理2, ?1.则 )-+l()?0. . ' . A非奇异. 4)若,l=3,s>1,走=3ql为偶数,设走= 6q,q无因子3.'.',l=2k+3,.'.s为奇数(否则, 若s为偶数,则3一3=3(3.)一1=3[(4—1). 一 1]=3[(4d一1)一1]=3(4d一2)不能被4整 除,矛盾.其中4为(4—1)0二项展开式中的前s 一 1项).又3=2k+3=12q+3,3一.=4q+1, . ' . 3一.+2+5q=9q+3,设s一1=2r,贝03一.= 3=9,其个位或9或1,.'.30+2不是5的倍数, 即9q+3无因子5,.'.(5q,9q+3)=1,取 fAlA2\ AIAJ' —jL 其中Al=Circ(0,0,…'0'1,一,1,0,…,Q), A2= 2 l…I I…l 1} 3q+1,A4= J 则A?A(2k+3,走),由引理3知Al非奇异,再由 引理6知A非奇异.证毕. 定理7当,l?13时,除A(6,3),A(,l,,l一2)外, A(,z,走)-1?o,其中,z,走至少有一为偶数. 证直接验证可得. 定理8对任意,l?13,0<走<,l,,l,走至少有一 为偶数,除走=,l一2外,A(,l,走)-1?o. 证由定理7,,l=13时,V偶数量,1<走?,l一 1,A(,l,走)-1?o,设13<,l?t一1时,结论成立; 当,z=t时,若t为偶数,当走=詈,詈+1时,定理 4,5已证,当走<詈时,由文献[1]得,B(詈,走).? 椭^f?B(量-1,令A=非 参考文献: 奇异;当詈+2?走?,l一1时,4?2k一,l?,l一 2,1~12k一,l为偶数,取走l=,,ll=号,,ll一 点l=詈一=,l一点?22,I=l,ll?7一,由假设意l=一—=,l一患?,,ll,田1阪议 A(l,走1)一.?o,取M?A(l,走1),,令A= l,'l,则A?Ac,走,由引理4知A非奇 异;若,为奇数,则是为偶数,当走<一1,如果 丁n-1一是>2,则A(,走)一?,A(, 走)一.?,如果生一点=2,则生一点=1, A(生,走)一.?,A(生#,走)一.?,由假设, 总可以找到非奇异矩阵^f,jv,使M 一 . jvO)? A(,l,走)一l;若是=一1,则,l=2k+3,定理 6已证;若是:生},生,则(,l,走):1,由引理 3知A(,l,走)一.?,若<走?,l一1,则3? 2k一,l?,l一2,且2k一,l为奇数,令2k一,l=2s +1,取是l=s+1,是2=s,nl是一s,n2=是一s 一 1,贝00<,ll一点l=r/2一点2=,l一点?2,,l2? 走l,且(l,走1)?(6,3)(否则(,l,走)=(11,8)), (,l2,走2)?(6,3)(否则(,l,走)=(13,10)),由假设 A(l,走1)-1,A(,l2,k2)一.?o,取M?A(l, kt),.N?A(,l2.k2),,则A= A(,z,走),由引理4知A非奇异. 3结语 fMJ:1 N J? 证毕. 综上,作者已证明了本文的主要结果,当,z,走 中至少有一个为偶数(0<走<71)且(,l,?(6, 3),(,z,,z一2)时,存在邻接矩阵非奇异的阶走一 正则简单图. [1]HOUCKDJ,PAULME.Non-singular0-1MatriceswithConstantRowandColumnSums [J].LinearAlgebraandAppl, 1978,22:263—266. [2】程云鹏.矩阵论[M】.西安:西北工业大学出版社,1989, [3]PULLMANDJ,STANFORDM.Singular(0,1)Mamc~withConstantRowandColumnS ums[J].LinearAlgebraandAp- pl,1988,106:195—208. [4]潘承洞,潘承彪.初等数论[M].北京:北京大学出版社,1992.(责任编辑:彭守敏)