Namespaces
Variants
Actions

Difference between revisions of "Latin square"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(→‎References: + ZBL link)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
A square matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l0576201.png" /> in which each row and each column are permutations of the elements of a finite set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l0576202.png" /> consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l0576203.png" /> elements. The Latin square is said to be constructed on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l0576204.png" />; usually <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l0576205.png" />. A Latin square exists for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l0576206.png" />; for example, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l0576207.png" />, where
+
<!--
 +
l0576201.png
 +
$#A+1 = 110 n = 0
 +
$#C+1 = 110 : ~/encyclopedia/old_files/data/L057/L.0507620 Latin square
 +
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/l/l057/l057620/l0576208.png" /></td> </tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
 +
A square matrix of order  $  n $
 +
in which each row and each column are permutations of the elements of a finite set  $  S $
 +
consisting of  $  n $
 +
elements. The Latin square is said to be constructed on the set  $  S $;
 +
usually  $  S = \{ 1 \dots n \} $.
 +
A Latin square exists for any  $  n $;  
 +
for example,  $  A = \| a _ {ij} \| $,
 +
where
 +
 
 +
$$
 +
a _ {ij}  \equiv  i + j - 1  (  \mathop{\rm mod}  n ) ,\ \
 +
i , j = 1 \dots n ,
 +
$$
  
 
is a Latin square.
 
is a Latin square.
  
Every Latin square can be regarded as the multiplication table of a [[Quasi-group|quasi-group]]; the converse is also true: the multiplication table of a finite quasi-group is a Latin square. For a Latin square <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l0576209.png" /> to be the [[Cayley table|Cayley table]] of a group it is necessary and sufficient that the following condition (the square criterion) is satisfied: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762010.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762011.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762012.png" /> then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762013.png" />.
+
Every Latin square can be regarded as the multiplication table of a [[Quasi-group|quasi-group]]; the converse is also true: the multiplication table of a finite quasi-group is a Latin square. For a Latin square $  A = \| a _ {ij} \| $
 +
to be the [[Cayley table|Cayley table]] of a group it is necessary and sufficient that the following condition (the square criterion) is satisfied: If $  a _ {ik} = a _ {i _ {1}  k _ {1} } $,
 +
$  a _ {il} = a _ {i _ {1}  l _ {1} } $,  
 +
$  a _ {jk} = a _ {j _ {1}  k _ {1} } , $
 +
then $  a _ {jl} = a _ {j _ {1}  l _ {1} } $.
  
From two Latin squares, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762014.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762015.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762016.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762017.png" />, one can always construct a Latin square <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762018.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762019.png" />, for example as follows:
+
From two Latin squares, $  A = \| a _ {kl} \| $
 +
of order $  n $
 +
and $  B = \| b _ {rs} \| $
 +
of order $  m $,  
 +
one can always construct a Latin square $  C = \| c _ {ij} \| $
 +
of order $  mn $,  
 +
for example as follows:
  
<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/l/l057/l057620/l05762020.png" /></td> </tr></table>
+
$$
 +
c _ {ij}  = b _ {rs} + ( a _ {kl} - 1 ) m ,\ \
 +
= r + m ( k - 1 ) ,\ \
 +
= s + m ( l - 1 ) .
 +
$$
  
For the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762021.png" /> of Latin squares of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762022.png" /> one has the following lower bound:
+
For the number $  L _ {n} $
 +
of Latin squares of order $  n $
 +
one has the following lower bound:
  
<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/l/l057/l057620/l05762023.png" /></td> </tr></table>
+
$$
 +
L _ {n}  \geq  n ! ( n - 1 ) ! \dots 1 ! .
 +
$$
  
A Latin square is said to be reduced (or a Latin square of standard form) if the elements of its first row and first column are in the natural order. For the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762024.png" /> of reduced Latin squares of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762025.png" /> one has
+
A Latin square is said to be reduced (or a Latin square of standard form) if the elements of its first row and first column are in the natural order. For the number l _ {n} $
 +
of reduced Latin squares of order $  n $
 +
one has
  
