《关于符号模式和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