Greco-Latin Squares

A Greco-Latin square (Wikipedia link) is an n-by-n grid in which every cell contains a Latin letter and a Greek letter. There are n letters from each alphabet; each one occurs once in every row and once in every column. Additionally, each possible combination of Latin letter and Greek letter occurs exactly once. It's like a souped-up Sudoku grid.

These are occasionally useful to have. I've heard that people doing experimental design really like them, but only second-hand. They're one of many tools that are good to have in your toolbox when figuring out tournament designs, where you have a bunch of constraints like "you don't want to have the same pair of people play more than once" or "you don't want the same person to play at the same table more than once" or whatnot.

The reason I have a page of Greco-Latin squares and not of 2-factorizations of K_n or anything else is that some Greco-Latin squares are annoying to find. There's a few regular patterns; for odd n, there's a particularly nice one I'll tell you about at the end. But for several of these, the best way to get one is to copy it from a page like this one. I couldn't find a page like this one when I briefly needed to find one, so I decided to make it myself.

The large squares are probably not very useful in this form (maybe the text file format, where the letters are replaced by numbers, is more useful). But I decided to go up to 24, because that's when the Greek alphabet runs out.

Here is the one-line table of contents: 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24.

3-by-3 Greco-Latin square

Download as a text file

This square was generated using the rule for odd numbers at the end of this page.

4-by-4 Greco-Latin square

Download as a text file

I found this square by hand.

5-by-5 Greco-Latin square

Download as a text file

This square was generated using the rule for odd numbers at the end of this page.

Lame knockoff version of a 6-by-6 Greco-Latin square

There is no 6-by-6 Greco-Latin square. I found an interesting 6-by-6 square that cheats by allowing two Greek letters or two Latin letters to occupy the same cell. Otherwise, the solution (which is given below) satisfies all the constraints: each row and column has a single copy of each letter, and no pair of letters appears in the same cell more than once.

There is also, apparently, a "quantum solution" to this problem. I do not understand it, so I will not put it on this page, but I will leave a link to the paper: Thirty-six Entangled Officers of Euler: Quantum Solution to a Classically Impossible Problem by Rather et al.

7-by-7 Greco-Latin square

Download as a text file

This square was generated using the rule for odd numbers at the end of this page.

8-by-8 Greco-Latin square

Download as a text file

This square was generated using the finite field construction (Wikipedia link) over GF(8), the finite field of order 8. This is similar to the (a+b, a-b) rule for odd numbers, but we do calculations in the finite field. Also, instead of a-b, we must take a+bx for some other element of the field, because 1 and -1 are equal in GF(8).

9-by-9 Greco-Latin square

Download as a text file

This square was generated using the rule for odd numbers at the end of this page.

10-by-10 Greco-Latin square

Download as a text file

This square is taken from Bose, Shrikhande, and Parker's paper Further Results on the Construction of Mutually Orthogonal Latin Squares and the Falsity of Euler's Conjecture. Euler's conjecture was that, just as there is no solution for n=6, there is no solution for n=10, 14, 18, 22, and so on. This paper proved that actually, all n>6 have solutions.

Historically, Bose and Shrikhande were the first to disprove Euler's conjecture, by finding a 22-by-22 Greco-Latin square. Second, Parker found a construction for n=10 (which is found in his paper Orthogonal Latin Squares). Finally, all three of them together proved the general result.

11-by-11 Greco-Latin square

Download as a text file

This square was generated using the rule for odd numbers at the end of this page.

12-by-12 Greco-Latin square

Download as a text file

This square was generated by taking a product of the 3-by-3 and 4-by-4 solutions.

13-by-13 Greco-Latin square

Download as a text file

This square was generated using the rule for odd numbers at the end of this page.

14-by-14 Greco-Latin square

Download as a text file

This square was generated from the difference matrix in Todorov's paper Four Mutually Orthogonal Latin Squares of Order 14. From the title, you can see that using Todorov's construction here is overkill: it could be used to generate a "Greco-Latin-Cyrillic-Hebrew square" with four letters from four different alphabets in each cell, such that any two letters from different alphabets occur together exactly once!