<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/l/l057/l057620/l05762026.png" /></td> </tr></table>
+
$$
 +
L _ {n}  = n ! ( n - 1 ) ! l _ {n} ,\ \
 +
l _ {n}  \geq  m _ {n}  = ( n - 2 ) ! ( n - 3 ) ! \dots 1 !
 +
$$
  
Two Latin squares constructed on the same set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762027.png" /> are said to be equivalent or isotopic if one of them can be obtained from the other by a permutation of rows and columns and renaming of elements. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762028.png" /> be the number of equivalence classes of Latin squares of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762029.png" />. The following first few values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762030.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762031.png" /> are known:''''''<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/l/l057/l057620/l05762032.png" /></td> <td colname="2" style="background-color:white;" colspan="1">3</td> <td colname="3" style="background-color:white;" colspan="1">4</td> <td colname="4" style="background-color:white;" colspan="1">5</td> <td colname="5" style="background-color:white;" colspan="1">6</td> <td colname="6" style="background-color:white;" colspan="1">7</td> <td colname="7" style="background-color:white;" colspan="1">8</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762033.png" /></td> <td colname="2" style="background-color:white;" colspan="1">1</td> <td colname="3" style="background-color:white;" colspan="1">2</td> <td colname="4" style="background-color:white;" colspan="1">2</td> <td colname="5" style="background-color:white;" colspan="1">22</td> <td colname="6" style="background-color:white;" colspan="1">563</td> <td colname="7" style="background-color:white;" colspan="1">1 676 257</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762034.png" /></td> <td colname="2" style="background-color:white;" colspan="1">1</td> <td colname="3" style="background-color:white;" colspan="1">4</td> <td colname="4" style="background-color:white;" colspan="1">56</td> <td colname="5" style="background-color:white;" colspan="1">9408</td> <td colname="6" style="background-color:white;" colspan="1">16 942 080</td> <td colname="7" style="background-color:white;" colspan="1">535 281 401 856</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762035.png" /></td> <td colname="2" style="background-color:white;" colspan="1">1</td> <td colname="3" style="background-color:white;" colspan="1">2</td> <td colname="4" style="background-color:white;" colspan="1">12</td> <td colname="5" style="background-color:white;" colspan="1">288</td> <td colname="6" style="background-color:white;" colspan="1">34 560</td> <td colname="7" style="background-color:white;" colspan="1">24 883 200</td> </tr> </tbody> </table>
+
Two Latin squares constructed on the same set $  S $
 +
are said to be equivalent or isotopic if one of them can be obtained from the other by a permutation of rows and columns and renaming of elements. Let $  k _ {n} $
 +
be the number of equivalence classes of Latin squares of order $  n $.  
 +
The following first few values of l _ {n} $
 +
and $  k _ {n} $
 +
are known:<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 $
 +
</td> <td colname="2" style="background-color:white;" colspan="1">3</td> <td colname="3" style="background-color:white;" colspan="1">4</td> <td colname="4" style="background-color:white;" colspan="1">5</td> <td colname="5" style="background-color:white;" colspan="1">6</td> <td colname="6" style="background-color:white;" colspan="1">7</td> <td colname="7" style="background-color:white;" colspan="1">8</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"> $  k _ {n} $
 +
</td> <td colname="2" style="background-color:white;" colspan="1">1</td> <td colname="3" style="background-color:white;" colspan="1">2</td> <td colname="4" style="background-color:white;" colspan="1">2</td> <td colname="5" style="background-color:white;" colspan="1">22</td> <td colname="6" style="background-color:white;" colspan="1">563</td> <td colname="7" style="background-color:white;" colspan="1">1 676 257</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"> l _ {n} $
 +
</td> <td colname="2" style="background-color:white;" colspan="1">1</td> <td colname="3" style="background-color:white;" colspan="1">4</td> <td colname="4" style="background-color:white;" colspan="1">56</td> <td colname="5" style="background-color:white;" colspan="1">9408</td> <td colname="6" style="background-color:white;" colspan="1">16 942 080</td> <td colname="7" style="background-color:white;" colspan="1">535 281 401 856</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"> $  m _ {n} $
 +
