Skip to Main Content

Latin Squares in Practice and in Theory II

Feature Column Archive

3. Mutually Orthogonal Latin Squares (MOLS)

After the ``Euler spoiler'' examples of Bose, Parker and Shrikhande, pairs of orthogonal latin squares were known in every size except 2 and 6. For some sizes more was known. For example, if n is a prime, then one can construct n-1 mutually orthogonal latin squares.

Four MOLS of size 5. In the first, each row is shifted one spot to the left with respect to the row above it; in the second, each is shifted two spots to the left, etc. This pattern, using the n-1 possible slopes, gives n-1 MOLS for any prime size n.

What happens with other sizes? Let N(n) be the number of MOLS that exist of size n. It is known that

  • N(n) is at most n-1;
  • for primes (see above) and powers of primes, this upper bound can be attained.

Other numbers require special methods. The results are very incomplete, and the problem is currently a hot one in combinatorics. Here is a table from a recent paper by Charles Colbourn and Jeff Dinitz, reproduced with the authors' permission. They tabulate the best known lower bound on N(n), for n from 0 to 199. 

       0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19    0           1   2   3   4   1   6   7   8   2  10   5  12   3   4  15  16   3  18  20   4   5   3  22   6  24   4  26   5  28   4  30  31   5   4   5   6  36   4   5  40   7  40   5  42   5   6   4  46   7  48   6   5   5  52   5   6   7   7   5  58  60   4  60   4   6  63   7   5  66   5   6   6  70   7  72   5   5   6   6   6  78  80   9  80   8  82   6   6   6   6   7  88   6   7   6   6   6   6   7  96   6   8 100   8 100   6 102   7   7   6 106   6 108   6   6  13 112   6   7   6   8   6   6 120   7 120   6   6   6 124   6 126 127   7   6 130   6   7   6   7   7 136   6 138 140   6   7   6  10  10   7   6   7   6 148   6 150   7   8   8   7   6 156   7   6 160   9   7   6 162   6   7   6 166   7 168   6   8   6 172   6   6  14   9   6 178 180   6 180   6   6   7   9   6  10   6   8   6 190   7 192   6   7   6 196   6 198

The current state of the art in mutually orthogonal latin squares. This table gives, for n from 0 to 199, the best known lower bound for the number N(n) of MOLS of size n. Note that for n prime or a power of a prime, the lower bound is the maximum, n-1. Numbers in red are brand new or only a few years old. For more information, consult the CRC Handbook of Combinatorial Designs.