拉丁方陣

拉丁方陣（英語：Latin square）是一種 n × n 的方陣，在這種 n × n 的方陣裡，恰有 n 種不同的元素，每一種不同的元素在同一行或同一列裡只出現一次。以下是兩個拉丁方陣舉例：

${\displaystyle {\begin{bmatrix}1&2&3\\2&3&1\\3&1&2\\\end{bmatrix}}{\begin{bmatrix}a&b&d&c\\b&c&a&d\\c&d&b&a\\d&a&c&b\end{bmatrix}}}$

拉丁方陣有此名稱是因為瑞士數學家和物理學家欧拉使用拉丁字母來做為拉丁方陣裡的元素的符號。

當一個拉丁方陣的第一行與第一列的元素按順序排列時，称為這個拉丁方陣的標準型，英語稱為"reduced Latin square, normalized Latin square, 或Latin square in standard form"。

許多對於拉丁方陣的運算都會產生新的拉丁方陣。例如說，交換拉丁方陣裡的行、交換拉丁方陣裡的列、或是交換拉丁方陣裡的元素的符號，都會得到一個新的拉丁方陣。交換拉丁方陣裡的行、交換拉丁方陣裡的列、或是交換拉丁方陣裡的元素的符號所得的新的拉丁方陣與原來的拉丁方陣稱為同型(isotopic)。同型(isotopism)是一個等價關係，因此所有的拉丁方陣所成的集合可以分成同型類別(isotopic class)的子集合，同型的拉丁方陣屬於同一個同型類別，而不屬於同一個同型類別的拉丁方陣則不同型。

设有两个阶数相同的拉丁方阵${\displaystyle A_{1}=(a_{i,j}^{(1)})_{n\times n},A_{2}=(a_{i,j}^{(2)})_{n\times n}}$，其中将所有放置位置相同的元素组成一个二元组，组合成一个新的矩阵${\displaystyle ((a_{i,j}^{(1)},a_{i,j}^{(2)}))_{n\times n}}$。 当这个新的矩阵${\displaystyle ((a_{i,j}^{(1)},a_{i,j}^{(2)}))_{n\times n}}$中每一个元素互不相同时，拉丁方阵${\displaystyle A_{1}}$和${\displaystyle A_{2}}$是互相正交的。 此时，${\displaystyle A_{1}}$和${\displaystyle A_{2}}$即为一对正交拉丁方。 而在阶数固定的情况下，所有两两正交的拉丁方所成的集合称为正交拉丁方族。

根据前面所得到关于正交的定义，兩個拉丁方陣相正交所得到的方陣為希臘拉丁方陣(Graeco-Latin square)。 事实上，并不是任意阶数的拉丁方都存在一对正交拉丁方，也就是说，并不是任意阶数的拉丁方均存在希臘拉丁方陣。2阶和6阶的希腊拉丁方阵不存在，其他所有阶的希腊拉丁方阵都存在。

若n阶拉丁方存在r个两两正交的拉丁方，那么${\displaystyle r\leq n-1}$。

当该定理中的等号成立时，该阶正交拉丁方族称为完全的。 可以分析得到，当n为0或1时，存在无限多个正交的拉丁方，当n为2时，不存在正交拉丁方族。 此外，当n为6时，也不存在正交拉丁方族，这个结论是通过对三十六军官问题的尝试得到的。 三十六军官问题指的是是否有一个解决方案使得来自6个不同地区的6个不同军衔的军官排成${\displaystyle 6\times 6}$的方阵，其中每一行每一列的军官都来自于不同的地区且具有不同的军衔。 而该问题的方案即为6阶正交拉丁方的个数，该问题于1901年被Gaston Tarry证明为无解^[1][2]。 除了上述三种情况外，当阶数小于等于8时，均存在有n-1个正交的拉丁方。

如当n=3时，存在两个正交的拉丁方。 ${\displaystyle {\begin{bmatrix}1&2&3\\2&3&1\\3&1&2\\\end{bmatrix}}}$ ${\displaystyle {\begin{bmatrix}1&2&3\\3&1&2\\2&3&1\\\end{bmatrix}}}$ 当阶数更多时${\displaystyle n\leq 8}$，可以通过正交拉丁方表^[3]得到正交拉丁方族。

事實上，當階數n是質數或者質數的冪次時，必定存在n-1個正交拉丁方，另外，當n除以4餘1或2，而且n不是兩個平方數的和（0也算作平方數），就一定不存在n-1個正交的拉丁方，而對於10階的情形，已經確定至少存在2個正交的拉丁方，但是不存在9個正交的拉丁方，因此10階正交拉丁方的個數最少是2，最大是8（因為到目前為止，連3個正交的10階拉丁方都還沒找到，所以有猜測是10階正交拉丁方的個數是2），對於12階，已經確定至少存在5個正交的拉丁方了^[4]。

目前，沒有公式可以計算 n × n 的拉丁方陣的數量，當 n 很大時，拉丁方陣的數量的最精確的估計值，其上下界也相差很遠。 具体估计公式为： ${\displaystyle \prod _{k=1}^{n}(k!)^{n/k}\geq L_{n}\geq {\frac {(n!)^{2n}}{n^{n^{2}}}}}$

以下是已知的數值。當 n 增加時，拉丁方陣的數量急速增多。

若不要求行數等於列數，而考慮 ${\displaystyle r<n}$ 時 ${\displaystyle r\times n}$ 大小的矩陣，且將「${\displaystyle n}$ 種元素各在每行每列恰好出現一次」的條件，放寬成「至多出現一次」，則得到拉丁矩陣。利用圖論中有關二部圖匹配的霍爾婚配定理，可以證明任意 ${\displaystyle r\times n}$ 拉丁矩陣皆可擴展成 ${\displaystyle (r+1)\times n}$ 拉丁矩陣，並可如此重複，直至得到完整的拉丁方陣。^[5]

• 埃里克·韦斯坦因. Latin Square. MathWorld. 
• [1] （页面存档备份，存于互联网档案馆） Combinatorial Designs
• Latin Squares （页面存档备份，存于互联网档案馆） in the Encyclopaedia of Mathematics
• Latin Squares in Java （页面存档备份，存于互联网档案馆） at cut-the-knot
• Infinite Latin Square (Java) （页面存档备份，存于互联网档案馆） at cut-the-knot
• Magic Square in Latin Square

• 數獨
• 吠陀方形