</td> <td colname="2" style="background-color:white;" colspan="1">1</td> <td colname="3" style="background-color:white;" colspan="1">2</td> <td colname="4" style="background-color:white;" colspan="1">12</td> <td colname="5" style="background-color:white;" colspan="1">288</td> <td colname="6" style="background-color:white;" colspan="1">34 560</td> <td colname="7" style="background-color:white;" colspan="1">24 883 200</td> </tr> </tbody> </table>
  
 
</td></tr> </table>
 
</td></tr> </table>
  
Also, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762036.png" />. The problem of obtaining bounds for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762037.png" /> remains unsolved (1982).
+
Also, $  l _ {9} = 377  597  570  964  258  816 $.  
 +
The problem of obtaining bounds for l _ {n} $
 +
remains unsolved (1982).
  
In the theory of design of experiments it is required to construct Latin squares with various restrictions on the position of elements in them. A Latin square on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762038.png" /> is said to be complete if for any natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762039.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762040.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762041.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762042.png" />, there are numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762043.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762044.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762045.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762046.png" /> such that
+
In the theory of design of experiments it is required to construct Latin squares with various restrictions on the position of elements in them. A Latin square on $  \{ 1 \dots n \} $
 +
is said to be complete if for any natural numbers $  \alpha $,
 +
$  \beta $,  
 +
$  \alpha \neq \beta $,  
 +
$  1 \leq  \alpha , \beta \leq  n $,  
 +
there are numbers $  i $,  
 +
$  j $,  
 +
$  k $,  
 +
l $
 +
such that
  
<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/l/l057/l057620/l05762047.png" /></td> </tr></table>
+
$$
 +
( a _ {ij} , a _ {i,j+} 1 )  = \
 +
( \alpha , \beta ) \  \textrm{ and } \ \
 +
( a _ {kl} , a _ {k+} 1,l )  = ( \alpha , \beta ) ,
 +
$$
  
Algorithms for constructing complete Latin squares are known only for even <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762048.png" />; there are examples of complete squares for certain odd <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762049.png" />.
+
Algorithms for constructing complete Latin squares are known only for even $  n $;  
 +
there are examples of complete squares for certain odd $  n $.
  
A Latin subsquare of a given Latin square of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762050.png" /> is a submatrix of it such that it is itself a Latin square of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762051.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762052.png" />. Any Latin square of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762053.png" /> can be a Latin subsquare of a Latin square of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762054.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762055.png" />.
+
A Latin subsquare of a given Latin square of order $  n $
 +
is a submatrix of it such that it is itself a Latin square of order $  k $,  
 +
$  k < n $.  
 +
Any Latin square of order $  k $
 +
can be a Latin subsquare of a Latin square of order $  n $
 +
if $  n \geq  2 k $.
  
In the construction of [[Orthogonal Latin squares|orthogonal Latin squares]] an important role is played by the concept of a transversal of a Latin square. A partial transversal of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762056.png" /> of a Latin square <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762057.png" /> is a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762058.png" /> consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762059.png" /> cells of the Latin square,
+
In the construction of [[Orthogonal Latin squares|orthogonal Latin squares]] an important role is played by the concept of a transversal of a Latin square. A partial transversal of length $  t $
 +
of a Latin square $  A = \| a _ {ij} \| $
 +
is a set $  T $
 +
consisting of $  t $
 +
cells of the Latin square,
  
<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/l/l057/l057620/l05762060.png" /></td> </tr></table>
+
$$
 +
= \{ ( i _ {1} , j _ {1} ) \dots ( i _ {t} , j _ {t} ) \} ,
 +
$$
  
such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762061.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762062.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762063.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762064.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762065.png" />. One always has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762066.png" />; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762067.png" />, a partial transversal is called a transversal. The existence in a Latin square of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762068.png" /> of a set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762069.png" /> disjoint transversals is a necessary and sufficient condition for the existence of an orthogonal mate, i.e. a Latin square on the same symbols orthogonal to the given one. The Latin square of order 6,
+
such that $  i _ {k} \neq i _ {l} $,  
 +
