（基础数学专业论文）射影线性群作用下的区传递4设计.pdf

原创性声明 本人声明，所呈交的学位沦义是本人在导师十 导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或7 c f 电单位的学位或证书而使川过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：互j 生国一 日期：埠年卫月上日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位沦文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位沦文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：兰蛆导师签名诹日期：珥年卫月乒日 摘要 t 一设计的构造是组合设计理论中的重要问题，有着重要的理论意 义和实际应用背景。t 设计的理沦与方法在数理统计、运筹学、信息 沦、和计算机科学中都有着重要的地位。在研究t 设计的构造中，代 数方法占有极其重要的地位，其中，利用射影直线x = g f ( q ) u o o ) 的 k 子集在射影特殊线性群p s l ( 2 ，9 ) 作用下的轨道来构造单纯 3 一( g + l ，k ，允) 设计是近l o 年来活跃在组合界的重要课题，许多国内外 专家通过这方面的工作为丰富3 设计的存在性理论做出了重要贡献。 本文主要讨论了射影线性群p g l ( 2 ，g ) 为自同构的区传递单纯 4 一( q + 1 ，7 ，五) 设计和区传递单纯5 - ( q + l ，6 ，旯) 设计的存在性问题及其构 a 造。 本文的工作共分为三部分。 第一部分是概述，主要讲述了问题发展的历史和现状、采用的主 要方法，并介绍了本文的主要工作。 第二部分主要介绍一些关于群论和组合设计的基础知识。这些都 是本文所要用到的相关概念和结论，从而我们就建立起了本论文的基 本理论体系和构架。 第三部分介绍了在射影线性群p g l ( 2 ，g ) 作用下的区传递4 一设计， 5 设计的存在性问题及其构造，得到了以下结果： 定理l 设g = p g l ( 2 ，g ) ，x = g f ( q ) u o o ，b x | 7 i ，若( x ，b g ) 是一 个4 一( q + l ，7 ，旯) 设计，则下列情形会发生： ( 1 ) q = 1 6 ，允 6 ，2 0 ，6 0 ；( 2 ) q = 3 2 ，五 1 4 ，2 8 ；( 3 ) q = 1 7 ，兄 2 8 ，5 6 ； ( 4 ) q = 2 3 ，五 2 0 ，4 0 ) ；( 5 ) q = 3 7 ，名 4 , 1 2 ，2 4 ；( 6 ) q = 10 7 ，五 4 , 8 ) 定理2 设g = p g l ( 2 ，g ) ，x = g f ( q ) u o o ，b x h ，若( x ? b g ) 是一 个5 一( 9 + l ，6 ，五) 设计，贝0q = 1l ，a = 2 关键词p g l ( 2 ，g ) ，4 一( g + 1 ，7 ，a ) 设计，5 一( g + l ，6 ，五) 设计，区传递 n a bs t r a c t t h ec o n s t r u c t i o no ft - d e s i g n si sa ni m p o r t a n tp r o b l e mw i t hg r e a t t h e o r e t i cs i g n i f i c a n c ea n ds t r o n ga p p l i c a t i o nb a c k g r o u n di nt h ef i e l do f d e s i g nt h e o r y t h et h e o r i e sa n dm e t h o d so ft - d e s i g n sp l a ya ni m p o r t a n t r o l ei nm a t h e m a t i c a ls t a t i s t i c s ，o p e r a t i o n sr e s e a r c h ，i n f o r m a t i o ns c i e n c e a n dc o m p u t e rs c i e n c e a l g e b r a i cm e t h o d sa r ee f f i c i e n tm e t h o d sf o rt h e c o n s t r u c t i o no fs i m p l et - d e s i g n s ，e s p e c i a l l y , t h em e t h o do fu s i n gt h e o r b i t so fk s u b e t so fp r o j e c t i v eli n eu n d e ra c t i o no fp s l ( 2 ，q ) ，t h e p r o j e c t i v es p e c i a ll i n e a rg r o u p t h i sm e t h o di sw i d e l yu s e dr e c e n t 10 y e a r s e x p e r t sa th o m ea n da b r o a dh a v em a d eg r e a tc o n t r i b u t i o nt ot h e s t u d yo ft h ee x i s t e n c eo f3 - d e s i g n sb yu s i n gt h i sm e t h o d t h i st h e s i si s d e v o t e dt od i s c u s s i n gt h ee x i s t e n c ea n dc o n s t r u c t i o no fs i m p l e4 - d e s i g n s a n d5 - d e s i g n sw i t hp g l ( 2 ，q ) a sa na u t o m o r p h is mg r o u p t h i st h e s i si sd e v i d e di n t ot h r e ec h a p t e r s t h ef i r s tc h a p t e ri sd e v o t e dt ot h es u m m a r i z a t i o no ft h ed i s s e r t a t i o n w ed i s s c u s st h ed e v e l o p m e n to ft h es u b j e c t ，i n c l u d i n gt h eh i s t o r ya n d c u r r e n ts i t u a t i o no fi t w ea l s og i v et h em a i nr e s u l t so ft h i st h e s i s i nt h es e c o n dc h a p t e r , w ew i l li n t r o d u c et h ee l e m e n t a r yc o n c e p t sa n d c o n c l u s i o n st h a t w i l lb eu s e di nt h i st h e s i s t h e nw ec a nc o n s t r u c tt h e b a s i ct h e o r ys y s t e mo ft h i st h e s i s i nt h et h i r dc h a p t e r , w ew i l li n t r o d u c et h ee x i s t e n c eo fs i m p l e 3 - d e s i g n s ，a n d4 - d e s i g n sw i t hp g l ( 2 ，q ) a sa na u t o m o r p h i s mg r o u p a n d w eg e tt h em a i nt h e o r e ma sf o l l o w s ： m a i nt h e 。r e ml ：l e t g = p g l ( 2 ，g ) ，x = g f ( g ) u ) ，b ex 吲， i f ( x ，b g ) i sa4 一( 9 + l ，7 ，2 ) d e s i g n ，t h e nt h ef o l l o w i n g sm a yh a p p e n ： ( 1 ) q = 1 6 ，旯 6 7 2 0 ，6 0 ；( 2 ) q = 3 2 ，五 1 4 72 8 ；( 3 ) q = 17 ，五 2 8 ，5 6 ) ； ( 4 ) q = 2 3 ，兄 2 0 ，4 0 ；( 5 ) q = 3 7 ，兄 4 , 1 2 ，2 4 ；( 6 ) g = 1 0 7 ，兄 4 , 8 ) m a i nt h e o r e m2 ：l e tx ：g f ( g ) u o 。) ，g ：p g l ( 2 ，g ) ，be x 1 6 t ，i f ( x ，b 6 ) i sa5 一( g + 1 ，6 ，2 ) d e s i g n ，t h e nq = 1l ，五= 2 k e yw o r d s p g l ( 2 ，g ) ，4 一( q + 1 ，7 ，五) d e s i g n s ，5 一( g + l ，6 ，兄) d e s i g n s ， b l o c k t r a n s i t i v e l y i v ， 目录 第一章绪沦1 1 1 研究背景与研究现状1 1 2 本文：卜要工作5 第二章基础知谚 7 2 1 群论知识7 2 1 1 群与子群7 2 1 2 正规予群，商群和导群9 2 1 3 置换群11 2 1 4 线性群13 2 2 纽合设计知识1 4 2 2 1 有限关联结构1 4 2 2 2t 一设计l6 2 2 3 设计的自同构群1 8 第三章p g l ( 2 ，g ) 作用下的区传递4 一( g + 1 ，7 ，旯) 设计1 9 3 1 引言1 9 3 2 主要结果2 0 第四章p g l ( 2 ，q ) 作用下的区传递5 一( g + l ，6 ，允) 设计2 6 4 1 引言2 6 4 2 主要结果2 7 参考文献2 9 附录l 3 3 附j j ：2 4 0 致谢4 3 攻读学位期间主要研究成果4 4 v 硕十学位沦艾第一章绪沦 1 1 研究背景与研究现状 第一章绪论 先介纠儿个定义 定义1 1 1 参数为，一( v ，k ，a ) 的一个设计定义为符合以下条f t ：的一对符号 ( x ，b ) ： ( i ) x 是一个1 ，一集合； ( i i ) b 是x 的一组k 一子集； ( i i i ) x 的任意给定的，一子集都恰好含在b 的旯个成员中 x 的元素称为点，b 的成员称为区组若一个，一( v ，k ，旯) 设计不包含重复区组【就 叫做单纯的 定义1 1 2 令g 为x 的全对称群s y m ( x ) 的一个子群g 以一种自然的方 式作用于x 的子集：若g g ，s x ，则g ( s ) = g ( x ) ：x s ) g 叫做3 一设计 ( x ，b ) 的自同构群，若对任意g g 和s b 都有g ( s ) b 设s x ，令 g ( s ) = g ( s ) ：g g ) ； g s = g g ：g ( s ) = s ) ： 则g ( s ) 和g s 分别叫做s 的轨道和稳定子群 定理1 1 1 【5 1g 是3 设计( x ，b ) 的自同构群当且仅当b 是g 作用下x 的 k 一子集轨道的并 定义1 1 3 假设g 为1 ，元集合x 的全对称群s y m ( x ) 的一个子群，令 r l ，r 2 ，r m 是七一子集的轨道，a i ，a 2 ，m 是卜- 子集的轨道定义卜- 子集 与k 一子集的轨道关联矩阵么政为一，n 七阶矩阵，其中 硕十学何论文 第一章绪沦 爿，。 ，f - ， = i k 1 1 ，：tgk i ， 其中t a f 山定义1 1 3 可知存在一一个以g 为自同构群的单纯f 一( v ，k ，五) 设计当e l 仪当存住 ( 0 ，1 ) 解u 使得矩阵方程 成立令 a ，k u = 【五】 b = uf ， ，t ；l i = l 则( x ，b ) 即足一个t 一( v ，k ，五) 设计 定义1 1 4 令g 为素数幂，x = 卯( g ) u ) 定义 们毯。o 扎o o + 口= 口+ o o 吨一o o ，筹= 虽， 其蝴叫咖m 足酬o ，舸定义函数 f ：x 专x ， 其中 似) = 而a x + b ， f 叫做线性分式 d e t 厂= 层宝i = 日d 一6 c 叫做厂的行列式所有行列式为非零平方的线性分式的集合构成一个群，叫做线性 分式群，i 酢l f ( 2 ，q ) ，它同构于射影特殊线性群p s l ( 2 ，q ) t 一设计的构造是组合设计领域中的一个重要问题目前有关2 设计的结果已 经非常丰富，3 设计的结果也比较丰富因此4 设计5 设计的构造问题成为重要课 题而单纯4 设计，5 设计的构造尤其重要 在单纯t 设计的构造中，多重传递群占有极其重要的地位，它们的轨道是 2 硕十学位沦文第一章绪论 以射影特殊线性群p g l ( 2 ，q ) 为自刚构群的区传递单纯4 一设计的存在性问题- f ( 1 ) q = 2 盯时以p s l ( 2 ，q ) 为自同构群的单纯3 一设计 在这部分中，我们总是假设g = p s l ( 2 ，2 盯) ，x = g f ( 2 疗) u ) ，所指轨道 定理1 1 2 删p s l ( 2 ，g ) 在射影线x 上作用的彳3 4 矩阵为： 2 巴掣 若刀为偶数， 巳掣 若刀为奇数 定理1 1 3 p s l ( 2 ，g ) 在射影线x 上作用的a 3 5 矩阵为： 糍攀 ，糍攀 若n 为偶数， 若行为奇数 定理1 1 4 西2 1 任意6 子集的轨道是个3 一( 2 疗+ l ，6 ，彳) 设计，其中 a 2 0 ，2 4 ，6 0 ，1 2 0 ) 硕f 7 ”f - 何论文第一章绪论 定理1 1 5 哑1 任意7 子集的轨道是一个3 一( 2 打+ l ，7 ，a ) 设计，其中 兄 1 5 ，2 1 ，7 0 ，1 0 5 ，2 1 0 ) ( 2 ) q 兰3 ( m o d 4 ) 时以e s l ( 2 ，q ) 为自同构群的单纯3 一设计 在这一部分中，我们总是假设q 兰3 ( m o d4 ) ，g = p s ( 2 g ) ，x = g f ( q ) u o o 所指轨道郜是在g = p s l ( 2 ，q ) 作用下的轨道熟知g 是3 齐次的，故其任意不相 交的k 子集的并构成一个单纯3 一( r + l ，k ，旯) 设计，其中旯是一个正整数。 定理1 1 6 1 任意4 一子集的轨道是一个3 - ( q + l ，4 ，五) 设计，其中2 1 ，3 ，6 ) 定理1 1 7 阳1 任意5 一子集的轨道是一个3 一( g + l ，5 ，力) 设计，其中 兄 6 ，1 0 ，3 0 ) 定理1 1 8 町任意6 一子集的轨道是一个3 一( g + l ，6 ，力) 设计，其中 五 1 0 ，1 2 ，2 0 ，3 0 ，6 0 ) ( 2 ) q 三l ( m o d 4 ) 时以e s l ( 2 ，q ) 为自同构群的单纯3 - 设计 在这一部分中，我们总是假设g 三l ( m o d 4 ) ，g = p s l ( 2 ，g ) ，x = a f ( q ) u o o 所指轨道都是在g = e s l ( 2 ，q ) 作用下的轨道熟知此时g 不是3 齐次的，故不能 保证其k 一子集的轨道构成一个单纯3 一( 2 疗+ l ，k ，五) 设计，其中允是一个f 整数 因此对于解决单纯3 设计在其轨道上的分布问题而言要比前两种难度大但 m s k e r a n e n ，d l k r e h e r 和p j s s h i u e 在文献【2 0 】中给出了这样的结论：x 的3 一 子集的轨道恰有两条，分别是 l = g ( o ，1 ，o 。) ) 和2 = g ( o ，7 ，o 。) ) ， 其中7 是g f ( q ) 的一个本原元，每条轨道恰好包含x 的一半3 一子集这一结论的 给出对于解决这类问题起了关键性的作用经过努力，m s k e r a n e n ，d l k r e h e r 和 p j s s h i u e 等人解决了四元系在4 子集的轨道分布问题，最后它们给出了轨道关 联矩阵彳3 4 4 硕斗：学伉沦文第一章绪论 定理1 1 9 乜们p s l ( 2 ，g ) 在射影线x = g f ( q ) j o o 上作用的a 3 1 矩阵为： i2 03066 600 066 6 l 10 20300 066 666 6i 若q 三l ( m o d2 4 ) ， i ( q - 2 5 ) 2 4 ( q - 2 5 ) 2 4 ( 3 q - 3 ) 2 4i 1 - 3 66 600 066 6 l 300 066 666 6 f 名? q 三5 ( 1 n o d2 4 ) ， l ( g 一5 ) 2 4 ( g 一5 ) 2 4 ( 3 q 一15 ) 2 4 j - 1 0 66 600 066 6 10 100 066 666 6l 若q 兰9 ( m o d2 4 ) ， l ( 9 9 ) 2 4( q 一9 ) 2 4 ( 3 q 一3 ) 2 4 j r 2 0366 600 06 6 6 10 2300 066 666 6i 若q 三13 ( m o d2 4 ) ， l ( g 一1 3 ) 2 4( q 一13 ) 2 4 ( 3 q i5 ) 2 4 j r 30 66 600 066 6 10 300 066 666 6i 若q 兰17 ( m o d2 4 ) l ( q 一1 7 ) 2 4 ( q 一1 7 ) 2 4 ( 3 q 一3 ) 2 4 j 1 2 本文主要工作 本文主要讨论p g l ( 2 ，q ) 区传递作用下的4 一( g + l ，7 ，兄) 设计和 p g l ( 2 ，9 ) 区传递作用下的5 - ( q + 1 ，6 ，力) 设计我们以p g l ( 2 ，g ) 区传递作用下 的4 一( q + l ，7 ，五) 设计为例来作介绍： 设g = p g l ( 2 ，g ) ，x = g f ( q ) j o o ) ，g 作用在x 上，则自然的作用在x 1 7 i 上若b x 1 7 i ( x ，b c ) 是一个4 一( g + 1 ，7 ，五) 设计，则显然g 是区传递的根据组 p 睁臀 5 硕十学何论文第一章绪论 五l g 8 i ( g 一2 ) = 8 4 0 这里q 是一个素数幂，所以我们可以把所有的q 的可能值均列出来，那么与之对应 的五的值也可铭出来然后根据群论和没计的付1 关知i j 尽可能的排除一些兄的值 最后冉利j jm a t l a b 来构造设计 6 硕 学位论文第二章基础知识 2 1 群论知识 2 1 1 群与子群 第二章基础知识 定义一个群有多种不同的方式 定义2 1 1 1 称非空集合g 为一个群，如果在g 中定义了一个二元运算， 丌l l 做乘法，它满足 ( 1 ) 结合律：( a b ) c = a ( b c ) ，c l , b ，c g ； ( 2 ) 存在单位元素：存在l g ，使得对任意的a g ，恒有 l a = a l = a ： ( 3 ) 存在逆元素：对任意的a g ，存在口一g ，使得 口口一i ：a - l a ：1 定义2 1 1 2 称非空集合g 为一个群，如果在g 中定义了一个二元运算，叫 做乘法，它满足 ( 1 ) 结合律：( a b ) c = a ( b c ) ，口，b ，c g ； ( 4 ) 对任意的口，b g ，存在x ，y g ，满足a x = b 和y a = b 定义2 1 1 1 和定义2 1 1 2 是等价的 在任一群g 中，还成立下述运算规律： ( 5 ) 消去律：对任意的a ，b ，c g 成立 a c = b c ：口= b 和 c o = c b ：口= b 一般来说，条件( 1 ) 和( 5 ) 不足以定义一个群。例如全体下整数集合对 于加法就满足条件( 1 ) 和( 5 ) ，但它不是群可是我们有下面的结论： 定理2 1 1 1 9 1 有限非空集合g 是群，如果g 中定义了个二元运算，满足 7 硕十学何论文第二章基础文i j 识 条件( 1 ) 利( 5 ) 设g 是群，h ，k 是g 的子集，规定h ，k 的乘积为 h k = h kh 月，k k ) 如果k = a ) ，仅由一个元素口组成，则简记为h a = h a ；类似地有a h 等 我们还规定 h = h 。1 i h h ) 定义2 1 1 3 称群g 的非空子集日为g 的子群，如果h 2 h ，日c zh 这 时记作h g 定义2 1 1 4 群g 的子群m 称为极大子群，如果mcg ，且如果有g 的子 群t 满足m t g ，那么总有t = m 或者t = g 定义2 1 1 5 设h g ，口g 称形如a h ( 胁) 的子集为何的一个左( 右) 陪 集容易验证a h ：b h a - l b h 类似地有h a ：h b 营a - i b h 定理2 1 1 2 呻1 ( l a g r a n g e ) 设g 是有限群，h g ， _ ! i l j l g i = i h i i g ：h i 定理2 1 1 3 哺钔设g 是群，日和k 是g 的有限子群，则 i h k i = 阿t h 田i k i 定义2 1 1 6 设g 为群，口，g g ，规定：口x = g a f t , ，称为a 在g 下的共轭 变形称g 中元“，b ( 或子集h ，k ) 在g 中共轭，若存在元g g ，使得 矿= b ( h g = k ) 共轭关系是等价关系于是群g 的所有元素依共轭关系可划分若干等价类， 称之为共轭类 定义2 1 1 7 设g 为群，h 是g 的子集，g g 若日g = h ，则称元素g 正 规化h ，而称g 中所有正规化的元素的集合 n a ( h ) = g g i h g = 日) 为在g 中的正规化子 又若元素g 满足对所有h h 恒有h g = h ，则称g 元素中心化h ，而称g 中 硕十学位论文 第一二章基础失i l 谚3 所有中心化h 的元素集合 c ：；( h ) = g gh 。= 厅，v h ) 为在g 中的中心化子 规定z ( o ) = g ；( g ) ，称之为群g 的中心 定理2 1 1 4 俺们g 中元口所属的轭类c 的k 度l c l = i g ：g ；( 口) 1 凶此，l c l 也 是i g i 的因子类似的，子群( 子集) h 的共轭予群( 子集) 的个数为i g ：( j ( ) i 也是 l g i 的因子 定义2 1 1 8 我们称映射口：g 专g i 为群g 到g l 的一个同态映射，如果 ( a b ) 口= a a b a , v a ，b g 如果口满( 单) 射，则称为满( 单) 同态；而如果口是双射，即一一映射，则称t 2 为g 到g i 的同构映射这时称群g 和g l 同构，记作g 兰g 1 群g 到自身的州念及同构 具有重要的意义。我们称之为群g 的自同态和自同构 2 1 2 正规子群，商群和导群 定义2 1 2 1 群g 的子群h 称为g 的正规子群，如果对于任意的x g ，都 有x _ 1 h x h ，记为hqg 任意群g 1 至少有两个币规子群g 和1 ，叫做平凡正 规子群 定义2 1 - 2 2 只有平凡j 下规子群的群叫做单群 设qg i gn 的所有陪集的集合为否= g 陪g ) 定y - 6 中的乘法为 群子集的乘法，即 ( n g ) ( n h ) = n ( g n ) h = ( g ) 向= n z g h = n g h 定理2 1 2 1 【5 们g 对乘法( ：i c ) 封闭，并且成为一个群，叫做g 对的商群，记 作否= 定理2 1 2 2 删( 同态基本定理) ( 1 ) 设q g ，则映射y ：g 一g 是g 到多的同念映射，满足 9 硕十学位论文第二章基础知识 k e r y = n ，g r = 这样的y 叫做g 到乡上的自然f 司态 ( 2 ) 改口：g - - - h 是同态映射，f ：) 1 1 jk e 厂a 司g ，且g 口兰9 乞r 口 定理2 1 2 3 呻1 ( 第一同构定理) 设qg ，mqg ，且n m ，则 q 并且 ( ) ( ) 兰 定理2 2 2 4 脚1 ( 第二同构定理) 设h g ，kqg ，则( nk ) q 日，并且 吆兰nkk 一nk 定义2 1 2 3 群g 称为其子群h ，k 的直积，如果下面的条件满足： ( 1 ) h 司g ，k 司g ； ( 2 ) g = h k ： ( 3 ) hnk = 1 此时记为g = k 定义2 1 2 4 设n ，f 为两个抽象群，口：f a u t ( n ) 是同态映射，则n 和 f 关于口的半直积g = n 。f 规定为 ( “，x ) ( 6 ，y ) = ( a b 。一，x y ) 和f 关于口的半直积g = n x 。f ，也可记为n ：f ，即n 被f 的可裂扩张 定义2 1 2 5 设g 为有限群，群6 的基柱( s o c l e ) 是指g 的所有极j , i f 规 子群的直积，记为s o c ( g ) 有限群g 称为几乎单群，如果存在非交换单群丁使得 t = s o c ( g ) q g a u t ( t ) 定义2 1 2 6 g 的导群g 。是由所有换位子 口一b a b a ，b g ) 生成的群 g 也是使g k 为交换群的最小正规子群k 我们定义子群列 g = g ( o ) 2 g ( ) 2 g ( 2 ) 2 ， 这里g 7 是g 1 的导群，( 待l ，2 ，3 ，) 称子群列为g 的导群列 1 0 、l f ， fx口 、， x 吼，- 、，i = f =g 为算运 硕十学1 市论文 第二章基础知识 设g 为群，称群列 ， 1 = z o ( g ) z i ( g ) z ，( g ) ， ( ；g e e 互( g ) 为g 的中心) y , jg 的中心群列，如果埘任意的n ，乙( g ) z ，h ( g ) 是 g 互，一。( g ) 的中心 如果g 的导群列终止于l ，则称g 是可解的：如果g 的中心群列终i e 于g ， 则称g 足幂零的 2 1 3 置换群 定义2 1 3 1 q 上的一个置换就是q 到自身的一个一一映射如果我们根据 公式口刖= ，) 9 来定义q 上置换p ，q 的乘积，那么q 上的全部置换对于上述运算 构成一个群，称之为对称群，记为s q 并且，s q 的予群称为置换张 定义2 1 3 2 设q = 口，厂，) 是一个有限集合，其元素称为点表示q 上的对称群g 在q 上f 拘f g f f l 指的是g 到s o 内的一个同念，即对每个元素 x g ，对应q 上的一个置换 矽( x ) ：口h 口。， 并且满足： ( 口。) ，= 口r yx ，y g ，口q 如果k e r ( o ) = 1 ，则称g 忠实地作用在q 上，这时g 看作q 上的置换群如果 k e r ( o ) = g ，则称g 平凡地作用在q 上 定义2 1 3 3 g 口= x g l a = a 。) ，则q 是g 的一个子群，称之为点口的稳 定子群对于任意的yeg ，都有g 口，= j ，一瓯y 定义2 1 3 4 设群g 作用在集合q 上，称二元素口，q 为等价的，记作 口一，如果存在x g ，使得a 。= 易验证“关系是q 上的等价关系q 对 “一”的一个等价类叫做g 在q 上的一个轨道一个轨道所包含的元素的个数叫 做该轨道的长 x , l ：j ：a q ，令口“= 缸。l x g ) ，n a “是包含口的轨道 1 1 硕十学何论文第二章基础知识 定义2 1 3 5 如果g 在q 上只有一个轨道，即q 本身，则称g 在q 上的作用 是传递的 定义2 1 3 6 设g 是q 卜的一个置换群，简言之：g s q 如果q 的一个子 集满足= 公i ，我们就说足g 的一个不动区，或者说在g 下不动，这时，每 个g g 诱导出a 上的一个置换g a 由所有g g 诱导 l 的g j 的全体组成的集合 g a 称为g 在上的成分g 是上的一个置换群显然，g 寸g 是一个同态映 射：g - - 写g 如果这个映射是一个同构映射， g i = i c l ，那么成分g 就称为真 实的 显然，g 的两个不动区的交与并还是不动区，对每一个子集r q ，g 的包 含r 的最小的不动区是r “ q 上的每个群g 都有平凡不动区中和q 如果g 没有其它不动区，g 称为 传递的否则就成为非传递的当( a ) 是一个极小不动区时，h 茈：7 g a 是传 递的在这种情形，称为g 的一个轨道或传递集 定义2 1 3 7 设g s s q ，a q g 中那些使中每个点都保持各自不动的 置换组成g 的一个子群g 如果只包含一个点口，我们就记g = g 。 定理2 1 3 1m 1 每个点口q 恰属于g 的一个传递集= 口“两个点口和 属于同一个传递集当且仅当对某个g g ，= 口g 定理2 1 3 2 删如果是g 的一个传递集并且s s q ，那么公是s 一g ，的一 个传递集 定理2 1 3 3 h 町对每个g g 和q ，有g g a g = g 丛特别地，如果g 保持 不动，那么g 多，g g 兰g 定理2 1 3 4 删( 轨道长定理) l g i l a g i - - l a l 定理2 1 3 5 脚1 设p 是一个素数，p m 是p g l 的一个因子p 是g 的一个 s y l 。w p 一子群那么p ”也是l 口i 的一个因子 1 2 定理2 1 3 6 m 1 设子群u 瓯具有下述性质：瓯的一个子群v 只要在g 中 与u 共轭，就一定在瓯中与它共轭设是u 在g 中的一规化子，如果g 在q 上 是传递的，那么在u 的全部不动点组成的集合上是f 冬递的 定理2 1 3 7 h 6 3 在一个传递群g 中，g 。的正舰化二f 在吒保持彳i 动的点上是 传递的 定理2 1 3 8 阻町在一个传递群g 中，g 。的每一个s y l o w 子群u 的讵规化子 在u 保持不动的点上是传递的 定义2 1 3 8 群g 传递地作用在q 上令q ，如果对于任意的g g ，都 有s = 或sna = o ，则称是g 作用在q 上的一个区显然，q ，空集a 以及 单点集( 口) 都是g 的区，则称它们是g 的平凡区如果g 仅有平凡区，就称g 作用 在q 上是本原的 定义2 1 3 9 设g 是q 上的一个置换群，如果对于任意口q ，都有g 口= 1 ， 则称g 是半正则的如果g 是传递的，则称g 是正则的 2 1 4 线性群 定义2 1 4 - 1 设f 为一域，是v = ( f ，胛) 上刀维向量空间y 的全体可逆线性 变换对于线性变换的乘积构成一个群，叫做v 上一般线性群取定v 的一组基 v i ，v 2 ，k ，则任意线性变换唯一对应一个刀线可逆方阵么从而也可将g ( 刀，f ) 视为f 上全体非奇异r l xr l 矩阵乘法构成的群，考虑g l ( n ，f ) 到乘法群f + 的映射 gi - - - - ) d e t ( g ) ，这是一个满同态，记同态核为： s l ( n ，f ) = g g l ( n ，f ) l d e t ( g ) = 1 ) ， 称为特殊线性群它是一般线性群的正规子群 记e 为f 上甩级单位矩阵，令z = a e l a f ) 为g l ( n ，f ) 之中心，有： p g l ( n ，f ) = g l ( n ，f ) z ， 硕j = 学何论文第：章基础知识 称为一般射影群它是疗一l 维射影空i h j 尸( 刀一1 ，) 上的更换群 进一步，记 p s l ( n ，f ) = s l ( n ，f ) ( s l ( n ，f ) nz ) ， 称为特殊射影群，其中，s l ( ”f ) nz = 订i 订f ，“”= 1 ) 假定f = g f ( q ) ，是包含q 个元素的有限域，则上述各群分别记作 g l ( n ，g ) ，s l ( n ，g ) ，p g l ( n ，g ) ，p s l ( n ，q ) 定理2 1 4 1 5 9 】( 1 ) i g l ( n ，g ) i = ( 口疗- 1 ) ( q 疗- q ) ( g 肝- q 川) ( 2 ) i s l ( n ，q ) i = i p g l ( n ，g ) l = l 吼( 门，q ) l ( q - 1 ) ( 3 ) l p s l ( n ，q ) l - l s l ( n ，q ) l ( n ，q 1 ) 2 2 组合设计知识 2 2 1 有限关联结构 组合设计理论的主要研究对象是各种有限关联结构 定义2 2 1 1 设y 与b 为两个不相交集合，为y 与b 之间的一个二元关系， 即，vxb ，则称d = ( v ，b ，) 为一个关联结构v 的元素叫做点，b 的元素叫做 区组，叫做关联关系设p v ，b b ，若( p ，b ) i ，则称点p 与区组b 关联，记 作p b ，若p 不与b 关联，则记作掷 有时为了强调关联结构的几何意义，也把区组叫做直线此时，”p b 也可以 叫做“点p 在直线b 上 或“直线b 经过点p ” 本节只讨论有限关联结构，即v 与b 都是有限集的关联结构当d = ( v ，b ，) 为有限关联结构时，常以y 表示集合v 的基数，以b 表示b 的基数，即 v - - i v l ，b = i b i 并称v 为d 的阶 定义2 2 1 2 设d l = ( k ，b 。，厶) 与d 2 = ( ，b ：，1 2 ) 为两个有限关联结构设 1 4 硕十学侮论文第一：章基础知识 仃：kus ，一心ub ：为满足下述条件的一个双射： ( i ) 仃( k ) = k ，o - ( b 1 ) = b2 o ， ( ii ) 对任意p 巧与任意b b 。，当且仪当p l 。b 时彳有o - ( p ) 2 0 - ( b ) ， 则称仃为d 到以上的一个同构，此时称d i 与d ：为两个同 = = 的关联结构，特 别地，当d 。= d 2 = d 时，d 剑它自身的同构叫自同构d 的全体e 仆司构关于映射 的乘法组成一个群，l l t l 作d 的全自同构群，记作a u t ( d ) a u t ( d ) 的任一子群都叫 做d 的自l 司构群 有限关联结构w 以用它的关联矩阵来刻划 定义2 2 1 3 设矿= n ，p 2 ，p ，) ，b = e ，岛，b a ，d = ( y ，b ，) 为有限关 联结构对l f v , 1 j b ，令 l ，若p i i b l n 21 0 若p | 则v x b ( o ，1 ) 一矩阵 a = q ，ia i ，2 口2 i口2 2 a v 1口，。2 叫做d 的关联矩阵 对l f y ，令表示b 中与p i 关联的区组数：对l 6 令k ，表示v 中与q 相关联的点的个数：对1 f ，v ，i ，令乃，表示b 巾同时与点p ，及p ，关联的区 组数叫做点p ，的重复度，k ，叫做区组e 的容量( 或长度) ，a 叫做点p ，与p ， 的相遇数，l 等于么的第的列和，而 ，则是彳的第，行与第行的内积因此， 用两种方法计算彳中的l 的个数，可以得到下面等式： 令氓表示元素全为1 的v 维行向量，a 7 1 表示彳的转置矩阵，则 西 吼吒； q 厶n 。问 i i r 1 ， 硕十学位论文第二章基础知识 a a 7 = 1 2 如 “旯。2 丑， 如， ： 气 ，a = ( k i ，七2 ，k ) 设d = ( ，b ，) 为有限关联结构对p v ，令0 表示点p 的重复度：对b b ， 令k 占表示区组b 的容量：对v 的任一，元子集s ，令五表示与s 中每一点都关联 的区组个数在设计理论的研究中，以下条件是最常用的： ( 1 ) 正则性：存在常数， 0 ，使对所有p v 都有0 = ， ( 2 ) 均匀性：存在常数k 0 ，使对所有b b 都有心= k ( 3 ) f 一平衡性：对给定的正整数，存在常数五 0 ，使对v 的任一，元子集s 都有疋= 五 1 一平衡性即正则性，2 一平衡性通常就叫作平衡性 2 2 2t 一设计 在本节中，我们要从另一个角度来推广b b 设计的概念下面要研究的是一 类满足正则性、均匀性和，_ 平衡性条件的有限关联结构 定义2 2 2 1 设d = ( v ，b ) 为有限关联结构若下列条件满足： ( i ) i v l = v ： ( i i ) 存在常数七，使对所有b b ，都有k 口= 七： ( i ii ) 对给定的正整数，存在常数五 0 ，使对v 的任意一个，元子集s ，都有 五= 兄 则称d 为一个t - ( v ，k ，见) 设计，简称t 一设计f 一( 1 ，七，a ) 常记作s ( f ，k ，1 ，) 设d = ( v ，b ) 为一个，一( 1 ，七，名) 设计如果v 的每个七元子集都在b 中出现相 同的次数，则称d 为平凡的f 一设计例如当v k + t 时，任一，一( v ，k ，五) 设计都是 1 6 硕十学位论文第一二章基础生i i l 5 平凡的 ，_ 设计的若干特殊类型： ( i ) ，= 1 ，1 一设计也叫战术构形或构形 ( ii ) f _ 2 ，2 一设计即熟知的b i b 设计 2 (