Transversals

An idea that we need to explore the question of whether or not you can find a second Latin square to form a Graeco-Latin pair is that of a transversal.

A transversal in a Latin Square is a collection of positions, one from each row and one from each column, so that the colors that are in these positions are all different.

Here is an example of a transversal in a 4×4 Latin square

Now look at the bottom squares of the Graeco-Latin square that correspond to this transversal of the top Latin square. Notice that all these squares have the same color!

If you now look at the small squares with the same color in the top Latin square, you'll notice that they are on a transversal of the big (bottom) Latin square. So, if you have a Graeco-Latin square, then the transversals of one correspond to the positions with the same color in the other, and vice-versa.

So, how can we use this idea? Suppose you are trying to make a Graeco-Latin square. If you start with a bottom square and can break it up into transversals which don't overlap each other, then you can make a second Latin square which will form a Graeco-Latin pair with the first. You form the second square by taking each of these transversals and putting the same color in each of the positions. Use a different color for each transversal. Here's an example. We first start by breaking up a Latin square into non-overlapping transversals.

Now we form a new square by coloring each transversal with the same color and put them back together.

Looking (carefully) at this final square and the one we started with, we see that they form a Graeco-Latin pair. In fact, this always works ... the problem is finding the non-overlapping transversals. If they don't exist, then you can't form a Graeco-Latin pair from your starting Latin square.

There are more transversals of the small square than just the 4 I used. Can you find them all? Can you break up the small square by using a different collection of non-overlapping transversals?

Finding Transversals

Finding non-overlapping transversals is in general hard to do and depends on the type of Latin square you start with. There are a few easy Latin squares to do this with. We'll start by looking at what we call cyclic Latin squares of odd order. You form these Latin squares by starting with any first row you like then make the second row by moving everything in the first row over one position to the left. The first entry (which would be outside the Latin square) is moved to the last position of the second row (this is called cycling, which is where the name comes from.) Repeat this to form the third row from the second row,and then the fourth row from the third and keep going until you are finished. In the example below I will use numbers instead of colors to make it easier to see what is happening, but each number just represents a different color. In this example of a cyclic Latin square of order 5, I show the construction of the second row in the first two pictures and the completed square in the last.

Look at the complete Latin square of order 5 that we have just constructed. We are trying to find non-overlapping transversals. Did you spot the transversal that goes down the diagonal? Now look at the positions just above the diagonal and also the bottom left corner. Yep, another transversal. In the picture below I've marked 5 non-overlapping transversals with lines of different colors.

You should build other cyclic Latin squares of different orders, both odd and even. Notice that only when the order is odd do you get the transversals in the same pattern as the order 5 example.

Transversals of a 10 × 10 Latin Square

The ideas used in the last section don't work for order 10 Latin squares. When Jay (ask Mrs. Krupnick about him) showed an interest in constructing a pair of order 10 Graeco-Latin squares, he learned about transversals and worked out a solution by building a Latin square of order 10 using 10 non-overlapping transversals. You can try to duplicate his feat using the hints (some of the transversals) that I give below. At the end you can also see Jay's solution.

The picture below shows an unfinished Latin square with 4 transversals drawn in. You should find and record (you will need this information later) each of the 4 transversals.

If you would like to see more transversals, click on the number you want to see:

Jay's solution to the 10 × 10 Graeco-Latin Square.