proof of the completion of a certain kind of partial latin square

Question

About THE PROOF of the partial latin square has a completion. Let $r, n \in \mathbb N$, with $r \leq n$. Let $P$ be a PLS of order $n$, in which the first $r$ values are used in $n$ entries and the remaining $n − r$ values are not used at all. Then $P$ has a completion. Can this be proved as a Corollary of the latin rectangle proof by Hall’s Theorem?

Answer 1

Yes it can. Here's a proof by example: The partial Latin square $$L=\begin{array}{|ccccc|} \hline \cdot & 1 & \cdot & 2 & \cdot \\ 1 & \cdot & \cdot & \cdot & 2 \\ 2 & \cdot & \cdot & \cdot & 1 \\ \cdot & \cdot & 2 & 1 & \cdot \\ \cdot & 2 & 1 & \cdot & \cdot \\ \hline \end{array}$$ is equivalent to the set of entries (called the orthogonal array) $$\{(1,2,1),(1,4,2), (2,1,1),(2,5,2), (3,1,2),(3,5,1), (4,3,2),(4,4,1), (5,2,2),(5,3,1)\}.$$ Here, an entry e.g. $(5,3,1)$ says in row 5, column 3, we have symbol 1.

If we swap the first and third coordinates of the elements in the above set, we obtain $$\{(1,2,1),(2,4,1), (1,1,2),(2,5,2), (2,1,3),(1,5,3), (2,3,4),(1,4,4), (2,2,5),(1,3,5)\}$$ which is equivalent to the partial Latin square $$L^{(13)}=\begin{array}{|ccccc|} \hline 2 & 1 & 5 & 4 & 3 \\ 3 & 5 & 4 & 1 & 2 \\ \cdot & \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \cdot \\ \hline \end{array}.$$ This partial Latin square is called a parastrophe (or conjugate) of the original partial Latin square.

We know $L^{(13)}$ admits a completion by Hall's Theorem, which we denote $(L^{(13)})^c$, and thus $((L^{(13)})^c)^{(13)}$ is a completion of $L$.

To prove this formally, we'd need to show for an arbitrary such partial Latin square:

• $L^{(13)}$ is indeed a partial Latin square,
• the first two rows of $L$ are filled, and no other cells are filled,
• $((L^{(13)})^c)^{(13)}$ is a Latin square, and
• $L$ and $((L^{(13)})^c)^{(13)}$ agree in the non-empty cells of $L$.

Each of these checks should take about one sentence.

(Alternatively, we could prove this using Hall's Theorem directly in much the same way as for Latin rectangles.)