Chapter 9

Latin squares with particular properties

In Section 2.1, we discussed quasigroups of some special types and their associated latin squares. Also, in Section 2.6, we introduced complete latin squares. Here, we discuss latin squares with various other special properties most of which had not been thought of when [DK1] was published.

9.1 Bachelor squares

The name bachelor square for a latin square which has no orthogonal mate was introduced by Van Rees(1990) who drew attention to Mann’s theorem of 1944 on this subject (which applies to squares of orders 4m + 1 and 4m + 2 [see Theorem 5.1.6]) and who proved for the case of latin squares of order 4m + 3 that (i) such a square can be in a set of at most 2m + 2 MOLS if it contains a latin subsquare of order 2m + 1; and (ii) that there exist latin squares of such orders which cannot be in a set of three MOLS. Statement (i) had earlier been proved by Drake(1977). See Theorem 5.2 of Chapter 2 in [DK2].

Clearly, a latin square which has no transversals is a bachelor square so, in particular, cyclic squares of even order and latin squares of q-step type are bachelor squares. (See Section 4.5.)

It follows as a corollary to Mann’s theorem that if a latin square L is of order 4m + 2 and contains a latin subsquare of order 2m + 1 or if it is of order 4m + 1 and contains a latin subsquare of order 2m then L is a bachelor square. However, this leaves completely open the question for which orders n ≡ 3 mod 4 (other than 3 itself) bachelor squares exist.

The general question “For which orders do bachelor squares exist?” was solved almost simultaneously by Wanless and Webb(2006) and by A.B.Evans(2006) using a similar method: namely, to modify a certain latin square by exchanging the elements in particular cells. However, the proof given by the first two authors has the virtue of elegance and of being applicable to latin squares of all orders, not just those of form 4m + 3. These authors showed that, for every order n > 3, there exists a latin square which contains a cell that is not included in any transversal. We gave their proof in Section 3.5. Since a latin square which has an orthogonal mate has a decomposition into disjoint transversals of which precisely one must pass through every cell, it follows at once that bachelor squares exist of every order except three.

9.2 Homogeneous latin squares

Definition

A latin square is said to be h-homogeneous if each of its cells lies in exactly h intercalates.

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

To return to h-homogeneous latin squares, it is easy to see that 1-homogeneous latin squares exist only of even orders and that (n − 2)-homogeneous latin squares of order n do not exist since any such square must in fact be (n − 1)-homogeneous. Also, (n − 1)-homogeneous latin squares exist if and only if n is a power of 2. See Heinrich and Wallis(1981). It was shown in Hobbs, Kotzig and Zacs(1982) that (n − 3)-homogeneous latin squares exist if and only if n ∈ {3, 4, 6, 8, 12, 16}. Killgrove(2001) called a 1-homogeneous latin square two-tiled and he proved:

Killgrove’s lemma

A group-based latin square is two-tiled if and only if the group has a unique element of order two.

Proof

Suppose without loss of generality that the latin square is in reduced form and is bordered by its own first row and column so as to form the Cayley table of a group.

If the square is 2-tiled, the identity element e in the cell (e, e) belongs to a unique intercalate whose remaining cells are (h, h), (e, h) and (h, e) for some element h. But then h ² = e, since the cell (h, h) must contain e. Thus, the group has an element of order two. If there were a second element k of order two, then the cells (e, e), (k, k), (e, k) and (k, e) would form an intercalate overlapping the first, which is a contradiction. Therefore, the element h of order two must be unique.

Conversely, suppose that there is a unique element h of order two. Any inner automorphism fixes h since g ⁻¹ hg also has order two, so h is in the centre of the group. Consider any cell (i, j). This cell, and also the cell (ih, hj), contains the element ij. Similarly, the cells (ih, j) and (i, hj) both contain the element ihj so the three cells (ih, hj), (ih, j) and (i, hj) form an intercalate with the cell (i, j). Suppose, if possible, that the cells (r, s), (r, j) and (i, s) also form an intercalate with the cell (i, j). Then rs = ij and is = rj. Thus, r ⁻¹ i = sj ⁻¹ and r ⁻¹ i = js ⁻¹ whence sj ⁻¹ = js ⁻¹ or (sj ⁻¹)² = e. That is, sj ⁻¹ = h. Therefore, s = hj and r = ih. This proves that the cell (i, j) lies in only one intercalate, so the square is 2-tiled. □

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.

