miguelgondu's blog

Latin Squares and Finite Groups

Last semester, for an algebra homework, I was trying to prove that there exist only 2 groups of order 6 (namely Z6\mathbb{Z}_6 and S3S_3). The usual argument uses the classification of groups with order pqpq (with pp and qq prime), which itself uses Sylow theorems, but I wondered if I could prove it computationally. Here's my attempt.

Definition: a magma is a pair (G,)(G,\ast) where GG is a non-empty set and \ast is a binary operation on GG. A quasigroup is a magma in which the equations gx=hgx=h and yg=hyg=h, with g,hGg,h\in G, always have a unique solution for xx and yy in GG. A group is a magma in which \ast is associative, modulative and invertive.

Another way of defining a quasigroup is as a magma in which the left and right cancellation laws hold. Note that we're not asking \ast to be associative in a magma (let alone in a quasigroup).

All there is to know about a finite magma (G,)(G,\ast) is encoded in its Cayley table: a matrix that shows how the elements in MM operate among themselves. In general, if G={a1,,an}G = \{a_1, \dots, a_n\}, the Cayley table looks like this:

a1ana1a1a1a1ananana1anan\begin{matrix} \ast&a_1&\dots &a_n\\ \hline a_1&a_1a_1&\dots &a_1a_n\\ \vdots&\vdots&\dots&\vdots\\ a_n&a_na_1&\dots &a_na_n\\ \end{matrix}

That is, the element in the (i,j)(i,j)-th position is the result of multiplying aia_i with aja_j in that order.

You can tell a lot about a magma and its operation just by looking at its Cayley table. For example, consider Klein's 4 group VV:

eabceeabcaaecbbbceaccbae\begin{array}{c|cccc} *&e&a&b&c\\ \hline e&e&a&b&c\\ a&a&e&c&b\\ b&b&c&e&a\\ c&c&b&a&e\\ \end{array}

You can immediately tell its commutative (because the matrix is symmetric), you can tell there is an identity (namely ee) and that each element is its own inverse. You could also tell if the binary operation is associative from its Cayley table using Light's test, although it isn't any better, computationally speaking, that just verifying every case by hand.

We will use Cayley tables as the bridge between algebra and combinatorics.

Latin squares and quasigroups

Definition: a n×nn\times n matrix of nn different entries is called a latin square if no element appears more than once in any row or column. This property is called the latin square property.

We will deal with latin squares of size nn whose entries are the integers from 00 to n1n-1. For example

[012120201]\begin{bmatrix} 0&1&2\\ 1&2&0\\ 2&0&1\\ \end{bmatrix}

is a latin square of size 33. We will also start indexing by 0.

Theorem 1: if (G,)(G, \ast) is a quasigroup, then its Cayley table is a latin square.

Proof: Suppose G={a1,,an}G = \{a_1, \dots, a_n\} and that an element bGb\in G appears twice in row ll (say, in columns jj and kk), by the definition of the Cayley table, this means that

alaj=b=alaka_la_j = b = a_la_k

and because GG is a quasigroup, the left cancellation law implies that aj=aka_j = a_k, which is absurd because we assumed that jj and kk were different. Analogously, the right cancellation law implies that no element appears twice in any column. Q.E.D.

This theorem has a reciprocal of some sort:

Theorem 2: Given a latin square L=(lij)L = (l_{ij}), one can construct a quasigroup whose Cayley table is LL.

Proof: Let G={l11,,l1n}G = \{l_{11}, \dots, l_{1n}\} and denote gi:=l1ig_i := l_{1i}. Define \ast by

gigj=glijg_i * g_j = g_{l_{ij}}

by definition, \ast is well defined (that is, it is closed in the set). We need to check that the equations gx=hgx =h and yg=hyg = h have unique solutions. Consider glx=gkg_lx = g_k, because LL is a latin square, gk=l1kg_k = l_{1k} appears somewhere in row ll, call the column it appears in mm, then x=gmx = g_m is a solution to glx=gkg_lx = g_k. It is unique, because if there existed gm~g_{\widetilde{m}} such that glgm~=gk=glgmg_lg_{\widetilde{m}} = g_k = g_lg_m, then gkg_k would appear twice in row ll, which contradicts the fact that LL is a latin square. Analogously, now arguing with columns, yg=hyg = h has a unique solution in GG. Q.E.D.

