（应用数学专业论文）整数完全正矩阵及其应用.pdf

摘要 摘要 完全正问题研究源于1 9 6 1 年，其应用涉及不等式理沦、统讣学、 组合设计、线性经济模型等。给定一个n 阶元素为非负整数的矩阵爿，爿 称为整数完全正，如果存在一个 m 阶非负整数矩阵b ，使得爿= 船7 成立。若曰是( 0 ，1 ) 一矩阵，则4 称为一个 0 册一完全正矩阵，并简记a 为 0 ，q 一印。对应曰的最小可能的列数卅称为爿的整数完全正指数，类似 定义 0 ，1 一指数。此时若b 的每列恰含有r 个1 ，则称该分解是r 一一致 分解。如果对每个非零、非负n 阶对角矩阵d ，矩阵爿一d 非 0 ，u 一印矩 阵，则称 0 ，1 - - c p 矩阵“为最小 o 册一印。记印r n 础t 爿和叩m 础j 爿分 别为爿的整数完全_ j = 指数和 0 ，1 卜完全正指数，缩写为r 七。爿和 m 础 0 1 1 j 4 。 判断整数完全分解( 或 0 册一印分解) 的存在性，即给定一个矩 阵一，判断爿是否为整数完全正矩阵( 或 o ，l 一印矩阵) 为p 一矗n 耐问 题，至今为止它仍然是个公开性难题，而求分解指数更是一个挑战。 本论文分为四章。第一章主要介绍整数完全i f 背景知识和它的 应用，特别洋细地介绍它在区组设计中的应用。第二章从整数完全正 矩阵的定义出发讨论了。般整数完全正矩阵的性质。第三章考虑低阶 整数完全正矩阵( 阶数hs4 ) 。首先我们给出了低阶矩阵( hs4 ) 的 整数完全正分解( 或 0 ，1 卜印分解) 的有关结论以及其分解指数的刻 画。我们证明了n = 2 ，3 时，爿_ n i 】z r 为完全正的充要条件；对于 n ：4 时，我们对几类特殊情形进行了讨论。最后我们还考虑了。些特 殊类型的整数完全正矩阵( 或 o ，1 ) 一印矩阵) 和它们的性质。在第四 i 整数完全i e 矩阵段其应用 章中我们首先刻画了一致 o ，1 一印矩阵的一些性质，然后给出了一个矩 阵是最小 0 ，1 ) 一c p 矩阵的一些充分和必要条件，最后我们给出了 0 ，1 一 分解指数的估计界。 关键词：完全正矩阵；分解指数； 0 ，i 卜整数完全正分解；一致 0 ，1 ) 一 整数完全1 1 j = 分解；最小 0 ，1 ，一整数完全币分解。 a b s t r a c t a b s t r a c 嚏 t h ep r o b l e ma b o u t c o m p l e t e i yp o s n i v em a t r i c e sh a sb e e n r e s e a r c h e ds i n c e19 6 1 c o m p l e t e f yp o s i t i v em a t r i c e sh a v es h o w n t h e r i m p o r t a n c e i nt h e s t i j d y o fb l o c k d e s i g n s i nc o m b i n a t i o n a l a n a l y s i s ，p r o b a b i i i mi n e q u a | | t yt h e o r y ，s t a t i s t i c s ，e c o n o m i cm o d e l se t c r e c a t h a ta nn nm a t r i xai ss a i dt 0b e m p ，e 招妒p o s 衙怕i ft h e r e ex i s t san o n n e g a t i v en mm a t r i xbs u c ht h a ta = b b t h es m a i l e s t s u c hn u m b e rmi sc a e dt ，e 自c 南，妇f j 0 ，7 ，仃c ，e * 0 raa n dd e n o t e db y c p 厂a 门m 1 fbi s a ( 0 1 ) 一m a tr i ) ( ，t h e n ai s c a i i e d 以7 ，c d m p e i 台0 ， _ p d s m 怕a 叫i sd e n o t e db y 徊7 ，一c p ai sc a i l e dr - u n ，o 厂m 阡bi sa ( o ，1 ) 一m a t r i xw i t hr1 si ne a c hc o i u m n ，a n dc a | l e dm 加f m a ，| f ，f o re v e r y n o n z e r on o n n e g a t i v en nd i a g o n a im a t r i xd ，a di s n o t 0 ，1 卜c p s - m i i a r l yt h ef a c t o r i z a t i o ni n d i c e so fn o n n e g a t i v ei n t e g r a ia n dt h a to f 0 ，1 卜c p m a t r i c e sa r e r e s p e c t i v e l y d e n o t e d b yc p r a 仃眨4 a n d c p r a 门f 芦，i ns h o n ，a n b aa n dr a 几，以 1 - od e t e r m i n et h ee x i s t e n c e0 fac o m p l e t e i yp o s i t i v e i n t e g r a i f a c t o r i z a t i o n ( o r 0 ，1 卜c o m p i e t e l yp o s i t i v ef a c b r i z a t i o n ) o fag i v e n m a t r i xi san p - h a r dp r o b i e ma n dh a sr e m a i n e do p e nt in o v v m o r e o v e lt 0c a i c u i a t et h ef a c t o r i z a _ c i o ni n d e o fam a t r i xh a sb e c o m e e v e nm o r ec h a e n g i n g t h i s p a p e rc o n s i s t so f f o u rc h a p t e r s i nc h a p t e ro n e ，w e i n t f _ o d u c es o m en o t i o n sa n da p p i i c a t i o n sa b o u ti n t e g r a ic o m p i e t e l y p o s i t i v em a t r i c e s s p e c i f i c a yw es h o wt h e i ri m p o r t a n ta p p c a t i o n i n b i o c kd e s i g n si nd e t a i nc h a p t e rt w o ，w ed i s c u s ss o m ec h a r a c t e r s0 f i n t e g r a lc o m p l e t e l yp o s i t i v em a t r i c e sb yt h e i rd e f i n i t i o n s 1 nc h a p t e r t h r e e ，w ea t t e m p ts t a r t i n gw i t hm a t r i c e sw j t ho r d e rn om o r et h a n4 w e f i r s tc h a r a c t e r i z et h ei n t e g r a jf a c t o r i z a t i o n sa n dt h ei n d i c e s ( o r 0 ，1 卜 整数完全正矩阵及其应用 c o m p i e t e i yp o s m v ef a c t o r i z a t i o n s o fm a t r ；c e sw 时、o r d e rn om o r et h a n 4 t h e nv v ep r o v et h a tw h e nt h i so r d e r ，7i s20 r3 ， t h e r ee x i s t sa s u f f i c i e n ta n dn e c e s s a c o n d i t i o nf o rag i v e nn o n n e g a 蠢i v em a t r i xw i t h o r d e rnt ob ec o m p i e t e i yp o s i t i v e ，a n dw h e n 门= 4 。w et u r nt od i s c u s s s e v e r a i s p e c i a i m a t r i c e s0 f t h i so r d e r 1 n c h a p t e rf o u l w ef l r s t c h a r a 烈e r i z e卜u n i f o f m o ，1 卜c pm a t n c e s ， t h e nw eo b t a i ns o m e n e c e s s a r yc o n d i t i o n sa n ds u f f i c i e n tc o n d i t l o n sf o ram a t r i t ob e m i n i m a i 0 ，1 ) - c p ，a fl a s tw ep r e s e n ts o m eb o u n d sf o r 0 ，1 ) 一r a n k s k e y w o r d s ：c o m p i e t e i yp o s i t j v em a t n ：f a c t o r ；z a t i o ni n d e x l o ，1 卜c p ： u n i f o r m 0 ，1 一c p ：m i n i m a i 0 ，1 卜c p 址 记号 ( o ，1 ) 一向量： 所有元素为o 或l 的向量 ( o 1 ) 一矩阵：所有元素为o 或l 的矩阵 爿： 爿7 ： 4 陋】 集合 1 2 ，n ) 矩阵4 的逆 矩阵爿的转置 爿的指标集为a 的子阵 爿( a ) ：爿的指标集为a 的补集的子阵 ： ， b 在爿中的s 曲耵补 c e ： 所有以阶完全正矩阵构成的集合 c p 阳n 刖：爿的完全分解指数 d e t o ) ： 爿的行列式 剧州。：所有胆阶双非负矩阵构成的集 硪口g ( 一，口。) g 似) ： 合 行阶以“l i 一，口。为主 对角元的对角矩阵 ；l 阶第f 行第j 列为l 其余元素为o 的矩阵 方阵爿的关联图 g c d ( ，6 ，c ) ：整数n ，6 ，c 的最大公约数 f n d ( x ) ：向量z 的指标，即i n d ( 盖) j ： j n ： ；m a x i s 卿( z j ) i ：l sjs n ) h 阶所有元素全部为1 矩阵 ，l 阶属于指标集为a 的元素 鄙为1 其它元索为0 的矩阵 m a x 扣，町：在数，6 中取最大元 m i n 扣，6 ) ：在数n ，6 中取最小元 j 靠以( 爿) ：爿的记忆，即矩阵爿的 列向量支撑最小值 r ：所有实数元素构成的集合 尺：全体非负实数元素构成的集合 r ”枷 r 口n m ： 朋珂t ，4 ： r 口舭) ，4 s 一印： s ( 爿) ： 仰哔) 州) z ： z 。： z ”期： z 所确n 阶元素为实 数方阵构成的集合 所有月阶元素为非负 实数方阵构成的集合 彳的秩 爿的非负整数分解指数 爿的( 【) ，1 ) 一分解指数 可s 的完全分解 爿的所有元素和 向量x 的支撑， 即，y 中非零元素个数 彳的逊 所有整数元索构成的集合 所有非负整数元素构成的集合 所有元素为整数的 矩阵构成的集合 所有元索为非负整数 的矩阵构成的集台 独创性声明 y 7 6 5 s 6 s 本人声明所呈交的学位论文是本人在导师指导下迸行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得睡弘订或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名：j 缸 n 签字日期： 沙年 月卜日 学位论文版权使用授权书 本学位论文作者完全了解鸣j 肇大专有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权壤j 杈越以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：毫茁t 唣 导师签名：红每可 签字日期：矽年月 1 一日签字日期：衍年r 月d 日 学位论文作者毕业去向：、多；太鼍 工作单位： 电话：f 妒6 “占37d 、 通讯地址：雪木专窃弓阿露研；钎之。1 弘叶邮编：1 h 吗t 第一章引言 第一节背景知识 第一章引言 1 1背景知识 1 9 3 7 年柯召和朋b 胁，( 哈代f 加脚，学生) 证明了对给定的任意一个整数二 次型q ( z ) ，存在整数s ，使得 j q ( z ) = s z 7 爿z = l ；0 ) + 上；( x ) + t t + l ：0 ) ， ( 1 1 ) 工f ( 工) 一口，1 2 1 + 杯，2 石2 + + 口x 。，以z 。 ( 1 2 ) 1 9 6 2 年凸胁d ap m 重用不等式理论考察了一个实非负二次型能够分解 成若干个非负线性平方和的问题，即q 0 ) 可写成 q ( 砷- 三：( x ) + l ：( 工) + + ：o ) ， ( 1 3 ) l f ( 工) - 口j j 石1 + 盘f 2 x 2 + + n 。石。， v f 盘“o ( 1 4 ) 的情形，他证明了：ns 4 时，q 0 ) 满足( 1 3 ) ，( 1 4 ) 当且仅当q ( x ) 为非负半币定 二次型。 设q 0 ) 为实二次型， q 0 ) 一q 0 1 ，一，z 。) = z 7 血= ；( x ) + + 三：0 ) ， ( 1 5 ) 己f ( x ) = 口。l x l + 口，2 工2 + 口。，耳v i ( 1 6 ) v f ，j ，口i 为非负整数，即n 。z + ，此时爿称可整数分解。 一般地，设s 是r 的子集，彳称为可s 一分解，如果彳= 邱7 ，其中 日- ) ，且v f ，j ，s 。b 可能的最小列数称为爿的s 完全分解指数，记为 r 玎k 爿；如果s 为非负数组成集合，那么称爿为可s 的完全正分解，记s 一印。 整数完全正矩阵段其艘用 很明显，如果s r r ，且爿是可s 分解的，那么爿一定是可r 分解的 且旭，l k 彳阳础，爿：当s = r ，可s 分解的矩阵即是半n 。：定矩阵；当s = z 时 z 一分解矩阵即是出肘o ，抛 1 0 、，面 1 3 和肋钟舯 1 5 1 研究的整数分解矩阵 当s ；r + ，r + 分解矩阵是完全正矩阵，电为印：当s = r + 时，我们把5 分解矩 阵称为s 一印矩阵：当s = z + 时，5 一c p 的矩阵即为整数完全正矩阵：特别当 s 一 o ，1 ) 时，s 一肇矩阵即为 o ，1 ) 一完全正矩阵。 一个 o ，1 ) 一叩矩阵称为最小的，如果对每个非零非负，z ，l 阶对角矩阵d 爿一d 不是 0 ，1 ) 一印的。一个 o ，1 ) 一印矩阵爿称为，一一致的，如果它能分解为 爿= 肋7 ，这里阜是个 o ，1 ) 矩阵且b 的每列恰含r 个l 。此时，该分解称为r 一致分解。称一个h 阶半正定非负矩阵彳为双非负矩阵，并记所有n 阶双非负矩 阵构成的集合为d 。，记所有n 阶完全f 矩阵构成的集合为c 只。m 肋肛打和 m 店嗍，7 提出并证明了当月s4 时，c 只= 删。和当n 5 时，哦为d w 。的 真子集。利用以上记号对于一个实二次型q 0 ) ；z 7 舭q 可分解为形如( 1 5 ) 和( 1 6 ) 当且仅当爿c e 。 蔓二塞! i 童，。 一一：。 塑= 卫鳖墼垄竺里坌墅箜：氅塑生旦 1 2 整数完全正矩阵的应用 整数完全正分解在区组设计( 又称块设计) 、不等式理论和搜索矩阵理论等 方面有广泛的应用，本节主要讨论它在区组设计中的应用。 一问题提出 设有一块地用作某一作物3 种不同品种彳，占，c 的试验用。若浚地划分成如 图的( n ) 和( 6 ) 所示，则可能由于自然条件差异，使试验4 i 准确。较合理的试验 方案如图( c ) 所示 爿 曰 c 彳口c 爿启c c爿b bc 爿 ( c ) 二区组设计 上面实验方案( c ) 采用的是均衡不完全区组设计思想。更一般地，设 丑= 协。，x ：，z ，) 为试验对象的数目。 辑谤均筏不完全捐区组设、诗0 8 a i a n c e d | n c 。m p | e e8 | o c kd e s i g n ，缩写为 尉日功指的是由石中子集构成区组的集合，6 为区组的数目，即设为 x ，x ：，z 。，满足以f 条件： ( 1 ) 每组有石的t 个元素，即l 0 = t ； ( 2 ) x 中的每一元素在b 区组中f 好出现，次； ( 3 ) 任意一对属于x 的元素在6 区组中正好出现九次： ( 4 ) 任意一对区组的含公共元素的个数恰为肛个。 满足以上条件( 1 ) ，( 2 ) ，( 3 ) 的均衡不完全设计聊，记为( v ，6 ，k ，a ) 一设 计。 整数完全i ；= ：矩阵及其应用 利用上面的定义，图( c ) 区组设计可以写成( 3 ，3 ，3 ，3 ，1 ) 一设讨4 。 如果个区组设计满足上面条件( 1 ) ，( 3 ) ，我们称该设计为( v ，七， ) 一设计。 容易看出( p ，a ) 一设汁是( v ，6 ，r ，九) 一设计的推广。对应地，满足( 2 ) 和( 4 ) 的 设计，称为p ，r ，肛) 一设计，或称p ，r ，“) 一共轭设计。 注：( 1 ) 以上参数并非完仝独立。事实上，我们有肪：v r 。 ( 2 )七 o ，注意到 h ：，矢口有口1 l i d e t ( ：i 塞里| 表示整除斓a 记c2 半五z 鸭z - c ( 锄， 4 也珈z2 可知结论成立。 下面从矩阵元素的和来考察完全正矩阵的整数分解的性质。 定理2 3 设n n 阶矩阵爿= o 。) ，盯_ ) 。乏n “。如果4 可以完全正整数分 解，则存在，1 个正整数c ，c z ，c m 使得u 口) 2 善。； 证明： 因为爿可以完全正整数分解，即存在m 个向量卢，卢：，卢，使得 爿= 卢。卢? + 卢：卢；+ - - + 卢。芦三 ( 2 5 ) 在( 2 5 ) 式两边芹乘e 7 和右乘e ( 这里e = ( 1 ，i ) 】：) 得到 e 7 爿e 皇e 7 ( 卢1 卢j + 卢2 卢；+ + 以雕弦。善。7 卢z 雕e2 善8 7 成。7 成) 72 善( e 7 卢c ) 2 f 面令c 一2 e 7 卢- 易知c 是正整数，那么。= 。荟。口。，爿e 。善。? 。 口 例2 4 当a 研) = 4 时，o 口) 一1 2 + 1 2 + 1 2 + 1 2 = 2 2 故元素和等于4 的矩阵为 完全正矩阵只可能为两个。 一个是对于每个f 有慨i = 1 ，故 爿2 瞄习42 习n 。 + z 0 】 0 ：另一个是只有一个例= 2 ，故 爿。 11 。囝 1 m 但是定理z 。的条件不是充分条件。 例z - s 设t2 胡，。_ ，= s = ，2 + ，2 + 2 ，但是爿不是整数完全正矩阵。 整数完全正矩阵搜其应用 第三章 o ，1 一完全正矩阵 3 1 一般 o ，l - 完全正矩阵 称爿是 o ，1 ) 一完全正矩阵，如果爿能够写成 爿= b b 7( 3 1 ) 这里口= ) 且 o ，1 ，在( 2 1 ) 中口的最小可能列数称为爿的 o 册一分解指数， 记r 口n 七 0 i 爿n 因为 0 ，1 ) c z + c r + r ，故有 m 矗七 u 1 4 乏，啦，出z + 4 己i 印，口n 七0 4 ) 芑阳儿七( 一) ( 3 2 ) j 4 我们也注意到，一个 0 册一印矩阵，它的所有主子式都是 0 ，u c p 的。 对任意非空子集a t n ，这里c n ) - ； l 2 ，一 ，设j 。是，l h 阶( o ，1 ) 矩阵， 它的第i 行第列元素为1 当且仅当i ，j o ，此时集合n 称为，。的支撑，记为 泐。) 。 例虫n ，h = 4 ，a = 1 ，3 ，_ ，。= 10 00 1o o o 1o 00 l0 o 0 。兰j n = 时，j 。= j 这里厂是，l 阶全l 矩阵。 从定义不难看出爿是 o ，1 一印当且仅当 4 = z 1 - ，码+ z 2 - ，a 2 + 。+ x s ，a j ( 3 3 ) 这里_ ，x z ，z ，z + ，称( 3 3 ) 为爿的一个j 表示。注意到( 3 - 3 ) 知，j 表示 即为彳的秩为1 的，表示参见【3 】) 。明显地，在3 3 中善_ 最可能小的值为 爿的 0 ，1 一分解指数，此时称这个，表示为爿的最小i ，表示。 每个 o ，1 - 完全正矩阵与一个集合组态相联系。设爿一脚7 ，这里口= 鲰) 是 苎三兰i ! ：! ! ：塞全垩堑堕 一 釜= 羔：二墼! ! ：! ! ：塞竺! ! 堡壁 一个n k 阶( 0 1 ) 一矩阵，定义一个集合组态( x ；x l ，x 。) ，满足 x = v 1 ，p 2 ，) = 】u x 2u u z 。，x 。= pj 爿：b v ；l ( 3 4 ) 定理3 1 设爿= 爿7 = z y 。那么爿是 0 ，1 一叩当且仪当存在一个集合 组态僻；x 1 一，x 。) ，使得 k n x ，j = 口# ，v 1s i ，s n ( 3 5 ) 且吲。i n = 阳舭 0 1 ) 爿。 证明：( 必要性) 设爿一肋7 ，口一( ) r ， o ，1 ，则构造x = 饥，y ：，一，v 。) ， x f p ，：= 1 ) ，f 一1 ，2 ，n 。则x x 且 阮n x 小m ：= 一1 ) i ；t b “，b “，= n 。 ( 这里c ，表示内积，下同) 其中6 。1 表示口的第f 行( f = 1 ，2 ，一，n ) 。 ( 充分性) 设有一个集合组态( x ；x 一，x 。) 满足( 3 5 ) ，则我们记m 一例 且记x = p 。，v ：， ，并作( o ，1 ) 一矩阵口= ( ) 使得 铲传 则c 6 ，6 力 _ i x fn 爿j i = 口口，v 1 f ，s n ，从而有爿= 肋7 。 推论3 2 设爿一。 z ：”是 o ，1 ) 一印，那么 。己i ，v 1s f ，s 心 口 ( 3 6 ) 而且阳础爿m a x 扣：1 s j 5 盯) 。 证明：设爿是 0 ，1 一印。由定理3 1 可得存在一个集合组态叫；五，x 。) 使 1 ；n x ，j = 口口，v 1 s i ，jsn ，工。n x ，x ， 故口口= l x ；n z j ls p 。i = ，v 1s f ，js n 且r “以4z m a x 恤1 s fsh a口 整数完全正鲁| ! i 阵发其成用 性。 注3 3 条件( 3 6 ) 对于n ；2 的情形也为充分的，但对n = 3 时，不满足充分 例s a 爿；臣ii 】，满足条件。e l 但足爿不是似u 一叩a 事实上，彳 是 o ，1 卜- c p ，则由定理3 1 知有组态皤；x ，x ：，盖。) 使得l 。n x ：【= 眵zn x ，i = 3 ， 陋，n x ，l 一1 。不妨设x ，= n ，v ：，h ，x ：= v ，v ：，v 。，y 。 ：由i = 5 zn x ，i = 3 知 v 。，v ：，v ，中至少有2 个属于x ，从而有l 一口，= 陋，n x ，i z2 。矛盾，故爿不是 o 1 ) 一印。 注3 5 对任意厅， 印m ，删：爿c 只是有界的( 参见 3 ) 。然而，条件( 3 5 ) 暗示着i x f | = 。v f = 1 2 ，n ，所以对任意n ， m 础) 爿：爿叱 无界。 注3 6 一个 0 ，1 ) 一印矩阵一定是整数双非负矩阵，但逆不真。( 例3 8 给出 反例) 注3 7 ( 1 ) 如果爿= 肋7 是爿的一个 o ，1 ) 一c p 分解且口经适当列置换得到c ，那么 以= c c 7 也是彳的一个 o ，d 一印分解，但是这个两个分解对应同一个i ，表示： ( 2 ) 爿；砉工，。嘻t 卢。雕可以写成爿“p 1 ，。，卢s d s 田1 i 一，卢s r 这里 卢，一卢。，而且珐= 垅n g “，如) 因为所有一大于0 ， 所以 ，行七，4 = ，谊n 七( 卢1 ，8 5 ) 。 蔓二童! ! ：! ! ：塞全互堑堕 塑= 旦二些! ! j ! ：薹竺：互堑竖 例3 8 爿= 11 12 0 1 0o 1o o 0 1o 21引是整数双非负矩阵 121 o 13 但1 不是 0 ，1 卜印矩阵。 事实上，反设爿是 o ，1 ) 一c p 矩阵，则由定理3 ，1 知有组态皤；爿l ，x ：，x ，x 。，x 5 ) 。 那么z 1 = ”l ，x 2 = v 1 ，v 2 ，x 3 = p 2 ，h ) ， x 4 = b ，p 4 ，x 5 = q ，y 4 ，”5 ) ： 陋：n x ，i = 1 ，而n ：sm o ，矛盾。 注3 9m 臌扰打和m 胎提出并证明了当以4 时，c e d 心和 当，l 5 时，c 只为d 。的真子集。但是这个结论对 0 ，1 ) 一印矩阵不成立。 例。- 。爿2 ：； 2 ：0 一习，一是整数完全正分解和整数双非负 但由推论3 2 可知，爿不是 0 ，1 ) 一印。 定理3 1 1设爿是非奇异 0 ，1 一印矩阵，有一个形如( 3 3 ) 的j 表示，有 而且如果 s “m 0 。1 k ) s 1 ，i = 1 ，s s “m 0 “b ) 。1 ( 3 7 ) ( 3 8 ) 刃么x j = 1 。 证明：设卢i 是 o ，1 卜c p 向量，使得卢。；，。，那么 爿一，矿x ，i ，q + b ，一1 ) ，。 也是 o ，q c p ，故写成b 。口? ( 这里e 是一个( o ，1 ) 一矩阵) 。下面考虑0 + 1 ) 0 + 1 ) 矩阵五2 品0 】，如果b 2 r ： 那么五= b 口7 ，故五是似q 一印a 特别地， 整数完全正矩阵及其应用 当爿是半正定因为爿非奇异，故形；1 一卢_ a 一1 鼠也是半正定( 这里形表示爿在 j 中的s 曲u r 补) ，所以1 z 卢- 爿一1 成= s “m 口一陋】) 。故得到( 3 7 ) 成市，如果对某 个i 有( 3 8 ) 等号成立，下证工j = 1 。事实上，( 3 8 ) 成立当且仪当矩阵 爿一p 。= z ，成卢- + k l 礁 ( 3 9 ) - - ，l 是奇异的。由注3 7 得r 口础( 爿) = r 口础( 【卢t ，卢。】) = ，l ，因为4 是非奇异，如果 x 。) 1 ，那么由( 3 9 ) 得： r h 七( 爿一卢。卢_ ) = m ，l 七0 ，一，卢，卫= 玎 与爿一成卢，奇异性矛尉。 口 注意到z 。1 不是等式( 3 8 ) 成立的充要条件。 例3 1 2 爿= 七，。是一个n 阶数量矩阵，t 是一个大于，l 的自然数 那么爿一。丢l 。s “m 。1 陋 ) ：譬s 量c 1 ，v 。z n c a ) ，但爿有唯一j 表示 u l + + u 。 墨三雯! ! ：! ! ：塞全垩塑堕， 。 蔓：j 羔堕鍪! ：! ：! 塑! ! ：! ! ：塞全要笙堕 3 2 阶数小于3 的 o ，1 卜完全正矩阵 对爿z y ，当。：1 时，爿 。 ； 1 ，川阳，这啦! 的个数是。当。；。时 1 1 j 我们有 口 = o o 7 。注意到对任意一个正整数n ，取爿= 【n 】z # 1 ，由拉格朗同定 理知m n t z + 陋】4 ，但同时，鲫七( 0 j 陋】= 口，从而口= m 舭j 【“ z m 舭z 陋 o 对 4 1 ，2 ，3 时，上式中等号成立。对日= 4 ，有r n 七 。， 【4 = 4 m 舭z 【4 一1 。对口，4 ， 有m 础小卜口z m 础z ，从而知( 2 7 ) 中等式成立当且仅当日= 1 ，2 ，3 。 当h ；2 时，可以直接由推论3 2 得到： 定理3 1 2 设爿；l j z ：。2 且；，那么1 是 o ，1 卜印当且仅当 l 口2 l4 2 2 i 口1 2 s m i n 扣口2 2 ) ( 3 1 0 ) 且，口，l 露t o ，l ，爿= “1 1 + n 2 2 一口，29 证明：设爿为 o ，1 - 印，则由定理3 ，l 知，存在集合组念似；x 。，x ：) 使得 陋，n 石：1 ；口。：从而n ，：= l 盖。n x 。l s p i = n ，即n ，zs “1 1 0 同理可证s “：。 反之，设( 3 1 0 ) 成立，记口1 = d 1 1 4 1 2 ，口2 一“2 2 一n 1 2 t 则 爿2 玄 + n ，z ，忆z ，2 n ，t t ，+ n z ，t z ，+ 。z j ”。 从而4 为 o ，1 ) 一c p 。由上式不难得出： m 以一蔓口l + 口2 + d 1 2 畜+ n 2 2 一d 1 2 。 另一方面，由于对任一集合组态暖；x ，x ：) 有盖u ：e 爿，故 i 石l 芑i x ，u x ：1 = i x ，i 十阻：l l x ，n 爿：i = a l i + “：z 一曲： 从而m 础 爿苫口+ 口2 2 一1 2 。所以r 口舭 i ) - j j 爿= “1 1 + 口2 2 一“1 2 。 口 整数完全硅矩啡灶应用 当，l ；3 时，有下面的定理 蜀t 瑁s 。- s 蕾t 爿。蓐l ；ii i z ：“3 ，蕾t ，n = m ；n t n - ，n ，n ”， 定理3 1 3 设爿= i 口1 2 口2 2 日l z ，设m = m i n 慨2 ，n 口2 3 ) ， i 口【3 口2 3口3 3j ，= m a x 0 ，口1 2 + 口1 3 一口1 l ，1 2 + 以1 3 一日2 2 ，植+ “凹一“3 3 ) 那么爿是 o ，u 一印当且仅当m m ，在这种情况下， 旭咒七t 【l ，1 ) 一；口1 1 + 口2 2 + 3 3 一“】2 一口1 3 一n l 召+ m ( 3 1 1 ) ( 证明参见 2 。) 推论3 1 4 设爿是一个n n 阶 0 ，1 卜叩矩阵( 当月3 时) ，设 口一m i n 如“：1 s f sn ) ，那么爿一n 也是 0 ，1 ) 一掣，这里是n 阶全1 矩阵。 证明：当月：2 时可直接有定理3 1 2 得出：当n = 3 时有定理3 ，1 3 得出。 口 称爿为n 阶对角占优矩阵，如果爿；k l 。，n iz n u ( v i ；1 ，2 ，n ) 。 二； 定理3 1 5 设爿= 4 7 z ? 是对角占优，那么一是 0 ，”一印，在这种情况下， ，谊n 七帆。，爿= 主f r ( 爿，一；盯 这里盯是爿的所有元素和，即。一y 日一o 。 ( 3 1 2 ) 证明：设爿是一个，z 阶对称非负对角占优矩阵。爿的关联图g ) ；( 矿，e ) 其中顶点集矿= y ，v ：，v 。) 且，“j ) ，顶点v 。与顶点v ，之间存在“f ( 或口，) 条边。v f ，定义_ * 口“一n 如果，o ( 因为爿是对角占优矩阵) ，在每个顶点v ioj 我们添加个环。设边集e = 托，p ：，p ， ，这阜边集包括环，每个环只计算一次。 那么我们有 z 。砉+ 砉蓦n a2 罢砉n 。一；善“2 兰打，一三c ，。 墨三里! ! ：! ! ：塞竺匡堑堕 笙：羔堕塑! ：主! 塑! 堡! ! ：塞全垩堑堕 设曰是g ) 的关联矩阵，即口；( ) 是一个n m 的( o ，1 ) 一矩阵，且 铲忙穗，一纷，崩闩如m 因为一脚7 ，所以4 是 o ，1 一叩且r n 以七) 爿s 小。下面证明阳n 七 。j 弘一m 。因 为在4 的形如3 3 的，表示中m 础伸，一表示善_ 的可能最小值，我们可以得出 在对角占优矩阵最小，表示中，有m a ) ( h l s2 ，o = l ，2 ，s ) 。相反地，假设式( 3 3 ) 包含一个和项，不妨记- ，。使得h = 七，2 。因为爿是对角占优矩阵，所以在式 ( 3 3 ) 中对任意f ( j 口) 存在七一2 个和项， n 。这七仲一2 ) + 1 和项 t ，。，j 廿，+ 一，t ，甜， i a 、- - ， 能够被 尼 一1 ) 个和项，似，i ，a 替换。但是 七( 女一1 ) c 七 一2 ) + 1 ，矛盾。 故爿的最小j 表示形如： 月= 工l j 口+ 工2 j a 2 + + + b j 嘶 这里x 。是自然数且h i s2 ，( f ；1 ，2 ，5 ) 。对每个n ，设反是一个( o ，1 ) 一向量使得 侈。雕= j 扩令 曰霉 卢，一，卢。，p ：，一，卢：，。，卢，一，j b ，】 、，一、，r 一、，一 z i1 x 那么曰是g 口) 的关联矩阵，所以 这里仃= y n 。，。 t 。 加n 。m 爿一骞置= 聊= 吾肛( 4 ) 一丢。 口 整数完全正矩阵投其应用 一个h 阶方阵爿称为妇矩阵，如果它形如 这里口。r ，6 。 0 。 纯一2 口6 h 6 h 一1n ( 3 1 3 ) 定理3 1 6 设爿是一个整数非负妇所矩阵，形如( 3 1 3 ) ，那么爿为一个 0 ，1 j 一印当且仅当爿是对角占优。这时 m 疵伸m 爿。荟q 一善6 ( 3 1 4 ) 证明：如果彳为对角占优，那么出定理3 1 5 得月是 o ，l 卜印且满足( 3 1 4 ) 。 如果爿是 o ，1 ) 一c p ，那么爿得每个主子式均为 o ，1 一印。对f = 2 ，3 ，h l ，以的3 3 子阵州l l i ，f + 1 】是 o ，1 一印，由定理3 1 3 ，我们有 。m i n 0 ，b - 1 扣i _ ：0 己m a x 0 ，岛一i 一口川，6 h + 6 ，一订，6 ，一d ) 三m 从而推出口。z 峨_ l 口，也一l + b 。，n 。b 。这样一是对角阵。 口 一个实矩阵爿- r 称为2 带的，如果对所有f ，使得一爿 2 ，爿满 足n 。；o 。即形如