（计算数学专业论文）关于矩阵组合分析性质的若干结果.pdf

d o c t o r a ld i s 舱r t 8 t i o n ，2 0 1l j l | i i l i | | l l i | l f m l l l | l 舢l f i l f f | | l l f f | i i f y 19 0 3 6 0 0 c o u e g ec o d e ：1 0 2 6 9 s t u d e n tn l l i n b e r ：5 2 0 8 0 6 0 1 0 1 4 e a s tc h i n an o r m a lu n i v e r s i t y r e s u l t so nc o m b i n a t o r i a la n d a n a l y t i cp r o p e r t i e so fm a t r i c e s d e p a r t m e n t ： m a t h e m a t i c s s p e c i a l t y ：c o m p u t a t i o n a lm a t h e m a t i c s d i r e c t i o n ： m a t r 泌t h e o 巧a n d i t 8a p p l i c a t i o n s u p e i s o r ： a u t h o r ： p r o f e s s o r n g z h iz h a n z e j u nh u a n g a p m2 0 1 1 s h a n g h a i ， 、。 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文关于矩阵组合分析性质的若干结 果，是在华东师范大学攻读硕士沙勾选) 学位期间，在导师的指 导下进行的研究工作及取得的研究成果。除文中已经注明引用的内容外，本 论文不包含其他个人已经发表或撰写过的研究成果。对本文的研究做出重要 贡献的个人和集体，均已在文中作了明确说明并表示谢意。 作者签名：毒睁 华东师范大学学位论文著作权使用声明 关于矩阵组合分析性质的若干结果系本人在华东师范大学攻读学位 期间在导师指导下完成的硕士博矽( 请勾选) 学位论文，本论文的研究成 果归华东师范大学所有。本人同崽华东师范大学根据相关规定保留和使用此 学位论文，并向主管部门和相关机构如国家图书馆、中信所和“知网”送交 学位论文的印刷版和电子版；允许学位论文进入华东师范大学图书馆及数据 库被查阅、借阅；同意学校将学位论文加入全国博士、硕士学位论文共建单 位数据库进行检索，将学位论文的标题和摘要汇编出版，采用影印、缩印或 者其它方式合理复制学位论文。 本学位论文属于( 请勾选) ( ) 1 经华东师范大学相关部门审查核定的“内部”或“涉密”学位 论文木，于年月日解密，解密后适用上述授权。 ( 电z 不保密，适用上述授权。 翩签名：衄 作者签名：窖艮匀嘈l 一 木“涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定 过的学位论文( 需附获批的华东师范大学研究生申请学位论文“涉密”审批表方为有 效) 未经上述部门审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学 位论文，均适用上述授权) 。 黄泽军博士学位论文答辩委员会成员名单 姓名 职称 单位备注 邵壹裕教才受i 司裔卞乓 主席 孺茅竺翻压上i 蠢- i 车沌禾嚆 l 称暑霞拳才曼垡啬、陬兆氐嘻 i i 弧i 班教寸受上f 茭盈夫营 罄一军工表才受鱼e 7 太匿 摘要 我们研究了关于m 1 矩阵、部分矩阵、符号模式、非负矩阵的几个问题 我们的工作分为以下几部分： 1 综合运用图论和矩阵论的技巧证明了：当七仃一1 时，若n 阶m 1 矩 阵a 的七次方仍是m 1 矩阵，则a 中最多有n 一1 ) 2 个1 ，a 中有 n m 一1 ) 2 个l 当且仅当a 置换相似于对角线以上元素全为1 的严格 上三角矩阵 2 确定了任意次幂仍是m 1 矩阵的n 阶m l 矩阵中元素1 的最大个数和取 到这一最大个数的矩阵当n 是奇数时这一最大个数为何+ 1 ) 2 4 ，当死 是偶数时这一最大个数为n 唧+ 2 ) 4 3 刻画了所有填充具有相同行列式的部分矩阵 4 刻画了所有填充具有相同秩的部分矩阵，确定了给定阶数的这类矩阵中 未定元的最大个数以及达到最大个数的部分矩阵这一工作与刻画给定 部分矩阵的最小秩这一未解决问题密切相关 5 刻画了如幂零符号模式，找出了缸幂零符号模式中非零元的最大个数 并刻画了取得这个最大个数的珏幂零符号模式这项工作与1 1 u r 缸图 有关 6 证明了不等式 i l a o b i l p ( b ) ， p ( a 1oa 2o oa ) p ( a 1 如a 七) ， 这里矩阵是非负的，a ob 表示a 和b 的h a d 眦矾乘积，0 a i i 和 p ( a ) 分别表示a 的谱范数和谱半径它们加强了s c h _ i l r 的经典不等式， 推广了z h a n - a 1 l d 朗a e r t 的结果 7 否定地解决了关于非负矩阵的奇异值和酉不变范数的两个猜想 本文的部分工作是与c h 盯da b n l 龃d i 教授、詹兴致教授合作完成的 关键词 m 1 矩阵，有向图，部分矩阵，a c i - 矩阵，符号模式，非负矩阵， 行列式，秩，奇异值，谱半径，谱范数，酉不变范数 a b s t r a c t w es t u d y m ep r o b k m 8o nm 1m a t r i 嘲，p a r t i 缸m a t r i c 髑，s i g np a t t e 瑚 趿dn o 皿e g a t i 、，em a t r i 馏0 1 1 i 。m a j n 麟l l ：l t s 跚旧a 8f 0 u 佣穆 1 b y 咖t e c ：m q 啷丘o m 口a p ht 蛔趿dm a t 血t h e o 觋w ep r 0 、，et t h e 心e r o f e 丑姆l ，8 i n a m l m a 土血a j s 】麟t k 皿0 r 删t o n 一1 ) 2 i f i s 幽a0 - 1m a t 血，w h e r e 七n 一1i sag i 、，e np o s i t 慨砒e g e r ，缸d t h a tt h em 嬲血叭mm m l b e ri s 批a 删i f 舭l do n l yi fai sp e r m u t a t i o n s i m i l 缸t 0t h es t r i c t l yu p p e rt r i a 丑是阻缸m a t r i ) 【a u0 f 耐h 0 即【t r i 骼a b a 、，e t h e 出啦；o n a la r eo 嘲 2 w ed 甙e r m i 】t h em a 硒皿u 珂瑚】功b e r0 fe n t r i 髑e q l l a lt oli nt h o 舱m 1 m 8 t r i 嘲0 f0 r d e rna l l0 fw 】吣眈p o w e 瑙眦皿1m 8 t r i 嘲嬲w e u 鹪t h e m a t r i 嘲t h a i ta t t a i nt b i 8m c i i m lm 加1 b e r ，w b e r et h em a 硒如u 加m m l b 盯 i s ( n + 1 ) 2 4i fn i so d da n d 死( n + 2 ) 4i f 礼i 8 咖 3 w ec b a r 喊豇i z et h ep 哦i a lm a t r i c e sa u0 fw h 伽c 0 m p l e t i o 珊h 啪t h e s 丑皿ed 甙e m i d a 卫t 4 w e 出盯喊e i i z et h ep 响a lm “嘲a o fw h 嘲m p l 甙i 0 璐h 帆t h e 8 锄er a n ka n dd e b 朗1 口j 】舱t h em a 硒m u 功n u m b e ro fi n d e t a n n i l 龇e 8i i l 8 u c hp a r t i 8 lm a t r i c e s0 fa 咖no r d e r 锄骶嬲t h em a t r i c e st h a ta t t a i n t h i 8m 由咖珊瑚d b e r t h i 8w o r ki sc 1 0 鼬l yr e l a t e dt ot h eo p e np 咖i b l e m 0 fd e t e r m n gt h em i n i m mr a 卫k0 fa uc o m p l e t i 0 她0 fag i v p a r t i a l m a t r i x 5 w - ec h 盯碱e r 溉t h ei l i l p o t e n ts i g np 8 t t 咄0 fa 西v e ni n d e x 七觚dd e t e r - m i n et h em 蚁i i n u m 删j i i b e r0 f 皿e r o 眦r i 船i ns u c hs i g np a 七t e r 衄锄 w e n 嬲t h es i g np a t t e r 璐t h a ta t t 8 i nt h i sm 由姗瑚加出e r t 1 1 i 8w o r k i 8r e l a t e dt 0t h er 1 1 u r 缸铲印h - a o b l l p ( b ) ， p ( a 1oa 2o oa 七)p ( a 1 a 2 a 七) ， w h e r et h em a t r i c 髓a r e m l e g a t i v e ，a o bd e n o t 铭t h eh a d 衄缸dp r o d u c t 0 f a 趾d b ，i 趿dj d ( a ) d e n o t e t h e s p e c t r a i l 砌趾d 印e c t r a lr 础璐 0 fa ，r 箦p e c t i v e l y t h e 五i 吼i i l e q u 址锣i i l l p r o v 伪ad a 筠i c a li i l e q u a u 蚵o f s c b l 】r ，毗l dt h e 黜o n do n eg e n e r 出岫ar e 8 l mo fz h a n - a u d e n 地r t 7 w ，e l v e 栅oc o n j e c t e 8o ns 州缸、，8 l u i 陷毗l d 诎盯n y 哳i 趿tn o 皿啕 o fn o 珈1 e g a t i v em 枷嘲皿e g a t 呐 p a r t0 ft h i 8d i 8 8 e r t a t i o ni 8j o i l l tw o r kw i t hp r o f e 鼹叫m c h a r da b m a l l d i 衄dp r o f e s s o rx i n 留l l iz h 蛆 k e y w d r 凼 阻1m a t r i ) c ，d i f a p h ，p a r t i a lm a t r i ) 【，a c i - m a t r i ) c ，s i g np a t t 眦，n o m l e g a t i 、伦m a t r i ) 【，d e t e r m i n a n t ，r 砸l k ，咖g u l 盯v a l u e ，8 p e c t r a lr 8 m u s ， 8 p e c t r a l l d r m ，l m i t a r i ：i y 曲砌趿t 础) r m 目录 摘要 a b 8 t r a c t 第一章给定次幂仍是m 1 矩阵的m l 矩阵 1 1 问题描述、图论意义和主要结果 1 2 主要结果的证明 1 3 更多的结论 第二章任意次幂仍是m 1 矩阵的m 1 矩阵 2 1 问题描述、图论意义与主要结果 2 2 主要结果的证明 第三章所有填充的行列式都相等的部分矩阵 3 1 部分矩阵与a c i 矩阵 3 2 所有填充的秩有界的a c i - 矩阵和部分矩阵 3 3 非奇异a c i - 矩阵与非奇异部分矩阵 第四章所有填充都有相同秩的部分矩阵 4 1 引言 4 2 所有填充都有相同秩的a c i - 矩阵与部分矩阵的刻画 4 3 所有填充都有相同秩的部分矩阵中未定元的最大个数 4 4 两个未解决问题 第五章幂零符号模式 5 1 定义与问题描述 5 2b 幂零符号模式的刻画 5 3 缸幂零符号模式中非零元的最大个数 i 赶 1 1 4 6 9 9 2 7 7 1 7 2 2 3 2 8 9 9 0 3 ； 暑 1 1 4 璩 加 玲毖 盯盯组 盯 弛 s ；! 弱眈 铝 衙符 目录 第六章非负矩阵的h a d 衄瞰d 积 6 1引言 6 2 关于谱半径的一个不等式 6 3 关于谱范数的几个不等式 6 4 两个猜想的反例 参考文献 攻读博士学位期间完成的论文 致谢 7 5 7 5 7 6 7 9 8 4 8 6 8 8 8 9 第一章给定次幂仍是阻1 矩阵的皿1 矩阵 1 1 问题描述、图论意义和主要结果 1 1 1问题描述 。 m 1 矩阵是元素为。或1 的矩阵我们记n 阶m 1 矩阵的全体为 o ，1 ) 对给定的正整数n 和七，记 r ( n ，七) = _ 【a 霸 o ，1 ) i 小 厶 o ，1 ) ) 并记m 1 矩阵a 中元素1 的个数为，似) ， ，y ( n ，| ) = 麟 ，( a ) i a r ( n ，七) ) 2 0 0 7 年詹兴致教授在讨论班上提出以下问题： 问题1 1 对给定的正整数n 和七，确定，y ，七) 和r ，后) 中元素1 的 个数为7 ( 死，七) 的m 1 矩阵 r ( 佗，七) 中每个矩阵元素1 的个数在区间【o ，y m ，七) 】中事实上，若 a r ( n ，七) 中1 的个数为，y ，忌) ，m 是【o ，7 ( n ，七) 】中的一个整数，则在a 中 将7 ( n ，七) 一m 个1 变成。我们得到瞻1 矩阵a 1 r ( n ，七) 且其中1 的个数为 m 问题1 1 中七= 2 的情形已经被武宏琳【2 0 】解决她的结果是： 们= p 若n 是奇数， 若n 是偶数且铊4 ， 若n = 4 并且她刻画了取到这一最大值的皿1 矩阵我们将解决问题1 1 中七n 一1 的情况 2 第一章给定次幂仍是阻1 矩阵的0 1 矩阵 1 1 2图论意义 m 1 矩阵与图论密切相关，通过定义邻接矩阵建立图和m 1 矩阵的一一对 应关系，我们可以通过阻1 矩阵来研究图的相关性质，也可以通过图来研究 阻1 矩阵的相关性质本章我们将综合运用图论和矩阵论的技巧 在本章中，我们讨论的有向图允许有环但没有平行弧，有向图的圈和途径 分别指有向圈和有向途径我们采用【3 】和 5 】中的术语对有向图d ，d 的顶 点的个数和弧的条数分别称为d 的阶数和大小 对关于顶点1 ，2 ，n 的有向图d ，我们定义其邻接矩阵a ( d ) = ( ) 螈 o ，1 ) ，其中= l 当且仅当( f ，歹) 是d 中的一条弧反过来，我们可以 同样定义n 阶m 1 矩阵a = ( ) 的有向图d 似) ：d ( a ) 的顶点为1 ，2 ，扎， ( i ，j ) 是d 似) 中从i 到歹的弧当且仅当叼o 对给定的正整数n 和七，记r ，( n ，七) 为关于顶点l ，2 ，n 的满足以下条 件的有向图d 的集合：任给i ，j ，l i ，歹死，d 中最多有一条从i 到歹长为 七的途径记丫( n ，七) 为r ，( n ，七) 中最大有向图的大小显然对a o ，1 ) ， a r ( n ，七) 当且仅当d ( a ) r ，( n ，七) 考虑m 1 矩阵的有向图，问题1 1 与以 下问题等价： 问题l 1 对给定的正整数n 和七，确定y ，七) 和r ，七) 中大小为 y ，七) 的有向图 显然，7 ( 死，七) = 丫( 佗，七) 1 1 3 主要结果 记 为n 阶上三角竞赛矩阵 我们的主要结果是 瓦= 0 三) 定理1 1 设死和七是给定的正整数，n 5 且七n 一1 则，y ( n ，七) = n 一1 ) 2 并且矩阵a r ( n ，七) 满足，) = n 一1 ) 2 当且仅当a 置换相 1 1 问题描述、图论意义和主要结果，一 3 似于冗 如果有向图d 中没有环并且任意两个不同的顶点之间都恰有一条弧，则 我们称d 为竞赛图若对d 中任意三个顶点仇，陬，吻) 和( 吩，) 是d 中的弧意味着他，) 也是d 中的弧，则我们称d 为传递的显然n 阶竞赛 图d 是传递的当且仅当其顶点可以重新标号为1 ，2 ，n 使得( i ，歹) 是d 中 的弧当且仅当i j f 关于竞赛图的两个有用的参考文献是 1 0 】和 1 6 】一个n 阶有向图是传递竞赛图当且仅当其邻接矩阵置换相似于瓦定理1 1 等价于： 定理1 1 设n 和七是给定的正整数，n 5 且七n 一1 则y ( n ，七) = n 伽一1 ) 2 ，有向图d r ，( 竹，七) 的大小为死 一1 ) 2 当且仅当d 是传递竞赛 图 4 第一章给定次幂仍是阻1 矩阵的0 - 1 矩阵 1 2 主要结果的证明 本节我们给出定理1 1 的证明我们称长为p 的圈为p 圈对n 阶矩阵 a = ( ) 和正整数1 t 1 t 2 蟊礼，我们记a 【f l ，训为a 的行 指标和列指标为i 1 ，蟊的子矩阵，a ( z ) 为删除a 的第t 行和第i 列后得到 的几一1 阶子矩阵 记a 的转置为a t 我们将反复地用到以下三条等价性质： ( 1 ) a r ( 佗，七) ； ( 2 ) a ? f ( 佗，忌) ； ( 3 ) 对任意置换矩阵p ，p a p t r ( n ，七) 引理1 2 设a r ，七) 则关于d ( 舢有以下必要条件 ( i ) 若七2 ，任意两个环不能由一条孤连接若七3 ，任意两个环不能 由一条长为2 的途径连接 ( i i ) 若七2 ，环和2 - 圉不相交若七3 ，环和禾圈不能由一条孤连接 ( i i i ) 若七3 ，环和孓圈不相交 ( i v ) 若七2 ，任意两个2 圈不相交若七3 ，任意两个二圈不能由一 条弧连接 ( v ) 若七2 ，不存在i ，歹，t ，t 歹使得i _ t 和t _ t 是d ( a ) 中的弧，且 i j _ t 是d ( a ) 中一条途径 证明我们只证( v ) 而省略其余几种简单情形的验证若= j ，( v ) 是( i ) 中的一种情形；若t = i ，( v ) 是( i i ) 中的一种情形现在我们假设i ，j ，t 互不相 同，t _ i 和t _ t 是d ( a ) 中的弧，且i + j jt 是d ( a ) 中一条途径对 七2 ，我们有如下两条从t 到t 的长为七的不同途径： 这与a 七螈 o ，1 ) 矛盾 口 引理1 3若a r ( n ，七) 且b 是a 的m 阶主子矩阵，则b r ( m ，七) f 一r 斗1 o j 一 一 斗 _ 1 ，i_，、-l 1 2 主要结果的证明 证明删除d 似) 的任意n m 个顶点和与这些顶点相连的弧我们得到 r ，( 仇，忌) 中的一个图这一引理从矩阵观点来看也是显然的 口 引理1 4 若七2 ，则7 ( 2 ，七) = 2 证明由引理1 2 的( i ) 和( i i ) 我们有7 ( 2 ，七) 2 考虑任意2 阶置换矩 阵我们得到7 ( 2 ，七) = 2 口 引理1 5 若七3 ，则7 ( 3 ，七) = 4 证明设a = ( a 巧) r ( 3 ，七) ，( a ) 5 考虑a 中元素1 在以下四个互 不相交的集合中的分布： 口1 1 ，口毖，口h 口1 2 ，口2 1 ，【口1 3 ，口3 1 ) ，【口荔，口3 2 ) 我们 知道存在i 1 ，j 1 ，i 2 ，j f 2 ，【蕾1 ，j 1 ) i 2 ，j 2 ) 使得 啦l 矗= 啄l = 12 皿2 力= i 2 我们分三种情况讨论：i l = 歹l ，i 2 = 如；i 1 = 歹1 ，1 2 j f 2 ；i 1 j l ， 2 歹2 情形1 ：藿l = j 1 ，t 2 = 如若有必要我们可以进行置换相似变换，不失一般 性可以假设i 1 = a = l 和 2 = j f 2 = 2 考虑a 的2 阶主子矩阵，由引理1 3 和引理1 4 我们有 口1 2 = 口2 1 = 0 ，口1 3 + 铂l + 0 黯1 ，吻+ 0 3 2 1 a = 订 6 从而，( a ) 4 另一方面，令 第一章给定次幂仍是m 1 矩阵的m 1 矩阵 ，l 1 i b = loo lo 1；) r ( 啪， 则b 是幂等矩阵且，) = 4 这样我们就证明了，y ( 3 ，七) = 4 口 弓i 理1 6 若七3 ，则，y ( 4 ，七) = 6 证明假设存在矩阵a = ( ) r ( 4 ，七) 使得，( a ) 7 记t t 7 ( i ) = l ( + i ) 一如果存在某个t 使得凹( t ) 2 ，则由引理1 5 ， ，( a ) = t u ( t ) + ，( a ( ) ) 2 + 4 = 6 ， 矛盾所以对t = l ，2 ，3 ，4 都有埘( t ) 3 我们根据d ( a ) 中是否有环来分两种情形讨论 情形1 ：a 的主对角元全为0 由于 n 1 2 ，口2 1 ) ， 口1 3 ，口3 1 ) ，_ 【口1 4 ，口4 1 ) ， 口船，口3 2 ) ， 口丝，a 4 2 ) ，【妞，口4 3 ) 子情形1 ：a = ( 主：熹童孝) 和 子情形2 ：a = ( 三：熹童喜) 1 2 主要结果的证明 a 幢引 口m = 1 兮 口也21 兮 这里_ 表示利用圈1 2 _ 1 构长为七一3 的途径在后面的部分里我 们省略相似的解释所以o m = 0 ，从而口船= 1 由于 f _ 2 _ 1 叶2 3 口2 32 1 兮1 _ 2 _ 1 _ 4 3 i 我们有口船= 0 从而口3 2 = 1 但是 ， 1 _ 1 _ 2 1 2 口弛= 1 冷c i 1 4o 3 _ 2 矛盾 子情形2 若n 2 3 = 锄= 1 ，则交换第1 行与第2 行，再交换第1 列与第2 列可以将a 转换为子情形1 所以我们只需讨论口+ 口m 1 的情况由引 理1 2 的( i v ) ，口3 1 = 0 4 4 2 2 一 j - 一r 3 2 1 4 一 o _ _ l 1 2 3 一r o 寸 _ 2 2 l 1 一 叶 一 _ ，ljll-一，-j l l l 8 第一章给定次幂仍是m 1 矩阵的m 1 矩阵 a ) 设口m = 1 则口船= 0 由引理1 2 的( i v ) ，口4 2 = o 由于伽( 3 ) 3 ，口3 2 ，咄，a 铂中至少有两个为1 但是由引理1 2 的( i v ) ，口弘= 口鸽= 1 是不可能的从而口3 2 = 1 并且咏和a 4 3 两个中恰有一个为1 从 ，( a ) 7 我们得到口4 l = 1 但是这样会有两条有相同起点和终点的长为七的 不同途径 i _ 2j1 _ 3 _ 2 | 一2 4 _ 1 2 ， 、 矛盾 b ) 设o m = 0 由引理1 2 的( i v ) ，n 2 3 + n 3 2 1 ，咄+ 1 由 3 + ( a 嚣+ 口3 2 ) + ( 口3 4 + 口鹞) + 口4 1 + 嘞= ，( a ) 7 我们有口4 l = 口4 2 = 所以口船= 0 ，口3 2 = 矛盾 、l、 t 0 l 嘶0 1 0 0 钒 1 0 衄o 0 1 0 钆 ，-i-i_l-i一 = a 、，j， t o o 缸0 3 3 1 屹0 蚴 2 2 1 0 衄 毗 o l 0 毗 ，-iii-一 = a 1 2 主要结果的证明 j 9 - a 怔引 a = ( 熹三量奏) a = 100 0 0 口2 4 0 3 20 口鞋 口钇口铅a “ 由引理1 2 的 ) ，口2 4 + 姒2 1 ，+ a 4 3 1 由 3 + 知2 + a 4 4 + ( 锄+ ) + ( a 飘+ 口鹳) = ，( a ) 7 1 0 第一章给定次幂仍是阻1 矩阵的m 1 矩阵 由引理1 2 的( i ) 我们有口烈= 蚴= 0 从而 = 口弘= 姒z = 1 净 三二三：三二三， 这样我们就证明了，y ( 4 ，七) 6 另一方面，取 b = o1 1 、 l 三圳州4 ， l o o o 则b 是幂等矩阵且，( b ) = 6 所以，y ( 4 ，七) = 6 口 引理1 7若七4 ，则，y ( 5 ，七) = 1 0 若a = ( 叼) r ( 5 ，七) 满足 ，( a ) = 1 0 ，则对l i 5 有= 0 ，对l i j 5 有叼q t 证明设b r ( 5 ，七) 考虑j 5 i 的五个4 阶主子矩阵j e i ( i ) 中元素1 的个 数，i = 1 ，5 b 的每个非对角元在这些主子矩阵中出现3 次，每个对角元 出现4 次设b 有d 个对角元为1 由引理1 3 ，所有b ( i ) r ( 4 ，七) ，由引理 1 6 ，俾( i ) ) 6 ，i = l ，5 所以我们有 5 3 陟( b ) 一司+ 4 d = ，( b ( i ) ) 5 6 = 3 0 i = l 从而 j ，( b ) 1 0 一菩1 0 另一方面，碍坛 o ，1 只有一个元素为1 ，而七5 时砖= o ，且，( 露) = 1 0 从而7 ( 5 ，七) = 1 0 从以上的证明中我们知道，( a ) = 1 0 意味着对任意1 t 5 有= o 和，( a ( t ) ) = 6 接下来我们证明对i j 有叼叼 首先我们证明对i 歹有+ 啄1 反之假设存在i j 使得 叼= = 1 不失一般性我们设n 1 2 = 眈l = 1 记伽( i ) = 釜1 ( 叼+ 啄) 一 1 2 主要结果的证明 i 1 1 a 叫 0 2 5 ，a 5 2 ) ， 口3 5 ，口弱) ， o 侣，口弘) 我们知道存在歹使得口j 5 = 口5 j = 1 由引理1 2 的( i v ) ，歹2 所以3 j 4 设口3 5 = 口黯= 1 由引理1 2 的( i v ) ， 0 = 口1 3 = 口3 l = a 船= n 3 2 = a 1 2 5 = 口5 2 a ：，毒，喜辜i 喜、 1 0 = ，( a ) = ( + 啄) 1 j 5 我们知道每对，q ，l i j 5 中恰有一个为l 而另一个为0 所以对 i j 有叼啄 口 引理1 8 设七4 ，a r ( 5 ，七) 若，( a ) = 1 0 ，则a 置换相似于死 1 2 第一章给定次幂仍是m 1 矩阵的m 1 矩阵 证明 设a = ( ) 由引理1 7 ，对l t 5 有口馘= 0 ，对1 i 歹5 有咛 记a 中第t 行元素l 的个数为r ( i ) = 墨1 则r ( i ) 4 且1 0 = ，( a ) = 薹l t ( t ) 为了证明引理1 8 我们只需证 p ( ) 忙= 1 ，2 ，3 ，4 ，5 ) = o ，1 ，2 ，3 ，4 ) 这又等价于7 - ( f ) ，( t ) 对任意i t 成立容易看出在以上条件下a 置换相 似于死这里和接下来的部分我们需要这样一个事实：矩阵对称位置的一对 元素在置换相似变换后仍在对称位置，即如果矩阵g = 慨，) 和p 具有相同阶 数，p 为置换矩阵，p g p = ( b ) 且k = 趵，则k = 筋，即对角元在置换 相似变换后仍是对角元 首先注意到a 不能有两行行和为4 ，否则存在i 歹使得风，= q i = 1 如 果存在i t 使得f ( t ) = 7 ( t ) = 0 或7 ( t ) = r ( t ) = 1 ，则要么存在1 缸 5 使得7 ( t ) = r ( ) = 3 或2 ，要么a 有三行行和为1 接下来我们说明这三种情 况都不会出现 情形1 ：存在i t 使得r ( ) = ，( ) = 3 不失一般性设t = 1 ，t = 2 ，若有 必要可进行置换相似变换，我们不妨设 则 爱 口驰21 兮 口铀21 号 所以口m = 嘶= 0 ，与鲰n 4 3 矛盾 情形2 ：存在i t 使得r ( t ) = r ( t ) = 2 本质上有以下两种情形 4 4 3 3 一r j 一 一 2 3 2 4 _ 一r r o ，工，工 1 1 一r 寸 寸 寸 5 5 5 5 j r r 一 2 2 2 2 _ o 斗 一 ，-i-，、-_l，-_l，、-l 1 2 主要结果的证明j 则 子情形1 ， 口乳= 1 口鹳= 1 _ 4 1 _ 2o 4 一l - 4 _ 1 _ 3 _ 4 1 5 _ 2 4j 1 ( _ 2j4 1 一) 一3 5 _ lj2j 4 ( 一1 2 4 一) 一3 1 3 这里我们用每个顶点都有到3 的弧的孓圈1 _ 2 _ 4 1 来得到两条长为七 的不同途径所以咄= 嘶= 0 与咄矛盾 子情形2 ， 此时我们有 矛盾 情形3 ： a 1 2 ，口2 1 ) ， o a 有三行行和为1 不失一般性设r ( 1 ) = ，( 2 ) = r ( 3 ) = 1 由于 1 3 ，口3 1 ) ， 口2 3 ，a 3 2 ) 中每一对至少包含一个l ，利用( 1 ) = r ( 2 ) = 、liiliiill-， 5 5 o 0 蚴 蚴o t 4 o 1 弛0 1 1 o 咄 1 o o o 1 o 0 o 1 1 ，j-i_-i-一 = a ，j l_l，iil，、_【 号 令 、liiiiliil-、 5 5 0 1 蚴 蚴0 4 4 0 1 船0 的 1 o o 咄 1 0 l 0 o 0 0 0 1 1 ，i_i-i-一 = a 1 1 一 一 4 5 _ o 2 2 o 寸 1 工 1 一r _ 5 5 斗 - ，iiii，、_一 1 4 第一章给定次幂仍是阻1 矩阵的阻1 矩阵 a ：， ：莩葶三喜、 1 2 主要结果的证明 1 5 其中等式成立当且仅当a ( t ) 置换相似于7 k 1 下面我们计算a ( 1 ) ，a ( 2 ) ，a ( m ) 中1 的个数a 的每个非对角元在这 些主子矩阵中出现m 一2 次，而每个对角元出现m 一1 次设a 有d 个非零 对角元，d o 利用( 1 1 ) 我们有 ( m 2 ) m ) 一d 】+ ( m _ 1 ) d ：妻似) m 堕掣( 1 2 ) i = 1 一 由此有 似) 掣一老掣 ( 1 3 ) 从而( 1 3 ) 表明7 ( m ，七) m ( m 一1 ) 2 另一方面，霹_ 1 o ，1 ) 只 有一个1 在( 1 ，m ) 位置且七m 时孺= o 从而焉r ( m ，七) 另外， ，( 焉) = m ( m 一1 ) 2 所以，y ( m ，七) = 仇( m 1 ) 2 假设a r ( m ，七) 满足，( a ) = m ( m 一1 ) 2 且其仇个m 一1 阶主子矩阵 为a ( 1 ) ，4 ( 2 ) ，a ( m ) 由( 1 3 ) 我们有d = o ，进一步由( 1 2 ) 和( 1 1 ) 我们 知道对每个i = 1 ，2 ，m 有，( i ) ) = ( m 一1 ) ( m 一2 ) 2 从而( 1 1 ) 等号成 立的条件意味着每个a ( i ) 置换相似于岛一1 应用引理1 1 0 我们断言a 置换 相似于焉反之，若a 置换相似于焉，则对七m 一1 有a r ( m ，七) ，并且 ，( a ) = 仇( 仇一1 ) 2 口 注1 1当1 n 4 时定理1 1 的结论并不成立由于7 ( 1 ，七) = 1 ，当 七2 时，y ( 2 ，七) = 2 ，并且七3 时7 ( 3 ，七) = 4 ，公式，y ，七) = 佗一1 ) 2 对 n = 1 ，2 ，3 不成立n = 4 且七3 时公式，y ( n ，忌) = n 一1 ) 2 成立，但元素 1 的最大个数能在不置换相似于噩的矩阵上取到，例如 ，1 o1 i b ：1 0 11 i o o o i oo o 、 r ( 4 ，七) 1 6 第一章给定次幂仍是m 1 矩阵的m 1 矩阵 1 3 更多的结论 本节我们利用定理1 1 来确定7 ( n ，佗一2 ) 和，y ( n ，n 一3 ) 定理1 1 1 设n 6 则 1 ( 叩一2 ) ：坐- 1 证明设a r ( n ，n 一2 ) ，a ( 1 ) ，a m ) 是a 的n 个n 一1 阶主子矩阵 由引理1 3 ，每个a ( i ) r m 一1 ，n 一2 ) 由假设，n 一1 5 对a ( t ) 应用定理 l ! ：曼里垒塑笙鲨 一 1 7 _ 二：i = 一二：一： ： 定理1 1 2 设n 7 则 ，y ( m 一3 ) ：掣一2 证明设a r ( n ，n 一3 ) ，a ( 1 ) ，a ( n ) 是4 的n 个n 一1 阶主子矩阵 由引理1 3 ，每个a ( i ) r 一1 ，n 一3 ) 由假设，佗一1 6 对a g ) 应用定理 1 1 1 我们有 ，( a g ) ) 鱼l 二掣一1 ，i ：1 ，n ( 1 6 ) 设a 恰有d 个对角元为1 计算a ( t ) ，i = 1 ，n 中1 的个数，利用( 1 6 ) 我 们有 脚m 帕叫d = 喜似胁 学一1 一2 ) 【，( a ) 一d 】+ 唧一1 ) d = f ，( a g ) ) ni 坚尘二芝掣一1f 删掣一笺 掣乩 ，( a ) 掣一2 小阵针， 则，( a 1 ) = 亿( n 一1 ) 2 2 且 牡( 三名2 ) 叫叩卜 这样我们就证明了，y ( 死，佗一3 ) = 扎一1 ) 2 2 口 由定理1 1 1 和定理1 1 2 ，我们可能猜想对2 七n 一2 有 ，y ( n ，七) ：兰鱼与二堕一( 礼一知一1 ) ( 1 7 ) 但这一猜想并不成立如1 1 节所描述，武【2 0 】关于矩阵平方的结果说明了 1 8 第一章给定次幂仍是0 1 矩阵的阻1 矩阵 们证明，y ( 1 0 ，4 ) 和7 ( 1 1 ，4 ) 中至少有一个不满足( 1 7 ) 式反之，设，y ( 1 0 ，4 ) 和 7 ( 1 1 ，4 ) 都满足( 1 7 ) ，即 ，y ( 1 0 ，4 ) = 4 0 ，7 ( 1 l ，4 ) = 4 9 设a r ( 1 1 ，4 ) ，a ( 1 ) ，a ( 1 1 ) 是a 的1 0 阶主子矩阵由引理1 3 ，每个 a ( i ) r ( 1 0 ，4 ) 由假设，似( i ) ) 4 0 ，i = 1 ，1 1 设a 有d 个对角元为1 如前所述 1 1 9 ，( a ) 一司+ 1 0 d = ，( a o ) ) 1 l 4 0 = 1 从而 似) 警一言等 t 2 且在d ( g ) 中存在途径连接眠和吼，这与i i ) 矛 盾接下来如果g 的第i 2 块行不是零行，则存在某个t 3 t 2 使得a ：，i 3 = 1 且a 。= 0 由于阶数，l 是有限的，如此继续我们最后会找到一个零行 若g 有零行，则g 从而4 置换相似于形如 ( ：) 的矩阵，其中y 的阶数为n 一1 a e ( n ) 意味着y e 一1 ) 对y 用归纳 假设，a 置换相似于形如( 2 3 ) 的矩阵若g 有零列，则g 从而a 置换相似于 o 幸 iozj 其中z 的阶数为n 一1 a e ( n ) 意味着z e 一1 ) 对z 用归纳假设我 们得到a 置换相似于形如( 2 3 ) 的矩阵这样我们就完成了引理的证明 口 注2 1 以上证明中的性质i ) 和i i ) 已在【1 9 ，定理4 4 】中出现此外，【1 9 ， 定理4 7 】说明e ( 扎) 中的矩阵要么是置换矩阵，要么有零行或零列我们对这 些性质给出了更为简单的证明 由于每个置换矩阵都相似于基本循环矩阵的直和，由引理2 4 我们有如 下推论 推论2 5 设a e ( n ) 则a 是对称矩阵当且仅当a 置换相似于 m a g ( a l ，也，a ) ，其中a 都为。或1 或q 推论2 5 说明问题2 1 对无向图来说是平凡的 2 6 第二章任意次幂仍是m 1 矩阵的m 1 矩阵 设兀 o ，1 ) 是平方仍是阻1 矩阵的扎阶严格上三角m 1 矩阵的集合对矩 阵a ，我们记( t ，j ) 为小的( i ，歹) 位置的元素如前所述，( a ) 表示a 中元 素1 的个数 引理2 6 设佗是给定的正整数则 删悱啪肛 嚣萋意萋： 证明i ) 若n 是偶数，设n = 2 m 我们先证明 ，( a ) m 2 + m 一1 ，v a 乃机 o ，1 ) ( 2 5 ) 对m 用归纳法若m = l ，则 山= 是死 o ，1 中唯一的非零矩阵且，( 山) = 1 = m 2 + 仇一1 下面设m 2 且 ( 2 5 ) 对所有小于仇的正整数成立将a 【0 ，1 ) 分块为 a = 其中口，6 阳一1 ) ，1 o ，1 ) ，q = o 或1 a o ，1 ) 意味着b 正如一1 ) 【o ，1 ) 从而由归纳假设， ，( b ) ( m 1 ) 2 + ( m 一1 ) 一1 在本章接下来的部分我们将反复地利用以下事实：若z ，可是 o ，1 p 中的 向量且其内积伽，) 1 ，则z 和中总共最多有d + 1 个分量为1 注意到斧( 1 ，2 m ) = 矿6 1 意味着口和6 中最多存在2 m 一1 个元素1 ， 我们有 ，( 口) + ，( 6 ) + ，( q ) 2 m 从而 ，( 枷= ，( b ) + ，( 口) + ，( 6 ) + ，( 0 f ) ( m 一1 ) 2 + ( m 一1 ) 一1 + 2 m = m 2 + m 一1 ， 、lill-， q 6 0 矿b 0 0 0 0 ， a = ( ：o ) 尬m t 。，l ， ”r o 卜m 一们刮a 加m ) = 一+ m 一1 = 警# - 1 i i ) 若，l 是奇数，则存在某个非负整数仇使得n = 2 m + 1 注意到 丑 o ，1 ) = o ) ，对m 用归纳法，类似地我们有 另一方面，令 其中 ，(