Chapter 1: Introduction to Latin Squares

In this post, I will diverge from my typical topics to provide essential insights into a combinatorial structure known as a Latin square. These structures were the focal point of my undergraduate thesis, which I consider not particularly well-crafted, and they continue to be a central element of my ongoing research. You can find the details of this research on its GitHub page. This article serves as a foundational guide for understanding subsequent discussions related to my research, which primarily involves computational methods for generating Latin squares and examining whether groups of Latin squares exhibit a specific property known as (mutual) orthogonality. For a brief glimpse into this topic, refer to a previous blog post, although note that the code has since evolved. Below, I will outline key information about Latin squares, their structures, and properties that are relevant to developing algorithms for my ongoing research.

Understanding Latin Squares

A Latin square of order n is defined as an n x n array filled with n distinct symbols, each appearing exactly once in each row and each column. This definition may seem complex, so let’s look at an example of a Latin square of order 4.

As illustrated, the numbers 1, 2, 3, and 4 appear four times each, without repetition in any row or column. A practical example of a Latin square is a completed Sudoku puzzle, which constitutes a Latin square of order 9, though Sudoku has additional constraints involving 3x3 subgrids that do not apply to traditional Latin squares.

One significant application of Latin squares is in statistics, specifically in the design of experiments using Latin square designs. Their utility extends to error-correcting codes, algebraic Cayley tables, and various mathematical games and puzzles. For further details on these applications, you can refer to the Latin square Wikipedia page.

Normalized Latin Squares

Below are two additional examples of Latin squares: one of order 3 and another of order 5. Notice that, unlike the previous example, both the first row and the first column are arranged in ascending order.

Latin squares that conform to this format are termed normalized Latin squares. Formally, a normalized Latin square is characterized by the first row and column consisting of 1, 2, …, n. Any Latin square can be transformed into a normalized form through row and column permutations. For instance, the earlier order 4 square can be normalized by simply swapping the second and fourth rows, resulting in the normalized square displayed below.

While normalizing a Latin square typically requires multiple row and column swaps, the process remains straightforward.

Reduced Latin Squares

Although the terminology may not be universally accepted, I learned that a reduced Latin square is one where the first row is arranged as 1, 2, …, n, but the first column does not need to follow this order. The previously presented order 4 square is a reduced Latin square but not a normalized one. In most literature, including the Latin square Wikipedia page, the terms reduced and normalized are often treated interchangeably, which is likely the more accepted convention. I have yet to discover a better term for this specific structure, which plays a crucial role in assessing Latin square orthogonality. Instead of examining every square of order n for orthogonality, it suffices to check only the reduced Latin squares of that order.

Isotopy Classes

Two Latin squares belong to the same isotopy class if one can be derived from the other through permutations of rows, columns, and symbols. In simpler terms, if we can transform one square into another using row swaps, column swaps, and symbol substitutions (e.g., replacing all instances of 3 with 1 and vice versa), then the resulting square is in the same isotopy class as the original. Latin squares that share this property are said to be isotopic or to share isotopy class equivalence.

For each order, there exists a set of squares known as isotopy class representatives. By recursively permuting the rows, columns, and symbols of an isotopy class representative, we can generate all Latin squares within that isotopy class. For instance, for order 5, there are two isotopy classes, represented as shown below.

To illustrate, we can create a new square by swapping rows one and two of the leftmost isotopy class representative. This action alone generates a new Latin square. We can continue by swapping additional rows, columns, and symbols to produce even more squares. For symbol permutation, we can take the original representative and switch the symbol "3" with "1," resulting in yet another distinct Latin square.

Isotopy classes are significant because they enable the generation of all Latin squares of a particular order from just a few squares—one from each isotopy class. For instance, there are 22 isotopy classes for order 6, meaning that from just 22 Latin squares of this order, we can derive the remaining 812,851,178 squares (with a total of 812,851,200 squares of order 6).

(Mutually) Orthogonal Latin Squares

