Latin Quarter: Colours and Latin Squares

I read about aesthetic uses of Latin Squares on John Cook’s site a few months ago. Since I maintain a resource to use colour tables in Igor Pro, I thought it would be fun to use Latin Squares to display colour tables for easy visualisation.

Briefly, I wrote some code to generate a 9 x 9 latin square and assigned the values 1 – 9 to a colour table wave. The results were nice.

Categorical tables (distinct colours, designed for ordinal values) display better than continuous tables (a gradient of colours), but the results are aesthetically pleasing. Using the code, you can quickly view and scroll through the tables – there are hundreds of colour tables available!

Down the rabbit hole

So far, things were straightforward. But then I got to thinking, since we want to see colour tables to display information, it would be nice to know that all possible pairs are represented in adjacent positions. This would tell us whether all combinations can be easily distinguished.

Can we make a latin square where all possible pairs are represented in adjacent squares?

My approach to these kinds of problems is always brute force rather than analytical. So I wrote some code to generate all latin squares of size n x n. And then tested them for whether they had all possible pairs on adjacent squares, that is, horizontal and vertical pairings. When I say all latin squares… there’s a lot of them. For example, at 6 x 6 there is already >800 million. This created something of a headache in itself…

Before revealing what happened. I’ll describe how the squares are generated and then illustrate the problem.

Imagine a 5 x 5 square. We fill the first column with a permutation of digits 1,2,3,4,5. For simplicity, we’ll list them in that order.

1 . . . .
2 . . . .
3 . . . .
4 . . . .
5 . . . .

Now we can “rotate” this column so it starts with 2 and place in the next column

1 2 . . .
2 3 . . .
3 4 . . .
4 5 . . .
5 1 . . .

And so on, until we fill the square.

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

This example is actually a special kind of latin square called a normalised latin square, where the numbers are in order in the first row and column.

From this seed, it is possible to generate a bunch more latin squares by permuting the rows and permuting the columns. We can do this without fear of generating clashes (repeated digits in a row or in a column). For example:

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

So you can see how it is possible to generate many squares. There are n! possibilities for the first column, and then n! permutations of rows and n! permutations of columns. There’s duplicates which need to be removed but nonetheless a large number of latin squares can be generated very quickly.

If you consider the normalised latin square above, you will see that this doesn’t have all possible pairs on adjacent squares. In fact, when you look at the density of pairs, it looks like this

  | 1 2 3 4 5
-------------
1 | x 8 0 0 8
2 | x x 8 0 0
3 | x x x 8 0
4 | x x x x 8
5 | x x x x x

So, clearly it is not the case that all latin squares have this property.

My guess was that the answer was 1/4. That is, a probability of 0.25 that a random latin square would have all pairings. This is because the number of pairings in a latin square (adjacent pairs) is:

and the number of unique pairs in a series is:

Which would mean that there are four opportunities for each unique pairing to feature. Hence my guess was 1 in 4 on average.

I am going to leave this post here and (hopefully) return with a solution next week.

Feel free to leave a comment if you know the answer!

—

The post title is taken from “Latin Quarter” by Naked City. I have two versions, I’ll go for the one from “Live Vol. 1 Knitting Factory 1989”.