Semi-Latin squares: Constructions

Here are some methods of creating semi-Latin squares.

Inflation

Take an n×n Latin or semi-Latin square with s letters per cell. Replace each letter by r new letters. This gives an (n×n)/(sr) semi-Latin square. It is the r-fold inflation of the original square.

Superposition

Take Latin or semi-Latin squares of size (n×n)/ki for i = 1, ..., r. The squares must all have their rows labelled in the same way, and also their columns, and the letters in any one square must not appear in any other square. The superimposition of these squares has blocks of size k1 + ... + kr: in the block in row a and column b put all the letters that occur in this block of any of the squares.

Inflation is the special case of superposition that arises when the original squares are the same as each other apart from a renaming of letters. Superimposition of mutually orthogonal Latin squares gives a Trojan square.

Group method

Let G be a group of order nk. Suppose that G has subsets H, R and C of sizes k, n and n respectively, such that G = RH = HC. Label the rows and columns of an n×n square by the elements of R and C respectively. Then the elements in the block in row r and column c are all those of the form rhc for h in H.

If H is a subgroup of G then this method gives an inflated Latin square.

Relaxed Product

Take an (n×n)/s Latin or semi-Latin square M on the numbers 1, ... ns, and n2 further squares Lij of size (m×m)/r all on the same set of mr letters. In row i and column j of M put the whole of Lij and replace each of its letters by subscripted forms, using as subscripts all the numbers in that cell of the original M.

Example

A1 B1 C1 D1 A2 B2 C2 D2 A3 C3 B3 D3
C1 D1 A1 B1 C2 D2 A2 B2 B3 D3 A3 C3
A3 D3 B3 C3 A1 C1 B1 D1 A2 B2 C2 D2
B3 C3 A3 D3 B1 D1 A1 C1 C2 D2 A2 B2
A2 B2 C2 D2 A3 D3 B3 C3 A1 D1 B1 C1
C2 D2 A2 B2 B3 C3 A3 D3 B1 C1 A1 D1

This is a direct product if all the Lij are the same.

Deletion-augmentation

Start with a semi-Latin square formed by the orthogonal superposition of an n×n Latin square L and an (n×n)/(n-2) semi-Latin square. Arrange it so that a given letter A of L is on the diagonal. Add an extra row and column, and ``letters'' 1, ..., n. In the ith diagonal block, first replace A by i, then move that block to the ith position in the new row and column, then put all of 1, ..., n except i on the diagonal. Finally, put all letters of L except A in the cell in the new row and column.

Example

2 3 4D E FG H IJ K L B C 1
D K I1 3 4J E CG B F H L 2
G E LJ B I1 2 4D H C K F 3
J H FG K CD B L1 2 3 E I 4
B C 1 H L 2 K F 3 E I 4 D G J

Page maintained by R. A. Bailey

Page updated 4/8/00