Latin Square Problem: Indempotent Commutative Quasigroup of Order 7

Question

I missed the lecture that my professor went over Latin Squares and Idempotent Commutative Quasigroups. I understand it's essentially like the puzzle game Sudoku. I realize there are multiplication tables that correspond with each quasigroup. Can someone explain how those work exactly. I just need some help understanding how to make the table, what operation to use, etc. Ex's would be appreciated!

Answer 1

You probably know what a Magma is, simply a set with some binary operation back to itself. This means you put two things from the set in, and you get something from the same set out. Let's start with a small example, the set $\{a,b\}$. We can write the product of $a$ and $b$ in a multiplication table. Start with something like this:

$\begin{bmatrix} \times & a & b \\ a & \\ b& \end{bmatrix}$

And we can write the entry for $x \times y$ in the row with $x$ and column with $y.$ One Magma is as follows:

$\begin{bmatrix} \times & a & b \\ a & b & a\\ b& b & b \end{bmatrix}.$

Here $b \times a = b$ and so on. notice that if we take just the matrix products, what we get is not a Latin square:

$\begin{bmatrix} b & a\\ b & b \end{bmatrix}.$

What do we need to make it a Latin square? We need every element to appear in each row. For row $a$, and for any $c$ we need $a \times x = c$ for some $x$. For row $b$ we need to solve $b \times x = c$. Basically we need to be able to solve $$dx=c$$ for every $d$ and $c$. If you think about the columns, and what we need for every element to appear there, then we need to solve $$xd=c.$$ We get these same equations not just in the two element case, but for any finite set.

Thus what we really want is the ability to sort of $``$divide$"$ by $d$. A Magma where we can solve each of these equations is called a Quasigroup. Here the divisibility condition guarantees that every element will appear in each row and column, and we can simply use the fact that our set is finite to also conclude that no element can appear more than once.

You said your professor is adding in commutativity, which means that $a\times b=b\times a$. This will guarantee that your Latin square is also symmetric. Thus you can flip it over the main diagonal, the one from top left to bottom right, and it will still look the same.

Your professor is also adding in an idempotent element, which is an element where $x^2=x$. I don't know what you are learning for certain, but if every element has that property then the main diagonal would read off the elements themselves in the order for which you made the table. So I can't say more without you being more specific, but I hope this helps a little.

Answer 2

These tables are called Cayley tables. For binary operations on finite sets (usually groups, but it applies to quasigroups and other weaker structures), we can essentially develop a full multiplication table, in exactly the way you'd expect.

For example, take the group $\mathbb{Z}_2 \times \mathbb{Z}_2$, under addition. It has exactly $4$ elements: $(0, 0)$, $(1, 0)$, $(0, 1)$, and $(1, 1)$. We can form the Cayley table like so: \begin{matrix} & \color{red}{(0, 0)} & \color{red}{(1, 0)} & \color{red}{(0, 1)} & \color{red}{(1, 1)} \\ \color{red}{(0, 0)} & (0, 0) & (1, 0) & (0, 1) & (1, 1) \\ \color{red}{(1, 0)} & (1, 0) & (0, 0) & (1, 1) & (0, 1) \\ \color{red}{(0, 1)} & (0, 1) & (1, 1) & (0, 0) & (1, 0) \\ \color{red}{(1, 1)} & (1, 1) & \color{green}{(0, 1)} & (1, 0) & (0, 0) \\ \end{matrix} Each entry in the table represents the sum of the red column head and the red row head. For example, the highlighted green entry represents the fact that $$(1, 1) + (1, 0) = (0, 1).$$ Cayley tables have the advantage that certain group properties are easy to spot. For example, the group is commutative, since the table is symmetric about the main diagonal.

We can also see that $(0, 0)$ is the group's identity, since the row/column beside/under $\color{red}{(0, 0)}$ is identical to the row/column of table headers. That is, we get the property that $a + (0, 0) = (0, 0) + a = a$ for any $a$ from the four group elements. Moreover, we can see that this operation has inverses (like any group should), because $(0, 0)$ appears in every row and column (and since we get $(0, 0)$ down the main diagonal, we have $a = -a$ for every $a$).

Notice that the structure is a Latin square: every element of $\mathbb{Z}_2 \times \mathbb{Z}_2$ occurs exactly once in every row and column (the row/column heads don't count). If you're trying to find a given element $b$ in the row for $a$, you're solving the following equation for $x$: $$a + x = b.$$ In a group, there is always exactly one solution to this equation. Similarly, if you're solving for columns, $$x + a = b.$$ There's no difference if the group is commutative (i.e. when the rows match the columns), but this isn't always the case.

For example, if you're looking for $\color{green}{(0, 1)}$ in the $\color{red}{(1, 1)}$ row, the table shows you that you want the entry in the $\color{red}{(1, 0)}$ column. That is, the unique solution to $\color{red}{(1, 1)} + x = \color{green}{(0, 1)}$ is $x = \color{red}{(1, 0)}$.

So, you can take finite groups, find their Cayley tables, and get a whole bunch of Latin squares. Can you go the other way? Can you begin with a Latin square and find a Cayley table for a group to match it?

The answer is "no", in general. The notion of group is too strong. But, you can always take the set of entries in your Latin square (typically $\lbrace 1, \ldots, n\rbrace$) and use your Latin square to define an operation on the set (call it $\circ$). The Latin square structure, i.e. every entry is found in exactly one row or column, corresponds to unique solutions for equations of the form: $$\begin{align*} a \circ x &= b, \\ x \circ a &= b. \end{align*}$$ When a binary operation yields unique solutions to the above equations, regardless of the values of $a$ and $b$, we get a quasigroup. Conversely, the Cayley table of any quasigroup is a Latin square.

Let's do an example. Take the following $5 \times 5$ Latin square: $$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 5 & 3 \\ 3 & 5 & 4 & 2 & 1 \\ 4 & 1 & 5 & 3 & 2 \\ 5 & 3 & 2 & 1 & 4\end{pmatrix}.$$ We define an operation on $\lbrace 1, 2, 3, 4, 5 \rbrace$ by putting this matrix into a Cayley table: $$\begin{matrix} & \color{red}{1} & \color{red}{2} & \color{red}{3} & \color{red}{4} & \color{red}{5} \\ \color{red}{1} & 1 & 2 & 3 & 4 & 5 \\ \color{red}{2} & 2 & 4 & 1 & 5 & 3 \\ \color{red}{3} & 3 & 5 & 4 & 2 & 1 \\ \color{red}{4} & 4 & 1 & 5 & 3 & 2 \\ \color{red}{5} & 5 & 3 & 2 & 1 & 4\end{matrix}.$$ This defines our operation. For instance, if I wanted to know the value of $3 \circ 2$, I would look at my table in the $\color{red}{3}$ row and $\color{red}{2}$ column, to find the number $5$. So, $3 \circ 2 = 5$. Such a structure is a quasigroup. (Note, however, that it's not commutative, since $2 \circ 3 = 1 \neq 3 \circ 2$.)

Your problem is finding an order $7$ idempotent (meaning $x \circ x = x$, for all $x$) commutative quasigroup. In terms of Latin squares, you need to find a Latin square (quasigroup) that is symmetric about the main diagonal (commutative), and contains $1, 2, \ldots, 7$ down the main diagonal (idempotent). Good luck!