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 five independent LS’s by establishing symmetry relations between them and counting symmetry-identical LS’s as one. The reduction process for the 1344 LS’s of order 5 will be performed on the basis of the Latin patterns concept: the n arrangements of of same symbol sites in an order n Ls-structure. Lp’s are considered the same when they are geometrically isomorphous (isometric). So we aim here at the arrangement as such, indifferent of orientation, position in the cell and boundary-shifts displacements (par.1.5). A Latin square of order n is a superposition of n Latin patterns (par. 1.1) and can be represented by a Lp-diagram and – formula.
The number of different Lp’s happens to be 4 in 5×5 Latin squares. We term 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 directions of the sites lattice. We note that the number of different Lp’s here is lower than n. This means that each order 5 Latin square carries at least two equal Lp’s . Similar situation for n 2, 3 and 4 (par. 3.5).
The Latin pattern definition and – number originates from collecting and structuring equally valued sites in Lp’s within (already known Ls’s of fixed order. A more inductive way towards Lp’s and Lp-numbers is structuring them analytically, on the basis of one value per row and column, in a nxn frame. (Structuring related to the rooks problem on a chess board, see below). The number of unique Lp’s is lower than n up to order 5 but – as we will see (par.3.6) – much larger for n from n 6: 10 and 27 Lp’s for n=6 and 7 respectively. It remains to be seen in what ways some or all of them participate in building Latin squares (par. 3.6) – .
String Triple/Couple Couple/Couple/Single Lattice
Figure 3.1.1. Latin patterns in order 5 LS’s
The Latin patterns above taken from various order 5 Ls's (fig. 3.2.1), 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. 9); the other 19 are merely products of translation of ST, TC,CCS and L across the edges of the board 9. 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 are also lattice type Latin patterns for n=3 and 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 field ( wallpaper structure, par. 1.6, 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.
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 ten are binary or tertiary composites. String (ST) and Lattice (L) are (mutually) incompatible.
We established in this process that LS-structure type and Latin pattern composition and are strongly correlated. A specific structure type is adopted by the members of 10 families. The remaining 4 families are double-structured (ds): allow two structure types, ”we name them α 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. 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. Numbering 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.4).
|type||class||Latin pattern formula||mult||contr. TR||contr. PR||red. form||conv. planar group||symmetry elements||Bravais lattice conv. col.|
|1||(1)||5ST||2||2||1||1||pm||2D col. trl. symm.||rect rect|
|conv. m main|
|2||(1)||5TC||20||4||3||p1||1D col. trl. symm.||obl obl|
|i' (rb) (yg)|
|3||(2)||ST.4TC||100||4||13||10||p1||i' (yg) (bp)||obl obl|
|4||(2)||TC.CCS||200||6||25||16||p1||no symmetry||obl obl|
|5α||(2)||2ST.TC.2CCS||50||2||9||4||p1||m' main (yp)||obl rect|
|m' back (gb)|
|5β||(2)||2ST.TC.2CCS||50||2||9||4||p1||m' main (gb)||obl rect|
|m' back (ry)|
|6α||(2)||ST.TC.3CCS||100||4||15||p1||m' main (yb||obl rect|
|6β||(2)||ST.TC.3CCS||100||4||15||p1||m' back (yb||obl rect|
|7||(1)||ST.4CCS||50||2||9||5||pm||conv. m back||rect rect|
|m' main (yg) (bp)|
|8α||(2)||TC.4CCS||100||4||15||4||p1||m' back (yg)||obl rect|
|8β||(2)||TC.4CCS||100||4||15||4||p1||m' main (gp)||obl rect|
|9||(1)||4TC.L||50||2||7||p1||4' axis (rygp)||obl sq|
|10||(1)||5CCS||20||4||3||p1||1D col. trl. symm.||obl obl|
|i' (rb) (gp)|
|11||(2)||3TC.CCS.L||200||6||25||8||p1||no symmetry||obl obl|
|12α||(2)||4CCS.L||50||2||7||p1||4' axis (rbgp)||obl sq|
|12β||(2)||4CCS.L||50||2||7||p1||4' axis (prgb)||obl sq|
|13||(2)||2TC.CCS.2L||100||4||13||p1||i' (rg) (bp)||obl obl|
|14||(1)||5L||2||2||1||p1||2D col. trl. symm.||obl sq|
|4' axis (rpgb)|
List 3.2.2. All 14 families of 5×5 Latin squares, comprising 18 structure types in two isotopy classes (par. 1.2) with pattern compositions: columns 1,2,3.
The mulitiplicity of each of the structures (par.3.3 is given in column 4. The total is 1344. The contributions to the PR- and TR-representations (par.3.4 and Appendix III) are in the 5th and 6th column respectively. They are totalized underneath. Column 7 gives the numbers of the reduced-form Ls’s per structure and their total: 56.The conventional planar groups are in column 8. Column 9 mentions the conventional (conv.), colour (col.) and translation (trl.)symmetry elements of each of the structures. Bravais lattice-types based on conventional or colour symmetry abbreviated as obl (oblique) rect (rectangular) sq (square) are in colums 10 and 11 respectively.
Further abbreviations: colour fourfold axes: 4′, col. inversion centres i’ col. mirror lines m’, parallel with main or back diagonal: main / back. Lettering (yg) (rygp) etc. with r red, etc. 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 combinatorily 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 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.6).
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. 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 groups (planar groups), pm for 1 and 7 and p1 (oblique crystal system) for the other structures, totalling 2, are running far below the number of structures, 18. It means that 95 % of the 1344 order 5 LS’s are without conventional 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 . Fourfolds in a five by five! Accepting colour symmetry raises the symmetry here from oblique to square. Colour symmetry element 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 0f 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. This means that 200 different Ls’s can be retrieved from the toroidal representation (similar to Fig. 1.6.1) of structure type 4 (or 11). 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 in Chapter 2, from the full set of order 4 LS’s with 24 members, to a representation of 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). We will term them PR- and TR- representation for any order.
W. Barink (ref. 10) 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.11). 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 order 5 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 main diagonal to produce another or reproduce itself . Clearly, this will lead (again, par.3.3) 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 the order 4 – and most of the order5 Ls’s following the sequential enumeration scheme (Appendix II ) It is more rational for higher order to let nomenclature follow the multiplicity (par.3.3) movements (translations, rotations etc. in a certain order when the members of each LS-structure type are created, 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 such as 7 and 9, with multiplicity 50 (above), there will clearly be 4 paths leading from the preferred – to the same transformed member. Some symmetry convention could be for adopted for numbering, such as h >k etc., which are well known in crystallography.
Distinguishing LS members can be facilitated by abbreviating them as digital 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
Similar to Expr 3.1.1 we have the general composition:
hSTR.kCC with h+k=4 (3.5.1)
There are three composition families, 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 h=4, k=0 LS01, 05, 18, 24
2ST.2CC h=k=2 LS02, 03, 07, 09, 16, 20, 22, 23
4CC h=0, k=4 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 5.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 fitting (!) combination (superposition) of (some of) the Latin patterns shown in Figure 3.5, in numbers between 0 and 6, totalling 6.
We do know that such combinations exist, otherwise there would be no order 6 Latin squares.There are in fact 1128960 of them (Table 5.1).We also know that there are 10 order 6 monolithic (par.3.2) Ls's: 6Lp for all order 6 Latin patterns shown above by repeating the Lp's across the entire x or y axis of the Ls cell. Try to prepare others by completing a Ls with first rows: 1 2 3 4 5 6 / 2 1 4 3 6 5. Detect the Lp's in your Latin square; next alter your Latin square by switching rows or columns and see how many of the remaining Lp's appear.Try to design an order 6 Ls with high (colour) symmetry.
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 symmetry. 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