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.

Tags :

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"];