Bóna · 枚举与解析组合学导论 · 第 8 章 对称结构

8.1　设计Designs

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

在第 6 章中，我们曾从极值组合学（extremal combinatorics）的角度考察集合族。遵循该领域的传统，我们把这些集合族称作超图（hypergraph），以此暗示它们是图（graph）的推广。在本章中，我们将再次考察集合族，但这次我们感兴趣的是它们的对称性。遵循这条研究路线的传统，本章中我们把所考察的集合族称作设计（design）。

也就是说，一个区组设计（block design）\(B\) 由一个有限的元素集合 \(V\)（其元素称为该设计的顶点，vertices）以及 \(V\) 的一族非空子集 \(E\)（这些子集称为区组，blocks）组成。我们将沿用上一章术语中的一些词。特别地，如果一个区组设计 \(B\) 的每个区组都含有相同数目 \(k\) 的顶点，我们就称它是一致的（uniform）或 \(k\) 一致的（\(k\)-uniform）。

本节目标给“设计”这种带对称性的集合族建立一整套语言：把一致（每个区组等大）、正则（每个顶点出现次数相同）、平衡（每对顶点共同出现次数相同）这三条对称性说清楚；导出五个参数 \(v,b,r,k,\lambda\) 之间必然成立的等式（命题 8.2、8.3）；引入关联矩阵把“对偶”讲精确（命题 8.7）；最后证明参数间一条深刻的不等式——Fisher 不等式 \(v\le b\)（定理 8.12）。

在现实中，我们往往需要比区组设计更强的对称性。例如，假设一位足球教练想试验他的 \(v\) 名新进攻球员在各种 \(k\) 前锋阵型中的表现，他可能希望让每名球员获得相同的上场时间。这种情形下，他需要一个正则的（regular）、即 \(r\) 正则的（\(r\)-regular）区组设计，也就是每个顶点都出现在相同数目 \(r\) 个区组中的设计。不言而喻，这里顶点就是球员，区组就是阵型。

这位教练对公平性的要求可能更高，他也许想确保任意一对前锋在相同数目 \(\lambda\) 次试验中搭档出场。若果真如此，我们就说该教练所用的设计是平衡的（balanced）。

