Le groupe est-il cyclique?

21

introduction

Vous pouvez ignorer cette partie si vous savez déjà ce qu'est un groupe cyclique.

Un groupe est défini par un ensemble et une opération binaire associative $(c'est-à-dire (a $ b) $ c = a $ (b $ c). Il existe exactement un élément dans le groupe ea $ e = a = e $ apour tous adans le groupe ( identité ). Pour chaque élément adu groupe, il en existe exactement un btel que a $ b = e = b $ a( inverse ) Pour tous les deux éléments a, bdu groupe, a $ best dans le groupe ( fermeture ).

Nous pouvons écrire a^nà la place de a$a$a$...$a.

Le sous-groupe cyclique généré par n'importe quel élément adu groupe est <a> = {e, a, a^2, a^3, a^4, ..., a^(n-1)}nest l'ordre (taille) du sous-groupe (sauf si le sous-groupe est infini).

Un groupe est cyclique s'il peut être généré par l'un de ses éléments.

Défi

Étant donné la table Cayley (tableau des produits) pour un groupe fini, déterminez si elle est cyclique ou non.

Exemple

Jetons un coup d'œil au tableau Cayley suivant:

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

(Il s'agit du tableau de Cayley pour le groupe dièdre 3, D_3).

Ceci est indexé sur 1, donc si nous voulons trouver la valeur de 5 $ 3, nous regardons dans la cinquième colonne de la troisième ligne (notez que l'opérateur n'est pas nécessairement commutatif, donc 5 $ 3n'est pas nécessairement égal à 3 $ 5. Nous voyons ici que 5 $ 3 = 6(aussi que 3 $ 5 = 4).

On peut trouver <3>en commençant par [3], puis alors que la liste est unique, ajouter le produit du dernier élément et le générateur (3). Nous obtenons [3, 3 $ 3 = 2, 2 $ 3 = 1, 1 $ 3 = 3]. Nous nous arrêtons ici avec le sous-groupe {3, 2, 1}.

Si vous calculez à <1>travers <6>vous verrez qu'aucun des éléments du groupe génèrent tout le groupe. Ainsi, ce groupe n'est pas cyclique.

Cas de test

L'entrée sera donnée sous forme de matrice, la sortie sous forme de valeur de décision véridique / fausse.

[[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)

Vous serez assuré que l'entrée est toujours un groupe.

Vous pouvez prendre l'entrée comme des valeurs indexées 0.

HyperNeutrino
la source
L'entrée indexée sur 0 est-elle autorisée? (par exemple [[0,1,2,3],[1,2,3,0],[2,3,0,1],[3,0,1,2]])?
Neil
@Neil Oui; J'ai oublié de préciser. Merci!
HyperNeutrino
5
Vous devriez prémuter davantage les étiquettes de vos éléments de groupe dans les cas de test. À l'heure actuelle, la première ligne et colonne du tableau est toujours [1..n]ce qui peut cacher des défauts dans certaines réponses.
Lynn,
3
Cela ressemble à vérifier si le groupe est abélien suffit pour passer les cas de test. Des cas de test comme Z_2 * Z_2 pourraient résoudre ce problème.
xnor
2
@HyperNeutrino: C'est le produit direct du groupe à deux éléments avec lui-même - également connu sous le nom de groupe à quatre Klein .
Henning Makholm

Réponses:

8

J , 8 octets

1:e.#@C.

Essayez-le en ligne!

Explication

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?
miles
la source
Cela pourrait aussi être 1 e.#@C., fwiw
Conor O'Brien
Huh, J bat Jelly‽
Adám
@ Adám Jelly n'a pas de fonction intégrée pour convertir les permutations entre la notation directe et la notation cyclique. Je pourrais probablement les ajouter sous forme d'atomes plus tard, ce qui donne ŒCL€1e6 octets dans Jelly.
miles
8

Husk , 11 10 9 octets

VS≡`ȯU¡!1

1 basé. Renvoie l'index d'un générateur s'il existe, 0 sinon. Essayez-le en ligne!

Explication

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.
Zgarb
la source
3

JavaScript (ES6), 52 octets

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

Python 2 , 96 91 97 octets

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)

Essayez-le en ligne!

Halvard Hummel
la source
or 1+g-> or-~g.
Jonathan Frech
2

Gelée , 15 octets

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

Essayez-le en ligne!

Première idée idiote qui m'est venue à l'esprit: vérifier l'isomorphisme de Z n . (Ce code est 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]]
Lynn
la source
Huh c'est une approche intéressante; jamais pensé à ça! +1
HyperNeutrino
2

R , 101 97 octets

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

Vérifier tous les cas de test

Cela calcule simplement <g>pour chacun g \in G, puis teste si G \subseteq <g>, puis vérifie si certains d'entre eux sont vrais. Cependant, puisque nous appliquons toujours $gà droite, nous répliquons m[g,](la gtroisième ligne) puis indexons dans cette ligne avec le résultat de l'application $g, en accumulant les résultats plutôt qu'en les utilisant à m[g,g$g]chaque fois, ce qui a permis d'économiser environ 4 octets.

Giuseppe
la source
1

Clojure, 68 octets

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

Python 2 , 82 octets

lambda A:len(A)in[len(set(reduce(lambda a,c:a+[A[a[-1]][n]],A,[n])))for n in A[0]]

Essayez-le en ligne!

La table Cayley indexée 0 est entrée; Sortie vrai / faux pour le groupe cyclique / non cyclique.

Chas Brown
la source