Latin Squares: A Literature Survey (original) (raw)

Research Comments fromCiphers By Ritter

Terry Ritter

ALatin square oforder n is an n by _n_array containing symbols from somealphabet 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 somecryptographic applications, a Latin square can be seen as astream cipher combiner, a sort of generalizedexclusive-OR function. A Latin square combiner isinvertible 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 internalstate which may bekeyed, and that combining operations using keyed squares will benonlinear. 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, anorthogonal pair of Latin squares can be seen as ablock mixer, for relatively smallblocks. These squares can be constructed or selected from among a plethora of such squares, thus supportingkeying. 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 arithmeticbutterfly operations normally used inFFT'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 handleextremely large block widthsis very welcome, since that supports desirable features like fastdynamic keying and inherent per-blockauthentication.

Contents

1934 -- Fisher and Yates

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)! squares, all different, by permutation of all the columns, and all the rows except the first. Only the original square is a reduced square. It is therefore sufficient to enumerate all the reduced squares of the size under consideration."

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

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_n - 1 at most."

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 6 x 6 Graeco-Latin square. He found 1, 1, 4, and 56 standard Latin squares of sides 2, 3, 4 and 5 respectively, using an exhaustive process." "In searching for a 6 x 6 Graeco-Latin square, Euler constructed numerous 6 x 6 Latin squares and employed intercalate reversal to generate further Latin squares." "Euler proved the impossibility of a Graeco-Latin square on a cyclic Latin square of even side."

"Fisher & Yates (1934) enumerated the 6 x 6 Latin squares by a method different from that of Tarry, and found 9408 squares of 17 types, none of the 17 types having Graeco-Latin solutions." "They point out that there are 22 sets of which 7 are self-adjugate and the remainder belong to 5 adjugate triplets. Each triplet contains a conjugate pair, and if their identity is recognized but not that of the adjugate member, there appear to be 17 types, whereas recognizing adjugacy there are seen to be only 12 species."

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

The Latin square

"A Latin square of side s is an arrangement of_s_<sup2< sup=""> 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

</sup2<>

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]ux+uy}

u[lambda] = constant <> 0
_ux,uy_= 0,1,_u_2,...,u _s_-1

where u[lambda]ux+uy_is the letter in row ux and column_uy."

1942 -- Mann

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, ...,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."

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]."

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]s _t_-1times. 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 = 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].

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 N x _N_Latin square, the first R - 1 rows have been completed and in the _R_th row I - 1 elements have been filled in. Let AJ be the number of different letters that can be inserted in the _J_th position in the R_th row without violating the condition for a Latin square. If the_J_th position has already been filled then_AJ = 0, otherwise J is obtained by counting the number of different letters that have not already been included in either the _R_th row or the _J_th column. Let AN + K be the number of different positions in the R_th row in which the K_th letter of the alphabet can be inserted. If the K_th letter of the alphabet has already been used in this row then_AN + K = 0. Let AS be the smallest non-zero value in the set_A_1,A_2,...,A_2_N, and B be a random integer in the range 1 to_AS. (If there is a tie, the choice of_AS among the subset of jointly smallest elements is immaterial; that with the smallest value of S within this subset can conveniently be taken). The next step in constructing the square is then determined by the values of_S and B, as follows"

"(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."

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 6 x 6 Latin squares. A 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!)3transformations in all).

"In 1948, Sade [3] enumerated reduced 7 x 7squares by a method which by-passes the construction of species representatives. (His total of 16,942,080, however, did lead to the discovery of the 147th species [4] which had been overlooked by Norton [2].) Sade's method is to successively calculate for_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."

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 7 x 7 Latin squares, and by adapting his method to the Maniac II computer, Wells [2,3] enumerated the reduced 8 x 8 squares. We used an improved algorithm for determining equivalence classes in Latin rectangles, which made enumeration of the9 x 9 squares feasible."

"Sade's method is based on the fact that equivalent Latin rectangles can be filled out to complete_n_ x n Latin squares in the same number of ways (have the same count) where equivalent rectangles are intertransformable by column and label permutations such that corresponding columns have the same set of (unordered) symbols. The number of squares is then the sum of counts over all equivalence classes. The count of a k x n rectangle is computed by forming all (k+1) x n rectangles from it, dividing them into equivalence classes, repeating the process for all (k+1) x n rectangles for one representative of each class, and so on, until a convenient stage (usually k = _n_-3 or _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 than1 x 1) resulting from previous partitioning are individually sorted and partitioned in a similar manner where the resulting sorting and partitioning is applied to the entire matrix. It frequently happens that "deadlock" occurs in that there exist sub-matrices larger than 1 x 1 within which rows and columns cannot be differentiated. In this case, we arbitrarily break deadlock by partitioning one of the sub-matrices between its first and second columns and then proceed normally. At each step, the sub-matrix to be operated on is selected by a set of well-defined rules. The matrix is in "conventional form" when it is completely partitioned.

