Как составить таблицу кэли для умножения

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.

Property (2) was first observed by Frolov(1890a) who remarked that it is valid for any regular latin square (as defined below). Later Brandt(1927) showed that it was sufficient to postulate the quadrangle criterion to hold only for quadruples in which one of the four elements is the identity element. Textbooks on the theory of finite groups [see for example Speiser(1927)] adopted the criterion established by Brandt. Aczél(1969) and Bondesen(1969) have both published papers in which they have rediscovered the quadrangle criterion. Also, Hammel(1968) has suggested some ways in which testing the validity of the quadrangle criterion may in practice be simplified when it is required to test the multiplication tables of finite quasigroups of small orders for associativity.

To use the above theorem to test whether a latin square L is group-based it is often convenient to permute either the rows or symbols of L so that the entries in γ are in natural order (assuming the symbols of L are 1, 2, …, n). Then the elements of ∑ can be read directly from the columns of L. Of course, the same test will work if rows instead of columns are used throughout.

A third condition for a latin square to be group-based arises from a concept also due to Frolov (1890a,b), who called a reduced latin square “regular” if it has the following property: The squares obtained by raising each row in turn to the top and then re-arranging first the columns and then the remaining rows so that the square is again reduced are all the same.

We shall show (in Theorem 1.2.3 and as a corollary to Theorem 2.4.1 of the next chapter) that a latin square is regular in this sense if and only if it is group-based, though it seems that Frolov did not realize this.⁵

Note. If we wish to test whether a latin square is group-based using the Suschkewitsch method, we require n² tests since there are n² pairs of permutations in the set ∑. If we use the method which Frolov used to test whether a latin square is regular, we need at most n tests. In fact, we shall show in the next chapter that at most n/p tests are needed, where p is the smallest prime which divides the order n of the latin square.

Parker(1959a) proposed an algorithm for deciding whether a loop is a group but that author later found an error in his paper and his method turned out to give only a necessary condition, not a sufficient one.

Wagner(1962) proved that to test whether a finite quasigroup Q of order n is a group it is sufficient to test only about 3n³/8 appropriately chosen ordered triples of elements for associativity. However, if a minimal set of generators of Q is known, then it is sufficient to test the validity of at most n²log₂(2n) associative statements provided that these are appropriately selected.

Wagner also showed in the same paper that every triassociative quasigroup Q (that is, every quasigroup whose elements satisfy xy · z = x · yz whenever x, y, z are distinct) is a group, and the same result has been proved independently by D.A.Norton(1960).

These results lead us to ask the question “What is the maximum number of associative triples which a quasigroup may have and yet not be a group?”

In fact, as Sade(1962) has pointed out, the identities (iv) and (v) are equivalent and so also are (viii) and (ix). For example, if we permute the elements a, b, c in (v) it becomes b(ca) = a(bc), which is (iv).

More recently, it has been shown with computer aid that there are just four identities of length at most six (if we exclude mirror images and re-labellings) which force a quasigroup to be a group: namely, (A) a·bc = ab·c, (B) a·bc = ac·b, (C) a · bc = ca · b and (D) a · bc = b · ca. Moreover, all but the first of these forces the group to be abelian. See Fiala(2007) and Keedwell(2009a,b).

A Cayley table of a group is called normal if every element of its main diagonal (from the top left-hand corner to the bottom right-hand corner) is the identity element of the group [see page 4 of Zassenhaus(1958)].

If the notation of Theorem 1.1.1 is used, it follows as a consequence of the definition that a normal multiplication table ‖a_ij‖ of a group has to be bordered in such a way that aij=aiaj−1 holds. Thus, if the element bordering the i-th row is a_i, the element bordering the j-th column must be aj−1.

The same idea was mentioned again by Ginzburg(1964), who gave a reduced multiplication table for the quaternion group of order 8. Later, in Ginzburg(1967), he developed the concept in much more detail and gave full proofs of his results. This paper contains, among other things, a complete list of the minimal generalized normal multiplication tables for all groups of orders up to 15 inclusive.

It will be clear to the reader that of special importance to the theory is the determination of the minimal number of rows and columns of a generalized normal multiplication table. If r denotes the minimal number of rows (or columns), then Erdős and Ginzburg(1963) proved that r < C(n² log n)^1/3 (where C is a sufficiently large absolute constant) while Ginzburg(1967) showed that, in general, r > n^2/3 and that, for the cyclic group C_n of order n, r < (6n²)^1/3.

