（基础数学专业论文）关于disjunct矩阵的一些构作.pdf

摘要 本文利用完全图和仿射空间构作了六类d i s j u n c t 矩阵( 定理2 1 1 一定理3 2 ) 所得结 果具有良好的d i s j u n c t 性质然后在单纯复形上构作了矩阵 4 ( ) ，并在尬( ) 的行的基 础上增加 卵( ) 得到了一个新矩阵 矗( ) ( 定理4 2 ) ，证明了它是d i s j u n c t 矩阵并且当 1 r 七时，计算了 磊( ) 的任意两个至多7 列集的并的h a m m i m g 距离，证明了 尬( ) 可以纠正一个错误；而当2 7 t 七时计算了尬( ) 的任意两个至多r 一1 列集的并的h a m m i m g 距离，证明了 磊( ) 可以纠正两个错误最后利用区组设计构造了 一个d 8 一d i s j u n c t 矩阵( 定理5 1 ) ，从而可以对实验结果进行纠错和检错 关键词：d i s j u n c t 矩阵完全图仿射空间区组设计t 一填充单纯复形 l a b s t r a c t f i r s t l y w ec o n s n u c ts o m ed i s j u n c tm 撕c e so nc o m p l e t e 聊h 粕da f f i n es p a c e ( t h e o r e m 2 。1 1 一t h e o r e m3 2 ) ，t h er e s u l t sh a v eg o o dd i s j u n c tp r o p e r t y n e x t ，w ec o n s t r u c tam a t r i x 尬( ) o ns i m p l i c i a lc o m p l e x ，锄dg a i nan e wm a t r i x 尬( ) a st h a tw h i c hr e s u l t sb ym w a u g m e n t i n gt h em a t r i x 尬( ) w i t h 酊( ) ( t h e o r e m4 2 ) w r ep r o v et h a ti ti sad i s j u n c tm a t r i x ， 卸dw h e n1 7 t 七，w ec o m p u t et h eh a m m i n gd i s t 锄c eo f 觚yt w ou n i o n so fa tm o s t rc o l u m n si n 朋- r ( ) ，觚dp m v et h a t 4 ( ) c o u l dc o r r e c t 卸e r r o r ；w h c n2 7 亡 七， w ec o m p u t em eh a m m i n gd i s t 锄c eo f 觚yt w ou n i o n so fa tm o s tr lc o l u m n si n 坼( ) ， 锄dp r 0 v em a tm ；( ) c o u l dc o l l 广e c tt w oe n 0 r s f i n a l l y w eu s eb 1 0 c kd e s i g nt oc o n s l n l c tad e d i s j u n c tm a t r i x ( t h e o r e m5 1 ) ，i tc o u l dc o r r e c ta n dd e t e c te r r o r si nt h et e s tr e s u l t 1 【e y w o r d s ：d i s j u n c tm 枷xc o m p l e t eg r a p h 椭n es p a c eb l o c kd e s i g n 芒一p a c k i n gs i m p l i c i a lc o m p l e x i v 学位论文原创性声明 本人所提交的学位论文关于d i s j u n c t 矩阵的一些构作，是在导师的指导下，独 立进行研究工作所取得的原创性成果。除文中已经注明引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和 集体，均已在文中标明。 本声明的法律后果由本人承担。 论文作者( 签名) ： 劢b g 年y 月6 同 材宁 黼孙施州 埘脬y 只6 r j 学位论文版权使用授权书 本学位论文作者完全了解河北师范大学有权保留并向国家有关部门或机构送交学 位论文的复印件和磁盘，允许论文被查阅和借阅。本人授权河北师范大学可以将学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保 存、汇编学位论文。 ( 保密的学位论文在年解密后适用本授权书) 。 论文作者( 签名) ： 加a 占年r 月6 同 指导教师( 签名) ： 砂。f 年y 月石 仉=_j 田一 ，镑 秀h 引言 分组测试理论起源于二战期间为了确定n 个血样中哪些血样含有病毒的问题，它的 组合分支被称为组合分组测试理论( c o m b i n a t o r i a lg r o u pt e s t i n g ) ，由于在化学渗透试验，电 子检验，码，多路存取信道传递，分子生物学和艾滋病筛选等方面的应用【1 】【2 】【3 】而得以迅速 发展 首先介绍组合分组测试的基本模型：假定有n 个被测对象，它们或者是阴性的( 正常 的) ，或者是阳性的( 有缺陷的) ，同时阳性对象的个数不超过整数d 组合分组测试的根本 问题就是把所有的阳性对象找出来，在此过程中所用的方法就是所谓的分组实验( g r o u p t e s s ) 一个分组实验可以通过对检测对象集的任何一个子集进行测试，产生两个可能的结 果：阳性或阴性若输出结果为阴性，说明这个对象集的子集中所有被测对象都是阴性的， 否则说明对象集的子集中至少有一个被测对象是阳性的组合分组的目标是使用尽量少 的试验检测出所有阳性对象分组测试的算法有两种：时序性算法和非适应性算法时序 性算法指对被测对象一个挨一个地进行试验，允许后面试验使用前面所有试验的输出结 果非适应性算法是指所有试验同时进行，禁止用一个试验的输出结果来用于其它的试验 时序性算法只适用于被测对象数目较小的情况，而当试验对象相当多时，非适应性算法可 以节省很多时间而非适应性分组测试算法的数学模型就是d d i s j u n c t 矩阵 由于多方面的原因，在实验的输出结果中出现错误是在所难免的，因此构作容错的数 学模型是非常必要的，而能容错的数学模型就是d 。一d i s j u n c t 矩阵在【4 】中，h u 卸gt a y u 柚 和w 色n gc h i h w e n 证明了一个d 。一d i s j u n c t 矩阵能够检测出实验结果中的e 个错误并能纠 正ie 21 个错误 构作d d i s j u n c t 矩阵和c f e d i s j u n c t 矩阵是非适应性分组测试的研究问题之一，它在 很大程度上要借助一些数学知识去研究19 9 6 年，m a c u l aa j 用包含关系在集合上构作了 一类d d i s j u n c t 矩阵 5 】2 0 0 2 年，n g oh q 和d ud i n g z h u 把它应用到了图的匹配和有限 域上的线性空间，构作了一类d d i s j u n c t 矩阵【l 】2 0 0 6 年，w uw ；e i l i 等人又把它应用到了 单纯复形上，构作了一类d d i s j u n c t 矩阵和c f e d 蠲u n c t 矩阵f 2 】f 引2 0 0 6 年，f uh u n g l i n 和 h w a n gf k 在集合上利用t 一填充设计构作了一类d i s j u n c t 矩阵【7 】 本文利用完全图和仿射空间构作了六类d i s j u n c t 矩阵( 定理2 1 1 一定理3 2 ) 所得结 果具有良好的d i s j u n c t 性质然后在单纯复形上构作了矩阵尬( ) ，并在尬( ) 的行的基 础上增加m ；：( ) 得到了一个新矩阵坼( ) ( 定理4 2 ) ，证明了它是d i s j u n c t 矩阵并且当 1 r t 七时，计算了尬( ) 的任意两个至多r 列集的并的h a m m i m g 距离，证明了 翥蓁丝雾薹羹蓁一书l | l 潆咒i 蓁蓁 蓁，蓁霎潲蓁蓁耍堡蚕霪一萱l l i 鹱羲委i 蓉叁 墓蔼茎i i ，；塾霪至高骚耄邓薹雾耋雨鲞蕈型= 薹霎霎誊；蒌i i 嘉萋萋爹；蠹澎藩霪掣 萋囊蓁蓁至一对妻；茎冀浮翌暧季爷蓁蓑喜驷鬯蚕茎i i ! 晌稀警蓁塑蓠ii ；l 晶翟一翼琶一 羹嚣瀚弱瓣l 婪 臻鞣绺一麓雾辩。羹堡奏蠢墼醅；| ；簿薹蓁霪妻彝堂i 圣：霎i 垂羹设；_ ；耋；耋! ； 不窖镰霎誓星薹薹摹磊渭雾值稽，霾鎏霪翮d 磐肇蓁 一眍冀霎裂羁墅鎏藉望藓! 琴 郡藿鬟萎手其驻蓠娃一i l ；g ；羹薹磊霪翮冀? 。地薹雨篙蓿粱! 囊垦j 一镛蒜薹型篡要雾垄羹 霉繇蛞喜一渺爬智；廷率；l i 童 羹冀滓仿粥斋霉。鋈雾如；一躞强憋蠢型爹i 角ii 蠢i ；囊茎基； 戮鬟霪鬈袋伪塑季l 錾j 墓；薹l 萎霪雾誊羹一i 萋蓁；! 錾重一鼻奢i l 塞誊i k i i i b l 圭l l 。语霎塞塞；篁雾 i 熏l 爹! ! i 薹霎i ；i ；：i ! 璧萋i 囊? = t i 鬟錾三一! ：i ；每 骂i 雾必j x ，y b ，则称d = ( y ，b ，) 为一个关联结构y 的元素叫作点，b 的元素叫作区组，j 叫作 关联结构设p vb b ，若p ，b ) ，则称点p 与区组b 关联并记作p j r b ；若p 与b 不关联，则记作p 歹b 有限关联结构可以用它的关联矩阵来刻划 定义1 1 1 3 f l l l 设y = p 1 ，p 2 ，钆) ，b = b 1 ，岛玩) d = ( y ，b ，) 为一个有限关 联结构，对1 is ，1 歹6 ，令。巧：f 1 ，若p 1 b ； 。 l 0 ，否则 则j u 6 的( 0 ，1 ) 矩阵 l f 吼 a ：l 眈 i锄 蠹 吻n 2 6l n t ，2 o 曲 叫作d 的关联矩阵 定义1 1 1 4 【1 2 】对1 i 口，令n 表示b 中与鼽关联的区组数；对1 j 6 ，令略 表示y 中与岛相关联的点的个数；对1 i ，歹u ，i 歹，令b 表示b 中同时与点鼽 及功关联的区组数n 叫作点鼽的重复度，b 叫作区组岛的容量( 或长度) ，b 叫作点鼽 与砌的相遇数则n 等于关联矩阵a 的第i 行的行和即第i 行中1 的个数，幻等于关联 矩阵a 的第歹列的列和即第歹列中1 的个数，而九，则是a 的第i 行与第歹行的内积设 d = ( y ，b ，j ) 为一个有限关联结构，对p y ，令咋表示点p 的重复度，对b b ，令七日表示 区组b 的容量；对y 的任意一个亡元子集s ，用a s 表示与s 中每一点都关联的区组个数 定义1 1 1 5 【1 3 】设可，尼，入为给定的正整数，d = ( y ，b ，) 为有限关联结构，若以下条件满 足： ( i ) i y l = 口； ( i i ) 对任意的b b ，都有b = 七； ( i i i ) 对任意的p ，g vp 口，都有a 啪= a 则称d 是一个平衡不完全区组设计，简称区组设计或b ，b 设计，记作b ( 七，a ； ) 口叫作 d 的阶，七叫作d 的区组容量，入叫作相遇数a = 1 时的b b 设计通常叫作鼠e i 死e r 系 定义1 1 】61 2 】一个单纯复形是指基集x 的一个子集族，使得该子集族当中的每个 元素的子集也在该子集族中x 中所有元素叫做点，中的每个元素叫做面特别地，包含 足个点的面也叫做七一面例如，0 一面就是空集，而1 一面就是一个点 定义1 1 17 【_ 】一填充是一个有序对( kp ) ，y 是 个点的集合，p 是7 的一个七一子 集族使得v 7 的每个f 一子集至多出现在p 的一个克一子集中，我们也称这样的惫子集为 大小为尼的区组 定义1 1 1 8 【1 4 】给定两个二元向量x ，y ， x = ( z 1 ，z l ，z n ) ，y = ( y 1 ，犰，鼽) 用m k 犰) l 表示x 与y 的h 锄m i n g 距离且记为日( x ，y ) 定义1 1 1 9 【2 】m 是一个矩阵，珥( m ) 记作矩阵m 的任意两个r 列集的并的最小h 锄一 m i n g 距离；珥( m ) 记作矩阵m 的任意两个至多r 列集的并的最小h a m m i n g 距离 1 2 基本性质和已知结论 命题1 2 l 1 剐日上的n 维仿射空间a g ( n ，日) 中的m 一面的个数是矿一m 二 口，o m 佗 命题1 2 2 1 1 6 j 瓦上的n 维仿射空间a g ( 礼，日) 中包含在一个给定的仇一面中的七一 面的个数是g m 咄 翟 。，o 七m n 命题1 。2 3 【1 7 1 日上的佗维仿射空间a g ( n ，日) 中包含一个给定的后一面的m 一面的 个数是 鬟 口，o 七m n 其中 二】o 为高斯系数 三】口= 咎话名艚，对于叫扎 ll = 一 孙l 一n7 7i l m j 口( g m 一1 ) ( 口m 一1 1 ) ( 口一1 ) ”。”二。二“ 命题1 。2 4 【1 8 】d d i s j u n c t = = ( d 一1 ) 一d i s j u n c t = = ( d 一2 ) 一d i s j u n c t = = 今= = 争2 一d i s j u n c t = 净1 一d 蠲u n c t 命题1 2 5 【1 4 】一个矩阵p 是d d i s j u n c t 矩阵当且仅当它是c f 0 一出彩u 佗以矩阵 命题1 2 6 f 4 】一个d 8 一d i s j u n c t 矩阵可以纠正l e 2 j 个错误，检测e 个错误 命题1 2 7 【1 】m 是一个矩阵，如果它的任意两个至多d 列集的并的h a m m i n g 距离大 于等于后，则m 可以检测( 七一1 ) 个错误，纠正l ( 忌一1 ) 2 j 个错误 命题1 2 8 1 9 设尼2 ，d = ( y ，b ，) 是区组设计b ( 七，a ；u ) ，则b 中所包含的区组个数 为6 = i b i = a u ( 1 ) 尼( 庇一1 ) 2 利用图构造d d i s j u n c t 矩阵 2 1 利用完全图构造d d i s j u n c t 矩阵 定理2 1 1 设施仇是有2 m 个顶点的完全图对1 s 7 亡 七，设r 是m 的一 个固定的s 一匹配，p 是满足下列条件的七一匹配的集合：i ) 它们都包含r ；i i ) 任何一个t 一 匹配至多包含在一个七一匹配中对每个正整数7 ，构作一个u 他的( o ，1 ) 矩阵m ( m ，南，r ) ， 它的列由p 中的n 个元素来标定，行由所有包含固定的s 一匹配局的r 一匹配来标定，行 和列都按字典序排列( i ，歹) 位置的元素是1 ，如果对应于第i 行的r 一匹配包含在对应于第 歹列的七一匹配中，否则( t ，歹) 位置的元素是o 鲍m 中f 一匹配的取法数为( 哿) ( 2 1 ) ! 2 饥， 则上述构作的矩阵m ( 仇，七，r ) 的行数为钐= ( 雾玄) ( 2 r 一2 s ) ! 2 ( 卜3 ) ( 7 一s ) ! ，列数为n ，n ( 哿) ( 2 亡) ! 2 。t ! ( ：) ，且m ( m ，尼，r ) 是一个d d i s j u n c t 矩阵，其中d = ( ：二：) ( ：二：) 1 1 证明显然完全图中f 一匹配的取法数为( 哿) ( 2 f ) ! 2 z f ! ，事实上，从鲍m 中任取2 f 个点 的取法数为( 哿) ，而这2 z 个点做成的z 一匹配的个数为( 2 f 一1 ) ( 2 f 一3 ) 3 1 = ( 2 2 ) ! 2 2 f ! ， 因此鲍m 中f 一匹配的取法数为( 哿) ( 2 f ) ! 2 饥 在上述构作的矩阵m ( m ，尼，r ) 中，由于行由所有包含固定的s 一匹配的r 一匹配来标 定，从而有 = ( 絮玄) ( 2 r 一2 s ) ! 2 ( 卜5 ) ( 7 一s ) ! 列曲包含固定的s 一匹配的七一匹配来 标定，而每个七一匹配包含( ：) 个不同的一匹配，又由于任何一个亡一匹配至多包含在一 个七一匹配中，从而矩阵m ( m ，七，7 _ ) 的n 列对应的礼个七一匹配至多包含礼( ：) 个不同的 亡一匹配而鲍m 中亡一匹配的个数为( 哿) ( 2 亡) ! 2 t ! ，从而有礼( ：) ( 哿) ( 2 亡) ! 2 亡! ，故 n ( 哿) ( 2 t ) ! 2 。亡! ( ：) 只须证明对矩阵m ( m ，七，7 ) 的任意d + l 列并指定一列，存在一行使得这行在指定 列是1 而在其它d 列都是o m ( m ，七，r ) 的每一列有( ：二；) 个7 一匹配，即有( ：二；) 行在 该列为1 因为集合p 中任意两个七一匹配至多包含一个公共的( 芒一1 ) 一匹配，所以对 m ( m ，尼，r ) 的任意两列，至多有( ：二：) 行在这两列同时为1 ，即这两列的内积至多为( ：) 设m ( m ，后，7 ) 是d d i s j u n c t 的，且设矩阵m ( m ，七，7 ) 的至少g 个列a ，岛，四的并能 覆盖其他的某一列c ，则有 于是 这样， c=c n ( u 塾1 g ) = ( c nc 1 ) u ( cnc 之) u u ( cnq ) ( ：二；) = i c i = l ( cng ) u ( c nc r 2 ) u u ( cnq ) l cnc l l + i cng i + + i ( nc 0 l = q ( ；二：) q ( ：二；) ( ；二：) 1 7 令d = ( ：二；) ( ：二：) 1 一l ，则m ( m ，七，r ) 是d d i s j u n c t 矩阵 定理2 1 2 设m 1 ) ，m 2 ) ，坛l 1 ) 分别为如上构作的d 1 ，c f 2 ， 尬1 ) 的行指标集和列指标集分别为r 和g ，( 1 i ) 令 口 ，以一d i s j u n c t 矩阵，且 r = ( r 1u 局) ) ( r 2u 岛) ) ( r u r ) ) c = q 伤瓯 构作m ( 2 ) 如下：m ( z ) 的行由r 的子集r ( z ) 来标定，这里r ( z ) = a 兄i q = ( r 1 ，r 2 ，) ， r i 冠u _ 【r ) ，1 i ，且q 中分量r i 不等于岛的个数为味列由c = p c i 卢= ( c l ，c 2 ，c h ) ，q g ，1 t ) 来标定，行和列按字典序排列m ( 2 ) 的( q ，卢) 位置的元 素为1 ，如果q 卢，即对1 z 危，n 龟，否则( 口，卢) 位置的元素为o 在上述构作中， 对1 l ，设m i ) 是比一d i s j u n c t 矩阵，1 t ，令d = m 伽 d 1 ，如，如) ，则当 1 d z 时，矩阵m ( f ) 是d d i s j u n c t 矩阵 证明也m i 佗 d 1 ，c f 2 ，如) = d ，从而对每个i ，1 ，舰i ) 是d d i s j u n c t 的下 面来说明m ( z ) 也是d d i s j u n c t 矩阵 任取m ( f ) 的d + 1 个不同的列岛，卢l ，尻： 尻= ( c ：，彰，兹) ( 1 ) 这里司q ，歹= o ，1 ，d ；i = 1 ， 即c 0 ，c ，c d 是矩阵尬的d + 1 个列( 重复 的按重数计算) 设这 个d + 1 列集中有q 个列集有重元，即有g 个d + 1 列集的基数都小 于d + 1 ，口有如下三种情况： ( 1 ) g 危一z 此时必然存在z 个d + 1 列集无重元，不妨设它们为 8 ( c ? ，c ：，留) ( c ! ，c ；，c ! ) ( 2 ) 、l，、l，露畦馥畦日区i，f = i l 风风 、， d 0 c，l o z r ，rl 即i c o ，母，c ? ) i = d + 1 ，i = 1 ，2 ，2 因为矩阵m 1 的d + 1 个列c o ，c ，互 不相同，矩阵a 磊又是d d i s j u n c t 的，所以必存在一行7 l 使得在这行c o 处为1 ，其他d 列 处为o 如此作下去，在矩阵a 乃中必存在一行r ，使得在这行c ? 处为1 ，其他d 列处为 0 ，歹= 2 ，3 ，z 令q = ( r 1 ，7 2 ，n ，r ，r ，p o ) ，q 中分量r 的个数为 一f 此时有( q ，风) = 1 ， 而( q ，p 1 ) = ( q ，阮) = = ( q ，阮) = o 即对m ( f ) 的任意d + 1 列风，卢1 ，仍，阮，存在 一行q 使得在这行岛处为1 ，而其他d 个列处为o 此时m ( 2 ) 为d d i s j u n c t 矩阵 ( 2 ) 一z q d 1 ，构作一个( o ，1 ) 矩阵m ( m ，n ，忌，d ) ，它的行由，n 的所有d 一匹配来标定，列由，n 的所有七一匹配来 标定，行和列都按字典序排列( i ，歹) 位置的元素是1 ，如果对应于第i 行的d 一匹配包含 在对应于第歹列的七一匹配中，否则( i ，歹) 位置的元素是o 。n 中f 一匹配的取法数为 ( ? ) ( ? ) ( 2 z ) ! 2 f f ! ，则上述构作的矩阵m ( m ，n ，后，d ) 行数为u = ( ：) ( ：) ( 2 d ) ! 2 d d ! ，列数为 铷= ( 墨) ( 2 ) ( 2 七) ! 2 知南! ，且m ( m ，钆，七，d ) 是一个d d i s j u n c t 矩阵，行重为( 留) ( z 二：) ( 2 免一 2 d ) ! 2 ( 七_ d ) ( 七一d ) ! ，列重为( ：) 证明显然完全二部图中z 一匹配的个数为( t ：i ) ( ? ) ( 2 f ) ! 2 。z ! ，事实上，从，n 的两 部分中分别取2 f 个点的取法数为( 7 ) ( ? ) ，而这2 z 个点做成的f 一匹配的个数为( 2 z 一 1 ) ( 2 z 一3 ) 3 1 = ( 2 z ) ! 2 饥，因此，n 中j 一匹配的取法数为( ? ) ( ? ) ( 2 f ) ! 2 饥从而 矩阵m ( m ，n ，忍，d ) 的行为秽= ( ：) ( ：) ( 2 d ) ! 2 屹! ，列为叫= ( 翟) ( ：) ( 2 惫) ! 2 七七! ，且行重为 ( 留) ( 2 二：) ( 2 七一2 d ) ! 2 ( 扣d ) ( 七一d ) ! ，列重为( ：) 只须证明对矩阵m ( m ，礼，d ) 的任意d + 1 列并指定一列，存在一行使得这行在指定 列是1 而在其它d 列都是o 任取m ( m ，佗，后，d ) 的d + 1 个不同的列岛，g ，岛，吼， 因为这d + 1 个不同的列对应着d + 1 个不同的七一匹配，所以对i 问，存在，n 的 一条边e 使得e i g g 从而存在一个d 一匹配rcg ，r = e i ：i 问) 若 l e ：i 问) i = p d ，则从g 中选取除这p 条边之外的d p 条不同的边添加到r 中， 使r = l e t ：t d 】) l = d 此时冗c 岛，r 茌g ，i = 1 ，2 ，d ，即存在一行r 使得在这 行g 列处为1 ，其余d 列处为0 从而m ( m ，n ，后，d ) 是一个d d i s j u n c t 矩阵 口 定理2 2 2 对1 s d 亡 d 1 ，构作 一个( o ，1 ) 矩阵坞( 礼，尼，d ) ，它的行由a g ( n ，日) 的所有d 一面来标定，列由a g ( 佗，日) 的 所有七一面来标定，行和列都按字典序排列( i ，j ) 位置的元素是1 ，如果对应于第i 行的 d 一面包含在对应于第歹列的七一面中，否则( t ，歹) 位置的元素是0 a g ( n ，日) 中仿射f 一 面的取法数为旷一 ? 口，则上述构作的矩阵坞( 佗，七，d ) 的行数为移= 矿- d ： 口，列数为 伽= g n “ ：】口，且坞( n ，庇，d ) 是一个d d i s j u n c t 矩阵，行重为【：二： 口，列重为嘲口 证明a g ( n ，日) 中z 一面的个数为矿一吲口，从而鸠( 扎，后，d ) 的行为t ，= g 卜d 圈口，列 为叫= g n _ 七 ： 矿且行重为 凳二： 口，列重为 ： 口 只须证明对矩阵鸩( 扎，后，d ) 的任意d + 1 列并指定一列，存在一行使得这行在指定列 是1 而在其它d 列都是0 任取坞( 佗，七，d ) 的d + 1 个不同的列岛，a ，岛，优，因为这 d + 1 个不同的列对应着d + 1 个不同的七一面，由定理2 2 1 的做法可知必存在一个d 一 面在某个指定的七一面中，而不在其它d 个七一面中，故这个d 一面标定的行在指定列是1 ， 而在其它d 列都是o ，从而坞( 佗，七，d ) 是一个d d i s j u n c t 矩阵 口 定理3 2 对1 s d 芒 七，设岛是a g ( n ，j ；) 的一个固定的s 一面，p 是满足f 列条件的尼一面的集合：i ) 它们都包含岛；i i ) 任何一个亡一面至多包含在一个七一面中对 每个正整数d ，构作一个钞叫的( o ，1 ) 一矩阵磁( n ，d ) 它的列由p 中的叫个元素来标 定，行由所有包含固定的s 一面岛的d 一面来标定，行和列都按字典序排列( i ，歹) 位置的元 素是1 ，如果对应于第t 行的d 一面包含在对应于第歹列的七一面中，否则( ，歹) 位置的元素 是o a g ( 礼，岛) 中仿射f 一面的取法数为矿一 ? 口，则如上构作的矩阵磁( n ，尼，d ) 的行数 为 = 矿- d ：二； 口，列数为叫，伽矿一 ? 。 ： 口，且磁( n ，七，d ) 是一个r d i s j u n c t 矩阵， 其中r = f 篇。 = 】口卜1 证明在上述构作的矩阵磁( 佗，尼，d ) 中，由于行由所有包含固定的s 一面的d 一面来标 定，从而有 = 矿“ ：二； 。列由包含固定的s 一面的七一面来标定，而每个七一面包含 ： 。 个不同的亡一面，又由于任何一个亡一面至多包含在一个七一面中，从而矩阵嘭( 佗，尼，d ) 的叫 列对应的伽个后一面至多包含叫 ： 。个不同的一面而如m 中亡一面的个数为g n - 。 ： 。， 从而有枷嘲。矿“ ? 。，故伽s 口 。吲。嘲。 只须证明对矩阵嘭( n ，七，d ) 的任意，+ 1 列并指定一列，存在一行使得这行在指定列 是1 而在其它r 列都是o 嘭( n ，七，c f ) 的每一列有 ：二： 。个d 一面，即有 ：二； 。行在该列为 1 因为集合p 中任意两个匙一面至多包含一个公共的( t 1 ) 一面，所以对嘭( n ，七，d ) 的任 1 2 意两列，至多有 z ： 口行在这两列同时为1 ，即这两列的内积至多为 ： 。设嘭( n ，七，d ) 是r d i s j u n c t 的，且设矩阵m ( m ，尼，r ) 的至少口个列c l ，q ，g 的并能覆盖其他的某 一列c ，则有 于是 c=c n ( u 坠1 g ) = ( cnc 1 ) u ( c nq ) u u ( cn q ) ：二： 口= i c i = i ( c nc 1 ) u ( cnq ) u u ( cnq ) l i cng i + i c nq l + + i cnq i = g 瞄 口 这样，口n ：二； 口 ： 口1 令r = ：二： 口 ：】口1 1 ，则嵋( 礼，七，d ) 是r d i s j u n c t 矩阵 口 1 3 4 利用单纯复形构造d d i s j u n c t 矩阵 是一个单纯复形，把它的的区组大小为惫，基点数为u = i x i 的亡一填充记作 p ( ，七，u ) 设7 是正整数，令尬( ) 是一个( ：) n 的( o ，1 ) 矩阵，它的列用p ( ，后，u ) 的任意n 个忌一面标定，行用所有的r 一面标定，行和列按字典序排列元素( i ，歹) 为1 如果 第t 行的r 一面包含在第j 列的七一面中，否则为0 引理4 1 对1 r t 一1 七，尬( ) 是d d i s j u n c t 矩阵，其中d = ( ：) ( 。：1 ) 1 1 证明只须证明对矩阵坼( ) 的任意d + 1 列并指定一列，存在一行使得这行在指定 列是1 而在其它d 列都是o 坼( ) 的每一列有( ：) 个r 一面，即有( ：) 行在该列为1 因为 p ( t ，七，u ) 中任意两个七一面至多包含一个公共的( 亡一1 ) 一面，所以对尬( ) 的任意两列， 至多有( 。：1 ) 行在这两列同时为1 ，即这两列的内积至多为( 。：1 ) 设尬( ) 是d d i s j u n c t 的，且设它的至少q 个列a ，岛，q 的并能覆盖其他的某一列c ，则有 c = g n ( u 塾1 g ) = ( c nq ) u ( cnq ) u u ( cn q ) 于是 ( ：) = i g i = l ( c na ) u 旧n 伤) u u ( cnq ) i l cnc l i + l cnq l + + i c nq l = g ( i 1 ) 这样，口( ：) ( ：1 ) 1 令d = ( ：) ( i 1 ) 1 1 ，则尬( ) 是d d i s j u n c t 矩阵 口 定理4 2 构作矩阵尬( ) ，它是在矩阵尬( ) 的基础上按如下方式增加钉= i x l 行， 这 行用x = z t ，z 2 ，) 来标定，观x ，且元素( t ，j ) 为1 当且仅当z 簪马，即在 螈( ) 的基础上增加了聊( ) 那么砑忑耵是d d i s j u n c t 矩阵，其中d = ( ：) ( ：1 ) 1 1 。 证明由引理4 1 知珥( ) 是d d i s j u n c t 矩阵，而鸠( ) 是在矩阵尬( ) 的基础上 增加口= i x i 行得到的，从而由d d i s j u n c t 矩阵的定义可知尬( ) 也是d d i s j u n c t 矩阵， 并且d = f ( ：) ( ：1 ) 1 1 口 定理4 3 对1 7 亡 旺毯，又因b 1 ，磁p ( t ，忌，u ) ，从而 l b l b 0 七一( t 一1 ) 2 ，故必存在除z l 外的另一点z i ，z ；【b 1 b ：，考虑z l ： ( 1 ) 如果存在某些i 使得z 簪鹾，则令= z l ，不失一般性可得i 兢k = 1 ，2 ，r ) l = m r 一1 ，则可得( ：二：) 个不同的r 一面d r 满足 祝k = 1 ，2 ，r cd rcb 1 ，且 黝k = 1 ，2 ，7 ) c 研仁b ：又由于z i 和z 地位相同，也可以找到( ：二：) 个不同 的r 一面d r ，考虑到用z 1 和z ：找到的r 一面研至多重复( ：二篡二：) 个，从而可找到至少 2 ( 扣：+ 1 ) 一1 2 ( ：二三) 一( ：二：二：) 个不同的r 一面研使得这2 ( 七一r ) + 1 个不同的r 一 面研对应的行冗满足rn c = 1 ，r nc = o ( 2 ) 如果对t = 2 ，3 ，r ，都有既，则至少存在一个r 一面研满足 甄卜= 1 ，2 ，r ) c 研cb 1 ，且 以k = 1 ，2 ，r ) c4 茌e 又由于i b l b ：i 七一( 亡一1 ) = 七+ 1 一亡，从而z l 的选取数为七一芒+ 1 ，故至少可找到庇一亡+ 1 个不同的r 一面d ，满 足d rcb 1 且d r 茌耳这七一亡+ 1 个不同的7 一面对应着矩阵尬( ) 的第一部分的 七一亡+ 1 个不同的行r 使得r nc = 1 ，rnc = o 又因在矩阵坼( ) 的第二部分中 用瓦标定的行满足rnc = o ，冗n = 1 ，而z 1 的选取数至少为尼一t + 1 ，从而在矩 阵尬( ) 的第二部分中可找到至少七一t + 1 行满足r nc = o ，冗n = 1 故在矩阵 尬( ) 中可找到至少2 ( 七一亡+ 1 ) 行使得( r nc ) ( r n ) 互换b 1 和b i 的规定又可以找到至少2 ( 七一亡+ 1 ) 行使得( rnc ) ( rn ) 情形二i cnc 。i r 1 只须证明i c n c i = r 一2 的情形，其它的情形可由相同的方法得证 设b 1 ，b 2 c c 7 ，b ：，b ：c ，由假设知至少存在点z b 1 岛，对每个 i ，i l ，2 ，r ) ，存在甄b 1 e ，犰b 2 e ，因此 甄k = 1 ，2 ，r ) cb 1 且 甄瞳= 1 ，2 ，r ) 旺e ， 犰扣= 1 ，2 ，7 ) cb 2 且 训i = 1 ，2 ，r ) 仁b ：下面分两 种情况： ( 1 ) 如果z 不在某个e 中，不失一般性，取z i = z ，则 z i = 1 ，2 ，r ) 与 蚓i = 1 ，2 ，r 是不同的集合，则存在两个不同的r 一面d 1 ，d 2 使得 z i 卜= 1 ，2 ，7 - ) c d 1cb 1 ，且 z i 卜= l ，2 ，r ) cd l 眨b ；， 训i = 1 2 ，r cd 2cb 2 ，且 引i = 1 2 ，r cd 2 眨b ；故在矩阵尬( ) 的第一部分中与d i ，d 2 对应的行与 1 5 c 的交为l ，与c 的交为0 ( 2 ) 如果z 在所有的b ：中，此时 cd ，cb l ，且 戤k = 1 ，2 ，仇) c 研茌鹾因此这( 杠；+ 1 ) 个不同的r 一 面对应着矩阵砀疋酉的第一部分中的( 七一：+ 1 ) 个不同的行冗使得r n c = 1 ，冗n c 7 = o 从而有 珥( 尬( ) ) m 叭珥( 坼( ) ) ，( 七一7 + 1 ) ) = m i 几 2 ( 后一r ) + 1 ，4 ( 七一亡+ 1 ) ，2 ( 七一亡+ 2 ) ，( 七一r + 1 ) ) = m i n 尼一r + 1 ，2 ( 七一亡+ 2 ) ) 口 推论4 41 r 芒 尼时 珥( 尬( ) ) 5 ； 珥( 尬( ) ) 3 推论4 51 7 t 尼时尬( ) 可以检测2 个错误，纠正1 个错误 定理4 6 对2 7 亡 ； ( i i ) 矩阵a 磊( ) 的任意两个至多r 一1 列集的并的最小h 锄m i n g 距离 蛄( 瓦荭可可) m t n ( 七一；+ 2 ) ，4 ( 忌一r ) + 2 ，2 ( 2 七十l t ) ) 证明先考虑( i ) 式 令u 是矩阵尬( ) 的任意7 一1 列b l ，b 2 ，b r l 的并；u 是矩阵尬( ) 的另一 个任意，厂一1 列b ：，b ：，b ：一1 的并 断言( a ) u 在尬( ) 的第一部分有m i n ( 肛；+ 2 ) 2 ( 一，) + 1 ) 行是l ，而u 在这些 行中是o ：或 ( b ) u 在 砟( ) 的第一部分有2 七十2 一r t 行是1 ，而在这些行中是0 ，且u 在 露( ) 的第二部分有r l 行是o ，而u 7 在这些行中是1 其中之一成立 证明断言成立：选取o u 鼠b ：，n t ，2 鼠岛，o 寸一1 b 耳一1 令 厶= 口 ，1 ，o i ，2 ，o i ，卜1 ) ，则i 厶l 7 一1 ，i = 1 ，2 ，r 一1 下面分两种情形： 情形一当存在某些 使得吲r 一2 时 此时可以找到至少( 肛；+ 2 ) 个包含厶的r 一面在鼠中而不在每个e 中，这( 扣；+ 2 ) 个包含厶的，一面在第一部分标定了( b ；+ 2 ) 行使得u 在这些行是1 ，而u 7 在这些行中 是0 ，满足( a ) 情形二当对所有的 = 1 ，2 ，一1 都有= r 一1 时 ( 1 ) 如果存在1 t = m i 佗 ( 七一；+ 2 ) ，4 ( 启一，+ ) + 2 ，2 ( 2 七+ l t ) ) 口 1 8 推论4 72 7 亡 后时，珥一l ( 砑疋硒) 1 0 ； 马可( 尬( ) ) 6 推论4 82 r z 七时，砑_ 圆可以检测5 个错误，纠正2 个错误 5 利用区组设计构造d e d i s j u n c t 矩阵 本章考虑用a = 1 时的b ，b 设计( 即鼠e i n e r 系) b ( 忌，1 ； ) 的关联矩阵构造d 8 一d i s j u n c t 矩阵 定理5 1 设b ( 忌，1 ；口) 的关联矩阵 r m a ：i 眈 i o t ， n 1 2 0 1 6 i a 2 2 0 2 6 l l l j n 口2 o 曲 构造矩阵m ：m 的行是由( i ，歹) 来标定的，并且它的第( i ，歹) 个行向量是由矩阵a 的第i 行与第歹行的元素对应相乘得到的，i 歹，i = 1 ，2 ，钉一1 ，歹= 2 ，3 ，u 如上构作的 矩阵m 是一个m 6 的舻一d i s j u n c t 矩阵，其中仇= 可 一1 ) 2 ，6 = t ，0 1 ) 惫( 后一1 ) ， d = 口( u 一1 ) ( 克一1 ) 一1 ，e = 七( 七一1 ) 2 1 证明b ( 七，1 ；秽) 的关联矩阵a 的行数为 ，由矩阵m 的构造方法可知m = 锈= 口( 钉一1 ) 2 另外，由于a = 1 ，由命题1 2 8 可知6 = 口( 钉一1 ) 忌( 尼一1 ) 只须证明对矩阵m 的任意d + 1 列并指定一列，存在e + 1 行使得这e + 1 行在 指定列是1 而在其它d 列都是0 由定义1 1 1 6 知b ( 后，1 ；钉) 的相遇数为1 ，即对任意的 p ，g v p 口，都有，口= 1 由相遇数的定义知b ( 七，1 ；口) 的关联矩阵的任意两个不同 的行的内积为1 ，故矩阵m 的每行都只有一个1 ，即行和为1 又由于矩阵m 的列是由 b = b 1 ，岛，岛中元素来标定的，l 鼠i = 七，由定义1 1 1 5 和定义1 1 1 6 知，矩阵m 的每 列都有暌个l ，即列重为嚷故对矩阵m 的任意一列，都存在曜行使得在该列为1 ，而 在其余列全为o 从而矩阵m 是一个d e d i s j u n c t 矩阵，其中d = u ( 锄一1 ) 七( 七一1 ) 一1 ， e = 七( 七一1 ) 2 一1 口 推论5 2m 可以纠正【( 七( 尼一1 ) 2 一1 ) 2 j 个错误，检测后( 尼一1 ) 2 1 个错误 例：令y = 乙是模7 的全体剩余类的集合，且 b = ( o ，l ，3 ) ，( 1 ，2 ，4 ) ，( 2 ：3 ，5 ) j ( 3 ，4 ，6 ) ，( 4 ，5 ，o ) ，( 5 ，6 ，1 ) ，( 6 ，o ，2 ) ) 若将区组看作直线，则d = ( z - ，b ) 是一个由7 个点和7 条直线组成的关联结构，设 它的关联矩阵为a ，且用如上方法构造矩阵m ： 2 0 a = 10 0 o101 110 0 01o 011o 0 01 10l1o 0 0 010l100 001o1 10 0 o 01011 m = 10 o 0 0 0 0 o 0 0 0 o ol 100 0 o 0 0 o 0 0 01o 0 0 0 0 010 0 0 0 0 0 0 0l 010 o 0 0 0 10 o 0 0 0 0 0l0 0 0 0 0 0 000 o10 0 0 0 0 010 0 010 0 o 0 o10 0 0 o