1

I generally have a decent understanding of Latin Squares, at least I think I do, and I'm just running through some practice questions but I've found one that has puzzled me.

When constructing Latin Squares I understand that we only want each symbol to appear once in each row and column and this is easily achieved by shifting the values once to the right each row.

So a standard $5\times5$ LS might look like this: $\begin{pmatrix} 0&1&2&3&4 \\ 4&0&1&2&3 \\ 3&4&0&1&2 \\ 2&3&4&0&1 \\ 1&2&3&4&0 \end{pmatrix}$

However, in this particular question I'm given the first two rows:

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

and I'm asked to construct a $7\times 7$ Latin Square. I'm slightly confused here, in fact I'm not even sure where to start, usually I would start with my left to right diagonal, since this would just be $0$'s but I think in this case my diagonal might have values other than $0$ so I can't start there.

I might be missing something simple but I just can't seem to figure this out, there's no clear pattern (that I can see) that I can follow to work out the rest of the square.

Any help would be greatly appreciated, thanks in advance.

Edit: I've just been given the solution Latin Square but I still don't know how they obtained it, see below and hopefully you can explain it to me because I'm still lost.

enter image description here

Maximus
  • 73
Sean E.
  • 23
  • 1
    You can start filling in the 0, 1, 2, 3 and 5 by shifting their position in each row, as for a standard Latin Square. I think that should uniquely determined where you can put the 4 and 6 – Aidan Apr 29 '22 at 19:59
  • @Aidan That seems not to work for the second last and last rows – Henry Apr 29 '22 at 20:10
  • ... but allowing 5 to go off-diagonal in the last two rows seems to allow a solution – Henry Apr 29 '22 at 20:20
  • I've just been given the solution, however no method is given, and I'm not sure if the method you mentioned works, I'll edit it into my question so you can see and hopefully explain what they did because even with the solution given to me I have no clue what they did to obtain it. – Sean E. Apr 30 '22 at 15:30

1 Answers1

1

I might be missing something simple but I just can't seem to figure this out, there's no clear pattern (that I can see) that I can follow to work out the rest of the square.

That seems correct: there is no clear pattern. Most Latin squares have no clear pattern (formally, almost all Latin squares have a trivial autoparatopism group). These two rows will have many completions.

In general, the Latin square completion problem is NP-complete (Colbourn 1984). However, in the special case where some number of rows are completely filled in, we can prove via Hall's Marriage Theorem that a completion exists (this is a standard exercise given to students; see e.g. these notes). If you want to complete two given rows to a Latin square, it's thus best to proceed row by row, this way you (mostly) won't "paint yourself into a corner".

If you're able to write a backtracking algorithm, you can find all the completions on a computer. Otherwise, since you only want one example, just fill it in row-by-row by hand, and if there's a clash, edit the row to correct it.

So maybe I'll try this:

$\begin{pmatrix} 0&1&2&3&4&5&6 \\ 4&0&1&2&3&6&5 \\ \color{blue} 1&\color{blue} 2&\color{blue} 3&\color{blue} 4&\color{blue} 5&\color{red} 6&\color{blue} 0 \\ \end{pmatrix}$

But there's a clash, so I might fix it like this:

$\begin{pmatrix} 0&1&2&3&4&5&6 \\ 4&0&1&2&3&6&5 \\ \color{blue} 1&\color{green} 6&\color{blue} 3&\color{blue} 4&\color{blue} 5&\color{green} 2&\color{blue} 0 \\ \end{pmatrix}$

And then I just keep going until I fill the square. Importantly, since Latin rectangles complete to Latin squares (as per the aforementioned Hall's Marriage Theorem), by proceeding row-by-row, I won't get near the end and discover "oh, this is impossible".

Rebecca J. Stones
  • 26,845