（基础数学专业论文）符号矩阵的广义基指数与极大s2ns阵.pdf

同济大学博士学位论文 符号矩阵的广义基指数与极大s 2 s 阵 中文摘要 符号矩阵论是组合矩阵论的一个新兴的研究分支，是近年来在组合数学中 较为活跃的一个研究方向。该理论主要研究矩阵的仅与其符号模式有关的定性 性质。符号矩阵论最早起源于经济学中对某些问题的定性性质的研究，其开创性 工作由诺贝尔奖获得者、经济学家p s a m u e l s o n 作出( 参见文献f i 5 1 ) 。由于符号 矩阵论在经济学中有着重要的应用背景，从而引起了经济学家、数学家及计算 机理论专家的广泛关注。1 9 9 5 年，r a b r u a l d i 与b l s h a d e r 关于符号矩阵论 的专著( ( m a t r i c e so fs i g n s o l v a b l el i n e a rs y s t e m s ) ) ( m 1 ) 的问世极大地推动了符 号矩阵论的发展，它全面系统地总结了符号矩阵论领域的研究成果，给出了许 多新的结论，提出了许多新的研究课题，从而使符号矩阵论成为组合数学新兴 的研究热点之一。 本文的研究内容主要涉及两个方面：一是p o w e r f u l 与非p o w e r f u l 符号矩阵的 幂序列与广义基指数的研究；二是极大铲n s 阵的分支数与非零元个数的研究。 非负矩阵的幂序列一直是组合矩阵论中的一个重要的研究方向f 相关文献参 见 1 】， 4 】，纠， 1 铷，【1 4 】，【2 4 】， 3 4 ， 3 7 ， ! 叫，【4 7 】，【i 蚓，b 5 】，【( ；一】等) 。1 9 9 4 年，z l i ，f h a l l 和c e s c h e n b a c h 在文献：蚓中首次将对非负矩阵的幂序列的研 究推广到符号矩阵。他们引入了“p o w e r f u l ”符号矩阵的概念，继而定义并 研究t p o w e r f u l 符号矩阵的周期与基指数，并给出了一个不可约符号矩阵 为p o w e r f u l 符号矩阵的特征刻划。在符号矩阵的概念被推广到复符号模式矩 阵与r a y 模式矩阵后( 参见文献2 ( 】1 i 【：；：；】， 4 t ， 6 2 1 ，】等) ，z l i ，f h a l l 和j l s t u a r t 在文献f = ；6 1 中进一步将p o w e r f u l 符号矩阵的概念推广至l j p o w e r f u lr a y 模式矩 阵。同时，j s t u a r t 等在文献 1 9 1 ，f ( _ ；1 1 ，f ( j 2 1 ，【6 孔g 4 1 等中研究了与矩阵幂序列 相关的k 一幂等矩阵。 我们注意到，尽管文献f ：j 5 1 中将非负矩阵的幂敛指数的概念推广到了符号 矩阵的基指数，但是基指数的概念仅仅对p o w e r f u l 的符号矩阵有定义。当a 是 非p o w e r f u l 的佗阶符号矩阵时，a 的某一个幂次已经可以不再是符号矩阵，故此 时a 的基指数也就没有定义，再对其进行研究更是无从谈起。 在本文中，我们通过利用文献【3 孔m 】中引入的广义符号集合r = f 0 ，1 ，一1 ， 带) 及相应的广义符号矩阵，将p o w e r f u l 符号矩阵和非p o w e r f u l 符号矩阵( 及其可 能不再是符号矩阵的各个幂次) 统一纳入到广义符号矩阵的范畴之内，从而进 一步将符号矩阵的基指数的概念从p o w e r f u l 符号矩阵推广到了非p o w e r f u l 符号矩 阵( 乃至一般的广义符号矩阵) 的“广义基指数”。在此基础上，我们通过利用图 论、数论和矩阵论的多种方法相结合的技巧，以“违规圈对”和“三同一异”途径 对的关系为基本切入口，对非p o w e r f u l 不可约符号矩阵( 乃至一般的不可约符号 矩阵及不可约广义符号矩阵) 的广义基指数的上界，极矩阵刻划及指数集进行了 有效的研究。得到了如下一些结论： 1 在5 2 ： 中，我们得到了非p o w e r f u l 本原符号矩阵与一般本原符号矩阵的广 义基指数的最好上界，即：当n 5 时，若a 是n 阶( 非p o w e r f u l ) 本原符号矩 i i 中文摘要 阵，贝j j l ( a ) 2 n 2 3 n 十2 ，等号成立当且仅当a 的伴随有向图同构于d 1 ( 如 图2 j 之( a ) ) 同时我们指出了上述矩阵类的广义基指数集合都不是连续的正 整数集，即存在间隙。 2 在j 2 3 中，我们还研究了a 的带号伴随有向图s 的不定号指标r ( ，证明 t d ( s ) + r ( s ) + e x p ( s ) 也是非p o w e r f u l 本原符号矩阵的广义基指数的一个可 达上界，这里d ( s ) 是s 的直径。 3 在鼢4 中，我们得到了非p o w e r f u l 非本原符号矩阵与一般非本原符号矩阵的 广义基指数的上界，即：设a 是n 阶( 非p o w e r f u l ) 不可约符号矩阵，其非本原 指标为p ( 2 ) ，设n = p r + s ，这里r = l 詈j 且0 5 p 一1 ( 【z j 表示不大 于z 的最大整数) ，则l ( a ) p ( 2 ( r 1 ) 2 + r ) + 8 4 在犯1 中，我们还得到了一般不可约符号矩阵和不可约广义符号矩阵的广义 基指数的最好上界，并且指出上述矩阵类的广义基指数集合都不是连续的 正整数集。 5 在r ；2 5 中，我们给出了一般本原符号矩阵的广义基指数达到上界时的极矩阵 刻划，并给出了几个例子来说明( 非p o w e r f u l ) 非本原符号矩阵的广义基指数 的上界也是最好的。 显然，p o w e r f u l 符号矩阵与p o w e r f u l 带号有向图的广义基指数即为基指数。 c ，c o c k a d e s 是一类具有许多良好性质的十分有用的有向图。在文献卜5 1 中关 于p o w e r f u l 符号矩阵f 及p o w e r f u l 带号有向图) 的基指数的研究中，有一节专门研 究了负c ，一c o c k a d e s 的基指数，并给出了一些与之相关的关系式。我们在本文第 三章中对负c 。一c o c k a d e s 的基指数乃至一般p o w e r f u l 符号矩阵的基指数作了进一 步的研究，得到了如下的一些结论： 1 在啦2 中，我们研究了负c 。一c o c k a d e s 的基指数，所做的主要工作如下： ( 1 ) 指出了文献m 5 1 中一个与”基指数等于1 ”相当的结论一般说来不一定 成立。然后，在定理3 2 1 中给出了任意负c 。c o c k a d e 的基指数的一个简明的 计算公式，即f ( d ) = d 一7 + 1 ( 其中d 为负c ，一c o c k a d e ，而d 是d 的直径) 。 ( 2 ) 确定了所有n 阶非平凡的负c 。c o c k a f e s 的基指数所构成的集合就 是 1 ，2 ，n r 】 2 在：；：；中，我们进一步讨论了般的n 阶p o w e r f u l 符号矩阵的基指数集合，证 明了所有佗阶p o w e r f u l 符号矩阵的基指数所构成的集合就等于所有n 阶非负 矩阵的幂敛指数所构成的集合。 本文研究的另一个专题是极大铲n s 阵。 作为符号矩阵论中重要的研究内容之一的s n s 阵与s 2 n s 阵，近年来已得 到比较透彻的研究，也得到了许多经典结论( 参见文献，【1 i ) 】，【li 】，【1 5 】，【l ( q ， 【1 s ，匕乩) 】， 5 2 】， 5 ： 】， 5 4 ， f j 孔】等) 。但是对于极大铲s 阵的研究还远 不如对s s 阵与s 2 n s 阵那样深入而完全。事实上，我们对其知之甚少( 参见文 i i i 同济大学博士学位论文 献【l l 】，【1 6 ， 5 2 ， 6 6 】等) 。在本文第四章中，我们以极大s 2 s 阵的结构和组合 性质为着眼点，主要对其可能的分支数与非零元个数进行了研究。所做的主要 工作如下： 1 对任意的1 k n ，我们给出了恰含k 个完全不可分分支的n 阶极大s 2 n s 阵 存在的充要条件，即：当礼4 时，存在的充要条件是k 岩 2 ，3 】；当仡 5 时，存在的充要条件是k 2 关于极大s 2 n s 阵的完全不可分分支个数，文献 - j l 】和f 1 6 1 中分别构造了 恰含1 个完全不可分分支和恰含佗个完全不可分分支的几阶极大s 2 s 阵的例 子。但迄今为止未见有其他例子或定理说明n 阶极大s 2 n s 阵的完全不可分 分支个数能否是2 - 蛩j n 一1 间的某个给定数k 本文通过引入极大s 2 n s 带号有 向图的概念，用图论方法彻底解决了这一问题。 2 对于n 阶极大s 2 n s 阵的非零元个数构成的集合s ( n ) ，迄今为止所知的结论 只有( 参见 1l 】，2 】) ：当n24 时，5 ( 几) 几， n ( n + 1 ) ) ，3 n 一2 e 5 ( 礼) 和；n ( 佗+ 1 ) s ( n ) 本文通过运用图论方法并给出极大s 2 n s 带号 有向图的两种递归构造方法对集合s ( n ) 进行了细致的研究，完全确定了 除2 仡+ 1 n 3 n 一4 间的一段外的任一正整数是否在集合s ) 之中。 关键词：符号矩阵不可约p o w e r f u l 基指数极大s 2 n s 阵有向图 i v a b s t r a c t t h eg e n e r a l i z e db a s i so fs i g np a t t e r nm a t r i c e s a n dm a x i m a ls 2 n sm a t r i c e s a b s t r a c t s i g np a t t e r nm a t r i xt h e o r yi san e wb r a n c ho fc o m b i n a t o r i a lm a t r i xt h e o l ， which i n v o l v e st h es t u d yo ft h ep r o p e r t i e so fm a t r i c e st h a td e p e n do n l yo nt h e s i g np a t t e r n so ft h em a t r i c e s t h es u b j e c t ，s t a r t e db yt h en o b e l i s tp s a m u e l s o n w h oi sa ne c o n o m i s t i su b u a l l yc o n s i d e r e dt oh a v eo r i g i n a t e dw i t ht h ed i s c u s s i o n o n “q u a l i t a t i v ep r o p e r t i e s ”o fs o m ep r o b l e m si ne c o n o m i c s ( s e e 【4 5 1 ) b e c a u s e o fi t sg r e a ti m p o r t a n c ei ne c o n o m i c s i th a sb e e np a i dw i d ea t t e n t i o nb ym a n y r e s e a r c h e r si n c l u d i n ge c o n o m i s t s ，m a t h e m a t i c i a n sa n dt h e o r e t i c a lc o m p u t e rs c i e n t i s t s i n1 9 9 5 r a b r u a l d ia n db l s h a d e r sb o o k m a t r i c e so fs i g n s o l v a b l e l i n e a rs y s t e m s ) ) ( 【1 6 】) w a sp u b l i s h e d ，w h i c hi st h ef i r s tm o n o g r a p ho ns i g np a t t e r nm a t r i xt h e o r y i nt h i sb o o k ，t h e ys y s t e m a t i c a l l ys u m m a r i z e dt h er e s u l t so n t h es u bi e c ta n dg a v em a n yn e wr e s u l t s i tm a k e ss i g np a t t e r nm a t r i xt h e o r yb e i n g a na c t i v er e s e a r c ha r e ao fc o m b i n a t o r i c s i nt h i sp a p e r ，t w os p e c i a lt o p i c so ns i g np a t t e r nm a t r i xt h e o r yh a v eb e e n s t u d i e d o n ei st h es t u d yo nt h es e q u e n c eo fp o w e r sa n dt h eg e n e r a l i z e db a s i so f p o w e r f u la n dn o n - p o w e r f u ls i g np a t t e r nm a t r i c e s ；t h eo t h e ri st h es t u d yo nt h e n u m b e r so fc o n s t i t u t e sa n dn o n z e r oe n t r i e so fm a x i m a ls 2nsm a t r i c e s t h er e s e a r c ho nt h es e q u e n c eo fp o w e r so fn o n n e g a t i v em a t r i c e si sa ni m p o r - t a n tp a r to fc o m b i n a t o r i a lm a t r i xt h e o r y ( s e e 【l 】，h 5 】，】，【14 ， 2 4 ， 3 4 】，阻】， 阻】，1 8 1 ， 5 孔【67 】) i n1 9 9 4 ，z l i ，f h a l la n dc e s c h e n b a c hg e n e r a l i z e d t h er e s e a r c ho ft h es e q u e n c eo fp o w e r so fn o n n e g a t i v em a t r i c e st os i g np a t t e r n m a t r i c e si nf ：3 5 1 t h e yi n t r o d u c e dt h ec o n c e p to fp o w e r f u ls i g np a t t e r nm a t r i c e s a n ds t u d i e dt h ep e r i o d sa n db a s i so fp o w e r f u ls i g np a t t e r nm a t r i c e s t h e ya l s o g a v eac h a r a c t e r i z a t i o no fa ni r r e d u c i b l es i g np a t t e r nm a t r i xb e i n gap o w e r f u ls i g n p a t t e r nm a t r i x a f t e rt h ec o n c e p to fs i g np a t t e r nm a t r i c e sw a ne x t e n d e dt oc o r n - p l e xs i g np a t t e r nm a t r i c e sa n dr a yp a t t e r nm a t r i c e s ( s e e 2 ( ) 】，】，【4l 】，( 6 乳峭1 ) ， z l i f h a ua n dj l s t u a r te t c g e n e r a l i z e dp o w e r f u ls i g np a t t e r nm a t r i c e st o p o w e r f u lr a yp a t t e r nm a t r i c e si nm 1 i na d d i t i o n ，j s t u a r te t c s t u d i e dq u e s t i o n s o n 七一p o t e n tm a t r i c e s ( i n 【1 9 】，_ l 】，陋】，瞰】，【( j 4 】) w h i c hh a v ec l o s er e l a t i o n s h i p w i t ht h es e q u e n c eo fp o w e r so fm a t r i c e s w en o t i c et h a t ，a l t h o u g ht h ec o n c e p to fi n d i c e so fc o n v e r g e n c eo fn o n n e g a t i v e m a t r i c e sw a se x t e n d e dt ot h ec o n c e p to fb a s i so fs i g np a t t e r nm a t r i c e si n3 5i ，b u t t h ed e f i n i t i o no fb a s i sw a so n l ym a d ef o rp o w e r f u ls i g np a t t e r nm a t r i c e s i fa i sa n o n - p o w e r f u ls i g np a t t e r nm a t r i x ，t h e ns o m ep o w e ro fam a y n ol o n g e rb eas i g n p a t t e r nm a t r i x ，s ot h eb a s eo fa i sn o td e f i n e d ，w h i c hi si m p o s s i b l et ob es t u d i e d i nt h i sp a p e r ，w eu s et h eg e n e r a l i z e ds i g ns e tf = l ，一1 ，0 ，挣 a n dt h e c o r r e s p o n d i n gg e n e r a l i z e ds i g np a t t e r nm a t r i c e s ( i n t r o d u c e di n 陋】a n dm 】) t o c o m b i n ep o w e r f u la n dn o n p o w e r f u ls i g np a t t e r nm a t r i c e s ( t o g e t h e rw i t ht h e i r v 同济大学博士学位论文 p o w e m ) i n t ot h em o r eg e n e r a lc l a s so fm a t r i c e s - g e n e r a l i z e ds i g np a t t e r nm a t r i c e s ， t h u sf u r t h e re x t e n dt h ec o n c e p to fb a s i sf o rp o w e r f u ls i g np a t t e r nm a t r i c e st ot h e m o r eg e n e r a lc o n c e p to f “g e n e r a l i z e db a s i s ”f o rn o n p o w e r f u ls i g np a t t e r nm a t r i c e s a n d ( m o r eg e n e r a l l y ) g e n e r a l i z e ds i g np a t t e r nm a t r i c e s b a s e do nt h i sa n db y u s i n gt h ec o m b i n a t i o no fg r a p ht h e o r e t i c a lm e t h o d s ，n u m b e rt h e o r e t i c a lm e t h o d s a n dm a t r i xt h e o r e t i c a lm e t h o d s w eu s et h er e l a t i o n s h i p sb e t w e e n “d i s t i n g u i s h e d c y c l ep a i r ”a n ds s s dw a l k st os t u d yt h eu p p e rb o u n d s ，e x t r e m a lm a t r i c e sa n d b a s i ss e to ft h eg e n e r a l i z e db a s i sf o ri r r e d u c i b l en o n - p o w e r f u ls i g np a t t e r nm a t r i c e s ( a n dm o r eg e n e r a l l yi r r e d u c i b l eg e n e r a l i z e ds i g np a t t e r nm a t r i c e s ) ，a n do b t a i nt h e f o l l o w i n gr e s u l t s ： 1 i i l 2 3 ，w eo b t a i nt h es h a r pu p p e rb o u n d s ，t o g e t h e rw i t hc o m p l e t ec h a r a c t e r - i z a t i o no ft h ee q u a l i t yc a s e s ，o ft h eg e n e r a l i z e db a s i sf o rb o t hp r i m i t i v en o n - p o w e r f u ls l g np a t t e r nm a t r r i c e sa n dp r i m i t i v es x g np a t t e r nm a t r i c e s 1 、j a m e l y , l e tab eap r i m i t i v e ( n o n - p o w e r f u l ) s i g np a t t e r nm a t r i xo fo r d e rn 5 ，t h e n l ( a 1 2 n 2 3 n + 2 ，a n de q u a l i t yh o l d si fa n do n l yi ft h ea s s o c i a t e dd i g r a p h d ( a ) o fa i si s o m o r p h i ct od l ( s e e ( a ) o ff i g 2 1 ) f u r t h e r m o r e ，w es h o wt h a t t h e r ee x i s t “g a p s ”i nt h eg e n e r a l i z e db a s i ss e to ft h ec l a s s e so fs u c hm a t r i c e s 2 i n 珏3 ，w es t u d yt h e “a m b i g u o u si n d e x ”r ( s ) o f t h ea s s o c i a t e ds i g n e dd i g r a p h so fa ，a n dp r o v et h a td ( s ) + r ( s ) + e x p ( s ) i sa l s ot h es h a r pu p p e rb o u n do f t h eg e n e r a l i z e db a s i sf o rp r i m i t i v en o n - p o w e r f u ls i g np a t t e r nm a t r i c e s ，w h e r e d ( s ) i st h ed i a m e t e ro ft h ed i g r a p hs 4 i n 蛇4 ，w eo b t a i nt h eu p p e rb o u n do ft h eg e n e r a l i z e db a s i sf o rb o t hi m - p r i m i t i v en o n - p o w e r f u ls i g np a t t e r nm a t r i c e sa n di m p r i m i t i v es i g np a t t e r n m a t r i c e s n a m e l y , l e ta b ea ni r r e d u c i b l e ( n o n p o w e r f u l ) s i g np a t t e r nm a t r i x o fo r d e r 几w i t hi n d e xo fi m p r i m i t i v i t yp 2 ，a n dl e tn = p r + 8 ，w h e r e 7 = 【罟ja n d0 s p 一1 ( 【z ji st h el a r g e s ti n t e g e rn o te x c e e d i n gz ) ，t h e n l ( a ) p ( 2 ( r 1 ) 2 + r ) + 8 i n 犯4 ，w ea l s oo b t a i nt h es h a r pu p p e rb o u n d s ，t o g e t h e rw i t hc o m p l e t ec h a r - a c t e r i z a t i o no ft h ee q u a l i t yc a s e s ，o ft h eg e n e r a l i z e db a s i sf o rb o t hi r r e d u c i b l e s i g np a t t e r nm a t r i c e sa n di r r e d u c i b l eg e n e r a l i z e ds i g np a t t e r nm a t r i c e s ，a n d w es h o wt h a tt h e r ee x i s t “g a p s i nt h eg e n e r a l i z e db a s i ss e to ft h ec l a s s e so f s u c hm a t r i c e s i n 2 5 ，w eg i v et h ec h a r a c t e r i z a t i o no ft h ee x t r e m em a t r i c e so fp r i m i t i v e s i g np a t t e r nm a t r i c e s ，a n dw eg i v es e v e r a le x a m p l e st od e p i c tt h a tt h eu p p e r b o u n do ft h eg e n e r a l i z e db a s i so ft h ei m p r i m i t i v e ( n o n p o w e r f u l ) m a t r i c e s ( i n 2 4 ) a r es h a r p c l e a r l y ，t h eg e n e r a l i z e db a s eo fap o w e r f u ls i g np a t t e r nm a t r i xo rap o w e r f u l s i g n e dd i g r a p hi s t h eb a s eo ft h em a t r i xo rt h ed i g r a p h v i a b s t r a c t c , - c o c k a d e sa r eac l a s so fu s e f u ld i g r a p h sw h i c hh a v eq u i t em a n yn i c ep r o p e r - t i e s i nt h es t u d yo ft h eg e n e r a l i z e db a s i so fp o w e r f u ls i g np a t t e r nm a t r i c e s ( a n d p o w e r f u ls i g n e dd i g r a p h s ) i n 1 ，t h e r ei saw h o l es e c t i o nw h i c hs t u d yt h eb a s i so f t h en e g a t i v ec r - c o c k a d e sw h e r es o m ec o r r e s p o n d i n gr e l a t i o n si n v o l v i n gt h eb a s i s w e r eo b t a l n e d i nc h a p t e r3o ft h i sp a p e rw ef u r t h e rs t u d yt h eb a s i so ft h en e g - a t i v ec r c o c k a d e s ( a n dt h eb a s i sf o rg e n e r a lp o w e r f u ls i g np a t t e r nm a t r i c e s ) a n d o b t a i nt h ef o l l o w i n gr e s u l t s 1 i n ! i 3 2 ，w es t u d yt h eb a s i so fn e g a t i v ec r c o c k a d e s t h em a i nw o r kw eh a v e d o n ea sf o l l o w s ( 1 ) w e c l a i mt h a tt h er e s u l ti n 【3 5 】w h i c hi se q u i v a l e n tt o “t h eb a s i sa r e e q u a lt o1 ”i sn o ta l w a y sr i g h t t h e nw eg i v eas i m p l yf o r m u l af o rt h eb a s eo f e a c hn e g a t i v ec r _ c o c k a d ei nt h e o r e m ：；2 1 ，n a m e l y , f ( d ) = d r + 1 ( w h e r e d i san e g a t i v ec r c o c k a d ea n ddi st h ed i a m e t e ro fd ) ( 2 ) w e d e s c r i b et h eb a s i ss e to ft h ec l a s so fa l ln e g a t i v ec r - c o c k a d e sw i t h o r d e rni s l ，2 ，r , 一r 】 2 i n 姆j ，w et a k eaf u r t h e rs t u d yo np o w e r f u ls i g np a t t e r nm a t r i c e so fo r d e r n a n dw ed e t e r m i n et h eb a s i ss e to ft h ec l a s so fa l lt h ep o w e r f u ls i g np a t t e r nm a t r i c e so fo r d e rnb ys h o w i n gt h a ti ti se q u a lt ot h es e to fi n d i c e so f c o n v e r g e n c eo ft h ec l a s so fa l lt h en o n n e g a t i v em a t r i c e so fo r d e rn t h ea n o t h e rt o p i co ft h i sp a p e ri st h es t u d yo fm a x i m a l 铲n sm a t r i c e s snsm a t r i c e sa n d 铲nsm a t r i c e sa x ev e r y 、m p o r t a n tc l a s s e s 、ns i g np a t t e r n m a t r i xt h e o r y t h e yh a v eb e e ns t u d i e dt h o r o u g h l ya n dan u m b e ro fi m p o r t a n t r e s u l t sa r eo b t a i n e di n 隙【l 【) 】，【11 】，1 ，】， 1 8 】， 2 札眇1 ， 5 2 1 ，阳】，卜4 】，【t ；5 1 ， 阶】b u ti ng e n e r a l l ys p e a k i n g ，t h es t u d yo fm a x i m a ls 2 sm a t r i c e si sn o ts o t h o r o u g ha st h es t u d yo fs n sm a t r i c e sa n ds 2 n sm a t r i c e s i n d e e d ，w h a tw e h a v ek n o w na b o u tm a x i m a ls 2 sm a t r i c e sa r ev e r yl i t t l e ( s e e 】，【l g 】， 5 2 】，【6 g 】) i nc h a p t e r4o ft h i sp a p e r ，w es t a r to u rw o r ko nt h es t r u c t u r ea n dc o m b i n a t o r i a l p r o p e r t i e so fm a x i m a l 铲n sm a t r i c e sa n ds t u d yt h en u m b e r so fc o n s t i t u t e sa n d n o n z e r oe n t r i e so ft h ec l a s so fs u c hm a t r i c e s t h em a i nw o r kw eh a v ed o n ea r ea s b e l o w 1 f o re a c hi n t e g e rkw i t h1 k 佗，w eo b t a i nt h en e c e s s a r ya n ds u 伍c i e n t c o n d i t i o n sf o rt h ee x i s t e n c eo fm a x i m a ls 2 n sm a t r i c e so fo r d e rnw i t he x a c t l y k ( f u l l yi n d e c o m p o s a b l e ) c o n s t i t u t e s n a m e l y ，i f 礼4 ，t h e nt h ec o n d i t i o ni s 七g 2 ，3 ) a n di fn 5 ，t h e nt h ec o n d i t i o ni sk 2 c o n c e r n i n gt h en u m b e r so fc o n s t i t u t e so fm a x i m a l 铲n sm a t r i c e s t h e e x a m p l e so fk = 1c o n s t i t u t ea n dk = 佗c o n s t i t u t e sw e r ec o n s t r u c t e di n l l a n df “j 1 b u tu pt on o w ，w ed on o ts e ee x a m p l e so rr e s u l t ss h o w i n gw h e t h e r t h e r ea r em a x i m a ls 2 n sm a t r i c e so fo r d e r 几w h o s en u m b e ro fc o n s t i t u t e sc a n b es o m eg i v e ni n t e g e rkb e t w e e n2a n dn 一1 i nt h i sp a p e r w ec o m p l e t e l y i 同济大学博士学位论文 s o l v et h i sp r o b l e mb yi n t r o d u c i n gt h em a x i m a l 擎nss i g n e dd i g r a p h sa n d u s i n gt h eg r a p ht h e o r e t i c a lm e t h o d s 2 f o rt h es e ts ( n ) o ft h en u m b e r so fn o n z e r oe n t r i e so fm a x i m a l 铲n s m a t r i c e s t h eo n l yr e s u l t sk n o w nu pt on o wa r e ( 【l l 】，【5 q ) ：s ( n ) 佗， 佗( 佗+ 1 ) ， 3 n 一2 s ( n ) a n d ；n ( 他+ 1 ) s ( n ) b yu s i n gg r a p ht h e o r e t i c a lm 。e t h o d s ，w e g i v et w or e c u r s i v ec o n s t r u c t i o n so fm a x i m a l 铲n ss i g n e dd i g r a p h st os t u d y t h es e ts ( 佗) f o re a c hi n t e g e r 尼g ( 2 佗十1 ，3 礼一4 】，w ed e t e r m i n ew h e t h e r o rn o tki si nt h es e t5 ( 佗) k e y w o r d s ：s i g n ；m a t r i x ；i r r e d u c i b l e ；p o w e r f u l ；b a s e ；m a x i m a l 铲nsm a r t r i c e s ；d i g r a p h i i 学位论文独创性声明 本人声明，所呈交的学位论文系在导师指导下本人独立完成的研究成果。 文中依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法 律意义上已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申 请的论文或成果。 本人如违反上述声明，愿意承担以下责任和后果： 1 交回学校授予的学位证书； 2 学校可在相关媒体上对作者本人的行为进行通报； 3 本人按照学校规定的方式，对因不当取得学位给学校造成的名誉损害， 进行公开道歉。 4 本人负责因论文成果不实产生的法律纠纷。 论文作者签名： 孟。兰! l 錾 日期： 迦翌丝年卫月卫日 第一章