18
$\begingroup$

Are there two orthogonal complete Latin squares of any order greater than 1? If so, what is the smallest order for which they exist?

(A Latin square of order $n$ is an $n\times n$ array of symbols $\{ s_1\ldots s_n \}$ such that each of the symbols appears exactly once in each row and in each column. Two Latin squares $L_{ij}$ and $G_{ij}$ are orthogonal if each of the $n^2$ pairs $(L_{ij}, G_{ij})$ is distinct; such a pair together form a Graeco-Latin square. A Latin square $L_{ij}$ is complete if each of the $n\cdot(n-1)$ pairs $(L_{ij}, L_{i+1,j})$ is distinct and if each of the $n\cdot(n-1)$ pairs $(L_{ij}, L_{i,j+1})$ is distinct.)

  • 0
    I would like to recommend an article, titled "Tuscan Squares" in The CRC Handbook of Combinatorial Designs, CRC Press, 2006, for more general situations than complete latin squares.2016-03-04

3 Answers 3

48

The problem is open no longer. It turns out that there are many pairs of orthogonal complete Latin squares of order 12. Here is one example. I also know how to build some bigger ones.

\begin{pmatrix} 1 & 2 & 5 & 7 & 4 & 8 & 9 &11 & 6 &12 &10 & 3\\ 7 &12 & 9 & 3 &10 & 2 & 1 & 5 & 8 & 4 & 6 &11\\ 2 & 3 & 6 & 8 & 5 & 9 &10 &12 & 1 & 7 &11 & 4\\ 8 & 7 &10 & 4 &11 & 3 & 2 & 6 & 9 & 5 & 1 &12\\ 10 & 9 &12 & 6 & 7 & 5 & 4 & 2 &11 & 1 & 3 & 8\\ 3 & 4 & 1 & 9 & 6 &10 &11 & 7 & 2 & 8 &12 & 5\\ 9 & 8 &11 & 5 &12 & 4 & 3 & 1 &10 & 6 & 2 & 7\\ 12 &11 & 8 & 2 & 9 & 1 & 6 & 4 & 7 & 3 & 5 &10\\ 11 &10 & 7 & 1 & 8 & 6 & 5 & 3 &12 & 2 & 4 & 9\\ 6 & 1 & 4 &12 & 3 & 7 & 8 &10 & 5 &11 & 9 & 2\\ 4 & 5 & 2 &10 & 1 &11 &12 & 8 & 3 & 9 & 7 & 6\\ 5 & 6 & 3 &11 & 2 &12 & 7 & 9 & 4 &10 & 8 & 1 \end{pmatrix}

\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &10 &11 &12\\ 6 & 4 &11 & 2 & 8 & 1 & 9 & 5 & 7 &12 & 3 &10\\ 4 &10 & 7 & 1 &11 & 9 & 3 &12 & 6 & 2 & 5 & 8\\ 9 & 1 & 5 &10 &12 & 4 & 6 &11 & 3 & 8 & 7 & 2\\ 2 &12 & 9 & 6 & 3 & 7 &11 &10 & 1 & 4 & 8 & 5\\ 3 & 9 &12 & 8 & 2 &10 & 4 & 7 & 5 &11 & 6 & 1\\ 10 & 8 & 6 & 9 & 7 & 3 & 5 & 2 & 4 & 1 &12 &11\\ 5 & 3 & 2 &11 & 1 & 8 &10 & 6 &12 & 7 & 4 & 9\\ 11 & 7 &10 & 5 & 4 &12 & 2 & 9 & 8 & 3 & 1 & 6\\ 8 &11 & 4 & 3 & 6 & 5 &12 & 1 &10 & 9 & 2 & 7\\ 7 & 6 & 8 &12 &10 & 2 & 1 & 3 &11 & 5 & 9 & 4\\ 12 & 5 & 1 & 7 & 9 &11 & 8 & 4 & 2 & 6 &10 & 3 \end{pmatrix}

  • 3
    Thank you, and congratulations!2012-05-18
9