如果一个设计既是平衡的、又是一致的、还是正则的，那么它就被称为一个区组设计。最后，如果 \(k平衡不完全区组设计（balanced incomplete block design），简记为 BIBD。

三条对称性（直观版）把一份设计想成一张“出勤表”：行是顶点（球员），列是区组（阵型），某球员入选某阵型就在格子里打勾。
  1. 一致：每一列的勾数都相同，等于 \(k\)（每个阵型人数一样）。
  2. 正则：每一行的勾数都相同，等于 \(r\)（每名球员上场次数一样）。
  3. 平衡：任取两名球员，他们共同出现的列数都相同，等于 \(\lambda\)（任意一对搭档次数一样）。
三条都满足且 \(k

当然，只要教练把全部 \(\binom{v}{k}\) 种可能阵型都试一遍，这一切肯定都能实现，但那也许直到赛季结束都试不完。因此，寻找区组数目更少、却仍满足上述全部条件的设计，是一件有意思的事。

下文中，我们将考察具有上述一条或多条对称性质的设计。在本节余下部分，我们约定如下记号。在一个设计 \(F\) 中，

  1. 顶点的数目记作 \(v\)；
  2. 区组的数目记作 \(b\)；
  3. 若 \(F\) 是一致的，则任意（等价地，每一个）区组所含顶点的数目记作 \(k\)；
  4. 若 \(F\) 是正则的，则任意（等价地，每一个）顶点所出现的区组数目记作 \(r\)；
  5. 若 \(F\) 是平衡的，则任意（等价地，每一对）顶点共同出现的区组数目记作 \(\lambda\)。

我们常常这样提及一个 BIBD 的参数：称它为一个 \((b,v,r,k,\lambda)\)-BIBD。

在本章余下部分，我们假定所讨论的设计具有多于一个区组；否则，\([n]\) 上的一个设计可以只由一个区组——即 \([n]\) 本身——构成。事实证明，这个设计会成为许多定理的唯一反例。回忆上一章：我们不允许设计含有重复的区组。

例 8.1 以 \([n]\) 的全体 \(k\) 元子集为区组的设计 \(F\)，是正则的、一致的、且平衡的。
解：每个顶点出现在 \(r=\binom{n-1}{k-1}\) 个区组中，故 \(F\) 正则；每个区组含 \(k\) 个顶点，故 \(F\) 一致；最后，任意两个顶点共同出现在 \(\lambda=\binom{n-2}{k-2}\) 个区组中，故 \(F\) 平衡。♦
把例 8.1 算成数字（\(n=4,\ k=2\)） 取顶点集 \([4]=\{1,2,3,4\}\)，区组为全部 \(2\) 元子集，共 \(b=\binom{4}{2}=6\) 个：\(\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}\)。
  1. 正则：顶点 \(1\) 出现在 \(\{1,2\},\{1,3\},\{1,4\}\) 中，共 \(3\) 个；其余顶点同理。验证 \(r=\binom{n-1}{k-1}=\binom{3}{1}=3\)。
  2. 一致：每个区组都恰有 \(k=2\) 个顶点。
  3. 平衡：任取一对顶点，例如 \(\{2,3\}\)，它们只在区组 \(\{2,3\}\) 里共同出现，共 \(1\) 个。验证 \(\lambda=\binom{n-2}{k-2}=\binom{2}{0}=1\)。

这么多对称性会严重限制一个设计的结构，这并不奇怪。接下来的两个命题，先从参数本身这五个数所受的限制开始探讨。

命题 8.2设 \(F\) 是一个一致正则设计，则 \[\tag{8.0a}bk=vr.\]
证明. 我们来数所有满足“\(a\) 是区组 \(B\) 的一个顶点”的有序对 \((a,B)\)。按区组数：有 \(b\) 个区组，每个区组含 \(k\) 个顶点，故这种对共有 \(bk\) 个。按顶点数：有 \(v\) 个顶点，每个顶点含于 \(r\) 个区组，故这种对共有 \(vr\) 个。两种数法数的是同一批对，所以 \(bk=vr\)。♦
这就是“双重计数”同一堆东西换两种角度去数，结果必相等——这是组合学中最有力的一招。这里那“一堆东西”就是出勤表里所有的勾。
出勤表：行=顶点，列=区组 ✓✓✓✓✓✓✓ 按列数：\(b\) 列 × 每列 \(k\) 勾 = \(bk\) 按行数：\(v\) 行 × 每行 \(r\) 勾 = \(vr\) 同一批勾 ⟹ \(bk=vr\)
把“勾”这一对 \((a,B)\) 按列（区组）数得 \(bk\)，按行（顶点）数得 \(vr\)，两者必相等。

我们可以对例 8.1 中的设计 \(F\) 验证命题 8.2。在那个例子里，\(b=\binom{n}{k}\)，\(v=n\)，其余参数已在该例证明中算出。于是我们得到等式 \[\binom{n}{k}\cdot k=n\cdot\binom{n-1}{k-1},\] 这确实是正确的。

命题 8.3设 \(F\) 是一个平衡一致正则设计，则 \[\tag{8.0b}\lambda(v-1)=r(k-1).\]
证明. 固定 \(F\) 的任意一个顶点 \(a\)。我们来数所有形如 \((B,c)\) 的对，其中 \(a\) 与 \(c\) 是区组 \(B\) 的两个顶点。按顶点 \(c\) 数：\(c\) 有 \(v-1\) 种选择（除 \(a\) 外的任一顶点），对每一种选择，含 \(a\) 与 \(c\) 的区组有 \(\lambda\) 个，这解释了左端 \(\lambda(v-1)\)。按区组 \(B\) 数：含 \(a\) 的区组有 \(r\) 个，每个这样的区组还含 \(k-1\) 个其他顶点，它们都能充当 \(c\)，这解释了右端 \(r(k-1)\)。两种数法数的是同一批对，故等式成立。♦
用 \(n=4,k=2\) 验证命题 8.3 此设计 \(v=4,\ k=2,\ r=3,\ \lambda=1\)。固定顶点 \(a=1\)，数对 \((B,c)\)：
  1. 左端：\(c\) 可取 \(2,3,4\) 共 \(v-1=3\) 个；每个 \(c\) 与 \(1\) 恰在 \(\lambda=1\) 个区组中搭档。合计 \(\lambda(v-1)=1\times3=3\)。
  2. 右端：含 \(1\) 的区组有 \(\{1,2\},\{1,3\},\{1,4\}\) 共 \(r=3\) 个；每个区组里除 \(1\) 外还有 \(k-1=1\) 个顶点可当 \(c\)。合计 \(r(k-1)=3\times1=3\)。
  3. 两端都是 \(3\)，等式 \(\lambda(v-1)=r(k-1)\) 成立。

对例 8.1 中的 \(F\) 再次验证此命题，我们得到等式 \[\binom{n-2}{k-2}(n-1)=\binom{n-1}{k-1}(k-1).\]

务必注意：必要而不充分命题 8.2 与 8.3 只给出了某类设计存在的必要条件，而非充分条件。

必须指出，命题 8.2 与命题 8.3 只确立了某些设计存在的必要条件，而非充分条件。例如，不存在参数为 \(v=16,\ b=8,\ k=6,\ r=3,\ \lambda=1\) 的平衡一致正则设计——即使这些数满足上述两个命题的等式。定理 8.12 将说明为何没有这样的设计。

验证“满足等式却不存在” 取 \(v=16,b=8,k=6,r=3,\lambda=1\)：
  1. 命题 8.2：\(bk=8\times6=48\)，\(vr=16\times3=48\)，相等 ✓。
  2. 命题 8.3：\(\lambda(v-1)=1\times15=15\)，\(r(k-1)=3\times5=15\)，相等 ✓。
  3. 但 Fisher 不等式（定理 8.12）要求 \(v\le b\)，这里 \(16\le 8\) 不成立，故此设计不存在。两条等式过得去，并不保证设计真能造出来。

读到这里，读者也许会期待有一条定理，能给出参数为 \(v,b,r,k,\lambda\) 的设计存在的充分必要条件。遗憾的是，目前并不知道这样的定理。事实上，存在相当多的参数五元组 \((v,b,r,k,\lambda)\)，人们至今不知道以它们为参数的设计（简称为 \((v,b,r,k,\lambda)\)-设计）是否存在。（参数 \(r,k,\lambda\) 出现这一事实本身，就意味着我们考察的是平衡一致正则设计。）我们将在下一节稍微详细地讨论这些困难问题。在此之前，我们向读者提出挑战：判断一个 \((7,7,3,3,1)\)-设计是否存在。用我们最初那个例子的语言来说，就是在问：一位拥有七名前锋的足球教练，能否试验出七套进攻阵型，使每套阵型恰由三名前锋组成、每名前锋恰获三次出场机会、且任意一对球员恰好搭档出场一次？

\((7,7,3,3,1)\)-设计真的存在：Fano 平面 答案是“能”。取 \(7\) 名球员 \(\{1,\dots,7\}\)，七套阵型为 \[\{1,2,3\},\{1,4,5\},\{1,6,7\},\{2,4,6\},\{2,5,7\},\{3,4,7\},\{3,5,6\}.\]
  1. 每套阵型 \(k=3\) 人 ✓；共 \(b=7\) 套、\(v=7\) 人 ✓。
  2. 每名球员恰好出现在 \(r=3\) 套中（如 \(1\) 在前三套里）✓。
  3. 任意一对，如 \(\{4,5\}\)，恰在 \(\{1,4,5\}\) 这一套里搭档，\(\lambda=1\) ✓。
这就是著名的 Fano 平面（Fano plane），它是最小的非平凡 BIBD。
3675412
Fano 平面：\(7\) 个点、\(7\) 条“线”（三条边、三条中线、中间那个圆），每条线恰 \(3\) 个点，每点恰在 \(3\) 条线上，每两点恰被 \(1\) 条线相连，正是上面列出的 \((7,7,3,3,1)\)-设计。这里三条边为 \(\{3,5,6\},\{3,4,7\},\{1,6,7\}\)，三条中线（交于中心点 \(2\)）为 \(\{1,2,3\},\{2,4,6\},\{2,5,7\}\)，内圆为 \(\{1,4,5\}\)。

到目前为止，我们考察了设计的三种不同性质，即平衡、一致与正则。这些都是很强的性质，能严重限制一个设计的结构。习题 1 表明：若一个设计是平衡且一致的，则它也必是正则的。学到这一事实之后，读者也许会猜测：一个平衡且正则的设计必然是一致的（因为“正则”之于顶点，与“一致”之于区组，意思大致相同）。然而，下面的例子表明，这个猜测是错误的。

例 8.4 设 \(F\) 是 \([n]\) 上的设计，其区组为 \([n]\) 的全部 \(2\) 元子集与 \(3\) 元子集。那么 \(F\) 是正则的（\(r=n-1+\binom{n-1}{2}=\binom{n}{2}\)），也是平衡的（\(\lambda=1+(n-2)=n-1\)），但不是一致的。
用 \(n=4\) 把例 8.4 数清楚 区组 = 全部 \(2\) 元子集（\(6\) 个）+ 全部 \(3\) 元子集（\(\binom{4}{3}=4\) 个）。
  1. 正则：顶点 \(1\) 在 \(2\) 元子集中出现 \(n-1=3\) 次，在 \(3\) 元子集中出现 \(\binom{n-1}{2}=\binom{3}{2}=3\) 次，共 \(r=6=\binom{4}{2}\) ✓。
  2. 平衡：一对 \(\{1,2\}\) 在 \(2\) 元子集里搭档 \(1\) 次，在 \(3\) 元子集里搭档 \(n-2=2\) 次（即 \(\{1,2,3\},\{1,2,4\}\)），共 \(\lambda=3=n-1\) ✓。
  3. 不一致：区组大小有 \(2\) 也有 \(3\)，不全相等。所以“平衡 + 正则”推不出“一致”。

读到这里，读者也许会想：一致性与正则性看上去是彼此的对偶，是什么造成了它们之间这种微妙的差别呢？答案在于平衡性质的本性。平衡性质保证任意两个顶点共同出现在相同数目的区组中。然而，我们尚未定义这一性质的对偶版本，也就是说，我们还没有讨论过这样的设计：其中任意一对区组的交集都有相同的大小。下面的定义填补了这一空白。

定义 8.5若一个设计的任意两个区组都恰好交于相同数目 \(\mu\) 个顶点，则称该设计是连结的（linked）。
对偶一览（行 ↔ 列）
  1. 一致：每个区组等大（列视角）　↔　正则：每个顶点出现次数相同（行视角）。
  2. 平衡：每对顶点共现次数 \(\lambda\) 相同　↔　连结：每对区组相交 \(\mu\) 个顶点相同。
例 8.6 当 \(k=1\) 时（此时 \(\mu=0\)）以及当 \(k=n-1\) 时（此时 \(\mu=n-2\)），例 8.1 中的设计 \(F\) 是连结的。对 \(k\) 的其他取值，上述设计不是连结的。
用 \(n=4\) 看例 8.6
  1. \(k=1\)：区组为 \(\{1\},\{2\},\{3\},\{4\}\)，任两个区组无公共顶点，故 \(\mu=0\)，连结。
  2. \(k=n-1=3\)：区组为 \(\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}\)，任两个区组恰交 \(\mu=n-2=2\) 个顶点（如 \(\{1,2,3\}\cap\{1,2,4\}=\{1,2\}\)），连结。
  3. \(k=2\)：区组 \(\{1,2\}\) 与 \(\{1,3\}\) 交 \(1\) 个顶点，而 \(\{1,2\}\) 与 \(\{3,4\}\) 交 \(0\) 个，交集大小不恒定，故不连结。