9.3 Diagonally cyclic latin squares and Parker squares

A latin square of order n is said to be diagonally cyclic (or sometimes, and more accurately, left diagonally cyclic) if each of its left-to-right broken diagonals contains each of its n symbols and each is a cyclic permutation of the main left-to-right diagonal. If the same statement is true for the right-to-left diagonals also, the square is called totally diagonal or to be a Knut Vik design, see page 219. Two examples of the latter type of square are given in Figure 6.3.1.

The term “diagonally cyclic” is due to Franklin(1984a,b) who was probably the first to discuss construction of such squares explicitly. He also used what he called “bordered cyclic latin squares” (obtained by a prolongation of a diagonally cyclic latin square) to construct orthogonal latin squares and, in particular, pairs of MOLS of order 10. However, Franklin was certainly not the first to conceive and make use of the latter idea.

In the papers already referred to, Franklin frequently abbreviated “diagonally cyclic” to “cyclic”. However, not all left diagonally cyclic latin squares are cyclic in the sense used elsewhere in this book: that is, isotopic to a multiplication group of the cyclic group of the same order. A smallest counter-example, kindly supplied by Ian Wanless, is given in Figure 9.3.1. Wanless remarks that this is the multiplication table of a Steiner quasigroup of order 7 and that it cannot be isotopic to (Z ₇, +) because it has too many subsquares, also that it is smallest because (see Theorem 9.3.1) all orthomorphisms of (Z _n , +) for n ≤ 5 are linear ¹ and so define cyclic groups.

Fig. 9.3.1

A left diagonally cyclic latin square A = ‖a_ij ‖ is completely determined by its first row (or column) and by the order of the symbols in the main left-to-right diagonal. To see this, suppose that the latter order is a_o , a ₁, …, a_{n −1}. We regard the square as a collection of ordered triples, say (i, j, a_ij ), as we did on page 14. Then, if (i, j, a_k ) is a triple, so is (i + 1, j + 1, a_{k +1}) where arithmetic is modulo n.

In Bedford(1995), that author showed that:

Theorem 9.3.1

A diagonally cyclic latin square of order n exists if and only if the group (Z _n , +) has an orthomorphism.

Proof

Suppose that A = ‖a_ij ‖ is diagonally cyclic and based on the integers 0, 1, …, n − 1. Define a bijection φ of Z _n by the statement that φ ( j ) = a 0 j for j = 0, 1, …, n − 1. Since A is diagonally cyclic, a_{i ,t+i} = a _0t + i, where arithmetic is modulo n, so a_{u −t,u} = a _0t + (u − t) = φ(t) + (u − t). But a_{u −t,u} ≠ a _0u since A is a latin square. That is, φ(t) + (u − t) ≠ φ(u) or φ(t) − t ≠ φ(u) − u for all t, u ∈ Z _n . Thus, the mapping φ is an orthomorphism of (Z _n , +).

Conversely, let φ be an orthomorphism of (Z _n , +). We construct an n × n matrix A = ‖a_ij ‖ in which a _0j = φ(j) for j = 0, 1, …, n − 1 and put a_{i ,t+i} = a _0t + i = φ(t) + i mod n so that each left-to-right diagonal is cyclic. Then, a_ij = φ(j − i)+i so a_ij ≠ a_ik because φ is a permutation of Z _n and so φ(j − i) ≠ φ(k − i).

Also, a_hj ≠ a_ij otherwise φ(j − h) + h = φ(j − i) + i which would imply that φ(j − h) − (j − h) = φ(j − i) − (j − i) and contradict the fact that φ is an orthomorphism. Thus, A is a latin square as well as being diagonally cyclic. □

Corollary

A left diagonally cyclic latin square of order n exists if and only if n is odd.

