As Evenly As Possible. Block Designs and Error Correcting Codes

Introduction

Moto-cross Races

十六个摩托越野比赛参赛者，需要评比第一名和其他名次。场地一次只允许四个人同时比赛，就是一场小组赛。每组得分不同，最后根据得分多少得出第一名和其他名次。
问题在于如何组织这些小组赛。比如只需要选出第一名，那么就很简单。十六个人分成四组，每组的第一名再进行一场比赛即可。但是如果还需要选出第二名，这种方法就不可行，因为第二名和可能在第一轮小组赛和第一名分到了一起，那么就没有机会参加第二轮了。
另一个极端的方法很公平合理，就是比赛会太长。比如进行$<script type="math/tex; mode=display">\begin{pmatrix}16\\4\end{pmatrix}$=1820场比赛，按照总得分依次排序。问题是1820场比赛实在太多了。就算一场比赛十分钟，没有休息时间，也需要十二天多才能结束比赛。观众不会看这么久，参赛者也不可能坚持。
所以问题就是要如何安排这些小组赛，使得比赛公平，同时还是能保持适合的长度。长度很容易衡量，公平就稍微复杂一点。首先参赛者要参与同样数量的比赛来积分。第二要充分利用场地，尽可能多的人参赛。任意两个参赛者至少交手过一次，如果能把至少一次变成精确一次，那就更好了。如果两个参赛者最后积分一样，那么看他们的交手历史，胜者比分更高。
如果能设计出这样的比赛，那么每位参赛者至少需要参加五场小组赛。这是因为每位参赛者至少需要在一场比赛中与其他十五个参赛者竞争，但在任何一场比赛中只能与三名参赛者竞争。接着分析，十六个参赛者中的每人至少有五场比赛意味着至少有80个有序对$(d, H)$，其中$d$是参加比赛$H$的参赛者。由于每场比赛由四名参赛者组成，这意味着必须至少有20场小组赛。
那么问题又变成了最小值，20，是否合理呢？也就是说组织20场小组赛。恰好每个参赛者参加其中五场，和其他十五个参赛者进行了比赛，也就是任意$d_1,d_2$两个参赛者都交过手。
这个问题的答案显然不是很显然，但确实是可以做到的。下面就是一个示例。如果20场比赛，每场十分钟，中间休息两分钟，19个中场休息，那么接近四个小时就能完成比赛了。

Example 17.1. 下面是一个满足所有条件的赛程。每个参赛者参加了五场比赛，每场包含四个参赛者，任意两个参赛者，恰好只交手一次。

(1) 1, 2, 3, 4
(2) 5, 6, 7, 8
(3) 9, 10, 11, 12
(4) 13, 14, 15, 16

(5) 1, 5, 9, 13
(6) 2, 6, 10, 14
(7) 3, 7, 11, 15
(8) 4, 8, 12, 16

(9) 1, 6, 11, 16
(10) 2, 5, 12, 15
(11) 3, 8, 9, 14
(12) 4, 7, 10, 13

(13) 1, 7, 12, 14
(14) 2, 8, 11, 13
(15) 3, 5, 10, 16
(16) 4, 6, 9, 15

(17) 1, 8, 10, 15
(18) 2, 7, 9, 16
(19) 3, 6, 12, 13
(20) 4, 5, 11, 14

这样的安排是如何形成的呢？为什么满足这些需求的赛程是存在的呢？下面让我们慢慢的解答。

Incompatible Computer Programs

