A
**Latin square** of
order *n* is an *n* by *n*
array containing symbols from some
alphabet of size *n*,
arranged so that each symbol appears exactly once in each row
and exactly once in each column. The best introduction here is
in Bose and Manvel.

It seems that Latin squares were originally mathematical curiousities, but serious statistical applications were found early in the 20th century, as "experimental designs." The classic example is the use of a Latin square configuration to place 3 or 4 different grain varieties in test patches. Having multiple patches for each variety helps to minimize localized soil effects. Similar statements can be made about medical "treatments."

In some cryptographic applications, a Latin square can be seen as a stream cipher combiner, a sort of generalized exclusive-OR function. A Latin square combiner is invertible provided one of the inputs to the combiner is known, as is generally the case for a stream cipher combiner. Advantages of the Latin square include a massive internal state which may be keyed, and that combining operations using keyed squares will be nonlinear. Thus, architectures which have little worth with linear combining, such as a sequence of combinings, or a selection between combinings, are new opportunities when we have nonlinear combiners with internal state.

In other cryptographic applications, an
orthogonal pair of Latin squares
can be seen as a
*block mixer*,
for relatively small
blocks.
These squares can be constructed or selected from among a plethora
of such squares, thus supporting
keying.
In general, such squares will not be trivial or cyclic, thus
being more appropriate for cryptographic use.

For larger blocks, orthogonal Latin squares can replace the arithmetic butterfly operations normally used in FFT's. As a consequence, we can construct a FFT-like block mixer with very good mixing properties, which is keyed and nonlinear, and which handles blocks of dynamically different width using a single unchanged program code. The ability to handle extremely large block widths is very welcome, since that supports desirable features like fast dynamic keying and inherent per-block authentication.

- 1934
- Fisher and Yates, The 6 x 6 Squares. The article enumerates the squares, but we extract only a few comments here.

- 1939
- Norton, The 7 x 7 Squares. Big. Perhaps the last attempt to enumerate squares in print. Here we extract essentially a glossary of terms.
- Bose, On the Construction of Balanced Incomplete Block Designs. A big, famous article, but too complex to extract very much.
- Stevens, The Completely Orthogonalized Latin Square.

- 1942
- Mann, The Construction of Orthogonal Latin Squares. These turn out to be important in Ritter's Balanced Block Mixing designs.

- 1949
- Shannon, Communication Theory of Secrecy Systems. Shannon defines perfect security and identifies that with a Latin square.

- 1952
- Bush, Orthogonal Arrays of Index Unity. Here we have an introduction to orthogonal arrays.
- Bose and Bush, Orthogonal Arrays of Strength Two and Three. A few extracts.

- 1960
- Bose, Chakravarti and Knuth, On Methods of Constructing Sets of Mutually Orthogonal Latin Squares Using a Computer. II. Apparently somebody was interested in finding orthogonal Latin squares; wonder why?

- 1961
- Johnson, Dulmage and Mendelsohn, Orthomorphisms of Groups and Orthogonal Latin Squares. An approach to the sub-structure of a Ls order.
- Yamamoto, Generation Principles of Latin Squares. More delving into sub-structure.

- 1962
- Collison, Magic Square algorithms in Algol, but no extracts here.

- 1963
- O'Carroll, A Method of Generating Randomized Latin Squares. The full description is here, but backtracking will be required to get to order 256.

- 1967
- Wells, The Number of Latin Squares of Order 8. The order is too big to enumerate in print. Here we have extracts on how a count is done.

- 1971
- Wells, the book. Very lofty, however.

- 1975
- Bammel and Rothstein, The Number of 9 x 9 Latin Squares. More extracts on how a count is done, and a few timing values.
- Alter, How Many Latin Squares Are There? Oddly, still an open question in mathematics. Here we have counts of reduced squares for each order, with the corresponding prime factorization.

- 1980
- Encyclopedic Dictionary of Mathematics Links Latin squares to triplets and quasigroups, and gives counts for both reduced and nonisomorphic squares.

- 1984
- Bose and Manvel, Introduction to Combinatorial Theory. Here we have an introduction to Latin squares.

- 1987
- Stein, Large Sample Properties of Simulations Using Latin Hypercube Sampling.
- Kull and Specker, Direct Construction of Mutually Orthogonal Latin Squares. The algorithms are in math and set notation, and are much too general and detailed to get right if included here.
- Massey, Maurer and Wang, Non-Expanding, Key-Minimal, Robustly-Perfect, Linear and Bilinear Ciphers. A contemporary cryptographic use of Latin squares.
- Hunter, Are Some Latin Squares Better Than Others? Mainly a statistics issue, but the article has an interesting graph of order-3 sub-structure.

- 1989
- Wolf, Nondeterministic Circuits, Space Complexity and Quasigroups. Included here for a view of quasigroups.

- 1990
- Godsil and McKay, Asymptotic Enumeration of Latin Rectangles.