For further generalizations of the concept of a generalized normal multiplication table and for discussion of some of the mathematical ideas relevant to it, the reader should consult Ginzburg(1960), Ginzburg and Tamari(1969a,b), Tamari(1960) and Specnicciati(1966).

The perceptive reader will realize that these ideas may have application in coding and cryptography.

(4) Two-dimensional coding problems

The coding and transmission of pictures, one aspect of which we discussed in the previous section, may be regarded as one kind of two-dimensional coding problem in which latin squares have a role to play. Another concerns the allocation of frequencies in a mobile radio telephone system and a third arises in connection with the so-called two dimensional codes (especially cyclic codes) which have recently become a subject of attention.

In a mobile radio telephone system, each region is served by a local transmitter and it is required to allocate frequencies to these transmitters in such a way that there is no interference between neighbouring transmitters. Consequently, adjacent transmitters must be allocated different frequencies. In practice, each transmitter will require several frequencies for sending messages and further frequencies will be required for receiving back messages from the outstations. Since the total number of frequencies which are available for the system is usually limited, it is important to be able to allocate frequencies as efficiently as possible.

In a recent paper [J. Dénes and A. D. Keedwell (1988)], the present authors have suggested several ways in which the frequency allocation may be carried out. Two of these make use of latin squares and we shall now describe them.

If we suppose that the transmitters are arranged in the form of a rectangular grid, an optimal solution may be obtained as follows:

The 5×5 latin square which we use is one which has appeared many times in the literature of Mathematics. It has the remarkable properties of being both a strict knight’s move square (as defined by P. J. Owens (1987), see also Part II of the present book) and also a totally diagonal latin square or Knut Vik design (as defined by A. Hedayat and W. T. Federer (1975)).

It was shown by E. N. Gilbert (1965) that the number of different Cayley tables of a given cyclic group G of order n is n! (n-1)! (n-1)!/ϕ(n), where ϕ(n) is Euler’s function. For example, when n = 3, this number is 12, as in Figure 4.4.

Another class of two-dimensional arrays which arise in coding theory and which have connections with latin squares are the so-called Costas arrays.

A Costas array is called vertically singly-periodic (horizontally singly-Periodic) if all its vertical translates (horizontal translates), when read cyclically as if on a horizontal (vertical) cylinder, are also Costas arrays. It is known that singly-periodic Costas arrays exist for all orders p-1, where p is a prime number, and the question has been raised as to whether they exist for orders not of this form. Several attempts have been made to solve this problem with the aid of latin squares. In order to be able to show the connection, let us first remark that if we replace the blanks of a Costas array by zeros, we may regard it as a permutation matrix. If the corresponding permutation of the integers 1, 2, …, n maps i to θ(i) then the cells of the array which contain the entry one have co-ordinates [i, θ(i)] and the Costas property requires that the vectors [i+k, θ(i+k)] — [i, θ(i)] and [j+k, θ(j+k)] — [j, θ(j)] be different whenever i≠j. So θ must be a permutation of 1, 2, …, n such that θ(i+k) -θ (i) = θ(j+k)-θ(j) ⇒ i = j for all choices of k, k = 1, 2, …, n−2. We shall call this the first condition on θ.

As an example, the permutation
θ=[1     2    3    4    5    64    1     2    6    5    3] defines the Costas array given in Figure 4.5. We observe that the differences θ(i+1)-θ(i) = −3, 1, 4, −1, −2 are all different, the differences θ(i+2)-θ(i) = −2, 5, 3, −3 are all different, the differences θ(i+3)-θ(i) − 2, 4, 1 are all different and, finally, the differences θ(i+4)-θ(i) = 1, 2 are different. We can exhibit the differences compactly in the form of a triangle as in Figure 4.5.

T. Etzion (1989) has shown that when and only when a Costas array is horizontally singly-periodic, the first condition on θ is replaced by the stronger condition θ(i+k)-θ(i)≡θ(j+k)-θ(j) (mod n) ⇒ i=j for all choices of k, k=1, 2, …, n−2. We shall call this the second condition on θ.

