# Given a Cayley table, is there an algorithm to determine if it is a dihedral group?

Showing that it is a group is simple enough, but is it possible to determine if it is a dihedral group or not just by looking at the Cayley table?

• what am I allowed to look for? If I can check for orders of elements and relations then yes. You can recover any finite group from its Cayley table so I guess you'd have to define looking at the Cayley table first. – rVitale Jun 8 '14 at 20:51
• To be specific, I mean that the only data given is the matrix representation (or 2d array if you prefer) of the Cayley table. I know you can recover any finite group from it's Cayley table, but given a Cayley table of a finite group, how do you tell whether or not it is a dihedral group? – Nathan BeDell Jun 8 '14 at 20:59

Lets assume the group is size $6$ or larger. If the Cayley table is symmetric with respect to the diagonal or has an odd number of elements, then it is not a dihedral group. If the table passed, then it is a $2n$ by $2n$ asymmetric grid. Now assuming our table has passed we can search for an element of order $n$ by repeated self multiplication of each element. If this order $n$ element doesn't exist, then the group is not dihedral. If the table has passed then we must have some element $\rho$ of order $n$, and we can list out all powers of $\rho$. Now search for an element of order 2 which is not in the list of powers of $\rho$. If this doesn't exist then we don't have a dihedral group. If it does, call it $\tau$. Now multiply these generators to get $\tau \rho$ and square the result to get $( \tau\rho)^2$. If that is the identity element then you must have a dihedral group, otherwise you have something else.

This process is maybe not too efficient but it works.

• I would be tempted to count the elements of order $2$ by looking at the diagonal, before checking for an element of order $n$. – David Wheeler Jun 9 '14 at 0:04
• @DavidWheeler I think you're right, that would improve the algorithm – rVitale Jun 9 '14 at 13:52
• Just to clarify, do you mean: " If the table passed it is a 2n by 2n asymmetric grid, search for an element of order n by repeated self multiplication of each element."? You have a few clauses like this, an "if" without a corresponding "then", and it makes your algorithm hard to read. – Nathan BeDell Jun 9 '14 at 14:57
• Let me edit the post and place "then" where I meant to put it. – rVitale Jun 9 '14 at 23:31

Theoretically, yes. If you are given two finite groups in whatever form you want (matrices, permutations, Cayley tables, presentations, whatever) then, so long as you are also told that they are finite, you can determine if they are isomorphic or not. This is because the isomorphism problem for groups is a property of the class of groups (here, finite groups) not of the way you are representing them. The isomorphism problem for finite groups is soluble, and this decidability merely asserts the existence of a Turing machine which can determine if these groups are isomorphic or not.

This is overkill for finite groups (just take the set of all possible maps from your group to the Cayley table and work out if any of them are isomorphisms - it may take a while, but that is okay...) However, the above generalises: If you are given two groups $G$ and $H$ from a class $\mathcal{C}$ such that $\mathcal{C}$ has soluble isomorphism problem and you are told that $G, H\in\mathcal{C}$ then it is possible to determine if $G$ and $H$ are isomorphic, no matter how $G$ and $H$ are given to you.

Note that I said "...so long as you are also told that they are finite..." and "...and you are told that $G, H\in\mathcal{C}$...". This is because you need to know the class of groups you are working with. If you are given two arbitrary groups then it is not possible to determine if they are isomorphic (the isomorphism problem for all groups is insoluble). More concretely, if you are given a presentation $\mathcal{P}$ it is not possible to determine if $\mathcal{P}$ is a presentation of the trivial group. Wowzer!

For more information on the isomorphism problem and other decision problems, see this survey article of Charles Miller III (very long and detailed) or see this post of mine (much shorter and less detailed).