现在我们可以陈述与习题 1 相对应的命题。

命题 8.7设 \(F\) 是一个正则且连结的设计，则 \(F\) 是一致的。

但愿读者此刻在想：也许我们不必为这个命题另写一个独立的证明；也许我们能或多或少毫不费力地从习题 1 的结果把它推导出来。如果是这样，我们有好消息要告诉读者。确实存在一种通用技巧，它在把命题翻译成其对偶命题时非常有用。（我们终于能够精确地解释“对偶”这个词的含义了。）关键的定义如下。

定义 8.8设 \(F\) 是顶点为 \(a_1,a_2,\dots,a_v\)、区组为 \(e_1,e_2,\dots,e_b\) 的设计。则 \(F\) 的关联矩阵（incidence matrix）是 \(v\times b\) 矩阵 \(M=M_F\)，其中 \[M_{i,j}=\begin{cases}1,&\text{若 }a_i\in e_j,\\[2pt]0,&\text{若 }a_i\notin e_j.\end{cases}\] 换言之，\(M_F\) 的行对应 \(F\) 的顶点，\(M_F\) 的列对应 \(F\) 的区组。一行与一列的交叉处为 \(1\)，当且仅当该行对应的顶点含于该列对应的区组。
例 8.9 若 \(F\) 的顶点集为 \([4]\)，区组为 \[e_1=\{1,2\},\ e_2=\{1,3\},\ e_3=\{2,4\},\ e_4=\{2,3,4\},\ e_5=\{1,4\},\] 则 \[M_F=\begin{pmatrix}1&1&0&0&1\\1&0&1&1&0\\0&1&0&1&0\\0&0&1&1&1\end{pmatrix}.\]
行 = 顶点 1..4　列 = 区组 e₁..e₅ e₁e₂e₃e₄e₅ 1234 11001 10110 01010 00111 某格为 1 ⟺ 该顶点属于该区组
例如第 \(4\) 列（区组 \(e_4=\{2,3,4\}\)）在第 \(2,3,4\) 行为 \(1\)，正好对应 \(e_4\) 的三个顶点。

