| Manifesto | Bookstore | Contents | Amazon store | Term index | What changed? | Contact | Recommend |
Orthogonal Latin SquaresThe following story is told by W. McWorter. It was the early 1960's. A famous conjecture of Leonhard Euler on orthogonal latin squares had recently been proven false after more than 100 years of valiant effort. Now it seemed that everybody was scrambling to construct orthogonal latin squares, including me. Even when a french visitor to Ohio State University, Dominique Foata, invited me to accompany him on his european vacation, I took along my trusty clipboard to jot down any ideas that might come to me suddenly. Even when I was sitting in the beautiful garden of a friend of Dominique's in northern France, I was testing ideas on orthogonal latin squares. The lady of the house asked me, mercifully in English, what I was doing. I told her I was working on a problem in mathematics but she wanted to know more. So I described the problem of the "trente six officiers" as a diplomatic problem for France and Algeria. Algeria had won its independence in 1962 but problems remained and there were angry demonstrations on both sides. We have six representatives from Algeria, six representatives from France, and six mediators. We want to schedule six tours of Paris to let the negotiating parties get to know each other as follows. Each representative from Algeria goes on all six tours with a french representative and a mediator in such a way that the algerian representative tours with each of the six mediators and no mediator has to go on the same tour twice. The same conditions must also hold for french representatives. The lady wanted more details. I illustrated the situation with a schedule for three algerian representatives A1, A2, and A3, french representatives F1, F2, and F3, tours t1, t2, and t3, and mediators m1, m2, and m3. The table below provides a schedule. F1 F2 F3 ---------------------- A1 | t1 m1 t2 m2 t3 m3 A2 | t2 m3 t3 m1 t1 m2 A3 | t3 m2 t1 m3 t2 m1 The table says that A1 (row 1) and F1 (column 1) go on tour 1 (t1) with mediator 1 (m1), A2 (row 2) and F3 (column 3) go on tour 1 with mediator 2, A3 and F2 go on tour 1 with mediator m3, etc. Since each row and column of the table have all tours and all mediators, all representatives go on all tours with all mediators. Also, the table is designed so that no mediator goes on the same tour twice because each goes on all three tours. I wish I had told the lady that the problem I described with six tours has no solution, but I had no idea that she would try to solve the problem. For, later, while I was attending the Salzburg festival in Austria, I received a long letter from the lady detailing her 'solution' to the problem! That a housewife has attempted to solve an abstract mathematical problem - this kind of thing was unheard of in America of the early 1960s. I don't recall what I wrote to her in response but I felt terrible about misleading her. A pair of latin squares A=(aij) and B=(bij) are orthogonal iff the ordered pairs (aij,bij) are distinct for all i and j. Here are a pair of orthogonal latin squares of order 3.
1 2 3 1 2 3 1 1 2 2 3 3
2 3 1 3 1 2 2 3 3 1 1 2
3 1 2 2 3 1 3 2 1 3 2 1
A and B
A B superimposed
A and B are clearly latin squares and, when superimposed, you can see that all ordered pairs from corresponding square entries are distinct. Orthogonal latin squares are generally hard to come by. There are no orthogonal latin squares of order 2 because there are only two latin squares of order 2 in the same symbols and they are not orthogonal. There are orthogonal latin squares of order 3 as exemplified above. Orthogonal latin squares of order 4 exist but won't be exposed without a little struggle. Orthogonal latin squares of order 5, or any odd order, on the other hand, are not so hard to find. Let A=(i+j) be the addition table for the integers modulo 2n+1 and let B=(2i+j), entries taken modulo 2n+1. Then A and B are orthogonal latin squares. For, A is a latin square because it is the addition table for the integers modulo 2n+1 and B is a latin square because it is just A with its rows rearranged. To show that A and B are orthogonal, suppose that for some i,j,m,n, the ordered pairs (i+j,2i+j) and (m+n,2m+n) are equal. Then i+j=m+n and 2i+j=2m+n. Subtracting (modulo 2n+1) the first equation from the last, we get i=m, from which it follows that j=n. Hence all ordered pairs from different cells of the two latin squares are distinct and the squares are orthogonal. Here is an example for order 5.
0 1 2 3 4 0 1 2 3 4
1 2 3 4 0 2 3 4 0 1
2 3 4 0 1 4 0 1 2 3
3 4 0 1 2 1 2 3 4 0
4 0 1 2 3 3 4 0 1 2
B C
There are no orthogonal latin squares of order 6 but it took a long, long time to find this out. Leonhard Euler began to believe that there are no orthogonal latin squares for orders 2, 6, 10, 14, and indeed for all orders of the form 4n+2. In 1900, G. Tarry has proven that no orthogonal squares of order 6 exist thus lending credibility to the Euler's conjecture. 60 years later, in 1960, it was shown by Bose, Shrikhande, and Parker that, except for this one case, the conjecture was false. With Euler's conjecture settled, interest shifted to finding how many pairs of mutually orthogonal latin squares there are for a given order. It turns out that the maximum number of mutually orthogonal latin squares of order n is at most n-1. In particular, there are at most 3 mutually orthogonal latin squares of order 4. We construct three such using a generalization of the integers modulo n. The integers modulo two under addition and multiplication is a number system like the real number system in that every nonzero number has a multiplicative inverse, that is, it has a reciprocal. In this system the quadratic equation x2+x+1=0 has no solution. However, we can "adjoin" a solution, say a, of this equation to our number system to obtain a larger number system called the Galois field of order 4 (named after the mathematician Evariste Galois who singlehandedly invented a whole field of mathematics before he was killed in a senseless duel when he was only 21 years old). If you feel that a is not really a number, then you can understand why the ancient mathematicians balked at accepting the 'incommensurable' square root of 2 as a legitimate number. The addition table for this number system is 0 1 a a+1 1 0 a+1 a a a+1 0 1 a+1 a 1 0 Let A=(s+t) be the above latin square with s and t ranging over {0,1,a,a+1}. As we did earlier with modular arithmetic, but now with this new arithmetic, form the latin squares B=(as+t) and C=((a+1)s+t). Then, using the same argument used with earlier with the integers modulo 2n+1, the latin squares A, B, and C are mutually orthogonal. Here are B and C.
0 1 a a+1 0 1 a a+1
a a+1 0 1 a+1 a 1 0
a+1 a 1 0 1 0 a+1 a
1 0 a+1 a a a+1 0 1
B C
(a0=0; a1=a; aa=a+1; a(a+1)=1)
Euler began his research in this area with what he called a new kind of magic square. Let's end by applying his kind of magic squares to the old magic squares, those n by n squares which contain all numbers from 1 to n2, or equivalently, 0 to n2-1, in such a way that all rows, columns, and diagonals have the same sum. Let's replace the symbols in the latin squares of order 4 above with 0, 1, 2, and 3, and use the squares B and C to form an array of two-digit numbers written in base 4. 00 11 22 33 0 5 10 15 23 32 01 10 converted 11 14 1 4 31 20 13 02 to base 10 13 8 7 2 12 03 30 21 6 3 12 9 Voila! An old fashioned magic square of size 4! All row, column, and diagonal sums are equal to the magic number 30. The row and column sums are all the same because latin squares B and C are orthogonal. The diagonal sums are the same as those of the rows and columns because latin square A is orthogonal to both B and C, and one diagonal of A has all entries 0 and the other diagonal has all entries a+1.
|
| 34381674 |  |
