Latin squares of order 5 and Latin patterns up to order 7
3.1. Latin patterns as building blocks for Latin squares
The set of LS’s of order 4 was stepwise reduced in Chapter 2 to a small number of independent LS’s by establishing symmetry relations between them. The reduction process for the 1344 LS’s of order 5 will be performed in a different manner. The notion of a Latin pattern: the arrangement of all same- symbol sites of a LS-structure , was coined in Chapter 2. We aim here at the arrangement as such, indifferent to orientation, mirror imaging, or position in the cell. A Latin square of order n is a superposition of n Latin patterns (par. 1.1) represented by a Latin patterns diagram.
We define 4 different Latin patterns in 5×5 Latin squares terming them: string (ST), triple-couple (TC), couple-couple-single (CCS), and lattice (L) (Figures 3.1.1).The first three run diagonally; the (singles) lattice L is a square lattice at an oblique angle with the orientation of the sites lattice String Triple/Couple Couple/Couple/Single Lattice
Figure 3.1.1. Latin patterns in order 5 LS’s
The Latin patterns above correspond with four solutions of the so-called n-rooks problem on a n x n chessboard (placing the rooks in such a manner on the board that they are not attacking each other), for n=5. In fact this problem has 23 solutions (ref.10); the other 19 are merely products of translation of ST, TC,CCS and, L across the edges of the board 9 (ref.8) The lattice (L) has symbol-sites at next nearest neighbour distances (V5, the knight's move in chess), and with periods meeting the lengths and directions of the corners of an order 5 Latin square. Again, extension beyond the Latin square boundaries (par. 2.3) is helpful to confirm its square (sub)lattice character (Fig. 3.1.1). Each occupied site is the rotation point of a fourfold axis of L. There is also a lattice type Latin pattern for n=7 (par.3.5).
A Latin pattern composition formula (briefly composition formula) can now be written for each Latin square of order 5 as:
kST . lTC. mCCS . nL (3.1.1)
with k, l, m, n natural numbers, and k+l+m+n = 5. The mosaic structure of Fig. 3.1.2 offers an example: composition formula TC.4CCS, with k=n=0, l=1 and m=4 .
The pattern composition of a Latin square is fully determined within any bounded LS but recognition of the constituting Latin patterns is facilitated in a corresponding Latin structure or wallpaper structure (par. 1.2, Fig 3.1.2, subscript).
Figure 3.1.2. Latin-periodic structure of an order 5 Latin square, composition formula: TC. 4CCS, structure type 8α (Table 3.2.1).The blue boards form a TC (triple-couple) Latin pattern running topleft – bottom right (tl – br). The pattern of the red boards is CCS (couple-couple-single), running tr – bl . The three remaining patterns, in yellow, green and purple, are also CCS but these are running tl – br, parallel with the direction of TC.
The composition TC.4CCS allows for another structure-type, 8β (Table and Fig. 3.2.1), again with a CCS trio running parallel with TC. Both types have a colour mirror line with one-pair switch, (par. 1.1) coinciding with the axis of of TC in 8α and perpendicular to the triple of TC in 8β.
3.2. Grouping order 5 Latin squares in 18 families
Resolution of hundreds of 5×5 Latin squares in Latin patterns resulted in establishing 14 different Latin pattern compositions. We collected them in corresponding same-composition families, briefly families. (List 3. 2. 2, second column). Four families are uni-patterned or “monolithic”: 5ST, 5TC, 5CCS, 5L. The other 10 are binary or tertiary composites. String (ST) and Lattice (L) are (mutually) incompatible.
We established in this process that Latin pattern composition and LS-structure type are strongly correlated : one single structure type is adopted by the members of 10 families. The remaining 4 families are double-structured (ds): allow two structure types, α and β. Relating LS – composition and LS structure type is entirely unambiguous for LS’s up to order 5 with the α and β addition – if necessary – to the LS formula and family.
All this results in a total of 18 families, and in a Geometric Representation (par. 2.2 and 2.4) for the 1344 order 5 LS’s comprising 18 independent Latin square structures (Table 3.2.1, Fig.3.2.1 and List 3.2.2).
Figure 3.2.1. Geometric representation for the 1344 order 5 Latin squares comprising 18 independent Latin structures (structure types) . Latin patterns are in one of the colours, red, yellow, green, blue, purple and equal nearest neighbours have been connected. Pairs of family members with equal Latin pattern composition but with different structure types, α and β, are connected in blue. Ordinary mirror lines are in black.
Table 3.2.1. All 18 order 5 structure types, in standard numeric format, numbered, and with Latin-pattern composition added. Different structure types, α and β, with same composition, (indicated ds), are connected. Sites indicated in italics are the intersections of sequentially equal rows and columns (see reduced-form section of par.3.5).
|type||class||Latin pattern formula||mult||contr. TR||contr. PR||red. form||conv. planar group||colour symmetry elements||Bravais lattice conv col|
|1||(1)||5ST||2||2||1||1||pm||2D col. tr. symm.||rect rect|
|conv ml tl-br|
|2||(1)||5TC||20||4||3||p1||1D col. tr. symm.||obl rect|
|3||(2)||ST.4TC||100||4||13||10||p1||col. ic (yg) (bp)||obl rect|
|4||(2)||4TC.CCS||200||6||25||16||p1||no symmetry||obl. obl|
|5α||(2)||2ST.TC.2CCS||50||2||9||4||p1||col.ml tl-br (yp)||obl rect|
|col.ml tr-bl (gb)|
|5β||(2)||2ST.TC.2CCS||50||2||9||4||p1||col. ml tl-br (gb)||obl rect|
|col. ml tr-bl (ry)|
|6α||(2)||ST.TC.3CCS||100||4||15||p1||col. ml tl-br (yb||obl rect|
|6β||(2)||ST.TC.3CCS||100||4||15||col. ml tr-bl (yb||obl rect|
|7||(1)||ST.4CCS||50||2||9||5||pm||conv ml tr-bl||rect rect|
|col.ml tl-br (yg) (bp)|
|8α||(2)||TC.4CCS||100||4||15||4||p1||col.ml tr-bl (yg) )||obl rect|
|8β||(2)||TC.4CCS||100||4||15||4||p1||col.ml tl-br (gp) )||obl rect|
|9||(1)||4TC.L||50||2||7||p1||col. 4f. axis (rygp)||obl sq|
|10||(1)||5CCS||20||4||3||p1||1D col. tr. symm. )||obl obl|
|11||(2)||3TC.CCS.L||200||6||25||8||p 1||no symmetry||obl obl|
|12α||(2)||4CCS.L||50||2||7||p1||col.4f. axis (rbgp)||obl sq|
|12β||(2)||4CCS.L||50||2||7||p1||col. 4f. axis (prgb)||obl sq|
|13||(2)||2TC.CCS.2L||100||4||13||p1||col. ic (rg) (bp)||obl obl|
|14||(1)||5L||2||2||1||p1||2D col. transl. symm. )||obl obl|
List 3.2.2. All 14 families of 5×5 Latin squares, comprising 18 structure types in two isotopy classes (par. 1.2) with compositions (columns 1,2,3).
Multiplicities of structures (par.3.3 ) are in the 4th column. They total 1344.
PR- and TR-contributions (par. 3.7 and AppendixIII)) 5th and 6th column, also totalized underneath. Numbers of reduced-form LS’s (par. 3.5 ), totalling 56, in column 7.
Space groups: column 8. Symmetry elements conventional (conv bold), colour (col) and translation symmetry (tr) specified in column 9.
Bravais lattice types oblique (obl), rectangular (rect), square (sq) based on conventional or colour symmetry: column 10. Further abbreviations: fourfold (4f) axes, inversion centres(ic), mirror lines(ml), top left -bottom right: tl-br . Lettering (yg) (rygp) etc. with r red, y yellow, g green, b blue, p purple are shorthands for permutations under colour symmetry switches.
3.3. General result for order 5: symmetry, Geometric Representation, multiplicities, classification.
General. Expression (3.1.1), with k+l+m+n = 5, corresponds combinatory with 56 (k, l, m, n) Latin pattern compositions. We saw that about one fourth of them can indeed be arranged structurally in order 5 Latin squares; 10 with a unique fit into a Latin square structure and 4 allowing arrangement in a LS in two ways: α and β.
Fig. 3.2.1 shows the resulting 18 independent Latin squares with the constituting Latin patterns coloured. Note that Fig. 3.2.1 and List 3.2.2 are the order 5 equivalents of Fig. 2.4.1 and List 2.4.1 respectively for order 4.
Any 5×5 Latin square (in corresponding nomenclature) is identical with one of these 18 Latin squares or: is contained in their boundary-free representations: on the torus, or in an ongoing Latin structure (par. 1.2).
Figure 3.2.1 with corresponding multiplicities, is our final reduction result for LS’s of order 5 if we count all point symmetry and/ or translation-related members as one .
Conventional and colour symmetry. A striking difference between order 4 and 5 Latin squares is the lack of conventional symmetry of the latter, due to its odd dimensions (5×5) which forbid inversion centres, perpendicular mirror lines and glide lines.
One could envisage inversion centres lying in between rows or columns like in 4x4 Latin squares. But a set of of such centres is always accompanied by a second set lying halfway between, that is: on rows or columns, which violates the Latin square condition. Perpendicular mirror lines always induce inversion centres at their intersections which again is impossible. Glide lines cannot copy (repeat) a section of an odd Latin structure because the translation length would be half an odd number of intersite distances. The same holds for centering of the square.
The only conventional symmetries possible are diagonal reflection and internal translation symmetry which is indeed present in some structures: 1, 7 and 2 . The 2D-space group (planar group) for 1 and 7 is pm; for the other structures p1(oblique crystal system). This means that 95 % of the 1344 order 5 LS’s are without ordinary symmetry.
However, colour-symmetry provides additional symmetry relationships, reduction of multiplicities, higher Bravais lattice symmetries and a far lower percentage (30 %) of “symmetry-free” structure types. Note the colour fourfold axes of structures 9, 12α and β, and 14 in Fig. 3.2.1 specified in List 3.2.2 . Accepting colour symmetry raises the symmetry here from oblique to square. Planar colour ymmetry group notations are included in List 3.2,2.
Another example is a the colour-inversion centre in structure 3. This double switch inverts yellow(2) into green(3), blue(4) into purple(5) and vice versa, red (1) unchanged; abbreviated in List 3.2.2 as: (yg) (bp). The overall colour-symmetry is readily noted when (part of) of the Latin patterns are drawn . We have restricted drawing connecting lines in Fig. 3.2.1 to (diagonal) nearest neighbours.
Choice of LS’s for our Geometric Representation (Fig.3.2.1.) LS’s, selected from families with (colour)symmetry, were those with intersections of colour-mirror lines, colour-fourfold axes, and/or colour inversion centres located at their centres in bounded representation.The choice was entirely arbitrary in the symmetry-free structures 4 and 11 (List 3.2.2).
Multiplicity- symmetry dependencies within the (sub) families. Order 5 Latin squares are multiplied in a complete LS set by a factor 8 ( the number of elements of the dihedral group for a square), and by a factor 25; the number of 5×5 translation related positions on its site lattice, bringing the total member-multiplicity to 200 for symmetry-free structure types. Dihedral- and translation symmetry-elements wil bring this multiplicity factor (k) down in all other cases because multiplication operations coinciding with symmetry operations will simply copy the original. This would results in k=4×25 for structures with a colour mirror line or a colour symmetry centre (2, 3, 6α, 6β, 8α, 8β, 10 and 13) , in k=2×25 for structures with two (colour) mirror lines (5a, 5b, and 7) or a colour-fourfold axis (9, 12α, 12β), and in k=2 for structures which are multiplied only by orientation (“twinning”): 1 and 14). Structures 2 and 10 do repeat themselves (colour-symmetrically) by translation in horizontal (2) and vertical (10) direction (Fig. 3.2.1), reducing the “default” translation multiplicity by a factor of 5, so k=4×5.
LS’s 1 and 14 copy themselves at all sites of the sites lattice (after permutation to standard format): total multiplicity remains k=2.
This brings the multiplicities per structure type to the values given in List 3.2.2, and the total number of order 5 Latin squares in standard format up to the literature value of 1344.
3.4. Further classifications
Isotopy classification: similar to the order 4 LS’s: all LS’s sharing a structure type are allocated in the same isotopy class. LS’s sharing structure types 1, 2, 7, 9, 10, 14 constitute class (1) with 144 members; the remaining 1200 LS’s, sharing the other structure types, occupy class (2).
Intermediate representations for order 5 Latin squares. We concluded that the number of independent Latin squares necessary and sufficient for generating the full set of order 5 LS’s on the basis of symmetry-kinship, is 18, similar to the minimum representation, 5, for order 4 LS’s.
However, during our march from 24 – the full set of order 4 LS’s – to 5 , we passed two intermediate representations: one with 12 LS’s representing the full set if we count all point symmetry related squares as one (par. 2.2), and another with 7 LS’s, counting all translation-related members as one (par. 2.3). For brevity we will term them PR- and TR- representation for any order.
W. Barink (ref. 9) deduced and published the size of the PR-representation for order 5: 192, using an elegant graphic method, and his result has been confirmed by Joriki (ref.10). Joriki also determined the PR number for order 6 LS’s. The sequence 12 192 145164 has been adopted by the Online Encyclopedia of Integer Sequences (OEIS) under A264603. We have retrieved PR and TR numbers for any order 5 structure type, ( List 3.2.2, Appendix III).
Reduced form: 56 LS’s of order 5 exist in reduced form (first row and column equal); a result going back to Euler, 1782 (ref.1). The number is easily obtained by dividing 1344 by 4!
When a LS is put on a torus (or: extended to a Latin-periodic structure), looking for reduced form is generalized to noticing sequential equality of a “row” and a “column”, and noting their site of intersection. Marked in the LS’s of Table 3.2.1 in italics. We find that reduced-form is present in 9 structure types: 1, 3, 5.1 , 5.2, 6, 7, 8.1, 8.2 and 11.
Reduced-form LS’s are simply the 5×5 cuttings out of these Latin structures with the mentioned intersections top-left, normally followed by conversion to standard format. Such cuttings can be done in four directions and each reduced-form LS can be reflected across the tl-br diagonal to produce another or reproduce itself . Clearly, this will lead (again) to different reduced-form multiplicities, depending on (colour)symmetry and particular structure of the LS’s. The resulting arithmetic (structure types between parentheses) is:
1(1) +10 (3) + 16 (4) + 4 (5α) + 4 (5β) +5 (7) + 4 (8α) +4 (8β) +8 (11) =56 (3.4.1)
in agreement with Euler’s result.
Indexing and abbreviating specific members. It may be necessary to distinguish and number specific LS’s (members) within a structure type, particularly when dealing with orthogonality (par. 4.2). We numbered order 4 LS’s (1 to 24) following the sequential enumeration scheme (Appendix II ) It is more rational for higher order to let nomenclature follow the movements (translations, rotations etc. when the members of each LS-structure type are created (par.3.3, multiplicities) with a preferred member as starting point ( List 3.2.2 and par. 3.3 for order 5). An index (path) hk.l would mean: applying translations h and k along the x and y axis of the sites lattice (par. 1.1) of the selected member and applying the l-numbered member of the of the dihedral symmetry group for a square (par. 1.2), or vice versa (l.hk). When numbering members, and in par 4.2 on orthogonality, we do translations first. Both sequences are employed in Appendix III. Indexing with paths hk.l and l.hk will only be unique in families without symmetry (4 and 11); in symmetric structures 7 and 9, with multiplicity 50 (above), there will clearly be 4 paths leading from the preferred – to the transformed member. A convention could be for adopted for numbering, such as h >k etc.
Distinguishing LS members can be facilitated by abbreviating them as checksums instead of using the full LS descriptions themselves. Checksums are unique for any section of programming code and can be shortened in our case to handy numbers with five or less digits. We will employ HP 48 checksums and, if handy, combine indices and checksums in multiplication tables (Appendix III)
3.5 Order 4 Latin squares revisited. LS’s of order 2 and 3
In order to complement the the symmetry-identity and – distinction procedure of Chapter 2 (par. 2.2 and 2.3) with the pattern-partition method of this chapter), we will re-derive the reduction results for 4×4 Latin squares (Chapter 2) with the pattern composition approach.
We detect two Latin patterns in the 4×4 case: ST (string) and CC(couple-couple). An alternative for CC is SQ, a square at an oblique orientation, Fig. 3.5.1.
String (ST) Couple/Couple (CC) or Square (SQ)
Figure 3.5.1. Order 4 Latin patterns
There are three composition families with formula: 4ST, 2ST.2CC and 4CC, listed underneath. The allocation of all order 4 squares – numbered following Table 2.1.1 – in these families is:
4ST: LS01, 05, 18, 24
2ST.2CC: LS02, 03, 07, 09, 16, 20, 22, 23
4CC: LS04, 06, 08, 10, 11, 12, 13, 14, 15, 17, 19, 21.
Pairs (05, 18) and (01, 24) within 4ST differ in structure: the string patterns (ST) are parallel in LS05 and 18, and pairwise perpendicular in LS01 and 24. So ST is a ds-family (par. 3.2) with two structure types. Proceeding in the same way we obtain a total of 5 families listed beneath (3rd column) similar to List 3.2.2:
1 2 3 4 5 6
1 (1) 4ST α 2 LS01, 24
4 (2) 4ST β 2 LS05, 18
2 (2) 2ST.2CC 8 LS07, 02, 03, 9 16, 20, 22, 23
3 (1) 4CCα 4 LS11, 04, 14, 21
5 (2) 4CCβ 8 LS06, 08, 10, 17, 12, 13, 15, 19
The structure type order 1…5 of Chapter 2 (first column) has been maintained here. Isotopy classes ( ) , family notation, multiplicities (totalling 24) preferred LS’s for representation in bold and the other family members are in columns 2,3,4,5,6 respectively.
The present results agree with those of Chapter 2 particularly in identifying the LS’s required for representing the full order 4 set (the Geometric Representation). However, point – and translation symmetry relationships between the members which were given in List 2.4.1, are not obtained with the Latin-pattern resolution method. A symmetry analysis per family would be required to complete the agreement.
For general completeness we add that the only Latin pattern in order 2 and 3 Latin squares is a string ST, in compositions 2ST and 3ST respectively. ST in order 3 can be replaced by L (an oblique lattice) for better correspondence with the lattice type Latin patterns in the other odd- dimensioned LS’s (order 5 and 7).The numbers of Latin squares of orders 2 and 3 (in standard format) are 1 and 2 respectively (the latter are orthogonal); there is only one structure type and one isotopy class, and the number of squares in reduced form is 1 for both orders (table 4.2.1).
3.6. Latin patterns in order 6 and 7 Latin squares
It was tempting , and feasible without elaborate computational means, to determine shape and number of Latin patterns of orders 6 and 7, thus following the rise with order number of a significant parameter: the number of Latin patterns. This was done in a manner similar to the sequential enumeration method (Appendix II).
Ten order 6 Latin patterns emerged , presented in Fig. 3.6.1 in such a manner that their geometry and symmetry are best shown. They are (still) remarkably symmetric, similar to those of orders up to 5. Numbers 4 and 10 show a fourfold axes, numbers 1, 2, 5, 8, 9 two diagonal mirror lines, numbers 3 and 7 a mirror line and a beautiful horizontal glide line respectively, and number 6 “only” an inversion centre. Sites at diagonal nearest-neighbour – and at “knight’s move” distance – have been connected in Fig. 4.1.1. The patterns are rather chain-like in a diagonal direction, numbers 4, 6 and 10 excepted.
An order 6 Latin square will be a combination (superposition) of (some of) the Latin patterns shown in Figure 3.5, in numbers between 0 and 6, totalling 6.
In order to determine the number of independent order 6 LS's - following up on our result, 18, for order 5 LS's - one might follow the Latin pattern procedure laid down in the Chapter 3: generate (Appendix II) a number of order 6 LS's, determine the Latin pattern composition for all of them, determine the number of structure types (α, β, ..) per composition, determine the multiplicity for the structure types obtained, sum the multiplicities and count the structure types, proceed - repeating the preceding steps with additional LS's - until the sum of the multiplicities reaches 1128960, the literature value for the number of order 6 LS's in standard format. The structure type count at this point is the number of independent order 6 LS’s
Figure 3.6.1. All Latin patterns of order 6 Latin squares.
The number of Latin patterns obtained for order 7 is 28. We have confined ourselves to presenting their position coordinates in Table 3.6.1. Many of them are without symmetryfree. Fig. 3.6.2 shows some patterns with remarkable structure. There is also a lattice type Latin pattern (nr 27) similar to the orders 3 and 5 Latin patterns L (Fig. 3.1.1, par. 3.5).
Table 3.6.1. Position coordinates of all Latin patterns of order 7.
First number is vertical coordinate in column 1, etc.
1. 7654321 06. 7645231 11. 7651432 16. 7324651 21. 7632514 26. 7531642
2. 7265431 07. 7653421 12. 7645123 17. 7631425 22. 7524631 27. 7351624
3. 7354261 08. 7564231 13. 7615234 18. 7642531 23. 7635214 28. 7536142
4. 7546132 09. 7354612 14. 7254361 19. 7632541 24. 7536241
5. 7563241 10. 7651234 15. 7562143 20. 7634152 25. 7624153
Figure 3.6.2. Left: order 7 Latin pattern nr 12 “Aircraft in combat”, symmetry m
Right: order 7 Latin pattern nr 27 “Two-type distorted hexagons”, symmetry mm