When the second condition on θ holds, the latin square whose (i, j)-th cell contains θ(j)+(i-1) is a Vatican square: that is, a Tuscan-(n-1) square which is a latin square. (For a discussion of these concepts, see Section 5 of Chapter 3.) A Vatican square which takes this particular form (in which the i-th row is obtained by adding i-1 to each of the elements of the first row) is said to be constructed by the polygonal path construction [S. W. Golomb, T. Etzion and H. Taylor (1990)] because, when the vertices of a regular n-gon are numbered 1, 2, …, n in order, the joins θ(i+1)-θ(i) form n-1 directed chords no two of which coincide when the polygon is rotated.

Since the permutation i → θ (i) in Figure 4.8 defines a horizontally singly-periodic Costas array whose non-empty cells have co-ordinates [i, θ(i)], it follows that the Costas array whose non-empty cells have co-ordinates [θ(i),i] or [j, θ^-1(j)] will be vertically singly-periodic. Consequently, each of the permutations j → θ^-1(j+h) defines a Costas array. In particular, this means that, when the six differences θ^-1(j+1)- θ(j), where j = 1, 2, 3, 4, 5, 6 and 6+1 = 1, are read cyclically, every consecutive five of them are distinct and define a proper difference triangle. Moreover, when the six differences θ^-1 (j+h) θ^-1 (j), h = 2, 3, 4, are read cyclically, every consecutive 6-h of them are distinct. Now, it is easy to see that if a sequence of n symbols is arranged in a circle and if every subset of
r≥1+⌊n/2⌋ consecutive symbols has all its members distinct, then the n symbols must be distinct.

In fact, only one systematic construction for vertically singly-periodic Costas arrays is known. This is due to L. R. Welch [see S. W. Golomb and H. Taylor (1982)] and is as follows:

Let p be a prime and α a generating integer of the multiplicative group of the Galois field GF[p]. Then a Costas array of order p-1 is obtained by defining θ(i) = αⁱ, i = 1, 2, …, p-1.

Since θ(i+k)- θ(i) = αⁱ (α^k-1), the defining permutation of a Costas array which is constructed by the Welch method has a stronger property than that required by Theorem 4.4: namely, it satisfies the condition
θ(i+k)- θ(i) = θ(j+k)- θ(j) mod(n+1) ⇒ i = j for all values of k, 1≤k < n, where j+k is computed modulo n. We shall call this the third condition on θ.

It follows then that the (n+1)xn array whose (i, j)-th cell is θ(j) + (i-1) and where arithmetic is modulo n+1, is a circular Vatican array.

[Compare Theorem 5.1 of Chapter 3 and the remarks which follow it and also Theorem 7.4.1 of [DK]. The latter theorem gives a direct construction of a complete set of mutually orthogonal latin squares from an (n+1) × n circular Vatican array of the type whose existence is guaranteed by the third condition on θ.]

Since it appears likely that singly-periodic Costas arrays only exist for orders of the form p-1, we may ask the more interesting (but more difficult) question whether the plane can be filled with Costas arrays in such a way that no one is the translate of any other. In other words, is it possible to construct a latin square of order n such that all those cells which contain the same symbol form a Costas array and no two of these n Costas arrays are translates one of another?

To construct such a latin square, we require n permutations i → θ_u(i), u = 1, 2, …, n, such that (i) each permutation has the difference properties required for it to define a Costas array, (ii) θ_u(i)≠θ_v(i) for u≠v, (iii) θ_v (i)≠θ_u(i+h) and θ_v(i)≠ θ_u(i)-h mod n for any fixed h; where i varies from 1 to n.

Finally, in this Section, we draw attention to the use of a single latin square in connection with the allocation of the pixels of a two-dimensional raster-graphics display to the M memory chips which store the display in such a way that it is possible to copy or alter small rectangles of N pixels very rapidly whatever their shape. Essentially, the requirement is that the N pixels of a randomly chosen rectangle should all be allocated to distinct memory chips. In B. Chor, C. E. Leiserson and R. L. Rivest (1982), the authors have shown that this requirement can be met using only approximately √5N memory chips if the allocation of memory chips to the pixels of the complete array is described by a certain cyclic latin square with rows rearranged in a prescribed way. The prescription for rearranging the rows is described in terms of Fibonacci numbers.

2.4 Group-based latin squares and nuclei of loops

