Encyclopaedia of DesignTheory: Latin squares

General Partition Incidence Array
Experimental Other designs Math properties Stat properties
Server External Bibliography Miscellanea

Miscellanea about Latin squares

Random Latin squares

Fisher and Yates recommended that, in order to randomize an experimental design based on a Latin square, one should pick a random Latin square of the appropriate size. At the time, no general method of choosing a random Latin square was known.

Accordingly, they tabulated all Latin squares up to n=6 (up to isotopy) and recommended choosing a random square from the tables and randomly permuting rows, columns and symbols.

Nowdays, this is no longer regarded as necessary for valid randomization. The row, column and symbol permutations suffice; any Latin square, however structured, will do.

On the other hand, now we do have a general method! In the paper

M. T. Jacobson and P. Matthews, Generating uniformly distributed random Latin squares, J. Combinatorial Design 4 (1996), 405-437
there is a Markov chain method for generating a random Latin square of given order. The limiting distribution of the Markov chain makes all Latin squares equally likely. However, little is known about the rate of convergence.


Here is a picture of a 5 × 5 Latin square laid out at Beddgelert Forest in 1929 to study the effect of exposure on Sitka spruce, Norway spruce, Japanese larch, Pinus contorta and Beech; and here is the key to the layout. (Plates 6 and 7 from J F Box, R. A. Fisher: The Life of a Scientist; available from Peter M. Lee's History of Statistics website at the University of York.)

Here is a picture of the R. A. Fisher window in Gonville and Caius College, Cambridge (designed by Maria McClafferty, based on a Latin square used by Fisher; photograph by A. W. F. Edwards).

Dartmouth College Mathematics Department have an order-10 Graeco-Latin square as a logo. Their site includes a remarkable picture of the square projected onto a rotating sphere.

Latin squares in cryptography EXTERNAL

The one known completely secure cipher system, the "one-time pad", uses a Latin square as substitution table to combine the plaintext with the random key to produce the ciphertext. That is, suppose that we use an alphabet {a1,...,an} for our messages. Assume that the plaintext message is a string p1p2... of symbols from this alphabet, and the key is a random string k1k2... of symbols from the same alphabet. Then the ciphertext is a string z1z2..., where, for each position i, zi is the symbol in row pi and column ki of the Latin square.

(Note: Of course, no cipher is completely secure in the real world! A one-time pad can be broken if the key is stolen, or if the sender uses it incorrectly, or if the key is not a random string. The above assertion refers to Shannon's theorem, which states that, if the keystring is random, then an interceptor's posterior probabilities on messages after intercepting a ciphertext are the same as the prior probabilities; that is, no information even of a statistical kind is leaked by the cipher.)

Terry Ritter's page Latin Squares in Cryptography gives pointers to this and other applications of Latin squares and orthogonal arrays. See also his Crypto Glossary. I am grateful to Terry Ritter for his comments on this item.

Table of contents | Glossary | Topics | Bibliography | History

Peter J. Cameron
16 September 2004