So now we're set!, we only need to find all latin squares of size nn and to verify if they represent a valid binary operation for a group. Moreover, we could force the existence of an identity by focusing on finding normalized (or reduced) latin squares (that is, latin squares where the first row and column are 0,1,,n10, 1, \dots, n-1).

The algorithm for finding normalized latin squares of size n.

I use a depth-first-search style algorithm, starting with a normalized n×nn\times n matrix

A=[01n1111n111]A = \begin{bmatrix} 0&1&\cdots&n-1\\ 1&-1&\cdots&-1\\ \vdots&\vdots&\ddots&\vdots\\ n-1&-1&\cdots&-1\\ \end{bmatrix}

where the unvisited locations are labeled with a 1-1. We also start with an empty stack SS. The algorithm goes as follows:

  1. Put matrix AA in the stack SS.
  2. If the stack SS is empty, stop; if it isn't, pop a matrix BB from it.
  3. Find the first unvisited position (i,j)(i,j) in BB (i.e. the first 1-1), if there isn't any, it is finished, put it in a special list of finished latin squares and go to step 2.
  4. Push into the stack the result of replacing this 1-1 with every number from 00 to n1n-1 that isn't already on its row or column.
  5. Go to step 2.

Here's the algorithm implemented in python:

def dfs_in_matrix(A):
    # First we create an empty stack and we put the initial matrix
    # in it.
    list_of_solutions = []
    stack = LifoQueue()
    stack.put(A)
    
    while not stack.empty():
        # We pop a matrix from the stack
        B = stack.get()
        
        # We check if it's finished.
        if is_finished(B):
            list_of_solutions.append(B)
            continue
        
        # We find an unvisited position
        position = find_first_unvisited_position(B)
        if position == None:
            continue
        
        span = span_of_position(position, B)
        for k in range(len(B)):
            if k not in span:
                C = B.copy()
                C[position] = k
                stack.put(C)

    return list_of_solutions

def find_normalized_latin_squares(number):
    A = np.zeros((number, number))
    for k in range(number):
        A[0, k] = k
        A[k, 0] = k
    for i in range(1, number):
        for j in range(1, number):
            A[i, j] = -1
    list_of_solutions = dfs_in_matrix(A)
    return list_of_solutions

(the functions is_finished, find_first_unvisited_position and span_of_position are auxiliary, check this jupyter notebook for all the code discussed in this post). It checks out with the literature on the topic1, saying that there are 9408 normalized latin squares of size 6.

The Magma class

Once we have all the normalized latin squares, we can build up a Magma class in python and we can write a verification function to find which of these correspond to associative operations (and thus to groups).

class Magma:
    def __init__(self, _matrix):
        self.cayley_table = _matrix
        self.set = set(range(0, len(_matrix[0,:])))
    
    def mult(self, a, b):
        return int(self.cayley_table[a, b])

def is_magma_associative(mag):
    '''
    This function verifies if magma `mag` is associative by brute force.
    '''
    n = len(mag.cayley_table)
    _flag = True
    for a in range(n):
        for b in range(n):
            for c in range(n):
                _flag = _flag and (mag.mult(a, mag.mult(b,c)) == mag.mult(mag.mult(a,b),c))
    return _flag

def find_groups(number):
    latin_squares = find_normalized_latin_squares(number)
    associative_magmas = [sol for sol in latin_squares if is_magma_associative(Magma(sol))]
    return associative_magmas

After running this is_magma_associative in all 9408 reduced latin squares of order 6 we're left with 80 reduced latin squares such that, when interpreted as quasigroups, are associative. That is, only 80 of the original 9408 reduced latin squares of size 6 can be interpreted as Cayley tables for groups.

The main result

We're trying to prove the following theorem:

Theorem 3: There are only 2 groups of order 6, namely S3S_3 and Z6\mathbb{Z}_6.

It is useful, then, to cleary state what we interpret as S3S_3 and Z6\mathbb{Z}_6. Z6\mathbb{Z}_6 are the usual integers modulo 6 with sum modulo 6, but note that Z6\mathbb{Z}_6 can also be interpreted in the following way: its a group of six elements {a1,a2,a3,a4,a5,0}\{a_1, a_2, a_3, a_4, a_5, 0\} such that

  • a1a_1 and a5a_5 have order 6.
  • a2a_2 and a4a_4 have order 3.
  • a3a_3 has order 2.
  • a22=a4a_2^2 = a_4
  • a1a2=a3a_1a_2 = a_3

(note that we just changed ii for aia_i). We can use this information to find an isomorphism between a latin-square-generated group and Z6\mathbb{Z}_6.

