正交拉丁方的构造

MatrixGroup · 2025-10-22 23:27:42 · 算法·理论

前言

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

引入

定义. 对于一个 n 元集 S，一个 n 阶拉丁方（Latin square）是一个 n 阶方阵，满足每行每列恰有 S 中的每个元素各一个。

（注：S 本身是什么并不重要。在语境清晰的情况下，可以省去 S。否则，不妨设 S=\{1,2,\cdots,n\}。）

例. 如下是一个 6\times 6 的拉丁方：

定义. 一对 n 阶拉丁方 P,Q 是正交的（orthogonal），当且仅当对于每对 i,j\in \{1,2,\cdots,n\}，二元组 (P_{i,j},Q_{i,j}) 两两不同。

例. 如下是一对 10\times 10 的正交拉丁方：

定义. 一些 n 阶拉丁方是（相互）正交的（mutually orthogonal），当且仅当其中每两个拉丁方都是正交的。

例. 如下是一组 4\times 4 的相互正交拉丁方：

定义. 对于正整数 n，N(n) 表示最多的（相互）正交拉丁方组的拉丁方个数。特别的，N(1)=+\infty。

例. N(2)=1,N(3)=2。

前置：区组设计

定义. 对于一个 v 元集 S，一个集合 K\subseteq\{1,2,\cdots,v-1\}，一个正整数 \lambda，定义一个 (v,K,\lambda)-两两平衡设计（pairwise balanced design, PBD）为 S 的一个子集族（其中每个 S 的子集被称为一个「区组（block）」），满足以下两点：

• 每个区组的大小都是 K 中的元素。
• 对于每对不同的元素 x,y\in S(x\neq y)，恰有 \lambda 个区组同时包含 x 和 y。

特别的，若 K=\{k\} 是单元集，则称它为一个 (v,k,\lambda)-平衡不完全区组设计（balanced incomplete block design, BIBD）。

特别的，对于正整数 n\ge 2，一个 (n^2+n+1,n+1,1)-BIBD 被称为一个 n 阶有限射影平面（finite projective plane）。

特别的，对于正整数 n\ge 2，一个 (n^2,n,1)-BIBD 被称为一个 n 阶有限仿射平面（finite affine plane）。

（注：S 本身是什么并不重要。在语境清晰的情况下，可以省去 S。否则，不妨设 S=\{1,2,\cdots,v\}。）

例. 一个 (v,3,1)-BIBD 是熟知的 Steiner 三元系（Steiner triple system）。

例. \{0,7,10,11,23\} 和 \{0,5,14,20,22\} 在模 41 意义下每个元素同加一个数得到的 82 个集合，组成了一个 (41,5,1)-BIBD。

定理 1. 对于素数幂 q，存在 q 阶有限射影平面和 q 阶有限仿射平面。

证明. 所有 \{(a,b,c)|a,b,c\in \mathbb F_q,(a,b,c)\neq (0,0,0)\} 在 (a,b,c)\sim (at,bt,ct)(t\in\mathbb F_q,t\neq 0) 的等价关系下构成等价类。对于所有等价类，任取代表元 (a,b,c)，则所有 (x,y,z) 满足 ax+by+cz=0 所在的等价类为一个区组，则容易验证这就是一个 q 阶有限射影平面。

强制要求 c\neq 0（区组中去掉 (a,b,c)\sim (0,0,1) 即 z=0 的等价类）即可得到 n 阶有限仿射平面。\square

定义. 一个 PBD 是可分解的（resolvable）当且仅当存在一个区组的划分，使得划分的每一类中的区组构成了 S 的一个划分。这个划分的每一类被称为一个分解类（resolution class）或平行类（parallel class）。

例. \{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\} 是一个可分解的 (4,2,1)-BIBD，它可以被分解为 \{\{1,2\},\{3,4\}\},\{\{1,3\},\{2,4\}\},\{\{1,4\},\{2,3\}\}。

初步的探索

先来研究一些关于 N(n) 的简单结论！

