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.


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


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.

  • \$\begingroup\$ Is 0-indexed input allowed? (e.g. [[0,1,2,3],[1,2,3,0],[2,3,0,1],[3,0,1,2]])? \$\endgroup\$
    – Neil
    Sep 24, 2017 at 18:52
  • \$\begingroup\$ @Neil Yes; I forgot to specify. Thanks! \$\endgroup\$
    – hyper-neutrino
    Sep 24, 2017 at 18:52
  • 5
    \$\begingroup\$ 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. \$\endgroup\$
    – lynn
    Sep 24, 2017 at 19:51
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – xnor
    Sep 25, 2017 at 3:34
  • 2
    \$\begingroup\$ @HyperNeutrino: That's the direct product of the two-element group with itself -- also known as the Klein four-group. \$\endgroup\$ Sep 25, 2017 at 15:47

12 Answers 12


Husk, 11 10 9 bytes


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


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


Try it online!


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?
  • \$\begingroup\$ This could also be 1 e.#@C., fwiw \$\endgroup\$ Sep 25, 2017 at 17:44
  • \$\begingroup\$ Huh, J beats Jelly‽ \$\endgroup\$
    – Adám
    Sep 25, 2017 at 23:55
  • \$\begingroup\$ @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. \$\endgroup\$
    – miles
    Sep 26, 2017 at 0:07

Jelly, 13 11 bytes


Try it online!


JavaScript (ES6), 52 bytes

a=>a.some(b=>!a[new Set(a.map(_=>r=b[r],r=0)).size])
  • \$\begingroup\$ Test with group \$D_3\$ but it outputs true \$\endgroup\$
    – atzlt
    Feb 20, 2021 at 6:33
  • \$\begingroup\$ @SketchySketch Sorry, I should have mentioned that this answer is 0-indexed. \$\endgroup\$
    – Neil
    Feb 20, 2021 at 8:25

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!

  • 1
    \$\begingroup\$ or 1+g -> or-~g. \$\endgroup\$ Sep 25, 2017 at 3:10

Jelly, 15 bytes


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]]
  • \$\begingroup\$ Huh this is an interesting approach; never thought of that! +1 \$\endgroup\$
    – hyper-neutrino
    Sep 24, 2017 at 19:51

R, 101 97 bytes


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.


Jelly, 8 bytes


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


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
for i;x+=($@[x[-1]])

Try it online!


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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.