# Semi-Latin squares and SOMAs: Definitions

## 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