Latin Squares

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': ab = c means "a plays b in round c". Rewrite the schedule as a multiplication table.

	    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 n = 4, or 8 tennis players. Look at the addition table for the integers modulo 2n - 1 = 7.

	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 a = x + x = 2x modulo (2n - 1). Since 2n - 1 is odd, the number 2 has a multiplicative inverse modulo 2n -1, and so the equation 2x = a has a unique solution for each a.

34383555

Amazon.com Widgets