Latin Squares

A Latin square is a square with an equal number of rows and columns which is filled with symbols (numbers, letters, colors, actually anything you like) so that each symbol appears exactly once in each row and once in each column of the square. The number of different symbols you will need to do this is the same as the number of rows (or columns). The number of rows ( = number of columns = number of symbols) of a Latin square is called the order of the square.

In the examples below I will use colors as the symbols (you can make Latin squares like these very easily by cutting small squares of the same size of different colored paper and moving them around to form a big Latin square.)

Examples:

Two Latin squares of order 3.

Two Latin squares of order 4.

Latin squares are easy to make for any order. You should try to make a few Latin squares of order 5.

Graeco-Latin Squares

An interesting question involves using pairs of Latin squares of the same order. When two Latin squares of the same order are placed on top of one another so that the ordered pairs of symbols in each position are all different, the two squares are called Graeco-Latin squares. The word ordered means that, for example, a blue entry in the first square and a red entry in the second square in the same position is to be considered different from a red entry in the first square and a blue entry in the second square in the same position.

In the examples below, there is a bottom Latin square and a top Latin square. In order to see the entries of both squares, I've drawn the entries in the top square as smaller boxes to make the entries in the bottom square visible.

Examples

Graeco-Latin squares of order 3.

Graeco-Latin squares of order 4.

Forming Graeco-Latin squares is more difficult that just finding Latin squares. Given one Latin square it is not always possible to find a second one so that the pair form a Graeco-Latin square. For instance, it can't be done if you start with the second example of a Latin square of order 4 that we gave above. Let's see what happens. In the figure below I've started by picking the first two rows of the "top" square and now want to fill out the last two rows.

In the second picture, I fill out the first column. Since I need to have a yellow in this column (I already have a red and a blue) and I can't put it on top of the yellow bottom square (I already have a yellow on yellow pair), I must fill out the column as shown. Now I try to fill out the second column (third picture). I must use a red in this column, but where can I put it? I can't put it on the bottom red square because I already have a red on red pair (top row) and I can't put it on the bottom yellow square because I already have a red on yellow pair (second row). So, I can't build Graeco-Latin squares with the second row that I have picked. You should try to use a different second row than the one I picked. You will run into the same problem. In fact, you will always run into this type of problem - even if you use a different first row.

This example leads us to two interesting questions. The first one is, if I give you a Latin square, can you look at it and decide if you can find another Latin square so that the two form a Graeco-Latin pair? The second question is similar. If I give you just the order (size of the squares) can you find a Graeco-Latin pair with that order? The first question is easier and we will answer it in the next section. The second question turns out to be very difficult. It took over a hundred years from the time it was first asked until it was finally answered. The answer is YES, except if the order is 2 or 6. You can check that it can't be done for order 2 very quickly, but the order 6 exception is difficult because there are so many possibilities that have to be checked. The reason it took so long to find this answer is that while some orders are very easy to deal with, others are very, very difficult. These very difficult orders are the even numbers which are twice an odd number. Notice that 2 and 6 are like this. The smallest of the very difficult orders that took over one hundred years to handle is 10.