Proof

Since cyclic groups of even order have no orthomorphisms, this follows immediately from the theorem. □

Later, Bedford [see Bedford(1998b)] used the fact that a diagonally cyclic latin square A can be constructed by putting a_ij = φ(j − i) + i to obtain his example of a non-cyclic latin square of order 15 with property P as defined in Section 9.4. The orthomorphism of (Z ₁₅, +) which he used was

φ = ( 0 ) ( 1 2 ) ( 3 9 13 ) ( 4 11 7 ) ( 5 8 10 ) ( 6 14 12 ) .

Since each broken diagonal of a left diagonally cyclic latin square of order n is a transversal, such a square can be n times prolonged and this fact has been exploited by very many authors including Parker(1959b) who used it (though not explicitly as he described his construction in the language of orthogonal arrays) to disprove Euler’s conjecture by constructing for the first time a pair of MOLS of order 10 and, more generally, a pair of MOLS of order (3q − 2)/2, where q is any prime power congruent to 3 modulo 4. Yamamoto(1961) and, later, Hedayat and Seiden(1971,1974) under the title of sum composition used the idea of multiple prolongation ² to construct t MOLS of order n + m from t +1 MOLS of order n and t MOLS of order m (n > 2m). The required procedure is described in detail on pages 436-442 of [DK1]. The method has been generalized and also re-presented in a more easily understood form by Guérin(1966b) and this author has christened it “Yamamoto’s method”. For some related constructions and for a proof that, as t → ∞, the number of non-equivalent pairs of MOLS of order t also tends to infinity, the reader is referred to chapter 6 of Guérin(1966b) and also to Barra and Guérin(1963a,b) and Guérin(1963a,b,1964,1966a).

In Wanless(2004b), that author has made the following definition: We adjoin b infinity symbols to the cyclic group Z _m to obtain the set Z _{m ,b} = Z _m ⋃ {∞₁, ∞₂, … ∞ _b } and we define z ⁺ for z ∈ Z _{m ,b} by z ⁺ = z + 1 mod m if z ∈ Z _m and z ⁺ = z otherwise. Then a bordered diagonally cyclic latin square (henceforward to be called a Parker square, see below) with rows, columns and symbols indexed by Z _{m ,b} is one for which the presence of any triple (i, j, a_ij ) implies that the triple (i ⁺, j ⁺, a ij + ) also occurs in the square. We say that this Parker square is of B_b -type if it is based on Z _{m ,b} in the above way for m ≥ 1 or if its symbols can be mapped bijectively to Z _{m ,b} in such a way that the resulting square has the above properties.

It was because of the important role which squares of B_b -type played in the disproof of Euler’s conjecture that Wanless christened them Parker squares. In fact, the pair of MOLS of order 10 obtained by Parker and illustrated in Figure 9.3.2 is of B ₃-type. Here, the integers 7, 8, 9 play the roles of ∞₁, ∞₂, ∞₃. This pair of squares could have been constructed directly by sum composition from a triple of MOLS of order 7 of which the first has constant left-to-right diagonals and the remaining two are diagonally cyclic (shown in Figure 9.3.3) and a pair of MOLS of order 3. ³

Fig. 9.3.2

Fig. 9.3.3

In his paper of 2004, Wanless has extended Theorem 9.3.1 to provide necessary and sufficient conditions for a Parker square of any given B_i -type to exist by introducing the idea of a partial orthomorphism of (Z_m , +). (In the case of a B ₁-type Parker square, this is the same as a near orthomorphism. See Section 7.6.)

In the same paper, he has given an example of a B ₁-type square and a B ₂-type square which are quasigroup isomorphic: that is, there exists an isotopism which transforms one square to the other and which re-labels the rows, columns and symbols in the same way. Thus, Parker squares of different types may lie in the same isomorphism class and, a fortiori, in the same isotopism or main class of latin squares. Also, the B ₂-type Parker square given by Wanless illustrates the fact that not all Parker squares can be contracted to diagonally cyclic latin squares.