Further to what Doug wrote above, I can confirm that there is no pair of orthogonal complete latin squares of order 10 or less. There are 26088 normalized complete latin squares of order 10 (the next number for Doug's table). Of these only 64 possess an orthogonal mate, and none of those mates are themselves complete latin squares. You can download data on all these squares from my homepage at:

http://users.monash.edu.au/~iwanless/data/RCLS/index.html

  • 0
    Welcome to math.stackexcha$n$ge.com!2012-05-08
6

As far as I know, this is still an open problem. It was posed by Keedwell in "Some problems concerning complete Latin squares" (1974).

Observation: If L and M are orthogonal complete Latin squares, then we can permute the symbols in L (or M) without affecting the orthogonality property, nor the completeness property. Hence, we can assume that the first row of L and M are in order (i.e. "normalised"). I wrote some code to check up to $8 \times 8$ squares, and found: \[ \begin{array}{|r|rrrrrrrr|} \hline n & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\\\ \text{nr. normalised complete Latin squares} & 1 & 0 & 2 & 0 & 8 & 0 & 192 & 0 \\\\ \hline \end{array} \]

None of the Latin squares encountered were orthogonal.

My guess is they exist, as there doesn't seem to be any reason for them not to exist. I suspect they don't exist for small orders simply because there's too many conditions placed on them.

Here's my C code below:

#include   /* change this to the order of your latin square */ #define ORDER_LATIN_SQUARE 9 #define MAX_NR_LATIN_SQUARES 100000  int n; int latin[ORDER_LATIN_SQUARE][ORDER_LATIN_SQUARE]; int latin2[ORDER_LATIN_SQUARE][ORDER_LATIN_SQUARE]; int complete_latin_squares[MAX_NR_LATIN_SQUARES][ORDER_LATIN_SQUARE][ORDER_LATIN_SQUARE]; int nr_complete_latin_squares=0; int nr_orthogonal_pairs_of_complete_latin_squares=0;  void print_latin_square() {   for(int i=0;i0 && i==1 && j==0) { printf("%f percent complete.\n",(float) (s-1)/(n-2)*100); }      for(int c=0;c0) {       int t=latin[i][j-1];       for(int r=0;r0) {       int t=latin[i-1][j];       for(int r=0;r

Here's a GAP version of the same program (it's slower, but it's nice to check the results are correct):

SetOfCompleteLatinSquares:=[];  GenerateCompleteLatinSquaresBacktrackingAlgorithm:=function(L,i,j,n)   local s,k,S1,S2,try_symbol;    # S1 is the set of extant pairs (l[r][c],l[r][c+1])    S1:=List([1..i-1],r->List([1..n-1],c->[L[r][c],L[r][c+1]]));   S1:=Concatenation(S1);   S1:=Concatenation([S1,List([1..j-2],c->[L[i][c],L[i][c+1]])]);    # S2 is the set of extant pairs (l[r+1][c],l[r][c])    S2:=List([2..i-1],r->List([1..n],c->[L[r-1][c],L[r][c]]));   S2:=Concatenation(S2);   if(i>1) then S2:=Concatenation([S2,List([1..j-1],c->[L[i-1][c],L[i][c]])]); fi;    for s in [1..n] do     try_symbol:=true;     for k in [1..j-1] do if s=L[i][k] then try_symbol:=false; fi; od; # row clash     for k in [1..i-1] do if s=L[k][j] then try_symbol:=false; fi; od; # column clash     if(j>1) then if([L[i][j-1],s] in S1) then try_symbol:=false; fi; fi; # row pair clash     if(i>1) then if([L[i-1][j],s] in S2) then try_symbol:=false; fi; fi; # column pair clash      if(try_symbol) then       L[i][j]:=s;       if(i=n and j=n) then         # Print(L,"\n");         Append(SetOfCompleteLatinSquares,[Immutable(L)]);       elif(j=n) then         GenerateCompleteLatinSquaresBacktrackingAlgorithm(L,i+1,1,n);       else         GenerateCompleteLatinSquaresBacktrackingAlgorithm(L,i,j+1,n);       fi;       L[i][j]:=0;     fi;   od; end;;  GenerateCompleteLatinSquares:=function(n)   local L,j;   L:=List([1..n],i->List([1..n],j->0));   for j in [1..n] do L[1][j]:=j; od; # assumes the first row is 1,2,..,n    SetOfCompleteLatinSquares:=[];   GenerateCompleteLatinSquaresBacktrackingAlgorithm(L,2,1,n);   return SetOfCompleteLatinSquares; end;; 
  • 0
    The code just finished the n=9 case (it took about 2 days on my home computer).2012-03-20