"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

1975 -- Alter

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] = {_a_1,a_2,...,an} be a set of n symbols. An n x n square array_L of _n_2 symbols taken out of [omega] is called a Latin square over [omega] (or Latin square oforder 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_n_2 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 _a_1 and the column _a_1 consist of the natural sequence_a_1,_a_2,...,_an._Thus the binary operation system ([omega],.) has an identity element _a_1, 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 n <= 8; L(1) = L(2) = L(3) = 1,L(4) = 4, L(5) = 56,L(6) = 9,408, L*(7) = 16,942,080,L(8) = 435,281,401,856,L(9) = 377,597,570,964,258,816. Two Latin squares over the same set [omega] are called isomorphic if one is obtained from the other by a combination of permutations of rows, columns, and the entry alphabets. The number L*(n) of nonisomorphic Latin square of order n has been calculated for_n <= 8; L*(1) = L*(2) = L*(3) = 1,L*(4) = L*(5) = 2,L*(6) = 22, L*(7) = 563,L*(8) = 1,676,257." (p. 233)

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 _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 altogether4 * 144 = 576 distinct Latin squares of order 4."

"There are 56 different Latin squares of order 5 in which the initial row and column are in the natural order, each giving rise to5! * 4! = 2,880 different squares by permuting the columns and then the rows other than the initial row. Thus there are 161,280 distinct Latin squares of order 5."

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 ofmutually 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:"

  1. There is a unique x such that a*_b_=x.
  2. There is a unique x such that a*_x_=b.
  3. There is a unique x such that x*_a_=b.
  4. (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'."

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_ = 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 ) 2

for k = O(n_5/12 - e) and_k = o(_n_1/2).

1991 -- Byers

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 n x n matrix L whose entries are taken from a set S of n symbols and which has the property that each symbol from S occurs exactly once in each row and exactly once in each column of L."

"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 calledCayley 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 agraeco-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 In = {1,2,...,n}.A k x n Latin rectangle (k <= n)is a k x n matrix on the set _In,_whose rows are permutations of the letters {1,2,...n} and whose columns do not contain any repeated letter."

"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 m <= n be integers, and Sn(m) the set of all _m_-permutations of the elements in the set In = {1,2,...,n}.

"For any m x n real matrixA = (aij),define the permanent per A of the matrix A to be

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 n x n permutation matrix is a (0,1) matrix of order n, each row and column of which contains exactly one nonzero element." (Apparently this is the_n_ x n (0,1) matrix described initially.)

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 n!(n-1)!/(n-k)!."

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.

1. SUMMARY

"In this article, we construct Markov chain Monte Carlo algorithms for generating random n x n Latin squares: by simulating an ergodic Markov chain whose stationary distribution is uniform over this space, we can obtain Latin squares that are (approximately) uniformly distributed." (p. 405)

"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_n_ >= 2, how many distinct latin squares are there of order 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 Ln denote the total number of distinct latin squares of order n. In an effort to help us calculate Ln, we introduce the notion of a reduced latin square of order n. A latin square of order n based on the numbers0, 1, ..., n - 1 is said to be reduced_if both the first row and the first column are in the standard order 0, 1, ..., n - 1. This restriction significantly reduces the number of latin squares of a given order that need to be considered in the calculation of_Ln.

"If In denotes the number of reduced latin squares of order n, and n! the usual product of_n_(n - 1)(n - 2) ... (2)(1),we have

"Theorem 1.2. _For each n_>=2 the total numberLn 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 n - 1 rows in any of(n - 1)! ways. Once again each of the resulting squares will be latin, distinct from each other, and more important, each of these squares will be distinct from those obtained by any column permutation. This last statement is true since in the row permutations the first row is not disturbed. Thus, starting with a reduced latin square of order n, the_n_! column and (n - 1)! row permutations will result in exactly_n_!(n - 1)! distinct latin squares of order n, and exactly one of these squares will be reduced. Since there are In reduced latin squares of order n, the result follows." (p.4)

Terry Ritter, hiscurrent address, and his top page.

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