Introduction

You can skip this part if you already know what a cyclic group is.

A group is defined by a set and an associative binary operation $$\\times\$$ (that is, $$\(a \times b) \times c = a \times (b \times c)\$$. There exists exactly one element in the group $$\e\$$ where $$\a \times e = a = e \times a\$$ for all $$\a\$$ in the group (identity). For every element $$\a\$$ in the group there exists exactly one $$\b\$$ such that $$\a \times b = e = b \times a\$$ (inverse). For every two elements $$\a, b\$$ in the group, $$\a \times b\$$ is in the group (closure).

We can write $$\a^n\$$ in place of $$\\underbrace{a\times a\times a\times ...\times a}_{n \text{ times}}\$$.

The cyclic subgroup generated by any element $$\a\$$ in the group is $$\\langle a \rangle = \{e, a, a^2, a^3, a^4, ..., a^{n-1}\}\$$ where $$\n\$$ is the order (size) of the subgroup (unless the subgroup is infinite).

A group is cyclic if it can be generated by one of its elements.

Challenge

Given the Cayley table (product table) for a finite group, determine whether or not it's cyclic.

Example

Let's take a look at the following Cayley table:

1 2 3 4 5 6
2 3 1 6 4 5
3 1 2 5 6 4
4 5 6 1 2 3
5 6 4 3 1 2
6 4 5 2 3 1


(This is the Cayley table for Dihedral Group 3, $$\D_3\$$).

This is 1-indexed, so if we want to find the value of $$\5 \times 3\$$, we look in the fifth column on the third row (note that the operator is not necessarily commutative, so $$\5 \times 3\$$ is not necessarily equal to $$\3 \times 5\$$. We see here that $$\5 \times 3 = 6\$$ (also that $$\3 \times 5 = 4\$$).

We can find $$\\langle 3 \rangle\$$ by starting with $$\[3]\$$, and then while the list is unique, append the product of the last element and the generator ($$\3\$$). We get $$\[3, 3 \times 3 = 2, 2 \times 3 = 1, 1 \times 3 = 3]\$$. We stop here with the subgroup $$\\{3, 2, 1\}\$$.

If you compute $$\\langle 1 \rangle\$$ through $$\\langle 6 \rangle\$$ you'll see that none of the elements in the group generate the whole group. Thus, this group is not cyclic.

Test Cases

Input will be given as a matrix, output as a truthy/falsy decision value.

[[1,2,3,4,5,6],[2,3,1,6,4,5],[3,1,2,5,6,4],[4,5,6,1,2,3],[5,6,4,3,1,2],[6,4,5,2,3,1]] -> False (D_3)
[[1]] -> True ({e})
[[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3]] -> True ({1, i, -1, -i})
[[3,2,4,1],[2,4,1,3],[4,1,3,2],[1,3,2,4]] -> True ({-1, i, -i, 1})
[[1,2],[2,1]] -> True ({e, a} with a^-1=a)
[[1,2,3,4,5,6,7,8],[2,3,4,1,6,7,8,5],[3,4,1,2,7,8,5,6],[4,1,2,3,8,5,6,7],[5,8,7,6,1,4,3,2],[6,5,8,7,2,1,4,3],[7,6,5,8,3,2,1,4],[8,7,6,5,4,3,2,1]] -> False (D_4)
[[1,2,3,4,5,6],[2,1,4,3,6,5],[3,4,5,6,1,2],[4,3,6,5,2,1],[5,‌​6,1,2,3,4],[6,5,2,1,‌​4,3]] -> True (product of cyclic subgroups of order 2 and 3, thanks to Zgarb)
[[1,2,3,4],[2,1,4,3],[3,4,1,2],[4,3,1,2]] -> False (Abelian but not cyclic; thanks to xnor)


You will be guaranteed that the input is always a group.

You may take input as 0-indexed values.

• Is 0-indexed input allowed? (e.g. [[0,1,2,3],[1,2,3,0],[2,3,0,1],[3,0,1,2]])?
– Neil
Sep 24, 2017 at 18:52
• @Neil Yes; I forgot to specify. Thanks! Sep 24, 2017 at 18:52
• You should premute the labels of your group elements more in the test cases. Right now the first row and column of the table is always [1..n] which may be hiding flaws in some answers.
– lynn
Sep 24, 2017 at 19:51
• It looks like checking if the group is abelian suffices to pass the test cases. Test cases like Z_2 * Z_2 would fix this.
– xnor
Sep 25, 2017 at 3:34
• @HyperNeutrino: That's the direct product of the two-element group with itself -- also known as the Klein four-group. Sep 25, 2017 at 15:47

Husk, 11 10 9 bytes

VS≡ȯU¡!1


1-based. Returns the index of a generator if one exists, 0 otherwise. Try it online!

Explanation

V          Does any row r of the input satisfy this:
¡!    If you iterate indexing into r
1   starting with 1
ȯU      until a repetition is encountered,
S≡         the result has the same length as r.


J, 8 bytes

1:e.#@C.


Try it online!

Explanation

1:e.#@C.  Input: matrix M
C.  Convert each row from a permutation to a list of cycles
#@    Number of cycles in each row
1:        Constant function 1
e.      Is 1 a member of the cycle lengths?

• This could also be 1 e.#@C., fwiw Sep 25, 2017 at 17:44
• Huh, J beats Jelly‽
Sep 25, 2017 at 23:55
• @Adám Jelly doesn't have a builtin to convert permutations between direct and cycle notation. I could probably add them as atoms later, making ŒCL€1e for 6 bytes in Jelly. Sep 26, 2017 at 0:07

Jelly, 8 bytes

JịƬ"ZẈiL


Try it online!

Outputs 0 for False and a non-negative integer for True

Jelly finally ties J!

How it works

JịƬ"ZẈiL - Main link. Takes the Cayley matrix n×n M on the left
Z    - Transpose M
J        - Yield [1, 2, ..., n]
Ƭ      - Until reaching a fixed point, do the following and replace i with the result
"     -   Pair each i (intially 1,2...,n) with each row, then do the following:
ị       -     Take the i'th element of each row
Ẉ   - Get the length of each
L - Yield n
i  - Index of n in the lengths, or 0 if not present


Clojure, 68 bytes

#(seq(for[l % :when(apply distinct?(take(count l)(iterate l 0)))]l))


Python 2, 82 bytes

lambda A:len(A)in[len(set(reduce(lambda a,c:a+[A[a[-1]][n]],A,[n])))for n in A[0]]


Try it online!

0-indexed Cayley table is input; True/False output for cyclic/non-cyclic group.

JavaScript (Node.js), 42 bytes

a=>a.some(b=>a.every(r=z=>r=1/r?b[r]:[0]))


Try it online!

Starting from element 0, go n-1 steps, if 0 never appear

Zsh, 72 bytes

Input each row as a separate argument; rows are space-delimited. Exits 0 if cyclic, 1 otherwise.

for r;(set $=r x=($1)
for i;x+=($@[x[-1]]) x=(${(u)x})
(($#==$#x)))&&bye


Try it online!

Explanation:

for r;                # for each row
(                     # In subshell:
set $=r # split row on spaces, set as ARGV x=($1)              #   initialize $x with the first element for i x+=($@[x[-1]])  #   use $x[-1] as the index, add that element to$x
x=(${(u)x}) # remove duplicates from$x
(($#==$#x))         #   Compare length of $@ with length of$x
) && bye              # If subshell exited true, early-exit whole program true
# If we haven't early-exited by the end of the program,
# the exit code would be 1 (falsy) since the last loop
# had no generator, and therefore returned 1.