S3={σ1,σ2,σ3,ρ1,ρ2,id}S_3 = \{\sigma_1, \sigma_2, \sigma_3, \rho_1, \rho_2, \text{id}\} is usually interpreted as the group of symmetries of a triangle (where σi\sigma_i is the reflection that fixes vertex ii and ρj\rho_j is a rotation of 120j120*j degrees, but we prefer the following presentation:

S3=σ,ρσ2=ρ3=id,σρ=ρ2σS_3 = \langle \sigma, \rho\,\vert\,\sigma^2 = \rho^3 = \text{id},\, \sigma\rho = \rho^2\sigma \rangle

In this presentation, the 6 different elements are id,σ,ρ,ρσ,ρ2σ\text{id}, \sigma, \rho, \rho\sigma, \rho^2\sigma and ρ2\rho^2.

So, to prove theorem 3, we will follow this strategy: we will give an isomorphism from either S3S_3 or Z6\mathbb{Z}_6 to each of the 80 groups found using latin squares:

Proof (of Theorem 3): Theorem 1 and 2 show that all possible groups of a certain order are restricted by the amount of normalized latin squares of said order. After filtering the normalized latin squares of size 6 by verifying which represent an associative binary operation, we're left with 80 Cayley tables for groups. In this jupyter notebook we show an explicit isomorphism between each of these 80 latin square generated groups and either Z6\mathbb{Z}_6 or S3S_3, but for the sake of completeness we show how these isomorphisms were constructed with explicit examples for Z6\mathbb{Z}_6 and S3S_3. Consider the following normalized latin square:

[012345154230230154345012421503503421]\begin{bmatrix} 0 & 1 & 2 & 3 & 4 & 5\\ 1 & 5 & 4 & 2 & 3 & 0\\ 2 & 3 & 0 & 1 & 5 & 4\\ 3 & 4 & 5 & 0 & 1 & 2\\ 4 & 2 & 1 & 5 & 0 & 3\\ 5 & 0 & 3 & 4 & 2 & 1\end{bmatrix}

and call the group it induces GG. After inspecting it, we can tell that the orders of their elements are either 22 or 33, so it is a candidate for being isomorphic to S3S_3. Choose 4σ4\mapsto \sigma and 5ρ5\mapsto \rho, and note that (55)4=14=3=45,(5*5)*4 = 1*4 = 3 = 4*5, that is, this group obeys the presentation given for S3S_3. The isomorphism would then be given by

S3Gid0σ14σ23σ32ρ5ρ21\begin{matrix} S_3 & & G\\ \hline \text{id}&\mapsto&0\\ \sigma_1&\mapsto&4\\ \sigma_2&\mapsto&3\\ \sigma_3&\mapsto&2\\ \rho&\mapsto&5\\ \rho^2&\mapsto&1 \end{matrix}

Now consider the group HH given by the following reduced latin square:

[012345154230245103321054430512503421]\begin{bmatrix} 0 & 1 & 2 & 3 & 4 & 5\\ 1 & 5 & 4 & 2 & 3 & 0\\ 2 & 4 & 5 & 1 & 0 & 3\\ 3 & 2 & 1 & 0 & 5 & 4\\ 4 & 3 & 0 & 5 & 1 & 2\\ 5 & 0 & 3 & 4 & 2 & 1\end{bmatrix}

because the elements of HH have order either 2, 3 or 6, we will construct an isomorphism between HH and Z6\mathbb{Z}_6 using the identification Z6={a1,a2,a3,a4,a5,0}\mathbb{Z}_6 = \{a_1, a_2, a_3, a_4, a_5, 0\} stated before. First note that 3H3\in H is an element of order 2, 2,4H2, 4\in H have order 6 and 1,5H1, 5\in H have order 3. Because 11=51\ast1 = 5 and 41=34\ast1 = 3, we construct the following isomorphism

Z6H001421334552\begin{matrix} \mathbb{Z}_6 & & H\\ \hline 0&\mapsto&0\\ 1&\mapsto&4\\ 2&\mapsto&1\\ 3&\mapsto&3\\ 4&\mapsto&5\\ 5&\mapsto&2\\ \end{matrix}

Q.E.D



  1. The results the algorithm gave were in par with what's said in Small Latin Squares, Quasigroups and Loops, an article by Brendan D. Mackay, Alison Meynert and Wendy Myrvold. Check Table 1 of their article for more details.