- 1991
- Byers, Basic Algorithms for Random Sampling and Treatment Randomization. While not particularly impressive programming, the basic idea of shuffling the rows and columns of an easy-to-produce square can be very useful.
- Denes and Keedwell, Latin Squares: New Developments in the Theory and Applications. Perhaps the major modern book, covering a range of uses and related ideas.
- Camion, Carlet, Charpin and Sendrier, On Correlation-Immune Functions. Identifies orthogonal arrays as correlation-immune combining functions.

- 1992
- Shao and Wei, A formula for the number of Latin squares.

- 1995
- McKay and Rogoyski, Latin Squares of Order 10.

- 1996
- Jacobson and Matthews, Generating uniformly distributed random latin squares.

- 1998
- Laywine and Mullen, the text:
*Discrete Mathematics Using Latin Squares*

- Laywine and Mullen, the text:

Fisher, R. and F. Yates. 1934. The 6 x 6 Latin Squares.Proceedings of the Cambridge Philosophical Society.30: 492-507.

"The problem of the enumeration of the different arrangements
of *n* letters in an *n* x *n* Latin square, that
is, in a square in which each letter appears once in every row
and once in every column, was first discussed by Euler(1)."

"The problem of the Latin square has become of practical interest in recent years in conjunction with the development of an adequate theoretical basis for the design of biological experiments . . . ." "The reason for its special suitability lies in its satisfactorily fulfilling two distinct requirements: (1) in equalising more thoroughly than can be done in other ways the fertility of the land on which the different treatments are to be tested, and (2) in allowing, subject to the fixed restrictions of the Latin square, of a random choice among the different possible squares which could be laid down on the same area. This element of randomisation is now recognized to be a necessary condition for the validity of the estimate of error by which the results of the experiment are to be judged, and it is the fact that it is not a particular Latin square but a random selection from an aggregate of possible squares which is required for agricultural practice, that have given a renewed interest to Euler's problem of their enumeration."

*Reduced Latin square*.- "A square with the first row and first column in alphabetical
order
*ABCDEF...*has been named by MacMahon a*reduced Latin square*." *Transformations*.- "Any permutation of the rows, columns, or letters of a square,
among themselves, generates another square (possibly identical
with the original square). Any rearrangement of this nature
will be called a
*transformation*." *Intramutations*.- "In a reduced Latin square any permutation of all the letters
other than
*A*may be made, and the rows and columns (excluding the first) then rearranged so as to give another reduced Latin square by arranging the letters of the first row and first column in the standard order. A transformation of this type will be styled an*intramutation*."

"Any square of order *n* can be transformed in
(*n*!)^{3} ways (including no change).
All these transformations do not necessarily give different squares,
but all possible squares of order *n* can be classified in
sets of squares which are derivable from one another by some
transformation."

"Each reduced square generates a set of
*n*!(*n*-1)!

"There does not appear to be any generating process which when applied to a reduced square will generate a fixed number of other reduced squares, all different. The process of intramutation, however, enables the enumeration to be carried out by sets of varying sizes . . . ."

Norton, H. 1939. The 7 x 7 Squares.Annals of Eugenics.9: 269-307.

"Latin squares were first studied by Euler near the end of the eighteenth century, and have since been investigated rather widely but with small success."

**Latin square**- "A Latin square of side
*n*is a square arrangement of*n*^{2}letters,*n*of each of*n*kinds, such that each letter occurs once in each row and once in each column." **Cyclic Latin square**- "An
*n*x*n*Latin square in which each row is derived from any other in a cyclic permutation of degree*n,*or by a power of such a permutation, is a*cyclic*Latin square." **Standardization**- "If the letters of the top row and of the left column of a
Latin square are in some standard order, alphabetic order being
convenient, the square is said to be
*standard*or*in standard form.*It follows that*n*!(*n*-1)! Latin squares of side*n*may be represented by a single standard square. Standard squares have been called*reduced*squares by MacMahon (1915)." **Constraints**- "Since the elements of a Latin square are constrained to certain
rows and columns and letters, rows, columns and letters will be
called
*constraints,*and a Latin square may be said to be a square of three constraints. **Orthogonal Latin squares**- "It may be possible to find two Latin squares of the same size,
necessarily not both standard, such that when one is superposed on
the other, each letter of the one coincides once with each letter
of the other. Two such Latin squares are said to be
*orthogonal.*" "If one of the two Latin squares be written in Greek letters and superposed on the first, the resulting square is called a*Graeco-Latin square,*and may be said to be a square of four constraints. It may be possible to go further, but a group of mutually orthogonal squares of side*n*can number at most."*n*- 1 **Orthogonal Standardization**- "The requirements of the Graeco-Latin square do not permit that both of the component Latin squares be standard. The standard form of a Graeco-Latin and higher squares is therefore defined to be that in which the basic Latin square is standard and the superposed square or squares have the top row in standard order."
**Transformations**- "Any permutation of the rows, columns or letters of a Latin
square, or any combination of such permutations, is called a
*transformation.*" **Conjugacy**- "Two Latin squares are said to be
*conjugate*if the rows of one are the columns of the other. In other words, if the rows and columns of a square be interchanged, the conjugate square is generated." **Adjugacy**- "Adjugacy is a generalization of the concept of conjugacy and
is used here to include conjugacy. Two squares are said to be
*adjugate*if a permutation of the constraints of one generates another." **Species**- "A
*species*of Latin squares is a group of adjugate sets such that any permutation of the constraints of any member generates a member, and all possible permutations of the constraints of any member generates all members." **Intercalate**- "An intercalate is a Latin square of side 2 embedded in a
larger square. For example, the following 7 x 7 Latin square
has 10 intercalates, one of which contains the elements 21B,
24G, 71G and 74B."
A B C D E F G

