在组合数学中,如果两个同阶的拉丁方阵叠加后,每个位置上的有序对条目都是唯一的,则这两个拉丁方阵被称为正交的。
如果一组同阶的拉丁方阵中,任意两个方阵都是正交的,则这组方阵被称为一组相互正交的拉丁方阵(MOLS)。
基于两个集合S和T(两个集合可以是相同的),每个集合包含n个符号,形成一个n×n的单元格排列的方阵。每个单元格包含一个有序对(s, t),其中s属于S集合,t属于T集合。在这样的方阵中,每一行和每一列恰好包含S集合和T集合中的每一个元素一次,且没有两个单元格包含相同的有序对。
以MOLS(4)为例子讨论
一个阶数为 𝑛 的拉丁方阵是一个 𝑛×𝑛 的方格表,其中每个数字或符号在每一行和每一列中恰好出现一次。
而对于相互正交的拉丁方阵,其中任意两个方阵都正交。即任意两个方阵叠加时,每个可能的有序对(来自两个方阵的元素组合)在叠加的方阵中都恰好出现一次。
叠加方阵形式
(1,1,1)(2,2,2)(3,3,3)(4,4,4)
(2,4,3)(1,3,4)(4,2,1)(3,1,2)
(3,2,4)(4,1,3)(1,4,2)(2,3,1)
(4,3,2)(3,4,1)(2,1,4)(1,2,3)
可以看出,叠加方阵中的元素无重复
完全集是一个重要概念。指一组大小为 𝑛−1的相互正交拉丁方阵集合(记作 MOLS(n-1)),其中每个方阵的阶数都是 𝑛。这意味着在 𝑛×𝑛 的拉丁方阵中,可以有最多 𝑛−1 个互相正交的方阵。例如,如果一个方阵的阶数为 4,那么最多可以有 3 个互相正交的拉丁方阵形成一个完全集。
定理:对于任何给定的阶数n,最多可以有(n-1)个相互正交的拉丁方阵(MOLS),当n是素数的幂时,达上界。
定理:当阶数n是一个素数的幂时,可以构造一个完整的相互正交拉丁方阵集合(MOLS),即(n−1)个MOLS。这个构造方法是通过填充每一个方阵𝐿𝑖,其中0<𝑖<𝑛,使用公式 𝐿𝑖[𝑥,𝑦]=𝑖⋅𝑥+𝑦(mod n)