（应用数学专业论文）五阶完全正矩阵.pdf

独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得眩徽孵或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名：书琴真 签字日期：伽右年仁月w 日 学位论文版权使用授权书 本学位论文作者完全了解腥榭学有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权詹傲趔琦以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：韦翠童 导师签名： 签字日期：储年e 月叫曰签字日期： 学位论文作者毕业去向：珥批燥甏，吁勘增院 工作单位：电话： 通讯地址： 邮编： 弼2 凇f 辱5 iafab 捕。担 摘要 称一一个月阶半正定、元素非负的矩阵为双非负矩阵，并融所有n 阶双非负 矩阵构成的集合为d n n ，对于a c r “。，若有：| i = 负矩阵b r 满足 a = b b 7 ( r 表示转管) ，则称a 为完全i i 孙0 汜所有，l 阶完全f r 矩阵构成的集 合为c p , ，所有使得a = 删成立的口的最小列数称为1 的分解指数( 或 以的印一秩) 记作) 一个圈g 称为完全正闰，简配为c p 引，如果每个以g 为伴随图的双非负矩阵均为完全j rg 的个双非负实现定义为伴随巨j 是g 的一个双非负矩阵类似定义g 的非负、( p ) 正定、完全i i 实现 与1 在1 9 6 3 年，m i a l l 雨lm n e w n 川1 就汪明了：当hs4 州。，c f ，= d n n 随后m i n c 和m a x f ie ld 利用解矩阵方程j7 = 爿的方法再次词：明了这一结沦， 他们还给出阶数大于等于5 的双非负矩阵不是完令i f 矩阳1 勺例了从而既明 了n 5h 、| c e 为d n n 。的真了集1 9 8 0 年，( 汁a y 和w l i s o n 利用几何方法给出 了这一结论的另一证明特殊类完全 i j 矩阵研究始于1 9 8 7 年1 9 8 8 年， m k a y k o b a d 利用图论方法证明了剥角r 耳优情况下的双非负矩阵为完全正的 1 9 9 1 年，t a n d o 证明了：若a 是一个n 阶j l k e l 矩阵，嗣a 的予矩阵 哇( 1 l n ) d 。，则a 为完全征的19 9 4 年，d l 。w 等人证明了：对称非负矩 阵a 是完全正的，如果它的比较矩阵足个m 一矩阼 1 9 9 1 年，a b o r m a n 等人给 | - _ j ，完个i e 图的儿个等价刻划他们首先证叫 了一个无圈图( 从而树图) 对应的双非负矩阵为完伞| 哪q 进一步他们完成 了剐完全证图的刻划，汪了个图g 为完全i r 罔当f ；_ i 仅当以下条件之成 立： g 的每一个块( b l o c k ，即不含割点的连通分支) 是完仝i e 的 g 的每一个块或是二部图，或足m u 阶完全蚓，或足瓦( 有公共底边的t 个三角形) ! ! i ! ! ! 一一 g 不含氏度大丁4 的奇i 剖 g 是一个完美线图 从完全正研究的4 0 多年的发展历史，不难看出5 阶双非负矩阵的完全l f 问 题是完全正问题研究的关键和分水岭j e 是山于这一原刚，我们在本文主要研 究了5 阶双非负矩阵的完全正问题，为：寄予对5 阶完令i i 。问题研究，能从l l ，得到 更般情形下完全正研究的进一步肩发，从而寻找刽彻底刻划完全正矩阵的突 破n全文共分五章：第一章介绍了完全正矩阵产生的背景；并从矩阵、二次 型和向量组的角度给出了完全j _ 1 j 的儿个等价定义：介绍丁la ，b e r m a n 教授在 1 9 8 8 年提出的关二r 完全正矩阵研究的三个基本问题，h j 1 ) 提出一个可行的判断一个矩阵为完全1 f ：的充坚条件： 2 ) 求完全正矩阵的分解指数； 3 ) 给定图g ，求gn 勺所有完全正矩阵实现晌分解指数构成的集合， | j ，( g ) * 如) ：g ) = g ，a c 只 到i j 前为止，没有一个问题有比较完整的答案 第二章概述完全正矩昨研究的有关进展： 我们将归纳概括低阶矩阵为完 全难的若干充要条件、完全正图的刻划，和一些特殊类完全m 矩阶的描述第 三、四章为本文重点和创新点所在：我们在第i 章商先给u 15 阶r r 完全正图的 分类，并利用初等变换刻划前5 类非完全1 7 - 1 写的完全l 卜实现：我们还利用书图 ( b o o k g r a p h ) 的有关结果刻划了第6 类q l e i l ：圈的完仝j ：实现在第叫章， 我们利用s c h u r 补、去边矩阵利几何方法将后两类非完令限罔的职非负实现的 完全正性转化为前面已解决的情l ； 关键词：矩阵双非负矩阵完全正矩阵 分解分解指数 实二一次型 完全图奇圈三角形完全正图锥 坐坚l 一 a b s t r a c t a nn nm a t r i xai sc a l l e dd o u b l yn o n n e g a t i v ei fai s b o t he n t r y w i s e n o n n e g a t i v ea n dp o s i t i v es e m i d e f i n i t ea sw e l l ai sc a 1 e dc o m p l e t e l yp o s i t i v ei f ac a nb ef a c t o r i z e da sa = b b 7 w h e r ebi sn i l1 3 1 1 1 e n t r y w i s en o n n e g a l i v e m a t r i xf o rs o m ei n t e g e rm t i l es m a l l e s ts u c hl _ 1 u n l b c r1 1 1i sc a l l e dt h ef a c t o r i z a t i o n i n d e x ( o rt h ec p r a n k ) o fa w ca s e d n n 。t od e n o t et i l e s e to fa l l1 1 x nd o u b l y n o m m g a t i v em a t r i c e sa n dc 只t h es e to fa l l 1 3 n c o m p l e t e l yp o s i t i v e m a t r i c e s ， t h ec p - r a n ko fai sd e n o t e db yc p r a n k ( a ) ag l 。a p hgo ro ld e rui sc a l l e dc pi f f o re a c hm a t r i xa ( 彳 d n n ) w i t hg ( a ) ggi sc p ，r e c a l lt h a tad n n ( d o u b l y n o n n e g a t l v e ) r e a l i z a t i o no fag r a p hg i sd e f i n e dt ob cam a t r i xacd n n 。w h o s e a s s o c i a t eg r a p hi sg ；a n a l o g i c a l l y ，w ed e li n ec p ，n o n n e g a t i v e ，a n dp o s i t i v e ( s e m i ) d e f i n i t er e a l i z a t i o n so fg e a r l yi n1 9 6 3 ，m a x f i e l da n dm i n ep r o v e d ，b yu s i n gm a t r i xt h e o r y , t h a ta m a t r i xo fo r d e rl e s st h a n5i s c o m p l e t e l yp o s i t i v e i fa n do n l yi fi ti sd o u b l y n o n n e g a t i v e t h e ya l s og a v eac o u n 【e r c x a m d 】ct os h o wt h a tt h i si sn o tt h ec a s e f o rm a t r i c e so fo r d e r g r e a t e rt h a n4 ，ie ，c t ；，cd n n 。f o r “5 s t u d yo n c o m p l e t ep o s i t i v i t yo fs o m es p e c i a lm a t r i c e sb e g a ni n1 9 8 7 1 u1 9 8 8 ，k a y k o b a d u s e dt h e g r a p h i cm e t h o d t o p r o v e t h a ta l l s y m m e t r i cn o n n e g a t i v ed i a g o n a l l y d o m i n a n tm a t r i c e sa r ec p i n1 9 9 1 ，a n d os h o w e dt h a ta p o s i t i v es e m i d e f i n i t e h a n k e lm a t r i xi sc pi ft h es u b m a t r i xo b t a i n e df r o ma b yd e l e t e dt h ef i r s tc o l u m n a n dt h el a s tr o wi sa l s op o s i t i v es e m i d e f i n i t e i n1 9 9 4 d r e we ta 1 s h o w e dt h a ta s y m m e t r i cn o n n e g a t i v em a t r i xai sc pi fi t sc o m p a r i s o nm a t r i xi sa nm m a t r i x c h a r a c t e r i z a t i o no f 。pg r a p h si sf u l f i l l e db ya b e r m a ne t c t h e ys h o w e dt h a t t h ef o l l o w i n gf o u rc o n d i t i o n sa r ei d e n t i c a l ： 1 ) ag r a p hgi sac pg r a p h 2 ) e a c hb l o c ko fgi s 印， 曼幽唑坐! 竺! 坚竺坠竺堕塑堕坐l 一 3 1e a c hb l o c ko fgi si a ) m o r p h i ce i t h e rt oa k4 ( t h ec o m p l e t eg r a p ho f o r d e 。4 ) ， o rt oa 瓦( kt r i a n g l e sw i t hac o m m o nb a s e ) ( ) rt oab i p a r t i t e ， 4 ) gd o e sn o tc o n t a i na n yl o n go d dc y c l e ( o d dc y c l e o fl e n g l hg r e a t e rt h a n4 ) ， 5 ) g i sal i n ep e r f e c tg r a p h f r o mt h ed e p a r t m e n th i s t o r yo fm o r et h a ni b r t yy e a r so ft h et e s t a r c ho f c o m p l e t e l yp o s i t i v em a t r i c e s w ec ：t n s c et h a it h eq u e s t i o no fc o m p l e t e l yp o s i t i v e m a t r i c e so fo r d e rf i v ei st i l ek e ya n dw a t e r s h e do ft h er e s e a r c ho ft h eq u e s t i o no f c o m p l e t e l yp o s i t i v em a t r i c e s e x a c t l yb e c a u s eo ft h i sr e a s o n ，w em a i n l yi n v e s t i g a t e t h eq u e s t i o no fc o m p l e t e l yp o s i t i v em a t r i c e se l 、d o u b l yn o n n e g a t i v em a t r i c e so f o r d e rf i v e ，w ew i s hg e tt h eh o l eo ft h eq u e s t i o no fc o n l n l o nd o u b l yn o n n c g a t i v e m a t r i c e s i nt h i st f i e s i s ，w ef o c u so nt h ep lo b l e mo fc o m p l e t ep o s i t i v i t yo fd o u b l y n o n n e g a t i v em a t r i c e so fo r d e rf i v e f h i sl h e s i sh a sf o m - s e c l i o n s ins e c t i o nlw e i n t r o d u c et h eb a c k g r o u n do fc o m p l e t e l yp o s i t i v em a t r i c e s ，s e v e r a le q u i v a l e n t d e f i n i t i o n sf o rc pa n dr e l e v a n tc o n c e p t s t h e nw er e s t a t et h et h r e eb a s i cp r o b l e m s c o n c e r n i n gc o m p l e t e l yp o s i t i v em a t r i c e s 1 ) f i n d i n gaf e a s i b l es u f f i c i e n ta n dn e c e s s a r yc o n d i t i o nt od i s c u s sam a t r i xb e i n g c o m p l e t e l yp o s i t i v e ； 2 ) c o m p t l t i n gt h el h c t o r i z a t i o ni u d e xo fc o m p l e t e l yp o s i t i v em a t r i c e s ； 3 ) g i v e nag r a p hg ，c o m p u t i n g ，( g ) ；如) ：g ) = g , a e c r b yf a r ，n oq u e s t i o nh a sm o r ec o m p l e t es o l u t i o n i ns e c t i o n2w ei n t r o d u c es o m ed e v e l o p m e n to i lc pp r o b l e ma n dg i v es o m e n 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 m a l lm a t r i c e st ob ec p ；c h a r a c t e r i z a t i o n so f c pg r a p h sa n dt h a to fs e v e r a ls p e c i a lk i n d so fc o m p l e t e l yp o s i t i v en l a t r i c e sa r ea l s o p r e s e n t e dh e r e s e c t i o n3a n d4a r et h em a i np a r t so ft h et h e s i s ：i ns e c t i o n3 ，w e f i r s tc l a s s i f y ：h em a t r i c e si nd n n 5a c c o r d i n gt o t i r ea s s o c i a t eh e f t c pg r a p h so f o r d e rf i v e ，a n du s ee l e m e n t a r yt r a n s f o r m a t i o n s0 1 3m a lr i c e st od e s c r i b en 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 so fd o u b l yn o n u e g a t i v er e a l i z a t i o n so ft h ef i r s tf i v ec l a s s e s l v t ob ec p ，a n do b t a i nn e c e s s a r ya n ds u i t i c i e n tc o n d i t i o n sf o rd o u b l yn o n n e g a t i v e r e a l i z a t i o n so ft h e6 t hc l a s st ob ec p ，b ye m p l o y i n gs o m ek n o w nr e s u l t s0 1 1b o o k g r a p h s i ns e c t i o n4 ，w ed e a lw i t ht h el a s tt w oc l a s s e so fm a ! r i c e s ，a n dt r a n s f o r m t h ep r o b l e mi n t ot h ef a m i l i a rc a s e sw eh a v ec o p e dw i t hi ns e c t i o n3 ，b yu s i n gt h e t e c h n i q u e sr e l a t e dt os c h u rc o m p l e m e n t ，e d g e d e l e t i n gp r o c e s s ，a l l dg e o m e l r y k e y w o r d s ：m a t r i xd o u b l yn o n n e g a t i v em a t r i x c o m p l e t e l yp o s i t i v e m a t r i xf a c t o r i z a t i o nf a c t o r i z a t i o ni n d e x r e a lq u a d r a t i cf o r m c o m p l e t e g r a p h o d d c y c l et r i a n g l ec o m p l e t e l yp o s i t i v eg r a p h c o n e 符；j 约定 r ” ( ，) 一k 例 爿k = 爿陋ic t 4 0 ) = a ( n l a l n ) t 3 a ( o = 爿( _ ) 符号约定 欧氏窄问的标准内积 4 的以d 为行标，卢为列标的子矩阵( a ，卢为 ( ，- ) 的两个1 空子集) a 的以a 为行标、列标的子矩阵( a 为“) 的非 空子集) a 的以( n ) a 为行标，m ) 卢为列标的子矩阵 ( ( n ) a ，( h ) 卢为知) n q 两个非宁子集) a 的以( ，z ) 为行标、列标的予矩| j 乍( ( ，1 ) t 为 “) 疗，j 两个非卒子集) 彳：z 稿：爿中的s c h l ”补，这单一2 ( ：1 2 ：) 第i 行第j 列的元素足1 ，而其余元素是0 的，2 阶 矩阵 1 , 2 ，一) n 阶完全j f 矩阵 n 阶双= 怍负矩阵 爿的比较矩阵( m o ) 1 ，；吩i 卜川 a 是非负矩阵 a 是正矩阵 g 0 ) 中长为5 的罔的权的和 v 帆 旬 o 0 吧 跳 毗 胜拈铀 第一章简介 1 1 几个等价定义 称一个n 阶半f 定非负矩阵a 为双非负矩阵，并记所有n 阶双非负矩阵构 成的集合为d n n ，对a d a r n 。，若有非负矩阵b 满足 a = 册7 ( 11 ) 则称爿为完全正的记所有n 阶完全n 瑚i 阵构成的集合为印f 。所有使得 ( 1 1 ) 式成立的b 的最小列数称为a 的分解指数( 或爿的q ；r a n k ) ，已作) ( c p r a n k ( a ) ) 已知完全i f 矩阵有以下几个等价定义 1 设ad n n 由a 决定的实1 次型为 q ；q 0 一，x 。) = x7 叙，x ；b l ，x 。) 。月”q 称为完全】j i 二次型，如果q 叮 分解成 q = l i + - + l j ( 12 ) 其中l t = c l 石1 + c 2 k 石2 + + c 。 为非负线性型( 即。* 0 ) 删5 么a c p ，满 足( 1 2 ) 的最小的t 即为q ( 或a ) 的分解指数 2 设爿= g r a l l l ( c z l ，一，a 。) 为n n 的非负矩阵其，书o 一，a 。为r ”中的n 个向量，满足 b ，a ，j z0 ( 1 f ) 则爿；g r a m ( a ，“。) c e 当e l 仅当存在i f 交变换u ，使得 u a 。r ? ( q = 1 , 2 ，”) ，其中用为某个自然数 一个h 阶图g 称为完全正图( c o m p l e t e v ) ( ) s i t iv eg r a p h ) ，简记为c p 图，如果每一个以g 为伴随图的双非负矩阵均为完全i t ! 图g 称为无圈图， 亘堕型堑型! ! ! ：一 若g 中不含圈g 的陡为3 的圈称为g 的三角形 注：以上涉及的图均，b - - i i - - 零的简单图，关 二图的其它一些概念，参看( 2 2 ) 设a 为n 阶非负实对称矩阵，a 的伴随图g 0 ) 定义为c ( v ，e ) ，其中 v = 如) ，e ； ( f ，- ) = n ，0 ，i ；，f ，( n ) 这甩积) 定义为集合缸，2 ，一 若双非负矩阵i 满足g ) = g ，i ) f j a 称为图g 的双非负矩阵实现 个二次型q = q 0 1 ，一，z 。) 称为协正的( t o p o s t i r e ) ，如果有 q b l ) 一，) z0 ，v b ，z ，yc r ： ( 1 4 ) 矩阵a r 称为协正的如果爿是对称的并目v x r ”有x 7 a x 0 用 c o p 表示所有的m 阶协正矩阵的集合c 8 , 锥和c o p , 锥关于，z 阶对称矩阵的 空问瓯上的内积臼，b ) = t r a c e a b 是互为对偶的 b c 。为全体h 阶协正二次型对应的矩阵| ! | j 集合，则c ，构成闭的凸锥，若记 只为全体n 阶非负矩阵构成的集合( 它为凸锥) ，则有 e + s ，cc ， ( 1 5 ) 记s 。为n 阶半正定矩阵锥，j i ! i j c pc d n n 。cs 。 对于n54 ，已知有c 只= d n n 。( 2 4 ， 3 ，1 1 8 ， 9 ) 但对n 5 ，c e 为 d n n 。的一个真子集( 9 ) 因此，考察一个，zz5 阶的双非负矩阵何时为完 全正成为完全正矩阵研究的一个关键性问题 ! 三! ! j 1 2 背景知识 判断一个双非负矩阵是否为完全i f 矩阵的研究始于本世纪六十年代初， 并由m h a l i ( j r ) 在1 9 5 8 年( 】 ) 提出，之后由卜f 1 1 ) i a n a n d a 在1 9 6 3 年( 1 9 ) 7 t ：始研究完全正问题作为组台分析中的重要部分一区纰设计，的重 要内容，早在l9 5 8 年m a r s h a l lh a l lj r 的( 1 ) 中就出现过 9 6 2 年，h a l l 和m n e w m a n 从二次型和锥理论角度正式提出“完全正二：次型”这一概念并证 明了完全正锥与协正锥构成对偶锥，从而将叻f 二次型的部分结果转化到了完 全正二次型上面( 9 ， 1 9 ) 有关咖j f 矩阵的研究也是普遍关心的问题( i l0 ， 1 1 ， 1 2 ， 9 ， 1 3 ， 1 4 ， 1 5 ) ，因此，弼完全证 ：阵的研究具有_ 卜5 分 重要的应用价值和理论价值直到1 9 6 7 年山m ，h a l1 j r 的组合理论一书( 2 ) 的出版，才出现完全正矩阵这个词它的应用= 怍常广泛，涉及组合设计尤其块 设计( 1 ， 2 ) ，经济学及统计学等领域( 3 ， 4 ， 5 ， 6 ， 7 ， 8 ) 它还与在控制冷、计算机辅助几何设计( c a g d ) 等领域有重要应用 1 ，据我们所知，完全正矩阵的第个应用是区组1 ；殳计个均衡不完全设 计d 0 ，b ，r ，k ， ) 是一个试验这个试验是把v 个不同的物体“，口，口。放到6 个 块且，b ：，b 。中使得每个物体在6 个块中正好出现了，次每一个块中 恰好有k 个不同的物体任意一对不同的物体在b 个块中j f 好同时出现j l 次 ecv 区组设计可以由关联矩阵b = ( b 。) 来描述b 。= 1 如果“，口，否则 6 i = 0 b 的每一列描述一个块，含有k 个1 口的每。行描述集合t j 的一个i 素，含有r 个1 如果口是区纽发计d ( b ，r ，k ，a ) 的关联矩阵那么 4 = 肋7 = ( r 一九) ，。+ 3 i ，显然a 是完全n i 的完全正矩阵经常与下面的问题 相关联出现给出参数v ，6 ，r ，女，a 利块b i , 厅：，b ，是否存在一个区纽设计 d v , b ，r ，a ) ，且b i , b z ，e 是它的块，若a = ( ，一 ) ，。+ 。令d l ，方：，包是 r ”中的( o ，1 ) 向量，它们描述了块b ，b ：，b ，令c 是一个列山b l , b ，b ，组成 的v t 矩阵，那么，存在具有块b 。，b 。一，b ，的区组设计d ( v ，6 ，r ， ， ) 的必要条 件楚a c c7 是完全歪的 2 完全正矩阵经常用于统计学中的西方差阵，任一向鲞x = ，) 被称为相关的，如桨对任意单调增的实函数，g 有c o v ( ，g k ) ) 0 任懑随机 向鬃y 的一个多元正态分布宠全由它的数学期望向量“和l 办方差阵决定 的c h e r n i c k 提l 出的这样的猜想：y 是相关的当h 仪当e 三d n n ，在这方抠i 麓一令结采是：如巢e c p ，嬲芦是裰关的，因此c h e s n jc k 猜怒在墨4 围成 立 3 1 9 9 4 年，g e l y 撼述了有个共蚓掇毙的两个物靴进化的m a r k o v 援型 运瘸这种模型可_ 以计算正在观察的两个其意g 同禳壳的d n a 序列的溉搴， 数据是有四阶方| j 车j v 来刻划的 n = j v _ 强：a h i | n h n m i 百c e nc c n t c h 。 ( 砧 n c 懈 月f 魏：r n g t 这墨蠢，c ，g ，t 跫d n a 豹四个攀本爨减零覆，。为第个耪种是魏l 成蕈位 鼠第二个物种悬组成单位的场合的数目不同的模犁依赖于一些简单化的 假设决定一令模越镁设在某种数集上是蛋满足是缀有意恐的、在一个模型中， 我们镁设在d n a 序列中所有位攒的数掘进化率都是相同的，所有的位霞部是独 立的不相关的科个物种的跃迁矩阵是一样| 勺k e i l y 观察了矩阵n 适合模型 豹充簧象馋是n 十7 鹣；嚣望簇是宠全歪豹n 为4 酚矩黪，黟；以只须涯鞠 + 7 是双非负的就行了。 1 9 8 0 年，美翻的两位统计学家i 。j g r a y ，i ) ( ；w js o n 在为美戮豳蒙 麓源部设诗缝源後濡数掌搂型时遭到茈阀怒，鼹丽将这闷遴爵次提出，并应 用几何方法重新诞明了c e = d n n z 4 ) 这结沦( ：3 ) 1 9 8 7 年，t m a n 定义了完全正强艉概念，1 9 9 3 鼋三憾及其学生n ，k o g a n 等人宠成了对宠全茅强 的粼划( 2 0 3 ，e 2 l l ，( 2 3 ， 1 7 3 ) 1 9 9 1 年，皓。i m n 在他的练述文章( c 2 1 1 ) 翌：!l 。! ! i ： 中提出了涉及这一领域的三个基本问题如下： 1 提出一个可行的判断一个矩阵为完全计j 的充要条俐：； 2 求完全正矩阵的分解指数： 3 给定图，求 ，( g ) s 如0 ) ：g ) = g ，a c p , ， 到目前为上f j ，没有个问题有一个比较完整的答案 本文重点考察5 阶双非负矩阵的完全i r 判别，我们还综述完全正问 题在近4 0 多年的研究进展我们将在第二章归纳概括低阶( 3 、4 阶) 双非负 矩阵为完全正的若干充要条件、完全正图的刻划，和些特殊类完全正矩阵的 描述第三、四章为本文重点和创新点所在： 我们在第三章首先给出5 阶非 完全正图的分类，并利用初等变挨刻划f f 5 类非完仓f 图的完全正实现：我 们还利用书图( b c 3 0 k g r a p h ) 的有关结柴刻划了第6 类非完全正图的完全正实 现在第四章，我们利用s c h u r 补、去边矩阵和几何方法将后两类非完全矿图 的取非负实现的完全正性转化为前面已解决的情形 五阶完全正矩阼 第二章已知结论 早在1 9 6 3 年，m h a l l 干m n e w m a n 就证明，： 引理2 1 9 1 当，l 4 时，c 只= d n n 。： 2 当n25 时，c p , 。为d n n 。的真了集 随后，m a x f i e l d 和m 1d c 利用解矩阵方程x7 x = a 的力法再次证明了这 结论( 1 6 ) ，他们给出，阶数人于等 ：5 的双非负矩阵不是完全i f 矩阵的1 9 8 0 年，g r a y 和w i l s o n 利用几何方法给h j 了这一结论的”一证明( 3 ) 关于特殊矩阵类的完全f 性的研究始于1 9 8 7 年，m k a y r o b a d 利用图论 证明了对角占优情形下的双非负矩阵为完全f f 一个，z 阶( 复) 矩阵爿；k 。，) 称 为对角占优的，若有k z i 鲫f ，i c 因为i 在g 的三角形中，我们可以假设，存在订：整数 l ，m 2 ，州“ ，j + l ，1 = 川l ，”2 0 ，m ，s 埘。，否l f l j j b 。= 0 ， 由a ：b b 7 可得 令 m h l l a u = 扫n 6 ，j e cd ， 。酗 d j 。善6 i ，j g ( d ( ) ) 由( 3 3 ) 和( 3 4 ) 利用c a n c h y s c h w a r z 不等式可得 ， 堕ds 擎：，皿 ，盎，” 。 ” 叭3 3 冲“3 _ 可得三，? 嘶 因舶= 爿啦薪，j n u 所以h c c 7 ，这里c = 口( 1 i c 优，) 0 所以h 吧 2 ( 3 2 ) ( 3 3 ) ( 3 4 ) ( 3 t5 ) 2 驴叶 m f d s 2 u 仃 第二三章五阶竞争n 矩阶的土鲤结果 引理3 1 3 3 3 3 设a e d n n ，形如( 3 1 ) 式，这毕“。0 当且仪当 d e t a a i c ，j 引理3 1 4 a d n n ；，如果存在某个( i ，j ) 使得“。= 1 ( j ；j ) 那么 “e c 巴，且妒) s 4 证明 因为爿是半正定的，存在a 一，a ，r j ，使得爿一g r a ，n ( a ，“5 ) ， 由假设可知，2 f - i 发a ：= 1 ，那么我们有川= 1 ，i c5 ，和缸：，口：) ；1 ，由柯西 布涅柯夫斯基4 ；等式可得a ，；。，把，j 分块为 ： 这里爿：，= 爿( 1 ) ，c 7 = 0 。口。“。n ，) ，我 f 确爿，= ( 升“m 如：，a ，a 。，髓；) 和 爿。，e ，= c ，这里e i 为月4 的第i 个坐标向量，因为a d n n ；，所以存在某个4 x m 非负矩阵爿，使爿。= b 1 b ? ，这里m = 妒0 。) s4 ， 令 川2 m 我们有 一b 矧bb = ( c a l l l xl 川i 【cj 因为j 7 z ；p 旭b 。= p j a ，e ；= p i c n 。，：l 引理3 - 1 4 还可以这样表述：a d n n j ，若爿有一个二阶主子式为0 ， 则爿c 只 不妨设爿的为零的二阶主子式为i ：l = “。一。；= 。， “口2 = a i l a f f , “f = 扛瓦， 亘堕塞竺i ! ：堡堕 把爿的。i ( f ；1 ，。) 化为1 ，1 1 l l a 化为彳= 瓴) 毛2 夕氲卅， 设“是主对角元为1 的5 阶双j 怍负矩阵，出引理3 1 4 可知，从现在开始 我们假设n 。c l ，f ；j 如果g 0 ) 不含长为5 的圈，j t b 4 , a c c g ，弗且妒0 ) 蔓7 引理3 1 5 设爿d n n ；，且s ( a ) 中有列顶点“v 满足力0 ) 力p ) ， 则存在爿的一个去边矩阵彳，使得彳e d n n 、 证明不妨设( f ) c ( ) 1 ici 5 ，i 己 由题设可知，对w ( 5 ) ，只要，0 就有口m ，0 ，a i h j oc c + 。 现令肛；兰堡，。 0 ，从而。，0 记s ：j 一# 坍，五；s a s 7 即g 仁) ；g 0 ) ( ，) ( 注意有可能还有其它的边被删去) 由i 为双非负 知，d e t a i ，】z0 ，b u a i 。生 n wn ? 由上式可知，s ；从而边( ，s ) e g ) 故彳为a 的一个去边矩阵，且易 氮a d n n s ? 引理3 1 6 设4 = 0 。，) 为5 阶完全正矩阵，g ) 为一怍完全正图，且有 个顶点，不在三角形中，o o ) 一 不含长奇阁，彳为a 的一个去边矩阵，且 所去的边与f 不关联，则彳为完全正矩阵 证明对g 的顶点重新编吼可使得t = 5 以及( f ) ； l ，2 ，r ( 显然 1 src4 否则，= 4 ，有g 0 ) e k 。当然g 0 ) 为完全i e i 鍪1 ) ，将一分块 皿一* “一口 ，：i nm l l p 第三章五阶完伞正 _ | ：( 啡的土篮 i t i 粜 这里a = q m ，口m 0 ，o ) te r 4 4 韶 由a c 只和目i 理3 1 2 知，存在d l ，d ：，一d 0 使得 ( a ) l 口：d 1 + 口未d 2 +