Row Complete Latin Squares

Latin Square

A Latin Square is an n×n array containing n different symbols so that each symbol appears exactly once in each row and once in each column.
An example of a Latin Square of order 5 is:

0  1  2  3  4
1  2  3  4  0
2  3  4  0  1
3  4  0  1  2
4  0  1  2  3

Another example is:

0  4  3  1  2
2  1  0  3  4
4  3  2  0  1
1  0  4  2  3
3  2  1  4  0

These are examples of cyclic squares: each column is obtained from the previous one by adding the same difference to each element of the previous column, working modulo n. For the first square, the difference set, or sequence, is 1, 1, 1, 1. For the second square, the difference set is 4, 4, 3, 1.

Row Complete Latin Squares

Consider a Latin Square L=[l(i,j)] which has element l(i,j) in row i and column j. 

The Latin Square is described as being row complete or row balanced if the n(n-1) ordered pairs (l(i,j),l(i,j+1)) are all distinct.

An example of a cyclic row complete Latin Square of order 4 is:

0  1  3  2
1  2  0  3
2  3  1  0
3  0  2  1

Such squares have important applications in pharmaceutical testing.

Construction of Cyclic Row Complete Latin Squares

Even Order

In 1949, E. J. Williams gave a very simple method for constructing cyclic row complete Latin Squares of even order.

Method: Arrange the n elements in any order for the first column. Successive columns are constructed using the difference set:

1, n-2, 3, n-4, 5, n-6, ......., n-1

So, for example, for n=6, the difference set is:

1, 4, 3, 2, 5

Starting with the elements in the first column in any order, an example of a row complete cyclic Latin Square of order 6 is:

0  1  5  2  4  3
5  0  4  1  3  2
2  3  1  4  0  5
1  2  0  3  5  4
4  5  3  0  2  1
3  4  2  5  1  0

To see that this is row complete, consider any label, say 0. Each other label follows label 0 in a row exactly once and in the other row, 0 appears as the final element.

0  1  5  2  4  3
5  0  4  1  3  2
2  3  1  4  0  5
1  2  0  3  5  4
4  5  3  0  2  1
3  4  2  5  1  0

This property holds for all six labels.

Exercise 1: construct row complete cyclic Latin Squares of orders 8 and 10.
Inspect the difference set for n=6. Note that no set of adjacent differences sums to 0 modulo 6.
Is a similar result true for the difference sets for n=8 and n=10?
Also, explain why the difference set must consist of the elements 1, 2, 3, ..., n-1 in some order.

Odd Order

Exercise 2: Try to use the same approach to produce a row complete cyclic Latin Square of order 5.
Experiment with different difference sets.
Why is no order of the elements 1, 2, 3 and 4 suitable to produce a row complete cyclic Latin Square of order 5?

It is possible to produce pairs of cyclic squares of odd order which together are row balanced, in that each of the n(n-1) ordered pairs (l(i,j),l(i,j+1)) occurs exactly twice.

Exercise 3: Devise a strategy to produce pairs of cyclic squares of odd order which, together, are row balanced.

Hint: For n=5, two suitable squares are:

0  1  4  2  3         0  4  1  3  2
1  2  0  3  4         1  0  2  4  3
2  3  1  4  0         2  1  3  0  4
3  4  2  0  1         3  2  4  1  0
4  0  3  1  2         4  3  0  2  1

References and Recommended Reading

J. Dénes and A.D. Keedwell, Latin Squares : New Developments in the Theory and Applications (Annals of Discrete Mathematics)

C.F. Laywine and C.M. Mullen, Discrete Mathematics Using Latin Squares, Wiley Interscience, 1998.

E. J. Williams, Experimental designs which are balanced for the estimation of residual effects of treatments, Australian J. Sci. Res. 2, 149 - 164, 1949.