Partial latin square with $\le n-1$ filled cells

How do we show that is $P$ if a $n\times n$ Latin square with $\le n-1$ filled cells, then $P$ can be completed to a proper Latin square?

(WHAT I HAVE DONE SO FAR: I have worked examples for $n=2,3,4$ but am unable to find a pattern that is rigorous, or any pattern for that pattern. A step-by step proof would be appreciated- or if you could tell me what facets here are of paramount importance when it comes to my observation.)

Could someone explain the inductive step in the link provided by Gerry Myerson in Theorem 5? I don't get it.

-

You have a partial Latin square $P$ of order $m+1$ with exactly $m$ filled cells, and you’re assuming that the number of distinct symbols in $P$ is greater than $\frac{m+1}2$. If each of these symbols occurred in more than one cell, they would fill more than $m+1$ cells altogether, contradicting the assumption that $P$ has just $m$ filled cells. Thus, some symbol $s$ appears in exactly one cell of $P$. Here’s an example with $m=4$; I’ve marked the back diagonal in red.

$$\begin{array}{|c|c|c|c|c|} \hline &&&5&\color{red}\cdot\\ \hline &&&\color{red}\cdot&\\ \hline &&\color{red}\cdot&3&\\ \hline &\color{red}\cdot&&&\\ \hline \color{red}5&2&&&\\ \hline \end{array}$$

At this point we use the second of the ‘key ideas’ identified at the top of p. 254 to conclude that the rows and columns of $P$ can be permuted to yield a new partial Latin square $Q$ of order $m+1$ with exactly $m$ filled cells in such a way that $s$ now lies on the back diagonal of $Q$, and the other filled cells of $Q$ lie above the back diagonal. Then we relabel the symbols so that $s$ becomes $m+1$. In my example I change the order of the rows from $12345$ to $13524$, bringing the lone $3$ to the back diagonal, relabel the $3$ as $5$, the $5$’s as $2$’s, and the $2$ as $3$ to get this:

$$\begin{array}{|c|c|c|c|c|} \hline &&&2&\color{red}\cdot\\ \hline &&&\color{red}5&\\ \hline 2&3&\color{red}\cdot&&\\ \hline &\color{red}\cdot&&&\\ \hline \color{red}\cdot&&&&\\ \hline \end{array}$$

The next step is to delete the $m+1$ on the back diagonal and the last row and last column. Note that the only cells in the last row and column that could possibly be filled at this point are the ones in the upper right and lower left corners, on the back diagonal, so the only symbol deleted in this step is the $m+1$ on the back diagonal. In the example above we’d be left with the following partial Latin square of order $4$:

$$\begin{array}{|c|c|c|c|c|} \hline &&&\color{blue}2\\ \hline &&&\color{red}\cdot\\ \hline \color{blue}2&\color{blue}3&\color{red}\cdot&\\ \hline &\color{red}\cdot&&\\ \hline \end{array}$$

The red dots mark the cells that were on the back diagonal of $Q$; the one just below the $2$ in the upper right corner is where the $\color{red}5$ was in $Q$. The blue cells are the entries retained from $Q$.

We now have a partial Latin square of order $m$ with $m-1$ filled cells; by the induction hypothesis, it can be completed to a Latin square $L$. In my example $L$ might be this Latin square:

$$\begin{array}{|c|c|c|c|c|} \hline 1&4&3&\color{blue}2\\ \hline 3&2&4&1\\ \hline \color{blue}2&\color{blue}3&1&4\\ \hline 4&1&2&3\\ \hline \end{array}$$

Now construct the partial Latin square $P(L)$ of order $m+1$ as described at the bottom of p. 253 and top of p. 254: erase every symbol below the back diagonal of $L$ and add an empty last column and last row to get a partial Latin square of order $m+1$, and fill the back diagonal of this partial Latin square with the symbol $m+1$. In my example this produces the following partial Latin square $P(L)$, where the blue entries are those retained (or, in the case of the $5$, reintroduced) from $Q$:

$$\begin{array}{|c|c|c|c|c|} \hline 1&4&3&\color{blue}2&5\\ \hline 3&2&4&\color{blue}5\\ \hline \color{blue}2&\color{blue}3&5&\\ \hline 4&5&&\\ \hline 5\\ \hline \end{array}$$

Next we apply the other of the two ‘key ideas’ mentioned at the top of the page to conclude that $P(L)$ can be completed.

One possible completion is this:

$$\begin{array}{|c|c|c|c|c|} \hline 1&4&3&\color{blue}2&5\\ \hline 3&2&4&\color{blue}5&1\\ \hline \color{blue}2&\color{blue}3&5&1&4\\ \hline 4&5&1&3&2\\ \hline 5&1&2&4&3\\ \hline \end{array}$$

The blue cells, as before, show the cells retained from $Q$.

The final step is to reverse the relabelling and rearrangement of the rows and columns that took us from the original $P$ to $Q$. I changed $3$ to $5$, $5$ to $2$, and $2$ to $3$, so I must now change $3$ to $2$, $2$ to $5$, and $5$ to $3$:

$$\begin{array}{|c|c|c|c|c|} \hline 1&4&2&\color{blue}5&3\\ \hline 2&5&4&\color{blue}3&1\\ \hline \color{blue}5&\color{blue}2&3&1&4\\ \hline 4&3&1&2&5\\ \hline 3&1&5&4&2\\ \hline \end{array}$$

I also have to reverse the permutation of the rows; this, finally, yields this Latin square:

$$\begin{array}{|c|c|c|c|c|} \hline 1&4&2&\color{blue}5&3\\ \hline 4&3&1&2&5\\ \hline 2&5&4&\color{blue}3&1\\ \hline 3&1&5&4&2\\ \hline \color{blue}5&\color{blue}2&3&1&4\\ \hline \end{array}$$

This is clearly a completion of the original partial Latin square $P$.

Does this help, or were you more worried about the proofs of the two ‘key ideas’, for which the authors refer you to a paper by Lindner?

-
THis certainly helps! Thank you. I was, however, also concerned about the Lindner references. Also, when you say: Next we apply the other of the two ‘key ideas’ mentioned at the top of the page to conclude that P(L) can be completed: which key ideas do you mean? – Xuan Huang Jul 14 '12 at 5:47
@Danielle: Right below the diagrams of $P$ and $L(P)$ at the top of page 254 is the sentence ‘The proof of Smetaniuk’s result relies on two key ideas’. The author’s then give these ideas as a pair of bullet points. I’ll think about how these two statements might be proved; I suspect that it’s not horrendously difficult but may be a bit messy to describe. – Brian M. Scott Jul 14 '12 at 5:56
Brian- that would be fantastic. THank you so much. A lot of the things in Latin squares construction wise go by axiomatically almost, and a lot of things are provable but many are messy, so thanks. – Xuan Huang Jul 14 '12 at 6:14

This is discussed in Chapter 32 of Proofs From The Book. The authors write, "Bohdan Smetaniuk's proof from 1981 ... is a beautiful example of just how subtle an induction proof may be...."

This paper also gives Smetaniuk's proof.

-
Where in the link can I find the proof? – Xuan Huang Jul 11 '12 at 6:26
The result is Theorem 5 on page 254 (but the proof refers back to earlier parts of the paper). – Gerry Myerson Jul 11 '12 at 6:51
Could you explain the inductive step, please? I don't understand it. A visual aid might be nice... – Xuan Huang Jul 12 '12 at 4:23