A set of Latin squares of the same order such that every pair of squares are orthogonal (that is, form a Graeco-Latin square) is called a set of
mutually orthogonal Latin squares (or
pairwise orthogonal Latin squares) and usually abbreviated as
MOLS or '
MOLS(n
)' when the order is made explicit. For example, a set of MOLS(4) is given by: :\begin{matrix} 1&2&3&4 \\ 2&1&4&3\\ 3&4&1&2\\4&3&2&1 \end{matrix}\qquad\qquad \begin{matrix} 1&2&3&4 \\ 4&3&2&1 \\2&1&4&3 \\3&4&1&2 \end{matrix}\qquad\qquad\begin{matrix}1&2&3&4 \\3&4&1&2\\4&3&2&1\\2&1&4&3\end{matrix}. And a set of MOLS(5): :\begin{matrix}1&2&3&4&5 \\2&3&4&5&1\\3&4&5&1&2\\4&5&1&2&3\\5&1&2&3&4\end{matrix} \qquad\begin{matrix}1&2&3&4&5\\3&4&5&1&2\\5&1&2&3&4\\2&3&4&5&1\\4&5&1&2&3\end{matrix} \qquad\begin{matrix}1&2&3&4&5\\5&1&2&3&4\\4&5&1&2&3\\3&4&5&1&2\\2&3&4&5&1\end{matrix} \qquad\begin{matrix}1&2&3&4&5\\4&5&1&2&3\\2&3&4&5&1\\5&1&2&3&4\\3&4&5&1&2\end{matrix}. While it is possible to represent MOLS in a "compound" matrix form similar to the Graeco-Latin squares, for instance, : for the MOLS(5) example above, it is more typical to compactly represent the MOLS as an orthogonal array (see
below). In the examples of MOLS given so far, the same alphabet (symbol set) has been used for each square, but this is not necessary as the Graeco-Latin squares show. In fact, totally different symbol sets can be used for each square of the set of MOLS. For example, is a representation of the compounded MOLS(5) example above where the four MOLS have the following alphabets, respectively: • the background color:
black,
maroon,
teal,
navy, and
silver • the foreground color:
white,
red,
lime,
blue, and
yellow • the text:
fjords,
jawbox,
phlegm,
qiviut, and
zincky • the typeface family:
serif,
sans-serif,
monospaced,
cursive, and
slab-serif. The above table therefore allows for testing five values in each of four different dimensions in only 25 observations instead of 625 (= 54) observations required in a
full factorial design. Since the five words cover all 26 letters of the alphabet between them, the table allows for examining each letter of the alphabet in five different typefaces and color combinations.
The number of mutually orthogonal Latin squares The mutual orthogonality property of a set of MOLS is unaffected by • Permuting the rows of all the squares simultaneously, • Permuting the columns of all the squares simultaneously, and • Permuting the entries in any square, independently. Using these operations, any set of MOLS can be put into
standard form, meaning that the first row of every square is identical and normally put in some natural order, and one square has its first column also in this order. The MOLS(4) and MOLS(5) examples at the start of this section have been put in standard form. By putting a set of MOLS() in standard form and examining the entries in the second row and first column of each square, it can be seen that no more than squares can exist. A set of − 1 MOLS() is called a
complete set of MOLS. Complete sets are known to exist when is a
prime number or
power of a prime (see
Finite field construction below). However, the number of MOLS that may exist for a given order is not known for general , and is an area of research in
combinatorics.
Projective planes A set of − 1 MOLS() is equivalent to a finite
affine plane of order (see
Nets below). As every finite affine plane is uniquely extendable to a
finite projective plane of the same order, this equivalence can also be expressed in terms of the existence of these projective planes. As mentioned above, complete sets of MOLS() exist if is a prime or prime power, so projective planes of such orders exist. Finite projective planes with an order different from these, and thus complete sets of MOLS of such orders, are not known to exist. This rules out projective planes of orders 6 and 14 for instance, but does not guarantee the existence of a plane when satisfies the condition. In particular, = 10 satisfies the conditions, but no projective plane of order 10 exists, as was shown by a very long computer search, ''MacNeish's Theorem'': If n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r} is the factorization of the integer into powers of distinct primes p_1,p_2,\cdots,p_r then ::{{nowrap|the minimum number of MOLS() \ge \underset{i}{\operatorname{min}} \{p_i^{\alpha_i} - 1 \}.}} MacNeish's theorem does not give a very good lower bound, for instance if ≡ 2 (mod 4), that is, there is a single 2 in the prime factorization, the theorem gives a lower bound of 1, which is beaten if > 6. On the other hand, it does give the correct value when is a power of a prime. For general composite numbers, the number of MOLS is not known. The first few values starting with = 2, 3, 4... are 1, 2, 3, 4, 1, 6, 7, 8, ... . The smallest case for which the exact number of MOLS() is not known is = 10. From the Graeco-Latin square construction, there must be at least two and from the non-existence of a projective plane of order 10, there are fewer than nine. However, no set of three MOLS(10) has ever been found even though many researchers have attempted to discover such a set. For large enough , the number of MOLS is greater than \sqrt[14.8]{n}, thus for every , there are only a finite number of such that the number of MOLS is . Moreover, the minimum is 6 for all > 90.
Finite field construction A complete set of MOLS() exists whenever is a prime or prime power. This follows from a construction that is based on a
finite field GF(), which only exist if is a prime or prime power. The multiplicative group of
GF() is a
cyclic group, and so, has a generator, λ, meaning that all the non-zero elements of the field can be expressed as distinct powers of λ. Name the elements of
GF() as follows: ::α0 = 0, α1 = 1, α2 = λ, α3 = λ2, ..., α-1 = λ-2. Now, λ-1 = 1 and the product rule in terms of the α's is αα = α, where = + -1 (mod -1). The Latin squares are constructed as follows, the ()th entry in Latin square L (with ≠ 0) is L() = α + αα, where all the operations occur in
GF(). In the case that the field is a prime field ( = a prime), where the field elements are represented in the usual way, as the
integers modulo, the naming convention above can be dropped and the construction rule can be simplified to L() = + , where ≠ 0 and , and are elements of
GF() and all operations are in
GF(). The MOLS(4) and MOLS(5) examples above arose from this construction, although with a change of alphabet. Not all complete sets of MOLS arise from this construction. The projective plane that is associated with the complete set of MOLS obtained from this field construction is a special type, a
Desarguesian projective plane. There exist
non-Desarguesian projective planes and their corresponding complete sets of MOLS can not be obtained from finite fields.
Orthogonal array An
orthogonal array, OA(), of strength two and index one is an array ( ≥ 2 and ≥ 1, integers) with entries from a set of size such that within any two columns of (
strength), every ordered pair of symbols appears in exactly one row of (
index). An OA( + 2, ) is equivalent to MOLS(). An ( + 1, )-net is an affine plane of order . A set of MOLS() is equivalent to a ( + 2, )-net. For example, the OA(5,4) in the above section can be used to construct a (5,4)-net (an affine plane of order 4). The points on each line are given by (each row below is a parallel class of lines): :
Transversal designs A
transversal design with groups of size and index λ, denoted T[, λ; ], is a triple () where: • is a set of varieties; • {{math|1=
G = {
G1,
G2, ...,
Gk}}} is a family of -sets (called
groups, but not in the algebraic sense) which form a partition of ; • is a family of -sets (called
blocks) of varieties such that each -set in intersects each group in precisely one variety, and any pair of varieties which belong to different groups occur together in precisely λ blocks in . The existence of a T[,1;] design is equivalent to the existence of -2 MOLS(). A transversal design T[,1;] is the
dual incidence structure of an ()-net. That is, it has points and 2 blocks. Each point is in blocks; each block contains points. The points fall into equivalence classes (groups) of size so that two points in the same group are not contained in a block while two points in different groups belong to exactly one block. For example, using the (5,4)-net of the previous section we can construct a T[5,1;4] transversal design. The block associated with the point () of the net will be denoted
ij. The points of the design will be obtained from the following scheme:
i ↔ ,
j ↔ 5, and
ij ↔ 5 + . The points of the design are thus denoted by the integers 1, ..., 20. The blocks of the design are: : The five "groups" are: :
Graph theory A set of MOLS() is equivalent to an edge-partition of the
complete ( + 2)-partite graph K
n,...,
n into
complete subgraphs of order + 2. ==Applications==