第十二章平衡不完全区组 设计的一般理论 平衡不完全区组设计是一类很基本的设计,既有着许多重的 特款,又有着许多有用的推.本章寸论这类设计的三个…一没性问 题和一个特殊情形,三个一般性间题是:第一,它的关联矩阵及其 牲质以及它们在没计上的反映(§12.1);第二,它的完备化问题 (§12.2);第二,一种有效的构造方法.在§12.4中介绍的一个特 殊情形是=3和λ=1的设计,著名的 Steiner三连系,本章 的结果在后面诸章中将经常用到 §12.1关联矩阵 按定义11.31,一个(b,r,死,4)-设计是“元集S的满足 定条件的·个子集系.正如§5.2中指出的,刻划子集系的一个 有力工具是其关联矩阵,因此可以预料,关联矩阵对区组设计的 升究将起于分重要的作用 设={B1,B1……,Bb}是t元集S的一个(bD3,) 设计,如§5.2,涕的关联阵是一个b×以的(0,1)-矩阼阵 A=(a:1)、1≤≤b,1≤i≤U,(12.1.1) 其中 1,若5;∈B 0,若忘;B;(1≤i≤b,1≤j≤t) 由关联矩阵(121.1)很容易得出(b,,r,k,λ)设计的诸参 数之叫的一些简单关系 定理121.1,如果存(b,,”,,)-设计,则 (12.1.2) 33
(-1)=r(饣-1) (121.3) 证明.设为仼一(b,U,r,,)-设计的关联矩阵.一方 面,因A中每行有收个1,故A中1的总数为;另一方面,因d 中每列有r个1,故A中1的总数又为v。这二数必相等,从而 12.1.2)得 今把矩阵A按列写成分块矩阵的形状: A=(A1A2…A) (12.1.4) 因为内积 (A1,4;)=(2≤j≤), 故 (A1,A1+∴+A)=λ(v-1) (1215) 另一方面,因 0 a;,十 若 故 (41,A+…+1)=∑(一1)=(一1) (1≤b (13.1.6) 比较(12.1.5)和(121.6)即得(121.3).证毕 然也可以把上述证明过程用其所蕴含的组合意义来阐述, 这留给读者作为练习.此外,(12.13)式也可由定理115.2得到 (1216)式表明,毋须事先假定每一元在诸区组中出现的次数 相同,即可推得每元在诸区组中出现的次数都同为 这又一次说明了定义11.3,中的条件(2)可以删去, (1212)和(121.3)是(b23r,,1)-设计存在的最简单的必 要条件,它虽然简单,却能由此断定许多(b,,r,,)-设计不 存在.自然,条件(12.1.2)和(12.13)只是存在(b,U,r,饣,)-设 计的必要条件,并不是充分的 现在来研究关联矩的性质
今约定,在本书的以后章节中,以J表元全为1的"阶方阵: I,表v阶单位阵,H。表元全为1的“×1矩阵、在阶数不会引 起混淆的地方,也何略去下标而分别写成J,I,W 定理1212。设A是一个b×〃的(0,1)-矩阵.那么,A是 个(b,Ur,k,4)-设计的关联矩阵,当且仅当A满足下面两个 关系式 A2=(r-λ)l十J 21.7) 44,=k (1218) 证明.把A表为分块形状(12.1.4),则AA的(i2)元为 内积(A,A;).因此,(121.7)成立的充要条件是 若 (l≤i,j≤v).(12,1.9) 若 因A是(0,1)-矩阵,故是元集S的一个子集系={B,B1,… Bb}的关联矩阵,当i=1时,(4;A1)为S中的元在闭的 诸子集中出现的次数;当;≠j时,(424;)为S中的二元子集 {;,s;}在的诸子集中出现的次数 又,AⅣ的第i个元即B;中所含元素的个数饣。这就是说, (1218)成立的充要条件是子集系沼中每个子集都包含个元 结合上述两个方面即得定理.证毕 今后要多次用到(121.7)的右节的矩阵,为方便计特引入下 面的记号: B (r-λ)l+aJ λ元 (12.1.10) 且常把(12.1.7)叫做关联方程 矩阵B,的行列式的值在一些问题中很有用,且不难求得 引理121。1,设B*=(一)十B这里a和P是复
数,那么 deB*=(a-9)"(F+m一p) (12f,l1) 证明.把dtB*除第一行以外的全部行加到第一行,然后 提出新的第行的公共元(-1)3+a,可有 p B求=(t-1)3十c) (12.1.2) Pp° 在(12.1.2)右节的行列式中,从除第一行外的每一行中减去第 行的倍,可得 detB*m((t-1)于a) ,, 由此立得(121.11).证毕 利用引理121.1可以证明(b,v,r,,)-设计的诸参数间 的一些不等式关系 定理1213.如果(b,,r,,λ)-设计存在,则 b≥ ≥ 121.13 证明.假设(b,”,r:,)设计存在,A是其关联矩阵,且 B*=ATA.如果detB*=0,则r=λ或(t-1)2+r=0. 当r=时,由λ(-1)=r(-1)得v=饣,故此时的区组 设计是平凡的,很明显,当(4-1)+r〓0时的区组设计也 是平凡的.出于§11.3已约定不考虑平凡设计,故有dB*≠0, 因detB*≠0,长B*的秩为t,另一方面,A2A的秩不 能超过A的秩,而A的秩又不能超过b故有(12.113)的前一式 再由砍〓r便得(12.1.13)的第二式,证毕 不等式(121,13)最先由 Fisher发现,通常训做 Fisher不等
很易让另…一些不等式 定理11,4,如果(b,t,r,f,λ)-设计存在,则 b r≥max vib, dul (12.|4) 证明.因为S中的元s在r个区组中出现,而S中的二元子 集{s;sx}在λ个区组中出现,故 (12115) 由(121.3), r-L=rk一 由此和(121.15)得 ≥礼v, (121.16) 因有(12.1.2),放 点(r2-b)=kr2 r(r一x). 由此和(12116)得 r2≥b (121.17) (12.1.3)和(12,1.2)二式相减,得 (b-)=(λ-r)(v-1) 从而 (b-r)(-饣一1)=(b-2r+1)(v-1) 因b≥r,v≥饣十1(见§11.3),放b一2r+λ≥0.此即 b十λ≥2r, (12.1.18) 结合(121.16)一(12.1.18)便得(12.1.14).证毕 个(b,U,r,k,L)-设计的关联矩阵的补A=Jbx-a (见§91)也是一个b×的(0,1)-矩阵,这里Jx,是bד的 全1阵.那么自然会问,A会不会也是某个(b,,r饣,1)设 计的关联矩阵?下面的定理给这个问题以肯定的回答. 定理1215.设A是一个(b,,r,,飞)-设计的关联矩阵 则A是一个(b,”,b一r,一,b一2r+)-设计的关联矩