orthogonal Latin squares

Given two Latin squares $L_{1}=(A,B,C_{1},f_{1})$ and $L_{2}=(A,B,C_{2},f_{2})$ of the same order $n$ , we can combine them coordinate-wise to form a single square, whose cells are ordered pairs of elements from $C_{1}$ and $C_{2}$ respectively. Formally, we can form a function $f:A\times B\to C_{1}\times C_{2}$ given by

$f(i,j)=(f_{1}(i,j),f_{2}(i,j)).$

This function $f$ says that we have created a new square $A\times B$ , whose cell $(i,j)$ contains the ordered pair of values, the first coordinate of which corresponds to the value in cell $(i,j)$ of $L_{1}$ , and the second to the value in cell $(i,j)$ of $L_{2}$ . We may write the combined square $L_{1}*L_{2}$ .

For example,

$\left(\begin{array}[]{cccc}a&b&c&d\\ c&d&a&b\\ d&c&b&a\\ b&a&d&c\end{array}\right)*\left(\begin{array}[]{cccc}1&2&3&4\\ 4&3&2&1\\ 2&1&4&3\\ 3&4&1&2\end{array}\right)=\left(\begin{array}[]{cccc}(a,1)&(b,2)&(c,3)&(d,4)\\ (c,4)&(d,3)&(a,2)&(b,1)\\ (d,2)&(c,1)&(b,4)&(a,3)\\ (b,3)&(a,4)&(d,1)&(c,2)\end{array}\right)$

In general, the combined square is not a Latin square unless the original two squares are equivalent: $f_{1}(i,j)=f_{1}(k,\ell)$ iff $f_{2}(i,j)=f_{2}(k,\ell)$ . Nevertheless, the more interesting aspect of pairing up two Latin squares (of the same order) lies in the function $f$ :

Definition. We say that two Latin squares are orthogonal if $f$ is a bijection.

Since there are $n^{2}$ cells in the combined square, and $|C_{1}\times C_{2}|=n^{2}$ , the function $f$ is a bijection if it is either one-to-one or onto. It is therefore easy to see that the two Latin squares in the example above are orthogonal.

Remarks.

•

The combined square is usually known as a Graeco-Latin square, originated from statisticians Fischer and Yates.
•

It can be shown that if $L_{1},\ldots,L_{m}$ are Latin squares of order $n\geq 3$ such that each pair of them are orthogonal, then $m\leq n-1$ . If the equality occurs, then the set of Latin squares are said to be complete.
•

(Bose) If $n\geq 3$ , then $L_{1},\ldots,L_{m}$ form a complete set of pairwise orthogonal Latin squares of order $n$ iff there exists a finite projective plane of order $n$ .

References

1 H. J. Ryser, Combinatorial Mathematics, The Carus Mathematical Monographs, 1963

Title	orthogonal Latin squares
Canonical name	OrthogonalLatinSquares
Date of creation	2013-03-22 16:04:47
Last modified on	2013-03-22 16:04:47
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	12
Author	CWoo (3771)
Entry type	Definition
Classification	msc 62K10
Classification	msc 05B15
Synonym	mutually orthogonal Latin squares
Synonym	MOLS
Synonym	pairwise orthogonal Latin squares
Defines	complete set of Latin squares