Orthogonal Latin squares

A pair of Latin squares (cf. Latin square) $ A = \| a _ {ij} \| $, $ B = \| b _ {ij} \| $ of order $ n $ such that $ ( a _ {ij} , b _ {ij} ) \neq ( a _ {kl} , b _ {kl} ) $ if $ ( i, j) \neq ( k,l) $, $ i, j, k, l \in S = \{ 1 \dots n \} $. The squares $ A $ and $ B $ are called orthogonal mates. The matrix obtained by the superposition of $ A $ on $ B $ is called a Greco–Latin or Euler square; its elements are all the $ n ^ {2} $ ordered pairs of elements from $ S $. The orthogonality of $ A $ and $ B $ is denoted by $ A \perp B $. An example of a pair of orthogonal Latin squares and their Euler square for $ n = 3 $ is:

$$ \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \\ \end{array} \ \ \ \begin{array}{ccc} 1 & 2 & 3 \\ 3 & 1 & 2 \\ 2 & 3 & 1 \\ \end{array} \ \ \begin{array}{ccc} 11 &22 &33 \\ 23 &31 &12 \\ 32 &13 &21 \\ \end{array} $$

A Latin square $ A $ of order $ n $ has an orthogonal mate if and only if $ n $ non-intersecting transversals exist in $ A $ (see Latin square). If $ A $ is a Latin square of order $ 4t+ 2 $ (or $ 4t+ 1 $) with a subsquare of order $ 2t+ 1 $ (or $ 2t $) all cells of which, with the possible exception of $ t $ (or $ [( t- 1)/2] $) cells, are filled by not more than $ 2t+ 1 $ (or $ 2t $) elements, then no orthogonal mate exists for $ A $. For all $ n > 2 $, $ n \neq 6 $, there are examples of pairs of orthogonal Latin squares, while for $ n = 6 $, examination of all possibilities proves that there are no such pairs [3].

A number of Latin squares of the same order are called pairwise orthogonal or mutually orthogonal if any two of them are orthogonal. If $ N( n) $ is the maximum possible number of pairwise orthogonal Latin squares, then $ N( n) \leq n- 1 $.

A set of $ n- 1 $ pairwise orthogonal Latin squares of order $ n $ is called complete. When $ n > 4 $, a set of $ n- 3 $ pairwise orthogonal Latin squares can always be made complete. Up till now (1989), the only complete sets known are for $ n = p ^ {k} $, where $ k $ is a natural number and $ p $ is a prime number (i.e. $ N( p ^ {k} ) = p ^ {k} - 1 $). The following lower bounds have been obtained for $ N( n) $:

<tbody> </tbody> $ n \geq $ 7 52 53 63 90 $ N( n) \geq $ 2 3 4 5 6

Moreover, $ N( 12) \geq 5 $, $ N( 33) \geq 3 $, $ N( 35) \geq 4 $, $ N( 40) \geq 4 $, $ N( 45) \geq 4 $, and it has been proved that $ N( n) \rightarrow \infty $ as $ n \rightarrow \infty $; for example, $ N( n) > n ^ {1/17} - 2 $ for sufficiently large $ n $ (see [2]). If $ n \equiv 1 $ ($ \mathop{\rm mod} 4 $) or $ n \equiv 2 $ ($ \mathop{\rm mod} 4 $), and if the square-free part of the number $ n $ contains even one prime factor $ p \equiv 3 $ ($ \mathop{\rm mod} 4 $), then no complete set of pairwise orthogonal Latin squares of order $ n $ exists. For example, no complete sets exist for $ n = 2p $, $ p \equiv 3 $ ($ \mathop{\rm mod} 4 $).

Complete sets of pairwise orthogonal Latin squares have a statistical application in the creation of symmetric balanced incomplete block designs (cf. Block design) with parameters $ v = n ^ {2} + n + 1 $, $ k = n+ 1 $, $ \lambda = 1 $, since complete sets can also be interpreted as finite projective planes (see [2]).