**B**E D**G**F C A C A B E D G F D G F C B A E E C G F A D B F D E A G B C**G**F A**B**C E D **Intercalate reversal**- "It is obvious that the two letters, or the two rows or the two
columns, involved in an intercalate may be interchanged within the
intercalate but not elsewhere, or
*visa versa,*while preserving the Latin square." "This interchange is called*intercalate reversal,*and usually generates a member of a new species." **Groupings of species**- "A
*family*of species is a group such that the reversal of any intercalate contained in the group generates a member of the group, and the reversal of all intercalates contained in the group generates all members of the group. A*domain*is exactly analogous to a family, but includes reversal of generalized intercalates. The*universe*of squares of side*n*contains all the squares of that size and of a specified number of constraints."

"The enumeration of Latin squares was first undertaken by Euler
(1782) in searching for a

"Fisher & Yates (1934) enumerated the

"The recognition of Latin squares, and hence their enumeration, is greatly facilitated by standardization. A group of 7!6! = 3,628,800 squares (one standard and the remainder not) may be represented by a single square."

Bose, R. 1939. On The Construction of Balanced Incomplete Block Designs.Annals of Eugenics.9: 353-399.

"The interest of mathematicians in combinatorial problems,
involving the arrangement of a finite number of things in sets or
patterns, satisfying given conditions, can be traced back to at
least as far as Euler (1782), who interested himself in the
construction of Latin and Graeco-Latin squares. Steiner (1853)
proposed the problem of arranging *N* things in triplets,
such that every pair occurs in just one and only one triplet.
Such an arrangement may be called a *simple triplet system*
or a *Steiner's triplet system.*" "The object of this
paper is to study the combinatorial problem involved in the
construction of a certain type of design, first introduced in
experimental studies by F. Yates (1936), and called
*Balanced Incomplete Block Design.* An example of such a
design is afforded by a simple triple system."

"If *v* varieties or treatments are to be compared in
randomized blocks of *k* experimental units
(*k*<*v*), then block differences can be simply
eliminated, if the arrangement is such that every two varieties
occur together in the same number [lambda] of blocks. It is
readily seen that the integers *v, b, r, k,* [lambda]
satisfy the equations

*bk = vr,*
[lambda](*v*-1) = *r*(*k*-1),

so that these equations provide necessary conditions, for the
existence of a balanced incomplete block design, with *v*
varieties arranged in *b* blocks of *k* units each,
each variety being replicated *r* times, and each pair
occurring [lambda] times. These equations do not, however,
provide sufficient conditions . . . ."

Stevens, W. 1939. The Completely Orthogonalized Latin Square.Annals of Eugenics.9: 82-93.

**The Latin square**- "A Latin square of side
*s*is an arrangement of*s*letters, *s*of each*s*kinds, such that in each row and in each column each letter occurs exactly once. Thus when*s*=3, a suitable arrangement is"A B C B C A C A B

**The Graeco-Latin Square**- "It may or may not be possible to write down another Latin
square with the same letters such that when the two squares are
superimposed, each letter of one square coincides exactly once
with each letter of the other square. Two squares of side 3
with this property are"
A B C A B C B C A C A B C A B B C A

"When the second square is written in Greek letters and superimposed on the first, the composite is called a Graeco-Latin square. In general, any two such Latin squares are said to be orthogonal to each other." **Mutually orthogonal Latin squares**- "The number of squares in a set of orthogonal squares of side
*s*is not greater than (*s*-1). For the letters of each square may be permuted among themselves without destroying the property of orthogonality. Let this be done so that the top line of each square commences*A B ....*Then, since between any two squares*B*coincides with itself in the top row, it follows that in the first column*B*cannot occupy any position twice or the top position at all. Hence there are not more than (*s*-1) positions available for*B.*""The same fact is obvious from consideration of Analysis of Variance. For differences between the "plots" with the same letter in one Latin square, or between rows or columns account for (

*s*-1) degrees of freedom, and since there are altogether*s*^{2}-1 degrees of freedom, it follows that there are not more than*s*+1 independent methods of subdivision. Of these rows and columns account for two, leaving only*s*-1 different subdivisions by letters." **Construction of a complete set of orthogonal squares**- "Assuming that a field of
*s*letters exist, we may write a square of letters as{

*u*}_{[lambda]}u_{x}+u_{y}*u*= constant <> 0_{[lambda]}

*u*= 0,1,_{x},u_{y}*u*_{2},...,*u*_{s-1}where

*u*is the letter in row_{[lambda]}u_{x}+u_{y}*u*and column_{x}*u*"_{y}.

