（基础数学专业论文）有限几何上ddisjunct矩阵的构作.pdf

中文摘要 本文利用n 阶射影平面和n 维射影几何构作了d 一击s j u n c t 矩阵和( d ，e 卜 d f s j u n c t 矩阵，讨论了它的析取( d 纫u n c t ) 性质及检纠错能力；在有限域上n 维向量空间和2 p 维辛空间中，构作了( d m ，e ) 一d i s j u n c t 矩阵，讨论了其容 错和纠错性，证明了当d 的值减小时，矩阵的容错和纠错能力增强了，主要结论 是： 定理3 1 1 设”是n 阶( n 2 ) 射影平面 f 是一个( n 2 + n + 1 ) 阶方 阵，其行用7 f 上的( 舻+ n + 1 ) 个点标定，其列用上的( n 2 + t i + 1 ) 条直线标 定，肘的第i 行第j 列的元素为1 0 第i 行的点在第j 列的直线上则 1 ) 矩阵m 为个( n 2 + n + 1 ) 阶n 一幽s j u n c t 矩阵； 2 ) 矩阵吖的转置矩阵m 7 为一个( 舻+ n + 1 ) 阶n d i s j u n c t 矩阵 定理3 13 在n 阶( n 2 ) 射影平面”上构作一个( 0 ，1 ) 一矩阵，其 列用 上舻+ n + l 条直线标定，其行用上n 2 + n + 1 个点的2 一子集标定， 矩阵肘的第i 行第j 列的元素为1 当且仅当第i 行的2 一子集中的2 个元素都 在第j 列的直线匕则 1 ) 矩阵m 为( d ，r ) 一s e p a r a b l e 矩阵； 2 ) 矩阵m 为( d ，e ) 一d i 鲥u n e t 矩降 其中1s d 疗2 + 吼r = 2 ( 4 ；1 ) ，e = ( ”；1 ) 一1 定理3 2 1 设m 是( 0 ，1 ) 矩阵，行和列分别用，l 维射影几何p a ( n ，q ) 上的z 维子空间，m 维子空间标定 肘的第i 行第j 列的元索为1 当且仅当第i 行的l 维子空间包含在第j 列的m 维子空问中，则对于n 打l f 21 ，m 是 【n l + l + l 】。 揣】。的( d ，e ) 一d 幻w 成矩阵，其中 有限几何上d d i s j u n c t 矩阵的构作 a = f q 。m 。+ 一l 。一- - ，1 j t q + l t ， e = 瞄l - m 。+ ( 筹1 - 1 ) t 而f z l 表示不小于z 的整数 定理4 1 4 设g 是一个素数的幂，品是g 个元素的有限域，f j “是昂 上的n 维向量空间m 是一个( o ，1 ) 矩阵，行用巧“中所有的d 维子空间 a 1 ，a 2 ，a t 标定，列用曩“中所有的维子空间b l ，岛， ，b 二标定，且矩 阵m 的第i 行第j 列的元素为1 = = a 。c 马，则对于n2k d m 0 ，m 至少是一个( d m ，e ) 一威巧n 磁矩阵，其中 1 1 ( 矿一1 ) e = 型l 一一1 n ( 旷一1 ) 定理4 2 2设p d21 ，砖”是有限域日上的2 维辛空间， m 是一个( o ，1 ) 一矩阵，行用曩刎中所有的( d ，o ) 型子空间a 1 ，a 2 ，a 标 定，列用砖2 ”中所有的( ，0 ) 型子空间b l ，b 2 ，b i 标定，且m 的第i 行 第j 列的元素为1 甘acb j 则对于p 之k d 2 m 0 ，m 至少是一个 ( d m ，e ) 一d i 巧u n c t 矩p 氛其中 k d + m n ( q l 1 ) e = 苎笋l 一矿啡一神一1 兀( 矿一1 ) l = l 关键词； 有限射影平面有限射影几何，有限域最上n 维向量空间， 有限域上2 v 维辛空间，有限域舀：上的酉空问，d d i s j u n c t 矩p 较 ( d ，e ) 一出印u n c t 矩阵( d ，r ) 一s e p a r a b l e 矩阵 a b s t r a c t i nt h i sp a p e r ，u s i n gap r o j e c t i v ep l a n ew i t hno r d e ra n da nn - d i m e n s i o n a lp r o - j e c t i v es p a c e ，r e s p e c t i v e l y , w ec o n s t r u c t ad - d i s j u n e tm a t r i xa n da ( d ，e ) - d i s j u n c t m a t r i x u s i n gt h ev e c t o rs p a c eo v e rf i n i t ef i e l d sa n d2 v d i m e n s i o n a ls y m p l e c t i c s p a c eo v e rf i n i t ef i e l d s ，w ec o n s t r u c ta ( d m ，e ) - d i s j u n c tm a t r i xa n dd i s c u s si t s e r r u r a o l e r a n td e c o d i n ga n de w o t - c o r r e c t i n gc a p a b i l i t y i ti ss h o w nt h a tt h ee r r o r - t o l e r a n td e c o d i n ga n de r r o r c o r r e c t i n gc a p a b i l i t ya r ci n c r e a s e d t h ef o l l o w i n gi so u rm a i nr e s u l t s t h e o r e m3 1 1l e t 丌b eap r o j e c t i v ep l a n ew i t hno r d e r s u p p o s em i sa 舻+ n + 1m a t r i x 。w h o s er o w sa n dc o l u m n sa r ei n d e x e db y 1 2 + n + 1p o i n t s ，a n d 7 1 2 + ，l + 1l i n e s ，r e s p e c t i v e l y t h e0 ，j ) t he n t r yo f m i se q u a lt o1i f a n do n l yi f t h ei t hp o i n ti sc o n t a i n e di nt h ej t hl i n e t h e nw eh a v e 1 ) t h e m a t r i x m i sa n d f s f u n c t m a t r i x w i t h 扎2 + n + 1o r d e c 2 、t h e m a t r i x m r i s a n d i s j u n c t m a t r i x w i t h 舻+ 扎+ lo r d e r t h e o r e m3 ，1 3l e tm b ea ( 0 ，1 ) 一m a t r i xo nt h ep r o j e c t i v ep l a n e ，rw i t h no r d e r , w h o s ec o l u m n sa g ei n d e x e db yn 2 + n + 1l i n e sa n dr o w sa r ci n d e x e db y a i i2 一s u b s e t s o f 矿+ ，i + 1p o i n t s 0 1 1 丌m h a sa l i nr o w i a n d c o l u m n j f e n d o n l yi f e l e m e n t si n 也ei t 2 一s u b s e t s a 他o nt h ej t hl i n e s t h e n 1 ) mi s ( d ，r ) 一s e p a r a b l em a t r i x ； 2 ) mi s ( d ，e ) 一d i s j 钍n dm a t r i x , w h e r e l d 舻+ n ，r = 2 ( “；1 ) ，e = ( 譬1 ) 一1 t h e o r e m3 2 1 l e tm b ea ( 0 ，1 ) - m a 比i x , w h o s er o w sa n dc o l u m n sa r ei n - 有限几何上d 一击s j u n c t 矩阵的构作 d e x e d b y t h es e t o f a l l l - d i m e n s i o n a ls u b s p a c e s a n d t h es e t o f a l l m d i m e n s i o n a l s u b s p a c e s ，r e s p e c t i v e l y , t h e ( f ，j ) t he n t r yo f m i se q u a l t 0 1 i f a n d o n l y i f t h e i t h l d i m e n s i o n a ls u b s p a e e si sc o n t a i n e di nt h ej t hm d i m e n s i o n a ls u b s p a c e s i f n m l l ，t h e n m i s a ( d ，e ) 一d i s j u n c t m a u l x w i t h 嘣n + 1 q “n + l 】口，w h e r e d = f 岩1 1 一t e = 譬a 一例。( 篇卜) “ w h e r ek 1d e n o t et h ei n t e g e ra tl e a s tz t h e o r e m4 1 ，4l e teb et h ef i n i t ef i e l dw i t hqe l e m e n t s ，w h a r eqi sap o w e r o fap r i m e , a n dl e tnb eap o s i t i v ei n t e g e r s u p p o s ef j 州i st h en d i m e n s i o n a l l o wv e c t o rs p a c eo v e rra n ds u p p o s emi sa ( 0 ，1 ) 一m a t r i x ，w h o s el o w sa r ei n - d e x e d b y t h es e t o f a l l d d i m e n s i o n a ls u b s p a c e s o v e r m c o ，s a y a t ，a 2 ，a ， a n dc o l u m n sa l ei n d e x e db yt h es e to f a l lk d i m e n s i o n a ls u b s p a c e so v e rt h e 留， s a y b l ，b 2 ，风t h e ( ，j ) t he n t r y o f m i s e q u a l t 0 1 i f a n d o n l y i f ac 岛i f n k d m 0 ，t h e n m i s a t l e a s t ( d m ，e ) 一d 巧越珏d ，w h e r e 1 - i ( 矿一1 ) e 2 1 f 一一1 n ( 垡 一1 ) t h e o r e m4 2 2l e t 扩膏 d 21 ，a n d l e t 砖知b ea 2 v d i m e n s i o n a l s y m p l e c t i es p a c e s u p p o s em i sa ( 0 ，1 ) 一m a t r x ，w h o s el o w sa ”i n d e x e db y t h es e to f a l l ( d ，0 ) s u b s p a e e so v e l t h e 砖”，s a ya l ，a 2 ，a ，a n dc o h m m sa r e i n d e x e db y t h es e to f a l l ( ，0 ) s u b s p a c e so v e r t h e 砖，s a y 蜀，b 2 ，既t h e ( i ，j ) t he n t r yo f m i se q u a l t 0 1 i f a n d o n l y i f ac 岛i f 2k d 2 m20 ， t h e n m i s a t l e a s t ( d m ，e ) 一d i s j u n a ，w h e r e 河北师范大学硕士学位论文 n ( 矿一1 ) e = 型亲生一g m “”) 一1 n ( 矿一1 ) l = i k e y w o r d s ：a f i n i t e p r o j e c t i v e p l a n e ，a f i n i t ep r o j e c t i v e s p a c e ，t h e n - d i m e n s i o n a l v e c t o rs p a c eo v e rf i n i t ef i e l d se ，t h e2 1 一d i m e n s i o n a ls y m p l c c t i cs p a c eo v e rf i n i t e f i e l d s ，t h eu n i t a r ys p a c eo v e rf i n i t ef i e l d s 印；d - d i s j u n c tm a t r i x , ( d ，e ) 一d i s j u n c t m a t r i x ，( d ，r ) 一s e p a r a b l em a t r i x v 学位论文原创性声明 本人所提交的学位论文概垮锄椰，是在导师的指 导下，独立进行研究工作所取得的原创性成果。除文中已经注明引用 的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研 究成果。对本文的研究做出重要贡献的个人和集体，均已在文中标明。 本声明的法律后果由本人承担。 论文作者( 签名) 走差牝 。引鼬师 学位论文原创性确认书 学生粪多二雏所提交的学位论文伽嘶蜘咖7 7 i 潴p ，是在 本人的指导下，由其独立进行研究工作所取得的原创性成果。除文中 已经注明引用的内容外，该论文不包含任何其他个人或集体已经发表 或撰写过的研究成果。 指导教师( 签名) ：窍铡 二，蕾7 年j 一月纩日 ， 第一章绪论 5 1 1 课题背景与发展概况 分组测试理论是1 9 4 3 年提出的，它的组合分支被称为组合分组测试理论 ( c o m b i n a t o r i a l g r o u pt e s t i n g ) , 因为在血试验，化学渗透试验，电子检验，码，多路 存取信道传递和艾滋病筛选等方面的应用而迅速发展 组合分组测试的基本模型如下：假设有日个对象，它们中的每一个要么是 阳性的卜般称为有缺陷的) 要么是阴性的卜般称为正常的 并且阳性对象的 个数不超过d 组合分组测试的根本问题就是找出所有的阳性对象为了达到 这个目的，我们用分组实验的方法( g r o u pt e s t s ) 所谓的分组实验就是对检测对 象集的任何一个子集进行测试的时候只会产生两个可能的结果：阳性或阴性 结果是阴性就说明这个对象集的子集中所有对象都是阴性的，结果是阳性就说 明这个对象集的子集中至少有个对象是阳性的分组实验的的主要原理我们 可用圣诞树灯泡问题加以说明我们按照电学原理把一批灯泡串联，给这整批 灯泡或者其中一部分加上电压加以测试如果所有灯泡都亮，说明它们全部合 格；如果所有灯泡都不亮，说明其中至少有一个不合格组合分组的最终目的是 用最少的试验次数找出全部的阳性对象常用的分组测试算法有两种：时序性 的的和非适应性的如果试验一个接一个地进行，而且允许后面的实验使用前 面试验的试验结果，则称这种算法为时序性的；如果所有的试验都是同时进行 的，不允许使用前面试验的结果，则称为非适应性的算法这两种算法具有各自 的优缺点：时序性算法所需试验个数少但所用时间较长，而非适应性算法所需 试验个数多但所用时间较短还有个s - 部算法介于这两种算法之间，此种算 法中的每一步中所作的试验同时进行的，但每两步之间又是时序性的 分组测试理论在分子生物学上也有广泛的应用在分子生物学的应用上， 一个分组测试算法称为一个p o o l i n g 设计，每个实验构成一个p o o l 虽然分子生 l 有限几何上d d i s j u n c t 矩阵的构作 物试验的目的是使用尽量少的试验，但由于分子生物试验具备以下两个特点： 1 需要测试的对象是大量的；2 分子生物试验极易出错因此分组测试算法用 在分子生物试验上，时序性算法是不切实际的，而且必须建立能容错的算法。即 能容错的p o o l i n g 设计而非适应性分组测试算法的数学模型就是d d i s j u n c t 矩阵 能容错的数学模型就是( d ，e ) 一d i s j u n c t 矩阵 同时，h a m m i n g 距离大f 等于4 的d 一出s j u n c t 矩阵也具有容错功能 构作容错和纠错能力强的分组设计是非适应性分组测试的中心问题之 它在很大程度上要借助一些数学分支去研究例如，w uw e i l i 等人利用单纯复 形研究d d i s j u n c t 矩阵( 【1 4 】) ，m a c u l aa j 等人进步用复形构作了几乎析 取( a l m o s td i s j n d ) 矩阵( f l l j ) ，而nh u n g - l i n 和h w a n gfk 利用一填充 来构作( 【4 】) ，h u n gq n g o 和d ud i n g - z h u 则甩图理论( 7 】) ，d y a c h k o va g 等 人用的是有限域上的向量空间( 【3 】) 本文首先研究了n 阶射影平面和t t 维射影几何上d - d i s j u n c t 矩阵，( d ，e ) 一 出s j u n c t 矩阵的新构作，证明了它的析取( 出s j u n c t ) 性质及检纠错能力然后 在有限域上的向量空间和辛空间中构作了( d m ，e ) 一d l s j u n c t 矩阵，研究了 其容错和纠错性证明了当d 的值减小时，矩阵的容错和纠错能力大大增强了 2 河北师范大学硕士学位论文 1 2 本文综述 本文共分4 章第1 章阐述了课题背景及发展概况第2 章为预备知识。着 重介绍了后面几章中要用到的一些符号，概念和基本性质第3 章研究了n 阶 射影平面和n 维射影几何上d d i s j u n c t 矩阵的构作：第4 章在有限域上的向 量空间和辛空问中构作了( d m ，e ) 一d i s j u n c t 矩阵，讨论了其容错和纠错也 证明了当d 的值减小时，矩阵的容错和纠错能力x - - ) c 增强了主要结果是二 定理3 1 1 设f 是n 阶( 扎22 ) 射影平面，m 是个( n 2 + n + 1 ) 阶方 阵，其行用7 r 上的( 1 - i 2 + ，l + 1 ) 个点标定，其列用7 1 上的( n 2 + n + 1 ) 条直线标 定，m 的第i 行第j 列元素为1 甘第i 行的点在第j 列的直线上则 1 ) 矩阵m 为个( n 2 + n + 1 ) 阶n d i s j u n c t 矩阵； 2 ) 矩阵肘的转置矩阵吖7 为一个( 铲+ n + 1 ) 阶n d i s j u n c t 矩阵 定理3 1 3 在n 阶m 2 ) 射影平面”上构作个( 0 ，1 ) - 矩阵m ，其 列用7 r 上舻+ r t + 1 条直线标定，其行用 r 上舻+ n + 1 个点的2 一子集标定， 矩阵m 的第i 行第j 列的元素为1 当且仅当标定第i 行的2 一子集中的2 个元 素都在标定第j 列的直线上则 1 ) 矩阵m 为( d ，r ) 一s e p a r a b l e 矩隆 2 ) 矩阵m 为( d ，e ) 一d i s j u n c t 矩阵， 其中1 sd sn 2 + t l ，r = 2 ( ”；1 ) ，e = ( “；1 ) 一1 定理3 2 1 设m 是( 0 ，1 ) 一矩阵，行和列分别用n 维射影几何p g ( n ，q ) 上的l 维子空间，m 维子空间标定，m 的第i 行第j 列的元素为1 当且仅当第i 行的l 维子空间包含在第j 列的m 维子空间中，则对于n m f 1 ，m 是 3 有限几何上d d i s j u n c t 矩阵的构作 【嚣门。【。n + + l 。 。的( d ，e ) 一击巧u n d 矩阵，其中 a = f 筹 - 1 e = 瞄卜。( f 岩1 - 1 ) 乩 而f z l 表示不小于的整数 定理4 1 4 设g 是一个素数的幂，日是q 个元素的有限域，日哪是f 口 上的n 维向量空间m 是一个( 0 ，1 ) 一矩阵，行用日哪中所有的d 维子空间 a l ，如，a 标定，列用蹬中所有的k 维子空间b l ，岛，b n 标定，且 m 的第 行第j 列的元素为1 甘a c 蜀则对于n 2 女 d m 0 ，m 至 少是个( d m ，e ) 一d i s j u n c t 矩阵，其中 l - i ( 旷一1 ) i - i ( q t 一1 ) 定理4 2 2设p 芝 d 1 ，曩”是有限域e 上的2 u 维辛空间， m 是一个( 0 ，1 ) ，矩p t 行用曩”中所有的( d ，0 ) 型子空间a l ，a 2 ，a 标 定，列用砖“中所有的( k ，o ) 型子空间日l ，岛，巩标定，且m 的第i 行 第j 列的元素为1 a ic 易则对于p d 2 m20 ，m 至少是一个 似一m ，e ) 一d i s j u n e t 矩p # 其中 k - d + n n 旧一1 ) e = 兰喜嘉生l g “一“) 一1 n ( 矿一1 ) 4 第二章预备知识 本章介绍有限射影平面，有限射影几何，有限辛几何，d d i s j u n c t 矩阵的 概念和基本性质， 2 1 有限射影平面，有限射影几何的概念和基本性质 定义2 1 1 【1 2 1 设，r = ( k b ，i ) 为有限关联结构，y 的元素叫点，口的元素 叫直线若满足下列公理： p p l对y 中任意两个不同的点p l 与p 2 ，都存在b 中唯一的一条直线 工使p x l l ，p 2 l l ； p p 2 对b 中任意两条不同的直线工l ，l 2 ，都存在矿中唯一的一点p 使 p j l l ，p l l 2 ； p p 3 v 中存在4 点，其中任意3 点都不与同一条直线关联，则称”为一 个有限射影平面 设p v ，l b ，当p l l 日于常称点p 在直线l 上，或直线l 经过点 p ，或l 包含p 若点p l ，p 2 ，p 。与同一直线关联，则称这些点共线若直线 工l ，l 2 ，工。与同一点p 关联，则称这些直线共点，而p 叫做它们的交点 定义2 1 2 1 1 2 】设7 r 为个有限射影平面，若其中有一条直线恰好包含n + 1 个点，则称”为n 阶射影平面 定义2 1 3 1 1 设( x ，c ，j ) 为有限关联结构，x 的元素叫点，c 的元素叫 做直线再把x 的某些特定子集叫做子空间，全体子空间的集合记为f 若以 下公理成立： 5 有限几何上d d i s j u n c t 矩阵的构作 p g i 设矶q x ，若p q ，则有c 中唯一的一条直线同时过p 与q 两 点； p g 2 中任意条直线都至少包含3 点； p g 3 若直线l 与m 交于点如，又设p l 与见为l 上不同于p 0 的两点， m 与m 为m 上不同于p o 的两点，则过点p i 与船的直线和过点p 2 与p 4 的直 线岿有一个交点； p g 4 设f ，为个子空间，p ，q 为任意不同的两点若p ，q f 则f 也包含了过p 与q 的直线反之，对任一具有上述性质的f x ，都有f ， 则称( x ，刁为一个射影几何 定义2 1 4 【1 2 1 设( x ，门为射影几何，定义圣为一l 维子空间，x 的任一单 点子集扫 为。维子空间设f 为一个i 维子空间，p 为不属于f 的一点，则所 有同时包含子空间f 与点p 的子空间的交为i + 1 维子空间当x 为n 维子空 间时，称( x ，) 为一个n 维射影几何 设q 为数幂，k + - ( f q ) 为日上n + 1 维向量空间取k + l ( 日) 中全体l 维 子空同的集合作为点的集合x ，以2 维子空问作为直线，以包含关系作为关联 关系，以k + l ( ) 全体子空间的集合作为，则得到局上的一个n 维射影几 何，记作p g ( n ，q ) k + d r , ) 中的i + i 维子空间是p g ( n ，q ) 中的i 维子空 间，- i s i n 注记；n = 2 时即射影平面的情形，换句话漉p g ( 2 ，q ) 是q 阶射影平面， 且存在与p c ( 2 ，q ) 不同构的q 阶射影平面但n23 时，任一n 维有限射影几 何都和某个有限域日上的n 维射影几何p g ( n ，乃) 同梅仗献【1 2 | 土 6 河北师范大学硕士学位论文 命题2 1 5 1 1 设口为一个n 阶射影平面，则n 22 且 j j 每一条直线都恰好包含n + 1 点； 乃过每一点的直线都恰有+ i 条； 3 ) 共有扎2 十n + 1 个点； 4 ) 共有n 2 + n + 1 条直线 命题2 1 6 【1 q 设口为素数幂，1 f msn ，则p g ( n ，q ) 中m 维子空问 个数为 。n + + l t 】。 包含在个给定的m 维子空间中的f 维子空间的个数为【m f + l + l 】。； 包含个给定的f 维子空间的m 维子空闻的个数为【2 。， 其中【? 。为高斯二项式系数 吼= 与等斋等譬铲衙刊之【l j 。2 再f = j 巧i f = r 二1 了_ _ i i = 1 了一州1 1 1 7 查堡垒笪圭! 二! ! 墅! ! 垡堑堡塑苎丝 2 2 有限域上向量空间，辛空间的概念和基本性质 设是有限域f ：“是有限域b 上的n 维向量空间，g l 。( ) 是日上的 n 级殷线性群，g l 。( ) 以下面通常的方式作用在曩“上 砖“g 厶( 品) 砖， ( ( x l ，现，一，x n ) ，t ) 一( z l ，z 2 ，z n ) r 令p 表示向量空间可“的m 维子空间，用同一符号p 表示向量空间p 的 矩阵表示，即尸为秩为m 的m n 矩阵由文献1 1 3 l ，厨维子空间的集合组成 作用下的个轨道，并用n ( m ，n ) 表示曩”中m 维子空闻的个数，有 m 川卜群 用n ( k ，m ，n ) 表示在f j 哪中给定的一个m 维子空问中维子空间的个 哪，m 小嘲。= 群 令n = z “日是有限堍定义z ”z ”阶交错阵耳= ( 三p ：”) 有限 竣b 上的2 v 级辛群被定义为 研k ( b ) = r g k ( 日) ：t k t 7 = k 其中矩阵的乘法为群运算，4 为r 的转置矩阵 令砖”表示有限域上目的2 v 维向量空间，辛群s | b ( 日) 在向量空问 8 河北师范大学硕士学位论文 砖。上的作用定义为 矗”却知( ) 一司驯 ( ( z l ，互2 ，】；知) ，t ) ( l ，z 2 ，z 2 ，) t 具有以上群作用的向量空间日被称作2 v 维辛空间 令p 表示向量空间砖刎的m 维子空间，甩同一符号p 表示向量空间p 的矩阵表示，即p 为秩为m 的m 2 v 维矩阵，矩阵| p 的行构成向量空间p 的基易知p k p 7 是交错阵，假定它的秩为2 s ，那么我们称p 为( m ，5 ) 型子 空间，( m ，0 ) 型子空间被称作全迷向子空闻，( 2 s ，s ) 型子空间被称作非迷向子空 问2 p 维辛空间日中( m ，s ) 型子空间存在的充要条件是2 ssmsp + o ， 曩”中( r n ，s ) 型子空间的个数，记为n ( m ，s ；2 p ) ，且有 p n ( 矿一1 ) n ( m ，s ；2 v ) = q “( v + s - m ) 兰竺甍荔一 n ( 矿1 ) n ( q i 一1 ) t = ll = l 给定一( m ，r ) 型子空间，包含在( m ，r ) 中的( m l ，n ) 型子空间，记为n ( m l ，r l ；m ，r ；2 v ) 且有 m i n m 一2 r m l - 2 r l n ( m l ，r l ；r r t ，r ；2 v ) = 矿“”1 一”1 + 耐+ “1 一耐”一“一耐 k - - - m a x 0 ，”1 一r l l rm - - 2 1 r n( 严一1 )n( q i 一1 ) ：= 1 2 ：竺! ：竺! ! 三竺：堡：! 1 1优i - 2 r 1 - k k 玎( 矿一1 )1 7 ( 一1 ) n ( 旷一1 ) 9 有限几何上d d i 臼u n c t 矩阵的构作 2 - 3d d i s j u n c t 矩阵的概念和基本性质 定义2 3 1 【1 目分量为。或1 的两个二元列向量q ，q 的布尔和avg 2 是指它们的列分量按规则o v l = 1 ，1 v o = 1 ，1 v 1 = 1 ，o v o = o 计算 ：闻 o v o ) o 定义2 3 2 t 1 ”5 1 一个t n ( o ，1 ) 一矩阵肘称为d d i s j u n c t 矩阵如果 矩阵m 的任何d 列的布尔和不包含任何其它列 定义2 3 3 n 一个t n ( o ，1 ) 一矩阵m 称为( d ，r ) 一s e p a r a b l e 矩阵，如果 对矩阵m 中的任意两个不同的d 列集s 1 ，s 2 ，s l 岛， 蜀f = s 2 = d ，它们的 布尔和vg 与vg 至少有r 个不同的分量 ，s l，岛 定义2 3 4 n ，【1 q 一个t n ( 0 ，1 ) 一矩阵m 称为( d ，e ) 一d i s j u n c t 矩阵，如 果从m 中任意取d + 1 列，指定其中的任意一列，在指定列至少有e + 1 行为1 ， 在其它d 列相对应的行为0 注记：定义2 3 4 还有许多等价叙述，这里从珞 命题2 3 5 1 s 0 田设m 为( 0 ，1 ) - 矩阵，屿表示g 列的权重，k 为矩阵 m 任意两列g 和g 列的内积，令型2 呼屿，j = m ；。a x ) q j ，则矩阵m 是 ( d ，e ) 一班巧u 似矩阵，其中d = l 竿j ，e = 盟一瓠一1 矩阵m 某列的权重是 指这一列的j 的个妻虹矩阵m 某行的权重是指这一行的l 的个数 1 0 河北口f 范大学硕士学位论文 命题2 3 6 蝌如果n 的( 0 1 ) 一矩阵 ，为( d ，e ) 一d i s j u n c t 矩阵，则矩 阵可识别d 个有缺陷项，捡测e 个错误，纠正【刳个错误 1 1 第三章有限射影几何上d d i s j u n c t 矩阵的构作 3 1n 阶射影平面上d d i s j u n c t 矩阵的构作 定理3 1 1 设7 r 是n 阶( n 三2 ) 射影平面，m 是一个( n 2 + n + 1 ) 阶方 阵。其行用 上的( n 2 + ，l + 1 ) 个点标定，其列用口上的( n 2 + n + 1 ) 条直线标 定，m 的第i 行第j 列的元素为1 铮第i 行的点在第j 列的直线上则 1 ) 矩阵m 为一个( 舻+ n + 1 ) 阶n d i s j u n c t 矩阵； 2 ) 矩阵肘的转置矩阵7 为一个( 舻+ ，l + 1 ) 阶n d i s j u n c t 矩阵 证明： 1 ) 因n 阶( n22 ) 射影平面”上共有n 2 + n + 1 条直线，共有 n 2 + n + 1 个点所以在n 阶( 扎22 ) 射影平面口上构作的矩阵m 为( 2 2 + n + 1 ) 阶( 0 ，1 ) - 矩阵由命题2 1 5 知，的任意一条直线上有n + 1 个点，故 ，的任意 一列有n + 1 个元素是l ，其它元素为0 从中任取n + l 列三o ，i ，三2 ，三。， 从中任意指定一列比如k ，则列l 0 中总存在至少一行在工。为1 ，在其它列都 为0 否则，l o 与l 1 ，。交出n + 1 个点 又因为由定义2 1 1 中p p 2 ：对b 中任意两条不同的直线l l 与l 2 ，都存 在y 中唯一的一点p 使得p 儿l ，p l l 2 所以岛与l l ，岛，一，工。最多只能交出 n 个点河能有多条直线共点 从而工。与厶，易，k 不可能交出n + 1 个 点，故m 为一个t l d i s j u n c t 矩阵 2 ) 由命题2 1 5 ，过口上任意一点有n + 1 条直线，可知a 矿的任意一列有 礼+ 1 个元素是1 ，其它元素是0 从胪中任取n + 1 列p o ，p l ，p 2 ，从中 任意指定一列，比如珈，则列p o 中总存在至少一行在p 0 为1 ，在其它列为0 否 则，p o 与p l ，以，p n 确定n + 1 条直线 又因为由定义2 1 1 中p p i ：对y 中任意两个不同的点p l 与m ，都存在b 1 2 河北师范大学硕士学位论文 中唯一的一条直线l 使p l 儿，p 2 ，所以皿与p l ，p 2 ，肌最多只能确定出 n 条直线r 可能有多个点共线 从而p 0 与p 1 ，i 2 ，m 不可能确定n + 1 条直 线，故m 为一个n d l 即u n c t 矩阵 定义3 1 2 个( 0 ，1 ) 一矩阵 ，的列称为孤立列是指这一列中的每一个 元素1 所在行的其它位置元素都是0 例如：矩阵m = lo o1 0o l0 ol o 0 01 1l 0 o lo 的第一列为孤立列 定理3 1 3 在n 阶( n 2 ) 射影平面上构作一个( 0 ，1 ) 一矩阵吖，其列 用 上n 2 + n + 1 条直线标定，其行用”上舻+ n + 1 个点的2 一子集标定，矩 阵m 的第i 行第j 列的元素为l 当且仅当标定第i 行的2 一子集中的2 个元素 都在标定第j 列的直线上，则 1 ) 矩阵 f 为( d ，r ) 一s e p a r a b l e 矩阵； 2 ) 矩阵肼为( d ，e ) 一d i s j u n c t 矩阵， 其中1 d n 2 + m r = 2 ( ”；1 ) ，e = ( ”；1 ) 一1 证明； 由定义2 1 ，1 中p p l 知：对矿中任意两个不同的点p l 与m ，都 存在b 中唯一的一条直线l 使p 1 儿，见儿，所以矩阵m 第f 行的2 一子集恰 好出现在b 中唯一的一条直线岛上，即得矩阵m 每一行的权重为l ；另一方 面，由命题2 1 5 知矩阵m 的每一列所对应的壹线恰好包含n + 1 个点，从而 矩阵肘中每列有( 譬1 ) 个元素为1 ，其它元素为o 故矩阵盯每一列的权重为 ( 4 ：1 ) 又因为由定义2 1 ，l 中p 尸2 知：对b 中任意两条不同的直线l 1 与l 2 ， 有限几何上d d i 巧u o c l 矩阵的构作 都存在y 中唯一的一点p 使p l l l ，p l l 2 ，即b 中任意两条直线相交于唯一一 点，所以对矩阵 的任意两列不存在这样的一行使得在这两列同时为1 即任 意两列的内积为0 ，从而 ，的每一列都是孤立列，又共有n 2 + n + 1 列：故 由定义2 3 3 和2 3 4 ，m 显然是( d ，r ) 一s e p a r a b l e 矩阵，( d ，e ) 一d 研u n c t 矩阵， 其中1 曼d n 2 + mr = 2 ( “；1 ) ，e = ( “；1 ) 一1 ， 即1 ) ，2 ) 成立 推论3 1 4 矩阵m 可识别1 1 , 2 + n 个缺陷项，可检出e = ( “；1 ) 一1 个错 误并能纠正l i ：! 1 个错误 证明：因为矩阵m 是( d ，e ) 一d i s j u n c t 矩阵其中1s dsn 2 + n ， e = ( “；1 ) 一1 ，所以由命题2 3 6 直接得证 1 4 河北师范大学硕士学位论文 3 2n 维射影几何上d d i s j u n c t 矩阵的构作 定理3 2 1 设 ，是( 0 ，1 ) 矩阵行和列分别用n 维射影几何p g ( n ，g ) 上 的f 维子空间，m 维子空间标定，m 的第i 行第j 列元素为1 当且仅当第i 行 的l 维子空问包含在第j 列的m 维子空间中，则对于n m l21 ，m 是 【n + 1 。【。n + + l 。 。的( d ，e ) 一出巧u n d 矩阵，其中 a = q 。m 。+ 一l 。一- - 。1 1 l t 一+ l 一 e = 【饼卜m 。 ( iq 。m 。+ 一l 。一- - 。1 1 l 一- ) 一， 而k 1 表示不小于。的整数- 证明： 由命题2 1 6 ，m 的列数为所有m 维子空间的个数u = 蒜 。，行 数为所有f 维子空间的个数6 = n + l 】，故m 为b u 的( 0 ，1 ) 一矩阵；h i 矩阵 的行重与列重分别为包含个给定的f 维子空间的m 维子空间的个数【= 】。， 包含在一个给定的m 维子空间中的l 维子空间的个数 搿 。，即m 的列重 u = 型= 【搿】。 任取矩阵m 的两列，由于这两列由n 维射影几何p g ( n ，口) 上的两个m 维 子空间标定，而这两个m 维子空间的交至多为一个( m 一1 ) 维子空闯，从而这 两个m 维子空间至多同时包含【f 3 】。个l 维子空间，也就是说这两列的内积至 多为 j m l 。，即天= 【f m l 】。因此由命题2 3 5 得m 为6 ”的( d ，e ) 一d i s j u n c t 矩阵其中 d = e = 。m 。+ + 。1 。d 。 。+ m 。 。一t 有限几何上d 一击s j “n “矩阵的构作 由高斯二项式系数表示公式， 所以 篙1 】。 何2 l “ij g f q ”+ 1 一i ) ( 9 “一1 ) f 口一+ 1 一1 ) 可正讯f 讽矛j 再莉 ( 口”+ 1 1 ) ( g ”一1 ) ( q ”。+ 1 1 ) f 口”一1 ) ( 口”一1 1 ) ( g ”一f 一1 ) u 4 + l 一1 o ”一f 一1 a = l 寄j = f 黜卜= 妒q ”+ 一l - - 旷1 1 t 撕一 嚣a 一。( 筹1 - 1 ) 屯 化简得 d = f 再q r n + l _ 1 1 - 1 = 筹岩1 一 一“一1 ，。 其中【叫和卜1 分别表示不大于z 和不小于的整甄 第四章有限域上向量空间和辛空间中 ( d m ，e ) 一d i s j u n c t 矩阵的构作 4 1 有限域上向量空间硝哪中 ( d m ，e ) 一d i s j u n c t 矩阵的构作 引理4 1 1 当k d o b o 时，有( ：) 筝芝g o b 丸 ：q k 。- y _ 一1 1 q d f 一1 1 - ( 矿一1 ) g ( ”) = 瓮芋l q 肛 n ( 矿一1 ) t = 1 的值随着y 的增大而减小 有限几何上d 出s j u n c t 矩阵的构作 证明：易知当d 0 且g 盹，( ) = ( d 一) 是减函甄由引理4 1 2 k 一0 兀( 矿- t ) 号昌生一的值随着增大而减小，故9 ( y ) 的值随着的增大而减小 n i q 一1 = 1 设口是一个素数的幂，日是q 个元素的有限堍日哪是目上的n 维向量 空间 f 是一个( 0 ，1 ) 矩阵，行用日州中所有的d 维子空间a i ，a 2 ，。a 。标