Existence of Latin Squares without symmetry around main-diagonal

by Paul   Last Updated March 14, 2019 20:20 PM - source

A Latin square of order $n$ is a matrix $L$ with entries from $[n] \equiv \{0, \dots, n-1\}$ such that each row and column contains every symbol from $[n]$ once.

For which orders does there exist a Latin square such that $L(i,j) \neq L(j,i)$ for all $i \neq j$? For $n=2$, none exists. For $n=3$, the following exists: \begin{pmatrix} 0 & 1 & 2 \\ 2 & 0 & 1 \\ 1 & 2 & 0 \end{pmatrix} However, already for $n=4$, I'm unable to construct such a Latin square and I'm starting to wonder whether this is for a deeper reason.

Ideally, I'm interested in the answer to the question for Latin squares with the additional constraint that $L(i,i) = L(j,j)$ for all $i,j$, but lets maybe do one thing after the other.



Answers 1


I found the following for $n = 4$:

\begin{pmatrix} 0 & 3 & 2 & 1 \\ 1 & 2 & 3 & 0 \\ 3 & 0 & 1 & 2 \\ 2 & 1 & 0 & 3 \end{pmatrix}

Note that both diagonals contain all $0..n-1$ values.

Another solution with that property:

\begin{pmatrix} 1 & 3 & 0 & 2 \\ 2 & 0 & 3 & 1 \\ 3 & 1 & 2 & 0 \\ 0 & 2 & 1 & 3 \end{pmatrix}

For $n = 8$:

\begin{pmatrix} 1 & 6 & 5 & 2 & 0 & 4 & 3 & 7 \\ 3 & 2 & 4 & 1 & 5 & 7 & 6 & 0 \\ 4 & 3 & 0 & 6 & 1 & 5 & 7 & 2 \\ 5 & 0 & 1 & 7 & 4 & 6 & 2 & 3 \\ 2 & 4 & 7 & 3 & 6 & 1 & 0 & 5 \\ 6 & 5 & 2 & 0 & 7 & 3 & 4 & 1 \\ 7 & 1 & 3 & 4 & 2 & 0 & 5 & 6 \\ 0 & 7 & 6 & 5 & 3 & 2 & 1 & 4 \end{pmatrix}

In fact, for all $n \gt 2$ I tried, MiniZinc found a solution using the following model:

include "globals.mzn";

int: n = 8;

set of int: N = 0..n-1;

array[N, N] of var N: square;

%  main diagonal
constraint
    alldifferent([square[k, k] | k in N]);

%  2nd diagonal
constraint
    alldifferent([square[k, n-k-1] | k in N]);

constraint
  forall(row in N) (
    alldifferent([square[row, col] | col in N])
  );

constraint
  forall(col in N) (
    alldifferent([square[row, col] | row in N])
  );

constraint
  forall(i, j in N where i != j) (
    square[i, j] != square[j, i]
  );

output
[
  if  j = 0 then "\n" else " " endif ++
    show(square[i,j]) 
  | i,j in N
] ++ ["\n"];
Axel Kemper
Axel Kemper
March 14, 2019 20:03 PM

Related Questions


Link between prime numbers and 3x3 magic squares

Updated July 03, 2017 12:20 PM




Interdimensional Matrix Transformations?

Updated July 01, 2018 17:20 PM