The concept of orthogonality in Latin squares was the primary focus of my undergraduate thesis. Two distinct n x n Latin squares, A = (a_ij) and B = (b_ij), are considered orthogonal if every ordered pair (a_ij, b_ij) is unique. A collection of Latin squares that are mutually orthogonal is referred to as mutually orthogonal Latin squares (MOLS). This characteristic is best understood through examples. Below is a set of two order 4 Latin squares that are orthogonal.

The resulting square of pairs is formed by taking the element at position (i,j) in both Latin squares and creating the pair (a_ij, b_ij) in the rightmost square. It is easy to verify that no pairs in this square are repeated, confirming that these two Latin squares are indeed orthogonal. In contrast, the squares below are not orthogonal, as evidenced by the repeated pairs (1,1), (2,2), (3,3), (4,4), (1,3), and (3,1). The three squares presented are mutually orthogonal.

The verification of orthogonality for these squares is omitted for brevity.

Orthogonal Latin squares find applications in various fields, including the design of experiments, error-correcting codes, and the study of finite projective planes. R. C. Bose formulated the following theorem regarding this last application:

Theorem: A finite projective plane of order n exists if and only if there exists a complete set of MOLS, i.e., a set of MOLS containing (n-1) Latin squares of order n.

Current Research

My undergraduate research was centered on Latin squares. Lacking formal education in combinatorics, I began as a self-study of these objects. Eventually, I investigated the orthogonality of Latin squares of orders 2–6. Interestingly, I discovered that all orthogonal squares were also isotopic, and the representative of this isotopy class was symmetric. This observation held true for order 5, trivially for order 4 (as all representatives are symmetric), and vacuously for order 6 (since there are no orthogonal squares). My ongoing research aims to explore whether this conjecture extends to higher orders: specifically, whether orthogonal Latin squares are isotopic to a symmetric Latin square. To further investigate this for higher-order Latin squares, it has become essential to develop efficient algorithms capable of handling large quantities of Latin squares.

Currently, the most efficient method for generating Latin squares involves producing one isotopy class at a time. This approach allows for clearing memory after generating all squares in a class. However, I am also developing a GPGPU algorithm that generates squares in bulk, disregarding isotopy classes. This method consumes substantial memory, which my desktop (32 GB of RAM) struggles to accommodate. The challenge arises from needing to maintain a list of all previously generated distinct squares to determine if newly created squares are duplicates, which leads to their discarding if so. Detailed information about the algorithms used for generating Latin squares can be found in my undergraduate thesis.

To illustrate the memory implications, consider generating Latin squares of order 6, which requires storing 36 values ranging from 0 to 5. This can be optimally achieved with 3 bits. In practice, however, using bitwise operations to store each digit within a 64-bit integer is cumbersome, leading to the use of smaller data types, such as short in C++. Therefore, each square realistically requires at least 576 bits for storage. Notably, approximately 812 million Latin squares exist for order 6. A 32-bit integer can effectively represent all these values. Consequently, if a mapping can be devised that translates a Latin square of order n to a distinct real value, the algorithm would utilize less than one-third of the optimal memory and approximately 6% of the realistic implementation memory for order 6. This efficiency would improve significantly for higher-order Latin squares. Developing such a mapping is currently one of my primary research objectives. It’s important to note that the mapping does not need to maintain the correlation between squares and their represented values; the goal is simply to track whether a square was generated.

Additionally, I have developed a keen interest in another unresolved question regarding orthogonal Latin squares: is it possible to find a set of three mutually orthogonal Latin squares of order 10? While it has been established that pairs of Latin squares of order 10 exist, the existence of a full set (containing n-1, or 9, mutually orthogonal Latin squares) remains uncertain. Insights from my ongoing research on Latin squares could potentially shed light on this question.

For more detailed visual insights, consider watching the following videos:

This lecture discusses Two Way ANOVA and the significance of Latin squares in experimental design.

This video explains the Latin Square Design of Experiments, illustrating examples using Minitab.