Definition of semi-Latin square
A (n × n)/k
semi-Latin
square is a square array with n rows and n
columns in which nk letters are placed in such a way that
there are k letters in each cell (row-column intersection)
each letter occurs once in each row and once in each column.
Note that the order of the letters in each cell is immaterial.
A semi-Latin square is called simple if no
pair of letters occurs together in more than one cell.
Definition of orthogonal array
An orthogonal array
OA[N; r; n1, ...,
nr; t]
is an array with N columns and r rows such that
each row-column intersection has one symbol
there are ni symbols appearing
in row i
every t-rowed subarray has all ordered combinations of
symbols in columns equally often.
Example 1
A set of s mutually orthogonal n × n
Latin squares is
an OA[n2; s+2; n, ..., n; 2].
Example 2
An (n × n)/k semi-Latin square is an
OA[n2k; 3; n, n, nk; 2].
Warning!
The ``rows'' of the semi-Latin square are the symbols of one of the
``rows'' of the orthogonal array.
Definition of orthogonal multi-array
An orthogonal multi-array (OMA)
is like an orthogonal array except that
there are extra parameters m1, ...,
mr such that
each row-column intersection in row i has
mi symbols,
possibly including repeats
there are ni symbols appearing
in row i
every t-rowed subarray has all ordered combinations of
symbols in columns equally often, with careful counting
(for example, there are
m1m2 combinations in
each column for rows 1 and 2).
If t >=1 then each symbol appearing on row i appears
Nmi/ni times in that row.
Example 3
A set of u mutually orthogonal 1-factorizations of a graph
on 2n vertices with valency n is an
OMA[n2; u+1; n, ..., n,
2n; 1, ..., 1, 2; 2].
This is called a (special case of a) Howell
design if u = 2 and a
Howell cube if u = 3.
Easy Construction 1
If an OMA has mi
= 1 for i >= 2 then you can
make from it an OA with Nm1 columns.
Example 4
Applying Easy Construction 1 to an
OMA[n2; 3; nk, n, n; k,
1, 1; 2] gives a semi-Latin square.
If the semi-Latin square is simple then the orthogonal multi-array is
also called simple, and is abbreviated to SOMA(k,n).
Easy Construction 2
In an OMA, if n1/m1 =
n2/m2 then the first two
rows can be replaced by a new (merged) row (z) with
nz = n1 + n2
and mz = m1 + m2.
Example 5
Take the orthogonal array in Example 1, and apply Easy Cconstruction 2
to merge all but two of the rows and get an orthogonal multi-array.
Then apply Easy Construction 1 to get a semi-Latin square. Every such
semi-Latin square is called a Trojan square.
Example 6
Take a Howell cube and apply Easy Construction 2 to the last two lines to
get an OMA[n2; 3; n, n, 3n; 1,
1, 3; 2] then apply Easy Construction 1 to get a semi-Latin square.
This is how the nice SOMA(3,6)s arise.
Definitions of decomposable and orthogonal and superposition
A (n × n)/k semi-Latin square S is
orthogonally decomposable
into (n × n)/k1 and
(n × n)/k2 semi-Latin squares
T1 and T2 if there
is an
OMA[n2; 4; n, n,
nk1, nk2; 1, 1,
k1, k2; 2]
such that
omitting the third row gives
an OMA to which Easy Construction 1 may be applied to give
the component semi-Latin square T2
omitting the fourth row gives an
OMA to which Easy Construction 1 may be applied to give
the other component semi-Latin square T1
merging the third and fourth rows by Easy Construction 2 gives an
OMA to which Easy Construction 1 may be applied to give the whole
semi-Latin square S.
In this case we say that T1 and T2
are orthogonal to each other.
More generally, we say that
a (n × n)/k semi-Latin square S is
decomposable
into (n × n)/k1 and
(n × n)/k2 semi-Latin squares
T1 and T2,
or that S is the superposition of
T1 and T2,
if there is a four-rowed array
such that
omitting the third row gives
an OMA corresponding
the component semi-Latin square T2
omitting the fourth row gives an OMA corresponding
the component semi-Latin square T1
merging the third and fourth rows by Easy Construction 2 gives an
OMA corresponding to the semi-Latin square S.
Page maintained by
R. A. Bailey
Page updated 24/6/00