假设我们下载了七个程序。我们的计算机有足够的内存同时运行任意的三个。我们需要测试两两之间的兼容性，来确定七个程序中没有两个程序$A,B$会导致错误（非内存错误）。假设所有的兼容性问题一定是一对程序导致的，也就是说程序子集$S$不能运行的话，一定有一个两个元素的子集$T\subset S$中的那两个程序不能兼容。如果一次测试需要三分钟，那么最高效的测试方式是什么呢？
在找到最高效的方式之前，先看看上限是什么。显然，$<script type="math/tex; mode=display">\begin{pmatrix}7\\3\end{pmatrix}$=35分钟是上限，因为把所有可能性都测试了一遍，但是浪费也是巨大的，对于某一对程序而言，一起测试了五次（三个程序选定两个，第三个有五种可能性）。一个更好的上限是$<script type="math/tex; mode=display">\begin{pmatrix}7\\2\end{pmatrix}$=21分钟，两两测试即可。这种方式也没能充分利用内存，三个程序一起测试。
最佳方案是什么呢？每一次都尽可能运行三个程序，不浪费。因为运行两个程序和三个程序的时间成本是一样的。
令$b$是最佳测试方案的三元组个数。一个三元组测试等价的测试了三对程序，那么最多测试了$3b$对，如果各不相同，那么恰好是$3b$对。从另一个角度看，必须测试21对程序。那么$3b\geq 21$，也就是说$b\geq 7$。
下面的问题是如何构造一个只有七个三元组的测试了。如下面的例子。
Example 17.2. 下面的$\mathcal{F}$是集合$S=\{A,B,C,D,E,F,G\}$的三元组子集的集合，且满足任意两个元素$x,y\in S$，在$\mathcal{F}$中都有唯一的元素包含$x,y$。

{A, B, D},
{B, C, E},
{A, F, C},
{A, E, G},
{B, F, G},
{C, D, G},
{D, E, F}.

一种验证的方式是验证某个$x\in S$，$x$恰巧出现在$\mathcal{F}$的三个集合中，除了$x$之外的元素在这三个集合中也只出现一次。

上面的测试计划只要七分钟。同时，完全没有浪费，因为每对仅测试一次。通常情况下，像这样毫无浪费是不可行的。比如，我们测试八个程序，每组三个程序。对的数量是$<script type="math/tex; mode=display">\begin{pmatrix}8\\2\end{pmatrix}$=28，不是三的整数倍，所以至少要测试十次，这意味着有几个对测试超过一次。再比如测试六个程序，总共有$<script type="math/tex; mode=display">\begin{pmatrix}6\\2\end{pmatrix}$=15，虽然15能够被3整除，但是也不能完全不浪费。因为选择一个程序，剩余五个程序，三元组去掉被选择的程序之后，只有两个空位置，测试两次不够，测试三次会出现浪费。
正如我们看到的，很多原因都会导致完全不浪费的计划是不存在的。不过，有的时候无法证明它们不存在，可能是由于某些不存在的原因是未知的。由此得到一系列的问题，即存在完全不浪费的计划的冲要条件。

Balanced Incomplete Block Designs

令$S$是$v$个元素的有限集合，这些元素被称为顶点。令$\mathcal{B}$是$b$个$S$的非空子集的集合，称为块(block)。那么$(S,\mathcal{B})$被称为块设计(block design)或简称为设计。$\mathcal{B}$中的块可以出现不止一次，也就是说是可以重复的。我们大部分例子都不包含重复块。
如果一个设计$(S,\mathcal{B})$至少有一块不包含$S$所有的顶点，那么称为不完全的(incomplete)，否则是完全的(complete)。完全设计就是包含所有的点，没有太多意思。所以后续的例子都是不玩全的。
如果一个设计每个块都包含$k$个顶点，那么称为均匀的(uniform, k-uniform)。简单图是一个2均匀的例子，每条边是一块，包含两个顶点。如果每个顶点出现在$r$个块中，那么称为规则的(regular, r-regular)。
如果一个$k$均匀、$r$规则的不完全设计$(S,\mathcal{B})$，每一对恰好出现在$\lambda$块，我们成为平衡不完全块设计(balanced incomplete block design,BIBD)，参数记作$(b,v,r,k,\lambda)$。（这里更多的时候中文称作平衡不完全区组设计）。有时，我们简称这样的设计为$(b,v,r,k,\lambda)$设计，因为这里参数$r,k,\lambda$表明$(S,\mathcal{B})$是规则的、均匀的、平衡的，如果$k<v$，那么$(S,\mathcal{B})$是不完全的。