$  j _ {k} \neq j _ {l} $,  
 +
$  a _ {i _ {k}  j _ {k} } \neq a _ {i _ {l}  j _ {l} } $
 +
for $  k \neq l $,
 +
$  1 \leq  k , l \leq  t $.  
 +
One always has $  t \leq  n $;  
 +
if $  t = n $,  
 +
a partial transversal is called a transversal. The existence in a Latin square of order $  n $
 +
of a set of $  n $
 +
disjoint transversals is a necessary and sufficient condition for the existence of an orthogonal mate, i.e. a Latin square on the same symbols orthogonal to the given one. The Latin square of order 6,
  
<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/l/l057/l057620/l05762070.png" /></td> </tr></table>
+
$$
 +
 
 +
\begin{array}{c}
 +
012  345  \\
 +
120  453  \\
 +
201  534  \\
 +
345  012  \\
 +
451  320  \\
 +
534  201  \\
 +
\end{array}
 +
 
 +
$$
  
 
does not have a transversal.
 
does not have a transversal.
  
In any Latin square of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762071.png" /> there is at least one partial transversal of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762072.png" />. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762073.png" /> one can always construct a Latin square such that both its main diagonals are transversals.
+
In any Latin square of order $  n \geq  7 $
 +
there is at least one partial transversal of length $  t \geq  ( 2 n + 1 ) / 3 $.  
 +
For $  n \geq  4 $
 +
one can always construct a Latin square such that both its main diagonals are transversals.
  
 
==Some generalizations of Latin squares.==
 
==Some generalizations of Latin squares.==
A partial, or incomplete, Latin square of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762074.png" /> is a matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762075.png" /> in which part of the cells are filled by the elements of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762076.png" /> of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762077.png" />, but such that in every row and every column the elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762078.png" /> occur at most once. There are partial Latin squares that cannot be completed to a Latin square, for example,
+
A partial, or incomplete, Latin square of order $  n $
 +
is a matrix of order $  n $
 +
in which part of the cells are filled by the elements of a set $  S $
 +
of cardinality $  n $,  
 +
but such that in every row and every column the elements of $  S $
 +
occur at most once. There are partial Latin squares that cannot be completed to a Latin square, for example,
  
<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/l/l057/l057620/l05762079.png" /></td> </tr></table>
+
$$
  
An incomplete Latin square containing exactly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762080.png" /> elements can be completed to a Latin square. It is known that when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762081.png" /> the Cayley tables of two different groups of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762082.png" /> differ from each other in at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762083.png" /> places.
+
\begin{array}{cccc}
 +
1  & .  & .  & .  \\
 +
.  & 2  & 3  & 4  \\
 +
.  & .  & .  & .  \\
 +
.  & .  & .  & .  \\
 +
\end{array}
 +
 
 +
$$
 +
 
 +
An incomplete Latin square containing exactly $  n - 1 $
 +
elements can be completed to a Latin square. It is known that when $  n > 4 $
 +
the Cayley tables of two different groups of order $  n $
 +
differ from each other in at least $  2 n $
 +
places.
  
 
An infinite Latin square is an infinite matrix whose elements are natural numbers that occur in each row and each column exactly once.
 
An infinite Latin square is an infinite matrix whose elements are natural numbers that occur in each row and each column exactly once.
  
There are a few generalizations of the concept of a Latin square to the multi-dimensional case. Thus, an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762085.png" />-dimensional permutation cube of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762086.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762087.png" />-dimensional matrix
+
There are a few generalizations of the concept of a Latin square to the multi-dimensional case. Thus, an $  m $-
 +
dimensional permutation cube of order $  n $
 +
is an $  m $-
 +
dimensional matrix
  
<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/l/l057/l057620/l05762088.png" /></td> </tr></table>
+
$$
 +
= \| a _ {i _ {1}  \dots i _ {m} } \|
 +
$$
  
