Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

up vote 7 down vote accepted

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.

matrix([ [ 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]]);

matrix([ [ 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]]);

share|improve this answer
2  
Fantastic answer. –  Potato May 18 '12 at 9:10
1  
Thank you, and congratulations! –  MJD May 18 '12 at 11:13
add comment

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

share|improve this answer
    
This is a wonderful resource. Thanks very much. –  MJD May 8 '12 at 3:16
    
Welcome to math.stackexchange.com! –  Douglas S. Stones May 8 '12 at 5:17
add comment

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 <stdio.h>

/* 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;i<n;i++) {
    for(int j=0;j<n;j++) {
      printf("%d ",latin[i][j]);
    }
    printf(" ");
  }
  printf("\n");
}

void print_latin_square2() {
  for(int i=0;i<n;i++) {
    for(int j=0;j<n;j++) {
      printf("%d ",latin2[i][j]);
    }
    printf(" ");
  }
  printf("\n");
}

int are_orthogonal_latin_squares() {
  for(int i=0;i<n;i++) {
    for(int j=0;j<n;j++) {
      for(int r=0;r<n;r++) {
        for(int c=0;c<n;c++) {
          if(!(i==r && j==c)) {
            if(latin[i][j]==latin[r][c] && latin2[i][j]==latin2[r][c]) { return 0; }//i,j,r,c
          }
        }
      }
    }
  }
  return 1;
}

/*
backtracking algorithm for generating complete latin squares
proceeds row-by-row, then column-by-column
never introduces one of the following clashes:
- two symbols in the same row
- two symbols in the same column
- two order pairs of symbols (l(i,j),l(i,j+1))=(l(r,c),l(r,c+1))
- two order pairs of symbols (l(i+1,j),l(i,j))=(l(r,c),l(r+1,c))
*/

void generate_complete_latin_squares_backtracking_algorithm(int i, int j) {
  for(int s=0;s<n;s++) {
    if(s>0 && i==1 && j==0) { printf("%f percent complete.\n",(float) (s-1)/(n-2)*100); }

    for(int c=0;c<j;c++) { if(latin[i][c]==s) { goto dont_use_this_symbol; } } /* s would occur twice in row i */
    for(int r=0;r<i;r++) { if(latin[r][j]==s) { goto dont_use_this_symbol; } } /* s would occur twice in column j */

    /* check for (latin[i][j-1],s) occuring already */
    if(j>0) {
      int t=latin[i][j-1];
      for(int r=0;r<i;r++) {
        for(int c=0;c<n-1;c++) {
          /* (latin[i][j-1],s) occurs as (latin[r][c],latin[r][c+1]) where r<i */
          if(latin[r][c]==t && latin[r][c+1]==s) { goto dont_use_this_symbol; }
        }
      }
      for(int c=0;c<j-1;c++) {
        /* (latin[i][j-1],s) occurs as (latin[r][c],latin[r][c+1]) where r=i and c<j-1 */
        if(latin[i][c]==t && latin[i][c+1]==s) { goto dont_use_this_symbol; }
      }
    }

    /* check for (latin[i-1][j],s) occuring already */
    if(i>0) {
      int t=latin[i-1][j];
      for(int r=0;r<i;r++) {
        for(int c=0;c<n;c++) {
          /* (latin[i-1][j],s) occurs as (latin[r][c],latin[r+1][c]) where r<i-1 */
          if(latin[r][c]==t && latin[r+1][c]==s) { goto dont_use_this_symbol; }
        }
      }
      for(int c=0;c<j-1;c++) {
        /* (latin[i-1][j],s) occurs as (latin[r][c],latin[r+1][c]) where r=i-1 and c<j */
        if(latin[i][c]==t && latin[i][c+1]==s) { goto dont_use_this_symbol; }
      }
    }

    /* trying symbol s for entry l[i][j] */
    latin[i][j]=s;
    if(i==n-1 && j==n-1) {
      for(int r=0;r<n;r++) { for(int c=0;c<n;c++) {
        complete_latin_squares[nr_complete_latin_squares][r][c]=latin[r][c];
      } }
      print_latin_square();

      /* checks if any of the earlier-discovered complete latin squares are othogonal */
      for(int t=0;t<nr_complete_latin_squares;t++) {
        for(int r=0;r<n;r++) { for(int c=0;c<n;c++) { latin2[r][c]=complete_latin_squares[t][r][c]; } }
        if(are_orthogonal_latin_squares()) {
          printf("Orthogonal complete Latin squares found!\n");
          print_latin_square();
          print_latin_square2();
          printf("\n");
          nr_orthogonal_pairs_of_complete_latin_squares++;
        }
      }
      nr_complete_latin_squares++;
      goto dont_use_this_symbol;
    }
    if(j==n-1) {
      generate_complete_latin_squares_backtracking_algorithm(i+1,0);
      goto dont_use_this_symbol;
    }
    generate_complete_latin_squares_backtracking_algorithm(i,j+1);

    dont_use_this_symbol: 
    latin[i][j]=-1;
  }
}

int main() {
  n=ORDER_LATIN_SQUARE;

  for(int j=0;j<n;j++) { latin[0][j]=j; } /* assumes the first row = 0,1,..,n */
  for(int i=1;i<n;i++) { for(int j=0;j<n;j++) { latin[i][j]=-1; } } /* -1 denotes an empty cell */
  generate_complete_latin_squares_backtracking_algorithm(1,0);

  printf("\nFound %d complete Latin squares of order %d.\n",nr_complete_latin_squares,n);
  printf("Found %d pairs of orthogonal complete Latin squares of order %d.\n",nr_orthogonal_pairs_of_complete_latin_squares,n);

  return 1;
}

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;;
share|improve this answer
    
Thanks for this wonderful answer, particularly for the Keedwell reference.. I will wait 24 hours to make sure nobody else response and then accept it. –  MJD Mar 18 '12 at 0:33
    
No worries, it's an interesting question. Note: there was a typo in the table, which I fixed. –  Douglas S. Stones Mar 18 '12 at 5:03
    
Funny thing: I just happened to download a copy of the Computational Problems in Abstract Algebra anthology of 1970, edited by John leech, and when I opened it at random the first thing I saw was a paper by Keedwell about Latin squares. As far as I know I had never heard of him before your answer, and now he's popped up twice in a week. –  MJD Mar 18 '12 at 16:43
    
The code just finished the n=9 case (it took about 2 days on my home computer). –  Douglas S. Stones Mar 20 '12 at 8:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.