专栏文章

正交拉丁方的构造

MMatrixGroup时序绚乱
算法·理论参与者 9已保存评论 8

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
8 条
当前快照
1 份
快照标识符
@minj1z08
此快照首次捕获于
2025/12/02 03:13
3 个月前
此快照最后确认于
2025/12/02 03:13
3 个月前
查看原文

前言

  • 本文只介绍对关键结论有用的定义和定理，中间另外一些有用和/或有趣的定理可以去原书阅读。
  • 别问构造怎么来的。
  • 按照自己的理解稍微修改了一些细节，如果改错了记得跟笔者讲一声。
  • 假定读者熟知有限域的构造。
  • AiA^i 表示上标，不是矩阵的幂。
  • 本文同步发表于知乎专栏。

引入

定义. 对于一个 nn 元集 SS，一个 nn 阶拉丁方（Latin square）是一个 nn 阶方阵，满足每行每列恰有 SS 中的每个元素各一个。
（注：SS 本身是什么并不重要。在语境清晰的情况下，可以省去 SS。否则，不妨设 S={1,2,⋯ ,n}S=\{1,2,\cdots,n\}。）
例. 如下是一个 6×66\times 6 的拉丁方：
[361425153264416532625341542613234156]\begin{bmatrix} 3&6&1&4&2&5\\ 1&5&3&2&6&4\\ 4&1&6&5&3&2\\ 6&2&5&3&4&1\\ 5&4&2&6&1&3\\ 2&3&4&1&5&6 \end{bmatrix}
定义. 一对 nn 阶拉丁方 P,QP,Q 是正交的（orthogonal），当且仅当对于每对 i,j∈{1,2,⋯ ,n}i,j\in \{1,2,\cdots,n\}，二元组 (Pi,j,Qi,j)(P_{i,j},Q_{i,j}) 两两不同。
例. 如下是一对 10×1010\times 10 的正交拉丁方：
[0417298365815273940698263745105983047621769841503267098521433071986254123456078923456018974560123978][0786935412617809452350278196349613782045390247815684913572607859246301456012378912345609782345601897]\begin{bmatrix} 0&4&1&7&2&9&8&3&6&5\\ 8&1&5&2&7&3&9&4&0&6\\ 9&8&2&6&3&7&4&5&1&0\\ 5&9&8&3&0&4&7&6&2&1\\ 7&6&9&8&4&1&5&0&3&2\\ 6&7&0&9&8&5&2&1&4&3\\ 3&0&7&1&9&8&6&2&5&4\\ 1&2&3&4&5&6&0&7&8&9\\ 2&3&4&5&6&0&1&8&9&7\\ 4&5&6&0&1&2&3&9&7&8 \end{bmatrix} \begin{bmatrix} 0&7&8&6&9&3&5&4&1&2\\ 6&1&7&8&0&9&4&5&2&3\\ 5&0&2&7&8&1&9&6&3&4\\ 9&6&1&3&7&8&2&0&4&5\\ 3&9&0&2&4&7&8&1&5&6\\ 8&4&9&1&3&5&7&2&6&0\\ 7&8&5&9&2&4&6&3&0&1\\ 4&5&6&0&1&2&3&7&8&9\\ 1&2&3&4&5&6&0&9&7&8\\ 2&3&4&5&6&0&1&8&9&7 \end{bmatrix}
定义. 一些 nn 阶拉丁方是（相互）正交的（mutually orthogonal），当且仅当其中每两个拉丁方都是正交的。
例. 如下是一组 4×44\times 4 的相互正交拉丁方：
[01xy10yxxy01yx10][01xyxy01yx1010yx][01xyyx1010yxxy01]\begin{bmatrix} 0&1&x&y\\ 1&0&y&x\\ x&y&0&1\\ y&x&1&0 \end{bmatrix} \begin{bmatrix} 0&1&x&y\\ x&y&0&1\\ y&x&1&0\\ 1&0&y&x \end{bmatrix} \begin{bmatrix} 0&1&x&y\\ y&x&1&0\\ 1&0&y&x\\ x&y&0&1 \end{bmatrix}
定义. 对于正整数 nn，N(n)N(n) 表示最多的（相互）正交拉丁方组的拉丁方个数。特别的，N(1)=+∞N(1)=+\infty。
例. N(2)=1,N(3)=2N(2)=1,N(3)=2。

前置：区组设计