(People think about large sets of mutually orthogonal Latin squares like this a lot. But I figured I'd stop at two alphabets for this page; it's already long enough.)

15-by-15 Greco-Latin square

Download as a text file

This square was generated using the rule for odd numbers at the end of this page.

16-by-16 Greco-Latin square

Download as a text file

This square was generated by taking a product of the 4-by-4 solution with itself.

17-by-17 Greco-Latin square

Download as a text file

This square was generated using the rule for odd numbers at the end of this page.

18-by-18 Greco-Latin square

Download as a text file

This square is taken from Wang's Ph.D. thesis On Self-Orthogonal Latin Squares and Partial Transversals of Latin Squares. As the title suggests, it's a self-orthogonal Latin square. This means that you can get the Greek letter in square (i, j) by taking the Latin letter in square (j, i) and switching alphabets.

19-by-19 Greco-Latin square

Download as a text file

This square was generated using the rule for odd numbers at the end of this page.

20-by-20 Greco-Latin square

Download as a text file

This square was generated by taking a product of the 4-by-4 and 5-by-5 solutions.

21-by-21 Greco-Latin square

Download as a text file

This square was generated using the rule for odd numbers at the end of this page.

22-by-22 Greco-Latin square

Download as a text file

This square is taken from Bose and Shrikhande's paper On the Construction of Sets of Mutually Orthogonal Latin Squares and the Falsity of a Conjecture of Euler. Historically, it's very exciting because Euler conjectured that Greco-Latin squares only exist when n is either odd or a multiple of four, and this 22-by-22 Greco-Latin square is the first counterexample found to that conjecture. Just as the 18-by-18 example earlier, this construction is also a self-orthogonal Latin square.

(I had to fix a typo in row 13, column 19 of Bose and Shrikhande's square, though. Understandable; I would have made some typos myself. But the squares on this page were all verified by computer program before I put them here.)

23-by-23 Greco-Latin square

Download as a text file

This square was generated using the rule for odd numbers at the end of this page.

24-by-24 Greco-Latin square

Download as a text file

This square was generated by taking a product of the 3-by-3 and 8-by-8 solutions.

General patterns

For n = 2k+1, there is a simple rule. Number the rows and columns from 0 to 2k, and use those numbers in place of the Greek and Latin letters. In the a^th row and b^th column, put the pair (a+b, a-b), where addition and subtraction are done modulo 2k+1: if the results are less than 0 or bigger than 2k, they wrap around. I generated all the odd-numbered Greco-Latin squares above in this way.

For many other values of n, there is a trickier rule. Suppose that n factors as pq, and you know how to make p-by-p and q-by-q Greco-Latin squares. Divide the numbers from 0 to n-1 into p blocks of q. Then take a p-by-p Greco-Latin square, and replace every cell of that square by a q-by-q table in the following way: replace a cell (a, b) by a copy of the q-by-q Greco-Latin square which uses the a^th block of q numbers for the first coordinate, and the b^th block of q numbers for the second coordinate.

In particular, once we find a 4-by-4 Greco-Latin square (easy to do by hand) and an 8-by-8 Greco-Latin square (which is trickier, but has an algebraic solution) we can use this product trick to find a 2^k-by-2^k Greco-Latin square for any k≥2. Then, by using the product trick again, we can find an n-by-n Greco-Latin square when n is any multiple of 4: just factor n into an odd number and a power of 2.

This much was known to Euler, who first studied Greco-Latin squares in general. However, the remaining values of n take considerably more effort to find a solution for (and the first two remaining values, n=2 and n=6, have no solutions). For this page, I did some research to find 10-by-10, 14-by-14, 18-by-18, and 22-by-22 solutions constructed by other people. I assume that the Bose, Shrikhande, and Parker paper cited above the 10-by-10 Greco-Latin square has a general algorithm, since it has a general proof of existence - but I haven't puzzled it out. For some large values of n, the product trick could be useful: for example, 30-by-30 can be solved using the 3-by-3 and 10-by-10 solutions.