In Section 1.2, we gave three ways of checking whether a given latin square L (which can be assumed to be in reduced form) is group-based: namely, the quadrangle criterion, Suschkewitsch’s test and Frolov’s regularity test. To be certain that L is group-based using the quadrangle criterion, it is necessary either to check every pair of quadrangles which agree in three corresponding places or else to border the square with its own first row and column so as to form the Cayley table of a loop and then check the subset of all such pairs of quadrangles which have the identity of the loop as top left member. [See Brandt(1927)]. Thus, the number of tests required is of order at least n³. If Suschkewitsch’s test is used, it is necessary to check every pair of row (or column) permutations. (See Theorem 1.2.2.) This requires n² tests. If Frolov’s test for regularity is used, it follows from Theorem 1.2.3 that at most n tests are required. However,by treating L as the Cayley table of a loop and making use of the concept of loop nuclei, we show in this section that in fact at most n/2 tests are necessary and this only when the square is idempotent and of even order.

We note that, if every column (or row) of a latin square has the Frolov property, this is equivalent to saying that the latin square is regular. See page 5.

Theorem 1.2.3 is an immmediate corollary to Theorem 2.4.1 since, if and only if all rows(columns) have the Frolov property, the middle nucleus is the whole of Q and so (Q, .) is a group.

However, it is well-known that the order of each of the nuclei of a loop divides the order of the loop. [See, for example, Pflugfelder(1990a) for a proof.] So, if p is the smallest prime which divides the order |Q| of a loop (Q, .) (or reduced latin square L formed by its Cayley table) and if |Q|/p rows, excluding the first, of L have the Frolov property, this is sufficient to ensure that L is group-based since it ensures that at least 1 + (|Q|/p) elements of Q are in the middle nucleus of (Q, .) whereas the maximum size of the middle nucleus is |Q|/p if it is not the whole loop.

(Note that, in particular, for a latin square of odd order, it is sufficient that at most a third of the rows have the Frolov property to be sure that the square is group-based. For a square of prime order, just one row is sufficient. Thus, for use by hand, our third test for a latin square to be group-based is considerably more economic than its two predecessors.)

But it is also well-known [again see Pflugfelder(1990a)] that each of the nuclei is a group and so all the powers of an element of the middle nucleus and likewise the product of each pair of its elements are themselves members. By exploiting these facts, we may reduce further the number of columns (or rows) which we need to test for the Frolov property to ensure that a given latin square is group-based. (When the square is idempotent, no further reduction is possible.)

In Keedwell(2005), the reader intersted in loop theory will find analogues of Theorem 2.4.1 for testing for elements of the left and right nuclei and will also find examples of loops of small order which have such (proper) nuclei.

(2) Without subsquares

One should notice that the latin square constructions described in Section 1 all produce subsquares. We now wish to discuss the problem of constructing latin squares without certain subsquares. Until now only two problems of this type have been considered.

A. Kotzig, C. C. Lindner and A. Rosa (1975) asked if for all n, n ≠ 2, 4, there exists an LS(n) with no order 2 subsquares. Such squares were termed N₂-latin squares and interest in them arose as they could be used to construct sets of disjoint Steiner triple systems. In fact, to construct a set of (v+1)/2 pairwise disjoint Steiner triple systems of order v, v ≡ 3 or 7 (mod 12) and v > 7, they needed an LS((v+1)/2) with at least one column no cell of which was contained in a subsquare of order 2. Clearly N₂-latin squares have this property.

A second problem, posed by A. J. W. Hilton, asks if for all sufficiently large n there exists an LS(n) with no proper subsquares. Following the above notation we will call this an N_∞-latin square.

We will exhibit a complete solution to the first problem and then describe constructions for N_∞-latin squares giving a partial solution to the second. In both problems we use mainly a product construction.

M. McLeish (1975) has remarked that if A and B are N₂-latin squares then so too is their product. As pointed out by R. H. F. Denniston (1978) this now provides a straightforward recursive construction for N₂-latin squares of all orders n, ≠ 2, 4, once N₂-latin squares of order 8, 16, 32, 2k+1, 2(2k+1), and 4(2k+1), where k ≥ 1, have been constructed. Historically, however, progress proceeded along the following lines.

And now the proof.

We now turn to the existence of latin squares with no proper subsquares, N_∞-latin squares. To date the best general result is that for all n ≠ 2^a3^b there exists an N_∞-latin square.

One easily discovers (for example from the list of LS(4) and LS(6) given in [DK, p. 129–137]) that every latin square of order 4 or 6 has a proper subsquare, and that all three of the N₂-latin squares of order 8 are in fact N_∞-latin squares.