Mann, H. 1942. The Construction of Orthogonal Latin Squares.Annals of Mathematical Statistics.13: 418-423.

"A Latin square is an arrangement of *m* variables
*x*_{1}, *x*_{2}, ...,
*x _{m}* into

**Definition 1**- "
*If A is orthogonal to B, and if in the reduced form the permutations of A are the same as B in a different order, and if these permutations form a group G, then the pair A and B is said to be based on the group G.*"

"Most of the sets of orthogonal Latin squares that have been
constructed so far are based on abelian groups of the type
(*p,p,...,p*) and the mappings of the squares of the sets
into each other are automorphisms of this group."

"Below are given two examples of Graeco-Latin squares obtained from complete mappings which are not obtained from automorphisms. Neither could have been obtained by combining Graeco-Latin squares constructed by the method of Bose [1] and Stevens [2]."

Shannon, C. 1949. Communication Theory of Secrecy Systems.Bell System Technical Journal.28: 656-715.

"Perfect systems in which the number of cryptograms, the
number of messages, and the number of keys are all equal are
characterized by the properties that (1) each *M* is
connected to each *E* by exactly one line, (2) all keys
are equally likely. Thus the matrix representation of the
system is a "Latin square." (p. 681)

Bush, K. 1952. Orthogonal Arrays of Index Unity.Annals of Mathematical Statistics.23: 426-434.

"In this paper we shall proceed to generalize the notion of a
set of orthogonal Latin squares, and we term this extension an
orthogonal array of index unity. In Section 2 we secure bounds
for the number of constraints which are the counterpart of the
familiar theorem which states that the number of mutually
orthogonal Latin squares of side *s* is bounded above by
*s* - 1. Curiously, our bound depends upon whether
*s* is odd or even. In Section 3 we give a method of
constructing these arrays by considering a class of polynomials
with coefficients in the finite Galois field *GF*(*s*),
where *s* is a prime or a power of a prime."

Let a set of *s* integers, 0,1,...,*s*-1 be arranged
in an *s* x *s* square in such a way that every integer
occurs *s* times. If each integer occurs once and only once
in every row and column, the square is said to be a Latin square
of side *s.* Two squares are said to be orthogonal to one
another if, when one square is superimposed upon the other square,
every number of the first occurs once and only once with every
number of the second square. To the set of at most *s* - 1
Latin squares which are mutually orthogonal, we may adjoin two
other squares which are not Latin squares, but which are orthogonal
to each other and to every other Latin square in the orthogonal
set. The first of these squares is constructed by taking each
element of the first row as 0, each element of the second row as 1,
and so on. The second square is the transpose of the first square.
Conversely it may be noted that any square orthogonal to these two
squares must be a Latin square. Thus a total of *s* + 1
orthogonal squares is possible at best, and it is known that this
bound is attainable when *s* is a prime or a power of a
prime [1]. When this bound is attained, we say that we have a
complete set of orthogonal squares. As an example of a complete
set, we might choose *s* = 3 and write

0 0 0 0 1 2 0 1 2 0 1 2 1 1 1 0 1 2 1 2 0 2 0 1 2 2 2 0 1 2 2 0 1 1 2 0

"If we write in order the elements of each square in a line, we can display these squares in the following form:"

0 0 0 1 1 1 2 2 2 [first square] 0 1 2 0 1 2 0 1 2 [second square] 0 1 2 1 2 0 2 0 1 [third square] 0 1 2 2 0 1 1 2 0 [fourth square]

"In this form we see that any two rows have the property that each one of the nine possible ordered pairs occurs exactly once when one row is superimposed on another row. We now generalize this basic idea."

"Let us consider a matrix *A* = [*a _{ij}*],
where each

Bose, R. and K. Bush. 1952. Orthogonal Arrays of Strength Two and Three.Annals of Mathematical Statistics.23: 508-524.

"Orthogonal arrays can be regarded as natural generalizations of orthogonal Latin squares . . . ."

"A *k* x *N* matrix *A,* with entries from a set
[sigma] of *s* >= 2 elements, is called an orthogonal array
of strength *t*, size *N,* *k* constraints and
*s* levels if each *t* x *N* submatrix of *A*
contains all possible *t* x 1 column vectors with the same
frequency [lambda]. The array may be denoted by (*N,k,s,t*).
The number [lambda] may be called the index of the array.
Clearly *N* = [lambda]*s ^{t}.*"

Bose, R, I. Chakravarti and D. Knuth. 1960. On Methods of Constructing Sets of Mutually Orthogonal Latin Squares Using a Computer. IITechnometrics.3(1): 111-117.

"In [1] a method of searching for sets of mutually orthogonal
Latin squares of size *v* = 4*t* where 4*t* is the
order of a Hadamard matrix is given. The method is based on the
concept of orthogonal mappings of a group, due to Mann [4].

Johnson, D., A. Dulmage and N. Mendelsohn. 1961. Orthomorphisms of Groups and Orthogonal Latin Squares. ICanadian Journal of Mathematics.13: 356-372.