Many methods for constructing orthogonal Latin squares have been proposed (see [2]). They all aim at obtaining the largest possible set of pairwise orthogonal Latin squares of order $ n $. Each method belongs to one of the following two groups. The first group (direct constructions) contains methods whose characteristic peculiarity is that they provide a method for constructing a "basic" Latin square and demonstrate how to interchange their rows and columns so as to obtain an orthogonal mate. The second group (recursive methods) contains methods which use known methods for constructing orthogonal Latin squares of lower order to construct orthogonal Latin squares of given order.

If $ A = \| a _ {ij} \| $ is a Latin square of order $ n $ on the set $ S $, then the ordered set of permutations $ \sigma _ {i} $, $ i \in S $, defined by the equations $ \sigma _ {i} ( j) = a _ {ij} $ uniquely determines $ A $. Not every ordered set of permutations corresponds to a Latin square. If $ A = [ \sigma _ {1} \dots \sigma _ {n} ] $ and $ B = [ \tau _ {1}, \dots, \tau _ {n} ] $ are two Latin squares defined in the above way by permutations $ \sigma _ {i} $ and $ \tau _ {i} $ of the set $ S $, then $ A \perp B $ if and only if $ [ \sigma _ {1} ^ {-1} \tau _ {1} \dots \sigma _ {n} ^ {-1} \tau _ {n} ] $ is a Latin square. If one defines products $ \alpha A = [ \alpha \sigma _ {1} \dots \alpha \sigma _ {n} ] $, $ A \beta = [ \sigma _ {1} \beta \dots \sigma _ {n} \beta ] $, where $ \alpha $ and $ \beta $ are permutations of $ S $, then, for example, $ A \perp \alpha A $ if and only if $ [ \sigma _ {1} ^ {-1} \alpha \sigma _ {1} \dots \sigma _ {n} ^ {-1} \alpha \sigma _ {n} ] $ is a Latin square.

The methods in the first group are usually used when $ A $ is the multiplication table of a finite group $ G $, i.e. $ a _ {ij} = g _ {i} g _ {j} $, $ g _ {i} , g _ {j} \in G $, $ i, j \in S $; the difference between one method and the other lies in the choice of the group $ G $, the choice of the one-to-one mappings $ \alpha , \beta $ of the group $ G $ onto itself, and the use of the products $ \alpha A $, $ A \beta $, $ \alpha ^ {-1} A \alpha $, etc.

If $ G $ is an additive group, then the condition $ A \perp \alpha A $ reduces to the fact that $ \alpha $ is an orthomorphism of $ G $, i.e. a one-to-one mapping of $ G $ onto itself such that if $ \alpha ( g _ {1} ) - g _ {1} = \alpha ( g _ {2} )- g _ {2} $ for $ g _ {1} , g _ {2} \in G $, then $ g _ {1} = g _ {2} $. For example, five pairwise orthogonal Latin squares of order 12 have been found after defining four non-trivial orthomorphisms of the Abelian group which is the direct product of the cyclic groups of order 6 and 2 (see [2], [6]).

If $ G $ is the additive group of a finite field $ \mathop{\rm GF} ( p ^ {r} ) = \{ a _ {0} = 0, a _ {1} = 1 , a _ {2} \dots a _ {n-} 1 \} $, $ n = p ^ {r} $, then all constructions are significantly simplified, and the following complete set of pairwise orthogonal Latin squares is obtained:

$$ A _ {k} = \| a _ {ij} ^ {k} \| ,\ \ a _ {ij} ^ {k} = a _ {i} a _ {k} + a _ {j} ; $$

$$ i, j \in \{ 0 \dots n- 1 \} ,\ \ k \in \{ 1 \dots n- 1 \} . $$

It may be noted that a Latin square $ A $ of order $ n $ such that $ A \perp A ^ {T} $ (i.e. a self-orthogonal Latin square) exists if and only if $ n \neq 2, 3, 6 $.

