5
$\begingroup$

I have a Cayley table with four elements and a binary structure $*$. I know that if I have the same element along the main diagonal (from top right corner to bottom left corner), then the set is Abelian.

What can I say about the set if the table also has the identity element of the set going down the other diagonal (from the top left to the bottom right)?

Every element appears once in every row and column so I'm tempted to say it's a group. But say the set is {a,b,c,d} where a is the identity element so I need to find the inverse of every element to show it's a group. So, $a*a=a$, $b*b=a$, $c*c=a$, and $d*d=a$. How can an element operated on itself be an inverse?

$\endgroup$
  • 2
    $\begingroup$ For the resulting group to be abelian, the matrix has to be symmetric: the entry corresponding to $a*b$ has to be the same as the entry corresponding to $b*a$. It does not require the same entry in the main diagonal. $\endgroup$ – Arturo Magidin Mar 5 '12 at 16:37
  • $\begingroup$ Okay, so it has to be symmetric. But what if it is also symmetric along the other diagonal and the identity element is the only element along that diagonal? Does this have any significance to determining the structure (say defining it as a group or anything) $\endgroup$ – user23793 Mar 5 '12 at 16:41
  • 2
    $\begingroup$ Note: The "main diagonal" is the name usually given to the diagonal running from top left to bottom right; the diagonal running from top right to bottom left is often called the "main anti-diagonal". $\endgroup$ – Arturo Magidin Mar 5 '12 at 16:42
  • $\begingroup$ @user23793: "Symmetric along the other diagonal" does not make sense. "Symmetric" means that it equals its transpose: the $(i,j)$ component equals the $(j,i)$ component for every $i$ and $j$. This is exactly "symmetric about the diagonal running from top left to bottom right." $\endgroup$ – Arturo Magidin Mar 5 '12 at 16:45
  • 1
    $\begingroup$ @user23793: No, that by itself is not enough to know that what you have is a group. And $b*b=a$ makes perfect sense in a group; what makes you think it doesn't "seem like it makes sense"? See the example I give below. $\endgroup$ – Arturo Magidin Mar 5 '12 at 17:00
9
$\begingroup$

The "main diagonal" of a table/matrix refers to the entries with index $(i,i)$; this is the diagonal that runs from "top left" to "bottom right": it's the entries marked with a $\mathbf{D}$ below: $$\begin{array}{|c|c|c|c|} \hline \mathbf{D}& \cdot & \cdot & \cdot\\ \hline \cdot & \mathbf{D} & \cdot & \cdot\\ \hline \cdot & \cdot & \mathbf{D} & \cdot\\ \hline \cdot & \cdot & \cdot & \mathbf{D}\\ \hline \end{array}$$

