（基础数学专业论文）条件s阵与符号稳定矩阵.pdf

条件s 一阵与符号稳定矩阵 摘要 符号矩阵理论是组合矩阵论中的一个新兴研究方向，该理论主要研究矩阵的 仅与其符号模式有关的那些性质它最早来源于经济学中对某些问题的定性性质 的研究其开创性工作是由诺贝尔奖获得者、经济学家p s a m u e l s o n 首先作出的( 参 见文阳) 由于符号矩阵理论在经济学上有重要的应用价值，从而引起了经济学 家、数学家及计算机理论专家的广泛关注1 9 9 5 年，a b r u a l d i 与b l s h a d e r 合作 完成了符号矩阵论的第一部专著m a t t i c e so f s i g n s o l v a b l el i n e a r s y s t e m s ) ) ( f 4 1 ) 该 专著全面系统地总结了在符号矩阵理论方面的研究成果，同时给出了许多新的结 论，从而使符号矩阵理论成为组合数学的一个新兴研究热点 本文主要研究了符号矩阵理论中的二个专题：一是条件s 一阵的性质、判别 和特征刻划问题；二是与符号稳定矩阵的判别相关的若干图论问题的研究 众所周知，线性方程组的符号可解性判别问题可转化为一阵与s 一阵的判 别问题( 9 1 、 2 9 1 、 3 8 1 ) 因此，三一阵与s 。一阵是符号矩阵论中非常重要且研 究得也十分透彻的两种矩阵另外，每行均有正有负的s 。一阵称为s 一阵一般 地，任一s 一阵可经适当的列变号化为s 一阵：故我们常直接对s 一阵进行研究在 文【5 】中，r b r u a l d i ，k l c h a v e y 及b l s h a d e r 把线性方程组的符号可解性判别问 题推广到条件符号可解性判别问题而在多数应用问题中，条件符号可解比一般 符号可解更接近于实际问题的要求与此相应地他们引进了s 。一阵和s 一阵的一 种推广一一阵和c s 一阵( 即条件s 。一阵和条件s 一阵) 利用c s + 一阵他们 证明了条件符号可解线性方程组的判别问题可转化为一阵与+ 一阵的判别问 题，从而推广了有关符号可解线性方程组的经典判别结果此后在文 5 4 1 中， t y s h a o 和s u k - g e u nh w a n g 利用锹船阵给出了四+ 一阵和c s 一阵的一个有用的 特征刻划但总的来说，对田+ 一阵和c s 一阵的研究还远不如对s 一阵和s 一阵 那样深入和完全在本文的第二章中，我们对田。一阵和c s 一阵进行了更为细致 深入的研究所做的主要工作如下： i i 1 通过引进矩阵的“强行 的概念，把在s 一阵，s 一阵及三一阵的 研究中起重要作用的“共形收缩”变换推广为“广义共形收缩变 换，使它成为研究凹。一阵和c s 一阵的一个有力工具 2 通过引入标准r s b 阵的概念，并且结合图论方法给出了c s 一方阵的 一个特征刻划及多项式时间的判别算法；同时给出了c s 一方阵的非 零元个数的s h a r p 上、下界及达到这些界的口一方阵的完全刻划 3 进一步研究了在【5 1 中已作了初步研究的一个重要的特殊c s 矩阵类 一口c s 一阵对固定的正整数n ，我们通过结合使用数论方法给出 了存在个mxn 的丑c s 一阵的充要条件：同时也给出了曰c s 一阵的 非零元个数关于列数刀的s h a r p 上、下界及达到这些界的b c s 一阵 的完全刻划 4 作为极大s 一阵概念的推广，我们引进了极大c s 一阵的概念，并给 出判别极大c s 一阵的一些( 递归的) 必要条件与充分条件以及某些 特殊情形下的充要条件 事实上，文【9 】的第四章中关于s 。一阵或s 一阵的许多重要性质都在本文中被 推广到了c s 一阵或c s 一阵，从而原来的结论就成为我们所得结果的推论 本文研究的另一个专题是矩阵的符号稳定性及与之相关的图论方法和图论问 题一个实矩阵的符号稳定性问题在经济学、生态学等诸多领域中均有重要的应 用背景在文f 2 1 1 中，c j e f f x i e s ，v k k e 及p v a i ld e nd r i e s s c h e 给出了不可约方阵彳 为符号稳定的一个特征刻划但该特征刻划主要是从纯矩阵论的角度给出的在 本文的第三章中，我们用图论方法进一步深入地研究了矩阵的符号稳定性并得到 了一些较为直观的充分必要条件所做的主要工作如下： 1 把一个实矩阵的符号稳定性判定问题转化为一个等价的图论问题， 即判定无向树中一个点子集的稳定性问题我们引入了树的稳定子 集的概念并给出了稳定子集的递归判别方法，由此不难得到一个多 项式步数的判别算法 2 提出并研究了树的稳定指标，即树中所有稳定子集的最小基数证 明了关于稳定指标的一个m i n m a x 型定理；并给出了树的稳定指标 的最好上界及达到该上界的极树的完全刻划 关键词：符号矩阵符号稳定稳定子集稳定指标图导出子图 i i i 绘光旌回济太堂簋堂僮论文 c o n d i t i o n a ls - m a t r i c e sa n d s i g n s t a b l em a t r i c e s a b s t r a c t s i g n e dm a t r i xt h e o r yi s an e ws u b j e c to fc o m b i n a t o r i a lm a t 1 a xt h e o r y ，w h i c hi n v o l v e st h e s t u d yo ft h ep r o p e r t i e so fr r l a t r i c e st h a td e p e i l do n l yo nt h es i g np a t t e mo 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 nw h oi s a l le c o n o m i s t , i su s u r y c o n s i d e r e dt oh a v eo r i g i n a t e d 谢d lt h ed i s c u s s i o no 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 e p r o b l e m si n e c o n o m i c ss e e 【4 6 】) b e c a u s eo 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 s b e e np a i dw i d ea t t e n t i o nb ym a n yr e s e a r c h e r ss u c ha se c o n o m i s t s ，m a t h e m a t i c i a n sa n d t 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 n19 9 5 ，t h ef i r s tm o n o g r a p h ( m a t r i c e so fs 咖一s o l v a b l e l i n e a rs y s t e m s ) ) ( 4 1 ) o ns i g n e dm a t r i xt h e o r yw a sp u b l i s h e db yr a b r u a l d ia n db l s h a d e r t h eb o o ks 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 nt h i ss u b j e c t i na d d i t i o n ，m a n yn e w r e s u l t sw e r e 洳t h r o u g h o u tt h eb o o k i tm a k e ss i g n e dm a t r i xt h e o r yb e i n ga na c t i v ea r e a o 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 培e am a t r i xt h e o r yh a v eb e e ns t u d i e d o n ei st h e s t u d yo nt h ep r o p e r t i e s ，r e c o g n i t i o nc r i t e r i ao f c o n d i t i o n a ls 一l l h q t n c e $ t h eo t h e ri st h e s t u d yo ns o m eg r a p h i c a lp r o b l e m sc o n c e r n i n g t h er e c o g n i t i o no fs i g ns t a b l em a t r i c e s i ti sw e l lk n o w nt h a tt h es t u d yo fs i g n - s o l v a b l el i n e a rs y s t e m sc a nb et r a n s f o r m e dt o t h es t u d yo f 三- m a t r i c e sa n ds - m a t r i c e ss e e 9 1 ， 2 9 1a n d 3 8 1 ) s ol m a t r i c e sa n d s 。一i i l a t r i c e sa r ev e r yi m p o r t a n ta n dh a v eb e e ns t u d i e dt h o r o u g m y i na d d i t i o n , a s “- m a t r i xai sc a l l e d 鲁s - m a t r i xi fe a c hr o wo fac o n t 出sb o t hp o s i t i v ea n d n e g a t i v ee n t r i e s i ng e n e r a l , a s 一m a t r i xc a nb em a d ei n t oas - m a t r i xb yn “d p l y i n g c e r t a i nc o l u m n sb y 一1 s o m e t i m e sw es t u d yt h ep r o p e r t i e so fs - m a t r i c e sd i r e c t l y i ni s ， r a b m a l d i , k l c h a v e ya n db l s h a d e rg e n e r a l i z e dt h ec o n c e p to fs i 铲一s o h r a b i l i t yt ot h e c o n c e p t o fc o n d i t i o n a l s i g n s o l v a b i l i t y o fl i n e a r s y s t e m s i n d e e d , c o n d i t i o n a l s g n s o l v a b i l i t yi sm o r ew i d e l ya p p l i c a b l et h a nt h eu s u a ls i 弘一s o l v a b i l i t yi nm o s ! c a s e s b y i n t r o d u c i n gc s - m a t r i c e sa n dc s - m a t r i c e st h a ta r eg e n e r a l i z a t i o n so fs - m a t r i c e s a n ds - m a t r i c e s ，t h e ys h o w e dt h a tt h es t u d yo fc o n d i t i o n a l l ys i g n - s o l v a b l el i n e a rs y s t e m s c a nb et r a n s f o r m e dt ot h es t u d yo fl - m a t r i c e sa n dc s 一m a t r i c e s ，t h u sg e n e r a l i z e st h e i v 猃迸龌回溘太堂墟堂僮论塞 c h s s i c a l r e c o g n i t i o n r e s u l t sf o rs 咖一s o l v a b l el i n e a rs y s t e m s i n 5 4 1 ，j y s h a oa n d s u k - g e u n h w a n go b t a i n e d a nu s e f u lc h a r a c t e r i z a t i o no fc s 一i n a t r i c e sa n d c s i i l a u ：i c e si nt e r m so fg r s bn 3 r t r i c e s 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 f c s 一m a m c e sa n dc s m a t r i c e si sn o ts ot h o r o u g ha st h es t u d yo fs 一m a t r i c e sa n d s m a t r i c e s i nc h a p t e r2 ，w et a k eam o r ec a r e f u ls t u d yf o rt h ep r o p e r t i e sa n dr e c o g n i t i o n c 诎o f 傩一r l a t f i c e sa n dc s m a t r i c e s t h em a i nw o r k sw eh a v ed o n e 牡ea s f o l l o w s 1 b yi n t r o d u c i n gt h ec o n c e p to f “m a j o r i z e d r o w o v e ram a t i n ) ，w eg e n e r a l i z et h e c o n f o m m lc o n t r a c t i o n o p e r a t i o nt ot h e g e n e r a l i z e dc o n f o r m a lc o n t r a c t i o n o p e r a t i o n t h a ti sa l le f f e c t i v et o o li nt h e s t u d y o fc s 一i l l a t 士i c e sa n d c s m a t r i c e ss u c ha st h ec o n f o r m a lc o n t r a c t i o no p e r a t i o ni nt h es t u d yo f s 一m a t r i c e s ，s - m a t r i c e sa n d 三一i d _ a t r i c e s 2 b vi n t r o d u c i n gt h ec o n c e p to fs t a n d a r d 兄归m a t r i x , w eu s eg r a p ht h e o r e t i c a l m e t h o d st o 咖eac h a r a c t e r i z a t i o na n d ap o l y n o m i a l - t i m er e c o g n i t i o na l g o r i t h mf o r s q u a r e a m a t r i c e s w ea l s ou s eg r a p ht h e o r e t i c a lm e t h o d st o 咖es 脚l o w e r a n du p p e rb o u n d sf o rt h en u m b e ro fn o n z e r oe n t r i e so fs q u a r ec s - m a t r t c e so f o r d e r 嚣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 n so f t h ee x t r e m a lc s m a t r i c e s w h o s en u m b e ro fn o n z e r oe n t r i e sa t t a i nt h e s eb o u n d s 3 w es t u d yv a r i o u sp r o p e r t i e so fas p e c i a lc l a s so fc s m a t r i c e s - - b c s m a t r i c e s w h i c hi sd e f i n e da n ds t u d i e di nf 5 】w eu s en u m b e r 也e o r e t i c a lm e t h o d st o 咖ea n e c e s s m r ya n ds u f f i c i e n tc o n d i u o nf o rt h ee x i s t e n c eo f 饥，打以 b c s m a t r i x w ea l s og i v es h a r pl o w e ra n du p p e rb o u n d sf o rt h en u m b e ro fn o n z e r oe n t r i e si n t e r m so ft h en u m b e ro fc o l u m n sy ，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 n so f t h ee x t r e m a lb c s m a t r i c e sw h o s en u m b e ro fn o n z e 譬oe n t r i e sa t t a i nt h e s e b o u n d s 4 w ei n t r o d u c et h ec o n c e p to fm a x i m a lc s 一蚴t r i c e s ，w h i c hi st h eg e n e r a l i z a t i o n o fm a x i m a ls - m a t r i c e s w eo b t a i ns e v e r a l ( r e c u r s i v e ) n e c e s s a r yc o n d i t i o n sa n d s e v e r a ls u f f i c i e n tc o n d i d o n sf o ram a t r i xt ob eam a x i m a lc s m a t r i x ，t o g e t h e r w i t hs e v e r a ln e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n sf o rs o m es p e c i a lc a s e s i nf a c t , m a n yo ft h er e s u l t so b t a i n e di nt h i sp a p e rf o rc s a n dc s m a t r i c e sa r e g e n e r a l i z a t i o n so f t h ec o r r e s p o n d i n gr e s u l t sf o rs a n ds m a t r i c e si n 【9 】( c h a p t e r4 ) t h eo t h e rs p e c i a lt o p i co ft h i sp a p e ri st h es t r a yo fs i g ns t a b i l i t yo f ar e a ls q i 1 a r em a t r i x a n dt h er e h t e dg r a p ht h e o r e t i c a lp r o b l e m s s i g ns t a b i l i t yo far e a ls q u a r em a t r i xh a s i m p o r t a n ta p p l i c a t i o n si nv a r i o u s a r e a ss u c ha se c o n o m i c s ，e c o l o g ya n ds oo n i n 【2 1 】， v 盆迸龌圄渣太堂埴堂僮途塞 c j e f f r i e s ，v k l e ea n dp v a nd e nd r i e s s c h eg a v eac h a r a c t e r i z a t i o nf o r 柚i r r e d u c i b l e s q u a r em a t r i x at ob eas i g i ls t a b l em a t r i x b u tt h i sc h a r a c t e r i z a t i o ni s 咖e i lm a i n l yf r o m t h ev i e w p o i n to fm a t r i xt h e o r y i nc h a p t e r3 ，w eu s eg r a p ht h e o r e t i c a lm e t h o d st ot a k ea m o r et h o r o u g hs t u d yf o rs i 妒s m b i l i t yo fas q u a r em a t r i xa n do b t a i ns o m ei n t u i t i v e n e c e s s a r y a n ds u f f i c i e n tc o n d i t i o n s t h em a i nw o r k sw eh a v ed o n ea lea sf o l l o w s 1 t h e 睁s t a b i l i t yp r o b l e mf o rm a t r i c e s i st a m e di n t o 砸e q u i v a l e n tg r a p h t h e o r e t i c a lp r o b l e m ，n a m e l y , t h es t a b i l i t yp r o b l e mf o rt h ev e r t e xs u b s e t so ft r e e s w ei n t r o d u c et h ec o n c e p to fs t a b l ev e r t e xs u b s e t so ft r e e sa n d 垂咒ar e c u r s i v e d e c i s i o nm e t h o df o r r e c o g n i z i n gt h e mf r o mw h i c hw ec a r le 2 s i l y o b t a i na p o l y n o m i a l - t i m er e c o g n i t i o na l g o r i t l 蚰 2 w ei n t r o d u c ef o rt r e e san e wp a r a m e t e r , s t a b l ei n d e x ，w h i c hi st h es m a l l e s t c a r d i m l i t ya m o n g a l lt h es t a b l ev e r t e xs u b s e t so fat r e e w ep r o v eal 血- m a xt y p e t h e o r e mf o rs t a b l ei n d e x ，季咒as h a f pu p p e rb o u n df o rt h es t a b l ei n d i c e so ft r e e s o fo r d e r ，l ，a n d 咖eac o m p l e t ec h a r a c t e r i z a t i o nf o rt h ee x t r e m a lt r e e sw h o s e s t a b l ei n d i c e sa 比咄t h i s u p p e r b o u n & k o 彻o r d s ：s i g n ；m a t r i x ；s i g ns t a b i l i t y ；s t a b l es u b s e t s ；s t a b l ei n d e x ；g r a p h ；i n d u c e d s u b g r a p h v i 猃左龌回渣太堂熊堂鱼迨塞 b 名词索引 标准兄妨阵，1 5 伴随有向图，1 6 伴随无向图，2 5 b c s 一阵( 勒四一阵) ，2 9 不带环( 或带环) 伴随有向图，4 2 不带环( 或带环) 带号伴随有向图，4 2 c s + 一阵，5 c s 一阵，5 定性矩阵类，1 定性性质，l 等价矩阵，9 度数，4 6 二元行，1 2 二元正则形，1 2 符号模式，1 符号可解，1 符号稳定矩阵，7 符号序，1 0 反稳子集，4 3 g 见妨阵，9 共形矩阵，1 1 c d e f g 共形收缩矩阵，1 2 广义共形收缩矩阵，1 2 共形拷贝，2 4 还原图，4 7 h 极大c s 一阵，3 6 三一阵，4 n e a r l yl 一阵，4 凝树，4 7 强行，1 0 圈的符号，4 3 兄妇阵，9 田v s 一阵，4 一阵，4 s 一阵，4 条件符号可解，3 ( “，) 一扇，4 7 l n q r s t u y 严格行( 或列) 定号，9 以2 为基的表达式，3 1 w 舛7 秘钳 阵集标矩子指定定定稳稳稳 第一章绪论 1 1 研究背景 实矩阵彳= ( ) 的符号模式是指以元素口 f 的符号s 印为元素所组成的一 个符号矩阵s 印彳= ( s 弘) 所有与彳具有相同符号模式的实矩阵组成的集合称 为a 的定性矩阵类，记作q 0 ) 符号矩阵论是研究矩阵的只与其符号模式有关， 而与其非零元素的绝对值大小无关的性质，也即研究定性矩阵类中那些矩阵所共 有的性质这些性质也称为矩阵的定性性质 符号矩阵理论是组合矩阵论中的一个新兴的研究方向它最初的研究背景来 自经济学中对某些问题的定性性质的研究事实上，经济学家们长期以来一直确 信并希望( 参见文1 1 0 ) ：经济学中有很大一部分理论及( 感性) 命题可以用定性 的方式来表述即利用一种方法使得某个量的代数符号可仅用系统中相关结构的 参数的符号来预测其数学模型可这样来表示： 设有n + 1 个变量_ ，x 2 ，口，满足如下刀个关系式： z ( x i ，一，x n , 口) = 0( f = 1 , 2 ，刀) ( 其中诸函数z 的具体表达式一般可能并不知道) 若已知诸，齐j i 者x j 及对口的 相对变化率方向( f ，j = l ，2 ，1 ) 能否由此确定诸x ，对口的相对变化率方向? 在考虑该问题的解法之前我们首先给出线性方程组符号可解的定义 定义1 1 1 ( 9 ) 称一个线性方程组a x = b 为符号可解，若它满足以下两个 条件： ( 1 ) 任取a i q ( 彳) 及岛q ( b ) ，方程组4 工= 岛均有解 ( 2 ) 任取4 ，a 2 q ( 么) 及6 l ，b 2 q ( 6 ) ，只要_ ，x 2 满足4 而= 6 l ，a 2 恐= 6 2 ， 霎_ 霎页 萋o x t 卜 蓁 i 挑缸。8a alla 口l f ；i ；l _ 一；1 l 阢既l 盟ll 盟i l 缸l瓯八抛 l 撒 2 参见文1 7 1 、 2 9 1 、 4 7 1 、 5 2 1 等而有关s 一阵的研究则可参见文同、【1 1 】、【1 7 】、 【1 8 1 、 2 5 1 、 2 8 1 、 2 9 1 、 3 8 1 、1 4 1 】、 4 7 1 、1 5 2 等 随着研究的不断深入，人们发现在许多实际问题中符号可解线性方程组的定 义( 即定义1 1 1 ) 中第一个条件经常是不能满足的而且也往往是不必要的1 9 9 3 年，i 沮b r u a l d i ，k l c h a v e y 及b l s h a d e r 在文【5 】中就迸一步考虑了把定义1 1 1 中 第一个条件放宽后的方程组，即条件符号可解线性方程组事实上他们把第一个 条件放宽为：存在4 q ( 彳) 及包q ( 6 ) ，使方程组, 4 i x = 岛有解他们证明了： 条件符号可解线性方程组的判别问题可转化为三一阵与c s 幸舛的判别问题而关 于线性方程组a x = b 还有一种情形是：任取4 q ( a ) 及b l q ( 6 ) ，方程组4 工= 4 均不可解此即符号不可解线性方程组在文 5 1 1 ，t y s h a o 给出了它的特征刻 划关于符号可解线性方程组的其他推广可参见文【2 4 】与【4 8 】 在研究线性方程组的符号可解性的同时，人们也在关注符号矩阵论中的其他 问题其中之一就是一个实方阵的符号稳定性问题( 其他如对矩阵的秩等问题的 研究可参见文【1 9 】与【4 3 】等) 它最初来源于生态学中对生态系统稳定性的研究我 们知道在一个生态系统中，各物种数量的变化规律可用满足初始条件x o = x e 的一 t l b r 常系数线性微分方程组i a x = a x 来表示，这里j = f ) = ( x 。( f ) ，x ( f ) ) r ， 口z a = ( a f t ) 腑而该生态系统是稳定( 即l i mx ( t ) 兰x e ) 的充要条件是a 为稳定矩 阵生态学家的问题是：若只知道a 中各元素的符号能否判定该生态系统是稳定 的? 即如何判断一个生态系统的符号稳定性? 1 9 7 4 年，c j e f f r i e s 在文 2 0 1 首先研究了生态系统的符号稳定性随后在1 9 7 7 年，c j e f f f i e s ，v k l e e 及p v a n d e nd r i e s s c h e 在文 2 1 1 给出了符号稳定矩阵的一个 特征刻划但该特征刻划主要是从矩阵论的角度给出的其他关于符号稳定矩阵 的研究可参见文【4 】、 2 2 】、【2 6 】、 2 7 1 、 3 7 1 、1 3 9 、 4 0 l 、 4 4 1 、 4 5 1 等 3 综上所述可见，对条件s 一阵及符号稳定矩阵的研究迄今为止仍不够全面系 统，还有很多重要问题没有涉及，有待进一步研究本文将对它们作更深入的探 讨 1 2 研究内容 称矩阵彳为三一阵，若任取彳q 0 ) ，彳的列均线性无关；称一个方的三一阵 为s n s 一阵 称一个m x 沏+ 1 ) 酗为s + 一阵，若a 的每个肌阶子方阵均为s n s 阵；又若 s 一酌的每行均有正有负，则称a 为s 一阵事实上任一s 一阵经过适当的列 变号后均可化为s 一阵 在文【2 9 】中，v k l e e ，l l l a d n e r 及r m a n b e r 得到了下面的结论 定理1 2 a ( 1 2 9 1 ) 设a 为m n 的( o ，1 ，1 ) 阵，b 3 0 m 维( 0 ，1 ，1 ) 非零 列向量 贝| j 触= 6 符号可解当且仅当其增广m ，6 ) 置换等价于矩阵( 舌舢 使以下条件同时成立： c ，) 6 位于( 吾) 列块中 ( 2 ) a 1 为s 一阵 ( 3 ) a 2 为一阵 这样线性方程组的符号可解性判别问题就转化为s 一阵与一阵的判别问 题 又称a 为n e a r l y 三一阵，若彳不是三一阵，但去掉任一列后为一阵由此可 定义田一阵 4 定义1 2 1 称一个实矩阵a 为c s 一阵，若它满足以下两个条件： ( 1 ) a 是一个没有全零行的n e a r l yl 一阵 ( 2 ) 任取a ，a 。q ( a ) 及满足a u = 0 ，a 。u 。= 0 的非零向量u ，u ，均有 s g n u = s g n u 。或s g n u = - s g n u 而若c s 一阵彳的每行均有正有负，则称彳为c s 一阵另外，我们知道任一 c s + 一阵均可经适当的列变号后化为c s 一阵因此在本文中我们经常直接对c s 一 阵进行研究 利用四一阵可得条件符号可解线性方程组的如下特征刻划 定理1 2 b ( 【5 】) 设a 为r n 的( o ，1 ，一1 ) 阵，b 为m 维( o ，1 ，1 ) 非 零列向量，则a x = b 为条件符号可解当且仅当增广阵( 彳，6 ) 置换等价于矩阵 ( 舌置) ，使以下条件同时成立： 6 位于( 伽她 ( 2 ) 4 为c s + 一阵 ( 3 ) a 2 为三一阵 因此条件符号可解线性方程组的判别问题可转化为c s 一阵与三一阵的判别 问题他们同时也证明了劣+ 一阵( c s 一阵) 是s 。一阵( s 一阵) 的推广 另外，文【5 】也研究了一种特殊的田一阵即b c s 一阵，而在文【5 4 】中j i a - y u s h a o 与s u k g e u nh w a n g 利用g r s b 阵给出了c s 一阵的一个有用的特征刻划但 总体来看，我们对四阵( 及c s 一阵) 的研究还不够深入，还有许多问题没有 5 得到解决为此在本文的第二章中我们对c s 一阵( 及c s 一阵) 进行了更深入的 探讨 在2 1 中我们首先给出了c s 一阵与c s 一阵的一些基本性质，这些性质中 的大多数( 及2 2 一2 4 中的某些主要结论) 都是文献 9 ( 第4 章) 中关于s 一 阵与s 一阵的对应结果的推广在该节中我们也引进了矩阵的“符号序 与“强 行的概念，并以此把“共形收缩变换( 它保持矩阵的s 一性与s 一性) 推广 到“广义共形收缩 变换( 它保持矩阵的c s 一性与c s 一性) 其中对s 一阵与 s 一阵而言，广义共形收缩也就是通常意义下的共形收缩 在2 2 中，我们进一步研究了c s 一阵的性质及判别算法另外，我们注意 到每个m 以的c s 一阵必满足条件，l m + 1 ，故在对c s 一阵的研究中最重要的两 种情形是r l = m + 1 与刀= m 在拧= 朋+ 1 时，c s 一阵就是s 一阵，故剩下的情形( 即 刀= m ) 就特别令人感兴趣为此我们在2 2 与2 3 中着重研究了c s 一方阵的 性质在2 2 中，我们利用图论方法给出了c s 一方阵的一个特征及多项式时间 的判别算法在2 3 中我们同样用图论工具给出了c s 一方阵的非零元个数的 s h a r p _ 1 2 、下界及达到这些界的c s 一阵的完全刻划 在2 4 中，我们进一步研究了b c s 一阵，同时引入并研究了c s 一阵的另一 特殊类即极大c s 一阵对b c s 一阵，当列数刀为固定的正整数时，我们利用数论 方法给出了存在一个m x 以的b c s 一阵的充要条件另外也给出了b c s 一阵a 的非 零元个数( 彳) 关于列数行的s h a r p 上、下界及达到这些界的b c s 一阵的完全刻 划对极大c s 一阵，我们给出了一个矩阵为极大c s 一阵的一些( 递归的) 必要 条件与充分条件，以及一些特殊情形下判别极大c s 一阵的充要条件 6 本文的另一研究内容是符号稳定矩阵一个实方阵么称为是稳定的，若彳的 每个特征值的实部均为负而一个实方阵彳称为是符号稳定的，若任一个与彳有 相同符号模式的矩阵b ( 即任取b q ( a ) ) 都是稳定的 由矩阵论中的经典结果( 【3 6 】) 可知任一门阶方阵么可置换相似于一个“可约 标准形”即对角块全为不可约方阵的下三角分块矩阵( 此地这些对角块称为 是彳的诸不可约分支) 又易见方阵a 为稳定( 或符号稳定) 当且仅当a 的诸不 可约分支均为稳定( 或符号稳定) ，故在讨论矩阵的符号稳定性时，总可假定所 讨论矩阵是一个不可约方阵 一个挖阶实方阵a = ( a 玎) 的不带环伴随有向图d ( a ) 是这样一个有向图，其顶 点集为y = 1 ，2 ， ) ，弧集为e = ( f ，州0 ，j ) 文【2 1 】中给出了一个不 可约方阵彳为符号稳定的如下的一个特征刻划 定理1 2 c ( 【2 1 1 )设么为刀阶实不可约方阵，则彳为符号稳定当且仅当a 满 足以下诸条件 ( i ) a “0 ，( 1 ，刀) ( 2 ) 口l 口0 ， ( 1 i j 聆) ( 3 ) a 的( 不带环) 伴随有向图d ( a ) 是一棵无向树 ( 4 ) a 的项秩= 刀 ( 5 ) 不存在集合 l ，2 ，刀 的非空子集夕，满足如下三条件： ( i ) 对任意的i 卢，= 0 ( i i ) 对任意的f ，存在j 使0 ( i i i ) 对任意的_ ，岳夕，l i lf 届a j j o l 1 但该定理中的五个条件基本上还是用代数语言来表述而我们知道把代数问 题转化为图论问题往往可使问题更清晰，更易于研究在本文的第三章中我们就 用图论方法对矩阵的符号稳定性问题作进步的研讨 7 在3 1 中，我们首先把一个实矩阵的符号稳定性问题转化为一个等价的图 论问题：即判定无向树中一个点子集的稳定性问题为此我们引入了树的反稳子 集及稳定子集的概念关于树的稳定子集，文献 2 1 与 2 7 中实际上已给出了树 的一个点子集为稳定子集的一些充分条件及在一些特殊情形下( 如所考虑的树是 一条路时) 的充要条件( 当然不是用稳定子集这个术语) 在该节中，我们将给 出在一般情形下一个任意树的一个点子集为稳定子集的递归判别方法( 由此不难 得到一个多项式步数的判别算法) 在3 2 中，我们引进了树丁的稳定指标，( 丁) ，即树丁中所有稳定子集的最小 基数我们证明了关于稳定指标的一个r a i n m a x 型定理，即 ，( r ) 。刚m a x 7 ) ( c o ( t s ) 一脚 其中c o ( g ) 表示g 中非平凡连通分支的个数同时我们还给出了甩阶树丁的稳定指 标i ( t ) 的最好上界及达到该上界的极树的完全刻划 本论文中直接引用的图论及组合矩阵论的一些术语和记号可参见文献 3 、 3 6 3 及 4 9 8 第二章条件s 一阵 2 1c s 一阵的一些基本性质 一个矩阵的某一行( 或列) 乘以1 或一1 称为这个矩阵的一个严格行( 或列) 定号设彳与口为m x 刀阵，若b 可由a 经适当的行列置换及严格的行列定号而得， 则称么与b 等价，记为彳b 一个实矩阵爿称为r 妨阵，如果a 的每一行均有正有负i 一个实矩阵彳称为 g r s b 阵，如果彳可经适当的列变号化为r s b 阵 定义1 2 1 已经给出了醯一阵的定义且易知彳为傩一阵当且仅当彳既是 傩+ 一阵又是憨口阵 由定义1 2 1 显然可知，一个矩阵是否为四一阵仅依赖于它的符号模式，且 在这个矩阵的行列置换及严格行列定号下保持不变 另外由定义1 2 1 的条件( 1 ) 可知，若彳是一个m 刀的醯一阵，则疗朋+ 1 在文【5 1 ，l s 4 i 中，我们知道一个田一阵必为g r g b 阵而且，如果a 是一个 m 沏+ 1 ) 实阵，则a 为岱一阵溅田一阵) 当且仅当a 为s 。一阵域s 一阵) 在 5 4 q ，有如下关于四一阵