of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762089.png" /> whose elements are the first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762090.png" /> natural numbers and which is such that for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762091.png" /> the set
+
of order $  n $
 +
whose elements are the first $  n $
 +
natural numbers and which is such that for any $  k $
 +
the set
  
<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/l/l057/l057620/l05762092.png" /></td> </tr></table>
+
$$
 +
a _ {i _ {1}  \dots i _ {k-} 1 1i _ {k+} 1 \dots i _ {m} } ,\
 +
a _ {i _ {1}  \dots i _ {k-} 1 2i _ {k+} 1 \dots i _ {m} } \dots
 +
$$
  
<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/l/l057/l057620/l05762093.png" /></td> </tr></table>
+
$$
 +
a _ {i _ {1}  \dots i _ {k-} 1 ni _ {k+} 1 \dots i _ {m} }
 +
$$
  
is a permutation of the first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762094.png" /> natural numbers. An <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762096.png" />-dimensional hypercube of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762097.png" /> and class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762098.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l05762099.png" />-dimensional matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l057620100.png" /> with elements belonging to a set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l057620101.png" /> elements, each of which occurs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l057620102.png" /> times in the matrix, and in every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l057620103.png" />-dimensional section of the matrix (that is, among the elements
+
is a permutation of the first $  n $
 +
natural numbers. An $  m $-
 +
dimensional hypercube of order $  n $
 +
and class $  r $
 +
is an $  m $-
 +
dimensional matrix of order $  n $
 +
with elements belonging to a set of $  n  ^ {r} $
 +
elements, each of which occurs $  n  ^ {m-} r $
 +
times in the matrix, and in every $  ( n - 1 ) $-
 +
dimensional section of the matrix (that is, among the elements
  
<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/l/l057/l057620/l057620104.png" /></td> </tr></table>
+
$$
 +
a _ {i _ {1}  \dots i _ {k-} 1 i _ {k}  ^ {0} i _ {k+} 1 \dots i _ {m} } ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l057620105.png" /> and the remaining indices run through all the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l057620106.png" /> values) it occurs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l057620107.png" /> times.
+
where $  i _ {k}  ^ {0} = \textrm{ const } $
 +
and the remaining indices run through all the $  n $
 +
values) it occurs $  n  ^ {m-} r- 1 $
 +
times.
  
 
====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,  "Latin squares and their applications" , Acad. Press  (1974)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  M. Hall,  "Combinatorial theory" , Blaisdell  (1967)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  H.J. Ryser,  "Combinatorial mathematics" , ''Carus Math. Monogr.'' , '''14''' , Math. Assoc. Amer.  (1963)</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,  "Latin squares and their applications" , Acad. Press  (1974)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  M. Hall,  "Combinatorial theory" , Blaisdell  (1967)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  H.J. Ryser,  "Combinatorial mathematics" , ''Carus Math. Monogr.'' , '''14''' , Math. Assoc. Amer.  (1963)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
 
The truth of the van der Waerden permanent conjecture (cf. [[Permanent|Permanent]]) implies that
 
The truth of the van der Waerden permanent conjecture (cf. [[Permanent|Permanent]]) implies that
  
<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/l/l057/l057620/l057620108.png" /></td> </tr></table>
+
$$
 +
L _ {n}  \geq  \
 +
 
 +
\frac{( n!)  ^ {2n} }{n ^ {n  ^ {2} } }
 +
,
 +