Example 17.3. Example 17.1的设计是一个平衡不完全块设计，参数是$(20,16,5,4,1)$，也就是说有20个块，16个顶点，每个顶点出现在5个块中，每个块4个顶点，每个对仅出现在1个块中。
Example 17.4. Example 17.2的设计是参数为$(7,7,3,3,1)$的平衡不完全块设计，有7个块，7个顶点，每个顶点出现在3个块中，每个块3个顶点，每个对仅出现在1个块中。
Example 17.5. 令$S=\{a,b,c\}, \mathcal{B}=\{\{a,b\},\{b,c\},\{a,c\}\}$，那么$(S,\mathcal{B})$是参数为$(3,3,2,2,1)$的平衡不完全块设计。
Example 17.6. 令$1<k<n$，那么集合$[n]$的所有$k$个元素的子集组成集合是BIBD，参数是$(<script type="math/tex; mode=display">\begin{pmatrix}n\\k\end{pmatrix}$,n, $$\begin{pmatrix}n-1\\k-1\end{pmatrix}$$ ,k, $$\begin{pmatrix}n-2\\k-2\end{pmatrix}$$ 。

有些BIBD比另一些更具有对称性。比如Example 17.2和Example 17.5中$b=v,r=k$。如果一个BIBD满足$b=v$或$r=k$（下面会证明这两者是等价的）的话，称其为对称的。所有Example 17.2和Example 17.5是对称的，而其他的例子则不是。
你可能会说有很多的BIBD。但是还不知道创建BIBD的难度，也不知道是否存在。下面两个命题会给出部分答案。

Proposition 17.7. 如果一个$(b,v,r,k,\lambda)$设计存在，那么$bk=vr$。
Proof. 令$(S,\mathcal{B})$是这样的设计，要证明的等式两边都是计算对$(w,B),w\in S,B\in\mathcal{B},w\in B$的个数。这些对就是存在一个点，且有一个块包含这个点。左边是从块来看，有$b$块，每块中$k$个点里面的任一点和自身组成对。右边是从点的角度来看，有$v$个顶点，每个存在在$r$块，组成$vr$个对。
注意，上面的证明和结论都不涉及$\lambda$，也就是说设计是平衡的和它无关。所以所有的均匀、规则的设计，都有$bk=vr$。

Proposition 17.8. 如果一个$(b,v,r,k,\lambda)$设计存在，那么$r(k-1)=\lambda(v-1)$。
Proof. 令$x\in V$是一个固定点，和上面的论证一样，对$(w,B)$计数，其中$x,w$都属于块$B$且$x\neq w$。左边先选择$r$个块，其中包含$x$，然后有$k-1$方式来选择点$w$。右边先选择$w$，有$v-1$种方式，然后$x,w$同时存在在$\lambda$个块中。
注意上面两个命题还可以说明BIBD中的$v,k,\lambda$三个参数能决定另外两个参数，所以也可以写作$(v,k,\lambda)$设计。使用这种写法，Example 17.1是$(16,4,1)$设计，Example 17.2是$(7,3,1)$设计。

New Designs From Old

有若干中方法从已有的设计中演变成新的设计。其中最简单的方法是互补性设计(complementary design)。对于两个集合$X,Y$来说，$X\setminus Y$表示某个元素在$X$但不在$Y$中。

Definition 17.9. 令$\mathcal{D}=(S,\mathcal{B})$是一个设计。$(S,\mathcal{B})$互补性设计$\mathcal{D}^c$的顶点集合是$S$，块是$\mathcal{B}$中的块的补集。也就是说$B$是$\mathcal{D}^c$的块，当且仅当$S\setminus B$是$D$的块。

Example 17.10. 如果$D$是Example 17.2的设计，那么$\mathcal{D}^c$是在顶点集$\{A,B,C,D,E,F,G\}$上包含如下块

{C, E, F, G},
{A, D, F, G}
{B, D, E, G},
{B, C, D, F},
{A, C, D, E},
{A, B, E, F},
{A, B, C, G}.

上面的例子是均匀、规则设计的，原来的设计也是均匀、规则设计。这对于任意均匀、规则设计都成立。简单说来，$(b,v,r,k)$设计，转化成了$(b,v,b-r,v-k)$。更进一步，如果一个设计是BIBD，那么互补性设计也是BIBD。练习5要求给与一个证明。简单说来，$(b,v,r,k,\lambda)$设计，转化成了$(b,v,b-r,v-k,b-2r+\lambda)$，关于最后一个参数，假定一对$(A,B)$，在$\mathcal{D}^c$出现的次数等于$\mathcal{D}$中不包含$A,B$的块的个数。

下面一个方法是采用关联矩阵(incidence matrix)。

Definition 17.11. $\mathcal{D}$设计的块是$B_1,B_2,\cdots,B_b$，顶点是$v_1,v_2,\cdots,v_v$。关联矩阵是一个定义如下的$v\times b$的矩阵 $$A_{i,j}=\begin{cases} 1&&\text{if }v_i\in B_j\\ 0&&\text{if }v_i\notin B_j \end{cases}$$

Example 17.12. 令$\mathcal{D}$是块是$[4]$两元素子集的设计，那么$\mathcal{D}$的关联矩阵是 $$\begin{aligned} &&&&&\{1,2\}\{1,3\}\{1,4\}\{2,3\}\{2,4\}\{3,4\} \end{aligned}\\ A=\begin{aligned} 1\\2\\3\\4 \end{aligned}\begin{pmatrix} 1&&1&&1&&0&&0&&0\\ 1&&0&&0&&1&&1&&0\\ 0&&1&&0&&1&&0&&1\\ 0&&0&&1&&0&&1&&1 \end{pmatrix}$$

Definition 17.13. 令$\mathcal{D}$是设计，其关联矩阵$A$。那么$\mathcal{D}$的对偶是$\mathcal{D}^d$，其关联矩阵是$A^T$。

Example 17.14. Example 17.12的对偶设计$\mathcal{D}^d$及其关联矩阵如下 $$\begin{aligned} &&&&&&\{a,b,c\}\{a,d,e\}\{b,d,f\}\{c,e,f\} \end{aligned}\\ A=\begin{aligned} a\\b\\c\\d\\e\\f \end{aligned}\begin{pmatrix} 1&&&1&&&0&&&0\\ 1&&&0&&&1&&&0\\ 1&&&0&&&0&&&1\\ 0&&&1&&&1&&&0\\ 0&&&1&&&0&&&1\\ 0&&&0&&&1&&&1 \end{pmatrix}$$ 上面例子中$\mathcal{D}^d$不是BIBD，因为它不是平衡的。这是因为$\mathcal{D}$中有的块中的对是相交的，有的不是，那么$\mathcal{D}^d$的点组成的对有的能出现在同一块，有的不能。

关联矩阵是一种在线性代数中证明设计相关命题很有用、很有影响的工具。我们下面从一些简单的观察入手。

Proposition 17.15. 令$A$是参数$(b,v,r,k,\lambda)$的设计$\mathcal{D}$的关联矩阵，那么 $$AA^T=(r-\lambda)I_v+\lambda J_v\tag{17.1}$$ 其中$I_v$是$v\times v$的单位矩阵，$J_v$是$v\times v$的全1矩阵。
Proof. 如果$i\neq j$，那么$AA^T$中第$(i,j)$项的值是$A$中第$i$行和第$j$行的点积。只有两个点在同一块的时候对应的值才同时为1，乘积是1，否则是0。有$\lambda$个这样的块。如果$i=j$，也就是同一行自己点积，那么有$r$个1。

如果非零向量$\boldsymbol{x}$和$m$满足$M\boldsymbol{x}=m\boldsymbol{x}$，那么$m$是特征矩阵，$\boldsymbol{x}$是特征向量。特征向量生成的空间是特征空间。

Corollary 17.16. 令$A$是参数$(b,v,r,k,\lambda)$的BIBD的关联矩阵，那么$AA^T$的特征值是$v-1$个$r-\lambda$和$r+\lambda(v-1)=rk$。由于没有特征值0，那么$\det{AA^T}\neq 0$。
Proof. 大致能看明白论证过程，但是细节还是不连贯。复习完线性代数回来补充？TODO

Example 17.14的例子说明BIBD的对偶不一定是BIBD。但是满足如下条件的话，那么对偶也是BIBD。设计$\mathcal{D}$的任意两个块$B_i,B_j$，其交集$B_i\cap B_j=l$是固定整数，该整数独立于块的选择。这时设计$\mathcal{D}$是链接的(linked)BIBD。如果$\mathcal{D}$是链接的，那么$\mathcal{D}^d$也会是平衡的，因为任意两个会一起出现在$l$块。

Proposition 17.17. 所有的对称BIBD是链接的。
Proof. 令$\mathcal{D}$是参数$(v,k,\lambda)$对称的设计，那么$\mathcal{D}$的关联矩阵$A$是方阵，所以$A^TA$是存在的。$A^T$是$\mathcal{D}^d$的关联矩阵。后面会证明$A^TA=AA^T$，那么$AA^T$非对角线上的项都是$\lambda$，这就说明$A$中的任意两个块有$\lambda=l$个点的交集。（这里$A^TA=AA^T$的作用是把Proposition 17.15中的点和这里需要的块联系起来，是等价的）。
很明显，$AJ=JA$，其中$J$是$v\times v$的全1矩阵。由Corollary 17.16可知，$A^{-1}$是存在的，否则$\det{AA^T}=0$。那么将$(17.1)$左边乘$A^{-1}$，右边乘$A$ $$\begin{aligned} A^TA&=A^{-1}((r-\lambda)I)A+\lambda A^{-1}JA\\ &=(r-\lambda)I+\lambda J\\ &=AA^T \end{aligned}$$

对称BIBD是链接的，那么对偶设计也是BIBD。下面的定理告诉我们它的反面也成立。也就是BIBD的对偶是BIBD的话，那么BIBD是对称的。

Theorem 17.18 (Fisher's inequality). 如果$\mathcal{D}$是有$v$点$b$块的BIBD，那么$v\leq b$。
Proof. $\mathcal{D}$的关联矩阵$A$，由Proposition 17.15得知$\det{AA^T}\neq 0$，$c\times v$的秩是$v$。另外两个矩阵的乘积的秩不会大于任意一个，所以 $$v=\text{rank}(AA^T)\leq \text{rand}(A)$$ 任意矩阵的秩不能大于独立行的数量，所以 $$\text{rank}(A)\leq b$$

下面的结果提供了另外一些关于对称BIBD存在的必要条件。
Theorem 17.19. 如果$\mathcal{D}$是参数为$(v,r,\lambda)$的对称BIBD，并且$v$是偶数，那么$r-\lambda$是完全平方数。
Proof. Corollary 17.16给出了特征向量，那么 $$\det{AA^T}=(r+(v-1)\lambda)\cdot(r-\lambda)^{v-1}$$ 左边是$\det{A}^2$，是平方数，$(r+(v-1)\lambda)=r+r(k-1)=rk=r^2$，也是平方数，那么$(r-\lambda)^{v-1}$是平方数，$v$是偶数，那么$v-1$是奇数，所以$r-\lambda$是完全平方数。

有一个和上面定理类似$v$是奇数的情况，证明比较难，所以下面只给出结论。
Theorem 17.20. 如果$\mathcal{D}$是参数为$(v,r,\lambda)$的对称BIBD，并且$v$是奇数，那么存在不全等于零的整数$x,y,z$，有 $$x^2=(k-\lambda)y^2+(-1)^{(v-1)/2}\cdot\lambdaz^2$$