（运筹学与控制论专业论文）bounds+on+the+kth+multig+base+index+of+primitive+irreducible+nearly+reducible+sign+pattern+matrices.pdf

摘要 文3 1 中，李宗山等把非负矩阵的基和周期的概念推广至l j p o w e r f u l 符 号矩阵然后，文| 4 中沼口嘉裕和尤利华又把p o w e r f u l 符号矩阵基的 概念推广到广义n o n p o w e r f u l 不可约符号矩阵在本文中我们研 究了广义n o n p o w e r f u l 不可约符号矩阵和几乎可约符号矩阵的广 义重基指数，得到了广义不可约符号矩阵的广义k 重基指数的最好 上界，以及广义几乎可约符号矩阵广义a 重基指数的上界和某些达 到上界的矩阵并由此得到了在广义k 重基指数集中存在缺数段 界 关键词：广义k 重基指数；矩阵；符号型；不可约；几乎可约；圈 a b s t r a e t i n1 3 1 ：z s l i ，f h 以la n dc ，e s c h e n b a s he x t e n d e dt h ec o n c e p t o ft h eb a s ea n dp e r i o df r o mn o n n e g a t i v em a t r i c e st op o w e r f u ls i g n p a t t e rm a t r i c e s t h e n ，i n1 4 i ，j y s h a oa n dl h y o ue x t e n d e dt h e c o n c e p t so ft h eb a s ef r o mp o w e r f u ls i g np a t t e r nm a t r i c e st on o n p o w e r f u li r r e d u c i b l eg e n e r a f i z e ds i g np a t t e r nm a t r i c e s i nt h i sp a - p e rw em a i n l ys t u d yt h ek t hm u l t i gb a s ei n d e xf o rn o n - p o w e r f u l p r i m i t i v ei 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 sa n dp r i m i r i v en e a r l yr 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 w eo b t a i n s 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 e e q u a l i t yc a s e so ft h ek t hm u l t i gb a s ei n d e xf o rp r i m i t i v ei r r e d u c i b l e g e n e r a n z e as i g np a t t e r nm a t r i c e sa n dp r i m i t i v e n e a r l yr 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 w ea l s os h o wt h a tt h e r e e x i s t “g a p s ” i nt h ek t hm u l t i - gb a s ei n d e xs e to ft h ed a s s e so fs u c hm a t r i c e s k e y w o r d s ：k t hm u l t i gb a s ei n d e x ；m a t r i x ；s i g np a t t e r n i r r e d u c i b l e ；n e a r l yr e d u c i b l e ；c y c l e ；b o u n d s e c t i o n1 i n t r o d u c t i o n t h e s i g no far e a ln u m b e ra d e n o t e db y8 9 n a i sd e f i n e dt ob e 1 一1o r0 ，a c c o r d i n g t oa 0 ，a a 2 t 盘 0a n d g c d ( a l ，a 2 ，) = l ，t h e n ( s e e 【i 2 ) 西( ，a k ) 虹掣 i ti sa l s ow e l lk n o w n t h a t i f ( a ，b ) = 1 ，t h e n 西( n ，b ) = ( a 1 ) ( b 1 ) l e t b eav e r t e xo fa p r i m i t i v ed i g r a p hd t h e v e r t e xe x p o n e n t o fv ，d e n o t e db ye x p d ( v ) ，i sd e f i n e dt ob et h el e a s tp o s i t i v ei n t e g e r 女s u c ht h a tf o re a c hv e r t e x 让i nd t h e r ei saw a l ko fl e n g t h f r o m 口t o 让 l e tr = 1 1 ，z r ) b eas e to fc y c l el e n g t h si nap r i m i t i v e d i g r a p hd s u c ht h a t9 c d ( 1 l ，tt - ，0 ) = 1 f o re a c hv e r t e xza n d v e r t e xyi nd ，l e td ( x ，g ) b et h ed i s t a n c ef r o mxt oga n dl e td n ( z ，y ) b et h el e n g t ho ft h es h o r t e s tw a l kf r o mzt oyw h i c hm e e t sa tl e a s t o n e c y c l eo f l e n g t hi i f o ri l ，一，rl e t 西r = 西( j 1 ，一，0 ) b e t h e f r o b e n i u sn u m b e r w eh a v ek n o w nt h e f o l l o w i n gu p p e rb o u n d s ( j 2 ) e x p ( d ) 墨垂r + m a x 。癌e v ( d ) d r ：y ) e x p d ( v ) 5 中r + m a x “e v ( o ) d n ( v ，“) ( 2 4 ) ( 2 5 ) s e c t i o n 3 t h e p r i m i t i v e n o n - p o w e r f u ls i g np a t e e r nm a t r l c e s w ew i l l i n t r o d u c et h e f o l l o w i n gd e f t n i t i o n sa n dp r o p e r t i e sw h i c h w e r ee s t a b l i s h e di n 【4 d e f i n i t i o n3 1l e tsb ea n o n - p o w e r f u ls i g n e dd i g r a p h t h e nt h e a m b i g u o u si n d e xo fs d e n o t e db yr ( s ) ，i sd e f i n e dt ob et h el e a s t i n t e g e rrs u c ht h a tt h e r ei sap a i ro fs s s dw a l k so fl e n g t hri ns a nm nm a t r i xw i t ha l le n t r i e se q u a lt o1i sd e n o t e d b yj m n a nmxng e n e r a l i z e ds i g np a t t e r nm a t r i xw i t ha e n t r i e se q u a lt o “妒i sd e n o t e db y 榉厶m p r o p o s i t i n r l3 1 l e tsb eap r i m i t i v en o n - p o w e r f u ls i g n e dd i g r a p h ，啊a n dw 2b eap a i ro fs s s dw a l k so fl e n g t hr u 。f r o m 5 v e r t e xu t ov e r t e xu t h e n w eh a v e ( 1 ) z s ( k ) sm i n d ( s ) ，k l + h ，。+ e x p s ( 口) ； ( 2 ) z s ( k ) m i n d ( s ) ，k 一1 ) + r ( s ) + e x p ( s ) ， w h e r ed ( s ) i st h ed i a m e t e ro ft h ed i g r a p hs p r o o f ( 1 ) l e t 口b ea n y v e r t e xo fss i n c esi sp r i m i t i v e ，t h e nsi s s t r o n g l yc o n n e c t e d w ec a nt a k ex 一 x l ，0 2 ，o r f = “) j ，w h e r e d ( x i ，“) m i n d ( s ) ，k 一1 ) 0 = 1 ，2 ，) l e t 只b eas h o r t e s tp a t hi n8f r o mx lt ouw i t hl e n g t hd ( z 。，札) ，c l e a r l y d ( x ；，“) s m i n d ( s ) ，k 一1 ) ，s oe x p s 如) + ( m m d ( s ) ，k 一1 一d ( x ，珏) ) e x p s ( v ) a n dt h u st h e r ee x i s t saw a l kq ，f r o mvt oyw i t hl e n g t h e x p s ( v ) + m i n d ( s ) ，k 一1 ) 一d ( x i ，“) t h e r e f o r e 只+ 啊+ q 。a n d 只+ + q i ，( i = 1 ，2 ，一，k ) b eap a i ro fs s s dw a l k so f l e n g t h m i n d ( s ) ，k 一1 ) ) + r 。+ e x p sv ) f r o m 孔t oy s o ( 1 ) h o l d s ( 2 ) c l e a r l y ，。sr ( 习，e x p s ( 口) se x p ( s ) f r o m ( 1 ) w eo b t a i n e d l s ( k ) m i n d ( s ) ，一1 + r ( s ) + e ) p ( s ) _ n o ww ec o n s i d e rt h ef o l l o w i n gt w o d i g r a p h s l e td 1a n dd 2b eap r i m i t i v ed i g r a p ha sf o l l o w s ： y ( d 。) = 1 ，2 ， 一1 ，2 ) ； e ( d i ) = ( 1 ，2 ) ，( 2 ，3 ) ，( 3 ，4 ) ，一，( 礼一1 ，1 ) ，( n l ，n ) ，( n ，1 ) ) ； e ( d 2 ) = ( 1 ，2 ) ，( 2 ，3 ) ，( 3 ，4 ) ，一，( n 一1 ，1 ) ，( n l ，n ) ，( ，1 ) ( n ，2 ) ) t h e ni ti sw e l l - k n o w nf r o mt h et h e o r yo f n o n n e g a t i v ep r i m i t i v eh l a - t r i c e s ( 【8 】) t h a t e x p ( d 1 ) = ( 一1 ) 2 + 1 ，e x p ( d 2 ) = ( n 1 ) 2 f 3 1 ) a n d e x p ( d ) 茎( n 一1 ) 2 + 1 ，f o r a l lp r i m i t i v ed i g r a p h so fo r d e rn ( 3 2 ) l e m m a3 2l e ts 1b ean o n - p o w e r f u ls i g n e dd i g r a p ho fo r d e rn w i t hd i 蠲i t s u n d e r l y i n gd i g r a p h t h e nw eh a v e i s 】( k ) = 2 ( n 一1 ) 2 + p r o o f , f i r s tw es h o wt h a tt h e r ei sap a i ro fs s s dw a l k so f l e n g t h 一1 ) 2 + 1f r o mv e t e xn 一1t ov e r t e x1 f o rt h j sp u r p o s e ， l e tq la n dq 2b et h ep a t ho f l e n g t h s1a n d2f r o mt h e v e t e xn 一1 t ov e r t e x1 l e t ( _ 一1a n dc 毛b et h ec y c l e so f l e n g t h s 礼一1a n d 扎 r e s p e c t i v e l y ，t a k e 2 q i + 如一1 ) g “= q 2 + 如一2 ) g l e tpb et h eu n i q u ep a t hf r o mv e r t e x 礼t ov e r t e xn 一1 t h e n w 1 + p n g 一1 ，+ p 一( n 一1 ) g s i n c e 岛i st h en o n - p o w e r f u la n dg 一1a n dg a r et h eo u l yt w o c y c l e so fs 1 ，g 一1a n d 瓯m u s tb ead i s t i n g u i s h e dc y c l ep 缸r s o 6 n g 一】a n d ( n 一1 ) g h a v ed i f f e r e n ts i g n s h e n c e a n d h a v e d i f f e r e n ts i g n s a n ds oi sap m r o fs s s dw a l k so fl e n g t h ( n 一1 ) 2 + 1 w eh a v er ( n 一1 ，1 ) 曼( n 一1 ) 2 十1 b y ( 2 5 ) ，w eh a v e e x p d ，( 1 ) 圣( 扎，”一+ 。m y a ( d x ，) d e ( 1 ，u ) = ( n 一1 ) ( n 一2 ) + ( n 一1 ) = m 1 ) 2 s ob yt h er e s u l t ( 1 ) o fp r o p o s i t i o n3 1 ，w eh a v e l s 。( 自) sm i n d ( 岛) ，k 一1 十r ( s ) + e x p s 。( 1 j s ( k 一1 ) + r ( n 一1 ，1 ) + e x ps 1 ( 1 ) ( k 一1 ) 十( n 一1 ) 2 + l + ( n 一1 ) 2 = 2 ( 扎一1 ) 2 + k n e x tl e tv e r t e xs e t y jw n 一1 ，礼一2 ，：礼一七+ 1 血2 ， 一 iv k21 o b v i o u s l y ，l x l = n 一+ 1 t h e n w e w i l ls h o w t h a t f o ra n y v e r t e x “x ，t h e r ei si i op a i ro fs s s dw a l k sf r o mut oww i t hl e n g t ho f l = 2 ( n 一1 ) 2 + k 1 w h e r e t h e r e i su n i q u ep a t h p f r o m “t o v w i t h l e n g t hk l e tw 1a n d b ea n yt w o w a l k s o f l e n g t h2 ( n - 1 1 2 + k - 1 f r o m u t o 口t h e ne a c h m ( i = 1 ，2 ) i sau n i o n o f p a t h pa n ds e v e r a l c y c l e sg a n ds e v e r a lc y c l e sc ：一1 t h e nw eh a v e 1 = 啦n + b i ( n 一1 ) + k ，啦三0 ，坟三0 ，i = 1 ，2 s o ( a 2 一a 1 ) n = ( b l b 2 ) ( n 一1 ) w r i t eb l b 2 = n z t h e na 2 一a l = f 扎一1 ) x w ec l a i m t h a tx = 0 i f 嚣l ，t h e nb l 札，s o l = 吼n + ( b l 一他) ( 札一1 ) + n 2 一n + 惫 w h i c hi m p l i e st h a t 圣( n ，n 一1 ) 一1 = ( n 一1 ) ( n 2 ) 一1 = 扎2 3 n + 1 = 2 ( n 1 ) 2 + ( k 1 ) 一n 2 + n 一 = 2 一扎2 + 札一詹 = a l n + ( b l 扎) ( 扎一1 ) s ( n l ，札) ， c o n t r a d i c t i n gt h ed e f i n i t i o no ft h ep r o b e n i u sn u m b e r 西( n j 一1 ) s i m i l a r l yw e c a n g e tac o n t r a d i c t i o nj fx 一1 t h u sw eh a v ez = 0 ， s oa l = a 2 ，b l = b 2a n dt h u ss g n 阢= s g n w 2 t h i s a r g u m e n t , s h o w s t h a t l s ，( k ) 2 ( n 1 ) 2 十k c o m b i n i n g t h ea b o v et w oi n e q u a l i t i e sw eo b t a i nt s l ( ) = 2 ( 札一 1 ) 2 十k _ o b v i o u s l y ，l s l ( n ) = 2 ( n 1 ) 2 + n = ? ( 岛) w h i c hi s t h es a i n e r e s u l ti n 【4 7 l e m m a3 3 l e t 岛b ean o n p o w e r f u ls i g n e dd i g r a p ho fo r d e r n 兰3w i t hd 28 si t su n d e r b d n gd i g r a p ht h e nw e h a v e ： ( 1 ) i ft h e ( o n l y ) t w oc y c l e so fl e n g t h n 一1o f 岛h a v ed i f f e r e n ts i g n s ， t h e nl s 2 ( k ) s ( n 一1 ) 2 + 女+ 1 ( 2 ) i f t h e t w oc y c l e so f l e n g t hn 一1o f & h a v e t h es a m es i g n t h e n w eh a v el s 2 ( 纠一( n 一1 ) 2 + 女一1 p r o o f ( 1 ) l e t q i 一( n 一1 ，1 ) + ( 1 ，2 ) a n d q 2 = ( 礼一1 ，扎) + ( n ，2 ) b e t w o p a t h so f l e n g t h2 f r o m 一1 t o2 i f t h e t w oc y e j e so f 嚣一1 o f 岛h a v ed i f f e r e n ts i g n s ，t h e nw eh a v es g n q l = - s g n q 2 t h e n c l e a r l yr ( ) s2 t h u sw e h a v e l s 2 ( k ) m i n d ( s 2 ) ，k 一1 ) + r ( s j ) + e x p ( d 2 ) k 一1 + 2 十( n 一1 ) 2 = ( n 一1 ) 2 + k + 1 ( 2 ) i ft h et w oc y c l e so fl e n g t hn 一1i n 岛h a v et h es f j n es i g n t h e n s g n q l = s g n q 2 a l s o e a c hc y c l eo fl e n g t hn 一1a n dc y c l eo fl e n g t h 礼w i l lf o r ma d i s t i n g u i s h e dc y c l ep a i r s i n c e 岛i sn o n p o w e r m la n d t h eo n l yt h r e ec y c l e so fs 2a r et h et w oc y c l e so fl e n g t hn 一1a n d o n ec y c l eo fl e n 昏h ，s o j g k la n df n 一1 ) w i l lh o ed i f f e r e n t s i g n s n o wl e t 尸1 = ( 礼，1 ) b et h eu n i q u ep a t hf r o mnt o 1a n d p 2 一( m2 ) + q + ( n 一1 ，1 ) b e t h ep a t ho f l e n g t h n 一2 f r o m n t o1 ， w h e r e o i s t h eu n i q u ep a t h f r o m2 t o 凡一1a n d l e t = p 1 + ( n 一2 ) g ，= p 2 + ( n 一2 ) g _ 1 t h e ni i = i v 矿2 l = 1 + n ( n 一2 ) 一( n 一1 ) 2 l e tp = ( 1 ，2 ) 十q + ( 礼