（基础数学专业论文）图的laplace矩阵的谱和smith标准形.pdf

中文摘要 本文中我们主要考虑了一般简单连通无向图的l a p l a c e 谱半径 和s m i t h 标准形，具体结果如下： 1 利用图的度平方和的不等式，得到一般简单连通无向图的l a p l a c e 谱半径的一个上界 仁) 笔+ x m ( n - 2 i ) ( r a n 了+ 2 n 一- 4 m - 2 ) n 一l甩一1 等式成立当且仅当g 为星图k q 。 2 研究了完全图与路图的积图k 4x c 的l a p l a c e 矩阵的s m i t h 标准 形，得到如下结论： ( a ) 对于n = 2 m + l 是奇整数图k c 。的l a p l a c e 矩阵的s m i t h 标准形为 其中序列k 定义为k = 6 k 一广k 印h o = 1 = 7m 2 ) ； ( b ) 对于n = 2 m 是偶整数，图k 。c 。的l a p l a c e 矩阵经过初等行 列变换得到的对角矩阵为： 。器 4 0 0 0 0 0 k 0 0 0 0 o k o 0 0 0 o k 0 0 0 o 0 k 0 0 0 0 0 k 0 0 0 0 0 、_ 、 o o o o o o o ，k ) 0 0 k o 0 00 00 0o 000 00o k 0 0 0 七_ 0 00 3 磁 000 000o0 00 o0 00 0o 其中序列k 定义为k = 呶q k 掣k o = o ，毛= 1 ( m 2 ) 一般地，此对角矩阵不是s m i t h 标准形。 关键词：图的l a p l a c i a n 矩阵；谱半径；矩阵的s m i t h 标准形；完全图 ： 0 放 0 ，j a b s t i 认c t i nt h i st h e s i s ，w em a i n l yi n v e s t i g a t et h el a p l a c i a n s p e c t r a lr a d i u sa n ds m i t hc a n o n i c a lf o r m o fg e n e r i cs i m p l e u n d i r e c t e dc i r c u m f e r e n c e ，a n da c h i v ef o l l o w i n gr e s u l t s ： 1 、b yu s i n gt h ei n e q u a l i t i e so nt h es u mo ft h es q u a r e so ft h e d e g r e e so fag r a p h ，w eg e tas h a r pu p p e rb o u n df o rt h el a p l a c e s p e c t r a lr a d i u so f si m p l ec o n n e c t e du n d i r e c t e dg r a p h s ： )旦n-1+、m(n-2)i(ran+广2n-4m-2)n l e q u a l i t yh o l d si fa n do n l yi fgi ss t a rg r a p h h - 1 2 、i n v e s t i g a t et h es m i t hn o r m a lf o r mo fl a p l a c em a t r i xo f k c - ，a n do b t a i nf o l l o w i n gr e s u l t s ： ( a ) f o ro d di n t e g e r n = 拥+ 1 ，t h es m i t hn o r m a lf o r mo fl a p l a c e m a t r i xo fk qi s ： w h e r e o ，k ) o 0 0 o 0 0 0 0 0 0 k 0 o0 k = 6 k q 九一2 ，h o = 1 ，j i l l = 7 ( m 2 ) ； ( b ) f o re v e ni n t e g e r 厅= 2 m ，t h el a p l a c em a t r i xo fk 4 q b e c o m e st h ed i a g o n a lm a t r i xt h r o u g hp r i m a r yt r a n s f o r m a ti o n ， t h ed i a g o n a lm a t r i xi s ： ：。盟m 0 0 0 0 o k o 4 0 o 0 k 0 0 o 0 k o 0 0 0 0 k 0 0 0 0 0 o ，k ) 0 0 吒 00 00 00 00 ooo 000 k 00 0 k 0 00 3 2 k 000 00000 00 00 00 00 w h e r ek = 呶q k 2 k o = o ，毛= 1 ( m a 2 ) g e n e r a l l y ，i ti sn o ts m i t hn o r m a lf o r m k e yw o r d s ：g r a p hl a p l a c i a n ：s p e c t r a lr a d i u s ：t h es m i t h n o r m a lf o r m ；c o m p l e t eg r a p h i v 。盟眠 0 放 0 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不合任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：王湘斗卅年f ，月w 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 研究生在校攻读学位期间论文工作的知识产权单位属湖南师范大学。 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“ ) 作者签名：王：嘶日期：w 7 年 tr 月沙 日 导师签名：专苌耀孚日期：u b 7 年i1 月吖日“ 图的l a p l a c e 矩阵的谱和s m i t h 标准形 第一章综述 1 1 图的l a p l a c e 矩阵的谱 图的谱理论是图论与组合矩阵论的一个重要研究课题，其主要研 究图的不同矩阵表示( 邻接矩阵，l a p l a c e 矩阵等) 的谱，建立图的 拓扑结构( 特别是图的各种不变量) 和图的矩阵表示的置换相似不变 量之间的联系，利用置换群理论和谱几何理论，研究图的拓扑结构性 质，同时也将图的谱理论的经典结论用于非负矩阵理论和组合矩阵 论，以推动组合矩阵论的研究。图的邻接矩阵的谱和l a p l a c e 矩阵的 谱都是图的同构不变量，前者是图论，特别是代数图论的一个基本研 究课题，已经形成了相当成熟的理论详见c v e t k o v i c ，d o o b 和s a c h s 的名著 s p e c t r ao fg r a p h s ) ) 8 】与图的邻接谱的研究相比，尽管早在 1 8 4 7 年g k i r c h h o f f 已将图的l a p l a c e 谱用于电流网络的研究并给出 了著名的矩阵一树定理 3 】，但图的l a p l a c e 谱的研究受到人们普遍关注 则是近几十年的事情在七十年代初期，通过图的l a p l a c e 矩阵在一些 文献 9 ，l o q b 的出现，人们才逐渐地认识到它。由于在l a p l a c e 矩阵 的定义中揉进了顶点的度，因此l a p l a c e 谱比邻接谱更能反映图的性 质，如图的连通度、直径、宽带、二部宽、等同数、最大割、超缩子 和扩冲子、平均距离、边前项指数等等，所以l a p l a c e 谱的研究越来 越受到更广泛的关注。 本文所研究的图均为无环、无重边的简单连通图。设图g = ( y ，e ) ， 其中y 为顶点集，v = y ( g ) = h ，吃， ，川= ”称为图g 的阶数；e 为边 集，e = e ( g ) = q ，e 29 1 9 ) ，吲= 聊为图g 的边数 高校教师在职硕士学位论文 图g 的邻接矩阵记为彳= 彳( g ) = ( 口 ) ，是一个以阶的( o ，i ) 方 阵以d ( g ) 表示图g 的顶点度构成的对角矩阵，即 d ( g ) = d i a g d 。，破，以) ，其中吐吐吃 则图的l a p l a c e 矩阵定义为三( g ) = d ( g ) 一彳( g ) 由定义可知上( g ) 是对称 半正定方阵且每一行的行和为零，所以0 是( g ) 的最小特征值三( g ) 的全体特征值可以如下表述： 印馏( 三( g ) ) = “( g ) ，鸬( g ) ，以一。( g ) ，以( g ) ) ，称为图g 的l a p l a c e 特征 值或l a p l a c e 谱。其中h ( g ) 鲍( g ) 以一( g ) 以( g ) = o ，称最大特征 值h ( g ) 为图g 的l a p l a c e 谱半径，通常用( g ) 表示。根据工( g ) 的定义， 我们可以得出谱半径与度序列之间的关系，即肛= 4 = 2 m 1 2s m i t h 标准形与图的临界群 整数矩阵的s m i t h 标准形，是指给定一个整数矩阵a ，它可以 在整数环z 上实施一系列的初等行列变换，得到唯一的对角矩阵 s ( a ) = d i a g ( s 。，最：，最。) 它的元素是非负整数且瓯整除墨+ 对每个i ， 积s 。s ：& 是a 的所有i 阶子式的最大公因式我们将由此来计算 矩阵a 的s m i t h 标准形。 两个矩阵彳，bez 删_ ，若存在矩阵peg l ( m ，z ) ，q g l ( n ，z ) ，使得 b = p a q ，则称a ，b 是幺模等价的 1 l 】，记作a b 易知由a 曰可得c o k e r a = c o k e r b ，若a = d i a g ( a l ，口2 ，吒) ，则 c o k e r a 兰z qo z 。：o o z 口_ 其中z 。= z 口z ( z 是平凡群且z 。= z ) 图的l a p l a c e 矩阵的谱和s m i t h 标准形 在矩阵分析中，矩阵( 指整数矩阵) 的s m i t h 标准形应用很广， 通过它可以得到矩阵的秩、矩阵的逆、特征值和简化矩阵的计算等。 把s m i t h 标准形应用到图论，求连通图的临界群( c r i t i c a lg r o u p ) 在 国内和国外都是才刚刚起步。在本文中，我们的主要方法是计算，就 是计算整数矩阵的s m i t h 标准形来确定连通图k 。x c 。的临界群。 连通图的临界群是定义在图上的一个有限群。其群的结构是图的 一个精细不变量，它与图的l a p l a c e 矩阵密切相关。设g _ e ) 是一 个多图，那么，它的l a p l a c e 矩阵三( g ) = d ( g ) 一a c g ) ，其中邻接矩阵为 彳= 彳( g ) = ( ) 嗍，度矩阵为d ( g ) = d i a g d 。，吃，以) 。将l ( g ) 看作射影 z ”专z 一，它的余核形式为： c o k e r l ( g ) = z 。l ( g ) z “兰zok ( g ) ， 在群的同构意义下这里的k ( g ) 称为图g 的临界群 图的临界群的研究不仅与自组织临界态 7 】的研究有关而且在理 论计算机的研究中有着重要作用。它潜在的a b e l i a n 结构被d h a r 6 和c r e u t z 5 所发现，特别地，这个群的阶恰好是图的生成树数目，且 有两个基本的双射存在，从纯数学上来看，图的临界群可以认为是图 的生成树数目的一个加细，即在图的生成树集上定义一个群结构，便 可以利用有限群的理论来研究图的生成树的数目在代数图论中，由 矩阵树一定理 3 知，g 生成树数目r ( g ) = ( 一1 ) “j d e t ( l ( g ) ) 驴，其中( 上( g ) ) 盯 为矩阵三( g ) 的元素厶的代数余子式这个定理的另一个表达方式是商 群7 , 4 a ( g ，) 也是有限的，且它的阶等于f ( g ) ，我们称此商群为g 的 临界群k ( g ) 高校教师在职硕士学位论文 目前，有许多图的临界群被完全确定，如格子图只e 、轮图、梯 子图只e 、阀值图、完全多部图、完全二部图的线图、m 6 b i u s 图、 手镯图、循环图q 、图c 3 q 等，它们的临界群结构被完全确定n 6 ， 1 4 ，1 5 ，1 8 ，1 9 ，2 0 ，2 1 ，2 2 ，2 3 ，2 4 。这些临界群都是有限交换 群，并且是几个循环群的直和。 由于有限交换群的s m i t h 标准形可由它的生成元的关系矩阵的 s m i t h 标准形而得到，因此为了确定群的结构，只需求出它的关系矩 阵的s m i t h 标准形即可 1 3 主要内容 1 第二章，我们主要讨论了简单连通无向图的谱半径，并利用图 的度平方和的不等式，得到了一个新的上界 邸) 各+ _ 、m ( n - 2 1 ) ( m n 丁+ 2 n 一- 4 m - 2 ) 刀一l以一l 等式成立当且仅当g 为星图毛巾。 2 第三章对图k 。c 。的l a p l a c e 矩阵s m i t h 标准形进行了研究， 得到了如下结论： 对于刀= 2 m + l 是奇整数图k 。x c 的l a p l a c e 矩阵的s m i t h 标准 形为 4 图的l a p l a c e 矩阵的谱和s m i t h 标准形 oooo oo 丝 ( 刀，死) 其中序nh 定义为死= 6 h m 一，一巾h o = l ， = 7 ( 聊2 ) ； 对于刀= 2 m 是偶整数，图k 。c 。的l a p l a c e 矩阵经过初等行 列变换得到的对角矩阵为： ( ，l ，k ) 0 00000 0 k 0000 j c l 00 k 0000 000 k 000 0000 3 2 k 00 0 0 0 00 3 2 吒0 000ooo 皇生 ( 力，k ) 其中序列吒定义为k = 6 k 一，一吒巾k o = o ，墨= 1 ( m 2 ) 一般地，此对角矩阵不是图k 。c 。的l a p l a c e 矩阵的s m i t h 标准形。 5 0 0 0 0 0 0 0 o 0 o 0 k 月i - 0 o o o k o o o 0 k o o 0 0 k 0 0 0 0 k 0 0 0 o 、 肌 加0 o o o 0 ，m 高校教师在职硕士学位论文 第二章图的l a pia c e 谱半径的一个上界 图的l a p l a c e 谱半径是图论研究的一个重要方面。关于l a p l a c e 谱 半径的上界已有很多好的结果。本节中，先给出与图的度序列有关的 l a p l a c e 谱半径的若干上界 ( 1 ) 1 9 9 7 年，7 s l i 和x d z h a n g 给出了下面两个关于度序列的 l a p l a c e 谱半径的上界 引理2 2 1 1 】若g 为以阶连通图，g 的度序列为吐d ：d 。则 ( g ) 2 + 托百i 丽i ；两 等式成立当且仅当g 为正则二部图或者路p ，或者路p 。 引理2 2 2 1 】记，= m a x 吃+ 盛 1 1 v ) ，设工，yey ( g ) 且d ，+ d ，= ，另记 j = m a x d + d ， u l j e e ( g ) 一x y ) ，则( g ) s 2 + 4 ( r - 2 ) ( s - 2 ) 2 0 0 2 年潘永亮( y l p a n ) 证明了上式等式成立当且仅当g 为正则二 部图或者半正则二部图或者路p 。 ( 2 ) 2 0 0 1 年，j s z i 和y l p a n 给出了与图的顶点的度及顶点数刀、边 数i n 有关的l a p l a c e 谱半径的几个上界 引理2 2 3 2 】若g 为刀阶连通图则 ( g ) 2 m + x ( n - 2 ) ( _ n ( - n - 1 ) - 2 一m ) m 刀一l 等式成立当且仅当g 为星图钆一。或者完全图七。 引理2 2 4 2 】若g 为刀阶连通图，则 ( g ) , 2 彳+ 4 m 一2 d ( n 1 ) + 2 d j ( d 一1 ) 等式成立当且仅当g 为正则二部图 引理2 2 5 1 2 】若g 为刀阶连通图，则 图的l a p l a c e 矩阵的谱和s m i t h 标准形 ( g ) m a x 历丽：“y ( g ) 等式成立当且仅当g 为正则二部图 ( 3 ) 2 0 0 2 年，上s h u 等给出了关于度序列的l a p l a c e 谱半径的上界 引理2 2 6 4 】若g 为刀阶连通图，度序列为面畋吃则 二( g ) 吃+ 丢+ ( 矾一圭) 2 + 喜嘎( 面一以) 等式成立当且仅当g 为星图毛川或者路仇 2 0 0 4 年k c d a sj 丕给出了下面的l a p l a c e 谱半径的上界 引理2 2 7 1 3 若g 为刀阶连通图，则 邸 盟一0 等式成立当且仅当g 为正则二部图或者半正贝, t l - 部图 ( 5 ) 2 0 0 4 年x d z h a n g 给出了另外两个图的l a p l a c e 谱半径的上界 引理2 2 8 1 1 6 】若g 为刀阶连通图，则 ( g ) m a x 2 + 厄百瓦丽瓦西瓦刁而：甜v 等式成立当且仅当g 为正则二部图或者半正则二部图或者路p 。 引理2 2 9 1 1 6 】若g 为玎阶连通图，则 ( g ) m a ) 【 反+ 厮，：y y ( g ) ) 等式成立当且仅当g 为正则二部图或者半正则二部图 ( 6 ) 2 0 0 4 年尹书华在硕士学位论文中给出了图的l a p l a c e 谱半径的 上界 引理2 2 1 0 1 17 若g 为行阶连通图，度序列为嘎吐d 则 ( g ) d ) + 2 4 - 1 + ( i - 1 ) ( 了d , - d , ) + ( d , - 一2 d , - 1 ) 2 高校教师在职硕士学位论文 其中1 i ，l ，当f 2 时等式成立当且仅当g 为正则二部图，当i = 2 时 等式成立当且仅当g 为正则二部图或者星图 通过比较，我们得到了另一个新的l a p l a c e 谱半径的上界 引理2 2 1 1 1 1 2 】设g 为刀阶m 边连通图，其度序列为4 畋以则 喜砰石n m 2 等式成立当且仅当g 为星图h 定理1 设g 为刀阶m 边连通图，d 是度对角矩阵，a 为邻接矩阵， 三= d a 为l a p l a c e 矩阵，则 “( ) 2 m + n m ( n - 2 ) ( m _ ：n - + 2 n - 4 m 一- 2 ) 1 1 一l 等式成立当且仅当g 为星图k 。扩 证明：设鸬( 三) 鸬( 三) 以( 三) = o 是g 的特征值，于是 鸬( 三) + 鲍( 工) + + 以( 三) = 喀 i = i 由于彳( 三) ，店( 三) ，正( 工) 是r 的特征根。因此， 彳( 三) + 詹) + + 群犯) = ( 砰+ 喀) i = 1 由c a u c h y s c h w a r z 不等式有 ( 刀一2 ) ( 正( 三) + 詹( 三) + + 三l ( 三) ) ( 鸬( 上) + 鸬( 三) + + 以一，( ) ) 2 ( 1 ) 且2 脚m + 懈舢脏静刊弘叫2 。c “c ，一窆t = l4 ，2 c 万一2 ，ic 刀一- ，喜c 砰+ z ，一i 喜珥1 2lij = ilj = li1 a l ( 上) 2 和卜， ( 玎一1 ) ( 矸+ z ) 一( z ) f = lv 扛lf = l 图的l a p l a c e 矩阵的谱和s m i t h 标准形 = 三二二! 二二兰 ! ：二! ：! 茎! 二薹兰! ! 二! 茎兰! ! ： 2 m + 力一1 ：三竺巫至夏至五亘画 以一1 ：三竺垣三亟亟至亚 以一1 s 2 m + 、! 匠( n - 2 萼) m ( m n 霉+ 2 n - 4 m - 2 ) 若肛( 驴2 m + x i n - 2 _ ) m ( 了m n + 囹2 n - 4 m - 2 ) 则 ( 以一2 ) ( 么( ) + 詹( 三) + + j 9 2 ，一l ( 三) ) ( 鲍( 三) + 鸬( 三) + + 以一l ( ) ) 2 式中等号成立，则g = 毛扩。 r 群一111 1 i 1 tl0 0 反之，若g = 毛扩，三= d a = i 1 01 0 l ；i i100 1 “( 三) = n ，鸬( 三) = 如( 三) = = a ( z ) = 1 。 而图向，剃中m = 刀一1 ，则 刀一1 ( 2 ) 和 2 ( n 一1 ) + 4 ( n - 2 ) ( n - 1 ) ( ( n - 1 ) n + 2 n - 4 ( n - 1 ) - 2 ) 刀一l 2 n 一2 + n 2 3 n + 2 疗一1 一( 三) = 2 m + n ( n - 2 ) m ( m _ n + 2 n - 4 一m - 2 ) 成立 刀一l 9 生 一彩 。问 高校教师在职硕士学位论文 第三章完全图与路图的积图的s m i t h 标准形 3 1引言 给出两个图g l = ( 巧，互) 和g 2 = ( 圪，易) ，g l 和g 2 的c a r t e s i a n 积图定 义为g i g 2 = ( 矿，e ) ，矿= k ，且g l g 2 中两顶点( 而，屯) 与( m ，躬) 相邻当 且仅当玉= 咒且 而，儿 易或 ，乃 骂且屯= 容易验证g l g 2 的l a p l a c e 矩阵与三( g 1 ) 和三( g 2 ) 的关系为： 三( g l g 2 ) = 三( g 1 ) i + io 三( g 2 ) 其中，为单位矩阵，o 为矩阵的张量积设三( g i ) 和三( g 2 ) 的特征值分别 为五，“，i = i ，2 ，i k l l j = l ，2 ，i v ：i ，由上可知三( g i g 2 ) 的特征值分别为 五+ 鸬，i = 1 ，2 ，k i ，= l ，2 ，i k i 3 2 图k 。c 。的l a p la c e 矩阵的s m it h 标准形 目前，关于图的l a p l a c e 矩阵的s m i t h 标准形已有一些结果，如 髟瞩，墨g 等。本节的计算s m i t h 标准形的方法类似于 2 4 中计算 c 3 e 的方法，并且这种方法可推广到一般的q 中。 图1 k 。c 。 i 3 2 1 图k 。c 生成元的关系矩阵 如图1 所示，设k 。的顶点集合是k = ( o ，1 ，2 ，3 ) ，q 的顶点集合为 k = ( 1 ，2 ，3 ，n ) ， 设 那么k 。c 。的顶点集合为 k k = ( i ，j ) ，i = o ，1 ，2 ，3 ，：j = 0 ，1 ，2 ，3 ，n 一1 l 毛= ( o ，i ) ，y f = ( 1 ，i ) ，z i = ( 2 ，i ) ，乃= ( 3 ，i ) ，产1 ，2 ，n ； 在断n e zz 4 n1 1 i l l l ( k 4 e ) 中，五，雎，z ；，以的像分别为霉，y j ，乏，万。 把倒塌规则运用于每一个项点，就可以得到以下等式： 且有 夏= 5 夏一l 一夏一2 一只一l 一- e , 一l 一死l m = 5 死1 一死2 一- e , 一广万一l 一 虿f = 5 瓦l 一- e , 一2 一元一l 一瓦l 一只- l 元= 5 万一l 一无2 一焉一l 一碌l 一一z i - i 瓦= 5 瓦1 一x 。一2 一一l z 。- 1 一九- 1 一一一一 死= 5 只一l y n 一2 一z n - l 一以一l 一一1 一- 一一 一 一一 毛= 5 瓦一。一乏一：一无一，一瓦一t 一兑一- 死= 5 死一，一无一：一瓦一。一死一- 一乏一- 写= 5 磊- - 一x n 一。一死一磊一死 甄= 5 死一只一一磊一死一磊 乏= 5 磊一乏一。一死一磊一死 万= 5 死一瓦一1 一磊一y o 一一z o 从以上的方程组可以看出，j i ：，歹：，乏，元 ( i = 0 ，1 ) 是 ( 3 2 1 ) ( 3 2 2 ) k e r 以口，z 4 一h n l ( k 4 e ) 的一组生成元对于3 f 刀一1 ， a i , 岛，q ，d i ，岛，z ，g i ，囊 被确定，所以 夏= q 写一岛写一c i y , +a y o e 夏 通过归纳证明，我们可以得到： + f i f o - g ，死+ 红死。 l l 和 高校教师在职硕士学位论文 只= q 只一b y o q 三+ d ：oq 元+ f y o 一写+ 噍写 乏= 口f 乏一b ：o q 万+ d 死一q 写+ z 磊一岛只+ 吩死 万= q 元一b y o q 墨+ 瓴- e , y , + z y o g ，一z i + 吩磊 a i25 a i l a i 一2 + q i + 乍l + 一l 6 ： = 5 b , 一l 一6 ：f 一2 + 吐l + z l + 红l q 2 5 q l q 一2 一q l g i l + a i i 4 = q 一。 q 2 q 氕= d i 9 1 2 e 囊= 石 岛= 口j l 初始值为口2 = 5 ，口3 = 2 7 ，b 2 = 1 ，b 3 = 5 ，c 2 = 1 ，c 3 = 8 。 ( 3 2 3 ) 由( 3 2 3 ) 式的后六个等式，将前面三个等式划为： 即 则有： c 1 = 3 c 2 一c 3 + 口2 = 3 5 + 8 = o ； c o = 3 q c 2 + c z l = 3 q c 2 + 包( 岛= a i 1 ) = 0 ； 岛= 5 6 2 6 3 + 3 q = 5 5 + 0 = 0 b o = 5 b , 一吃+ 3 c b = o 一1 + o = 一1 a l = b 2 = 1 a o = 岛= 0 所以，初始值为口。= 1 ，c z o = o ，6 1 = o ，b o = 一1 ，q = c o = o 命题3 2 1a i ，6 f ，q 如前定义，当f 3 时，以下等式成立。a i - 3 q = f ， 证明 q = 6 q l q 一2 + f 一1 由( 3 2 3 ) 式可知，q 一3 q = 2 ( a f l 一3 c ；一i ) 一( 咋2 3 q 一2 ) 1 2 ，又因 一 叫 l纠舻训 五 之 他 -卜 h ，- 力 3 ) 且而= 墨= o ， 我们通过计算有4 巳+ 玎= + ，一。 定理2 当刀4 时，c o k e r n e lz 4 “h n l ( q c ) 的生成元 一x o ，鬲，y o ，两，一g o ，乏，y o ，冗的关系矩阵等价于： 刀000 0 q墨 霸+ l 0 0 c 斛ls + 1 + 2 1 00 000 s 。一j 。一l + 1s n + l 一 00 0 4 s 。4 s 。+ l o0o0 0 0oo0 0 0o000 0 0 0 o o 一& 一l + 1 4 s o o o oo oo o0 o 0 + l 一0 4 s + l 0 0o 换句话说，当疗4 时，我们有s ( 墨e ) 兰z 6 a z 6 。 证明： 对于焉，y o ，一z o ，y o ，夏，y l ，乏，冗之间的关系矩阵等价于： 所以 一f ，4 lo 、 一l00 j x o = 口。夏一b - z o 一巳歹；+ 吃y o 一巳亏+ 五毛一 + 吃死 y o = q 只一阮y o 一巳乏+ a r o 一巳元+ z 死一g 。夏+ 吃瓦 一z o = a , , 一z t - b - e o - c 7 , + 吃7 0 e 2 t + z 磊一邑只+ 死死 死= 吒死一钆死一巳写+ 以瓦一巳只+ 六y o 一邑乏+ 吃毛 夏= a n + l 五- b + 。x o q + 。只+ 吃+ y o e h + 。乏+ z + i 磊一岛+ i 元+ 吃+ i 瓦 兄= n + l 习- b + l 瓦一巳+ l 乏+ 以+ l 磊一e n + l 元+ 五+ 1 7 0 g 。+ l - e , + 吃+ l 磊 乏=an+一-b+l磊一cn+1只+以+l死一en+i夏+z+lxog。+1只+吃+lyoani z ix ogz l2+ l z o 一+ l 乃+ d 月+ 1 一+ i j c l 十 + l一。+ l m 十+ l 万= 畋+ l 万一吃+ 。死一c n + l x 1 + 以+ ，瓦一e 州只+ 无+ ，元一+ 乏+ 吃+ - 乏 1 3 高校教师在职硕士学位论文 色2 口_ 一g 。 一气 一c | a l 一1 一g _ + i 一毛+ i 、 一c 3 c + 刀 _ i l 1 1 3 乞“+ 刀 q “ _ c 一+ i q + l 一( 吮+ 1 ) 以 五 d 吃+ 。 以+ 五“ 以+ 一( 3 0 l + 刀) c l - i q 一1 c | 一i - ( 3 巳+ 以) c c q c _ a _ - g - 一巳 一- a h l - i g - + l 一巳+ l q 3 c + 刀 q c 一 q “ 3 c 肿i + 疗 c 一+ i c 矗+ l 屯 一以+ 1 ) 屯 1 i t + i 一瓦+ 。 肿。 正+ i 1 一c 口膏 - g 一巳+ 1 一c | “ 口i “一i 一晶+ l 巳 一c 蠢 3 e + 万 c - c 肿l c 肿l 3 钆l + 露 c 0 i c 一一i c l - i 弋3 q l + 咒) 巳一i q c _ - ( 3 c , + 以) c i g | 一气 - c i 口一 一g n i 一+ i c 一+ l a _ + l - 1 _ c _ _ _ 3 乞+ 开 1 巳“ i _ + l k l + 刀 屯 工 以 一盹+ 1 ) 一+ 五“ 以“ k i 将所有的列加到最后一列上，然后将2 行乘以3 加到第1 行上，从第 3 行中减去第2 行，从第4 行中减去第3 行，将6 行乘以3 加到第5 行上，从第6 行中减去第7 行，从第7 行中减去第8 行，得 b 。 一刀 8 q + 3 n 3 c , + n - ( 4 c + 疗) o 8 乞“+ 3 n 4 c , 一l + 刀 0 一c 一“ 8 c + 2 n 心+ 刀 - ( 4 c + 刀) 0 8 q + t + 2 n 屯一l + n 0 o 一- l 一3 厅 3 c 一l + 玎) 4 c j - l + 疗 o ( 8 q + 3 甩) 一( 4 c + 胛) 0 8 q l 一2 万 一( 4 c 一一l + 刀) 4 c , 一l + 刀 o - ( 8 c + 2 n ) - ( 4 e + 以) o 0 一 4 c + 刀 一( 4 c + 疗) b + l 一( 4 c 一一i + 刀) 4 c , 一i + n 一乞+ i 魄一n o 4 c , + 万 一( 4 q + 万) - 4 q + l 一露 一( 4 巳一i + 刀) 心一l + 露 o 1 4 4 q l c 一- l 弋4 c 纠+ 刀) 4 c , 一l + n 4 c 咆+ 刀 - ( 4 c + 玎) c - 4 q l + n 0 一( 4 c 一一l + 刀) 乜一l + 捍 4 1 + 一 心+ 刀 一( 4 巳+ 拧) 0 到： 概 一 o 4 c + n 4 巳+ l o - ( 4 c 一i + 刀) 3 q + 1 + n 乜+ 3 n 0 -4巳0 0 o 4 q + 刀0 乜+ l + 3 n 0 00 一( 4 巳一i + 以) 0 n 0 以“吃厶k h h以吃丘“屯 o ) 谓 万 印印分州蟊厶“鳓 。 。 。孔nv 、一 一 帕 吩 棚 甜钳甜昏“鳓以以“厶渺厶办 1 是成立的，则 又因为 = 乞r = 6 峰一2 乞。一。 一= 乞乒，= 嘭一砖一。 6 砝= 3 2 ( 2 8 + 口2 州) 2 = 3 2 2 2 。( 1 + 2 口) 2 = 3 2 2 什1 ( 1 + 2 口) 2 暑0 ( m o d 2 什2 ) 嘭2 兰0 ( m o d 2 酣2 ) 所以 乞卅_ = - 2 k 2 ，k 2 , 一。( m o d 2 8 + 2 ) 詈2 ( 2 。+ 口2 e + 1 ) ( 2 8 - l + b 2 外1 ) ( m o d 2 什2 ) 兰- 2 抖1 ( 1 + 2 口) ( ( 2 。- 1 ) + b 2 甜1 ) ( m o d 2 什2 ) 喜- 2 “1 ( 1 + 2 口) ( 2 。- 1 ) ( r o o d 2 抖2 ) 量2 e + l ( 1 + 2 a ) ( m o d 2 2 ) 暑2 1 ( m o d 2 “2 ) 1 9 高校教师在职硕士学位论文 且 q 三一嘭一。( m o d 2 2 ) - - ( 2 。- l + b 2 。+ 1 ) 2 ( r o o d 2 。+ 2 ) - _ - - ( ( 2 。- 1 ) 2 - 2 ( 2 。一1 ) b 2 抖1 + ( 6 - 2 抖1 ) 2 ) ( m o d 2 m ) 暑- ( 2 。- 1 ) 2 ( m o d 2 外2 ) - - - - ( 2 知- 2 2 + 1 ) ( r o o d 2 m ) 量2 外1 1 ( m o d 2 2 ) 口 令p k ( t ) 为序列屯模，下的周期，那么由定义可直接得： 乞兰吒舢) ( r o o df ) ，k - 0 ( r o o df ) 引理3 2 3 1 2 4 如果f lf 乞，j g 么p k ( t , ) f p k ( t , ) 引理3 2 4 设p 1 ，当n = 2 m 时，如果2 。i 即，那么2 叫屯，2 e - i i k ；当n = 2 m + l 时， 2 。f k 证明：令口，是二次方程x 2 6 x + l ：0 的两个根，且 口+ = 6 ，筇= 1 ，则口= 3 2 芝，夕= 3 + 2 、f 2 又因为 吒= 6 吒一- k 一：，所以吒= ( 口+ ) 吒一一q 睨一： 由( 3 ) 有吒一口吒一。= ( 屯一。一口吒一：) = 2 ( 吒t - a k 4 ) - 一o - o = ”1 ( 墨一口气) 即 屯一口吒一。= ”1 ( 墨一a k o ) 同理，有 吒一吒一。= 口”1 ( 毛一七0 ) 由( 4 ) ( 5 ) 联立，解得： ( 一口) 吒= “( 毛一a l , o ) 一口4 ( 毛- p k o ) ( 3 ) ( 4 ) ( 5 ) 图的l a p l a c e 矩阵的谱和s m i t h 标准形 即 ( 一口) 吒= ( ”- - 5 ”) 毛一( ”口- - 5 “p ) k o 吒= ( p - a ) 与，- a 二p ( p - 一- a - ) k o 所以吒= 警一警= 硒1 ( ( 3 + 2 厨一( 3 2 厨) = 去c 剡3 州c 2 四一划3 川h ) j ( 2 勘 = 丽1c 。s 磊如( 2 二。 3 叫2 p 。c 2 压尸+ 1 ， = 磊如( 2 二。卜川增， 因此，如果2 。i ，l ，那么2 8 k 又因为九= 盥等攀 一( 3 + 2 q r 2 ) ”( 7 一( 3 2 f f 2 ) ) 一( 3 2 f f - 2 ) ”( 7 一( 3 + 2 f f 2 ) ) 4 压 = 硒t ( ( 4 + 2 压) ( 3 + 2 压) ”一( 4 2 压) ( 3 2 压n 2 去( ( 4 + 2 压) ( 压+ 1 尸一( 4 2 压) ( 压一1 ) 2 册) 2 击( 2 压( 压+ 1 ) 2 历“一2 压( 压一1 ) 2 m + 1 ) = 圭( ( 压+ 1 ) 2 州一( 压- 1 ) 2 州) 2 壶( 2 善m + l ( 压) f - 善( 压) j ( 一1 ) 2 肿i - ) 2 壶( 2 委m + l ( 压) + 善( 压) f ( _ 1 ) ) 2 1 高校教师在职硕士学位论文 = 1 砘胆e 川2 b1 p l 略“2 笏1 2 因为2 叶2 m + 1 ，所以2 。概。 定理4p k ( 2 。) = 2 。 口 证明：首先我们证明对所有的e ，有- f f io ( m o d2 e ) ， k 2 , 一。- 1 ( r o o d2 e ) ，这些可以由引理3 2 2 和引理3 2 4 得到，并且对 所有的e ，有p k ( 2 。) 1 2 。通过计算当p = 1 时有2 。i p k ( 2 。) ，由引理3 2 3 有 2 8 = p k ( 2 。) i p k ( 2 ”1 ) 和p k ( 2 。) f 2 1 ，于是有p k ( 2 什1 ) = 2 。或者2 抖1 所以 = 2 。( m o d 2 州) o ( r o o d 2 州) ，贝, l j p k ( 2 。+ 1 ) = 2 州 引理3 2 5 若2 ei 刀，2 州j ，力，则2 纠 k n - n 4 证明：令刀= 2 。m ，2j ，m ，则朋= 2 y + x ( x = i ) ，有 且 我们得到 从而 刀= 2 。m = 2 x + 2 什1 y 暑2 e x ( m o d 2 什1 ) = 2 。( m o d 2 什1 ) ，工= l 吒2 肘2 卅y 言工( r o o d 2 州) 兰2 。( m o d 2 什1 ) ，x = 1 七 一刀= 0 ( m o d 2 “1 ) 图的l a p l a c e 矩阵的谱和s m i t h 标准形 2 州l 吒一甩( m o 1 ) ，所以2 纠i k n 4 - n - 引理3 2 6 对任意 ，有 口 ( 吒，砖一，) = ( ，吃一。) = 1 ，( 吒一吒巾吒卅一吒) = ( 吃- 2 ，吃+ 一吃) = 1 证明：证明前一部分，假设吒，吒一。均被一正整数d 整除，则 6 吒一吒一= 吒一：也被d 整除。类似的，di 吒巾di 吒印，最后必然有di 墨 因为毛= 1 ，所以d = 1 。从而整除序列吒的连续两项的唯一正整数是 1 后一部分可以类似地证明 类似地，我们还可以得到下列等式 j 川一瓯= 吒 屯。= k 吒 s 2 。+ 2 = 吒吒+ i ( s 2 。，$ 2 m + i ) = k ，0 2 。+ l ，屯斫+ 2 ) = 吒 3 2 3 4 ，的s m i t h 标准形的计算 为了计算4 i 的s m i t h 标准形，我们先来确定e 和c 的s m i t h 标准形。 3 2 3 1 e 的s m i t h 标准形的计算 姐n 1 4j|，i f + l j 一s 一l + l = ( 台三) 另5 么上k = ( s n 4 + s l 。- - + 。s 4 s s n 。_ l + 1 ) 。 + o o 锄 。 o o一州 高校教师在职硕士学位论文 如果n = 2 m + l ，则 & + ，一毛= 哎。+ ，= 吃( k + ，一k ) 一一l + 1 = & 一( s 。一l 一1 ) = s h + ( j 。+ l 一6 s 。) = ( k k 一。) 那么，