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

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.

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

Updated November 19, 2017 01:20 AM

- Serverfault Query
- Superuser Query
- Ubuntu Query
- Webapps Query
- Webmasters Query
- Programmers Query
- Dba Query
- Drupal Query
- Wordpress Query
- Magento Query
- Joomla Query
- Android Query
- Apple Query
- Game Query
- Gaming Query
- Blender Query
- Ux Query
- Cooking Query
- Photo Query
- Stats Query
- Math Query
- Diy Query
- Gis Query
- Tex Query
- Meta Query
- Electronics Query
- Stackoverflow Query
- Bitcoin Query
- Ethereum Query