Keedwell / Dénes Latin Squares and Their Applications

Latin Squares and Their Applications
2. Auflage 2015
ISBN: 978-0-444-63558-7
Verlag: Elsevier Science & Techn.
Format: EPUB
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 455 Seiten

Latin Squares and Their Applications, Second edition offers a long-awaited update and reissue of this seminal account of the subject. The revision retains foundational, original material from the frequently-cited 1974 volume but is completely updated throughout. As with the earlier version, the author hopes to take the reader 'from the beginnings of the subject to the frontiers of research'. By omitting a few topics which are no longer of current interest, the book expands upon active and emerging areas. Also, the present state of knowledge regarding the 73 then-unsolved problems given at the end of the first edition is discussed and commented upon. In addition, a number of new unsolved problems are proposed. Using an engaging narrative style, this book provides thorough coverage of most parts of the subject, one of the oldest of all discrete mathematical structures and still one of the most relevant. However, in consequence of the huge expansion of the subject in the past 40 years, some topics have had to be omitted in order to keep the book of a reasonable length. Latin squares, or sets of mutually orthogonal latin squares (MOLS), encode the incidence structure of finite geometries; they prescribe the order in which to apply the different treatments in designing an experiment in order to permit effective statistical analysis of the results; they produce optimal density error-correcting codes; they encapsulate the structure of finite groups and of more general algebraic objects known as quasigroups. As regards more recreational aspects of the subject, latin squares provide the most effective and efficient designs for many kinds of games tournaments and they are the templates for Sudoku puzzles. Also, they provide a number of ways of constructing magic squares, both simple magic squares and also ones with additional properties. - Retains the organization and updated foundational material from the original edition - Explores current and emerging research topics - Includes the original 73 'Unsolved Problems' with the current state of knowledge regarding them, as well as new Unsolved Problems for further study

He has spent almost the whole of his teaching career at the University of Surrey. Since retirement from teaching he has been an Honorary Senior Research Fellow at that Institution. He is the author of some ninety research papers and two books, most related in some way to latin squares. He is a Foundation Fellow of the Institute of Combinatorics and their Applications and a member of the Editorial Board of \Quasigroups and Related Systems'. He was the _x000C_rst secretary of the British Combinatorial Committee and continued to serve in that capacity for 8 years. Also, he was one of the organizers of the 1991 British Combinatorial Conference and editor of its Proceedings. He is probably best known internationally as one of the authors of \Latin Squares and their Applications' of which the present book is a re-written and updated new edition.

Autoren/Hrsg.

Keedwell, A. Donald

Dénes, József

Leseproben