"It is a trivial fact that for any *n,* there are at most
*n* - 1 mutually orthogonal latin squares. When *n* - 1
such squares exist we say that the set of squares is complete.
There is an easily established 1-1 correspondence between complete
sets of orthogonal latin squares and finite affine (and hence
projective) plane geometries." "The basic square is the group
addition table of an elementary abelian group and the remainder
of the squares are obtained by a set of permutations of the rows
in each of which the first row is kept fixed."

Yamamoto, K. 1961. Generation Principles of Latin Squares.Bulletin of the International Statistical Institute.38(4): 73-76.

"In the universe *L* of Latin squares of order *n,*
the transformation group *G,* comprising all permutations of
rows, columns and treatments, and all the six adjugations, is
usually utilized to subdivide *L* into finer classes. But
the group *G* may also be regarded as a generation principle
to derive a new Latin square from a given one."

Collison, D. 1962. Algorithm 117. Magic Square (Even Order). Algorithm 118. Magic Square (Odd Order).Communications of the ACM.5(8): 435, 436.

O'Carroll, F. 1963. A Method of Generating Randomized Latin Squares.Biometrics.December. 652-653.

"The square is constructed row by row, but within each row the
elements are not necessarily entered in regular order. Consider
the position when, in constructing an *N* x *N**R* - 1 rows have been completed and in
the *R*th row *I* - 1 elements have been filled in.
Let *A _{J}* be the number of different letters that
can be inserted in the

"(i) If *S* <= *N,* insert in the *S*th position
in the *R*th row the *B*th letter among those that can
be entered in this position."

"(ii) If *S* > *N,* insert the (*S* - *N*)th
letter of the alphabet in the *B*th position among those
still open to it in the *R*th row."

Wells, B. 1967. The Number of Latin Squares of Order 8,Journal of Combinatorial Theory.3: 98-99.

"In 1934, Fisher and Yates [1] enumerated Latin squares of order
six, giving 9408 as the number of reduced squares. (A Latin square
is *reduced* when the first row and first column are in
lexicographic order.) They arrived at that total as a by-product
in the explicit construction of equivalence class representatives;
there are, in fact, 12 "species" of *species* is a class of squares equivalent under arbitrary
row, column, or label permutation ((*n*!)^{3} of them)
or permutation of the three "dimensions," the rows, the columns,
and the letters (3! of them -- giving 6(*n*!)^{3}
transformations in all).

"In 1948, Sade [3] enumerated reduced *k* = 1,2,...,*K,* *K* <= *n,* a (complete)
set of *reduced* *k* x *n* Latin rectangles (the
first column is not only lexicographic but contains the labels
1,2,...,*k*) inequivalent under row, column or label
permutation, keeping track of the number of ways the rectangle
could have been formed. The (*k* + 1)-row rectangles are
formed by adding a row to each *k*-row rectangle in all
possible ways, eliminating the equivalent rectangles (actually the
difficult part of the calculation) as they appear. It is not
necessary, or efficient, to continue the process until
*k* = *n.* When *k* = *K* (Sade used
*K* = 4), one may sum the product of the number of ways in
which a rectangle could have been formed (already known) and the
number of ways the rectangle could have been completed to a
square (easily computed) over the inequivalent *k*-row
rectangles, producing the number of *n* x *n* squares.

"Using a computer adaptation of Sade's method, the author has
enumerated 8 x 8 reduced Latin squares, *I*_{8},
finding *I*_{8} = 535,281,401,856."

Wells, M. 1971.Elements of Combinatorial Computing.Ch. 7, 198-206. Pergamon Press.

A *very* esoteric presentation of algorithms in
math and set notation (as opposed to a computing language).

"The enumeration of reduced Latin squares is an excellent example of the application of the equivalence algorithm just discussed (and of the branch merging technique of section 4.4.4)." (p. 203)

Bammel, S. and J. Rothstein. 1975. The Number of 9 x 9 Latin Squares.Discrete Mathematics.11: 93-95.

"Sade [1] enumerated the reduced

"Sade's method is based on the fact that equivalent Latin
rectangles can be filled out to complete
*n* x *n**k* x *n**k*+1) x *n**k*+1) x *n**k* = *n*-3*n*-4) is
reached for exhaustive enumeration. Then knowing the counts for
(*k*+1)-row classes, the counts for *k*-row classes are
easily computed. The total number of reduced squares is given by
*k* = 1.

"A modest improvement in algorithm efficiency is achieved by increasing equivalence class size. We note that if each row of a rectangle be regarded as a permutation of the top row, then the rectangle obtained by replacing each permutation by its inverse has the same count. Following Wells, we work with incidence matrices but now our rectangles are in the same class if their incidence matrices are equivalent under transposition as well as row and column permutation.

