ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 13 Jan 2022 10:31:03 +0100Graph Automorphisms as Permutation Matriceshttps://ask.sagemath.org/question/60661/graph-automorphisms-as-permutation-matrices/I am trying to take the automorphism group of a finite graph as a permutation group, and then have that permutation group act on R^{vertices of the graph} by permuting coordinates of points. However, when I convert the group elements to permutation matrices, sage seems to sometimes relabel the vertices of the graph, causing the group to act incorrectly. I noticed the problem with the wheel graph. I ran the following four lines in a sagemath jupyter notebook.
W5 = graphs.WheelGraph(5); W5
(I can't include the output since I can't attach pictures, but the important thing is that the middle vertex, which is fixed by all automorphisms, is labelled 0).
W5.adjacency_matrix()
`[0 1 1 1 1]`
`[1 0 1 0 1]`
`[1 1 0 1 0]`
`[1 0 1 0 1]`
`[1 1 0 1 0]`
(The adjacency matrix above is included as evidence that the center vertex is indeed indexed 0.)
aut = W5.automorphism_group(); aut.list()
`[(), (2,4), (1,2)(3,4), (1,2,3,4), (1,3), (1,3)(2,4), (1,4,3,2), (1,4)(2,3)]`
g=aut.an_element(); g
`(1,2,3,4)`
g.matrix()
`[0 1 0 0 0]`
`[0 0 1 0 0]`
`[0 0 0 1 0]`
`[1 0 0 0 0]`
`[0 0 0 0 1]`
I suspect that the problem occurs because the vertex 0 is fixed by *all* automorphisms. Notice that when the group element is converted to a matrix, the indexing seems to change from 0,..,4 to 1,..,5 with the last coordinate fixed instead of the first. I also tested the cycle graph, and here the problem does not occur, even when I choose a group element that fixes vertex 0:
C5 = graphs.CycleGraph(5); C5
(Again, I can't include a picture, but the vertices are numbered 0 to 4)
autcycle = C5.automorphism_group(); autcycle.list()
`[(),
(0,4,3,2,1),
(0,3,1,4,2),
(0,2,4,1,3),
(0,1,2,3,4),
(1,4)(2,3),
(0,4)(1,3),
(0,3)(1,2),
(0,2)(3,4),
(0,1)(2,4)]`
gcycle = autcycle.random_element(); gcycle
`(1,4)(2,3)`
gcycle.matrix()
`[1 0 0 0 0]`
`[0 0 0 0 1]`
`[0 0 0 1 0]`
`[0 0 1 0 0]`
`[0 1 0 0 0]`
I think this is a bug, but if not, I would love some tips on how to achieve my expected outcome. Thank you!
mjsupinaThu, 13 Jan 2022 10:31:03 +0100https://ask.sagemath.org/question/60661/Polyhedra, facets and verticeshttps://ask.sagemath.org/question/55597/polyhedra-facets-and-vertices/I have a 6-dimensional, convex, compact polyhedron in $\mathbb{R}^{12}$, that I am calling `P1`.
The polyhedron `P1` was specified by giving a large number of inequalities.
When I enter `P1.faces(5)` into Sage, I get the following
(A 5-dimensional face of a Polyhedron in RDF^12 defined as the convex hull of 6 vertices,
A 5-dimensional face of a Polyhedron in RDF^12 defined as the convex hull of 7 vertices,
A 5-dimensional face of a Polyhedron in RDF^12 defined as the convex hull of 7 vertices,
A 6-dimensional face of a Polyhedron in RDF^12 defined as the convex hull of 7 vertices,
A 5-dimensional face of a Polyhedron in RDF^12 defined as the convex hull of 6 vertices,
A 6-dimensional face of a Polyhedron in RDF^12 defined as the convex hull of 8 vertices,
...)
How can there be two 6-dimensional faces, each with a different number of vertices,
on the boundary of `P1`? I have checked that `P1` really does have dimension 6.
Also, when I try to find a list of vertices on the boundary of any 5-dimensional face of `P1`,
for example
P1.faces(5)[0].vertices_list()
I get an error message
AttributeError: 'tuple' object has no attribute 'vertices_list'
However, `P1.faces(5)[0].vertices()` works.
My second question is, how do I get a list of vertices on the boundary of an $n$-dimensional face?IngridSat, 06 Feb 2021 10:10:56 +0100https://ask.sagemath.org/question/55597/Orbit "OnSets" in Sagehttps://ask.sagemath.org/question/49044/orbit-onsets-in-sage/I have the following code from GAP which works in Sage 8.9 using gap.eval:
gap.eval("grp := Group([ (1,2,3,4,5), (1,2,4,3) ])")
gap.eval("els := Elements(grp)")
gap.eval("aut := AutomorphismGroup(grp)")
gap.eval("forbidden_orbit := Orbit(aut, els{[1,2,3,4]}, OnSets)")
F_orbit = gap.new("forbidden_orbit")
I'd like to do this directly in Sage. However, is there a Sage function analogous to Gap's "AutomorphismGroup()" and is there a Sage function analogous to how I'm using the "Orbit" function in GAP? I can't seem to find one that outputs the same as above, which should be:
[ [ (), (2,3,5,4), (2,4,5,3), (2,5)(3,4) ],
[ (), (1,2,4,3), (1,3,4,2), (1,4)(2,3) ],
[ (), (1,2)(3,5), (1,3,2,5), (1,5,2,3) ],
[ (), (1,3)(4,5), (1,4,3,5), (1,5,3,4) ],
[ (), (1,2,5,4), (1,4,5,2), (1,5)(2,4) ] ]DanPSun, 15 Dec 2019 21:30:46 +0100https://ask.sagemath.org/question/49044/Automorphism group of edge symmetryhttps://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 11:21:31 +0200https://ask.sagemath.org/question/47334/How can I compute the orbits of an automorphism group?https://ask.sagemath.org/question/43283/how-can-i-compute-the-orbits-of-an-automorphism-group/ I am new on automorphisms, need to know how to compute the orbits of an automorphism group in Sage.ASHWed, 08 Aug 2018 10:31:56 +0200https://ask.sagemath.org/question/43283/Number of graph automorphismshttps://ask.sagemath.org/question/43017/number-of-graph-automorphisms/ Using the below command in SAGE 8.2, the list of automorphisms for a graph could be attained.
G.automorphism_group().list()
What is the command for computing the number of graph automorphoisms?ASHSun, 15 Jul 2018 05:33:57 +0200https://ask.sagemath.org/question/43017/Automorphism group of weighted graphhttps://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 chenThu, 28 Jun 2018 03:22:14 +0200https://ask.sagemath.org/question/42762/Action of lattice automorphism group on discriminant grouphttps://ask.sagemath.org/question/40645/action-of-lattice-automorphism-group-on-discriminant-group/I have a lattice $L$ with automorphism group $G=Aut(L)$. The action of $G$ on $L$ should induce an action on the discriminant group $D={\tilde L}/L$ such that we have a group homomorphism $\phi: Aut(L) \rightarrow Aut(D)$. The kernel of this map will be a normal subgroup $N$ of $G$. I need to be able to compute the action of the quotient $G/N$ on $D$. In the actual example I am interested in $L$ has rank $20$ and is defined through its Gram Matrix. $L$ is an even lattice. A simpler model of this situation would be to take $L$ to be a root lattice, say the $A_2$ root lattice to be concrete, $Aut(L)$ is the dihedral group $D_6$ arising as the product of the $Z_2$ outer automorphism and the $S_3$ Weyl group of $A_2$. The dual lattice $\tilde L$ is the weight lattice of $A_2$ and the discriminant group ${\tilde L}/L$ is $Z_3$ with one non-trivial automorphism, taking $g \rightarrow g^{-1}$. In this simple case everything is computable by hand, but for the case I am interested in I only have $Aut(L)$ presented in terms of $20 \times 20$ matrix generators and computing by hand seems too difficult. Can anyone provide any hints on how to get sage to do this? I can compute $Aut(L)$ and $Aut(D)$ using sage, my problem is in figuring out how to determine $N$ and the action of the quotient $G/N$ on $D$.jahTue, 16 Jan 2018 21:37:35 +0100https://ask.sagemath.org/question/40645/