关联矩阵的一大好处在于：现在我们可以轻松地定义一个设计的对偶。

定义 8.10设计 \(F\) 的对偶 \(F^d\) 是这样一个设计：它的关联矩阵是 \(M_F\) 的转置。

如果我们在第 5 章之前就陈述这个定义，读者也许会问：你说 \(F\) 的对偶是关联矩阵为 \(M_F^T\) 的那个设计，是什么意思？万一有好几个设计具有相同的关联矩阵怎么办？然而到了现在，读者很容易就能打消这个疑虑：注意到具有相同关联矩阵的所有设计都是同构的。

我们尚未正式定义设计的同构，但其定义与图同构非常相似。也就是说，设 \(F\) 与 \(G\) 是两个设计。若存在一个从 \(F\) 的顶点集到 \(G\) 的顶点集上的双射 \(f\)，它把 \(F\) 的区组映成 \(G\) 的区组，则称 \(f\) 是一个同构，并称 \(F\) 与 \(G\) 是同构的。

例 8.11 为构造例 8.9 中设计 \(F\) 的对偶 \(F^d\)，我们先取 \(M_F\) 的转置，得到矩阵 \[M_F^T=\begin{pmatrix}1&1&0&0\\1&0&1&0\\0&1&0&1\\0&1&1&1\\1&0&1&1\end{pmatrix}.\] 然后读这个矩阵的第 \(j\) 列，看哪些顶点含于 \(e_j\)。我们得到 \(e_1=\{1,2,5\}\)，\(e_2=\{1,3,4\}\)，\(e_3=\{2,4,5\}\)，\(e_4=\{3,4,5\}\)。
M_F（4×5） 行=4 顶点　列=5 区组 → 转置 Mᵀ=M_{F^d}（5×4） 行=5 顶点　列=4 区组
取对偶 = 转置关联矩阵：原来的“区组”变成新设计的“顶点”，原来的“顶点”变成新设计的“区组”。

