Explain why $4$ cannot be replaced by $5$ in part a)

Question

a) Construct a Latin square of order $8$ in which the submatrix formed from the first $4$ rows and $4$ columns is the addition table for $Z_4$.

b) Explain why $4$ cannot be replaced by $5$ in part a)

For a) my Latin square of order $8$ I had: \begin{bmatrix} 0 & 1 & 2 &3 &4&5&6&7\\ 1&2&3&0&5&4&7&6\\ 2&3&0&1&6&7&4&5\\ 3&0&1&2&7&6&5&4\\ 4&5&6&7&0&1&2&3\\ 5&6&7&4&1&2&3&0\\ 6&7&4&5&2&3&0&1\\ 7&4&5&6&3&0&1&2 \end{bmatrix}

For b) I was trying to show that $N(i) \geq r+s-n$ fails, where N(i) is the number of i's in the rxs rectangle, and rxs is the $4\times4$ submatrix, and n is the order of the Latin square. However, I have $4\geq 5+5-8 \Longrightarrow 4 \geq 3$ which is true and I'm stuck here

Answer 1

The formula $N(i) \geq r+s-n$ comes from Ryser's criteria about the extensibility of an $r \times s$ matrix to an $n \times n$ Latin square. It works for this problem, but your values of $N(i)$ are incorrect.

Ryser's criteria: Let $X$ be an $r \times s$ matrix with (a) no repeated symbols in rows nor columns, and (b) symbols from $\{0,1,\ldots,n-1\}$. Let $N(i)$ denote the number of copies of symbol $i$ in $X$. Then $X$ can be completed to a $n \times n$ Latin square if and only if $N(i) \geq r+s−n$ for all symbols $i \in \{0,1,\ldots,n-1\}$.

For the question, we have a $5 \times 5$ subsquare $X$, so $r=s=5$, and we're working in a Latin square of order $8$, so $n=8$. Since $X$ is a $5 \times 5$ subsquare, some symbols $i$ have $N(i)=5$ and others have $N(i)=0$.

For the symbols $i$ with $N(i)=0$, we have $N(i) = 0 \not\geq 2 = r+s−n$, so Ryser's criteria is not satisfied (the inequality needs to be true for all symbols); we conclude a $5 \times 5$ subsquare cannot be extended to a $8 \times 8$ Latin square. (But if we had a $4 \times 4$ subsquare instead, then the right-hand side is $0 = r+s−n$, and Ryser's criteria would be satisfied for all symbols.)

---

It's not necessary to use Ryser's criteria: we can just count instead. We break up an $n \times n$ Latin square with an $a \times a$ subsquare $X$ (where $a < n$) as follows: $$ \begin{bmatrix} X_{a \times a} & Y_{a \times (n-a)} \\ Z_{(n-a) \times a} & W_{(n-a) \times (n-a)} \end{bmatrix}. $$ (Here the indices indicate the dimensions of the blocks.)

Since $X$ is a subsquare, any symbol $x$ in $X$ occurs exactly $a$ times in $X$: exactly once in each row. Thus, $x$ does not occur in $Y$ (or we have two copies of $x$ in a row, contradicting the Latin property). The last $n-a$ columns each contain an $x$, and since they don't occur in $Y$, they must occur in $W$. We conclude that $W$ contains $n-a$ copies of $x$.

Since this is true for every symbol $x$ in $X$, the submatrix $W$ contains $n-a$ copies of each of the $a$ distinct symbols in $X$. So $W$ has exactly $(n-a)^2$ cells containing at least $(n-a)a$ symbols. This is a contradiction when $(n-a)^2 < (n-a)a$, or equivalently when $a > n/2$.

The general conclusion is that a Latin square of order $n$ cannot have a (Latin) subsquare of order $a$ satisfying $n/2 < a < n$. Ryser's criteria generalizes this result.

In particular, a Latin square of order $8$ cannot have a (Latin) subsquare of order $5$.