正交的拉丁方阵（MOLS）

在组合数学中，如果两个同阶的拉丁方阵叠加后，每个位置上的有序对条目都是唯一的，则这两个拉丁方阵被称为正交的。

如果一组同阶的拉丁方阵中，任意两个方阵都是正交的，则这组方阵被称为一组相互正交的拉丁方阵（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）

原文地址：https://blog.csdn.net/qq_53286237/article/details/140147062

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！