|
|
|
|
|
|
|
|
|
Latin SquaresThe applet below offers you two problems: one simple and one less simple. In the simple one, you are requested to arrange numbers in a square matrix so as to have every number just once in every row and every column. The second problem imposes one additional condition: the arrangement must be symmetric with respect to the main diagonal (the one from the North-West to the South-East corner.) There are two ways to manipulate rows of the matrix:
RemarkBoth problems fall into the framework of Latin Squares originating with L.Euler. Professor W.McWorter who wrote his Masters Thesis on (orthogonal) latin squares kindly offered his assistance in preparing pages on this entertaining topic. His introduction follows the applet.
 A latin square of order n is an n by n array of n symbols in which every symbol occurs exactly once in each row and column of the array. Here are two examples.
The great mathematician Leonhard Euler introduced latin squares in 1783 as a "nouveau espece de carres magiques", a new kind of magic squares. He also defined what he meant by orthogonal latin squares, which led to a famous conjecture of his that went unsolved for over 100 years. In 1900, G. Tarry proved a particular case of the conjecture. It was shown in 1960 by Bose, Shrikhande, and Parker that, except for this one case, the conjecture was false. You can get a bunch more latin squares (but only one more of the 2 by 2) by permuting rows, columns, and/or symbols in any combination. For example, the latin squares below are derived from the 3 by 3 latin square above.
In one sense all of these latin squares of order 3 are all the same. The original latin square could be a table of information and the other tables just personal taste on how to display the information and code the data. For example, suppose a dating service wants to schedule dates for Ann, Bea, and Carol with Al, Brian, and Carl on Monday, Tuesday, and Wednesday in such a way that each woman dates each man in the three days. The dating service might display the schedule as follows, with x, y, and z codes for Monday, Tuesday, and Wednesday.
It is a matter of taste how the dating service chooses to order the people and code the days, so the other three latin squares above could display exactly the same information. Let's say two latin squares are isomorphic iff one can be transformed into the other by a combination of permuting rows, columns, and symbols. Isomorphic comes from greek; iso meaning same and morph meaning form. Consider the three latin squares constructed below. The latin square A of order 4 below is constructed by cyclically permuting the symbols in the first row for subsequent rows. 2 3 4 1 3 4 1 2 4 1 2 3 The latin square B arises as the multiplication table for the nonzero integers modulo 5: 2 4 1 3 3 1 4 2 4 3 2 1 Computers do modulo 2 arithmetic on strings of zeros and ones. Here is the addition table for two bit strings:
The rightmost array above is the latin square C. Latin square B can be obtained from A by interchanging the symbols 3 and 4 followed by interchanging the last two rows and last two columns. However, no permuting of rows, columns, and/or symbols will produce latin square C from A. Why is that? Taking a cue from our lead-in to the definition of isomorphism, note that latin square C has six 2 by 2 subtables which are latin squares involving the symbol 1. But in latin square B there is no symbol which is part of six 2 by 2 subtables which are latin squares. Since a combination of permuting rows, columns, and symbols preserves the number of 2 by 2 subtables which are latin squares containing a common symbol, latin squares B and C are not isomorphic. Latin squares of order n are extremely numerous for n>3. Indeed, the first row can be any one of n! permutations. After the first row is chosen, there are approximately n!/e choices for the second row (e is the base for the natural logarithm). And, no matter how many rows are chosen less than n rows consistent with being a latin square, it is always possible to choose another row. So any consistent start with k rows can always be completed to a latin square. This fact is based on a fundamental theorem in combinatorics variously known as the Marriage Theorem and the theorem on distinct representatives. References
|
| 31194196 |  |
|