Namespaces
Variants
Actions

Difference between revisions of "Orthogonal Latin squares"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (fixing spaces)
 
(3 intermediate revisions by one other user not shown)
Line 1: Line 1:
A pair of Latin squares (cf. [[Latin square|Latin square]]) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o0703101.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o0703102.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o0703103.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o0703104.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o0703105.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o0703106.png" />. The squares <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o0703107.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o0703108.png" /> are called orthogonal mates. The matrix obtained by the superposition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o0703109.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031010.png" /> is called a Greco–Latin or Euler square; its elements are all the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031011.png" /> ordered pairs of elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031012.png" />. The orthogonality of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031013.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031014.png" /> is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031015.png" />. An example of a pair of orthogonal Latin squares and their Euler square for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031016.png" /> is:
+
<!--
 +
o0703101.png
 +
$#A+1 = 231 n = 0
 +
$#C+1 = 231 : ~/encyclopedia/old_files/data/O070/O.0700310 Orthogonal Latin squares
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031017.png" /></td> </tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
A Latin square <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031018.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031019.png" /> has an orthogonal mate if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031020.png" /> non-intersecting transversals exist in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031021.png" /> (see [[Latin square|Latin square]]). If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031022.png" /> is a Latin square of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031023.png" /> (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031024.png" />) with a subsquare of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031025.png" /> (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031026.png" />) all cells of which, with the possible exception of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031027.png" /> (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031028.png" />) cells, are filled by not more than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031029.png" /> (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031030.png" />) elements, then no orthogonal mate exists for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031031.png" />. For all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031032.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031033.png" />, there are examples of pairs of orthogonal Latin squares, while for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031034.png" />, examination of all possibilities proves that there are no such pairs [[#References|[3]]].
+
A pair of Latin squares (cf. [[Latin square|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:
  
A number of Latin squares of the same order are called pairwise orthogonal or mutually orthogonal if any two of them are orthogonal. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031035.png" /> is the maximum possible number of pairwise orthogonal Latin squares, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031036.png" />.
+
$$
  
A set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031037.png" /> pairwise orthogonal Latin squares of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031038.png" /> is called complete. When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031039.png" />, a set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031040.png" /> pairwise orthogonal Latin squares can always be made complete. Up till now (1989), the only complete sets known are for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031041.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031042.png" /> is a natural number and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031043.png" /> is a prime number (i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031044.png" />). The following lower bounds have been obtained for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031045.png" />:
+
\begin{array}{ccc}
 +
1  & 2  & 3  \\
 +
2  & 3  & 1  \\
 +
3  & 1  & 2  \\
 +
\end{array}
 +
\  \ \
  
<table border="0" cellpadding="0" cellspacing="0" style="background-color:black;"> <tr><td> <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;"> <tbody> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031046.png" /></td> <td colname="2" style="background-color:white;" colspan="1">7</td> <td colname="3" style="background-color:white;" colspan="1">52</td> <td colname="4" style="background-color:white;" colspan="1">53</td> <td colname="5" style="background-color:white;" colspan="1">63</td> <td colname="6" style="background-color:white;" colspan="1">90</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031047.png" /></td> <td colname="2" style="background-color:white;" colspan="1">2</td> <td colname="3" style="background-color:white;" colspan="1">3</td> <td colname="4" style="background-color:white;" colspan="1">4</td> <td colname="5" style="background-color:white;" colspan="1">5</td> <td colname="6" style="background-color:white;" colspan="1">6</td> </tr> </tbody> </table>
+
\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|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 [[#References|[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) $:
 +
 
 +
<table border="0" cellpadding="0" cellspacing="0" style="background-color:black;"> <tr><td> <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;"> <tbody> <tr> <td colname="1" style="background-color:white;" colspan="1"> $  n \geq  $
 +
</td> <td colname="2" style="background-color:white;" colspan="1">7</td> <td colname="3" style="background-color:white;" colspan="1">52</td> <td colname="4" style="background-color:white;" colspan="1">53</td> <td colname="5" style="background-color:white;" colspan="1">63</td> <td colname="6" style="background-color:white;" colspan="1">90</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"> $  N( n) \geq  $
 +
</td> <td colname="2" style="background-color:white;" colspan="1">2</td> <td colname="3" style="background-color:white;" colspan="1">3</td> <td colname="4" style="background-color:white;" colspan="1">4</td> <td colname="5" style="background-color:white;" colspan="1">5</td> <td colname="6" style="background-color:white;" colspan="1">6</td> </tr> </tbody> </table>
  
 
</td></tr> </table>
 
</td></tr> </table>
  
Moreover, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031048.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031049.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031050.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031051.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031052.png" />, and it has been proved that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031053.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031054.png" />; for example, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031055.png" /> for sufficiently large <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031056.png" /> (see [[#References|[2]]]). If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031057.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031058.png" />) or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031059.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031060.png" />), and if the square-free part of the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031061.png" /> contains even one prime factor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031062.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031063.png" />), then no complete set of pairwise orthogonal Latin squares of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031064.png" /> exists. For example, no complete sets exist for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031065.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031066.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031067.png" />).
+
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 [[#References|[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|Block design]]) with parameters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031068.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031069.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031070.png" />, since complete sets can also be interpreted as finite projective planes (see [[#References|[2]]]).
+
Complete sets of pairwise orthogonal Latin squares have a statistical application in the creation of symmetric balanced incomplete block designs (cf. [[Block design|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 [[#References|[2]]]).
  
Many methods for constructing orthogonal Latin squares have been proposed (see [[#References|[2]]]). They all aim at obtaining the largest possible set of pairwise orthogonal Latin squares of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031071.png" />. 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.
+
Many methods for constructing orthogonal Latin squares have been proposed (see [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031072.png" /> is a Latin square of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031073.png" /> on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031074.png" />, then the ordered set of permutations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031075.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031076.png" />, defined by the equations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031077.png" /> uniquely determines <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031078.png" />. Not every ordered set of permutations corresponds to a Latin square. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031079.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031080.png" /> are two Latin squares defined in the above way by permutations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031081.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031082.png" /> of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031083.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031084.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031085.png" /> is a Latin square. If one defines products <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031086.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031087.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031088.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031089.png" /> are permutations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031090.png" />, then, for example, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031091.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031092.png" /> is a Latin square.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031093.png" /> is the multiplication table of a finite group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031094.png" />, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031095.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031096.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031097.png" />; the difference between one method and the other lies in the choice of the group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031098.png" />, the choice of the one-to-one mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o07031099.png" /> of the group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310100.png" /> onto itself, and the use of the products <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310101.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310102.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310103.png" />, etc.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310104.png" /> is an additive group, then the condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310105.png" /> reduces to the fact that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310106.png" /> is an orthomorphism of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310107.png" />, i.e. a one-to-one mapping of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310108.png" /> onto itself such that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310109.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310110.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310111.png" />. 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 [[#References|[2]]], [[#References|[6]]]).
+
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 [[#References|[2]]], [[#References|[6]]]).
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310112.png" /> is the additive group of a finite field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310113.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310114.png" />, then all constructions are significantly simplified, and the following complete set of pairwise orthogonal Latin squares is obtained:
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310115.png" /></td> </tr></table>
+
$$
 +
A _ {k}  = \| a _ {ij}  ^ {k} \| ,\ \
 +
a _ {ij}  ^ {k}  = a _ {i} a _ {k} + a _ {j} ;
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310116.png" /></td> </tr></table>
+
$$
 +
i, j  \in  \{ 0 \dots n- 1 \} ,\ \
 +
k  \in  \{ 1 \dots n- 1 \} .
 +
$$
  
It may be noted that a Latin square <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310117.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310118.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310119.png" /> (i.e. a self-orthogonal Latin square) exists if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310120.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310121.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310122.png" /> be orthogonal Latin squares of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310123.png" /> on a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310124.png" />, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310125.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310126.png" /> are orthogonal Latin squares of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310127.png" /> on a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310128.png" />; the direct products of matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310129.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310130.png" /> will then be orthogonal Latin squares of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310131.png" /> on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310132.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310133.png" />, then this method yields the bound <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310134.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310135.png" /> be pairwise orthogonal Latin squares of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310136.png" /> on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310137.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310138.png" /> be orthogonal Latin squares of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310139.png" /> on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310140.png" />. In order to obtain two Latin squares <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310141.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310142.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310143.png" /> on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310144.png" />, rows and columns with numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310145.png" /> with unfilled cells are added to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310146.png" />, with the result that a partial Latin square of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310147.png" /> containing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310148.png" /> in the top left corner is obtained. The cells of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310149.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310150.png" /> having the same numbers as the cells of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310151.png" /> that contain the element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310152.png" /> form a common <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310153.png" />-transversal, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310154.png" />, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310155.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310156.png" />. The elements of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310157.png" />-transversal in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310158.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310159.png" /> are placed in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310160.png" />-th column (and in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310161.png" />-th row) in the same order in which they stood in the rows and columns of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310162.png" />, and the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310163.png" /> is put in their place. It remains to insert <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310164.png" /> in the bottom right corner of the partial square in order to complete <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310165.png" />.
+
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 $.
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310166.png" /> is constructed from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310167.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310168.png" /> in the same way, but only by using transversals with the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310169.png" />. The squares <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310170.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310171.png" /> will be Latin, but not necessarily orthogonal. A pair of orthogonal Latin squares of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310172.png" /> can always be obtained if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310173.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310174.png" /> is odd and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310175.png" />; it has been shown, using the above construction, how to obtain a pair of orthogonal Latin squares of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310176.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310177.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310178.png" />), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310179.png" /> (see [[#References|[2]]]).
+
$  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 [[#References|[2]]]).
  
The applications of orthogonal Latin squares in statistics, information theory and in the theory of experimental design (cf. [[#References|[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|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310180.png" /> is said to be imbedded in the Latin square <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310181.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310182.png" /> coincides with a submatrix of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310183.png" /> (with the exception of the empty cells of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310184.png" />). 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 [[#References|[6]]]).
+
The applications of orthogonal Latin squares in statistics, information theory and in the theory of experimental design (cf. [[#References|[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|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 [[#References|[6]]]).
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  V.N. Sachkov,  "Combinatorial methods in discrete mathematics" , Moscow  (1977)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  J. Dénes,  A.D. Keedwell,  "Latin squares and their applications" , Acad. Press  (1974)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  M. Hall,  "Combinatorial theory" , Wiley, reprint  (1986)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  H.J. Ryser,  "Combinatorial mathematics" , Math. Assoc. Amer.  (1963)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  Ch. Lindner,  "Embedding orthogonal partial Latin squares"  ''Proc. Amer. Math. Soc.'' , '''59''' :  1  (1976)  pp. 184–186</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  V.N. Sachkov,  "Combinatorial methods in discrete mathematics" , Moscow  (1977)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  J. Dénes,  A.D. Keedwell,  "Latin squares and their applications" , Acad. Press  (1974)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  M. Hall,  "Combinatorial theory" , Wiley, reprint  (1986)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  H.J. Ryser,  "Combinatorial mathematics" , Math. Assoc. Amer.  (1963)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  Ch. Lindner,  "Embedding orthogonal partial Latin squares"  ''Proc. Amer. Math. Soc.'' , '''59''' :  1  (1976)  pp. 184–186</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
For a complete proof of the fact that there are no pairs of orthogonal Latin squares for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310185.png" /> see [[#References|[a1]]]. Some more bounds for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310186.png" /> are as follows:
+
For a complete proof of the fact that there are no pairs of orthogonal Latin squares for $  n = 6 $
 +
see [[#References|[a1]]]. Some more bounds for $  N( n) $
 +
are as follows:
  
1) For the first few non-prime powers: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310187.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310188.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310189.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310190.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310191.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310192.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310193.png" />. See [[#References|[a1]]] or [[#References|[a2]]]. These references contain a table of lower bounds on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310194.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310195.png" />.
+
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 [[#References|[a1]]] or [[#References|[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
 
2) In addition to the main article above one has
  
<table border="0" cellpadding="0" cellspacing="0" style="background-color:black;"> <tr><td> <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;"> <tbody> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310196.png" /></td> <td colname="2" style="background-color:white;" colspan="1">11</td> <td colname="3" style="background-color:white;" colspan="1">77</td> <td colname="4" style="background-color:white;" colspan="1">781</td> <td colname="5" style="background-color:white;" colspan="1">65279</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310197.png" /></td> <td colname="2" style="background-color:white;" colspan="1">3</td> <td colname="3" style="background-color:white;" colspan="1">6</td> <td colname="4" style="background-color:white;" colspan="1">7</td> <td colname="5" style="background-color:white;" colspan="1">30</td> </tr> </tbody> </table>
+
<table border="0" cellpadding="0" cellspacing="0" style="background-color:black;"> <tr><td> <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;"> <tbody> <tr> <td colname="1" style="background-color:white;" colspan="1"> $  n \geq  $
 +
</td> <td colname="2" style="background-color:white;" colspan="1">11</td> <td colname="3" style="background-color:white;" colspan="1">77</td> <td colname="4" style="background-color:white;" colspan="1">781</td> <td colname="5" style="background-color:white;" colspan="1">65279</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"> $  N( n) \geq  $
 +
</td> <td colname="2" style="background-color:white;" colspan="1">3</td> <td colname="3" style="background-color:white;" colspan="1">6</td> <td colname="4" style="background-color:white;" colspan="1">7</td> <td colname="5" style="background-color:white;" colspan="1">30</td> </tr> </tbody> </table>
  
 
</td></tr> </table>
 
</td></tr> </table>
Line 59: Line 266:
 
See [[#References|[a1]]].
 
See [[#References|[a1]]].
  
3) The best asymptotic bound today (1989) is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310198.png" /> (see [[#References|[a3]]]).
+
3) The best asymptotic bound today (1989) is $  N( n) \geq  n ^ {1/14.8 } $ (see [[#References|[a3]]]).
  
4) The Bruck–Ryser theorem states that there is no complete set of pairwise orthogonal Latin squares if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310199.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310200.png" />) or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310201.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310202.png" />) and if the square-free part of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310203.png" /> contains a prime <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310204.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310205.png" />). In conjunction with Bruck's completion theorem, this non-existence result gives the only known non-trivial upper bounds on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310206.png" />, e.g. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310207.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310208.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310209.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310210.png" /> (see [[#References|[a1]]]).
+
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 [[#References|[a1]]]).
  
A set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310211.png" /> mutually orthogonal Latin squares (MOLS) of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310212.png" /> is equivalent to a net of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310213.png" /> and degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310214.png" /> (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. [[#References|[a1]]] for fundamental results and [[#References|[a2]]] for a recent survey.
+
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. [[#References|[a1]]] for fundamental results and [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310215.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310216.png" /> can be more conveniently phrased by using  "difference matrices"  over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310217.png" />: Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310218.png" /> be a matrix with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310219.png" /> rows and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310220.png" /> columns with entries from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310221.png" />. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310222.png" /> is called a difference matrix if the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310223.png" /> differences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310224.png" /> contain each element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310225.png" /> exactly once (for all choices of rows <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310226.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310227.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310228.png" />). <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310229.png" /> can be used to construct <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310230.png" /> MOLS of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070310/o070310231.png" />. Most direct constructions are more sophisticated versions of this approach (cf. [[#References|[a1]]] and [[#References|[a2]]]), and are therefore also called  "difference methods" .
+
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. [[#References|[a1]]] and [[#References|[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 [[#References|[3]]] and [[#References|[a1]]].
 
The most important recursive constructions are much more involved and use the geometric interpretation of MOLS as transversal designs, see [[#References|[3]]] and [[#References|[a1]]].
Line 73: Line 308:
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  T. Beth,  D. Jungnickel,  H. Lenz,  "Design theory" , Cambridge Univ. Press  (1986)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  D. Jungnickel,  "Latin squares, their geometries and their groups. A survey" , ''Proc. IMA Workshops on Coding and Design Theory Minneapolis, 1988'' , Springer  (to appear)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  T. Beth,  "Eine Bemerkung zur Abschätzung der Anzahl orthogonaler lateinischer Quadrate mittels Siebverfahren"  ''Abh. Math. Sem. Hamburg'' , '''53'''  (1983)  pp. 284–288</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A.S. Hedayat,  J. Stufken,  "Orthogonal arrays and their applications"  (To appear)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  T. Beth,  D. Jungnickel,  H. Lenz,  "Design theory" , Cambridge Univ. Press  (1986)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  D. Jungnickel,  "Latin squares, their geometries and their groups. A survey" , ''Proc. IMA Workshops on Coding and Design Theory Minneapolis, 1988'' , Springer  (to appear)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  T. Beth,  "Eine Bemerkung zur Abschätzung der Anzahl orthogonaler lateinischer Quadrate mittels Siebverfahren"  ''Abh. Math. Sem. Hamburg'' , '''53'''  (1983)  pp. 284–288</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A.S. Hedayat,  J. Stufken,  "Orthogonal arrays and their applications"  (To appear)</TD></TR></table>
 
  
 
[[Category:Combinatorics]]
 
[[Category:Combinatorics]]

Latest revision as of 12:08, 21 March 2022


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)
How to Cite This Entry:
Orthogonal Latin squares. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Orthogonal_Latin_squares&oldid=34195
This article was adapted from an original article by V.M. Mikheev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article