Modified latin square

306 Views Asked by At

I'm trying to build a variation of a latin square.

In a latin square of size $n$, every row and every column contains a number from $1$ to $n$ exactly once. Given arbitrary $a$ and $b$ such that $n=a\cdot b$, I would like to build a size $n$ square where given an arbitrary row or column, it contains $b$ distinct numbers and each number appears exactly $a$ times. Additionally, any given number used in the square must appear exactly $n$ times in the entire square, as in the original latin square problem, except for the case where that number appears on the diagonal, in which case every diagonal occurrence is counted twice (with this counting the number of occurrences should be $n$ for every number). This means that the numbers are generally not the same across rows/columns for most values of $a,b$.

I would be particularly interested in the special case where the resulting square is symmetric.

Does anyone have any idea of how complicated the problem is (building a single instance of a latin square of size $n$ is trivial) and what previous work I could look at?

EDIT: As suggested by Jyrki Lahtonen, it is possible that the construction is not possible for arbitrary values of $a,b$. I'm mainly interested in cases where $a<b$, in particular the $b=a+1$ case, where $n$ allows it.

As an example, for $n=6,a=2,b=3$, you can build the following (symmetric) square: $$ \begin{array}{ccccccccc} 2&0&0&1&1&2\\ 0&4&0&3&4&3\\ 0&0&5&5&6&6\\ 1&3&5&5&1&3\\ 1&4&6&1&4&6\\ 2&3&6&3&6&2 \end{array} $$

2

There are 2 best solutions below

1
On

You can take a normal Latin square and reduce each number modulo $a$

1
On

This is not an answer but an observation, as I cannot use TeX in comments.

Starting from your constraints, and trying to find something symmetric, I came up with this square which is strictly equivalent to yours (with permutation of coordinates and permutation of symbols).

I have to stress, that as in your example, there are 7 different symbols used for this 6x6 square. So that 36 = 3*(2+2)+4*(6). So on this account the similarity with latin squares is even more stretched.

$$ \begin{array}{cccccc} 1 & 1 & 4 & 5 & 4 & 5 \\ 1 & 1 & 0 & 6 & 6 & 0 \\ 4 & 0 & 2 & 2 & 4 & 0 \\ 5 & 6 & 2 & 2 & 6 & 5 \\ 4 & 6 & 4 & 6 & 3 & 3 \\ 5 & 0 & 0 & 5 & 3 & 3 \end{array} $$

Symbols having at least one member on the diagonal are grouped as squares. It would change from squares to other constellations with a different n=a*b

$$ \begin{array}{cccccc} \bf 1 &\bf 1 & 4 & 5 & 4 & 5 \\ \bf 1 &\bf 1 & 0 & 6 & 6 & 0 \\ 4 & 0 &\bf 2 &\bf 2 & 4 & 0 \\ 5 & 6 &\bf 2 &\bf 2 & 6 & 5 \\ 4 & 6 & 4 & 6 &\bf 3 &\bf 3 \\ 5 & 0 & 0 & 5 &\bf 3 &\bf 3 \end{array} $$

There is an interesting mix of periodicity and mirror symmetry in this result as in various constructions I tried.

For this particular square, the non-diagonal symbols appear as $4545/0660$, $4040/5665$ and $4646/5005$, i.e. as $abab/xyyx$

Latin squares have many interpretations. It would probably valuable to have at least one for your new combinatorial object. Perhaps do you have one already ?