《关于符号模式和01矩阵的若干结果》由会员分享，可在线阅读，更多相关《关于符号模式和01矩阵的若干结果（42页珍藏版）》请在金锄头文库上搜索。
1、2 0 1 1 届研究生硕士学位论文 华东师范大学 学校代码：1 0 2 6 9 学号：5 1 0 8 0 6 0 1 0 5 l 关于符号模式和0 1 矩阵的若干结果 院系：数学系 专业：计算数学 研究方向：矩阵论及其应用 指导教师：詹兴致教授 研究生：白梁军 2 0 1 1 年4 月完成 D 碱a t i o no fM 够t e rC a n d i d a t ei n2 0 1 1 l l l 1 1 1 1 1 1 1 1 1 1 删洲I I Y 19 0 3 7 9 8 U I l i v e r 8 i 锣c o d e ：1 0 2 6 9 s t u d e n tm ：5
2、 1 0 8 0 6 0 1 0 5 1 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 nS i g nP a t t e r na n d0 1M a t r i c e s D e p a 砒m e l l t ： S p e c i a l 锣： D e p a r t m e n to fM a t h e m a t i c s C o m p u t a t i o n a JM a t h e m a t i c s R e s e a u r c hD i r e c t i o n ：M a t r
3、 议T h e o Wa n dA p p l i c a t i o 璐 S u p e r 访s o r ： C a d i d a t e ： P r o f n g z h iZ h a n L i a l I l 舀u nB 出 C o m p l e t e di nA p r ，2 0 1 1 是在华东师 除文中已经 本文的研究 华东师范大学学位论文著作权使用声明 o ，则o ( 七= 1 ，2 ，n ) ，且( 七= 1 ，2 ，扎) 不全为零若不然，不妨设 6 i 1 6 1 j ， 毛= 2 因此 = = 玩1 6 1 j + o 取实矩阵C = ( 勺) ，使得当n 幻
4、o 时， 1 ，令E _ o ，则俨( i ，歹) o ( 后= 1 ，2 ，n ) ，这意味着址( 七= 1 ，2 ，n ) 与k 2 ( 七= 1 ，2 ，n ) 是 同号的又因为A 是符号对称的，因此址( 七= 3 ，4 ，n ) 与6 姥( 七= 3 ，4 ，n ) 是同 号的即由6 1 七( 七= 3 ，4 ，n ) 可以确定6 觋( 七= 3 ，4 ，n ) 的符号这时我们可以对 6 1 七( 七= 3 ，4 ，礼) 分别讨论 6 1 七( 七= 3 ，4 ，n ) 可以取到两种符号，那么共有2 ，l 一2 中取法根据 c 1 产6 l 七k ，江3 ，4 ， 知= l 当6 l
5、七 = 3 ，4 ，n ) 的符号取定时，6 1 1 6 1 七( 七= 1 ，2 ，n ) 的符号也就得到确定，再 由上式右端可知6 1 乇k ( 七= 1 ，2 ，亿，t = 七十1 ，七+ 2 ，几) 的符号也就取定即 k ( 七= 3 ，4 ，n ，t = 七+ 1 ，七+ 2 ，n ) 符号得到确定 9 。- _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 。_ - 。_ _ _ _ _ 。_ _ 。_ _ _ 。- 。_ _ _ _ 。_ _ _ - 。_ _ _ _ 。_ _ _ _ _ _ _ _ _ 。_ _ 。_ _ _ _ 。_ _ 。_ _ -
6、。_ _ 。_ _ _ 。_ _ _ 。_ _ 。_ _ _ _ _ _ _ 。_ _ _ 。_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ - _ _ - _ _ _ - _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 华东师范大学硕士论文关于符号模式和0 - 1 情形2 当6 1 2 0 时，由c 1 2 0 得6 1 3 6 3 2 0 ，即6 1 3 与6 3 2 同号当6 1
7、 3 0 时，则 1 0 华 经 华东师范大学硕士论文关于符号模式和0 - 1 矩阵的若干结果 第三章0 1 矩阵和它的补 3 1 0 1 矩阵及其补的问题提出 关于0 - 1 矩阵的问题有很多，如皿1 矩阵的组合性质【1 5 ，2 9 】、m 1 矩阵的项秩【1 6 ，l7 】等 问题又因为m 1 矩阵为非负矩阵，因此在研究0 - 1 矩阵时还常常用到非负矩阵的知识和方 法 3 ，4 ，5 ，8 】在2 0 0 5 年，Q H u 、Y “、x z h 趿确定了给定秩的一般m 1 矩阵和给定秩 的对称m 1 矩阵的中元素1 的个数 1 9 】在文【2 5 】中则是通过对无圈图来研究m 1 矩
8、阵的特 征值在本章我们主要研究m 1 矩阵和它的补的有关问题这是导师在讨论班上提出的问 题首先来给出下面的定义 定义3 1 设A 为m 1 矩阵，我们将A 中的零元素换为l ，l 换为零元素，就可以得到一 个新的矩阵B 我们称B 为A 的补，我们把矩阵A 的补记为才也称A 和才是互补的 关于这两个矩阵有一些有趣的结论 我们先来看一个3 阶阻1 矩阵，设 那么它的补矩阵为 ，l1 I A = l1 l I11 I 1 阳 A = l00 I Oo 才氍广 r ( A ) + 7 - 口) = 6 1 2 、l-、 0 0 O 华东师范大学硕士论文关于符号模式和m 1 矩阵的若干结果 根据上面两个
9、式子我们是否可以认为 1 7 ( A ) + 7 _ ( 才) 6 成立的若是成立的，我们将上述的3 阶m l 矩阵推广到n 时，是否有 1 7 ( A ) + r ( _ ) 2 n 成立? 对此，詹兴致教授提出下面的问题： 设，：一C 是一个函数，例如秩、积和式、行列式， 问题3 1 确定 ，( A ) + ，( _ ) 的范围； 问题3 2 对于上述范围，是否对范围内的每个数七都有m 1 矩阵A 使得 ，( A ) + ，( _ ) = 七 成立： 问题3 3 如果问题3 2 答案是肯定的，那么找出所有满足 的0 - l 矩阵 在本章中，我们就上述问题 华东师范大学硕士论文 3 20 -
10、 1 矩阵及其补的秩的和 本节我们解决了问题3 1 和问题3 2 ，并部分的解决了问题3 3 定理3 2 设A 为n 阶m 1 矩阵，则 明显的 ( 3 4 ) 华东师范大学硕士论文 关于符号模式和m 1 矩阵的若干结果 因才的行列式不为零，因此它的秩为死，我们有 ，( A ) + 7 ( - ) = 2 n 这就证明了上界2 n 和下界1 都可以取到 定理3 2 回答了詹兴致教授提出的问题3 1 - 对于问题3 2 ，下面我们给出肯定的回答 定理3 3 对任意的正整数七( 1 七2 死) ，都存在n 阶m 1 矩阵A 使得 r ( A ) + r ( - ) = 七 证明当七= 1 或2 礼
11、时，由定理3 2 知 r ( A ) + r ( A ) = 七 是成立的 当1 七 2 n 时，我们分下面两种情况讨论 当七= 2 m + 1 时，令 A = 11 111 1 11 11l 1 01 111 l 00 11l 1 00 011 1 00 001 1 其中矩阵A 的前住一m 行全为1 时，这时A 的秩为n 一一m ) + 1 = 仇+ 1 易得r 口) = m ，即 r ( A ) + r ( - ) = m + 1 + m = 2 m + 1 = 后 1 5 华东师范大学硕士论文 关于符号模式和m 1 矩阵的若干结果 当七= 2 m + 1 时，令 A = 11 111 1
12、 11 l1l 1 01 111 1 00 111 1 ：。： 00 01l 1 00 000 0 其中矩阵A 的前n 一仇行全为1 ，最后一行全为零此时A 的秩为n 一一m ) + 1 1 = m 而，( _ ) = m ，因此 r ( A ) + 7 ( A ) = m + m = 2 m = 后 这就证明了定理结论 下面就取到七所有m l 矩阵A 进行刻画 设P 为置换矩阵，由于，- ( 4 ) = r ( P A ) = r ( A 尸) ，因此把A ，P A ，仰看做是同一类矩阵 命题3 1 设n 阶阻1 矩阵A 满足 r ( A ) + r ( - ) = 1 则A 为全1 矩阵或
13、零矩阵 证明由于秩为零的矩阵只有零矩阵又A 和才不能同时为零矩阵，所以r ( A ) + r ( _ ) = 1 说明 r ( A ) = 1 ，r ( A ) = o 或者 7 ( A ) = o ，r ( A ) = 1 第一种情况A 为元素全为1 的矩阵，第二种情况A 为零矩阵 命题3 2 若n 阶0 - 1 矩阵A 满足 r ( A ) + ，- ( _ ) = 2 ， 1 6 关于符号模式和m l 矩阵的若干结果 则A 具有形式 或者 ll 1 1l 1 00 0 O0 0 01 O1 ： O1 即矩阵A 中有t 个行或列的元素全部为零，且其余n t 行或列的元素全部为1 ，0 亡
14、n 为正整数 证明我们按照矩阵A 的零元素个数来分析当矩阵为1 阶矩阵时，它的秩为1 ，不用 考虑 当A 为全1 矩阵或零矩阵时，r ) + r ( _ ) = 1 ，显然不符合 当矩阵A 的零元素个数为l m n 时，容易看出当零元素在一行或者一列时矩阵A 的秩最小，此时r ( A ) = 2 ，当零元素不在同一行或者同一列时r ) 2 ，总有7 ( A ) 2 又由 于才至少有两个元素为1 ，因此r ( _ ) 1 ，也就是说 ，( A ) + ，( 萄2 + 1 = 3 矩阵A 的零元素个数为礼m 一1 ) m 佗2 时，这时矩阵A 有1 m 死个元素为1 ，当元素1 在一行或者一列时矩
15、阵A 的秩最小，此时r ( A ) = 1 ，当元素1 不在同一行或者同 一列时，- ( A ) 2 ，即r ( A ) 1 又由于才元素为1 的个数有n 一1 ) m n 2 ，这时页有 1 m n 个零元素，如前面分析r ( _ ) 2 ，也就是说 r ( A ) + ，- ( A ) 2 + 1 = 3 当矩阵A 的零元素个数为几 仇 n ( n 一1 ) 且仇不能整除n 时，矩阵A 必有两列或 者两行的元素不完全相同，此时，( A ) 2 ，矩阵才也必有两列或者两行的元素不完全相同， 此时也有r ( - ) 2 因此 r ( A ) + r ( A ) 2 + 2 = 4 1 7 华东师范大学硕士论文 关于符号模式和限1 矩阵的若干结果 当矩阵A 中零元素个数为m 且m 能整除n ，不妨设p = 7 7 l 加，但零元素不完全在这p 行或者p 列，那么A 必有两行或者两列元素不完全相同，此时r ( A ) 2 ，同时才也有两行或 者两列的元素不完全相同，此时r ( _ ) 2 因此 t