定义. 对于一个 vv 元集 SS，一个集合 K⊆{1,2,⋯ ,v−1}K\subseteq\{1,2,\cdots,v-1\}，一个正整数 λ\lambda，定义一个 (v,K,λ)(v,K,\lambda)-两两平衡设计（pairwise balanced design, PBD）为 SS 的一个子集族（其中每个 SS 的子集被称为一个「区组（block）」），满足以下两点：
  • 每个区组的大小都是 KK 中的元素。
  • 对于每对不同的元素 x,y∈S(x≠y)x,y\in S(x\neq y)，恰有 λ\lambda 个区组同时包含 xx 和 yy。
特别的，若 K={k}K=\{k\} 是单元集，则称它为一个 (v,k,λ)(v,k,\lambda)-平衡不完全区组设计（balanced incomplete block design, BIBD）。
特别的，对于正整数 n≥2n\ge 2，一个 (n2+n+1,n+1,1)(n^2+n+1,n+1,1)-BIBD 被称为一个 nn 阶有限射影平面（finite projective plane）。
特别的，对于正整数 n≥2n\ge 2，一个 (n2,n,1)(n^2,n,1)-BIBD 被称为一个 nn 阶有限仿射平面（finite affine plane）。
（注：SS 本身是什么并不重要。在语境清晰的情况下，可以省去 SS。否则，不妨设 S={1,2,⋯ ,v}S=\{1,2,\cdots,v\}。）
例. 一个 (v,3,1)(v,3,1)-BIBD 是熟知的 Steiner 三元系（Steiner triple system）。
例. {0,7,10,11,23}\{0,7,10,11,23\} 和 {0,5,14,20,22}\{0,5,14,20,22\} 在模 4141 意义下每个元素同加一个数得到的 8282 个集合，组成了一个 (41,5,1)(41,5,1)-BIBD。
定理 1. 对于素数幂 qq，存在 qq 阶有限射影平面和 qq 阶有限仿射平面。
证明. 所有 {(a,b,c)∣a,b,c∈Fq,(a,b,c)≠(0,0,0)}\{(a,b,c)|a,b,c\in \mathbb F_q,(a,b,c)\neq (0,0,0)\} 在 (a,b,c)∼(at,bt,ct)(t∈Fq,t≠0)(a,b,c)\sim (at,bt,ct)(t\in\mathbb F_q,t\neq 0) 的等价关系下构成等价类。对于所有等价类，任取代表元 (a,b,c)(a,b,c)，则所有 (x,y,z)(x,y,z) 满足 ax+by+cz=0ax+by+cz=0 所在的等价类为一个区组，则容易验证这就是一个 qq 阶有限射影平面。
强制要求 c≠0c\neq 0（区组中去掉 (a,b,c)∼(0,0,1)(a,b,c)\sim (0,0,1) 即 z=0z=0 的等价类）即可得到 nn 阶有限仿射平面。□\square
定义. 一个 PBD 是可分解的（resolvable）当且仅当存在一个区组的划分，使得划分的每一类中的区组构成了 SS 的一个划分。这个划分的每一类被称为一个分解类（resolution class）或平行类（parallel class）。
例. {1,2},{1,3},{1,4},{2,3},{2,4},{3,4}\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\} 是一个可分解的 (4,2,1)(4,2,1)-BIBD，它可以被分解为 {{1,2},{3,4}},{{1,3},{2,4}},{{1,4},{2,3}}\{\{1,2\},\{3,4\}\},\{\{1,3\},\{2,4\}\},\{\{1,4\},\{2,3\}\}。

初步的探索

