（计算数学专业论文）关于符号模式和01矩阵的若干结果.pdf

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 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 议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 幻 o 时， 1 ，令e _ o ，则俨( i ，歹) o 这与b 2 q ) ，c 哮q ( a ) 矛盾 咄= = 1 ；当 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 七 = 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 。- _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 。_ - 。_ _ _ _ _ 。_ _ 。_ _ _ 。- 。_ _ _ _ 。_ _ _ - 。_ _ _ _ 。_ _ _ _ _ _ _ _ _ 。_ _ 。_ _ _ _ 。_ _ 。_ _ - 。_ _ 。_ _ _ 。_ _ _ 。_ _ 。_ _ _ _ _ _ _ 。_ _ _ 。_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ - _ _ - _ _ _ - _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 华东师范大学硕士论文关于符号模式和0 - 1 情形2 当6 1 2 0 时，由 c 1 2 = f6 1 七k 2 ， j b l 可知6 1 七 o ( 忌= 1 ，2 ，佗) ，这意味着6 1 七 = 1 ，2 ，几) 与k 2 ( 七= 同号的又因为a 是符号对称的，因此6 1 七( 七= 3 ，4 ，n ) 与6 强( 七= 3 ， 号的即由6 1 七( 七= 3 ，4 ，佗) 可以确定6 觋( 七= 3 ，4 ，仃) 的符号这 6 1 七 = 3 ，4 ，n ) 分别讨论 6 1 k ( 忌= 3 ，4 ，呐可以取到两种符号，那么共有护- 2 中取法根据 c 1 _ 6 1 七k ，江3 ，4 ，n ， 七= 1 当6 1 七 = 3 ，4 ，m 的符号取定时，6 1 1 6 1 七( 七= 1 ，2 ，n ) 的符号也就得到确定，再 由上式右端可知6 1 七k ( 七= 1 ，2 ，n ，i = 七十1 ，七十2 ，n ) 的符号也就取定即 k ( 七= 3 ，4 ，竹，t = 七+ 1 ，七十2 ，乱) 的符号得到确定 上述过程是对求幂等符号模式矩阵的分析，综上可知n 阶无零幂等符号模式矩阵共有 2 n 一2 2 = 2 n 一1 种 下面就3 阶无零幂等符号模式来做一个说明由于主对角元为正元素已经证明，只需 考虑其他元素 情形l当6 1 2 0 时，由c 1 2 0 得6 1 3 6 3 2 o 时，则6 3 2 0 时，由c 1 2 0 得6 1 3 6 3 2 0 ，即6 1 3 与6 3 2 同号当6 1 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 矩阵的特 征值在本章我们主要研究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 矩阵的若干结果 根据上面两个式子我们是否可以认为 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 - 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 礼时，由定理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 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 矩阵或零矩阵 证明由于秩为零的矩阵只有零矩阵又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 亡 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 在一行或者一列时矩阵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 ( a ) + ，( 两2 + 2 = 4 当矩阵a 有m 个元素为1 且m 能整除n ，但它们不同在p 行或者p 列时，类似上面的分析 有 ，_ ( a ) + t ( _ ) 2 + 2 = 4 综上可知，当矩阵a 不满足上述两类矩阵时， 7 - ( a ) + 7 ( _ ) = 1 或者 7 - ( a ) + ，i 口) 3 因此当七= 2 时，满足条件的n 阶m 1 矩阵a 只有上述类型 命题3 3 若n 阶m 1 矩阵a 满足 ，) + r ( _ ) = 3 则a 具有形式 或者 a = 0 01 1 0 01 1 1 1 1 1 1 11 1 1 10 0 1 l0 0 0 0 0 o 0 o 0 0 1 8 = ) = ( 三：三：) 华东师范大学硕士论文 关于符号模式和m 1 矩阵的若干结果 其中矩阵块a 1 1 为t p 阶的，0 t 礼，0 p 礼为正整数 证明1 阶m 1 矩阵显然不满足条件对2 阶m 1 矩阵容易验证 a = a = r ( a ) + r ( a ) = 3 并且这是全部的满足条件的2 阶m 1 矩阵 只可能出现 或者 两种情况 当礼3 时，令矩阵 a = r ( a ) + r ( 两= 3 r ( a ) = l ，7 ( _ ) = 2 ， r ( a ) = 2 ，( 才) = 1 0 01 1 0 01 1 1 11 1 1 11 1 七垮 其中矩阵块a 1 1 为t p 的，0 t n ，0 p n 为正整数容易计算 r ) + ，_ ( _ ) = 3 当矩阵a 不能分成如上的矩阵块时，不妨设在矩阵块a 1 1 中有元素1 时，矩阵a 的秩为3 ， 又因7 ( 页) 1 ，所以 r ( a ) + r ( 才) 3 】9 华东师范大学硕士论文 关于符号模式和阻1 矩阵的若干结果 a = 1 10 0 1 10 0 0 00 0 0 0 0 0 其中矩阵块a l l 为t p 的，o t n ，o p 仃为正整数可以看出 r ( a ) + ，口) = 3 当矩阵a 不能分成如上的矩阵块时，不妨设在矩阵块a 1 1 中有一个零元素时，矩阵a 的秩为2 ，又因7 ( 再) 2 ，所以 ，( a ) + ，( 页) 3 由以上分析知道当七= 3 时，满足条件的n 阶阻1 矩阵只有以上类型 、li， 您 恐 a a n 牡 a a = 2 l 参考文献 【1 】m 舢印e r ，a0 0 u r i n 咖e r a t i 叽，s p 血g e r ，b 凹l i n ，2 0 0 7 【2 】r p a s t ，p r o p e r t i c 曙0 fd a 鹤o f ( m 1 ) 一m a t r i c e sc a 、i 研n ga 百啪m a t 呶，c 缸a d j m a t h ， 3 4 ( 1 9 8 2 ) ，4 3 & 4 5 3 【3 】r b b 印a t ，t e s m 幄r h a 吼，n 叩e g a t i v em a t r i 啷锄da p p h c a t i o 璐，c 彻出r i d g eu i l i 、r e 墙姆 p r e 锵，c 彻出r i d g e ，1 9 9 7 【4 】c b e r g e ，g r a p ha n d 王b 伊e r f 印h s ，n 删睡h o u 勰d ，1 9 7 6 【5 】r b h 撕a ，m a t r i 】ca n a l y s i s ，g t m1 6 9 ，s p 血g - v 矾a g ，n 呷y 0 r k 1 9 9 7 【6 】j a b 加d y 缸du s rh 细啊；g r a p h - i h e o 觋s p 血g 日，2 0 0 8 【7 】r - a b m a l d ，r l s h 8 d 盯，m 的酏篦o fs i 驴l 、7 a b _ l eh e 缸s y s t e m s ，c a 证b t i d g eu 1 小呦 p r e 锵，c 彻蛳d g e ，1 9 9 5 【8 】r a b 洲d i ，m a t r i o e sp 锄叫t a t i n oe 删v a l e n tt 0 眦i b l e m a t r i 啷锄da p p l i 础i o n ，l i e 肛 衄dm l l l t n i n e 缸，7 ( 1 9 7 9 ) ，1 1 2 【9 】r a b n l a l d i 趾db i 加，ai a t t t i c e 目匝e r a t e db y ( m 1 ) 一m a t r i o 铭，a 瑙c 叩幽i n ，3 1 ( 1 9 9 1 ) ，1 8 孓 1 9 0 【1 0 】r a b n l a l d i 锄db l s h a d e r ，m a t r i 啷0 fs i 驴s 0 1 _ 吨b l el i n e 缸s y 8 t e m s ，c 枷d g e u n i 、坝s 时 p r 岛s c 锄b r i d g e ，1 9 9 5 【1 1 】e r c a 血e l da n db d m c k a y ，a s y m p t o t i ce n u m e r a t i o no f 睁1 ) 。m a t r i c 皓丽t hc o n s t a 础r o w 衄dc o l u m ns 衄眵，e l e c t d 叩j c 锄1 b i n ，1 2 ( 2 0 0 5 ) ，2 9 1 2 】c 1 鼬e n b a d h ，c rj o b 璐，ac 伽出i n a t o r i a lc 0 v e 】鼬t ot h ep e m m - f ￥0 b e n i 璐t h e 咖， l i n e a r 他e b r aa p p l ，1 3 6 ( 1 9 9 0 ) ，1 7 3 - 1 8 0 【1 3 】c e s 出e n b a c h ，i d 锄p o t 朗c ef o rs i 印p 砒锄m a t r i c e s ，m 咄舢g e b r aa p p l ，1 8 0 ( 1 9 9 3 ) ，1 5 3 - 1 6 5 【1 4 1d r f l l l l 【e r s o n ，a j h o 伍眦，m h m c a d - 出e w ，s o m ep r o p e r t i 既0 f 鲫h s w i t hm 1 1 l t i p l ee d g e ， c a n a d j m a t h ，1 3 ( 1 9 6 1 ) ，2 3 争2 5 5 【1 5 】a o g e l f o n d ，s o m ec o m b i n a t o r i a lp r o p e r t i 笛0 f ( m 1 ) 一m a t r i c 嘲，m a t h u s s r s b o m _ i l 【，4 ( 1 9 6 8 ) ， 1 【16 】r m h a b e r ，t 锄r a n k0 f ( m 1 ) 一m a t r i c 笛，r e n d s 锄m a t r d d o 忸，3 0 ( 1 9 6 0 ) ，2 垂5 1 - 【17 】r m h a b e r ，m i n i m a lt 锄r 舡l l 【o f ac l a 船0 f ( m 1 ) - m a t r i c 鹤，c a n a d j m a t h ，1 5 ( 1 9 6 3 ) ，1 8 8 - 1 9 2 【1 8 】f j h a l l 衄dz l i ，s i g np a t t e mm a t r i c 鹤，c h 印盯3 3o ft h eb o o k ，l h o g b 朗( e d i t o r ) ，h 衄d - b o o ko fl i n e a ra 】学e b 啦c r cp r 铭8 ，2 0 0 6 【1 9 】 【2 0 】