"A major improvement in efficiency is achieved in the incidence
matrix equivalence algorithm by using a lexicographic procedure
which eliminates indeterminacy and back-tracking, normally a
time-consuming process. The rows and columns of the incidence
matrix are sorted and partitioned according to Wells' row and
column weights, but now if the set of column weights is
lexicographically less than the set of row weights, the matrix
is transposed. At each step sub-matrices (larger than

"Note that each matrix is reduced to conventional form only once before searching the table of previously encountered conventional forms (representing equivalence classes). This affords another major improvement in that it is not necessary to attempt to reduce one matrix to another at each comparison."

Table 1 n reduced Latin squares computation time 7 16 942 080 30 sec. 8 535 281 401 856 4 min. 9 377 597 570 964 258 816 4.7 hours

Alter, R. 1975. How Many Latin Squares Are There?American Mathematical Monthly.82: 632-634.

"A latin square of order *n* is an arrangement of the first
*n* integers in an *n* x *n* array so that every
integer appears exactly once in every row and exactly once in every
Column. Let *L _{n}* be the number of latin squares of
order

(1)"To answer the title question it suffices to determineL=_{n}n!(n-1)!R._{n}

Table 1 n R_{n}Prime Factorization 1 1 1 2 1 1 3 1 1 4 4 2^{2}5 56 2^{3}. 7 6 9 408 2^{6}. 3 . 7^{2}7 16 942 080 2^{10}. 3 . 5. 1103 8 535 281 401 856 2^{17}. 3 . 1 361 291 9 377 597 570 964 258 816 2^{21}. 3^{2}. 5 231 . 3 824 477

"With current computing facilities, Table 1 will undoubtably
be extended. This in turn may shed some light on the above
divisibility questions. However, the determination of
*R _{n}* (and thus also

Combinatorial Theory.Encyclopedic Dictionary of Mathematics.Mathematical Society of Japan. MIT Press. 1980.

"Let [omega] =
{*a*_{1},*a*_{2},...,*a _{n}*}
be a set of

Bose, R. and B. Manvel. 1984.Introduction to Combinatorial Theory.135-149 (Ch. 7). John Wiley & Sons.

"A *Latin square* of order *s* is identified as an
*s* x *s* square, the *s*^{2} cells of
which are occupied by *s* distinct symbols . . . such that
each symbol occurs once in each row and once in each column."

"Two Latin squares of the same order are said to be
*orthogonal* if, on superposition, each symbol of the first
square occurs exactly once with each symbol of the second square."

"A set of Latin squares (all of the same order), any two of
which are orthogonal, is said to be *a set of mutually
orthogonal Latin squares.*

"A Latin square is said to be in the *standard form* if
the symbols in the initial row are in the natural order.

"A Latin square can always be brought to the standard form by renaming the symbols. If two Latin squares are orthogonal, the renaming can be done independently for each square without destroying orthogonality."

"There are exactly two Latin squares of order 2."

0 1 1 0 1 0 0 1

"Next consider Latin squares of order 3. We shall show that once the initial row and column are filled, there is one way to complete the Latin square."

0 1 2 1 2 0 2 0 1

"We can permute the columns in six different ways. Corresponding to each of these permutations there are two ways to permute the rows other than the initial row. Hence there are twelve distinct Latin squares of order 3."

0 1 2 0 2 1 1 2 0 1 0 2 2 0 1 2 1 0 1 2 0 1 0 2 2 0 1 2 1 0 0 1 2 0 2 1 2 0 1 2 1 0 0 1 2 0 2 1 1 2 0 1 0 2 0 1 2 0 2 1 1 2 0 1 0 2 2 0 1 2 1 0 2 0 1 2 1 0 0 1 2 0 2 1 1 2 0 1 0 2 1 2 0 1 0 2 2 0 1 2 1 0 0 1 2 0 2 1

"There are exactly four Latin squares of order 4 in which the initial row and the initial column are in the natural order . . . ."

0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 1 2 3 0 1 3 0 2 1 0 3 2 1 0 3 2 2 3 0 1 2 0 3 1 2 3 0 1 2 3 1 0 3 0 1 2 3 2 1 0 3 2 1 0 3 2 0 1

"From any [of these] we can obtain 144 squares by first
permuting the four columns in all 24 possible ways and then
permuting the three rows other than the initial row in all 6
possible ways. Thus, there are altogether

"There are 56 different Latin squares of order 5 in which the
initial row and column are in the natural order, each giving
rise to

Stein, M. 1987. Large Sample Properties of Simulations Using Latin Hypercube Sampling.Technometrics.29(2): 143-151.

"Latin hypercube sampling (McKay, Conover, and Beckman 1979) is a method of sampling that can be used to produce input values for estimation of expectations of functions of output variables. The asymptotic variances of such an estimate is obtained. The estimate is also shown to be asymptotically normal."

Kull, H. and E. Specker. 1987. Direct Construction of Mutually Orthogonal Latin Squares.Computation Theory and Logic.224-236.

"The purpose of [algorithm] (DC) is to construct a system of
__m__utually __o__rthogonal __l__atin __s__quares
("MOLS" [3])."

Massey, J., U. Maurer and M. Wang. Non-Expanding, Key-Minimal, Robustly-Perfect, Linear and Bilinear Ciphers.Advances in Cryptology -- EUROCRYPT '87.237-247. Springer-Verlag.

"Section 2 introduces the notion of a robustly-perfect block cipher and shows the connection of such ciphers to Latin squares."

"In a deterministic secret-key cipher, the ciphertext *Y*
can be written in terms of the plaintext *X* and the key
*Z* in the manner

*Y* = *f*(*X*,*Z*)

"Shannon [1,p.679] has defined a cipher system
(*f*,*P _{Z}*) to be

"Shannon observed that condition (2) of the above proposition
*[proposition 1]* shows that the essential feature of a
non-expanding key-minimal robustly-perfect cipher is that, with
the rows indexed by plaintexts and the columns indexed by the
keys, the array or corresponding ciphertexts forms a Latin square."

Hunter, J. 1987. Are Some Latin Squares Better Than Others?Design, Data and Analysis.163-170.

Shows that order 3 Latin squares divide into two groups with different graph structures.

Wolf, M. 1989. Nondeterministic Circuits, Space Complexity and Quasigroups.Computer Sciences Technical Report #870.Computer Sciences Department, University of Wisconsin -- Madison.

"**Definition:** A *Latin square* is an
*n* x *n* grid with each of the integers 1,2,...,*n*
appearing exactly once in each row and column."

"If each of the integers 1,2,...,*n* appears as a label
for exactly one row and exactly one column then the Latin square
can be viewed as a multiplication table of a quasigroup. We
formalize the definitions of groups and quasigroups by considering
the following four properties of a set *Q* with an associated
binary operation *. For all *a,b,c* in *Q*:"

- There is a unique
*x*such that*a***b*=*x.* - There is a unique
*x*such that*a***x*=*b.* - There is a unique
*x*such that*x***a*=*b.* - (
*a***b*)**c*=*a**(*b***c*)

"**Definition:** *Q* is a *group* if * satisfies
properties 1,2,3, and 4."

"**Definition:** *Q* is a *quasigroup* if *
satisfies properties 1,2 and 3."

"Thus a quasigroup is more general than a group. In this paper
we view quasigroups of order *n* as a binary function on
{1,2,...,*n*}, thus the corresponding multiplication table
is a Latin square. Viewing Latin squares *L* and *L*'
as trinary relations <,,> and <,,>', *L* is *isomorphic*
to *L*' if there exists a permutation *g* such that if
<*x,y,z*> is in *L* then <*g(x),g(y),g(z)*>' is
in *L*'."

Godsil, C. and B. McKay. 1990. Asymptotic Enumeration of Latin Rectangles.Journal of Combinatorial Theory, Series B48: 19-44.

"A *k* x *n Latin rectangle* is a *k* x *n*
matrix with entries from {1,...,*n*} with the property that
no entry occurs more than once in any row or column. Thus an
*n* x *n* Latin rectangle is nothing more than a Latin
square."

"We prove that the number of *k* x *n* Latin rectangles"
(this is L(*k,n*)) "is asymptotically

k k n -n/2 -k/2 (n!) ( n(n-1)...(n-k+1) / n ) (1 - k/n) e (6/7) as n approaches infinity, with k = o(n )."

"The first attack on this problem was made by P. Erdos and
I. Kaplanski [8], who showed that, for
*k* = *O*(log *n*)^{3/2 - e}),

k k L(k,n) ~ (n!) exp( -( ) ). 2

"Further progress was made by Yamamoto [36] and Stein [27], who proved that

k k 3 L(k,n) ~ (n!) exp( -( ) - k / 6n ) 2for

Byers, J. 1991. Basic Algorithms for Random Sampling and Treatment Randomization.Computers in Biology and Medicine.21(112): 69-77.

"Five BASIC programs to select random samples from populations or to randomize treatments are presented." "Program 2 produces Latin squares of any size for treatment randomization."

"The algorithm uses the method of randomizing numbers by treatment . . . for two such arrays of treatments (columns and row). The column and row arrays . . . can then be used to calculate a unique latin square of . . . cell elements. Each column and row intersection, cell(c,r), of the latin square can be obtained from the sum of the numbers in the respective column and row arrays . . . ."

Denes, J. and A. Keedwell. 1991.Latin Squares: New Developments in the Theory and Applications.North-Holland.

"A __latin square__ of order n is an

"A set S on which a binary operation (.) is defined forms a quasigroup with respect to that operation if, when any two elements a,b of S are given, the element a.b is in S and the equations a.x = b and y.a = b each have exactly one solution in S."

"It is easy to see that the multiplication table (often called
__Cayley table__)of a quasigroup is a latin square."