先来研究一些关于 N(n)N(n) 的简单结论！
定理 2. 对于正整数 n≥2n\ge 2，N(n)≤n−1N(n)\le n-1。
证明. 设 N(n)=rN(n)=r。因为标号不重要，无妨设每个拉丁方都满足第一行是 1,2,⋯ ,n1,2,\cdots,n。则第二行第一列的元素不能是 11，也必须两两不同（每对相同的数都在第一行出现过了），因此 r≤n−1r\le n-1。□\square
定理 3. 对于素数幂 q≥2q\ge 2，N(q)=q−1N(q)=q-1。
证明. 根据定理 2，只需构造 q−1q-1 个相互正交的拉丁方即可。对于 Fq={x1,x2,⋯ ,xq}\mathbb F_q=\{x_1,x_2,\cdots,x_q\} 中的每个非零元素 a≠0a\neq 0，构造方阵 MaM^a 满足 Mi,ja=xi+axjM^a_{i,j}=x_i+ax_j。容易验证这些是相互正交的拉丁方。□\square
定理 4. 对于正整数 n,mn,m，N(nm)≥min⁡(N(n),N(m))N(nm)\ge \min(N(n),N(m))。
证明. 无妨设 n,m≥2n,m\ge 2。任取 q=min⁡(N(n),N(m))q=\min(N(n),N(m)) 个 nn 阶正交拉丁方 P1,P2,⋯ ,PqP^1,P^2,\cdots,P^q 和 mm 阶正交拉丁方 Q1,Q2,⋯ ,QqQ^1,Q^2,\cdots,Q^q（假定元素为 1∼m1\sim m 的正整数）。构造分块矩阵
Ri=[Ci,Q1,1iCi,Q1,2i⋯Ci,Q1,miCi,Q2,1iCi,Q2,2i⋯Ci,Q1,mi⋮⋮⋱⋮Ci,Qm,1iCi,Qm,2i⋯Ci,Qm,mi]R_i=\begin{bmatrix} C^{i,Q^i_{1,1}}&C^{i,Q^i_{1,2}}&\cdots&C^{i,Q^i_{1,m}}\\ C^{i,Q^i_{2,1}}&C^{i,Q^i_{2,2}}&\cdots&C^{i,Q^i_{1,m}}\\ \vdots&\vdots&\ddots&\vdots\\ C^{i,Q^i_{m,1}}&C^{i,Q^i_{m,2}}&\cdots&C^{i,Q^i_{m,m}} \end{bmatrix}
其中 Cx,yi,jC^{i,j}_{x,y} 为二元组 (j,Px,yi)(j,P^i_{x,y})。容易验证这些是相互正交的拉丁方。□\square
推论 4.1 对于任意正整数 n=∏pikin=\prod p_i^{k_i}，其中给出的是质因数分解，则 N(n)≥min⁡(piki−1)N(n)\ge \min (p_i^{k_i}-1)。
推论 4.2 对于任意正整数 n≢2(mod4)n\not\equiv 2\pmod 4，N(n)≥2N(n)\ge 2，即存在 nn 阶的正交拉丁方对。
定理 5. N(2)=1,N(6)=1N(2)=1,N(6)=1，即不存在 22 阶和 66 阶的正交拉丁方对。
证明. 使用电脑程序暴力枚举验证即可。□\square

进一步研究