把前面讨论过的各种设计性质翻译成关联矩阵的语言是直截了当的。例如：\(F\) 正则当且仅当 \(M_F\) 的所有行都含有相同数目 \(r\) 个 \(1\)；\(F\) 一致当且仅当 \(M_F\) 的所有列都含有相同数目 \(k\) 个 \(1\)；如此等等。因此，\(F\) 正则当且仅当 \(F^d\) 一致，而\(F\) 平衡当且仅当 \(F^d\) 连结，等等。于是，证明命题 8.7 现在就是小菜一碟了。

证明.（命题 8.7） 若 \(F\) 正则且连结，则 \(F^d\) 一致且平衡，于是由习题 1，\(F^d\) 正则。因此 \(F^d\) 的对偶——也就是 \(F\)——是一致的。♦
对偶技巧的威力本要为命题 8.7 重新证一遍，现在只需：把 \(F\) 转成 \(F^d\)，行列互换后“正则↔一致、连结↔平衡”，再调用已证的习题 1，结论自动得到。一句翻译省下一整篇证明。

关联矩阵的概念在证明比命题 8.7 困难得多的结果时也很有用，我们很快就会看到这一点。

我们已经证明了两个结果（命题 8.2 与 8.3），它们陈述的是涉及设计参数之乘积的等式，补充习题 1 还提供了又一个这样的结果。然而，不等式又如何呢？某些参数是否总是大于另一些参数？当然，有一些平凡的不等式：在每个一致设计中 \(k\le v\)，在每个正则设计中 \(r\le b\)。若 \(F\) 是平衡的，则 \(\lambda\le r\)，因为含有某顶点 \(x\) 的区组总数，至少不小于 \(x\) 与另一顶点 \(y\) 共同出现的区组数。事实上，\(\lambda=r\) 仅当所有顶点都出现在所有区组中时才可能，而那种情形实在没什么意思。

