An Orthogonal Mate for a Latin Square Based on an Asymmetric Tile

Year: 2023 Authors: Stephen M. Gagola, Jr.

Core claim

A Latin square formed from the asymmetric tile has a proper autotopy group isomorphic to D8, and this structure yields an orthogonal mate.

Topics

Latin squares, orthogonal mates, autotopies, asymmetric tiling, orthomorphisms

Domains

combinatorial design theory, group theory, finite algebra, Latin square theory, mathematical art, tiling, puzzle design, generative pattern

Methods

symmetry analysis, group labeling, orthomorphism construction, coloring assignment

Media

asymmetric tile, colored transparent acrylic sheets, laser-cut puzzle

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2023 Conference Proceedings

An Orthogonal Mate for a Latin Square Based on an Asymmetric Tile

Stephen M. Gagola, Jr.

Department of Mathematical Sciences, Kent State University; gagola@math.kent.edu

Abstract

The artist Peter Raedschelders has created what he calls a Magic square based on using 64 congruent copies of an asymmetric tile fitting together snugly in the style of M. C. Escher to form an 8 by 8 Latin square. The “elements” of this square are the 8 distinct aspects, or orientations, of the original tile. He then asks whether the tiles can be colored with 8 distinct colors so that the resulting configuration also forms a Latin square based on colors, and in which the two Latin squares taken together are orthogonal. This indeed is possible by making use of some “hidden symmetries” of the original square.

Latin Squares from Tiles

An $n$ by $n$ Latin square is a square array in which each row and column contains $n$ distinct symbols, usually numbers or letters. However other symbols shapes or colors may be used as well, sometimes with rather dramatic effect. Margaret Kepner’s collection [3] of Latin squares of size 7 by 7 is just such an example.

Two Latin squares of the same size (perhaps using different symbols) are orthogonal if, whenever the squares are super-imposed, no duplication appears among the various pairs of symbols. The reader at this point may choose a quick “sneak preview” of Figure 2 displaying two super-imposed Latin squares, one whose symbols are orientations of an asymmetric tile, and the other using colors for symbols. Orthogonality here simply means that tiles receiving the same color are all oriented differently.

We begin by describing the shape Raedschelders chooses for his tiles in [4]. Starting with a square, modify two adjacent sides to produce two identical curves, each being symmetric with respect to the midpoint of the interval forming a side of the original square. (In other words, if each curve were the graph of a function defined over $[-1,1]$, it would be the graph of an odd function.) A third side is a curve that is symmetric with respect to the perpendicular bisector of the original side of the square (think even function), and the last side is the reflection of the last curve through the side of the square (negative of the last function). Figure 1 shows 64 congruent copies of just such a tile.

There are actually 128 ways to assemble the pieces to build a Latin square. Figure 1 illustrates one of four of these that has $90^{\mathrm{o}}$ rotational symmetry. Other transformations are apparent: the jagged edges running along the left and right sides necessarily exactly match, as do the edges at the top and bottom. Therefore, the entire configuration naturally resides on a flat torus. The 128 examples are obtained by cyclically rotating rows, columns and flipping over any single example.

Hidden Symmetries: Autotopies

We alluded to some symmetries that are apparent in Figure 1. Some others are now described here.

In general, if $L$ and $M$ are Latin squares, an isotopy $L\to M$ is a triple combination of permutations $[{\sigma }_1,{\sigma }_2,{\sigma }_3]$ acting on rows, columns and symbols of $L$ which transforms $L$ into $M$. If the third permutation acting on symbols is trivial (${\sigma }_3=$ the identity), then the isotopy is proper, and if $L=M$ the isotopy is called an autotopy. In our case, where symbols are orientations, we also require that tiles continue to fit snugly together after the isotopy is performed.

Gagola Jr.

Figure 1: A Latin square based on orientations of an asymmetric tile. Rows and columns are indexed by elements of the group $D_8$ .

The $90^{\mathrm{o}}$ rotational symmetry mentioned in the last section is not a true autotopy as rows and columns are exchanged (it is an autoparatopy). But applying it twice produces a $180^{\mathrm{o}}$ rotation that is an autotopy which symbolically may be denoted by $[{\sigma }_1,{\sigma }_2,{\sigma }_3]=[(18)(27)(36)(45),(18)(27)(36)(45),r^2]$ , where $r$ denotes a $90^{\mathrm{o}}$ rotation of orientations. But this not a proper autotopy as $r^2\ne 1$ .

We now describe some proper autotopies.

The jagged edge running horizontally through the middle of the Latin square (between rows 4 and 5) exactly matches the horizontal edges at the top and bottom. So row 4 may be removed and placed at the top, and similarly, row 5 may be removed and placed at the bottom. The gap now appearing between rows 3 and 6 may be closed since appropriate jagged edges continue to match! Using cycle notation, the resulting permutation on rows is: ${\sigma }_1=(1234)(8765)$ . Stopping here transforms the Latin square into a new Latin square, but we’re not finished. Columns may be similarly permuted using ${\sigma }_2=(4321)(5678)$ . Notice that ${\sigma }_2={\sigma }_1^{-1}$ . (Using ${\sigma }_2={\sigma }_1$ would be a valid isotopy, but would not produce an autotopy.) Taking ${\sigma }_3$ to be the identity permutation (acting on orientations) produces the element $[(1234)(8765),(4321)(5678),1]$ which has order 4 in the proper autotopy group of the Latin square.