考虑一个方便的正交拉丁方组的等价表示：正交阵列。
定义. 对于一个 nn 元集 SS，一个 (s,n)(s,n)-正交阵列（orthogonal array) 是一个 s×n2s\times n^2 的矩阵（ss 个序列），每个元素都是 SS 中的元素，满足对任意两个不同的行，它们对应位置的元素的有序对恰好是所有 n2n^2 个可能的有序对。
（注：SS 本身是什么并不重要。在语境清晰的情况下，可以省去 SS。否则，不妨设 S={1,2,⋯ ,n}S=\{1,2,\cdots,n\}。）
定理 6. 存在 (s,n)(s,n) 正交阵列当且仅当 N(n)≥s−2N(n)\ge s-2。
证明.
⇐\Leftarrow. 取 s−2s-2 个相互正交的 nn 阶拉丁方组，把它们每个从上到下从左到右拼成一个序列，再加上对应的行号（[1,⋯ ,1,2,⋯ ,2,⋯ ,n,⋯ ,n][1,\cdots,1,2,\cdots,2,\cdots,n,\cdots,n]）和列号（[1,2,⋯ ,n,⋯ ,1,2,⋯ ,n][1,2,\cdots,n,\cdots,1,2,\cdots,n]），容易验证它们组成了一个 (s,n)(s,n)-正交阵列。
⇒\Rightarrow. 重排每一列使得第一行为 [1,⋯ ,1,2,⋯ ,2,⋯ ,n,⋯ ,n][1,\cdots,1,2,\cdots,2,\cdots,n,\cdots,n] 而第二行为 [1,2,⋯ ,n,⋯ ,1,2,⋯ ,n][1,2,\cdots,n,\cdots,1,2,\cdots,n]（根据定义显然可以做到），那么容易验证，接下来的每一行从上到下从左到右填入 nn 阶方阵就组成了 s−2s-2 个相互正交的 nn 阶拉丁方。□\square
例. 以下的一对三阶正交拉丁方对应了如下的 (4,3)(4,3)-正交阵列：
[123312231][123231312][111222333123123123123312231123231312]\begin{array}{c} \begin{bmatrix}1&2&3\\3&1&2\\2&3&1\end{bmatrix}\begin{bmatrix}1&2&3\\2&3&1\\3&1&2\end{bmatrix}\\\\ \begin{bmatrix}1&1&1&2&2&2&3&3&3\\ 1&2&3&1&2&3&1&2&3\\ 1&2&3&3&1&2&2&3&1\\ 1&2&3&2&3&1&3&1&2\end{bmatrix} \end{array}
定理 7. 若 N(m)≥2N(m)\ge 2，则 N(3m+1)≥2N(3m+1)\ge 2。
证明. 设 SS 为 {0,1,⋯ ,2m}∪{x1,x2,⋯ ,xm}\{0,1,\cdots,2m\}\cup\{x_1,x_2,\cdots,x_m\}。根据题设，存在关于 {x1,⋯ ,xm}\{x_1,\cdots,x_m\} 的 (4,m)(4,m)-正交阵列 A∗A^*。
设 W=[0,0,⋯ ,0]W=[0,0,\cdots,0]（mm 个 00），X=[1,2,⋯ ,m]X=[1,2,\cdots,m]，Y=[2m,2m−1,⋯ ,m+1]Y=[2m,2m-1,\cdots,m+1]，Z=[x1,x2,⋯ ,xm]Z=[x_1,x_2,\cdots,x_m]，则定义分块矩阵 A0A_0 为
[WXYZXWZYYZWXZYXW]\begin{bmatrix} W&X&Y&Z\\ X&W&Z&Y\\ Y&Z&W&X\\ Z&Y&X&W \end{bmatrix}
定义 AiA_i 为 A0A_0 中所有 {0,1,⋯ ,2m}\{0,1,\cdots,2m\} 中的元素加上 ii 对 2m+12m+1 取模的值。
定义 4×(2m+1)4\times (2m+1) 的矩阵 EE 满足其第 ii 列的数都是 i−1i-1。则分块矩阵
D=[EA0A1⋯A2mA∗]D=\begin{bmatrix}E&A_0&A_1&\cdots&A_{2m}&A^*\end{bmatrix}
为 (4,3m+1)(4,3m+1)-正交阵列。下面验证这一点。
对于 (i,xj)(i,x_j) 型的有序对，显然只会在某个 AkA_k 里出现。只需考虑对于任意两行，第二行是 xjx_j 的列恰在每个 AkA_k 里出现了相同的一次，且对应的数根据定义遍历了每个 {0,1,⋯ ,2m}\{0,1,\cdots,2m\} 的整数。(xj,i)(x_j,i) 同理。
对于 (xi,xj)(x_i,x_j) 型的有序对，只会在 A∗A^* 里出现，并且根据 A∗A^* 的定义的确符合要求。
对于 (i,j)(i,j) 型的有序对，若 i=ji=j，只会在 EE 里出现且恰好出现了一次。否则 i≠ji\neq j。这时它们只会在某个 AkA_k 里出现。
考虑它们的差（在模 2m+12m+1 意义下），可以验证 W−X,X−WW-X,X-W、W−Y,Y−WW-Y,Y-W、X−Y,Y−XX-Y,Y-X 在模 2m+12m+1 意义下都遍历了所有 {1,⋯ ,2m}\{1,\cdots,2m\} 。因此稍作讨论可以发现每个 AkA_k 恰能找到相同的一列满足差是符合要求的，而对应的数根据定义遍历了所有的可能。
综上，DD 为 (4,3m+1)(4,3m+1)-正交阵列。□\square
推论 7.1 N(12m+10)≥2N(12m+10)\ge 2。特别的，N(10)≥2,N(22)≥2N(10)\ge 2,N(22)\ge 2。

与区组设计的联系

