ASKSAGE: Sage Q&A Forum - Latest question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 05 Aug 2019 08:51:11 -0500How to draw a graph whose vertices are elements of permutation grouphttp://ask.sagemath.org/question/47395/how-to-draw-a-graph-whose-vertices-are-elements-of-permutation-group/How to write the following program in SageMath:
Consider the Permutation Group $S_3$.
The elements of $S_3$ are $e,(12),(13),(23),(123),(132)$.
I want to draw a graph $G$ whose members are the elements of $S_3$ and two vertices $x,y$ are adjacent if and only if $xy\neq yx$.
I am stuck in doing the following things:
1. How to call the elements of $S_3$ through a loop?
2. How to draw the graph $G$ ?
I can check whether they commute or not but I am stuck in the two things.
Is there any way to write the code in SageMath?
As an example if I input $S_3$ I want to get the following graph
$G=Graph({1:[2,3,4,5],2:[1,3,4,5],3:[1,2,4,5],4:[1,2,3],5:[1,2,3]})$
Any help will be highly appreciated.CaptchaMon, 05 Aug 2019 08:51:11 -0500http://ask.sagemath.org/question/47395/Automorphism group of edge symmetryhttp://ask.sagemath.org/question/47334/automorphism-group-of-edge-symmetry/ I asked a similar question before,
https://ask.sagemath.org/question/42762/automorphism-group-of-weighted-graph/
I am curious that is there any similar function for finding "edge symmetry"?
Note: the link I provided is for "node symmetry" in a network (graph). sleeve chenThu, 01 Aug 2019 04:21:31 -0500http://ask.sagemath.org/question/47334/Automorphism group of weighted graphhttp://ask.sagemath.org/question/42762/automorphism-group-of-weighted-graph/I know we can use sage to find the group of automorphisms of a graph $G$:
G.automorphism_group().list()
However, the above way can only be used to the unweighted graph. So for example:
G = matrix([[0,10,0],
[10,0,1],
[0,1,0]])
G1 = Graph(G, weighted = True)
G1.show(edge_labels=True )
G.automorphism_group().list()
The result is:
[(), (0,2)]
However, this result is not correct (correct for unweighted case). This is because $AD\neq DA$, where
$$D = \begin{bmatrix} 0 & 0 & 1 \\\ 0 & 1 & 0 \\\ 1 & 0 & 0\end{bmatrix},$$ which is a permutation matrix and
$$A = \begin{bmatrix} 0 & 10 & 0 \\\ 10 & 0 & 1 \\\ 0 & 1 & 0\end{bmatrix},$$ which is an adjacency matrix.
Can we use SAGE to find the group of automorphisms of a graph?sleeve chenWed, 27 Jun 2018 20:22:14 -0500http://ask.sagemath.org/question/42762/does as_permutation_group() respect generators?http://ask.sagemath.org/question/40927/does-as_permutation_group-respect-generators/From sage documentation I can construct a group as follows:
sage: m1 = matrix(GF(11), [[1,2],[3,4]])
sage: m2 = matrix(GF(11), [[1,3],[10,0]])
sage: G = MatrixGroup(m1, m2); G
Matrix group over Finite Field of size 11 with 2 generators (
[1 2] [ 1 3]
[3 4], [10 0]
)
Now I use the following code:
sage: G_p=G.as_permutation_group(); G_p
Permutation Group with generators [(1,2,3,4,5,6,7,8,9,10,11)(12,13,15,14,16)(17,18), (1,3,5,7,9,11,2,4,6,8,10)(12,14,13,16,15)(17,18)]
In this case it is true that the generators of G are in correspondence with the generators of G_p. Is this always the case? I mean, if I compute a very complicated group G with lots of generators and its corresponding permutation group G_p, then is it true that G.gens()[i] corresponds to G_p.gens[i]?amontero90Thu, 01 Feb 2018 13:20:47 -0600http://ask.sagemath.org/question/40927/Is there a way to relabel the domain of a permutation group?http://ask.sagemath.org/question/36592/is-there-a-way-to-relabel-the-domain-of-a-permutation-group/ Suppose I have a permutation group on the domain {1,2,3,4,5}, but instead I wanted this permutation group to be on the domain {a,b,c,d,e}. Is there a way to achieve this? Hopefully something like the `relabel` method for graphs...jaebondSun, 12 Feb 2017 19:12:31 -0600http://ask.sagemath.org/question/36592/Faster function for working with cosetshttp://ask.sagemath.org/question/34220/faster-function-for-working-with-cosets/I would like to get the cosets of a non-normal subgroup and in the documentation for the `.cosets()` method here:
[PermutationGroup_generic.cosets](http://doc.sagemath.org/html/en/reference/groups/sage/groups/perm_gps/permgroup.html#sage.groups.perm_gps.permgroup.PermutationGroup_generic.cosets)
there is a **Note:** that says
>Sage and GAP provide more sophisticated functions for working quickly with cosets of larger groups.
but doesn't mention what these functions are. I was hoping that someone could point me to these functions.
If it makes a difference, I want to iterate over a set of coset representatives and it will all be done in a permutation group.jaebondMon, 25 Jul 2016 11:49:42 -0500http://ask.sagemath.org/question/34220/How do I implement a Gap function I wrote in a gap cell in cloudsage?http://ask.sagemath.org/question/27154/how-do-i-implement-a-gap-function-i-wrote-in-a-gap-cell-in-cloudsage/I have written the following code in a cell:
%gap
OnChains:= function( c, g )
local i, k;
for i in [1..Length(c)] do
k[i] := OnSetsSets(c[i], g);
od;
return k;
end;
But when I try and run
G.orbit(Set(K[0]), action = "OnChains")
in a sage cell, I get:
Error in lines 1-1
Traceback (most recent call last):
File "/projects/b5d3c63b-a07d-41ae-905b-350044f6bb95/.sagemathcloud/sage_server.py", line 879, in execute
exec compile(block+'\n', '', 'single') in namespace, locals
File "", line 1, in <module>
File "sage/misc/cachefunc.pyx", line 1896, in sage.misc.cachefunc.CachedMethodCaller.__call__ (build/cythonized/sage/misc/cachefunc.c:11488)
w = self._cachedmethod._instance_call(self._instance, *args, **kwds)
File "sage/misc/cachefunc.pyx", line 2552, in sage.misc.cachefunc.CachedMethod._instance_call (build/cythonized/sage/misc/cachefunc.c:14934)
return self._cachedfunc.f(inst, *args, **kwds)
File "/projects/sage/sage-6.7/local/lib/python2.7/site-packages/sage/groups/perm_gps/permgroup.py", line 1208, in orbit
raise NotImplementedError("This action is not implemented (yet?).")
NotImplementedError: This action is not implemented (yet?).
Can someone help me implement my custom group action?
ChetakThu, 18 Jun 2015 16:11:45 -0500http://ask.sagemath.org/question/27154/Why the function .cardinality() doesnt work with a permutation group ?http://ask.sagemath.org/question/27127/why-the-function-cardinality-doesnt-work-with-a-permutation-group/ I have acode that use to run very good, but I dont know why no longer the basic functions works for my permutation groups, i.e Abelian, cardinality, order. Only degree seems to workhbanosWed, 17 Jun 2015 01:05:34 -0500http://ask.sagemath.org/question/27127/Add generator to a group? Combine generators of two groups?http://ask.sagemath.org/question/26590/add-generator-to-a-group-combine-generators-of-two-groups/Hi guys, I am wondering how to efficiently do the following two things in Sage
1. add a generator h to a existing group G to create a new group, e.g. from
sage: h = (3,4)
sage: G = PermutationGroup([(1,2),(1,3)])
how to get a new group N with generators [(1,2),(1,3),(3,4)].
I can do this by using `G.gens()` and adding `(3,4)` to the list and calling `PermutationGroup()`,
but it looks awkward, is there a more efficient way?
2. create a new group from generators of two existing group, e.g. from
sage: G = PermutationGroup([(1,2),(1,3)])
sage: H = PermutationGroup([(3,4)])
how to get a new group N with generators [(1,2),(1,3),(3,4)]?
Currently I can do this by : `N = PermutationGroup(G.gens()+H.gens())`
Thanks,
KevinskylibrarySat, 18 Apr 2015 15:50:47 -0500http://ask.sagemath.org/question/26590/Trouble importing groups from GAPhttp://ask.sagemath.org/question/24674/trouble-importing-groups-from-gap/I would like to use groups from the GAP library in Sage; something like:
sage: L = gap.AllGroups(16)
sage: G = PermutationGroup(gap_group = L[1])
and use `G` in my sage code. But I must be doing something wrong, becuase I get:
---------------------------------------------------------------------------
NameError Traceback (most recent call last)
<ipython-input-32-14053049143a> in <module>()
----> 1 G = PermutationGroup(gap_group = L[Integer(1)])
/home/amri/sage-6.4.beta4/local/lib/python2.7/site-packages/sage/groups/perm_gps/permgroup.pyc in PermutationGroup(gens, gap_group, domain, canonicalize, category)
335 raise TypeError("gens must be a tuple, list, or GapElement")
336 return PermutationGroup_generic(gens=gens, gap_group=gap_group, domain=domain,
--> 337 canonicalize=canonicalize, category=category)
338
339
/home/amri/sage-6.4.beta4/local/lib/python2.7/site-packages/sage/groups/perm_gps/permgroup.pyc in __init__(self, gens, gap_group, canonicalize, domain, category)
404
405 if domain is None:
--> 406 gens = [standardize_generator(x) for x in gens]
407 domain = set()
408 for x in gens:
/home/amri/sage-6.4.beta4/local/lib/python2.7/site-packages/sage/groups/perm_gps/permgroup_element.so in sage.groups.perm_gps.permgroup_element.standardize_generator (build/cythonized/sage/groups/perm_gps/permgroup_element.c:3761)()
/home/amri/sage-6.4.beta4/local/lib/python2.7/site-packages/sage/groups/perm_gps/permgroup_element.so in sage.groups.perm_gps.permgroup_element.string_to_tuples (build/cythonized/sage/groups/perm_gps/permgroup_element.c:3362)()
/home/amri/sage-6.4.beta4/local/lib/python2.7/site-packages/sage/misc/sage_eval.pyc in sage_eval(source, locals, cmds, preparse)
197 return locals['_sage_eval_returnval_']
198 else:
--> 199 return eval(source, sage.all.__dict__, locals)
200
201
/home/amri/sage-6.4.beta4/local/lib/python2.7/site-packages/sage/all.pyc in <module>()
NameError: name 'f1' is not defined
What is the correct way to do this?AmriWed, 29 Oct 2014 03:22:29 -0500http://ask.sagemath.org/question/24674/Testing if a group has a subgroup acting regularlyhttp://ask.sagemath.org/question/10879/testing-if-a-group-has-a-subgroup-acting-regularly/I am given a PermuationGroup $G$ and would like to find out if $G$ has a subgroup $H$ that acts regularly. The insane way to do it is of course to iterate over all subgroups of $G$ of size of the acting set and testing for regularity.
My question is - is there a more efficient way to do this?
Best,
JernejJernejFri, 03 Jan 2014 01:51:53 -0600http://ask.sagemath.org/question/10879/Computing permutationshttp://ask.sagemath.org/question/10790/computing-permutations/Is there a way to solve the following question is Sage? I have symmetric group $S_8$ and its elements $a=(x_1 x_2)(x_3 x_4),b=(x_5 x_6), c=(x_7 x_8)(x_9 x_{10})(x_{11} x_{12})(x_{13} x_{14})$ Here of course we might have $x_i=x_j$ if $i\ne j$. Is some given $(y_1 y_2)\in \langle a,b,c\rangle$?Jaakko SeppäläTue, 03 Dec 2013 09:41:38 -0600http://ask.sagemath.org/question/10790/Force Gap to forget graph automorphism groupshttp://ask.sagemath.org/question/10389/force-gap-to-forget-graph-automorphism-groups/I'm interested in computing and storing a huge number of graphs. For each graph I compute, I temporarily need to compute its automorphism group -- but I don't need to, and don't want to, remember that automorphism group. It looks like sage deals with graphs on its own but calls Gap to deal with automorphism groups.
The problem is that Gap, not sage, exceeds it permitted memory. Why? Here is a (silly) example of what I'm talking about: running
mylist=[];
count = 1;
while True:
g = graphs.RandomGNP(6, .5);
aut = g.automorphism_group();
mylist.append(g);
if aut.order() > 1:
print "Graph number %s has nontrivial automorphisms!"%(count);
count += 1;
gives me after some hours
RuntimeError: Gap produced error output
Error, exceeded the permitted memory (`-o' command line option)
How can I force sage/gap to forget the automorphism groups attached to the graphs (but remember the graphs)? Ideally Gap should only need to store one automorphism group at a time.MTFri, 26 Jul 2013 02:43:43 -0500http://ask.sagemath.org/question/10389/Writing a given permutaion as a product of generatorshttp://ask.sagemath.org/question/10267/writing-a-given-permutaion-as-a-product-of-generators/Suppose that I have a group generated by three elements (written in cycle notation). I know that Sage will find all of the elements of this group.
What I need is to be able to write a given permutation as a product of these generators.
Any ideas?
For refernce, I am working in S_16. My generators are a=(13,14,15,16), b=(1,2,3,4)(5,6,7,8)(9,10,11,12), and c=(1,5,9,13,12,8,4). I want to "factor" (1,2) and (1,5) as a product of a,b,c.CharyonFri, 21 Jun 2013 03:35:43 -0500http://ask.sagemath.org/question/10267/Orbits on group actions acting on setshttp://ask.sagemath.org/question/9652/orbits-on-group-actions-acting-on-sets/Hello!
I am wondering how to solve the following problem efficiently.
I have a Permuation Group $G$ acting on $A = \{1,\ldots,n\}$ and I wish to compute the orbits of $G$ but not the ones of $G$ acting on $A$ but rather for $G$ acting on some $S \subseteq A \times A$ in the natural way. That is if $g \in G$ and $ x = \{a,b\} \in S$ then $x^g = {a^g,b^g\} \in S$
Other software for permuation groups (magma, gap) allows to do this by specifing an additional option "on sets/on tuples" to compute the specifed orbits.
I am wondering how could I do the same in sage, given a permuation group $G$ and an $S$ as described above.
Thanks!SGQWed, 26 Dec 2012 03:56:11 -0600http://ask.sagemath.org/question/9652/A faster way to obtain orbits of a partition of the verrtex sethttp://ask.sagemath.org/question/9660/a-faster-way-to-obtain-orbits-of-a-partition-of-the-verrtex-set/I am given a graph $G$ a set $S \subseteq V(G)$ and a vertex $v.$ I want to compute the representatives for the orbits of the stabilizer of $v$ of $\rm{Aut}(G)$ whose equivalence classes contain elements of $S.$ Currently what I am doing is the following:
<pre>
def compute_valid_orbit_reps(G,S,v):
ret = []
O = G.automorphism_group(return_group=False, orbits=True,
partition=[ [v], [el for el in G.vertices() if el != v]])
for el in O:
if S.intersection(set(el)):
nb = el[0]
G.add_edge(nb,v)
if G.girth() >= 5:
ret += [nb]
G.delete_edge(nb,v)
return ret
</pre>
I am wondering if there is a more efficient way to do the same, perhaps using GAP directly?
Best,
JernejJernejSat, 29 Dec 2012 02:44:09 -0600http://ask.sagemath.org/question/9660/Does Sage keep the order of vertices in a graph and it's group or scramble them? For me it sometime scrambles them.http://ask.sagemath.org/question/9315/does-sage-keep-the-order-of-vertices-in-a-graph-and-its-group-or-scramble-them-for-me-it-sometime-scrambles-them/I use the Sage automorphism_group function to find the group that leaves an adjacency matric, say C, invariant under a similarity transformation. But sometimes it seems the results are for matrices on a vertex space that is not the same as the original, but is reordered.
A simple example on a 3-vertex graph: o--o--o.
with index order 1 0 2
Adjacency matrix= C =
[0 1 1]
[1 0 0]
[1 0 0]
The group is the identity and a reflection about the center vertex:
[1 0 0] [0 1 0]
[0 1 0] and [1 0 0] = R
[0 0 1] [0 0 1]
I would have expected the reflection to be,
[1 0 0]
[0 0 1]
[0 1 0],
but R is what Sage gives.
Sure enough, RCR^-1 gives the following,
[0 1 0]
[1 0 1]
[0 1 0]
which is *not* the original C matrix. However the R transformation leaves the matrix
[0 0 1]
[0 0 1] = C'
[1 1 0]
invariant. The last matrix is the C matrix where the vertices are indexed in reverse order.
Does Sage have some canonical way it orders the vertices in graphs and groups?
A bit more info, maybe. The order of the irreducible representation table seems to give a hint. If the trivial representation is the first row (which it is for some graphs), it appears (from a few tests) that the vertices retain their original order to align with C. If the trivial representation is the last row then the matrix C' is the adjacency matrix (suggesting a reordering of the vertices). I have no idea why this should be related if it is.
Bottom line for me is I cannot apply any matrices from the group that come from the matrix() method to C or other objects in my original vertex space since they are ordered differently. I don't see how to find the vertex order sage uses. Any help or insight appreciated.
LouChaosWed, 12 Sep 2012 05:20:15 -0500http://ask.sagemath.org/question/9315/Order of Irreducible Representation Characters wrong in Sage?http://ask.sagemath.org/question/9300/order-of-irreducible-representation-characters-wrong-in-sage/I am using Sage to calculate Irreducible Representations (IRR) of symmetry groups of graphs. Most of the time the order of the IRR characters match the order of the conjugacy class representatives. For example the trivial representation characters are the first row of the character table (1,1,1,1,...,1) and the first conjugacy class is ( ), the identity representation. But in the example below for a star graph (one central vertex, the 4 other vertices on spokes from the center) the trivial representation characters are the *last* row in the character table and the conjugacy class representatives have the identity as the *first* element.
Example (star graph).
ct=G.character_table()
print ct
[ 1 -1 1 1 -1]
[ 3 -1 -1 0 1]
[ 2 0 2 -1 0]
[ 3 1 -1 0 -1]
[ 1 1 1 1 1] <--- trivial rep. is last
cc=G.conjugacy_classes_representatives()
print cc
[(), (1,2), (1,2)(3,4), (1,2,3), (1,2,3,4)]
^ trivial class is first
Is this a bug or known issue for Sage? How can I get around it so I know the orders of the characters and representatives match up properly?
LouChaosThu, 06 Sep 2012 04:04:45 -0500http://ask.sagemath.org/question/9300/How to use elements of cartesian product of two groups?http://ask.sagemath.org/question/9306/how-to-use-elements-of-cartesian-product-of-two-groups/I want to have a group G = Sym(4) x Sym(4).
I try this to define G:
" G = CartesianProduct([SymmetricGroup(4)] , [SymmetricGroup(4)]) "
Thank you for help.FastfootSat, 08 Sep 2012 08:47:13 -0500http://ask.sagemath.org/question/9306/Can't thread with permutation groups?http://ask.sagemath.org/question/7510/cant-thread-with-permutation-groups/I'm having trouble running threads involving permutation groups. Here is a small example that shows the issue on Sage 5.2 (and also Sage 4.8).
import time
from threading import Thread
class f(Thread):
def __init__(self,val):
Thread.__init__(self)
self.val=val
def run(self):
G=CyclicPermutationGroup(self.val)
print 'here'
print G
a=f(4)
b=f(4)
a.start()
b.start()
a.join()
b.join()
The "here"s print but then the worksheet (usually) just keeps running without doing anything and refuses to be interrupted, or (sometimes) crashes and offers error messages such as
Exception in thread Thread-2:
Traceback (most recent call last):
File "/sagenb/sage_install/sage-5.2-sage.math.washington.edu-x86_64-Linux/local/lib/python/threading.py", line 551, in __bootstrap_inner
self.run()
File "/tmp/tmp4JA7Av/___code___.py", line 14, in run
print G
File "sage_object.pyx", line 154, in sage.structure.sage_object.SageObject.__repr__ (sage/structure/sage_object.c:1753)
File "/sagenb/sage_install/sage-5.2-sage.math.washington.edu-x86_64-Linux/local/lib/python2.7/site-packages/sage/groups/perm_gps/permgroup_named.py", line 436, in _repr_
return "Cyclic group of order %s as a permutation group"%self.order()
File "/sagenb/sage_install/sage-5.2-sage.math.washington.edu-x86_64-Linux/local/lib/python2.7/site-packages/sage/groups/perm_gps/permgroup.py", line 1400, in order
if not self.gens() or self.gens() == [self(1)]:
File "/sagenb/sage_install/sage-5.2-sage.math.washington.edu-x86_64-Linux/local/lib/python2.7/site-packages/sage/groups/perm_gps/permgroup.py", line 646, in __call__
return self.identity()
File "/sagenb/sage_install/sage-5.2-sage.math.washington.edu-x86_64-Linux/local/lib/python2.7/site-packages/sage/groups/perm_gps/permgroup.py", line 902, in identity
return self._element_class()([], self, check=True)
File "permgroup_element.pyx", line 452, in sage.groups.perm_gps.permgroup_element.PermutationGroupElement.__init__ (sage/groups/perm_gps permgroup_element.c:4337)
File "sage_object.pyx", line 463, in sage.structure.sage_object.SageObject._gap_ (sage/structure/sage_object.c:4518)
File "sage_object.pyx", line 439, in sage.structure.sage_object.SageObject._interface_ (sage/structure/sage_object.c:4118)
File "/sagenb/sage_install/sage-5.2-sage.math.washington.edu-x86_64-Linux/local/lib/python2.7/site-packages/sage/interfaces/interface.py", line 198, in __call__
return cls(self, x, name=name)
File "/sagenb/sage_install/sage-5.2-sage.math.washington.edu-x86_64-Linux/local/lib/python2.7/site-packages/sage/interfaces/expect.py", line 1328, in __init__
raise TypeError, x
TypeError: Gap produced error output
Syntax error: ; expected
$sage2:=Group([PermList([2, 3, 4, 1])]);;
^
executing $sage2:=Group([PermList([2, 3, 4, 1])]);;
I've gotten other error messages as well, but nothing I can reliably reproduce.
If you delete the start and join lines for a or b in the code, it runs fine, of course.
Any ideas here? In case you're curious, the reason I'm trying to thread is this. I have a bunch of problems that can be solved by either of two different methods. For any given problem, one method is usually much faster than the other, but it's difficult to predict in advance which one will be the faster one, so for a given problem I'd like to run both methods simultaneously and accept the result from whichever method finishes first. Any ideas for how to do this in a way that avoids this error are welcome.Martin MalandroFri, 24 Aug 2012 12:12:10 -0500http://ask.sagemath.org/question/7510/Permutation group: (1234)=(12)(13)(14)http://ask.sagemath.org/question/9060/permutation-group-1234121314/How do I show in sage that
(1234)=(12)(13)(14)
I tried make use of:
PermutationGroup([1,2]) * PermutationGroup([1,3])
but it doesn't do what is needed.bk322Tue, 12 Jun 2012 02:25:04 -0500http://ask.sagemath.org/question/9060/