（计算机应用技术专业论文）几类符号模式矩阵的研究.pdf

中文摘要 几类符号模式矩阵的研究 摘要 符号模式矩阵是组合矩阵中当前国际上十分活跃的一个研究课题，其重要原因之一 是它在经济学，生物学，化学，社会学，计算机科学等众多学科中具有广泛的实际应用 背景。符号模式矩阵的研究起源于研究线性动力系统的符号可解性和符号稳定性，是由 诺贝尔经济学奖获得者p _ a s a m u e l s o n 在他的著作( ( f o u n d a t i o n s o f e c o n o m i c a n a l y s i s ) ) 中首先提出的。r a b m 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 r s y s t e m s 总结了到1 9 9 5 年为止在符号模式矩阵研究中所取得的重要成果，将本课题 的研究推向了一个新的层面，本文专注于对一些特殊类型的符号模式矩阵进行了研究。 第一章概述符号模式矩阵研究的历史，介绍一些基本知识，提出本文所作的工作。 第二章讨论符号模式矩阵的惯量和谱。首先较为详细地讨论了一类特殊的符号模 式，介绍了它在惯量任意模式和谱任意模式中的研究进展；其次给出了一般反对称符号 模式a 的惯量，得到了4 惯量的刻划；最后介绍了一类谱任意的稀疏符号模式。 第三章研究平方非正矩阵的负元个数，系统总结了已有结论，并证明了当a 是阶数 n 4 的实矩阵时，r d e m a r r 和a s t e g e r 提出的猜想( b ) 是成立的。 第四章给出了蕴含正交矩阵的一种构造方法，进而给出蕴含正交矩阵的一些充分或 必要条件。 关键词：符号模式矩阵：惯量任意；谱任意；蕴含正交 英文摘要 t h es t u d yo fs o m e s i g np a t t e r nm a t r i c e s a b s t r a c t s i g np a t t e mm a t r i xi sav e r ya c t i v er e s e a r c ht o p i ci nc o m b i n a t o r i a lm a t r i xt h e o r y ，a n dt h e o r i g i no fw h i c hl i e si nt h es t u d yo fs i g n s o l v a b i l i t yo fl i n e a rs y s t e m i tw a s f i r s tp r o p o s e db y p a s a m u e l s o ni n ( ( f o u n d a t i o n so fe c o n o m i ca n a l y s i s ) ) ，a n dm a i nr e s u l t sr e l a t e di tb e f o r e 19 9 5w a ss u m m a r i z e di n ( ( m a t r i c e so fs i g n s o l v a b i l i t yo fl i n e a rs y s t e m ) ) b yr a b m a l d ia n d b l s h a d e r ，i nt h i st h e s i s ，w ef o c u s e s0 nd i s c u s s i o no fs o m es p e c i a ls i g np a t t e r nm a t r i c e s i nc h a p t e r1 , w ei n t r o d u c et h eh i s t o r yo fd e v e l o p m e n to nt h es i g np a t t e mm a t r i c e s ，s o m e m e t h o di no u rp a p e rh a du s e d ，a n do u rr e s e a r c hp r o b l e m sa n dm a i nr e s u l t s i nc h a p t e r2 ，w es t u d yt h ei n e r t i a sa n dt h es p e c t r ao ft h es i g np a t t e r nm a t r i c e s f i r s t l y ，w e g i v eap a r t i c u l a rd e s c r i p t i o no fac l a s so ft h es p e c i a ls i g np a t t e r nm a t r i c e s s e c o n d l y , w e i n t r o d u c et h ed e v e l o p m e n to ft h es p e c t r a l l ya n di n e r t i a l l ya r b i t r a r ys i g np a t t e r n n e x t ，w e c h a r a c t e r i z et h ei n e r t i ao fas k e w s y m m e t r i cs i g np a t t e r nao fo r d e rna n dt h es i g np a t t e r na 。 f i n a l l y , w ei n t r o d u c eas p e c t r a l l ya r b i t r a r ys p a r s es i g np a t t e r n i nc h a p t e r3 , w ec o n s i d e rt h en u m b e ro fn e g a t i v ee n t r yo ft h em a t r i xw h o s es q u a r ei s n o n p o s i t i v ea n ds u m m a r i z et h ec o n s i t i o n sb yt h en u m b e r s f u r t h e r ，w ep r o v et h er d e m a l v a n da s t e g e r sc o n j e c t u r ei st u r ew h e nt h eo r d e ro f ai s4 i nc h a p t e r4 , t h em e t h o do fc o n s t r u c t i n gt h es i g np a t t e r n st h a ta l l o wo r t h o g o n a lm a t r i xi s g i v e n i n p a r t i c u l a r , w ei n t r o d u c es o m es u f f i c i e n tc o n d i t i o n s o rn e c e s s a r yc o n d i t i o n so i l p o t e n t i a l l yo r t h o g o n a lm a t r i x k e y w o r d s ：s i g np a t t e r nm a t r i x ；l n e r t i a l l ya r b i t r a r ys i g np a t t e r n ；s p e c t r a l l ya r b i t r a r ys i g n p a t t e r n ；p o t e n t i a l l yo r t h o g o n a lm a t r i x 中北大学硕士学位论文 第一章绪论 1 1符号模式矩阵研究的历史 元素取自于集合( + ，一，0 或 1 , - 1 ，0 ) 的矩阵，称为符号模式矩阵，简称为符号模式 ( s i g np a r e m ) 。对于给定实矩阵爿= ( ) ，由的符号s i g n a , j 为元素组成的符号模式 ( s i g n a y ) 称为a 的符号模式，记为s g n a 用q 表示全体h 阶符号模式所组成的集合，对 任意a q ，所有与a 有相同符号模式的实矩阵组成的集合口i j 为h 阶实矩阵，且 s g nj = a 称为由a 所决定的定性矩阵类( q u a l i t a t i v em a t r i xc l a s s ) ，记为q ( a ) 。若a 是一个m ，z 实矩阵，则爿同样可以决定一个定性矩阵类q ( a ) = b i b 为n 实矩阵，且 s g n b = s g n a 。 符号模式矩阵主要研究符号模式矩阵或实矩阵所确定的定性矩阵类的组合性质，即 研究实矩阵所具有的仅与其符号有关而与元素的数量大小无关的组合性质，其主要研究 内容涉及线性方程组的符号可解性，符号稳定性，以及具有特定性质的符号模式矩阵类 的组合性质，它与图论、组合矩阵论、矩阵分析、常微分方程、算法理论和经济学有密 切联系。 符号模式矩阵起源于2 0 世纪3 0 年代诺贝尔经济学奖获得者p a s a m u e l s o n 为处 理当时国际经济出现的经济问题而提出的经济数学模式线性动力系统，研究其符号 可解性和符号稳定性，1 9 4 7 年r a s a m u e l s o n 系统总结了他的经济数学理论，写成 ( ( f o u n d a t i o n se c o n o m i ca n a l y s i s ) ) 一书，由哈佛大学出版社出版，并于1 9 7 1 年再版。此 后数学家及生物学家r m ma y ，c j e f f r i e s ，y um s v i r e z e r 和d 0 l o g o f e t 等人先后发 现生物学中的生态系统和经济学中数学模型的许多定性性质是一致的，而符号稳定性概 念也在化学家f ( 如7 0 年代b l c l a r k e ，j j t y s o n ) 和社会学家( 如8 0 年代ys h i r a k u r a ) 的各自研究领域中出现。这表明符号模式矩阵的研究在经济学、生物学、化学和社会学 以及理论计算机科学中具有广泛的实际应用背景。许多国际知名的数学家如r a b r u a l d i 、v k l e e 、c r j o h n s o n 、j s m a y b e e 、c a e s c h e n b a c h 、c j e f f r i e s 等在这一研 中北大学硕士学位论又 一_ 2 = 2 = 1 2 = = = = ! ! = d ! ! = ! ! ! = = = = = = = 。! = = ! ! 2 1 = = 一一 究领域都有重要贡献。1 9 9 5 年r a b r u a l d i 和bl s h a d e r 的专著m a t ：q c e - ：。 s i g n s o i v a b l el i n e a rs y s t e m s 系统总结了到1 9 9 5 年为止这一领域中所取得的研究成果， 将本课题的研究推向一个新的层面【l s 1 9 2 1 2 们。目前，国内在这方面的研究尚处于起步阶 段，但部分工作已处于国际领先水平，特别，同济大学邵嘉裕教授、中北大学高玉斌教 授、邵燕灵教授等的工作都引起了国际同行的广泛关注1 _ 5 ，6 ，1 0 ，1 3 ，2 0 3 0 ，3 4 ，4 2 j 4 8 4 9 1 。 1 2 符号模式矩阵的基本概念 1 2 1 一般矩阵的有关知识 定义1 2 1a m 。( | r ) 的主子矩阵是a 的具有相同行、列指标的k 阶子矩阵， 而t 。t 主子式是这个主子矩阵的行列式，_ = c 吩，有 个不同的七m 阶主子式，用 乓( _ ) 表示所有这些女k 阶主子式的和。特别地e 、( 4 ) = 以“称为a 的迹( 通常记为 t r y ) ，e 。( a ) = d e t a 。 命题1 2 2 每个矩阵爿m 。( r ) 在复数范围内恰好有h 个特征值( 重根按重数来 计) 。 命题1 2 3 若4 帆) ，且n 为奇数，则爿至少有一个特征值为实数。 定义1 2 4 “鸠 ) 的特征多项式定义为儿( f ) = p a i 。 显然，若将爿e m 。( r ) 的特征值记为a ，五，乃( 其顺序是任意的，且重根按其重 数计算) ，则有p 。( f ) = ( f a ) 9 一五) ( f 一 ) 。 命题l - 2 5 办( f ) ：，“一日_ ) ，“+ 邑( 爿) f “e 一) ，即，“的系数恰为a 的所 有k 阶主子式之和。 定义1 2 6 一个矩阵4 鸠( r ) 是幂零的，是指对某个正整数k 有a = 0 。 显然幂零矩阵的特征多项式为p 。( f ) = f ” 中北大学硕士学位论文 定理1 2 7 旧设爿m ( o 是给定的h e h i m 矩阵，y c ”为给定的向量，- e 丑是 给定的实数，设j 。( ( 1 ) 是如下形式的矩阵 j ：1 b a 设爿和j 的特征值分别用 五 和积 表示，且假定它们按递增排序 兄曼七 元五， 丑， 丑，丸。 那么丑茎 如兰如s 屯五。南。 以上定理称为加边矩阵的交错定理。值得注意的是，其逆定理也是存在的。 定义1 2 8 设a = ( 吩) ( r ) ，称a 0 ( 非负矩阵) ，是指它的元素都是非负 实数，a 0 ( 正矩阵) 是指其元素d 。都是正实数。 定义1 2 9 如果矩阵p t ，( 月) 在它的每一行和每一剜上正好有一个元素等于1 ， 而其余所有的元素均为0 ，则称p 为置换矩阵。 定义1 , 2 1 0 设0 l ( 露) ，如果存在置换矩阵p 屯( 固使 p a p r = 薯； ，其中嚣和。分别是疋，阶方阵，t v 副 则称a 是可约矩阵( r e d u c i b l e m a t r i x ) ，否则称a 为不可约矩阵( i r r e d u c i b l e m a t r i x ) 。 出定义知，每个一阶矩阵都是不可约矩阵。以后如没有特别说明，我们所说的不可 约矩阵都是非零的。 12 2 一个多项式的零点对它的系数的连续依赖性 定理1 2 1 1 l ”1 设”1 ，且设 p ( x ) = a n x ”+ a n _ i x ”_ + + 4 x ，- a 0 “n 0 是一个复系数多项式，那么，对任给 0 ，存在j 0 ，使得对任一适合6 。o 的多项 式 尊扛) = 丸j ”+ 吒一l x 肛1 + + 矗 x + 中北大学硕士学位论文 和 滕k b i l 占 我们有 r n ，i n m ，a x l 五，一以( f ) 0 ，使得，( b ( ) ) = ，( b ( 0 ) ) = ( 0 ，0 ) 。 令b = b ( e o ) ，则b q ( ) 。 类似的，可得到下面两个命题。 引理2 2 4 5 1 对n 2 ，存在c q ( 彤) ，使得，( c ) = ( ”，0 ，o ) 。 引理2 2 5 5 1 对n 2 ，存在a i , 也q ( s ) ，使得，( ，) = ( o ， ，o ) ，i ( a ：) = ( ，0 ，0 ) 。 引理2 , 2 6 8 1 设女2 ，a 1 q ( 爵) 且，( 4 ) = ( 0 ，k ，o ) ，则对任意正整数z m ，存在 如下( a + f ) x ( k + ) 分块阵 使得 1 4 = l 4 “爿，： 爿，i l 一，削：朋，j ( 2 ) p a 】l o ，a 13 0 ，p a ，3 0 ，p a 2 是f 阶具有零对角线且对角线以上所有 元素全正的符号反对称阵。 汪明：令x = ( 11 ，一1 ，x 。) 是一个k 维实向量，由a 的形式知，存在充雯豹正 整数 0 ，使得对诋i ，。7 都有n jj 0 。 ! ! ! 奎耋堡圭丝丝兰 再设 娅 i 一1n + m + t 一3 _ + ”4 ，# + l ，一，_ 1 ，+ + _ 2 ) 一1 n + m + k f 一2 j “ ( 4 ：，4 3 ) = ( m ，一， ，) ) = ( p a m p a l 3 ) + m l + 埘一2 11 卜一l ? 一2 z 一3 一( f1 ) 一( ，一2 ) 一( z 一3 ) 0 只= + m f 引。 容易看出，4 = l m a i l 。删m i 2 ，：蹦a 1 3 ， j l i , 抖两足条件( 1 ) 和( 2 ) 。证毕。 引理2 2 7 5 】设2 k ，则存在a q ( ) ，使得，( 爿) = ( 0 ，k ，m t ) 。 证明：若k = ，由引理2 2 5 ，显然。 若2 k ，只需在引理2 26 中取z = m = l k ，则儿= ( - i i 一，1 ) ，显然 一= 茂a 1 2 甜a i 3 鹏， 满足i ( a ) = ( o ，k ， 一) 。 用引理2 26 ，引理227 的证明方法，易证得下列两个引理 引理2 2 8 3 1 设女2 ，d 1 ，q ( ) 且( d 1 ) = ( k ，0 ，0 ) ，则对任意正整数，”，存 在如下矩阵。= 篇3 篇2 篇1 ，使得 ( 1 ) r a n k ( d ) = r a n k ( d ) = k ( 2 ) p d ， o q3 0 ，b ( d ) q ( s 。) 满足r a n k ( b ( 6 ) ) = s 。因为 b ( 6 ) 的特征值是h - 的连续函数，存在充分小的瓯 0 使得f ( b ( 瓯) ) = ( o ，s ，) ，即 ( 0 ，s ，) ，( s 。) 。 现在假设r 1 ，由引理2 27 ，存在一个伽一r ) 矩阵 b 恼9 12 剖lp b l l 朋1 2 p 口1 3j 这里b b m b l 3 及j d 分别是在引理2 27 的证明中定义的s s ，s t ，= r 及f j 矩 阵。如果r 1 ，则由引理2 28 ，存在c 。q ( 昂) 使得f ( c ，) = ( r , o j 0 ) 。如果。一；贝：取 ：1 。= m 。 ，( 五) 中北大学硕士学位论文 踯，= 慝p b8 妻p b 善c ， b ( 6 ) = l】12 酽b 1 3i l 一，1 一，2 l 】j 这里占0 ，是，s 矩阵，j ，是r t 矩阵，且j ，和，的每一个元素都是1 。显然， z ( b ( o ) ) = ( _ j ，t ) 。对任意j 0 ，b ( 艿) e q ( 瓯) 且满足，口础( 占) ) = j + r 。因为b ( d ) 的特征 值是j 的连续函数，故存在一个充分小的瓯 0 使得i ( 口( 磊) ) = p ，s ，力，即p ，j ，f ) ，( ) 。 d z l t 2 x 2 ： 积月一1 x 月 这里s 0 , 0 0 ，x l = ( - - 1 ，1 ，2 ，一2 ，6 ) ，x 。= ( - - i ，- - 1 ，一l ，口) ， i 一5 ，如果4 的第i 个对角元是 4 = 占，如黝。的第i 个对角元是+ i = 2 ，一，n 一1 1 0 ，如黝。的第i 个对角元是0 ，1 一瓦) s ( n 一3 一民一1 ) s ( 1 一只一，弦 1l 1 弦劲疋 一 +即o 一 ：蚴如 一 十 一 0 z f 弦一篙弦陋“暖以 丑 一 一 犯0 口 口 玩 1 j 一 一 一丑 十 +6 五 占 j s 一 ， 以瓯 + 一 q z 中北大学硕士学位论文 兄+ 112 一规五 一颤 兄 “ 11 1 + 1 一 一( n 一2 ) 一6 1 一( 1 一吒) dj 一( 2 一岛) 以i 旯 一( 一2 一瓯一，) 以l 1五一日i f n 一0 ( n 一2 ) g 刀：l 2 1 + 一2 ) c 刀一2 ( 牙+ c 且+ d ) = 刀f 2 9 ( z ) 这里c = 1 一日一s 占 一6 一( n - 2 ) ( n - 1 ) ( 2 n - 3 ) 8 6 五一日+ 坚 1 ) 0 2 k 州1 一生孥坐】 - 一( n - 1 了) ( n - 一2 ) 5 一s 二n - i 伽 + f ( i 一1 ) j s 4 + 1 + ( n 一2 ) s 6 + 9 1 二兰丛! 二竽一s 喜( i 1 ) 4 容易看出 l i r a c = 1 一d 1 i m d = 一日+ b 取s 及占充分小，我们可以选择及b 使得 ( 1 ) c = 0 且d 0 ，则g ( 旯) 有两个纯虚根，从而f ( d ) = ( 0 n , o ) ，所以( o ，0 ，月) r ( s 。) 。 ( 2 ) c 0 且d 0 时，c a 。q ( l ) ，而 jz l a 。卢= ”+ 一f z ”“+ 一z z “一2 + + z + r o 这表明定理对于( t o ，一。) 任意接近( 0 , 0 ，o ) 时是有效的。 考虑月= 4 ，a 。的特征多项式为： z4 + ( 4 。一日4 ) z 3 + ( “i + d 2 + d 3 一。a 4 ) z2 + ( 口。d 2 + a o d 3 一( 2 1 n 4 一( 3 2 d 4 ) z + ( t i “3 一。o 日2 4 以下构造正实数d 。，a 一，d 。，使得 口。一a 4 一r 3 = 0 “i + 0 2 + 日3a o 口4 “0 d 2 + “o 口3 一d 1 “4 d l ( 1 3 一d 0 ( 1 2 d q r o 不妨设a 。为幂等的，并记，0 = _ = = r 3 = 0 ，可确定( 1 ) 的一个解是 d o = d 4 = 1 ，d 】= d 3 = 4 2 1 ，d 2 = 3 2 2 令口。= d 。= 1 ，将( 1 ) 式的左端分别定义为函数；， ，六， 。注意到匝数，i 对于 ( o _ o 一 = q 吗o 中j b 大学硕士学位论文 所有八个变量有连续的偏导数。且 ，：鲻掣：。：+ a 。a i 蝴鸠 a ( a o ，a l ，a 2 ，a 3 ) ” ”。 取( 口o ，口l ，a 2 ，a 3 ，r o ，r l ，r 2 ，_ ) = ( a o ，占i ，占2 ，盎3 ，0 00o ) ，此时 l ，= a 。2 + 二。j 】+ 二。+ 二，= 2 压 ( 2 ) 由隐函数理论，若( r o ，b ) 充分接近( 0 ，0 ，0 ，0 ) ，则存在唯一的，_ ，r 2 ，r 3 连续函 数a 。，1 ，a ：，保持 = = = 正= 0 。这就导致了a 。的一个预期特征多项式的产生。 对于爿。的证明依赖两个事实：首先也蕴含一个幂零，其次一个确定的雅可比行列 式非0 。从a 4 到4 的证明也可按此扩展。 首先，我们可作以下取值，导致幂零的存在。( 下表中”= 7 是近似的) a oa la 2a 3a 4色a 6& 7 111 1 1 1 1 22 1 压一13 2 压压一1i l 堂一, g - 2 盟一3 - 4 9 1 2222 1 盟一3 3 - 一5 7 4 压一3 - , 5 - ，- s 一4 3 - 1 l 2 222 1 03 5 700 8 800 5 500 5 500 8 803 5 7 1 其次，对于2 n s7 ，必定表明一个确定l 0 ，注意计算l 可通过在微分前从中 删去，_ ，i 而不会改变结果。 令a ，= & 。= l ，当( “。，q ，“肛、，_ 一，) = ( 磊o ，黼肛、，o ，- ，o ) 时 中北大学硕士学位论文 以= 蒜葛枷 其中，表示iz 一4 t i 中z ”。的系数，由上表的对称分布，雅可比行列式可分别计算如下： 如= 1 ，= 2 ，山= 2 拒，山= 4 h 。( h 2 + 1 ) 以= 4 色 ( 占一龟) 2 + 龟( 磊+ 1 ) ( 也+ 1 ) = 8 h i 2 a 2 ( a i 一岛) 2 + a x ( h 2 + 1 ) ( 岛+ 1 ) 既然 ， ，是全正的，当然不为0 ，满足了要求，因此整个2 7 获得证明。 该定理表明，q 可被适当选择使得4 ，4 ，4 有任意特征多项式，即l 当2 n 7 时，是一s a p ( 从而也是一i a p ) 。而a 。又恰有2 n 个非零元，因此瓦又是一m s a p ，因 而对2 ”7 ，也是一m i a p 。要将该定理的证明推