Another proper autotopy of the Latin square is given by $[(15)(26)(37)(48),(18)(25)(36)(47),1]$ .

An Orthogonal Mate for a Latin Square Based on an Asymmetric Tile

This is an element of order 2 inverting the previous element of order 4. The group that these two autotopies generate therefore is the dihedral group $D_8$ . (It is purely coincidental that this group is the group of symmetries of the square.) Since the proper autotopy group cannot exceed having order 8, this must be the full proper autotopy group of the Latin square of Figure 1. In particular, the Latin square must be (isotopic to) the multiplication table of this group, and so its elements may be labeled by group elements of $D_8$ . We do mention here that this group is often denoted by $D_4$ by non-group theorists and other scientists.

We write $D_8=⟨h,x⟩$ where the generators $h$ and $x$ satisfy the relations $h^4=x^2=1$ and $xh=h^{3}x$ . The eight orientations may now be labeled by the elements of this group, and any tile can be chosen to be designated as the identity element. It is natural to choose the upper left entry to be so labeled, and there is some freedom to choose labels for the remaining elements (because the automorphism group of $D_8$ is transitive on the two elements of order 4, and the four non-central elements of order 2). Labels for tiles in the first column appear immediately to the left of that column, and the labels also serve as indexes for the rows. The first row of tiles is labeled accordingly. Notice that the ordering of the group elements for the rows is different from the ordering for the columns. This is necessary as the tiles must fit snugly together. In particular, the $(x,x)$ entry is not on the main diagonal, but rather is the tile in row 5, column 8 (incidentally illustrating that $x^2=1$ ).

Since the Latin square is known to be (essentially) the multiplication table of a group, the task of finding an orthogonal mate becomes much easier. This is so because an orthogonal mate for the multiplication table of a group exists if and only if some permutation of its columns is such a mate. (This is essentially Theorem 1.13 of [1].) The columns are indexed by the group itself, so a permutation $\sigma$ of its elements is sought so that the table whose $(a,b)$ entry is $a\cdot \sigma (b)$ is an orthogonal mate for the original multiplication table. It turns out that this condition on $\sigma$ holds if and only if the associated function $\tau$ given by $\tau (g)=g^{-1}\sigma (g)$ is also a permutation (in which case $\sigma$ is called an orthomorphism; the associated function $\tau$ is called a complete mapping). This alleviates the task of checking orthogonality of Latin squares to working within the group itself to find an orthomorphism. Notice that if distinct colors are assigned to group elements and the $(a,b)$ entry of the mate, namely $a\cdot \sigma (b)$ , is replaced by its color, a successful coloring of the tiles of Figure 1 is achieved.

Not every group has an orthomorphism. But $D_8$ does, and one example is given in the table below. We also give values for the associated complete mapping $\tau$ , confirming that $\sigma$ really is an orthomorphism. Included in the table is the coloring of group elements that we used to produce Figure 2.

Table 1: An orthomorphism of $D_8$ , and its associated complete mapping.

Concluding Remarks

The previous section used an orthomorphism of the group $D_8$ to construct an orthogonal mate for the Latin square which was its multiplication table. In other words, we produced an example of two orthogonal Latin squares. Since it is possible to produce a collection of seven mutually orthogonal Latin squares (MOLS) of size 8 by 8, it is natural to ask whether this small collection can be extended further. However, the seven MOLS mentioned are based on the multiplication table of the elementary abelian group of order 8. Using an

Gagola Jr.

Figure 2: A puzzle laser cut from colored transparent acrylic sheets depicting two orthogonal Latin squares.

orthomorphism of $D_8$ to construct an orthogonal mate produces two MOLS that cannot be further extended. Somewhat ironically, the multiplication table of $D_8$ can appear in a collection of three MOLS (and three is the maximal number of MOLS for this group). We just can’t use an orthomorphism.

Up to trivial modifications (rounding sharp corners, etc.), is this the only asymmetric tile possible that can be used to build an 8 by 8 Latin square? … No! Peter Raedschelders constructs another such tile, producing a Latin square (appearing in [2]) with a full group of proper autotopies of order eight that is not $D_8$ . Nevertheless, that group does possess orthomorphisms so orthogonal mates do exist. There are other asymmetric tiles whose associated Latin squares have degenerate proper autotopy groups, and for which the existence of an orthogonal mate is in doubt.

There’s still work to be done!

References

[1] A. B. Evans. Orthogonal Latin Squares Based on Groups. Springer, Developments in Mathematics, vol. 57, 2018. [2] B. Grünbaum. “Levels of Orderliness: Global and Local Symmetry.” Proceedings of a symposium at the Wenner-Gren Centre, Stockholm. Portland Press, London, vol 1, 2002, pp. 51-61. [3] M. Kepner. “Latin Fandango” and “Latin Fandango II.” Bridges Art Exhibition Catalog, 2016, p. 75. http://gallery.bridgesmathart.org/exhibitions/2016-bridges-conference/renpek1010 [4] P. Raedschelders. “Semimagic Tiling Based on an Asymmetrical Tile.” Geominatorics 10, 2000, pp. 45-50.