定理 8. 若 (v,K,1)(v,K,1)-PBD 存在，则 N(v)≥min⁡k∈KN(k)−1N(v)\ge \min\limits_{k\in K} N(k)-1。
证明. 设 q=min⁡k∈KN(k)q=\min\limits_{k\in K}N(k)。对于每个 k∈Kk\in K，取一个 (q+2,k)(q+2,k)-正交阵列。不妨设第一行是 [1,⋯ ,1,2⋯ ,2,⋯ ,k,⋯ ,k][1,\cdots,1,2\cdots,2,\cdots,k,\cdots,k]（重排），且接下来每行都以 [1,2,⋯ ,k][1,2,\cdots,k] 开头（重标号）。设 DkD_k 为它去掉第一行和前 kk 列组成的 (q+1)×(k2−k)(q+1)\times(k^2-k) 矩阵，则它的每两行恰好包含每个两元素不相等的有序对一次。
设这个 PBD 的每个区组为 B1,B2,⋯ ,BbB_1,B_2,\cdots,B_b。对于每个 BiB_i，定义 EiE_i 为将 D∣Bi∣D_{|B_i|} 的元素替换为 BB 中的元素得到的矩阵。定义 (q+1)×v(q+1)\times v 的矩阵 FF 满足第 jj 列都是 jj。则分块矩阵
A=[E1E2⋯EbF]A=\begin{bmatrix}E_1&E_2&\cdots&E_b&F\end{bmatrix}
是 (q+1,v)(q+1,v)-阶正交阵列。下面验证这一点。
对于任意两行，对于有序对 (x,y)(x,y)，若 x=yx=y，则它恰好在 FF 中出现了一次。否则，恰好有一个 BiB_i 同时包含 x,yx,y，故 EiE_i 恰有一列满足它在对应行上是有序对 (x,y)(x,y)，其它的 EjE_j 不会同时包含 x,yx,y，而 FF 的一列不会有不同的数。综上，AA 为 (q+1,v)(q+1,v)-正交阵列。□\square
定义. 对于 (v,K,1)(v,K,1)-PBD，若 K0⊆KK_0\subseteq K 满足所有大小在 K0K_0 中的区组不交，则称这些区组组成了一个离集（clear set）。
定理 9. 对于一个 (v,K,1)(v,K,1)-PBD，若 K0⊆KK_0\subseteq K 满足所有大小在 K0K_0 中的区组不交，K1=K\K0K_1=K\backslash K_0，则
N(v)≥min⁡k∈K{N(k)k∈K0N(k)−1k∈K1N(v)\ge \min\limits_{k\in K}\begin{cases}N(k)&k\in K_0\\N(k)-1&k\in K_1\end{cases}
证明. 设 q=1+min⁡k∈K{N(k)k∈K0N(k)−1k∈K1q=1+\min\limits_{k\in K}\begin{cases}N(k)&k\in K_0\\N(k)-1&k\in K_1\end{cases}。
对于 k∈K0k\in K_0，定义 PkP_k 为一个 (q+1,ki)(q+1,k_i)-正交阵列。对于 k∈K1k\in K_1，定义 PkP_k 为定理 8 中的 DkD_k。
设这个 PBD 的每个区组为 B1,B2,⋯ ,BbB_1,B_2,\cdots,B_b。对于每个 BiB_i，定义 EiE_i 为将 P∣Bi∣P_{|B_i|} 的元素替换为 BB 中的元素得到的矩阵。定义 (q+1)×v(q+1)\times v 的矩阵 FF 满足第 jj 列都是 jj。再定义 FF 为 q+1q+1 行都相等的矩阵，对于每个不在任何大小为某个 k∈K0k\in K_0 的组中的元素都对应了一列。
则分块矩阵
A=[E1E2⋯EbF]A=\begin{bmatrix}E_1&E_2&\cdots&E_b&F\end{bmatrix}
是 (q+1,v)(q+1,v)-阶正交阵列。下面验证这一点。
对于任意两行，对于有序对 (x,y)(x,y)，若 x=yx=y 且 xx 在 FF 中，则这一对恰好在 FF 中出现了一次。若 x=yx=y 且 xx 不在 FF 中，则这一对恰在某个离集里的区组对应的 EiE_i 中出现了一次。否则，恰好有一个 BiB_i 同时包含 x,yx,y，故 EiE_i 恰有一列满足它在对应行上是有序对 (x,y)(x,y)，其它的 EjE_j 不会同时包含 x,yx,y，而 FF 的一列不会有不同的数。综上，AA 为 (q+1,v)(q+1,v)-正交阵列。□\square
例. 取 44 阶有限射影平面，即 (21,5,1)(21,5,1)-BIBD，任取三不在一个区组中的元素删掉，可以得到一个 (18,{3,4,5},1)(18,\{3,4,5\},1)-PBD。现在大小为 33 的区组组成了一个离集，否则说明某两个区组在删除之前交的大小超过 11，矛盾。因此 N(18)≥min⁡(N(3),N(4)−1,N(5)−1)=2N(18)\ge \min(N(3),N(4)-1,N(5)-1)=2。
例. 取上文的例子中的 (41,5,1)(41,5,1)-BIBD，任取三不在一个区组中的元素删掉，可以得到一个 (38,{3,4,5},1)(38,\{3,4,5\},1)-PBD。现在大小为 33 的区组组成了一个离集，否则说明某两个区组在删除之前交的大小超过 11，矛盾。因此 N(38)≥min⁡(N(3),N(4)−1,N(5)−1)=2N(38)\ge \min(N(3),N(4)-1,N(5)-1)=2。
定理 10. 若 N(m)≥k−1N(m)\ge k-1，则存在一个可分解的 (km,{k,m},1)(km,\{k,m\},1)-PBD，其中 mm 个大小为 kk 的区组组成的分解类有 mm 个，kk 个大小为 mm 的区组组成的分解类有 11 个，共 m+1m+1 个分解类。
证明. 由题意，存在 (k+1,m)(k+1,m)-正交阵列，无妨设其第一行是 [1,⋯ ,1,2⋯ ,2,⋯ ,m,⋯ ,m][1,\cdots,1,2\cdots,2,\cdots,m,\cdots,m]。去掉这一行，则接下来每行的每 mm 个元素是一个 mm 阶排列，且是一个 (k,m)(k,m)-正交阵列。把每一行的元素改成它本身和行号组成的有序对，这样 m2m^2 列定义为一个区组，且每 mm 列构成了全集的一个划分。只有行号相同的有序对的对没有被分配到，那么加上 kk 个所有行号相同的元素组成的区组，构成一个划分即可。□\square
例. 取 m=4,k=3m=4,k=3，若第一步之后得到的 (k,m)(k,m)-正交阵列为
[123412341234123412342143341243211234341243212143]\begin{bmatrix} 1&2&3&4&1&2&3&4&1&2&3&4&1&2&3&4\\ 1&2&3&4&2&1&4&3&3&4&1&2&4&3&2&1\\ 1&2&3&4&3&4&1&2&4&3&2&1&2&1&4&3 \end{bmatrix}
则构成有序对，并重新按照正整数标号得到的结果是
[123412341234123456786587785687659101112111291012111091091211]\begin{bmatrix} 1&2&3&4&1&2&3&4&1&2&3&4&1&2&3&4\\ 5&6&7&8&6&5&8&7&7&8&5&6&8&7&6&5\\ 9&10&11&12&11&12&9&10&12&11&10&9&10&9&12&11 \end{bmatrix}
因此，所有划分分别是 {{1,5,9},{2,6,10},{3,7,11},{4,8,12}}\{\{1,5,9\},\{2,6,10\},\{3,7,11\},\{4,8,12\}\}，{{1,6,11},{2,5,12},{3,8,9},{4,7,10}}\{\{1,6,11\},\{2,5,12\},\{3,8,9\},\{4,7,10\}\}，{{1,7,12},{2,8,11},{3,5,10},{4,6,9}}\{\{1,7,12\},\{2,8,11\},\{3,5,10\},\{4,6,9\}\}，{{1,8,10},{2,7,9},{3,6,12},{4,5,11}}\{\{1,8,10\},\{2,7,9\},\{3,6,12\},\{4,5,11\}\} 和 {{1,2,3,4},{5,6,7,8},{9,10,11,12}}\{\{1,2,3,4\},\{5,6,7,8\},\{9,10,11,12\}\}。这构成了一个符合要求的 (12,{3,4},1)(12,\{3,4\},1)-PBD。
定理 11. 若 N(m)≥k−1N(m)\ge k-1，正整数 x<mx< m，则存在一组 (km+x,{x,m,k,k+1},1)(km+x,\{x,m,k,k+1\},1)-PBD，且 N(km+x)≥min⁡(N(x),N(k)−1,N(k+1)−1)N(km+x)\ge \min(N(x),N(k)-1,N(k+1)-1)。
证明. 取符合定理 10 条件的的一个 (km,{k,m},1)(km,\{k,m\},1)-PBD。设那个 kk 个组成了一个分解类的大小为 mm 的区组为 B1,B2,⋯ ,BkB_1,B_2,\cdots,B_k。对于 i=1,⋯ ,xi=1,\cdots ,x，取一个新的元素 cic_i，在第 ii 个由 mm 个大小为 kk 的区组组成的分解类的每个区组中加入 cic_i，再加入一个新的集合 B∗={c1,c2,⋯ ,cx}B^*=\{c_1,c_2,\cdots,c_x\}。这就完成了构造。
因为 BiB_i 和 B∗B^* 不交，所以若 xx 与 k,k+1k,k+1 都不相等那么后半句自然成立（注意 N(m)≥k−1N(m)\ge k-1 所以自然会取最小值时会被 N(k)−1N(k)-1 消掉）。而若 xx 与 kk 或 k+1k+1 相等的话那么根据取 min⁡\min 它们的贡献会被吃掉，所以也没有问题。□\square

收尾工作

既然已经得到了一个很强大的定理，那么接下来进行一些收尾工作。
定理 12. 对于素数幂 qq，N(q2−1)≥N(q−1)N(q^2-1)\ge N(q-1)。
证明. 取 qq 阶仿射平面，即 (q2,q,1)(q^2,q,1)-BIBD。去掉一个元素，得到一个 (q2−1,{q,q−1},1)(q^2-1,\{q,q-1\},1)-PBD，且大小为 q−1q-1 的元素显然构成了一个离集。因此 N(q2−1)≥min⁡(N(q−1),N(q)−1)N(q^2-1)\ge \min(N(q-1),N(q)-1)。因为 N(q)−1=q−2≤N(q−1)N(q)-1=q-2\le N(q-1)，故原式成立。□\square
定理 13. N(12)≥5N(12)\ge 5。
证明. 直接验证如下构造即可。设
A=[012345123450234501345012450123501234],B=[678910117891011689101167910116781011678911678910],L1=[ABBA]A=\begin{bmatrix}0&1&2&3&4&5\\1&2&3&4&5&0\\2&3&4&5&0&1\\3&4&5&0&1&2\\4&5&0&1&2&3\\5&0&1&2&3&4\end{bmatrix},B=\begin{bmatrix}6&7&8&9&10&11\\7&8&9&10&11&6\\8&9&10&11&6&7\\9&10&11&6&7&8\\10&11&6&7&8&9\\11&6&7&8&9&10\end{bmatrix},L_1=\begin{bmatrix}A&B\\B&A\end{bmatrix}
而 L2,L3,L4,L5L_2,L_3,L_4,L_5 为重排 L1L_1 的列得到的矩阵，满足它们的第一行分别是
[06827191141053036191128547100811159310276404111027869135]\begin{bmatrix} 0&6&8&2&7&1&9&11&4&10&5&3\\ 0&3&6&1&9&11&2&8&5&4&7&10\\ 0&8&1&11&5&9&3&10&2&7&6&4\\ 0&4&11&10&2&7&8&6&9&1&3&5 \end{bmatrix}
□\square
（这一结果由 Dulmage、Johnson 和 Mendelsohn 在 1961 年给出，感兴趣可以搜索他们的论文，笔者没有看。）
定理 14. N(4m)≥3N(4m)\ge 3。
证明. 根据推论 4.2 的构造，只需要考虑 mm 是 33 的倍数而不是 99 的倍数的情况，其它情况是不言自明的。且根据这个构造，只需要构造 12,2412,24 的情况，再乘上不小于 44 的素数幂就可以得到所有这些情况的结论。而 N(12)≥3N(12)\ge 3 由定理 13 给出，N(24)≥3N(24)\ge 3 是定理 12 在 q=5q=5 时的情形。□\square
定理 15. N(14)≥2N(14)\ge 2。
证明. 直接验证如下构造即可。设
A=[083129251061114137131940103611712258613210511147128039471331162125809110258134127306911011113691350841710212312471013619528110124058111372106391100516912138311742511162710013941283961227381111310504110703849122131165721181495100313126891011120123456713]A=\begin{bmatrix} 0&8&3&12&9&2&5&10&6&11&1&4&13&7\\ 13&1&9&4&0&10&3&6&11&7&12&2&5&8\\ 6&13&2&10&5&1&11&4&7&12&8&0&3&9\\ 4&7&13&3&11&6&2&12&5&8&0&9&1&10\\ 2&5&8&13&4&12&7&3&0&6&9&1&10&11\\ 11&3&6&9&13&5&0&8&4&1&7&10&2&12\\ 3&12&4&7&10&13&6&1&9&5&2&8&11&0\\ 12&4&0&5&8&11&13&7&2&10&6&3&9&1\\ 10&0&5&1&6&9&12&13&8&3&11&7&4&2\\ 5&11&1&6&2&7&10&0&13&9&4&12&8&3\\ 9&6&12&2&7&3&8&11&1&13&10&5&0&4\\ 1&10&7&0&3&8&4&9&12&2&13&11&6&5\\ 7&2&11&8&1&4&9&5&10&0&3&13&12&6\\ 8&9&10&11&12&0&1&2&3&4&5&6&7&13 \end{bmatrix}
则 AA 和 ATA^T 构成一组正交拉丁方。
（注意观察 AA 的对角线上的结构——忽略最后一行和最后一列。n=10n=10 的时候也有类似的构造。）
定理 16. N(26)≥2N(26)\ge 2。
考虑类似定理 7 的构造。设 SS 为 {0,1,⋯ ,18}∪{x1,x2,⋯ ,x7}\{0,1,\cdots,18\}\cup\{x_1,x_2,\cdots,x_7\}。存在关于 {x1,⋯ ,x7}\{x_1,\cdots,x_7\} 的 (4,7)(4,7)-正交阵列 A∗A^*。
设 W=[0,x1,⋯ ,x7]W=[0,x_1,\cdots,x_7]，X=[3,15,10,7,8,12,9,6]X=[3,15,10,7,8,12,9,6]，Y=[1,0,0,0,0,0,0,0]Y=[1,0,0,0,0,0,0,0]，Z=[6,1,2,4,6,7,8,10]Z=[6,1,2,4,6,7,8,10]，则定义分块矩阵 A0A_0 为
[WZXYXYWZYWZXZXYW]\begin{bmatrix} W&Z&X&Y\\ X&Y&W&Z\\ Y&W&Z&X\\ Z&X&Y&W \end{bmatrix}
定义 AiA_i 为 A0A_0 中所有 {0,1,⋯ ,18}\{0,1,\cdots,18\} 中的元素加上 ii 对 1919 取模的值。
定义 4×194\times 19 的矩阵 EE 满足其第 ii 列的数都是 i−1i-1。则分块矩阵
D=[EA0A1⋯A18A∗]D=\begin{bmatrix}E&A_0&A_1&\cdots&A_{18}&A^*\end{bmatrix}
为 (4,26)(4,26)-正交阵列。下面验证这一点。
对于 (i,xj)(i,x_j) 型的有序对，显然只会在某个 AkA_k 里出现。只需考虑对于任意两行，第二行是 xjx_j 的列恰在每个 AkA_k 里出现了相同的一次，且对应的数根据定义遍历了每个 {0,1,⋯ ,2m}\{0,1,\cdots,2m\} 的整数。(xj,i)(x_j,i) 同理。
对于 (xi,xj)(x_i,x_j) 型的有序对，只会在 A∗A^* 里出现，并且根据 A∗A^* 的定义的确符合要求。
对于 (i,j)(i,j) 型的有序对，若 i=ji=j，只会在 EE 里出现且恰好出现了一次。否则 i≠ji\neq j。这时它们只会在某个 AkA_k 里出现。
考虑它们的差（在模 2m+12m+1 意义下），可以验证 A0A_0 的任意两行中选取都是 (i,j)(i,j) 的元素对作差都遍历了 {1,⋯ ,18}\{1,\cdots,18\}，而对应的数根据定义遍历了所有的可能。
综上，DD 为 (4,26)(4,26)-正交阵列。□\square
定理 17. 对于正整数 nn，N(n)≥2N(n)\ge 2，即存在 nn 阶的正交拉丁方对，当且仅当 n≠2,6n\neq 2,6。
证明. 根据推论 4.2，只需考虑 n≡2(mod4)n\equiv 2\pmod 4 的情况。首先，在上文的例子、定理和推论中，n≤26n\le 26 的情况均已讨论完毕。
在定理 11 中取 m=4t,k=4m=4t,k=4，根据定理 14 有 N(m)≥k−1N(m)\ge k-1，因此符合条件。那么若 N(x)≥2N(x)\ge 2 且 x<4tx<4t 则有 N(16t+x)≥2N(16t+x)\ge 2。对于 n≡2,6,10,14(mod16)n\equiv 2,6,10,14\pmod {16} 的情况，可以取 x=18,22,10,14x=18,22,10,14。
对于 x=10x=10，t≥3t\ge 3 时即构造合法。因此只需要考虑 10+16×2=4210+16\times 2=42 以内的，>26>26 的只有 4242。
对于 x=14x=14，t≥4t\ge 4 时即构造合法，因此只需要考虑 14+16×3=6214+16\times 3=62 以内的，>26>26 的有 30,46,6230,46,62。
对于 x=18x=18，t≥5t\ge 5 时即构造合法。因此只需要考虑 18+16×4=8218+16\times 4=82 以内的，>26>26 的有 34,50,66,8234,50,66,82。
对于 x=22x=22，t≥6t\ge 6 时即构造合法，因此只需要考虑 22+16×5=10222+16\times 5=102 以内的，>26>26 的有 38,54,70,86,10238,54,70,86,102。
因为 N(nm)≥min⁡(N(n),N(m))N(nm)\ge\min(N(n),N(m))，因此只需要考虑 2p2p 即可（pp 为素数）。而根据推论 7.1，不需要考虑 12k+1012k+10 型的数。因此，筛选出需要考虑的只有 38,62,8638,62,86。对于 3838，它在上文的例子中给出了结论。对于 62,8662,86，它们分别是 4×13+104\times 13+10 和 4×19+104\times 19+10，而 13,1913,19 都是素数，满足其 NN 值为自己减 11，也可以利用定理 11 得出结论。□\square

后记

最初笔者也听说过定理 17，但是没有听过证明。仔细研究此题是来自群友的提问怎样构造 2p（4t+2）形式的正交拉丁方对？，去 StackExchange 的回答里找到了相关文献，在此整理，供大家学习。以上。

参考文献

[1] Ian Anderson, Combinatorial designs and tournaments, 1997.

评论

共 8 条评论，欢迎与作者交流。

正在加载评论...