# 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. – Henning Makholm Sep 25 '17 at 15:47

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

# 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. # 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 – 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 # Jelly, 13 11 bytes ị"⁸$ÐĿ«/E€Ẹ


Try it online!

## Clojure, 68 bytes

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


# Python 2, 9691 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!

• or 1+g -> or-~g. – Jonathan Frech Sep 25 '17 at 3:10

# Jelly, 15 bytes

JŒ!ị@€µṂ⁼Jṙ'’$$ Try it online! First silly idea that came to mind: check for isomorphism to Zn. (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]]

• Huh this is an interesting approach; never thought of that! +1 – HyperNeutrino Sep 24 '17 at 19:51

## JavaScript (ES6), 52 bytes

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