Is the group cyclic?

Question

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 $ (that is, (a $ b) $ c = a $ (b $ c). There exists exactly one element in the group e where a $ e = a = e $ a for all a in the group (identity). For every element a in the group there exists exactly one b such that a $ b = e = b $ a (inverse). For every two elements a, b in the group, a $ b is in the group (closure).

We can write a^n in place of a$a$a$...$a.

The cyclic subgroup generated by any element a in the group is <a> = {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 $ 3, we look in the fifth column on the third row (note that the operator is not necessarily commutative, so 5 $ 3 is not necessarily equal to 3 $ 5. We see here that 5 $ 3 = 6 (also that 3 $ 5 = 4).

We can find <3> 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 $ 3 = 2, 2 $ 3 = 1, 1 $ 3 = 3]. We stop here with the subgroup {3, 2, 1}.

If you compute <1> through <6> 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.

Answer 1

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.

Answer 2

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?

Answer 3

Jelly, 13 11 bytes

ị"⁸$ÐĿ«/E€Ẹ

Try it online!

Answer 4

JavaScript (ES6), 52 bytes

a=>a.some(b=>!a[new Set(a.map(_=>r=b[r],r=0)).size])

Answer 5

Python 2, 96 91 97 bytes

lambda x:any(g(r,r[i],i+1)==len(r)for i,r in enumerate(x))
g=lambda x,y,z:y==z or 1+g(x,x[y-1],z)

Try it online!

Answer 6

Jelly, 15 bytes

JŒ!ị@€µṂ⁼Jṙ'’$$

Try it online!

First silly idea that came to mind: check for isomorphism to Z_n. (This code is O(n!)…)

JŒ!ị@€             Generate all ways to denote this group.
                     (by indexing into every permutation of 1…n)
      µṂ⁼          Is the smallest one equal to this?
         Jṙ'’$$      [[1 2 …  n ]
                      [2 3 …  1 ]    (the group table for Z_n)
                      [… … …  … ]
                      [n 1 … n-1]]

Answer 7

R, 101 97 bytes

function(m)any(sapply(1:(n=nrow(m)),function(x)all(1:n%in%Reduce(`[`,rep(list(m[x,]),n),x,T,T))))

Verify all test cases

This simply computes <g> for each g \in G and then tests if G \subseteq <g>, then checks if any of those are true. However, since we're always applying $g on the right, we replicate m[g,] (the gth row) and then index into that row with the result of applying $g, accumulating the results rather than using m[g,g$g] every time, which saved about 4 bytes.

Answer 8

Clojure, 68 bytes

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

Answer 9

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.