平凡不等式小结
  1. 一致设计：\(k\le v\)（每个区组装不下比顶点总数还多的元素）。
  2. 正则设计：\(r\le b\)（一个顶点出现的区组数不超过区组总数）。
  3. 平衡设计：\(\lambda\le r\)；且 \(\lambda=r\) 仅在“所有顶点都在所有区组里”的乏味情形发生。

下面是设计参数之间一条深刻得多的不等式。

定理 8.12（Fisher 不等式）设 \(F\) 是一个至少有两个区组的平衡一致设计，则 \(v\le b\)。
这条不等式说什么区组数 \(b\) 至少和顶点数 \(v\) 一样多。回到足球例子：要想做到“任意两名球员都恰好搭档 \(\lambda\) 次”，所需的阵型数不会少于球员数。前面 \(v=16,b=8\) 的参数正因违反 \(v\le b\) 而不可能存在。
证明.

设 \(M\) 是 \(F\) 的关联矩阵，并反设 \(b

另一方面，习题 3 的解表明 \[MM^T=\begin{pmatrix}r&\lambda&\lambda&\cdots&\lambda\\\lambda&r&\lambda&\cdots&\lambda\\\lambda&\lambda&r&\cdots&\lambda\\\cdots&\cdots&\cdots&\cdots&\cdots\\\lambda&\lambda&\cdots&\cdots&r\end{pmatrix}.\] 在读者发问 \(r\) 是什么之前，我们先指出：习题 1 表明平衡一致设计是正则的，所以 \(r\) 就是每个顶点所含于的区组数目。

现在我们用初等行、列变换，把这个矩阵化为三角形，来计算 \(\det(MM^T)\)。首先，把第一列从其余各列中减去。这不改变矩阵的行列式，得到 \[\det(MM^T)=\det\begin{pmatrix}r&\lambda-r&\lambda-r&\cdots&\lambda-r\\\lambda&r-\lambda&0&\cdots&0\\\lambda&0&r-\lambda&\cdots&0\\\cdots&\cdots&\cdots&\cdots&\cdots\\\lambda&0&0&\cdots&r-\lambda\end{pmatrix}.\] 换言之，只要能算出上面这个行列式，我们就知道了 \(\det MM^T\)。这令人鼓舞，因为上面的矩阵几乎是下三角的；事实上，它在主对角线之上唯一的非零元都在第一行。

我们注意到，除第一列之外，每一列之和都为零（因为该列的元素是 \(\lambda-r\) 与 \(r-\lambda\) 各一个、其余为零，二者相加为 \(0\)）。因此，如果把每一行都加到第一行上，第一行的每个元素就变成相应那一列所有元素之和。第一行第一个元素变为 \(r+\lambda(v-1)\)（第一列之和），其余元素则全部变为 \(0\)。这一行、列运算不改变行列式，于是矩阵变为下三角形：第一行为 \(\bigl(r+\lambda(v-1),\,0,\,\cdots,\,0\bigr)\)，主对角线上其余的 \(v-1\) 个元素都是 \(r-\lambda\)。从而 \[\tag{8.2}\det(MM^T)=\bigl(r+\lambda(v-1)\bigr)\,(r-\lambda)^{\,v-1}.\] 由于设计平衡且有至少两个区组，故 \(\lambda0\)，于是 \((r-\lambda)^{v-1}>0\)；又 \(r+\lambda(v-1)>0\)。所以 \(\det(MM^T)>0\)。这与 (8.1) 给出的 \(\det(MM^T)=0\) 相矛盾。矛盾源于反设 \(b♦

把 Fisher 证明走一遍数字（\(v=4,k=2\) 的设计） 该设计 \(r=3,\ \lambda=1,\ v=4\)。
  1. \(MM^T\) 是 \(4\times4\) 矩阵，对角线为 \(r=3\)，其余为 \(\lambda=1\)。
  2. 代入 (8.2)：\(\det(MM^T)=\bigl(3+1\times3\bigr)(3-1)^{3}=6\times8=48>0\)。
  3. 因为 \(\det(MM^T)>0\)，关联矩阵 \(M\) 的列数（=区组数 \(b\)）不可能少于行数（=顶点数 \(v\)）。这里 \(b=6\ge v=4\)，与 \(v\le b\) 一致。
关键链条：列数太少 ⟹ \(\det(MM^T)=0\)；而公式 (8.2) 又说它 \(>0\)。矛盾，所以列数不能太少。
反设 b < v 补零列 ⟹ det=0 + 公式(8.2) (r+λ(v-1))(r-λ)^{v-1}>0 ⟹ 矛盾 故 v≤b
Fisher 不等式的证明骨架：同一个数 \(\det(MM^T)\) 被算出两个互相矛盾的结果（\(=0\) 与 \(>0\)），逼出 \(v\le b\)。
即时自测
  1. 对例 8.1 中以 \([5]\) 的全部 \(3\) 元子集为区组的设计，算出 \(v,b,k,r,\lambda\)，并验证 \(bk=vr\) 与 \(\lambda(v-1)=r(k-1)\)。
  2. 写出例 8.9 中设计的对偶 \(F^d\) 的关联矩阵的尺寸，并指出 \(F^d\) 有几个顶点、几个区组。
  3. 某参数组满足 \(bk=vr\) 与 \(\lambda(v-1)=r(k-1)\)，但 \(v>b\)。这样的平衡一致设计能否存在？为什么？

返回 全书目录