A. Rosa (and others) have noted that if there exists a perfect 1-factorization of the complete graph on 2n vertices, K_2n, then there exists an N_∞-latin square of order 2n-1. (A perfect 1-factorization of a graph G is a 1-factorization of G with the property that the union of any two of the 1-factors is a hamiltonian cycle.) Given a perfect 1-factorization of K_2n, with vertices 1, 2, …, 2n, consisting of the 1-factors F₁, F₂, …, F_2n-1, where edge {i, 2n} is in F_i, define the N_∞-latin square A by e_A(i, j) = k if i ≠ j and {i, j} ∈ F_k, and e_A(i, i) = i. Observe that if A has a proper subsquare B containing no cell of the main diagonal of A, then any two elements in B can yield a cycle of length at most twice the order of B, contradicting the fact that they correspond to a hamilton cycle. Since A is symmetric, if B has an entry on the main diagonal, then B is symmetric about the main diagonal and has odd order. It is easy to see that any two elements yield a cycle of length at most one more than the order of B, again a contradiction.

Perfect 1-factorizations of K_2n are known to exist when 2n ∈ {p+1, 2p: p prime}∪{16, 28, 36, 50, 244, 344, 1332, 6860}. These are described in A. Kotzig (1964), B. A. Anderson (1973), (1974), E. Seah and D. R. Stinson (1987), E. C. Ihrig, E. Seah and D. R. Stinson (1987), B. A. Anderson and D. Morse (1974), and a recent personal communication from Z. Kiyasu and M. Kobayashi respectively. Note that while perfect 1-factorizations yield N_∞-latin squares the converse is not true. The smallest unresolved case for perfect 1-factorizations is K₄₀, whereas the smallest order for N -latin squares is 16.

The first results on the existence of N_∞-latin squares were obtained by K. Heinrich (1980) who showed that for distinct primes p and q, there is an N_∞-latin square of order n = pq, n ≠ 6. L. D. Andersen and E. Mendelsohn (1982) generalized this construction to obtain N -latin squares of all orders n ≠ 2^a3^b.

We shall give the construction of L. D. Andersen and E. Mendelsohn (1982); the case n = pq being contained in it. Because of its length and detail the proof will not be given. We begin by defining three latin squares of order t each isotopic to the Cayley table of the cyclic group of order t. Recall that when t is a prime these squares have no proper subsquares.

Notice that in each square cells (1, 1) and (1, 2) contain the entries 1 and 2. Using these we construct N_∞-latin squares of orders n = pm where p is prime and p ≥ 5.

Because Cayley tables were used all proper subsquares of P(p, m) can be located. Having done this we look at the m × 2m subarrary S(p, m) consisting of the first two cells in the first row of each A(p), B(p) and C(p). Clearly S(p, m) is a latin rectangle in which each row contains the entries 1, 2, p+1, p+2, …, (m-1)p+1, (m-2)p+2. From P(p, m) we now construct the N_∞-latin square of order pm, D(p, m), by permuting the rows of S(p, m) according to the permutation ρ = (1 2 3 … m). Clearly D(p, m) is a latin square and it is not difficult to show that all subsquares in P(p, m) have been destroyed. Unfortunately, considerable work is involved in showing that this permutation of S(p, m) does not introduce subsquares.

5.2.11 Abstract group — group table

As realizations of the abstract group of order 3, let us mention the group of rotations leaving an equilateral triangle invariant (rotations around an axis perpendicular to the triangle, the group law being the composition of rotations) and the group (Z3, +) of residues modulo 3 (the law group being the addition modulo 3). Along this vein, a realization of the Klein four-group V is the group of rotations leaving a rhombus invariant and realizations of the cyclic group C₄ are the group of rotations leaving a square invariant and the group (Z4, +).

Characters tables.

Characters are constant over conjugacy classes, that is, χ (hgh⁻¹) = χ (g) for all g and h in G, owing to the invariance of a trace over cyclic permutation of matrices. On equipping the set of all the functions ϕ over G into C such that ϕ (hgh⁻¹) = ϕ (g) ∀g ∈ G and ∀h ∈ G with addition and multiplication by a complex number, we get a vector space K, the dimension of which is the number of the conjugacy classes in G. The characters χ ^U of the irreducible matrix representations Γ ^U of G forms in K an orthonormal set since 〈χ ^V|χ ^U〉 = 1 if U = V and 0 if U ≠ V. We prove that it is a basis for showing that if {ϕ |χ ^U} = 0 ∀χ ^U then Σ_g∈Gϕ (g)χ (g) = 0 so that ϕ = 0 on choosing χ = χ ^reg. Thus, the number of the irreducible matrix representations Γ ^U of a group G is equal to the number of the conjugacy classes.