If you have a Cayley table, and the elements along the top are ordered the same way as the elements along the side (so that the main diagonal entries correspond to $a*a$ for every $a$, and you already know that this is the Cayley table for a group, and every main diagonal entry is equal, then that entry must be the identity (since $e*e=e$ holds, so every entry must be $e$).

A group in which every element is its own inverse must be abelian: if $xx=e$ for every $x$, and $a$ and $b$ are any two elements, then we have that $(a*b)^2 = e = e*e = a^2*b^2$. So then we have $$a*b*a*b = a*a*b*b$$ and multiplying on the left by $a$ and on the right by $b$ we get $$b*a = a*b,$$ so the group is abelian.

To see an example of a group where this happens, consider the following operation: flipping a rectangular mattress. You can flip it end-to-end; you can rotate it without changing what is on top; you can flip it and rotate it; or you can do nothing. Each of these is an element of a group; if you do the same thing twice in succession, they cancel out. So every element of the group is its own inverse. There is absolutely no problem with that: there are lots of groups like that.

Here is what they look like:

Let us use $E$ to denote "Even", and $D$ to denote "Odd". We make a group with underlying set $\{E,D\}$, and add as follows: $E+E = E$; $E+D=D+E=D$; and $D+D=E$. (Even plus even and odd plus odd are both even; even plus odd and odd plus even or both odd).

Now let $n\geq 1$, and let $G$ be the set of all $n$-tuples $(x_1,x_2,\ldots,x_n)$, where $x_i$ is either $E$ or $D$. We add tuples by adding component by component: $$(x_1,x_2,\ldots,x_n) + (y_1,y_2,\ldots,y_n) = (x_1+y_1,x_2+y_2,\ldots,x_n+y_n),$$ where in each component we are adding following the rules of the previous paragraph. This is a group (it has $2^n$ elements); the identity element of the group is the element $(E,E,E,\ldots,E)$. And in this group, every element is its own inverse: $(x_1,\ldots,x_n) + (x_1,\ldots,x_n) = (E,E,E,\ldots,E)$, no matter what $x_i$ is: if $x_i=D$, then $x_i+x_i = D+D=E$; if $x_i=E$, then $x_i+x_i = E+E=E$. So either way, we get the identity.


However, if you simply happen to find a "Cayley table" on the ground in which every main diagonal entry is equal, this does not suffice to tell you that you have an abelian group before you: associativity is not easy to determine from just staring at the table, and it is possible to write down the Cayley table of a binary operation in which (i) every element appears exactly one in each row and in each column; (ii) the rows correspond to elements in the same order as the columns do; (iii) all the main diagonal entries are the same; but (iv) the table does not correspond to an associative operation (that is, you don't have a group).

Here's an example where this happens: $$\begin{array}{cc|c|c|c|} * && a & b & c\\ &&&&\\ \hline a && a & b & c\\ \hline b && c & a & b\\ \hline c && b & c & a\\ \hline \end{array}$$ Every element appears exactly once in each row and each column, but this table does not yield a group, because the operation $*$ it defines is not associative: $(b*c)*c = b*c = b$, but $b*(c*c) = b*a = c$.

$\endgroup$
0
$\begingroup$

What is being described here in terms of the question "What can I say about the set if the table also has the identity element of the set going down the other diagonal (from the top left to the bottom right)?" sounds to me like such a table could be an XOR Cayley table or at least that type of table could fit the description for associativity and the second diagonal axis also being symmetric.

For example: in a 16*16 Hex Cayley table that represents all possible XOR output values of XOR'ing two hex characters, where the outer two rows and columns become the lookup values, and the center 225 values are the outputs of any XOR equation in the range of 2^4, there exists at least two such configurations that I know of (one which I created, and the other common one seen here: https://i.stack.imgur.com/eIe24.png) where the main diagonal is filled (symmetrically) only with the identity value 0, and the other anti-diagonal is filled only with the value F.

Reasoning: I believe this occurs because exactly half of the table (diagonally) is the mirror inverse of the other half but also because the upper horizontal half is too the mirror inverse of the lower half. This allows lookups not just along the left and top edges, but also by using the right and bottom edges.

Notes: Also, if the length of the table is odd, then both diagonals intersect at the same coordinate and thus only one diagonal can have all uniqe values (else if both do there will be duplicate values per row/column elswhere), whereas a table with an even length on each side must have different diagonals to avoid a duplicate value on the same row/column, in terms of maintaining an abelian quality.

Here is a basic example of such an even length XOR cayley with differing diagonals that are both symmetric across their respective diagonals) table:

$$\begin{array}{c|c|c|c|} \oplus & \text{0} & \text{1} & \text{2} & \text{3} \\ \hline \text{0} & 0 & 1 & 2 & 3 \\ \hline \text{1} & 1 & 0 & 3 & 2 \\ \hline \text{2} & 2 & 3 & 0 & 1 \\ \hline \text{3} & 3 & 2& 1& 0 \\ \hline \end{array}$$

Changing the lookup labels make the table symmetry more visible (where A = 0, etc..):

$$\begin{array}{c|c|c|c|} \oplus & \text{A} & \text{B} & \text{C} & \text{D} \\ \hline \text{A} & 0 & 1 & 2 & 3 \\ \hline \text{B} & 1 & 0 & 3 & 2 \\ \hline \text{C} & 2 & 3 & 0 & 1 \\ \hline \text{D} & 3 & 2& 1& 0 \\ \hline \end{array}$$

P.S. I added the table I created to this question: https://crypto.stackexchange.com/questions/71288/how-many-possible-valid-xor-caley-hex-tables-are-there-in-a-1616

$\endgroup$
  • $\begingroup$ Did you misspell “Cayley”? I get no google hits for “hex Caley table”. $\endgroup$ – Arturo Magidin Jun 14 at 0:26
  • $\begingroup$ Thanks for catching that typo, just corrected it! $\endgroup$ – Steven Hatzakis Jun 14 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.