Graeco-Latin Squares

Graeco-Latin squares are a fascinating example of something that developed first as a puzzle, then as a mathematical curiosity with no practical purpose, and ultimately ended up being very useful for real-world problems.

As early as 1725, Graeco-Latin squares existed as a puzzle with playing cards. The puzzle, which you can play in your browser by clicking on the image link to the right, is simply to arrange the 16 face cards (including the aces) such that each row and column has only one of each value and one of each suit (and, in this puzzle but not in Graeco-Latin squares generally, the two major diagonals also must have only one of each value and one of each suit). Even this simple problem is harder than it looks.

Latin Squares

Mathematician Leonhard Euler named these arrays Graeco-Latin squares, as he used letters from the Greek and Latin alphabets for the values. A Latin square has only one “dimension,” which is represented by letters from the Latin alphabet (though there are three variables: the rows, columns and letters). The simplest form is a 3×3 square, in which the letters A, B and C appear once in each row and once in each column.

The squares above are both Latin squares of order 3. The one on the right is in its reduced or normalized form, because both the first row and first column are in their natural order. You can see that Latin squares are not difficult to create, and the number of possible permutations increases with the size of the square.

Graeco-Latin Squares

To create a Graeco-Latin square, we add a second dimension, superimposing a square with Greek letters over the Latin square. The two squares must be mutually orthogonal, meaning that each Greek-Latin pair occurs only once. Therefore the same square cannot be superimposed over itself, but we can use the two Latin squares above, switch one to Greek letters, and superimpose it over the other, to arrive at this Graeco-Latin square of order 3. Graeco-Latin squares are also referred to as mutually orthogonal Latin squares.

Euler devoted study to these arrangements in the 18th century. He noted that no Graeco-Latin square exists of order 2, and he could not construct one of order 6, a problem he presented as the Thirty-six Officers Problem. He conjectured that Graeco-Latin squares did not exist for any order n where is an even number not divisible by 4, but in 1959, mathematicians were able to disprove this conjecture. They discovered Graeco-Latin squares of order 10 and proved that they exist for every order except 2 and 6.

Practical Uses

Graeco-Latin squares are useful for designing scientific experiments and organizing tournaments efficiently.  Here is an example.

Suppose you have seven cars, each of a different color, that you want to subject to performance tests, and you want to test each car under seven different types of road conditions, so you have tracks that are asphalt, dirt, gravel, wet, oily, icy, and snowy. You decide to make good use of time by employing seven drivers over seven days. Each driver is assigned to a car, with a helmet and uniform that matches the color of the car. Each day, each driver will operate their assigned car on one of the seven different tracks. The next day, each driver and their car shift to the next track over. After seven days, each car would have been tested on each track. That can be represented by a Latin square like the image below, with the columns representing the seven different tracks and the rows representing the seven days that would be necessary to test all 49 combinations. In this scenario, you have one treatment factor, which is the different color cars, and two blocking factors, which are the tracks (columns) and the days (rows), for three total variables.

Now you wish to improve your experiment. It occurs to you that, although you have tried to select drivers of equal skill, a small difference in a particular driver’s performance may introduce experimental error. This would be true whether the driver stayed with a single car or stayed on a single track. To address this issue, you can introduce the drivers as a third blocking factor (or fourth variable), and now a Graeco-Latin square is needed. Here is one, with the larger squares still representing the cars, and the smaller squares representing the drivers.

As you can see, we were able to keep our same pattern with the cars shifting one track to the left on each subsequent day. On the first day, the drivers are with their original cars. On each subsequent day, the drivers have to shift two tracks to the left. Thus,  in addition to no car repeating a track, no driver repeats a track, and no driver repeats a car. The same method can be used to construct a Graeco-Latin square of order 5.

Hyper-Graeco-Latin Squares

As we have seen, a Graeco-Latin square has two dimensions, which can be represented by Greek and Latin letters, by inner and outer colors, or in other ways. Adding additional dimensions creates a Hyper-Graeco-Latin square. Below is a 4×4 square with 3 dimensions: the outer, middle and inner squares.

And here we have a Hyper-Graeco-Latin square of order 5, with four dimensions.

A Graeco-Latin square can only have dimensions of one less than its order at most. See the link below for a 9×9 square by Tyler Hyndman that has eight dimensions.

Graeco-Latin squares have an interesting link to finite projective planes: a Hyper-Graeco-Latin square of order n can have n-1 dimensions if and only if a finite projective plane of order n exists.

Higher Order Squares

Graeco-Latin squares of an order that is an even number not divisible by 4 are not all impossible as Euler conjectured, but they are much more difficult to construct, and none were discovered until 1959. The discovery was a dramatic disproof of Euler’s conjecture, which had stood for nearly two centuries.  Here is why squares such as 10×10 are so difficult: in all of the above examples, one of the initial Latin squares is in its reduced form, the orthogonal squares also have the first row in its natural order, and there is an easily discernible pattern to the succeeding rows. This is not the case for squares such as a 10×10. This reduced Latin square of order 10 will not yield a 10×10 Graeco-Latin square.

The 10×10 Graeco-Latin square below is one of those discovered by R. C. Bose, S. S. Shrikhande, and E. T. Parker. It was published in numerical form in the Canadian Journal of Mathematics in 1960. Many of the 10×10 squares they discovered include a 3×3 square, which you can see in the bottom right corner.

Mathematical Art with Graeco-Latin Squares

Beautiful mathematical artwork has been created using Graeco-Latin squares. Below are a few links to examples. Click on the images to visit the source websites.