Latin Squares

It's a perpetual wonder that mathematical theories developed with no useful purpose in mind except to satisify a mathematican curiosity, often and most unexpectedly apply not only to other parts of mathematics but to other sciences and real world problems. Non-euclidean geometries became an integral part of the General Theory of Relativity. Group Theory and the theory of Semigroups of Operators serve as an important tool in Quantum Mechanics. Encryption algorithms that underly security of internet transactions are based on finding huge prime numbers.

Orthogonal latin squares have been considered by Euler probably for their entertaining value. He posed the problem of 36 officers: Is it possible to arrange 36 officers, each having one of six different ranks and belonging to one of six different regiments, in a square formation 6 by 6, so that each row and each file shall contain just one officer of each rank and just one from each regiment?

Besides having an exciting history latin squares developed into a very respectable branch of mathematics with various applications. Starting with the early twentieth century latin square found statistical applications as experimental designs (BIB - balanced inclomplete block - designs.) The theory of designs depends on such abstract mathematical tools as finite fields and finite geometries.

Latin squares are good for scheduling round-robbin tournaments. As a matching procedure, latin squares relate to problems in Graph Theory, job assignment (or Marriage Problem), and, more recently, processor scheduling for massively parallel computer systems. Algorithms for solving the Marriage Problem are also used in Linear Agebra to reduce matrices to block diagonal form.

References

1. Euler, L., Recherches Sur une Espèce de Carrés Magiques, Commentationes Arithmeticae Collectae, vol. II (1849), pp. 302-361.
2. W.W.Rouse Ball and H.S.M.Coxeter, Mathematical Recreations and Essays, Dover, 1987
3. S.K.Stein, Mathematics: The Man-Made Universe, 3rd edition, Dover, 2000.
4. Encyclopædia Britannica

1. Partying With A Latin Square (modern applications: parallel computations, conflict resolution)
2. Latin Squares and Related Topics (Collection of references with quotes, cryptographic application)
3. The "Magic Carpet" Approach to Understanding Magic Squares
4. Graeco-Latin Squares
5. The History of the Problem (relevance of latin squares to existence of finite projective planes)

• Introduction
• Latin Squares
• Tournaments
• Orthogonal Latin Squares
  • A Tool for Constructing Orthogonal Latin Squares
• Marriage Problem and Algorithm
  • Marriage Problem, two proofs
  • Marriage Problem, simulation
    • Solutions
• Sharing Loot
• Infinite Latin Squares
  • A Problem on an Infinite Checkerboard