"Two latin squares L_{1} = ||a_{ij}|| and
L_{2} = ||b_{ij}|| on n symbols, say
1,2,...,n, are said to be __orthogonal__ if every ordered
pair of symbols occurs exactly once among the n^{2} pairs
(a_{ij},b_{ij}), i = 1,2,...,n; j = 1,2,...,n."

"A pair of orthogonal latin squares is also called a
__graeco-latin square__, especially in statistical applications,
because L. Euler (1779) used Greek letters for one square of
the pair and latin letters for the other."

Camion, P., C. Carlet, P. Charpin and N. Sendrier. 1991. On Correlation-Immune Functions.Advances in Cryptology -- CRYPTO '91.86-100. Springer-Verlag.

"In a general type of running-key generator, the output
sequences of m Linear Feedback Shift Registers are taken as
arguments of a singe non linear combining function f. If the
function is not properly chosen, it can happen that the generator
structure is not resistant to a *correlation attack* . . . ."

"The kth-order correlation immune functions were introduced by T. Siegenthaler in [6]."

"X. Guo-Zhen and J. L. Massey later gave an equivalent definition, using the Walsh transform of the boolean functions."

"In section 3, we first prove (theorem 1) that a k-ci function
is an *orthogonal array of strength k* . . . ."

Shao, J. and W. Wei. 1992. A formula for the number of Latin squares.Discrete Mathematics.110: 293-296.

