# For which divisors $a$ and $b$ of $n$ does there exist a Latin square of order $n$ that can be partitioned into $a \times b$ subrectangles?

There exists a Latin square of order $8$ which can be partitioned into $2 \times 4$ subrectangles: $$\begin{bmatrix} \color{red} 1 & \color{red} 2 & \color{red} 3 & \color{red} 4 & \color{purple} 5 & \color{purple} 6 & \color{purple} 7 & \color{purple} 8 \\ \color{red} 2 & \color{red} 3 & \color{red} 4 & \color{red} 1 & \color{purple} 6 & \color{purple} 7 & \color{purple} 8 & \color{purple} 5 \\ 7 & 8 & \color{blue} 1 & \color{blue} 2 & \color{blue} 3 & \color{blue} 4 & 5 & 6 \\ 8 & 5 & \color{blue} 2 & \color{blue} 3 & \color{blue} 4 & \color{blue} 1 & 6 & 7 \\ \color{pink} 5 & \color{pink} 6 & \color{pink} 7 & \color{pink} 8 & \color{green} 1 & \color{green} 2 & \color{green} 3 & \color{green} 4 \\ \color{pink} 6 & \color{pink} 7 & \color{pink} 8 & \color{pink} 5 & \color{green} 2 & \color{green} 3 & \color{green} 4 & \color{green} 1 \\ \color{orange} 3 & \color{orange} 4 & \color{brown} 5 & \color{brown} 6 & \color{brown} 7 & \color{brown} 8 & \color{orange} 1 & \color{orange} 2 \\ \color{orange} 4 & \color{orange} 1 & \color{brown} 6 & \color{brown} 7 & \color{brown} 8 & \color{brown} 5 & \color{orange} 2 & \color{orange} 3 \\ \end{bmatrix}$$ If we take the row-symbol parastrophe of this Latin square (i.e., replace each entry $(i,j,l_{ij})$ with $(l_{ij},j,i)$), then the entry colors define a decomposition of $K_{8,8}$ into $2$-regular spanning subgraphs of $K_{4,4}$. I would like to generalize this.

Question: For which divisors $a$ and $b$ of $n$ does there exist a Latin square of order $n$ that can be partitioned into $a \times b$ subrectangles?

(Note: We assume $a \leq b$. Subrectangles must have $b$ symbols. We don't assume that the boundaries of the subrectangles align.)

Observations:

• It's trivially possible when

• $a$ divides $b$ (construct a Latin square with blocks that are $b \times b$ subsquares)
• $a=1$ or $b=n$.
• The first non-trivial case is when $a=2$, $b=3$, and $n=6$. If my code is correct, then it is impossible (by exhaustive search). (I'm tempted to think this is just because the parameters are too small.) The best possible is $4$ subrectangles, which is straightforward to construct.

• My code found a random Latin square which gave an $a=2$, $b=5$, and $n=10$ example: $$\begin{bmatrix} \color{red} 7 & \color{red} 1 & 9 & 5 & \color{red} {10} & 4 & 8 & \color{red} 2 & 6 & \color{red} 3 \\ \color{red} 3 & \color{red} {10} & 5 & 8 & \color{red} 2 & 6 & 4 & \color{red} 1 & 9 & \color{red} 7 \\ \hline \color{blue} 9 & \color{blue} 6 & 4 & 7 & 1 & \color{blue} 2 & \color{blue} {10} & \color{blue} 3 & 5 & 8 \\ \color{blue} 6 & \color{blue} 3 & 7 & 1 & 5 & \color{blue} 9 & \color{blue} 2 & \color{blue} {10} & 8 & 4 \\ \hline \color{pink} 4 & 5 & 1 & \color{pink} 2 & \color{pink} 8 & 3 & 9 & \color{pink} 7 & \color{pink} {10} & 6 \\ \color{pink} 2 & 9 & 6 & \color{pink} {10} & \color{pink} 4 & 1 & 3 & \color{pink} 8 & \color{pink} 7 & 5 \\ \hline \color{purple} 1 & 2 & \color{purple} 8 & 3 & 7 & \color{purple} {10} & 6 & \color{purple} 5 & 4 & \color{purple} 9 \\ \color{purple} 8 & 4 & \color{purple} {10} & 6 & 3 & \color{purple} 5 & 7 & \color{purple} 9 & 2 & \color{purple} 1 \\ \hline \color{brown} 5 & 8 & \color{brown} 2 & 9 & 6 & 7 & \color{brown} 1 & 4 & \color{brown} 3 & \color{brown} {10} \\ \color{brown} {10} & 7 & \color{brown} 3 & 4 & 9 & 8 & \color{brown} 5 & 6 & \color{brown} 1 & \color{brown} 2 \\ \end{bmatrix}$$

• Hi Rebecca. Do you have an example where it isn't possible? Jan 23 '16 at 13:35
• I do now. I edited in some results of a computer search. Jan 24 '16 at 4:25