定理 2. 对于正整数 n\ge 2，N(n)\le n-1。

证明. 设 N(n)=r。因为标号不重要，无妨设每个拉丁方都满足第一行是 1,2,\cdots,n。则第二行第一列的元素不能是 1，也必须两两不同（每对相同的数都在第一行出现过了），因此 r\le n-1。\square

定理 3. 对于素数幂 q\ge 2，N(q)=q-1。

证明. 根据定理 2，只需构造 q-1 个相互正交的拉丁方即可。对于 \mathbb F_q=\{x_1,x_2,\cdots,x_q\} 中的每个非零元素 a\neq 0，构造方阵 M^a 满足 M^a_{i,j}=x_i+ax_j。容易验证这些是相互正交的拉丁方。\square

定理 4. 对于正整数 n,m，N(nm)\ge \min(N(n),N(m))。

证明. 无妨设 n,m\ge 2。任取 q=\min(N(n),N(m)) 个 n 阶正交拉丁方 P^1,P^2,\cdots,P^q 和 m 阶正交拉丁方 Q^1,Q^2,\cdots,Q^q（假定元素为 1\sim m 的正整数）。构造分块矩阵

其中 C^{i,j}_{x,y} 为二元组 (j,P^i_{x,y})。容易验证这些是相互正交的拉丁方。\square

推论 4.1 对于任意正整数 n=\prod p_i^{k_i}，其中给出的是质因数分解，则 N(n)\ge \min (p_i^{k_i}-1)。

推论 4.2 对于任意正整数 n\not\equiv 2\pmod 4，N(n)\ge 2，即存在 n 阶的正交拉丁方对。

定理 5. N(2)=1,N(6)=1，即不存在 2 阶和 6 阶的正交拉丁方对。

证明. 使用电脑程序暴力枚举验证即可。\square

进一步研究

考虑一个方便的正交拉丁方组的等价表示：正交阵列。

定义. 对于一个 n 元集 S，一个 (s,n)-正交阵列（orthogonal array) 是一个 s\times n^2 的矩阵（s 个序列），每个元素都是 S 中的元素，满足对任意两个不同的行，它们对应位置的元素的有序对恰好是所有 n^2 个可能的有序对。

（注：S 本身是什么并不重要。在语境清晰的情况下，可以省去 S。否则，不妨设 S=\{1,2,\cdots,n\}。）

定理 6. 存在 (s,n) 正交阵列当且仅当 N(n)\ge s-2。

证明.

例. 以下的一对三阶正交拉丁方对应了如下的 (4,3)-正交阵列：

定理 7. 若 N(m)\ge 2，则 N(3m+1)\ge 2。

证明. 设 S 为 \{0,1,\cdots,2m\}\cup\{x_1,x_2,\cdots,x_m\}。根据题设，存在关于 \{x_1,\cdots,x_m\} 的 (4,m)-正交阵列 A^*。

设 W=[0,0,\cdots,0]（m 个 0），X=[1,2,\cdots,m]，Y=[2m,2m-1,\cdots,m+1]，Z=[x_1,x_2,\cdots,x_m]，则定义分块矩阵 A_0 为

定义 A_i 为 A_0 中所有 \{0,1,\cdots,2m\} 中的元素加上 i 对 2m+1 取模的值。

定义 4\times (2m+1) 的矩阵 E 满足其第 i 列的数都是 i-1。则分块矩阵

为 (4,3m+1)-正交阵列。下面验证这一点。

对于 (i,x_j) 型的有序对，显然只会在某个 A_k 里出现。只需考虑对于任意两行，第二行是 x_j 的列恰在每个 A_k 里出现了相同的一次，且对应的数根据定义遍历了每个 \{0,1,\cdots,2m\} 的整数。(x_j,i) 同理。

对于 (x_i,x_j) 型的有序对，只会在 A^* 里出现，并且根据 A^* 的定义的确符合要求。

对于 (i,j) 型的有序对，若 i=j，只会在 E 里出现且恰好出现了一次。否则 i\neq j。这时它们只会在某个 A_k 里出现。