Chapter 1 Elementary properties
In this preliminary chapter, we introduce a number of important concepts which will be used repeatedly throughout the book. In the first section, we briefly describe the history of the latin square concept and its equivalence to that of a quasigroup. Next, we explain how those latin squares which represent group multiplication tables may be characterized. We mention briefly the work of Ginzburg, Tamari and others on the reduced multiplication tables of finite groups. In the third, fourth and fifth sections respectively, we introduce the important concepts of isotopy, parastrophy1 and complete mapping, and develop their basic properties in some detail. In the final section of the chapter we discuss the interrelated notions of subquasigroup and latin subsquare. 1.1 The multiplication table of a quasigroup
As we remarked in the preface to the first edition, the concept of the latin square is of very long standing and indeed arose very much earlier than the date of 1723 mentioned there. For details, see Wilson and Watkins(2013) and especially Chapter 6 thereof (written by L.D. Andersen). However, so far as the present author is aware, the topic was first systematically developed by Euler. A latin square was regarded by Euler as a square matrix with n2 entries using n different elements, none of them occurring twice within any row or column of the matrix. The integer n is called the order of the latin square. (We shall, when convenient, assume the elements of the latin square to be the integers 0, 1, …, n - 1 or, alternatively, 1, 2, …, n, and this will entail no loss of generality.) Much later, it was shown by Cayley, who investigated the multiplication tables of groups, that a multiplication table of a group is in fact an appropriately bordered special latin square. [See Cayley(1877/8) and (1878a).] A multiplication table of a group is called its Cayley table. Later still, in the 1930s, latin squares arose once again in the guise of multiplication tables when the theory of quasigroups and loops began to be developed as a generalization of the group concept. A set S is called a quasigroup if there is a binary operation (·) defined in S and if, when any two elements a, b of S are given, the equations ax = b and ya = b each have exactly one solution.2 A loop L is a quasigroup with an identity element: that is, a quasigroup in which there exists an element e of L with the property that ex = xe = x for every x of L. However, the concept of quasigroup had actually been considered in some detail much earlier than the 1930s by Schroeder who, between 1873 and 1890, wrote a number of papers on “formal arithmetics”: that is, on algebraic systems with a binary operation such that both the left and right inverse operations could be uniquely defined. Such a system is evidently a quasigroup. A list of Schroeder’s papers and a discussion of their significance3 can be found in Ibragimov(1967). In 1935, Ruth Moufang published a paper [Moufang(1935)] in which she pointed out the close connection between non-desarguesian projective planes and non-associative quasigroups. The results of Euler, Cayley and Moufang made it possible to characterize latin squares both from the algebraic and the combinatorial points of view. A number of other authors have studied the close relationship that exists between the algebraic and combinatorial results when dealing with latin squares. Discussion of such relationships may be found in Barra and Guérin(1963a), Dénes(1962), Dénes and Pásztor(1963), Fog(1934), Schönhardt(1930) and Wielandt(1962). Particularly in practical applications it is important to be able to exhibit results in the theory of quasigroups and groups as properties of the Cayley tables of these systems and of the corresponding latin squares. This becomes clear when we prove: Theorem 1.1.1 Every multiplication table of a quasigroup is a latin square and conversely, any bordered latin square is the multiplication table of a quasigroup. Proof Let a1, a2, …, an be the elements of the quasigroup and let its multiplication table be as shown in Figure 1.1.1, where the entry ars which occurs in the r-th row of the s-th column is the product aras of the elements ar and as. If the same entry occurred twice in the r-th row, say in the s-th and t-th columns so that ars = art = b say, we would have two solutions to the equation arx = b in contradiction to the quasigroup axioms. Similarly, if the same entry occurred twice in the s-th column, we would have two solutions to the equation yas = c for some c. We conclude that each element of the quasigroup occurs exactly once in each row and once in each column, and so the unbordered multiplication table (which is a square array of n rows and n columns) is a latin square. Fig. 1.1.1 In fact, a quasigroup has more than one multiplication table because it is always possible to permute the rows and/or columns, together with their bordering elements (an example is given in Figure 1.3.2). So, a given quasigroup defines a number of different (although closely related4) latin squares. Conversely, a given latin square defines a multiplication table for more than one quasigroup4 depending upon the order in which its elements are attached to form the borders. As a simple example of a finite quasigroup, consider the set of integers modulo 3 with respect to the operation defined by a * b = 2a + b + 1. A multiplication table for this quasigroup is shown in Figure 1.1.2 and we see at once that it is a latin square. Fig. 1.1.2 More generally, the operation a * b = ha + kb + l, where addition is modulo n and h, k and l are fixed integers with h and k relatively prime to n, defines a quasigroup on the set Q = {0, 1, …, n - 1}. As a special case of this, the operation a * b = 2a - b defines a quasigroup for which a * a = a. Quasigroups for which a * a = a for all elements a are called idempotent (see Section 2.1). Let us draw attention here to another useful concept. Definition A latin square is said to be reduced or to be in standard form if, in its first row and column, the symbols occur in natural order. For example, the latin square of Figure 1.1.2 takes reduced form if its first two rows are interchanged. We end this preliminary section by drawing the reader’s attention to the fact that quasigroups, loops and groups are all examples of the primitive mathematical structure called a groupoid. Definition A set S forms a groupoid (S, ·) with respect to a binary operation (·) if, with each ordered pair of elements a, b of S is associated a uniquely determined element a · b of S called their product. If a product is defined for only a subset of the pairs a, b of elements of S, the system is sometimes called a half-groupoid. [See, for example, Bruck(1958).] A groupoid whose binary operation is associative is called a semigroup. Theorem 1.1.1 shows that a multiplication table of a groupoid is a latin square if and only if the groupoid is a quasigroup. Thus, in particular, a multiplication table for a semigroup is not a latin square unless the semigroup is a group. 1.2 The Cayley table of a group
Next, we take a closer look at the internal structure of the multiplication table of a group. Theorem 1.2.1 Any Cayley table of a finite group G (with its bordering elements deleted) has the following properties: (1) It is a latin square, in other words a square matrix ?aik? in which each row and each column is a permutation of the elements of G. (2) The quadrangle criterion holds. This means that, for any indices i, j, k, l and i', j', k', l', it follows from the equations aik = ai'k', ail = ai'l' and ajk =...