Latin Squares. Simple Construction
Many traditional mathematical topics are related to latin squares.
1 2 3 4 1 2 3 4 2 3 4 1 2 4 1 3 3 4 1 2 3 1 4 2 4 1 2 3 4 3 2 1 Table A Table B
The addition table for the integers modulo n is a latin square (latin square A above, the integers modulo 4 in disguise), the multiplication table for the integers modulo n but relatively prime to n is a latin square (latin square B above, the nonzero integers modulo 5), and, for more abstract examples, the multiplication tables for finite groups and finite quasigroups are latin squares. Indeed, there is hardly any difference between latin squares and quasigroups. Every latin square is the multiplication table of some quasigroup. It is this observation that suggests a solution to the following problem.
Design a schedule for 2n tennis players to play a round robin tournament in which every player plays one match with every other player in 2n-1 rounds, n simultaneous matches per round.
For a small number of players, say 4, you can just fool around and find a solution:
round 1: 1 plays 2, 3 plays 4 round 2: 2 plays 3, 1 plays 4 round 3: 3 plays 1, 2 plays 4
Now think of this schedule as a kind of 'multiplication':
1 2 3 4 ----------- 1 | 1 3 2 2 | 1 2 3 3 | 3 2 1 4 | 2 3 1
If the blank entries were filled with the symbol 4, then we have a latin square. Also, the square is symmetric about the blank diagonal. These facts remain true when any schedule is converted to a 'multiplication' table. The table must be symmetric about the blank diagonal because "a plays b in round c" means the same thing as "b plays a in round c". The 'multiplication' table is also a latin square (when 2n fills the blank diagonal) because each player plays exactly one other player in a given round. Hence no row or column of the table can repeat an entry.
So how can we construct such a 'multiplication' table? One example should show the general construction. We do the construction for
0 1 2 3 4 5 6 1 2 3 4 5 6 0 2 3 4 5 6 0 1 3 4 5 6 0 1 2 4 5 6 0 1 2 3 5 6 0 1 2 3 4 6 0 1 2 3 4 5
We want to remove the entries in the diagonal that goes from the upper left to lower right and add entries to an eighth row and eighth column while maintaining no repeats in a row or column. If we remove the 2 in the second row second column and put a 2 in the eighth column second row and put a 2 in the eighth row second column, then the second row and second column still have all 7 symbols. Do this for every diagonal entry. Then the eighth row and eighth column will have all 7 symbols because the diagonal has all 7 symbols. Although it is not necessary, let's also replace all zeros by sevens. The result is the 8×8 table:
1 2 3 4 5 6 7 1 3 4 5 6 7 2 2 3 5 6 7 1 4 3 4 5 7 1 2 6 4 5 6 7 2 3 1 5 6 7 1 2 4 3 6 7 1 2 3 4 5 7 2 4 6 1 3 5
One detail for the general case left unsettled by this example is why the symbols on the diagonal from upper left to lower right are all different. The reason is because all such entries have the form

Latin Squares
- Latin Squares: An Introduction
- Two Simple Problems with Latin Squares
- Latin Squares. Simple Construction
- Orthogonal Latin Squares
- Marriage Problem, a constructive proof
- Robbers divide their loot
- Infinite Latin Squares
- Skyscrapers Puzzle

|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny68055104