The use of the direct product of Latin squares forms the basis of the following method, related to the second group. Let $ A _ {1} $ and $ B _ {1} $ be orthogonal Latin squares of order $ n $ on a set $ X $, while $ A _ {2} $ and $ B _ {2} $ are orthogonal Latin squares of order $ m $ on a set $ Y $; the direct products of matrices $ A _ {1} \times A _ {2} $ and $ B _ {1} \times B _ {2} $ will then be orthogonal Latin squares of order $ mn $ on the set $ X \times Y $. If $ n = p _ {1} ^ {k _ {1} } \dots p _ {r} ^ {k _ {r} } $, then this method yields the bound $ N( n) \geq \min ( p _ {i} ^ {k _ {i} } - 1) $.

The following construction lies at the basis of many other methods of the second group. Let $ A _ {1} , B _ {1} , C _ {1} $ be pairwise orthogonal Latin squares of order $ M \geq 2n $ on the set $ S _ {1} = \{ 1 \dots m \} $ and let $ A _ {2} , B _ {2} $ be orthogonal Latin squares of order $ n $ on the set $ S _ {2} = \{ m+ 1 \dots m+ n \} $. In order to obtain two Latin squares $ A $ and $ B $ of order $ m+ n $ on the set $ S = S _ {1} \cup S _ {2} $, rows and columns with numbers $ m+ 1 \dots m+ n $ with unfilled cells are added to $ A _ {1} $, with the result that a partial Latin square of order $ m+ n $ containing $ A _ {1} $ in the top left corner is obtained. The cells of $ A _ {1} $ and $ B _ {1} $ having the same numbers as the cells of $ C _ {1} $ that contain the element $ i $ form a common $ i $-transversal, $ i = 1 \dots m $, for $ A _ {1} $ and $ B _ {1} $. The elements of the $ i $-transversal in $ A _ {1} $ when $ i = 1 \dots n $ are placed in the $ ( m+ i) $-th column (and in the $ ( m+ i) $-th row) in the same order in which they stood in the rows and columns of $ A _ {1} $, and the number $ m+ i $ is put in their place. It remains to insert $ A _ {2} $ in the bottom right corner of the partial square in order to complete $ A $.

$ B $ is constructed from $ B _ {1} $ and $ B _ {2} $ in the same way, but only by using transversals with the numbers $ n+ 1 \dots 2n $. The squares $ A $ and $ B $ will be Latin, but not necessarily orthogonal. A pair of orthogonal Latin squares of order $ m+ n $ can always be obtained if $ m = p ^ {k} \neq 13 $, $ p $ is odd and $ n = ( m- 1)/2 $; it has been shown, using the above construction, how to obtain a pair of orthogonal Latin squares of order $ n $ when $ n \equiv 2 $ ($ \mathop{\rm mod} 4 $), $ n > 6 $ (see [2]).

The applications of orthogonal Latin squares in statistics, information theory and in the theory of experimental design (cf. [2]) require the construction of special forms of orthogonal Latin squares and the transfer of the concept of orthogonality to other subjects. Thus, orthogonal arrays (cf. Orthogonal array) are a generalization of orthogonal Latin squares. Two partial Latin squares of the same order are orthogonal if when superposed on each other the ordered pairs in the cells are all different. A Latin square $ A $ is said to be imbedded in the Latin square $ B $ if $ A $ coincides with a submatrix of $ B $ (with the exception of the empty cells of $ A $). Each square in a set of pairwise orthogonal Latin squares can be imbedded in a Latin square in such a way that the Latin squares obtained will be orthogonal (see [6]).

References

[1]	V.N. Sachkov, "Combinatorial methods in discrete mathematics" , Moscow (1977) (In Russian)
[2]	J. Dénes, A.D. Keedwell, "Latin squares and their applications" , Acad. Press (1974)
[3]	M. Hall, "Combinatorial theory" , Wiley, reprint (1986)
[4]	H.J. Ryser, "Combinatorial mathematics" , Math. Assoc. Amer. (1963)
[5]	A. Hedayat, E. Seiden, "On the theory and application of sum composition of Latin squares and orthogonal Latin squares" Pacif. J. Math. , 54 : 2 (1974) pp. 85–113
[6]	Ch. Lindner, "Embedding orthogonal partial Latin squares" Proc. Amer. Math. Soc. , 59 : 1 (1976) pp. 184–186

