A pair of Latin squares (cf.
Latin square)
,
of order
such that
if
,
.
The squares
and
are called
orthogonal mates.
The matrix obtained by the superposition of
on
is called a
Greco–Latin
or
Euler square;
its elements are all the
ordered pairs of elements from
.
The orthogonality of
and
is denoted by
.
An example of a pair of orthogonal Latin squares and their Euler square for
is:
A Latin square
of order
has an orthogonal mate if and only if
non-intersecting transversals exist in
(see
Latin square).
If
is a Latin square of order
(or
)
with a subsquare of order
(or
)
all cells of which, with the possible exception of
(or
)
cells, are filled by not more than
(or
)
elements, then no orthogonal mate exists for
.
For all
,
,
there are examples of pairs of orthogonal Latin squares, while for
,
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
is the maximum possible number of pairwise orthogonal Latin squares, then
.
A set of
pairwise orthogonal Latin squares of order
is called
complete.
When
,
a set of
pairwise orthogonal Latin squares can always be made
complete. Up till now
(1989),
the only complete sets known are for
,
where
is a natural number and
is a prime number (i.e.
).
The following lower bounds have been obtained for
:
 |
7 |
52 |
53 |
63 |
90 |
 |
2 |
3 |
4 |
5 |
6 |
|
Moreover,
,
,
,
,
,
and it has been proved that
as
;
for example,
for sufficiently large
(see
[2]).
If
(
)
or
(
),
and if the square-free part of the number
contains even one prime factor
(
),
then no complete set of pairwise orthogonal Latin squares of order
exists. For example, no complete sets exist for
,
(
).
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
,
,
,
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
.
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
is a Latin square of order
on the set
,
then the ordered set of permutations
,
,
defined by the equations
uniquely determines
.
Not every ordered set of permutations corresponds to a Latin square. If
and
are two Latin squares defined in the above way by permutations
and
of the set
,
then
if and only if
is a Latin square. If one defines products
,
,
where
and
are permutations of
,
then, for example,
if and only if
is a Latin square.
The methods in the first group are usually used when
is the multiplication table of a finite group
,
i.e.
,
,
;
the difference between one method and the other lies in the choice of the group
,
the choice of the one-to-one mappings
of the group
onto itself, and the use of the products
,
,
,
etc.
If
is an additive group, then the condition
reduces to the fact that
is an
orthomorphism
of
,
i.e. a one-to-one mapping of
onto itself such that if
for
,
then
.
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
is the additive group of a finite field
,
,
then all constructions are significantly simplified, and
the following complete set of pairwise orthogonal Latin squares is obtained:
It may be noted that a Latin square
of order
such that
(i.e. a
self-orthogonal Latin square)
exists if and only if
.
The use of the direct product of Latin squares forms the
basis of the following method, related to the second group. Let
and
be orthogonal Latin squares of order
on a set
,
while
and
are orthogonal Latin squares of order
on a set
;
the direct products of matrices
and
will then be orthogonal Latin squares of order
on the set
.
If
,
then this method yields the bound
.
The following construction lies at the basis of
many other methods of the second group. Let
be pairwise orthogonal Latin squares of order
on the set
and let
be orthogonal Latin squares of order
on the set
.
In order to obtain two Latin squares
and
of order
on the set
,
rows and columns with numbers
with unfilled cells are added to
,
with the result that a partial Latin square of order
containing
in the top left corner is obtained. The cells of
and
having the same numbers as the cells of
that contain the element
form a common
-transversal,
,
for
and
.
The elements of the
-transversal
in
when
are placed in the
-th
column (and in the
-th
row) in the same order in which they stood in the rows and columns of
,
and the number
is put in their place. It remains to insert
in the bottom right corner of the partial square in order to complete
.
is constructed from
and
in the same way, but only by using transversals with the numbers
.
The squares
and
will be Latin, but not necessarily orthogonal. A
pair of orthogonal Latin squares of order
can always be obtained if
,
is odd and
;
it has been shown, using the above construction, how
to obtain a pair of orthogonal Latin squares of order
when
(
),
(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
is said to be
imbedded
in the Latin square
if
coincides with a submatrix of
(with the exception of the empty cells of
).
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]).