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.
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."
"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
"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 . . . ."
1939 -- Norton
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."
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
"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."
1939 -- Bose
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 . . . ."
1939 -- Stevens
Stevens, W. 1939. The Completely Orthogonalized Latin Square. Annals of Eugenics. 9: 82-93.
A B C B C A C A B
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."
"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 s2-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."
{u[lambda]ux+uy}
u[lambda] = constant <> 0
ux,uy=
0,1,u2,...,us-1
where u[lambda]ux+uy is the letter in row ux and column uy."
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 x1, x2, ..., xm into m rows and m columns such that no row and no column contains any of the variables twice. Two Latin squares are called orthogonal if when one is superimposed upon the other every ordered pair of variables occurs once in the resulting square."
"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]."
1949 -- Shannon
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)
1952 -- Bush
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 = [aij],
where each aij represents one of the integers
0,1,...,s-1, s > 1. The matrix is rectangular
with N columns, which we shall call the blocks of the
array, and k rows. Consider all t-rowed
submatrices of N columns which can be formed from this
array, t <= k. Each column of any t-rowed
submatrix can be regarded as an ordered t-plet, so that
each t-rowed submatrix contains N such
t-plets. The matrix A will be called an
orthogonal array [N,k,s,t] of size N, k constraints,
s levels, strength t and index [lambda] if each of the
Ckt t-rowed N-columned
submatrices that may be formed from the array contains every one
of the st possible ordered t-plets each
repeated [lambda] times. It is clear that this definition
implies that each row contains the s integers
0,1,...,s-1, each repeated
[lambda]st-1
times. We shall consider the case where [lambda] = 1 and refer
to such arrays as "orthogonal arrays of index unity."
1952 -- Bose and Bush
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]st."
1960 -- Bose, Chakravarti and Knuth
Bose, R, I. Chakravarti and D. Knuth. 1960. On Methods of Constructing Sets of Mutually Orthogonal Latin Squares Using a Computer. II Technometrics. 3(1): 111-117.
"In [1] a method of searching for sets of mutually orthogonal
Latin squares of size v = 4t where 4t 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].
1961 -- Johnson, Dulmage and Mendelsohn
Johnson, D., A. Dulmage and N. Mendelsohn. 1961. Orthomorphisms of Groups and Orthogonal Latin Squares. I Canadian 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."
1961 -- Yamamoto
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."
1962 -- Collison
Collison, D. 1962. Algorithm 117. Magic Square (Even Order). Algorithm 118. Magic Square (Odd Order). Communications of the ACM. 5(8): 435, 436.
Algorithms in Algol.
1963 -- O'Carroll
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
"(i) If S <= N, insert in the Sth position in the Rth row the Bth 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 Bth position among those
still open to it in the Rth row."
1967 -- Wells
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
"In 1948, Sade [3] enumerated reduced
"Using a computer adaptation of Sade's method, the author has
enumerated 8 x 8 reduced Latin squares, I8,
finding I8 = 535,281,401,856."
1971 -- Wells
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)
1975 -- Bammel and Rothstein
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
"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 Ln be the number of latin squares of order n and let Rn be the number of reduced latin squares of order n. (A reduced latin square has the first row and first column in natural, i.e., lexicographic, order). It is easy to see that
(1) Ln = n!(n-1)!Rn."To answer the title question it suffices to determine Rn."
Table 1
n Rn Prime Factorization
1 1 1
2 1 1
3 1 1
4 4 22
5 56 23 . 7
6 9 408 26 . 3 . 72
7 16 942 080 210 . 3 . 5. 1103
8 535 281 401 856 217 . 3 . 1 361 291
9 377 597 570 964 258 816 221 . 32 . 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
Rn (and thus also Ln) still
appears to be extremely difficult."
1980 -- EDM
Combinatorial Theory. Encyclopedic Dictionary of Mathematics. Mathematical Society of Japan. MIT Press. 1980.
"Let [omega] =
{a1,a2,...,an}
be a set of n symbols. An n x n square array
L of n2 symbols taken out of [omega]
is called a Latin square over [omega] (or Latin square of
order n) if there is no repetition of symbols in
each row and in each column of L. It is convenient to
identify the row and column index sets with [omega]. Thus, we may
write z=x.y if the entry of L in the
row x and column y is the symbol z. Then we
can describe the Latin square as a binary operation system
([omega],.) . . . ." "On the other hand, if we take the
n2 triplets xyz formed in this way, then
the set of all these triplets forms an error-correcting code . . . ."
A Latin square L over [omega] is called reduced
(or in standard form) if both the row a1 and the
column a1 consist of the natural sequence
a1,a2,...,an.
Thus the binary operation system ([omega],.) has an identity
element a1, and hence is a quasigroup. The
number of Latin squares over [omega] is n!(n-1)!
times the number of L(n) of reduced Latin squares
of order n. The number L(n) has been
calculated for 1984 -- Bose and Manvel
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 s2 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
1987 -- Stein
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."
1987 -- Kull and Specker
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
mutually orthogonal latin squares
("MOLS" [3])."
1987 -- Massey, Maurer and Wang
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,PZ) to be perfect if X and Y are statistically independent."
"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."
1987 -- Hunter
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.
1989 -- Wolf
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:"
"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'."
1990 -- Godsil and McKay
Godsil, C. and B. McKay. 1990. Asymptotic Enumeration of Latin Rectangles. Journal of Combinatorial Theory, Series B 48: 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 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 )
2
for 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 . . . ."
1991 -- Denes and Keedwell
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 L1 = ||aij|| and L2 = ||bij|| on n symbols, say 1,2,...,n, are said to be orthogonal if every ordered pair of symbols occurs exactly once among the n2 pairs (aij,bij), 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."
1991 -- Camion, Carlet, Charpin and Sendrier
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 . . . ."
1992 -- Shao and Wei
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
"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] n
where B[n] is the set of n x n (0,1) matrices,
sigma0(A) is the number of zero elements in the matrix A and
per A is the permanent of the matrix A."
"Definition 1. Let
"For any
per A = SUM( a[1,i1] a[2,i2] ... a[m,im] ) .
(i1,...,im) in Sn(m)
"For the special case m = n we have
per A = SUM( a[1,i1] a[2,i2] ... a[n,in] ) .
(i1,...,in) in Sn(n)
"Definition 2. An 1995 -- McKay and Rogoyski
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 1033
12 1100000 1.62 x 1044
13 400000 2.51 x 1056
14 200000 2.33 x 1070
15 20000 1.5 x 1086
[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 10102, or about
2339./tfr]
1996 -- Jacobson and Matthews
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
"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]
1998 -- Laywine and Mullen
Laywine, C. and G. Mullen. 1998. Discrete Mathematics Using Latin Squares. John Wiley & Sons.
"We now ask a much more difficult question: for each
"If In denotes the number of reduced latin
squares of order n, and n! the usual product of
"Theorem 1.2. For each n>=2 the total number
Ln of latin squares of order n is given by
Ln = n!(n - 1)!In
"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
Last updated: 2003-12-21 (from 1998-05-29)