From: Robin Chapman Newsgroups: sci.math Subject: Re: Euler's squares - Where to find examples on the web? Date: Wed, 13 May 1998 13:22:00 GMT In article <6jbqs4$4p9$1@simian.nlr.nl>, wrote: > > On the web I've found several statements about Graeco-Latin squares, also > known as Euler's squares. I'm trying to collect a number of examples of > different sizes. They seem to exist for all odd numbers and multiples of 4. > Also for even numbers above 6 they should exist according to Parker, Bose & > Shrikhande, who proved this with an example of a Greaco Latin square of size > 10. > > I would like to use them for experimental design of experiments with two > independent variables spread evenly along the persons & runs to avoid > learning effects AND effects of combinations of the two variables. right now > I'm looking for an example of size 8, but for the future any size could be > useful. Order 8 are quite easy to construct from the theory of finite fields. There is a field k of 8 elements. In fact k = {0, 1, a, a^2, ..., a^6} where the elements obey the algebraic rules: 1 + 1 = 0 (and so by the distributive law b + b = b(1 + 1) = 0 for all b) and a^3 = a + 1. This is excellent news, since we can construct q - 1 mutually orthogonal Latin squares of size q when there is a field of k elements. To do this pick a non-zero t in the field k and label the rows and columns of the square by the elements of k. Then fill in the entry in row b and column c with tb + c. Each such t gives a Latin square and different t give orthogonal squares. for q = 8 I get the following examples (where I've relabelled the elements of k as b,..., i in the order shown) for t = 1 and t = a. bcdefghi cbfidhge dfbgceih eigbhdfc fdchbieg ghedibcf hgifecbd iehcgfdb and bcdefghi dfbgceih eigbhdfc fdchbieg ghedibcf hgifecbd iehcgfdb cbfidhge (I hope). > So far I've found Graeco-Latin squares of size 4 and 10. Who knows where I > can find more examples or maybe even an algorithm to generate the squares? I'm sorry, it's not on the web, but a good introduction can be found in van Lint and Wilson, A Course in Combinatorics, Cambridge UP, 1992. For instance they give one construction, which produces a pair of orthogonal Latin squares of size 2m+1 from a pair of size m. [Jargon: I apologize, I have used the term "pair of orthogonal Latin squares" instead of "Graeco-Latin" square. They mean the same though.] Robin Chapman + "They did not have proper Department of Mathematics - palms at home in Exeter." University of Exeter, EX4 4QE, UK + rjc@maths.exeter.ac.uk - Peter Carey, http://www.maths.ex.ac.uk/~rjc/rjc.html + Oscar and Lucinda -----== Posted via Deja News, The Leader in Internet Discussion ==----- http://www.dejanews.com/ Now offering spam-free web-based newsreading ============================================================================= From: Robin Chapman Newsgroups: sci.math Subject: Re: Euler's squares - Where to find examples on the web? Date: Thu, 14 May 1998 11:00:15 GMT In article <355aab94.0@news1.ibm.net>, SAPDMCPC22@ wrote: > > In <6jc6po$p79$1@nnrp1.dejanews.com>, Robin Chapman writes: > >In article <6jbqs4$4p9$1@simian.nlr.nl>, > > wrote: > >> > > > >I'm sorry, it's not on the web, but a good introduction can be found > >in van Lint and Wilson, A Course in Combinatorics, Cambridge UP, 1992. > >For instance they give one construction, which produces a pair of orthogonal > >Latin squares of size 2m+1 from a pair of size m. > > Are you sure that you don't mean: > Let Q_1,...Q_r be MOLS of order m and L_1,...,L_r MOLS of order n > then Q_i x L_i give rise of r MOLS of order nm ? > Even since for 2m+1=n =1 mod 2 trivally by the Cayley table of (Z_n,+) > and Q_2 =(a_(ij)) with a_ij = 2*i + j mod n a pair of MOLS is given. No. What I wanted was 3m + 1 (not 2m + 1). :-( Robin Chapman + "They did not have proper Department of Mathematics - palms at home in Exeter." University of Exeter, EX4 4QE, UK + rjc@maths.exeter.ac.uk - Peter Carey, http://www.maths.ex.ac.uk/~rjc/rjc.html + Oscar and Lucinda -----== Posted via Deja News, The Leader in Internet Discussion ==----- http://www.dejanews.com/ Now offering spam-free web-based newsreading ============================================================================== Newsgroups: sci.math From: kemoauc@de.ibm.com Subject: Re: Euler's squares - Where to find examples on the web? Date: 13 May 1998 14:12:45 GMT In <511@stt.win-uk.net>, iain@stt.win-uk.net (Iain Davidson) writes: > >In article <6jbqs4$4p9$1@simian.nlr.nl>, "Jacco Hoekstra" (hoekstra.nospam@nlr.nl) writes: >>On the web I've found several statements about Graeco-Latin squares, also >>known as Euler's squares. I'm trying to collect a number of examples of >>different sizes. They seem to exist for all odd numbers and multiples of 4. >>Also for even numbers above 6 they should exist according to Parker, Bose & >>Shrikhande, who proved this with an example of a Greaco Latin square of size >>10. >> >>I would like to use them for experimental design of experiments with two >>independent variables spread evenly along the persons & runs to avoid >>learning effects AND effects of combinations of the two variables. right now >>I'm looking for an example of size 8, but for the future any size could be >>useful. >> >>So far I've found Graeco-Latin squares of size 4 and 10. Who knows where I >>can find more examples or maybe even an algorithm to generate the squares? > >If a book is acceptable then > >Constructions and Combinational Problems in Design of Experiments >Damaraju Raghavarao >Wiley Series in Probability and Mathematical Statistics >John Wiley and Sons Inc. (1971) > >gives a very clear account of Latin squares, Graeco-Latin squares >and many other constructions relating to the design of experiments. > >Graeco-Latin squares with an order that is prime or the power of a >prime are very easy to construct from Galois fields. There is also >a full set of mutually orthogonal Latin squares or a >hypergraeco-Lation square. > >The GL square of order 8 that you want is 2^3 and so will be easy to >construct and there will be a set of 7 mutually orthogonal Latin >squares > >Iain Davidson Tel : +44 1228 49944 >4 Carliol Close Fax : +44 1228 810183 >Carlisle Email : iain@stt.win-uk.net >England >CA1 2QP Another good reference will be Beth, Jungnickel, Lenz Design Theorie B.I. Under availability of a (commutative) ring with '1' ( e.g. Z_n) you can construct MOLS (mutually orthogonal Latin squares) by Q_x =( a_(ij)) with a_(ij) = ix + j (mod Ring) if x is a unit in the ring. For Z_8 then there will be Q_1,Q_3,Q_5 and Q_7 as a set of MOLS. n=2 and n=6 are the only values (>1 of course) that doesn't provide at least two MOLS. It is unknown if there are other values as n= p^k (p prime) that give raise of a full set of MOLS (i.e. |MOLS| = n-1 occurs). Thereby they don't need to be constructed over GF(p^k). Another 'structure' for constructing some special kinds of MOLS are so called 'Difference matrices'. Interestingly even the Bose/Parker/Shrikehand example (n=10) is constructable by such a Difference matrix. It's open too if there are a set of three MOLS of order 10 .(AFAIK) ============================================================================== Date: Thu, 18 Feb 1999 19:54:16 -0800 To: rusin@math.niu.edu From: Greig Subject: Re: 98/graeco-latin Finding Graeco-Latin Squares A latin square of order n is an arrangement of n symbols in a square of side n such that each row and each column contains every symbol. A set of m mutually orthogonal latin sqares (MOLS) of order n is a set of m latin squares of order n, such that when any pair are superimposed each of the n^2 ordered pairs occurs exactly one. A set of 2 MOLS is sometimes called a Graeco-Latin square. We aim to give explicit constructions for Graeco-Latin squares for all orders except 2 and 6. Note that we can trivially construct an arbitary number of MOLS of order 1, (and order 0 too, since here they are all of size 0) Examples: n=3 0 1 2 0 1 2 1 2 0 2 0 1 2 0 1 1 2 0 n=4 00 01 10 11 00 01 10 11 00 01 10 11 01 00 11 10 10 11 00 01 11 10 01 00 10 11 00 01 11 10 01 00 01 00 11 10 11 10 01 00 01 00 11 10 10 11 00 01 Note that in both of these examples we could have just given the first columns of the squares as 0 0 00 00 00 1 2 01 10 11 2 1 10 11 01 11 01 10 since the remaider of these squares is generated by adding the elements of the Galois Field GF(3) or GF(4). Actually, apart from the first row, these generators are the multiplication table of the field, with the ordering x^0, x^1, ..., x^{q-1} where x is a root of a primitive polynomial in the field (here x-2=0 and x^2+x+1=0). This construction generalizes to any GF(q) where q is a prime power. Primitive polynomials for GF(8) and GF(9) are x^3+x^2+1 and x^2+x+2, which give the orderings 001 010 100 101 111 011 110 and 01 10 21 22 02 20 12 11, where we write the polynomial ax+b simply as ab, etc. There are a couple of equivalent ways of writing down these MOLS. The first is as on orthogonal array, (an OA). for n=3 our example gives the OA. 0 0 0 1 1 1 2 2 2 0 1 2 0 1 2 0 1 2 0 1 2 1 2 0 2 0 1 0 1 2 2 0 1 1 2 0 Where we can use the first row as the row index, and the second as the column index, and the third row gives the first square, and the last row gives the second square. Clearly, any set of m MOLS of order n gives an (m+2) by n^2 OA(n,m+2) and given the OA, we can generate the m MOLS (actually, we can pick any pair of rows of the OA to serve as the row and column indices for the squares.) The defining property of an OA is that, for any pair of rows, the n^2 columns span the ordered pairs. An equivalent representation of an OA(n,m+2) is as an incidence matrix, N, of a transversal design, (a TD(m+2;n)). We form this on n(m+2) points by adding the row label (0... m+1) to the element of the OA entry, and use the column to represent the line the points are incident on (so the last line contains the points 02 12 21 30). N has the property that NN' has a block diagonal form, with m+2 n*identity matrix of order n on the diagonal, and unities elsewhere. A pair of points that do not appear together in any block are said to be in the same group. There are m+2 groups, each of size n. Two examples of incomplete OAs are 0 x 0 1 6 y 0 2 5 z 0 3 4 0 0 6 4 1 x 1 4 0 y 2 6 0 z 8 9 0 0 0 x 6 1 0 y 5 2 0 z 4 3 0 1 0 6 4 0 x 1 4 0 y 2 6 0 z 8 9 0 1 6 x 0 2 5 y 0 3 4 z 0 0 4 1 0 6 4 0 x 1 6 0 y 2 9 0 z 8 0 6 1 0 x 5 2 0 y 4 3 0 z 0 6 4 1 0 1 4 0 x 2 6 0 y 8 9 0 z We form the OA(10,4) and OA(14,4) by developing each of the above columns over Z_7 and Z_{11}, (treating x,y,z as fixed elements), then appending an OA(3,4) to each. Although the construction we have give above shows that it is possible to construct q-1 MOLS of order q whenever q is a primepower, it relies upon us knowing a primitive polynomial for GF(q). We can give a direct construction of 3 MOLS of order n whenever n is not divisible by 2 or 3, as follows: Form 5 by n array whose ith column is (x_i, 0, i, 2i, 4i)' for i=0,...n-1, and develop over Z_n, treating the x_i's as fixed elements, then after this development replace x_i by i. This gives the required OA(5,n). Lemma If we have t MOLS of orders m and n, then we have t MOLS of order mn. Proof We take as the symbol set the ordered pairs of symbols. We form the order mn squares as m by m block structure matrices with each submatrix block having size n by n. If the k-th square of the order n square contains the symbol a in location (R,C) and the k-th square of the order m square contains the symbol m in location (r,c), then the k-th square of the order mn square will contain the symbol ab in location (R_r,C_c). QED So far, we have dealt with all orders except those of orders = 2 mod 4. Lemma If n = 2 mod 4, then we can write n = 3q+t, with odd t <= q, and t <= 13, and q odd and not divisible by 3 provided n \not\in {2,6,10,14,30}. Proof This follows for the larger cases (n>39) by noting that at least one of q,q+2 is not divisible by 3, and by inspection for the smaller cases. QED Note that 30=3*9+3, and we have dealt with 10 and 14 (and avoided 2 and 6), so in all remaining cases we can write the desired n as n=3q+t, with t<=q, s.t. we can construct 2 MOLS of order t, and 3 MOLS of order q. The final step is to emloy Wilson's construction to deal with the remaining cases. We shall construct the TD form, a TD(4;3q+t), starting with a TD(5;q) from which we delete some points in the same group, truncating that one group down to size t. This produces a design with blocks of size 4 and 5. For each block in this design, we construct a TD(4;3) or TD(4;4) depending on the original block size. Suppose that block contains, say, the points (0a, 1b, 2c, 3d, 4e) (with the point 4e missing for t <= e < q), then the point set we construct the TD on is 0a x {0,1,2}, 1b x {0,1,2}, 2c x {0,1,2}, 3d x {0,1,2}, {0,1,2,3} x 4e. (Here a,b,c,d are in {0,1,...,q-1}). The four groups of this TD are defined by the first element of the point set. W.l.o.g. we can assume there is a block (04e,14e,24e,34e) which we remove (when t<=e, wrote: >Does someone have suggestions for images of geometrical objects that >make nice desktop background pictures? Preferably more interesting than >just polyhedra. To make a nice picture, it should be large/hi-res and >with many colors. > >Probably mathematical objects (surfaces, fractals) are easiest to find, >although I would be very happy about examples from physics too. > I don't know if this is what you want, (you seem to be asking for more complicated items than this) but i created an order-10 Graeco-Latin square in a bitmap for my background. The ten digits are each represented with a different color. I think it turned out rather nice, although it probably won't compare with mesh- frame diagrams of a stellated dodecahedron. If you want, i can uuencode it and mail it off (or post it here if anyone cares). (For those wondering what the big deal is with an order-10 Graeco-Latin square, well, up until the 1959, it was thought to be impossible. A G-L square is a combination of two order-n matrices that individually have one digit (1..n) that occurs in only one row and column. A 3x3 example is: 1:1 2:2 3:3 2:3 3:1 1:2 3:2 1:3 2:1 A better (believe me) explanation can be found in Martin Gardner's *New Mathematic Diversions From Scientific American*, the chapter "Euler's Spoilers".) -john February 28 1997: Last day libraries could order catalogue cards from the Library of Congress. -- Pursuant to US Code, Title 47, Chapter 5, Subchapter II, '227, any and all unsolicited commercial E-mail sent to this address is subject to a download and archival fee in the amount of $500 US. E-mailing denotes acceptance of these terms. ============================================================================== From: Fred Galvin Subject: Re: Latin squares Date: Fri, 21 Jan 2000 18:56:05 -0600 Newsgroups: sci.math On Sat, 22 Jan 2000, Henrik [iso-8859-1] B=E4=E4rnhielm wrote: > Can anyone give me some sources, www-pages would be nice, I have books > already, where I can read about latin squares? Also, do anyone know of > any simple, concrete application of them? There must be, I think, > because they seem so nice, but the only applications I can think of > myself is very artificial... All I can think of is the book _Latin Squares and Their Applications_ by J. Denes and A. D. Keedwell but it sounds like you already have that.