Comments

For a complete proof of the fact that there are no pairs of orthogonal Latin squares for $ n = 6 $ see [a1]. Some more bounds for $ N( n) $ are as follows:

1) For the first few non-prime powers: $ N( 14) \geq 3 $, $ N( 15) \geq 4 $, $ N( 18) \geq 3 $, $ N( 20) \geq 4 $, $ N( 21) \geq 4 $, $ N( 22) \geq 3 $, $ N( 24) \geq 4 $. See [a1] or [a2]. These references contain a table of lower bounds on $ N( n) $ for $ N \leq 100 $.

2) In addition to the main article above one has

<tbody> </tbody> $ n \geq $ 11 77 781 65279 $ N( n) \geq $ 3 6 7 30

See [a1].

3) The best asymptotic bound today (1989) is $ N( n) \geq n ^ {1/14.8 } $ (see [a3]).

4) The Bruck–Ryser theorem states that there is no complete set of pairwise orthogonal Latin squares if $ n \equiv 1 $ ($ \mathop{\rm mod} 4 $) or $ n \equiv 2 $ ($ \mathop{\rm mod} 4 $) and if the square-free part of $ n $ contains a prime $ p \equiv 3 $ ($ \mathop{\rm mod} 4 $). In conjunction with Bruck's completion theorem, this non-existence result gives the only known non-trivial upper bounds on $ N( n) $, e.g. $ N( n) \leq n- 4 $ for $ n= 6, 14, 21, 22 $; $ N( n) \leq n- 5 $ for $ n= 30, 33, 38, 42, 46, 54, 57, 62, \dots $ (see [a1]).

A set of $ k $ mutually orthogonal Latin squares (MOLS) of order $ n $ is equivalent to a net of order $ n $ and degree $ k+ 2 $ (or, dually, a transversal design). This allows one to consider the study of MOLS as a part of finite geometry and to associate geometric invariants (like automorphism groups and groups of projectivities) with them. Cf. [a1] for fundamental results and [a2] for a recent survey.

The 4 known MOLS of order 15 also have been obtained by using orthomorphisms. The construction of MOLS by orthomorphisms of an additively written group $ G $ of order $ n $ can be more conveniently phrased by using "difference matrices" over $ G $: Let $ D $ be a matrix with $ k $ rows and $ n $ columns with entries from $ G $. $ D $ is called a difference matrix if the $ n $ differences $ d _ {ij} - d _ {hj} $ contain each element of $ G $ exactly once (for all choices of rows $ h $ and $ i $ of $ D $). $ D $ can be used to construct $ k- 1 $ MOLS of order $ n $. Most direct constructions are more sophisticated versions of this approach (cf. [a1] and [a2]), and are therefore also called "difference methods" .

The most important recursive constructions are much more involved and use the geometric interpretation of MOLS as transversal designs, see [3] and [a1].

For the existence of self-orthogonal Latin squares see [a1]. For applications of orthogonal Latin squares see also [a4].

References

[a1]	T. Beth, D. Jungnickel, H. Lenz, "Design theory" , Cambridge Univ. Press (1986)
[a2]	D. Jungnickel, "Latin squares, their geometries and their groups. A survey" , Proc. IMA Workshops on Coding and Design Theory Minneapolis, 1988 , Springer (to appear)
[a3]	T. Beth, "Eine Bemerkung zur Abschätzung der Anzahl orthogonaler lateinischer Quadrate mittels Siebverfahren" Abh. Math. Sem. Hamburg , 53 (1983) pp. 284–288
[a4]	A.S. Hedayat, J. Stufken, "Orthogonal arrays and their applications" (To appear)