考虑它们的差（在模 2m+1 意义下），可以验证 W-X,X-W、W-Y,Y-W、X-Y,Y-X 在模 2m+1 意义下都遍历了所有 \{1,\cdots,2m\} 。因此稍作讨论可以发现每个 A_k 恰能找到相同的一列满足差是符合要求的，而对应的数根据定义遍历了所有的可能。

综上，D 为 (4,3m+1)-正交阵列。\square

推论 7.1 N(12m+10)\ge 2。特别的，N(10)\ge 2,N(22)\ge 2。

与区组设计的联系

定理 8. 若 (v,K,1)-PBD 存在，则 N(v)\ge \min\limits_{k\in K} N(k)-1。

证明. 设 q=\min\limits_{k\in K}N(k)。对于每个 k\in K，取一个 (q+2,k)-正交阵列。不妨设第一行是 [1,\cdots,1,2\cdots,2,\cdots,k,\cdots,k]（重排），且接下来每行都以 [1,2,\cdots,k] 开头（重标号）。设 D_k 为它去掉第一行和前 k 列组成的 (q+1)\times(k^2-k) 矩阵，则它的每两行恰好包含每个两元素不相等的有序对一次。

设这个 PBD 的每个区组为 B_1,B_2,\cdots,B_b。对于每个 B_i，定义 E_i 为将 D_{|B_i|} 的元素替换为 B 中的元素得到的矩阵。定义 (q+1)\times v 的矩阵 F 满足第 j 列都是 j。则分块矩阵

是 (q+1,v)-阶正交阵列。下面验证这一点。

对于任意两行，对于有序对 (x,y)，若 x=y，则它恰好在 F 中出现了一次。否则，恰好有一个 B_i 同时包含 x,y，故 E_i 恰有一列满足它在对应行上是有序对 (x,y)，其它的 E_j 不会同时包含 x,y，而 F 的一列不会有不同的数。综上，A 为 (q+1,v)-正交阵列。\square

定义. 对于 (v,K,1)-PBD，若 K_0\subseteq K 满足所有大小在 K_0 中的区组不交，则称这些区组组成了一个离集（clear set）。

定理 9. 对于一个 (v,K,1)-PBD，若 K_0\subseteq K 满足所有大小在 K_0 中的区组不交，K_1=K\backslash K_0，则

证明. 设 q=1+\min\limits_{k\in K}\begin{cases}N(k)&k\in K_0\\N(k)-1&k\in K_1\end{cases}。

对于 k\in K_0，定义 P_k 为一个 (q+1,k_i)-正交阵列。对于 k\in K_1，定义 P_k 为定理 8 中的 D_k。

设这个 PBD 的每个区组为 B_1,B_2,\cdots,B_b。对于每个 B_i，定义 E_i 为将 P_{|B_i|} 的元素替换为 B 中的元素得到的矩阵。定义 (q+1)\times v 的矩阵 F 满足第 j 列都是 j。再定义 F 为 q+1 行都相等的矩阵，对于每个不在任何大小为某个 k\in K_0 的组中的元素都对应了一列。

则分块矩阵

是 (q+1,v)-阶正交阵列。下面验证这一点。

对于任意两行，对于有序对 (x,y)，若 x=y 且 x 在 F 中，则这一对恰好在 F 中出现了一次。若 x=y 且 x 不在 F 中，则这一对恰在某个离集里的区组对应的 E_i 中出现了一次。否则，恰好有一个 B_i 同时包含 x,y，故 E_i 恰有一列满足它在对应行上是有序对 (x,y)，其它的 E_j 不会同时包含 x,y，而 F 的一列不会有不同的数。综上，A 为 (q+1,v)-正交阵列。\square

例. 取 4 阶有限射影平面，即 (21,5,1)-BIBD，任取三不在一个区组中的元素删掉，可以得到一个 (18,\{3,4,5\},1)-PBD。现在大小为 3 的区组组成了一个离集，否则说明某两个区组在删除之前交的大小超过 1，矛盾。因此 N(18)\ge \min(N(3),N(4)-1,N(5)-1)=2。

