Hope Garcia and Margot Reed – Applications of Latin Squares

This is generally a good discussion of Latin squares and their applications. However, there are a few things that are either not explained very clearly, or where I’m not sure you completely understood what the point of the source discussion you were looking at was (see in particular the comments below). Writing about mathematics is different (and harder) than other sorts of writing because you have to be careful to state things so precisely.

Specific Comments

1) Pages 1, 2, 7, 8–The distinction between magic squares and Latin squares is not very clear from what you write in the first historical discussion (you fixed this in the presentation and later on page 6, but not here). They’re not the same thing because all the entries in a magic square are distinct (usually the integers 1, 2, …, n^{2}). In Latin squares, on the other hand, the same n entries are reused on every row. As you discuss later, though, Latin squares and magic squares are very closely related (as in the paper by Euler that I sent you after the run-through of your talk). You discuss one way he mentioned on your page 8. But there are other ways too that do not require the Latin squares used in the construction to be “diagonal” Latin squares. Here’s another construction: For instance, if n = 5 and

L = ( \begin{matrix}a & b & c & d & e \\ b & c & d & e & a \\ c & d & e & a & b \\ d & e & a & b & c \\ e & a & b & c & d \end{matrix} )  and  L′ = ( \begin{matrix}E & D & C & B & A \\ A & E & D & C & B \\ B & A & E & D & C \\ C & B & A & E & D \\ D & C & B & A & E \end{matrix} )

are any Latin square matrices with a+b+c+d+e = 5e and A+B +C +D +E = 5E, and {a, b, c, d, e} = {1, 2, 3, 4, 5}, {A, B, C, D, E} = {0, 1, 2, 3, 4}, then L and L′ are mutually orthogonal Latin squares (L is of the cyclic type and L′ is cyclic but in reverse order on each row), and moreover the linear combination L + 5L′ (using arithmetic in Z) is a magic square. Something similar works for any odd n. (This is a nice exercise – try it!) Euler also discussed yet other, different constructions.

2) Page 3–It would be better to say that every row (and every column) of a Latin square is a permutation of the set S of symbols. The permutations corresponding to different rows can be different, so your statement ”Latin Squares are examples of permutations of the n elements contained in S” is not exactly right.

3) Page 3 – I don’t quite understand what you are saying about the generalized pigeonhole principle and Latin squares toward the bottom of the page. It’s true that k = m means there don’t have to be any duplicates (not necessarily any pigeonholes getting more than one pigeon). But it’s not actually that complicated. If you have |S| = n, then each element of S has to appear exactly once in each row and column of an n × n Latin square (same comment about the corresponding place in the presentation – it was not clear there either).

4) Page 4 – In the definition of mutually orthogonal Latin squares, what you mean by “the n^{2} pairs” isn’t too clear because you haven’t described where the pairs come from. The idea, of course, is that you want to “overlay” or take the table of pairs of elements in corresponding positions. For instance with the Latin squares L and L′ from comment 1 above, you would have

L × L′ = ( \begin{matrix}(a, E) & (b, D) & (c, C) & (d, B) & (e, A) \\ (b, A) & (c, E) & (d, D) & (e, C) & (a, B) \\ (c, B) & (d, A) & (e, E) & (a, D) & (b, C) \\ (d, C) & (e, B) & (a, A) & (b, E) & (c, D) \\ (e, D) & (a, C) & (b, B) & (c, A) & (d, E) \end{matrix} )

5) Page 5 – the “banquet” example you give is OK, but it presupposes that the department is evenly split into four groups of equal sizes in both the breadth area and the length of service components. There is also another aspect that isn’t really addressed by the Latin square structure and that’s who sits with whom. The orthogonal Latin squares just deal with the combinations of breadth area and years of experience, not with the actual seating arrangements for the banquet. I’m not seeing how you are making up the tables for the banquet, or am I misunderstanding what you meant?

6) Page 6 – the xx in Euler’s notation is what we would write as x^{2} :) This was a holdover from the days before the introduction of numerical exponents to represent powers of numbers.

7) Page 11 – the Sudoku X, Even-Odd Sudoku, and Colored Sudoko variations are interesting. I think they are essentially different ways of presenting the known information to the puzzle solver that probably allow fewer of the squares to be given at the start. For the puzzle designer, they represent additional constraints on the construction of the puzzle.

8) Page 12 – I really don’t understand what you are saying here about Sudoku solution algorithms. A ”rejection algorithm” based on randomly generating permutations seems much too brute-force to be practicable as a way of solving Sudoku puzzles. That’s not what you described in your presentation either, so I’m not sure whether you really understand what this algorithm is saying. Note that in the presentation, you were analyzing the constraints on the unknown squares in a row or column based on the squares already known in a row or column, which is a much smarter approach than randomly sampling permutations to see if the Sudoku or Latin square condition is satisfied. Especially after the puzzle is partially filled in, there is a lot of extra information about excluded potential solutions that can be exploited.

9) The definition of quasi-complete Latin squares you give is confusing. I think the better way to say it is that every unordered pair p, q of symbols appear in adjacent squares either as p, q or as q, p twice in the rows and twice in the columns. You said “quasi-complete Latin squares are defined as pairs of adjacent entries, L_{i,j} and L_{i,j+1}, and L_{i,j} and Li + 1, j, that can appear in either order, twice in rows and twice in columns.” That does not mean the same thing even though it includes (most of) the same “ingredients.” The L_{i,j} and L_{i,j+1}, and L_{i,j} and Li + 1, j are just what we mean by adjacent elements in a row or a column. It’s not that ”quasi-complete Latin squares are defined as pairs of adjacent entries ... that can appear in either order ... .” It’s that a Latin square is quasi-complete if every unordered pair does appear twice in the rows and twice in the columns Final Project Grade Computation

Bibliography: 10/10 Paper: 54/60 Presentation: 27/30 Total: 91/100