# 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.

• 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 '17 at 18:52
• @Neil Yes; I forgot to specify. Thanks! – HyperNeutrino Sep 24 '17 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 '17 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 '17 at 3:34
• @HyperNeutrino: That's the direct product of the two-element group with itself -- also known as the Klein four-group. – hmakholm left over Monica Sep 25 '17 at 15:47

# 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 – Conor O'Brien Sep 25 '17 at 17:44
• Huh, J beats Jelly‽ – Adám Sep 25 '17 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. – miles Sep 26 '17 at 0:07

# 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.


# Jelly, 13 11 bytes

## 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.