例. 取上文的例子中的 (41,5,1)-BIBD，任取三不在一个区组中的元素删掉，可以得到一个 (38,\{3,4,5\},1)-PBD。现在大小为 3 的区组组成了一个离集，否则说明某两个区组在删除之前交的大小超过 1，矛盾。因此 N(38)\ge \min(N(3),N(4)-1,N(5)-1)=2。

定理 10. 若 N(m)\ge k-1，则存在一个可分解的 (km,\{k,m\},1)-PBD，其中 m 个大小为 k 的区组组成的分解类有 m 个，k 个大小为 m 的区组组成的分解类有 1 个，共 m+1 个分解类。

证明. 由题意，存在 (k+1,m)-正交阵列，无妨设其第一行是 [1,\cdots,1,2\cdots,2,\cdots,m,\cdots,m]。去掉这一行，则接下来每行的每 m 个元素是一个 m 阶排列，且是一个 (k,m)-正交阵列。把每一行的元素改成它本身和行号组成的有序对，这样 m^2 列定义为一个区组，且每 m 列构成了全集的一个划分。只有行号相同的有序对的对没有被分配到，那么加上 k 个所有行号相同的元素组成的区组，构成一个划分即可。\square

例. 取 m=4,k=3，若第一步之后得到的 (k,m)-正交阵列为

则构成有序对，并重新按照正整数标号得到的结果是

因此，所有划分分别是 \{\{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,7,12\},\{2,8,11\},\{3,5,10\},\{4,6,9\}\}，\{\{1,8,10\},\{2,7,9\},\{3,6,12\},\{4,5,11\}\} 和 \{\{1,2,3,4\},\{5,6,7,8\},\{9,10,11,12\}\}。这构成了一个符合要求的 (12,\{3,4\},1)-PBD。

定理 11. 若 N(m)\ge k-1，正整数 x< m，则存在一组 (km+x,\{x,m,k,k+1\},1)-PBD，且 N(km+x)\ge \min(N(x),N(k)-1,N(k+1)-1)。

证明. 取符合定理 10 条件的的一个 (km,\{k,m\},1)-PBD。设那个 k 个组成了一个分解类的大小为 m 的区组为 B_1,B_2,\cdots,B_k。对于 i=1,\cdots ,x，取一个新的元素 c_i，在第 i 个由 m 个大小为 k 的区组组成的分解类的每个区组中加入 c_i，再加入一个新的集合 B^*=\{c_1,c_2,\cdots,c_x\}。这就完成了构造。

因为 B_i 和 B^* 不交，所以若 x 与 k,k+1 都不相等那么后半句自然成立（注意 N(m)\ge k-1 所以自然会取最小值时会被 N(k)-1 消掉）。而若 x 与 k 或 k+1 相等的话那么根据取 \min 它们的贡献会被吃掉，所以也没有问题。\square

收尾工作

既然已经得到了一个很强大的定理，那么接下来进行一些收尾工作。

定理 12. 对于素数幂 q，N(q^2-1)\ge N(q-1)。

证明. 取 q 阶仿射平面，即 (q^2,q,1)-BIBD。去掉一个元素，得到一个 (q^2-1,\{q,q-1\},1)-PBD，且大小为 q-1 的元素显然构成了一个离集。因此 N(q^2-1)\ge \min(N(q-1),N(q)-1)。因为 N(q)-1=q-2\le N(q-1)，故原式成立。\square

定理 13. N(12)\ge 5。

证明. 直接验证如下构造即可。设

而 L_2,L_3,L_4,L_5 为重排 L_1 的列得到的矩阵，满足它们的第一行分别是

（这一结果由 Dulmage、Johnson 和 Mendelsohn 在 1961 年给出，感兴趣可以搜索他们的论文，笔者没有看。）

定理 14. N(4m)\ge 3。