"A Latin square of order *n* is an *n* x *n*
matrix, each row and column of which is a permutation of the set
of letters *I _{n}* = {1,2,...,

"We establish an explicit formula for the number of Latin squares
of order *n*:

sigma0(A) per A L[n] = n! SUM( (-1) ( ) A in B[n] nwhere B[n] is the set of

"**Definition 1.** Let *m* <= *n*_{n}(m) the set of all *m*-permutations
of the elements in the set *n*}.

"For any *m* x *n*_{ij}),

per A = SUM( a[1,i1] a[2,i2] ... a[m,im] ) . (i1,...,im) in Sn(m)"For the special case

per A = SUM( a[1,i1] a[2,i2] ... a[n,in] ) . (i1,...,in) in Sn(n)

"**Definition 2.** An *n* x *n**n,* each row and column of which
contains exactly one nonzero element." (Apparently this is the
*n* x *n*

McKay, B. and E. Rogoyski. 1995. Latin Squares of Order 10.Electronic Journal of Combinatorics.2(3): 1-4.

"We describe two independent computations of the number of Latin squares of order 10. We also give counts of Latin rectangles with up to 10 columns, and estimates of the number of Latin squares of orders up to 15."

Numbers of normalized Latin squares (excerpted from Table 1: Numbers of normalized Latin rectangles) n L(n,n) 1 1 2 1 3 1 4 4 5 56 6 9,408 7 16,942,080 8 535,281,401,856 9 377,597,570,964,258,816 10 7,580,721,483,160,132,811,489,280

"To obtain the total number of Latin rectangles, not necessarily
normalized, multiply L(k,n) by

Table 2. Estimates of L(n,n) for larger n. n trials L(n,n) 11 1000000 5.36 x 10^{33}12 1100000 1.62 x 10^{44}13 400000 2.51 x 10^{56}14 200000 2.33 x 10^{70}15 20000 1.5 x 10^{86}

*[Editorial Comment: It is tempting to extrapolate this to
order 16, by taking the ratios of adjacent values for L(n,n) as
powers of 10, to get the sequence (11,12,14,16). If we then take
the next element of the sequence as 18, we would expect L(16,16)
to be something like 10 ^{102}, or about
2^{339}./tfr]*

Jacobson, M. and P. Matthews. 1996. Generating Uniformly Distributed Latin Squares.Journal of Combinatorial Designs.4(6): 405-437.

"In this article, we construct Markov chain Monte Carlo algorithms
for generating random *n* x *n*

"The central issue is the construction of 'moves' between Latin squares that connect the space, i.e., that allow us to eventually reach any Latin square from any other." (p. 406)

". . . we derive a class of new moves that stay within the space
of proper Latin squares. Such a move either swaps elements between
two rows of a Latin square, along a 'cycle,' or swaps elements among
three rows using 'partial cycles' between two pairs of three rows.
These moves also connect the space of Latin squares [with graph
diameter bounded above by *4(n - 1) ^{2}*] and may be
applied randomly to form a suitable Markov chain having a uniform
stationary distribution." (p. 406)

*[It seems to me that for this to work we really have to make
a whole lot of expensive "moves" between samplings of random squares.
The whole point is to make every square equally probable given any
starting square, and that is going to take a lot of moves./tfr]*

Laywine, C. and G. Mullen. 1998.Discrete Mathematics Using Latin Squares.John Wiley & Sons.

"We now ask a much more difficult question: for each
*n* >= 2,*n*?
Here, by distinct squares, we mean distinct as matrices so that
two latin squares of order *n* will be considered different
if they differ in at least one position.
Let *L _{n}* denote the total number of distinct
latin squares of order

"If *I _{n}* denotes the number of reduced latin
squares of order

"**Theorem 1.2.** *For each n*>=2 *the total number
L_{n} of latin squares of order n is given by*

L=_{n}n!(n- 1)!I_{n}

"*Proof.* Given a latin square of order *n*, one can
interchange the *n* columns in any of *n*! ways simply
by permuting the columns.
Clearly each of the resulting squares will still be latin, and no
two of the squares will be the same as matrices.
Analogously, after permuting the columns, we can permute the last
or bottom *n* - 1*n* - 1)!*n*, the
*n*! column and *n* - 1)!*n*!(*n* - 1)!*n*, and exactly one of these squares will be reduced.
Since there are *I _{n}* reduced latin squares of
order

*Last updated:* 2003-12-21 (from 1998-05-29)