[Math] Are there complete Graeco-Latin squares

combinatoricslatin-square

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.)

Best Answer

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}

Related Solutions

[Math] Overlaying Latin squares of order 4

You’re asking about mutually orthogonal Latin squares. The answer to the specific question is that yes, it is possible to find three mutually orthogonal Latin squares of order $4$, and that is the maximum. You’ll find a little more information and a few references at OEIS A001438.

[Math] How to count the latin squares of order 4

For order 4, there's not many. We can just enumerate them using a backtracking algorithm (essentially a depth first search: we proceed cell-by-cell, filling it in in all possible non-clashing ways, then continuing to the next cell). Here's some GAP code I just whipped up:

# order of the Latin square
n:=4;;

# number of Latin squares found so far
count:=0;

# start with the empty Latin square
L:=List([1..n],i->List([1..n],j->0));;

# function for trying all non-clashing symbols in cell (i,j)
ExtendPartialLatinSquare:=function(i,j)
  local s;

  # try symbol s in cell (i,j)
  for s in [1..n] do

    # symbol s already used in column j
    if(ForAny([1..i-1],k->L[k][j]=s)) then continue; fi;

    # symbol s already used in row i
    if(ForAny([1..j-1],k->L[i][k]=s)) then continue; fi;

    # no clashes arise
    L[i][j]:=s;

    # if L is a Latin square, count it;
    # otherwise try filling in the next empty cell
    if(j=n) then
      if(i=n) then
        count:=count+1;
        Display(L);
      else
        ExtendPartialLatinSquare(i+1,1);
      fi;
    else
      ExtendPartialLatinSquare(i,j+1);
    fi;

    L[i][j]:=0;

  od;
end;;

ExtendPartialLatinSquare(1,1);

Print("Found ",count," Latin squares of order ",n,"\n");

which displays the 576 Latin squares of order 4. (It even works for the 161280 Latin squares of order 5.)

Enumeration in this way is not so easy for larger orders (Sade's algorithm is the only method that's been used for orders 8 or more, but it's non-constructive [as it must be--the numbers are simply too large]).

Best Answer

Related Solutions

[Math] Overlaying Latin squares of order 4

[Math] How to count the latin squares of order 4

Related Question