The number of conjugates of an element g of a group G is equal to the number of right cosets of the centralizer CG(g) of g. CG(g) = {x ∈ G | gx = xg} is a subgroup of G, not necessarily invariant. The intersection Z(G) = ∩_g C_G(g) = {x ∈ G |∀g, gx = xg] of all the centralizers is the center of G. Z(G) is an invariant subgroup of G. Any element of Z(G) commutes with all the elements of G and forms a conjugacy class by its own: the cardinal of Z(G) is the number of classes C_e for which n(C_e) = 1.

9.2 Homogeneous latin squares

For example, a cyclic latin square of order 4 is 1-homogeneous whereas a latin square of order 4 based on Klein’s Viergruppe Z₂ × Z₂ is 3-homogeneous.

A latin square which is 0-homogeneous has also been called an N₂—square. (In this notation, a latin square which has no latin subsquares of any size is an N_∞—square. We discuss these in Section 9.4.) By combining the results obtained in a series of papers, it was proved in the late 1970s that N₂-squares exist for all orders n except n = 2 and 4. Details of the proof are given on pages 113-116 of [DK2].

In two unpublished papers by D’Angelo and Turgeon and by Abrham and Kotzig, these authors obtained some further results; in particular, the latter authors show that 4-homogeneous latin squares do not exist if n < 8 but that they do exist of all orders n = 8k. (This leaves open the question whether and/or for which other orders such squares exist.) The former authors mention and/or prove several results: (i) There are 2-homogeneous latin squares of all orders divisible by 4 except 4 itself; (ii) If n = 4k and k ≥ 1, there is an (n − k)- or (n − k + 1)-homogeneous latin square of order n according as k is odd or even; (iii) If A is an h-homogeneous latin square of order m and B is a k-homogeneous latin square of order n, then A × B is an (hk + h + k)-homogeneous latin square of order mn (where A × B denotes the direct product of the quasigroups whose Cayley tables are defined by A and B); (iv) The Cayley table of a group G is an h-homogeneous latin square, where h is the number of elements of order 2 in G (cf. Killgrove’s lemma above). From (iv) it follows that, for each positive integer h ≥ 2, there is an h-homogeneous or (h + 1)-homogeneous latin square of order 2h according as h is odd or even. This last result makes use of the dihedral groups and had already been proved earlier in Heinrich and Wallis(1981) and in Hobbs, Kotzig and Zaks(1982).

So far as the present author is aware, the complete spectrum of integers h for which h-homogeneous latin squares exist is still an open question. But Hobbs and Kotzig(1983) contains a summary of results which were known at the time that paper was written regarding squares of orders up to 26. Another interesting question is: For which integers h do orthogonal h-homogeneous latin squares exist or, alternatively, can it be proved that they do not exist for some values of h? This question is partly answered by remark (iv) above. We notice, for example, that the three mutually orthogonal latin squares which are based on Klein’s Viergruppe are all 3-homogeneous.

(e) Quasi-orthogonal latin squares

It is well-known that a group based latin square has an orthogonal mate if and only if the group possesses a complete mapping or orthomorphism. Similarly, a group based latin square has a quasi-orthogonal mate if and only if the group possesses a quasi-complete mapping (defined below).

A group which has no complete mappings may nonetheless have quasi-complete mappings. This fact also is demonstrated by the triple of mutually quasi-orthogonal latin squares of order four based on the cyclic group of order four (which has no complete mappings) and shown in Figure 10.1.4. They were first given in Bedford and Whitaker(2000b,2003). Because there exist statistical experiments for which a pair of quasi-orthogonal latin squares may serve as well as an orthogonal pair, the former concept may be practically useful. In that connection, Bedford has shown (see below) that quasi-orthogonal latin squares of order six exist, although these are not group based.

In order to introduce the concept of quasi-complete mapping, we shall need the following definition.

Thus, for example, ϕ(3) = 3 + θ(3) = 3 + 3 ≡ 2 mod 4.

If ψ₁ and ψ₂ are permutations of a group (G, ·), where G = {g₁, g₂, …, g_n}, such that ψ₁(g₁)⁻¹ψ₂(g₁), ψ₁(g₂)⁻¹ψ₂(g₂), …, ψ₁(g_n)⁻¹ψ₂(g_n) is a quasi-ordering of G, then ψ₁ and ψ₂ will be called quasi-orthogonal permutations of G. (If, on the other hand, the above sequence is an ordering of G, then ψ₁ and ψ₂ are orthogonal permutations of G.)