We note that the diagonally cyclic latin squares in Figure 9.3.3 are orthogonal. A number of authors (including Franklin) have discussed the conditions for a diagonally cyclic latin square to have one or more orthogonal mates which are also diagonally cyclic. Since each such square is orthogonal to the latin square with the property that all the cells of each broken left-to-right diagonal contain the same fixed element, the maximum number of left diagonally cyclic squares of order n which are mutually orthogonal cannot exceed n − 2 by Theorem 5.1.2. Wanless(2004b) has shown more generally that, given arbitrary integers n and b, there cannot be more than n − 1 if b = 1 or min[N(b), (n − b/b] if b > 1 mutually orthogonal B_b -type latin squares of order n. He has further shown that both these bounds can be attained.

The Wanless paper of 2004 contains many further results concerning Parker squares and also it lists a surprisingly large number of papers whose authors had made use of such squares for their constructions up to the time when that paper was published. For example, Owens and Preece(1996) constructed their non-cyclic latin squares of prime order p ≥ 11 with property P (see Section 9.4) by modifying a Parker square of B ₁-type. In particular, Wanless himself, in collaboration with Bryant and Maenhaut [see Bryant, Maenhaut and Wanless(2006)] has used such squares to construct infinite families of atomic latin squares (again see Section 9.4 for the definition) which are of B ₁-type.

A number of the papers cited by Wanless had also been mentioned earlier in Bedford(1993) and in the latter paper the close connection between left diagonally cyclic latin squares and neofields had been shown: namely, the addition table for a cyclic neofield of even order can always be obtained by the prolongation of an appropriate left diagonally cyclic latin square taking its main diagonal as the transversal.

Parker squares continue to be valuable as a means of obtaining new results.

Finally, let us mention a paper [Cavenagh and Wanless(2010)] in which the authors show that the number of transversals in Cayley tables of cyclic groups of odd order increases exponentially with the order and they remark that, by virtue of Theorem 9.3.1, the number of diagonally cyclic latin squares likewise increases exponentially with the order of the square.

9.4 Non-cyclic latin squares with cyclic properties

One of the rare occasions when the authors of the first edition of the present book were in serious disagreement was when the question arose in the late 1980s (in connection with their research) as to whether a given latin square of prime order p with the property that each of its rows was a cyclic permutation of the first row would necessarily be isotopic to the cyclic group of order p. Dénes was strongly of the opinion that it would while Keedwell was equally strongly of the opinion that it would not. The issue was resolved when the two authors constructed counter-examples in Dénes and Keedwell(1988) for latin squares not only of prime orders but for all orders n ≥ 7. Shortly afterwards, a simpler construction of counter-examples was given in Keedwell(1991).

Next, in the development of the idea of constructing non-cyclic latin squares with cyclic properties, Owens and Preece(1996) constructed, for all prime orders p ≥ 11, a latin square with the stronger property P that the permutation from row i to row j is cyclic for all i and j, j ≠ i. The earlier construction only gave a square which had property P for the permutation from row 0 to row j, 1 ≤ j ≤ n − 1 (in the case of a latin square of order n). Let us remark here that every cyclic latin square of prime order has property P and also has the similar property for columns. On the other hand, no latin square of composite order based on a group has property P. (See below.) Despite this, Bedford(1998b), in an unpublished paper (see Section 9.3), gave an example of a latin square of order 15 which has property P.

The next step came when Wanless(1999) observed that every latin square L of order n defines a 1-factorization of the complete bipartite graph K_{n ,n} (and in several ways, see Section 8.3). He also observed that a latin square L having property P would not contain any proper latin subsquare M because, if rows i and j of L both contained rows of such a subsquare M, then the permutation from row i to row j of L would include one or more sub-cycles involving only the elements of M. That is, any latin square with property P is an N _∞-square and conversely.

Let L be as above and let one partite set {c ₁, c ₂, …, c_n } of vertices of K_{n ,n} denote the columns of L and let the second partite set {s ₁, s ₂, …, s_n } denote the symbols. Then each row of L defines a 1-factor as follows: if the symbol s_k occurs in column c_j of row r_h , join c_j to s_k . Since no two entries in r_h are the same, these edges form a 1-factor which corresponds to the permutation

σ h = ( c 1 c 2 … c n s 1 h s 2 h … s nh )

defining row r_h as a permutation from natural order. Also, the 1-factors associated with different rows are disjoint since each column contains each symbol only once. The permutation which maps row r_h to row r_i is then σ h − 1 σ i . Each of σ_h , σ_i defines a 1-factor of K_{n ,n} and σ h − 1 σ i defines a means of traversing the edges of the graph: s_lh → c_l → s_li → etc. If property P holds, then σ h − 1 σ i is a full length cycle and all edges of the graph are traversed by the union of the 1-factors corresponding to σ_h , σ_i . This led Wanless to say that a latin square (or rectangle) with property P is pan-Hamiltonian because of the connection with Hamiltonian decompositions of the complete bipartite graph just described.

For example, in Figure 9.4.1 the 1-factors which define the first three rows of L ₄ are F ₁, F ₂, F ₃. The unions F ₁ ⋃ F ₂ and F ₁ ⋃ F ₃ form Hamiltonian circuits in K_{n ,n} while F ₂ ⋃ F ₃ does not. As illustration, the union F ₁ ⋃ F ₃ gives s ₃ → c ₁ → s ₁ → c ₂ → s ₄ → c ₃ → s ₂ → c ₄ → s ₃. The latin rectangles which are given by the first two rows or the first and third rows are pan-Hamiltonian and so contain no sub-rectangles.

Fig. 9.4.1

Later, Wanless refined the name to row-panHamiltonian since the roles of rows, columns and symbols can be permuted to give parastrophes of L which may be column-panHamiltonian or symbol-panHamiltonian.

In his paper of 1999, Wanless also proved the following three lemmas:

Lemma A

If a k × n latin rectangle R is pan-Hamiltonian, then either n is odd or k = 2.

Proof

Suppose that n is even and that r_h and r_i are two rows of R. Then σ h − 1 σ i is a cycle of length n on an even number of symbols so it is an odd permutation. Consequently, σ_h and σ_i must be of opposite parity. As this must be true for any two rows of R, there cannot be more than two rows. □

This lemma and with the same proof had earlier been given as a closing remark in the paper of Owens and Preece(1996).

Lemma B

If a latin square L is pan-Hamiltonian, then so is any square isotopic to L and so is the row inverse L ^{(2 3)} of L.

Proof

Isotopies involve re-arranging rows, symbols and/or columns. The first of these does not affect the row cycles σ ₁, σ ₂, …, σ_n but only their order so, if σ h − 1 σ i was a single cycle, that property is not affected. Also, that property is not affected if the symbols are permuted. Thirdly, if the entries in two rows of L are permuted in the same way by a re-arrangement of columns, this does not affect the permutation which transforms one to the other.

The latin square L = (a_hk ) can be represented as a set of n ² triples (h, k, a_hk ) so the permutation σ_h which defines the hth row of L is ( … k … … a hk … ) . The triples of the row inverse L ^{(2 3)} take the form (h, a_hk , k) so the permutation which defines the hth row is σ h − 1 = ( … a hk … … k … ) . If σ h − 1 σ i is a full length cycle for all choices of h and i, h ≠ i, then so is ( σ h − 1 ) − 1 σ i − 1 = σ h σ i − 1 because σ h σ i − 1 = σ i ( σ i − 1 σ h ) σ i − 1 = σ i ( σ h − 1 σ i ) − 1 σ i − 1 and both conjugate and inverse permutations have the same cycle structure. 4 □

Lemma C

If a latin square L is pan-Hamiltonian, let ν(L) denote the number of its parastrophes (including itself) which are also pan-Hamiltonian. If L is isotopic to its transpose L ^{(1 2)} then ν(L) =4 or 6. If L is isotopic to its row inverse L ^{(2 3)} then ν(L) = 2 or 6.

Proof

Let A ~ B denote that both A and B are pan-Hamiltonian or that neither is. Then, by Lemma B, L ~ L ^{(2 3)}, L ^{(1 2)} ~ L ^{(1 2)(2 3)} = L ^{(1 3 2)} and L ^{(1 3)} ~ L ^{(1 3)(2 3)} = L ^{(1 2 3)}.

If L is isotopic to L ^{(1 2)} then, from Lemma B again, it follows that L ~ L ^{(1 2)} and so L ~ L ^{(2 3)} ~ L ^{(1 2)} ~ L ^{(1 3 2)}. If also one of L ^{(1 3)} or L ^{(1 2 3)} is pan-Hamiltonian, then both are. Thus, ν(L) ∈ {4, 6}.

If L is isotopic to L ^{(2 3)}, then their transposes L ^{(1 2)} and L ^{(2 3)(1 2)} = L ^{(1 2 3)} also are isotopic and so are L ^{(1 3)} and L ^{(2 3)(1 3)} = L ^{(1 3 2)} so L ^{(1 2)} ~ L ^{(1 2 3)} and L ^{(1 3)} ~ L ^{(1 3 2)}. But L ~ L ^{(2 3)}, L ^{(1 2)} ~ L ^{(1 3 2)}, L ^{(1 3)} ~ L ^{(1 2 3)} so L ^{(1 2 3)} ~ L ^{(1 2)} ~ L ^{(1 3 2)} ~ L ^{(1 3)}. If any one of these is pan-Hamiltonian, they all are and so ν(L) ∈ {2, 6}. □

Wanless called a latin square atomic if all six of its parastrophes are pan-Hamiltonian. A latin square is atomic if and only if none of its parastrophes has a proper latin sub-rectangle.

To test whether a given latin square L is atomic, it suffices to check that L, its transpose L ^{(1 2)} and the transpose of its row inverse L ^{(2 3)(1 2)} = L ^{(1 2 3)} are atomic. This follows from the first statement in the proof of Lemma C.

By Theorem 4.2.2, if a latin square L is the Cayley table of a group or of a loop with the inverse property, then all five of its parastrophes are isotopic to it. It follows from Lemma B above that in that case, if L is pan-Hamiltonian then it is in fact atomic. In the Cayley table of a group of order n (which we may assume to be in reduced form), the rows are represented by regular permutations with cycle lengths which divide n and so when and only when ⁵ n is prime and the group is cyclic, it is pan-Hamiltonian. Thus, the only group-based square which is atomic is that of the cyclic group C_p .

Wanless(1999) used a connection between perfect 1-factorizations of the complete graph K_{n +1} and perfect 1-factorizations of K_{n ,n} which we next describe to obtain two non-isomorphic perfect 1-factorizations of K_{p ,p} and hence the following result:

“Let p ≥ 11 be a prime. If 2 is a primitive root modulo p, then there exists an atomic square of order p outside the main class of latin squares which contains C_p .”

In a subsequent paper [see Bryant, Maenhaut and Wanless(2006)], these authors used similar ideas to construct five different main classes M _!, M ₂, M ₃, M ₄, M ₅ of latin squares of prime order which sometimes or always contain atomic latin squares. The squares in M ₁ include C_p and so are atomic always. The squares in M ₃ include those constructed by Owens and Preece(1996) who showed that they too are atomic. The squares in M ₂ include that constructed by Wanless and referred to in the preceding paragraph. These squares are atomic when p is such that it has 2 as primitive root and so also are the squares in M ₄ and M ₅.

In Maenhaut and Wanless(2004), a complete enumeration of atomic latin squares of order 11 (which is the smallest order for which there are examples distinct from isotopes of C_p ) is given. They belong to seven main classes.

Suppose that the complete graph K_{n +1} has a perfect 1-factorization F ₁, F ₂, …, F_n . We label the vertices of K_{n +1} by υ ₁, υ ₂, …, υ_n , υ _∞. We denote the 1-factor which contains the edge (υ_h , υ _∞) by F_h . Let the remaining edges of F_h be …, (υ_x , υ_y ), …, etc. Let K_{n ,n} have partite sets {c ₁, c ₂, …, c_n } and {s ₁, s ₂, …, s_n }. We use F_h to construct a 1-factor F′ _h of K_{n ,n} whose edges are …, (c_h , s_h ), (c_x , s_y ), (c_y , s_x ), …, etc. and thence construct a latin square L whose hth row is given by the involutary permutation σ_h = (h)(x y)…. If the union of F_h and F_i is a Hamiltonian circuit in K_{n +1}, then the union of F′ _h and F′ _i is a Hamiltonian circuit of K_{n ,n} , since the sequence of vertices → υ_a → υ_b → υ_d → υ_e →υ_f →, where (υ_a , υ_b ), (υ_d , υ_e ), … ∈ F_h and (υ_b , υ_d ), (υ_e , υ_f ), … ∈ F_i , is replaced by the sequences → c_a → s_b → c_d → s_e → c_f → and → s_a → c_b → s_d → c_e → s_f → in K_{n ,n} and the sequence → υ_h → υ _∞ → υ_i → by the sequences → c_h → s_h → and → s_i → c_i →. This construction had earlier been noted and used for various purposes by several authors, in particular see Keedwell(1978), Laufer(1980), Wanless and Ihrig(2005) and page 116 of [DK2]. Note that n + 1 must be even for such a 1-factorization to exist.

As illustration, Figure 9.4.2 gives a perfect 1-factorization of K ₆ and the corresponding perfect 1-factorization of K _5,5 and Figure 9.4.3 shows the pan-Hamiltonian latin square L ₅ thereby defined. The method of construction shows that this square will always be idempotent and involutary. That is, each row permutation σ_h is equal to its own inverse and so L = L ^{(2 3)}. By Lemma C, it follows that ν(L) = 2 or 6 for such a square. If rows and symbols are interchanged to obtain the parastroph L 5 * = L ( 1 3 ) , the latter will be symmetric, idempotent and symbol-panHamiltonian.

Fig. 9.4.2

Fig. 9.4.3

Using the above ideas, Wanless(1999) was able to construct an atomic latin square not in the main class which contains C_p for each prime p ≥ 11 for which 2 is a primitive root (as we stated earlier). Wanless also claimed that, by applying his construction procedure to a particular perfect 1-factorization of K ₂₈, he had obtained an atomic latin square of order 27.

In Wanless(2005), the same author used cyclotomic orthomorphisms in finite fields to construct atomic latin squares of other prime power orders but, so far as the present author is aware, no atomic latin square of composite but non-prime-power order has yet been found.

We end this section with a brief discussion of N _∞-squares. Such squares need not be atomic. Andersen and E.Mendelsohn(1982) showed that N _∞-squares exist of all orders n ≠ 2 ^a 3 ^b . We outlined their proof in Chapter 4, Section 2 of [DK2]. A further construction of N _∞-squares was devised by Elliott and Gibbons(1992) who obtained subsquare-free latin squares of orders 16 and 18. Later, Maenhaut, Wanless and Webb(2007) showed that if n is odd and divisible by 3, then an N _∞-square of order n exists. (See the bibliography of that paper for some papers on this topic not mentioned here.) Combining this with the earlier paper of Andersen and E.Mendelsohn, we are able to conclude that N _∞-squares exist of all odd orders. However, so far as the present author is aware, the situation regarding even orders is still not completely determined.

---

¹ A linear orthomorphism is a map that sends x to ax + b for some constants a, b. All diagonally cyclic squares based on linear orthomorphisms are isotopic to cyclic groups.

² Yamamoto used the term extension instead of prolongation and he called the inverse operation contraction as already mentioned in Section 1.5. The term prolongation is due to Belousov, as stated in the same section. These two authors worked independently neither being aware of the other’s work.

³ But, in order to achieve orthogonality, the order of the last three rows and columns is important so the procedure described by Yamamoto(1961) must be followed.

⁴ The proof of the last result given in Wanless(1999) is incorrect.

⁵ If n is not prime and p is a prime which divides n, then, by Cauchy’s theorem, at least one row is represented by a permutation whose cycles have length p < n.