证明. 根据推论 4.2 的构造，只需要考虑 m 是 3 的倍数而不是 9 的倍数的情况，其它情况是不言自明的。且根据这个构造，只需要构造 12,24 的情况，再乘上不小于 4 的素数幂就可以得到所有这些情况的结论。而 N(12)\ge 3 由定理 13 给出，N(24)\ge 3 是定理 12 在 q=5 时的情形。\square

定理 15. N(14)\ge 2。

证明. 直接验证如下构造即可。设

则 A 和 A^T 构成一组正交拉丁方。

（注意观察 A 的对角线上的结构——忽略最后一行和最后一列。n=10 的时候也有类似的构造。）

定理 16. N(26)\ge 2。

考虑类似定理 7 的构造。设 S 为 \{0,1,\cdots,18\}\cup\{x_1,x_2,\cdots,x_7\}。存在关于 \{x_1,\cdots,x_7\} 的 (4,7)-正交阵列 A^*。

设 W=[0,x_1,\cdots,x_7]，X=[3,15,10,7,8,12,9,6]，Y=[1,0,0,0,0,0,0,0]，Z=[6,1,2,4,6,7,8,10]，则定义分块矩阵 A_0 为

定义 A_i 为 A_0 中所有 \{0,1,\cdots,18\} 中的元素加上 i 对 19 取模的值。

定义 4\times 19 的矩阵 E 满足其第 i 列的数都是 i-1。则分块矩阵

为 (4,26)-正交阵列。下面验证这一点。

对于 (i,x_j) 型的有序对，显然只会在某个 A_k 里出现。只需考虑对于任意两行，第二行是 x_j 的列恰在每个 A_k 里出现了相同的一次，且对应的数根据定义遍历了每个 \{0,1,\cdots,2m\} 的整数。(x_j,i) 同理。

对于 (x_i,x_j) 型的有序对，只会在 A^* 里出现，并且根据 A^* 的定义的确符合要求。

对于 (i,j) 型的有序对，若 i=j，只会在 E 里出现且恰好出现了一次。否则 i\neq j。这时它们只会在某个 A_k 里出现。

考虑它们的差（在模 2m+1 意义下），可以验证 A_0 的任意两行中选取都是 (i,j) 的元素对作差都遍历了 \{1,\cdots,18\}，而对应的数根据定义遍历了所有的可能。

综上，D 为 (4,26)-正交阵列。\square

定理 17. 对于正整数 n，N(n)\ge 2，即存在 n 阶的正交拉丁方对，当且仅当 n\neq 2,6。

证明. 根据推论 4.2，只需考虑 n\equiv 2\pmod 4 的情况。首先，在上文的例子、定理和推论中，n\le 26 的情况均已讨论完毕。

在定理 11 中取 m=4t,k=4，根据定理 14 有 N(m)\ge k-1，因此符合条件。那么若 N(x)\ge 2 且 x<4t 则有 N(16t+x)\ge 2。对于 n\equiv 2,6,10,14\pmod {16} 的情况，可以取 x=18,22,10,14。

对于 x=10，t\ge 3 时即构造合法。因此只需要考虑 10+16\times 2=42 以内的，>26 的只有 42。

对于 x=14，t\ge 4 时即构造合法，因此只需要考虑 14+16\times 3=62 以内的，>26 的有 30,46,62。

对于 x=18，t\ge 5 时即构造合法。因此只需要考虑 18+16\times 4=82 以内的，>26 的有 34,50,66,82。

对于 x=22，t\ge 6 时即构造合法，因此只需要考虑 22+16\times 5=102 以内的，>26 的有 38,54,70,86,102。

因为 N(nm)\ge\min(N(n),N(m))，因此只需要考虑 2p 即可（p 为素数）。而根据推论 7.1，不需要考虑 12k+10 型的数。因此，筛选出需要考虑的只有 38,62,86。对于 38，它在上文的例子中给出了结论。对于 62,86，它们分别是 4\times 13+10 和 4\times 19+10，而 13,19 都是素数，满足其 N 值为自己减 1，也可以利用定理 11 得出结论。\square

后记

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

参考文献

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