Using this concept, Bedford proved the following theorem and corollary.

Hence, from the above theorem and corollary, the latin squares L, Lϕ1, Lϕ2 shown in Figure 10.1.4 are a set of MQOLS.

In a further paper, Bedford and Whitaker(2003), these authors discuss connections between quasi-orthogonal latin squres and various other combinatorial designs. In particular, they consider connections with orthogonal Steiner triple systems (see Section 2.3 and Section 5.4) and with Room squares (see Section 6.4).

First, they point out and prove that there exists a skew Room square of side n if and only if there exists a pair of quasi-orthogonal, symmetric and idempotent latin squares of order n.

In the construction of a Room square from a pair of Room quasigroups which we described in Section 6.4, the multiplication tables of the quasigroups have the properties of being symmetric and idempotent and if, when they are juxtaposed, the ordered pair a, b occurs in row u and column υ (and in row υ and column u by the symmetry), then the unordered pair u, υ occurs as the entry in the cell (a, b) of the Room square. When the juxtaposed squares are quasi-orthogonal, the ordered pair b, a cannot occur because the ordered pair a, b has already occurred twice and, consequently, when cell (a, b) of the square is filled, cell (b, a) is empty as required.

Bedford and Whitaker define two Steiner triple systems to be quasi-orthogonal if the Cayley tables of their associated Steiner quasigroups are quasi-orthogonal. O’Shaugnessy’s construction of Room squares from orthogonal Steiner triple systems is just a special case of the construction discussed above in which the Room pair of quasigroups are both Steiner quasigroups and so are totally symmetric. Consequently, when the Steiner quasigroups are quasi-orthogonal, the Room square is skew. In that case, the orthogonal Steiner triple systems, say S and S′, have the additional property that when (a, b, u) and (c, d, υ) both occur in S and (a, b, υ) and (c, d, w) occur in S′, then w ≠ u. The above authors point out that Dukes and E.Mendelsohn(1999) have introduced such pairs of Steiner triple systems independently and have called them skew-orthogonal rather than quasi-orthogonal. The latter authors have investigated for which orders such pairs of systems exist (or, equivalently, for which orders pairs of quasi-orthogonal totally symmetric idempotent latin squares exist).

Quite recently, Liang(201?) has studied standardized (defined as first row in natural order) quasi-orthogonal latin squares and has shown that some classical results of Parker, MacNeish and Sade can be modified to apply to such squares.

Since the pairs of latin squares which we have just been considering have all been perpendicular pairs, this seems a convenient point at which to discuss such squares more generally.

If a symmetric latin square is of odd order, the elements of its main diagonal are necessarily all different (see Theorem 1.5.4) and so it can be made idempotent. If a second idempotent square of the same odd order 2m + 1 is juxtaposed, the number of distinct ordered pairs then arising can be (1 + 2 + … + 2m) + (2m + 1) = (m + 1)(2m + 1) but not more. When the latter number is achieved, the squares are perpendicular. Symmetric squares of even order cannot be made idempotent so the same definition is not valid. In Gross, Mullin and Wallis(1973a,b), the maximum number ν(r) of idempotent symmetric latin squares which can occur in a pairwise perpendicular set has been investigated. The procedure used by these authors makes use of the connection with Room squares mentioned above and in Section 6.4. See also Section 4.3.

Steiner quasigroups (defined in Section 2.3) also have multiplication tables which are idempotent symmetric latin squares. Consequently, orthogonal Steiner triple systems and their associated perpendicular Steiner quasigroups provide examples of perpendicular idempotent latin squares. Perpendicular commutative quasigroups have been investigated from this point of view in O’Shaughnessy(1968), N.S.Mendelsohn(1970), Lindner and N.S.Mendelsohn(1973), Mullin and Németh (1969), Radó(1974) and Steedley(1974). (See also Section 5.4.)

2.3 Group structure

We recognize here the Cayley table of an abelian group, i.e., (ℛ, ⊕) is an abelian group with neutral element 22. Remark that we can define ⊕ on the whole of Ω, but (Ω, ⊕) is not a group.

In words, this closure relation means that the only “trivial additions” on ℛ are (integer column) multiples of the matrix Δ.