Cut the knot: learn to enjoy mathematics
A math books store at a unique math study site. Learn to enjoy mathematics.
Google
Web CTK
Terms of use
Privacy Policy

More Mathematics
CTK Exchange

Games to Relax
Guest book
Recommend this site

Sites for teachers
Sites for parents

Manifesto: what CTK is about Buying a book is a commitment to learning Things you can find on CTK Email to Cut The Knot Recommend this page

Latin Squares

The 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:

  1. You can cycle rows left or right by clicking just outside the matrix
  2. You can swap two squares in the same row by clicking first on one and then the other

Remark

Both 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.

<hr> <h3> This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet. </h3> <hr>

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.

Latin square of order 2Latin square of order 3
a   b
b   a
x   y   z
z   x   y
y   z   x

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.

Interchange
last two rows
Interchange
last two rows
and first and
last columns
Interchange
symbols y and z
x   y   z
y   z   x
z   x   y
z   y   x
x   z   y
y   x   z
x   z   y
y   x   z
z   y   x

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.

 AlBrianCarl
Annxyz
Beazxy
Carolyzx

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.

1   2   3   4
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:

1   2   3   4
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:

00   01   10   11
01   00   11   10
10   11   00   01
11   10   01   00
changed to
symbols 1 to 4
1   2   3   4
2   1   4   3
3   4   1   2
4   3   2   1

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

  1. R. C. Bose, S. S. Shrikhande, E. T. Parker, Further Results on the Construction of Mutually Orthogonal Latin Squares and the Falsity of Euler's Conjecture, Canadian Journal of Mathematics, vol. 12 (1960), pp. 189-203.
  2. Euler, L., Recherches Sur une Espèce de Carrés Magiques, Commentationes Arithmeticae Collectae, vol. II (1849), pp. 302-361.
  3. W.W.Rouse Ball and H.S.M.Coxeter, Mathematical Recreations and Essays, Dover, 1987

Copyright © 1996-2008 Alexander Bogomolny



Search:
Keywords: