21
\$\begingroup\$

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.

\$\endgroup\$
  • \$\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 '17 at 18:52
  • \$\begingroup\$ @Neil Yes; I forgot to specify. Thanks! \$\endgroup\$ – HyperNeutrino Sep 24 '17 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 '17 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 '17 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\$ – Henning Makholm Sep 25 '17 at 15:47
8
\$\begingroup\$

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

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.
\$\endgroup\$
4
\$\begingroup\$

Jelly, 13 11 bytes

ị"⁸$ÐĿ«/E€Ẹ

Try it online!

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 52 bytes

a=>a.some(b=>!a[new Set(a.map(_=>r=b[r],r=0)).size])
\$\endgroup\$
3
\$\begingroup\$

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!

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

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

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.

\$\endgroup\$
1
\$\begingroup\$

Clojure, 68 bytes

#(seq(for[l % :when(apply distinct?(take(count l)(iterate l 0)))]l))
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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