$$
  
 
cf. [[#References|[a1]]].
 
cf. [[#References|[a1]]].
  
P.W. Shor (cf. [[#References|[a2]]]) obtained the lower bound <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l057620109.png" /> for the length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l057620110.png" /> of a partial transversal in a Latin square (of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l057620111.png" />).
+
P.W. Shor (cf. [[#References|[a2]]]) obtained the lower bound $  t \geq  n - c (  \mathop{\rm log}  n)  ^ {2} $
 +
for the length $  t $
 +
of a partial transversal in a Latin square (of order $  n > 7 $).
  
The assertion that an incomplete Latin square containing exactly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057620/l057620112.png" /> elements may be completed to a Latin square is known as the Evans conjecture. It was proved by B. Smetaniuk [[#References|[a3]]].
+
The assertion that an incomplete Latin square containing exactly $  n - 1 $
 +
elements may be completed to a Latin square is known as the Evans conjecture. It was proved by B. Smetaniuk [[#References|[a3]]].
  
 
For a recent survey on Latin squares see [[#References|[a4]]].
 
For a recent survey on Latin squares see [[#References|[a4]]].
Line 91: Line 246:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R.M. Wilson,  "Nonisomorphic Steiner triple systems"  ''Math. Z.'' , '''135'''  (1974)  pp. 303–313</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P.W. Shor,  "A lower bound for the length of a partial transversal in a Latin square"  ''J. Comb. Theory (A)'' , '''33'''  (1982)  pp. 1–8</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  B. Smetaniuk,  "A new construction of Latin squares I: A proof of the Evans conjecture"  ''Ars. Comb.'' , '''11'''  (1981)  pp. 155–172</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  D. Jungnickel,  "Lateinische Quadrate, ihre Geometrien und ihre Gruppen"  ''Jahresber. Deutsch. Math. Verein.'' , '''86'''  (1984)  pp. 69–108</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  A. Penfold Street,  D.J. Street,  "Combinatorics of experimental design" , Clarendon Press  (1987)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  R.M. Wilson,  "Nonisomorphic Steiner triple systems"  ''Math. Z.'' , '''135'''  (1974)  pp. 303–313</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  P.W. Shor,  "A lower bound for the length of a partial transversal in a Latin square"  ''J. Comb. Theory (A)'' , '''33'''  (1982)  pp. 1–8</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  B. Smetaniuk,  "A new construction of Latin squares I: A proof of the Evans conjecture"  ''Ars. Comb.'' , '''11'''  (1981)  pp. 155–172</TD></TR>
 +
<TR><TD valign="top">[a4]</TD> <TD valign="top">  D. Jungnickel,  "Lateinische Quadrate, ihre Geometrien und ihre Gruppen"  ''Jahresber. Deutsch. Math. Verein.'' , '''86'''  (1984)  pp. 69–108</TD></TR>
 +
<TR><TD valign="top">[a5]</TD> <TD valign="top">  A. Penfold Street,  D.J. Street,  "Combinatorics of experimental design" , Clarendon Press  (1987) {{ZBL|0622.05001}}</TD></TR>
 +
</table>

Latest revision as of 11:23, 17 March 2023


A square matrix of order $ n $ in which each row and each column are permutations of the elements of a finite set $ S $ consisting of $ n $ elements. The Latin square is said to be constructed on the set $ S $; usually $ S = \{ 1 \dots n \} $. A Latin square exists for any $ n $; for example, $ A = \| a _ {ij} \| $, where

$$ a _ {ij} \equiv i + j - 1 ( \mathop{\rm mod} n ) ,\ \ i , j = 1 \dots n , $$

is a Latin square.

Every Latin square can be regarded as the multiplication table of a quasi-group; the converse is also true: the multiplication table of a finite quasi-group is a Latin square. For a Latin square $ A = \| a _ {ij} \| $ to be the Cayley table of a group it is necessary and sufficient that the following condition (the square criterion) is satisfied: If $ a _ {ik} = a _ {i _ {1} k _ {1} } $, $ a _ {il} = a _ {i _ {1} l _ {1} } $, $ a _ {jk} = a _ {j _ {1} k _ {1} } , $ then $ a _ {jl} = a _ {j _ {1} l _ {1} } $.

From two Latin squares, $ A = \| a _ {kl} \| $ of order $ n $ and $ B = \| b _ {rs} \| $ of order $ m $, one can always construct a Latin square $ C = \| c _ {ij} \| $ of order $ mn $, for example as follows:

$$ c _ {ij} = b _ {rs} + ( a _ {kl} - 1 ) m ,\ \ i = r + m ( k - 1 ) ,\ \ j = s + m ( l - 1 ) . $$

For the number $ L _ {n} $ of Latin squares of order $ n $ one has the following lower bound:

$$ L _ {n} \geq n ! ( n - 1 ) ! \dots 1 ! . $$

A Latin square is said to be reduced (or a Latin square of standard form) if the elements of its first row and first column are in the natural order. For the number $ l _ {n} $ of reduced Latin squares of order $ n $ one has

$$ L _ {n} = n ! ( n - 1 ) ! l _ {n} ,\ \ l _ {n} \geq m _ {n} = ( n - 2 ) ! ( n - 3 ) ! \dots 1 ! $$

Two Latin squares constructed on the same set $ S $ are said to be equivalent or isotopic if one of them can be obtained from the other by a permutation of rows and columns and renaming of elements. Let $ k _ {n} $ be the number of equivalence classes of Latin squares of order $ n $. The following first few values of $ l _ {n} $ and $ k _ {n} $

are known:

<tbody> </tbody>
$ n $ 3 4 5 6 7 8
$ k _ {n} $ 1 2 2 22 563 1 676 257
$ l _ {n} $ 1 4 56 9408 16 942 080 535 281 401 856
$ m _ {n} $ 1 2 12 288 34 560 24 883 200

Also, $ l _ {9} = 377 597 570 964 258 816 $. The problem of obtaining bounds for $ l _ {n} $ remains unsolved (1982).

In the theory of design of experiments it is required to construct Latin squares with various restrictions on the position of elements in them. A Latin square on $ \{ 1 \dots n \} $ is said to be complete if for any natural numbers $ \alpha $, $ \beta $, $ \alpha \neq \beta $, $ 1 \leq \alpha , \beta \leq n $, there are numbers $ i $, $ j $, $ k $, $ l $ such that

$$ ( a _ {ij} , a _ {i,j+} 1 ) = \ ( \alpha , \beta ) \ \textrm{ and } \ \ ( a _ {kl} , a _ {k+} 1,l ) = ( \alpha , \beta ) , $$

Algorithms for constructing complete Latin squares are known only for even $ n $; there are examples of complete squares for certain odd $ n $.

A Latin subsquare of a given Latin square of order $ n $ is a submatrix of it such that it is itself a Latin square of order $ k $, $ k < n $. Any Latin square of order $ k $ can be a Latin subsquare of a Latin square of order $ n $ if $ n \geq 2 k $.

In the construction of orthogonal Latin squares an important role is played by the concept of a transversal of a Latin square. A partial transversal of length $ t $ of a Latin square $ A = \| a _ {ij} \| $ is a set $ T $ consisting of $ t $ cells of the Latin square,

$$ T = \{ ( i _ {1} , j _ {1} ) \dots ( i _ {t} , j _ {t} ) \} , $$

such that $ i _ {k} \neq i _ {l} $, $ j _ {k} \neq j _ {l} $, $ a _ {i _ {k} j _ {k} } \neq a _ {i _ {l} j _ {l} } $ for $ k \neq l $, $ 1 \leq k , l \leq t $. One always has $ t \leq n $; if $ t = n $, a partial transversal is called a transversal. The existence in a Latin square of order $ n $ of a set of $ n $ disjoint transversals is a necessary and sufficient condition for the existence of an orthogonal mate, i.e. a Latin square on the same symbols orthogonal to the given one. The Latin square of order 6,

$$ \begin{array}{c} 012 345 \\ 120 453 \\ 201 534 \\ 345 012 \\ 451 320 \\ 534 201 \\ \end{array} $$

does not have a transversal.

In any Latin square of order $ n \geq 7 $ there is at least one partial transversal of length $ t \geq ( 2 n + 1 ) / 3 $. For $ n \geq 4 $ one can always construct a Latin square such that both its main diagonals are transversals.

Some generalizations of Latin squares.

A partial, or incomplete, Latin square of order $ n $ is a matrix of order $ n $ in which part of the cells are filled by the elements of a set $ S $ of cardinality $ n $, but such that in every row and every column the elements of $ S $ occur at most once. There are partial Latin squares that cannot be completed to a Latin square, for example,

$$ \begin{array}{cccc} 1 & . & . & . \\ . & 2 & 3 & 4 \\ . & . & . & . \\ . & . & . & . \\ \end{array} $$

An incomplete Latin square containing exactly $ n - 1 $ elements can be completed to a Latin square. It is known that when $ n > 4 $ the Cayley tables of two different groups of order $ n $ differ from each other in at least $ 2 n $ places.

An infinite Latin square is an infinite matrix whose elements are natural numbers that occur in each row and each column exactly once.

There are a few generalizations of the concept of a Latin square to the multi-dimensional case. Thus, an $ m $- dimensional permutation cube of order $ n $ is an $ m $- dimensional matrix

$$ A = \| a _ {i _ {1} \dots i _ {m} } \| $$

of order $ n $ whose elements are the first $ n $ natural numbers and which is such that for any $ k $ the set

$$ a _ {i _ {1} \dots i _ {k-} 1 1i _ {k+} 1 \dots i _ {m} } ,\ a _ {i _ {1} \dots i _ {k-} 1 2i _ {k+} 1 \dots i _ {m} } \dots $$

$$ a _ {i _ {1} \dots i _ {k-} 1 ni _ {k+} 1 \dots i _ {m} } $$

is a permutation of the first $ n $ natural numbers. An $ m $- dimensional hypercube of order $ n $ and class $ r $ is an $ m $- dimensional matrix of order $ n $ with elements belonging to a set of $ n ^ {r} $ elements, each of which occurs $ n ^ {m-} r $ times in the matrix, and in every $ ( n - 1 ) $- dimensional section of the matrix (that is, among the elements

$$ a _ {i _ {1} \dots i _ {k-} 1 i _ {k} ^ {0} i _ {k+} 1 \dots i _ {m} } , $$

where $ i _ {k} ^ {0} = \textrm{ const } $ and the remaining indices run through all the $ n $ values) it occurs $ n ^ {m-} r- 1 $ times.

References

[1] V.N. Sachkov, "Combinatorial methods in discrete mathematics" , Moscow (1977) (In Russian)
[2] J. Dênes, "Latin squares and their applications" , Acad. Press (1974)
[3] M. Hall, "Combinatorial theory" , Blaisdell (1967)
[4] H.J. Ryser, "Combinatorial mathematics" , Carus Math. Monogr. , 14 , Math. Assoc. Amer. (1963)

Comments

The truth of the van der Waerden permanent conjecture (cf. Permanent) implies that

$$ L _ {n} \geq \ \frac{( n!) ^ {2n} }{n ^ {n ^ {2} } } , $$

cf. [a1].

P.W. Shor (cf. [a2]) obtained the lower bound $ t \geq n - c ( \mathop{\rm log} n) ^ {2} $ for the length $ t $ of a partial transversal in a Latin square (of order $ n > 7 $).

The assertion that an incomplete Latin square containing exactly $ n - 1 $ elements may be completed to a Latin square is known as the Evans conjecture. It was proved by B. Smetaniuk [a3].

For a recent survey on Latin squares see [a4].

For a discussion of the role of Latin squares and sets of mutually orthogonal Latin squares in the design of experiments cf. [a5].

References

[a1] R.M. Wilson, "Nonisomorphic Steiner triple systems" Math. Z. , 135 (1974) pp. 303–313
[a2] P.W. Shor, "A lower bound for the length of a partial transversal in a Latin square" J. Comb. Theory (A) , 33 (1982) pp. 1–8
[a3] B. Smetaniuk, "A new construction of Latin squares I: A proof of the Evans conjecture" Ars. Comb. , 11 (1981) pp. 155–172
[a4] D. Jungnickel, "Lateinische Quadrate, ihre Geometrien und ihre Gruppen" Jahresber. Deutsch. Math. Verein. , 86 (1984) pp. 69–108
[a5] A. Penfold Street, D.J. Street, "Combinatorics of experimental design" , Clarendon Press (1987) Zbl 0622.05001
How to Cite This Entry:
Latin square. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Latin_square&oldid=15140
This article was adapted from an original article by V.M. Mikheev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article