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.Tue, 25 Jan 2022 10:17:06 +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!
Thu, 13 Jan 2022 10:31:03 +0100https://ask.sagemath.org/question/60661/graph-automorphisms-as-permutation-matrices/Comment by mjsupina for <p>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.</p>
<pre><code>W5 = graphs.WheelGraph(5); W5
</code></pre>
<p>(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).</p>
<pre><code>W5.adjacency_matrix()
</code></pre>
<p><code>[0 1 1 1 1]</code></p>
<p><code>[1 0 1 0 1]</code></p>
<p><code>[1 1 0 1 0]</code></p>
<p><code>[1 0 1 0 1]</code></p>
<p><code>[1 1 0 1 0]</code></p>
<p>(The adjacency matrix above is included as evidence that the center vertex is indeed indexed 0.)</p>
<pre><code>aut = W5.automorphism_group(); aut.list()
</code></pre>
<p><code>[(), (2,4), (1,2)(3,4), (1,2,3,4), (1,3), (1,3)(2,4), (1,4,3,2), (1,4)(2,3)]</code></p>
<pre><code>g=aut.an_element(); g
</code></pre>
<p><code>(1,2,3,4)</code></p>
<pre><code>g.matrix()
</code></pre>
<p><code>[0 1 0 0 0]</code></p>
<p><code>[0 0 1 0 0]</code></p>
<p><code>[0 0 0 1 0]</code></p>
<p><code>[1 0 0 0 0]</code></p>
<p><code>[0 0 0 0 1]</code></p>
<p>I suspect that the problem occurs because the vertex 0 is fixed by <em>all</em> 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:</p>
<pre><code>C5 = graphs.CycleGraph(5); C5
</code></pre>
<p>(Again, I can't include a picture, but the vertices are numbered 0 to 4)</p>
<pre><code>autcycle = C5.automorphism_group(); autcycle.list()
</code></pre>
<p><code>[(),
(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)]</code></p>
<pre><code>gcycle = autcycle.random_element(); gcycle
</code></pre>
<p><code>(1,4)(2,3)</code></p>
<pre><code>gcycle.matrix()
</code></pre>
<p><code>[1 0 0 0 0]</code></p>
<p><code>[0 0 0 0 1]</code></p>
<p><code>[0 0 0 1 0]</code></p>
<p><code>[0 0 1 0 0]</code></p>
<p><code>[0 1 0 0 0]</code></p>
<p>I think this is a bug, but if not, I would love some tips on how to achieve my expected outcome. Thank you!</p>
https://ask.sagemath.org/question/60661/graph-automorphisms-as-permutation-matrices/?comment=60806#post-id-60806Ah, I see. That's strange, but that explains my confusion.Tue, 25 Jan 2022 10:17:06 +0100https://ask.sagemath.org/question/60661/graph-automorphisms-as-permutation-matrices/?comment=60806#post-id-60806Comment by rburing for <p>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.</p>
<pre><code>W5 = graphs.WheelGraph(5); W5
</code></pre>
<p>(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).</p>
<pre><code>W5.adjacency_matrix()
</code></pre>
<p><code>[0 1 1 1 1]</code></p>
<p><code>[1 0 1 0 1]</code></p>
<p><code>[1 1 0 1 0]</code></p>
<p><code>[1 0 1 0 1]</code></p>
<p><code>[1 1 0 1 0]</code></p>
<p>(The adjacency matrix above is included as evidence that the center vertex is indeed indexed 0.)</p>
<pre><code>aut = W5.automorphism_group(); aut.list()
</code></pre>
<p><code>[(), (2,4), (1,2)(3,4), (1,2,3,4), (1,3), (1,3)(2,4), (1,4,3,2), (1,4)(2,3)]</code></p>
<pre><code>g=aut.an_element(); g
</code></pre>
<p><code>(1,2,3,4)</code></p>
<pre><code>g.matrix()
</code></pre>
<p><code>[0 1 0 0 0]</code></p>
<p><code>[0 0 1 0 0]</code></p>
<p><code>[0 0 0 1 0]</code></p>
<p><code>[1 0 0 0 0]</code></p>
<p><code>[0 0 0 0 1]</code></p>
<p>I suspect that the problem occurs because the vertex 0 is fixed by <em>all</em> 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:</p>
<pre><code>C5 = graphs.CycleGraph(5); C5
</code></pre>
<p>(Again, I can't include a picture, but the vertices are numbered 0 to 4)</p>
<pre><code>autcycle = C5.automorphism_group(); autcycle.list()
</code></pre>
<p><code>[(),
(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)]</code></p>
<pre><code>gcycle = autcycle.random_element(); gcycle
</code></pre>
<p><code>(1,4)(2,3)</code></p>
<pre><code>gcycle.matrix()
</code></pre>
<p><code>[1 0 0 0 0]</code></p>
<p><code>[0 0 0 0 1]</code></p>
<p><code>[0 0 0 1 0]</code></p>
<p><code>[0 0 1 0 0]</code></p>
<p><code>[0 1 0 0 0]</code></p>
<p>I think this is a bug, but if not, I would love some tips on how to achieve my expected outcome. Thank you!</p>
https://ask.sagemath.org/question/60661/graph-automorphisms-as-permutation-matrices/?comment=60674#post-id-60674Compare `list(W5)` and `list(C5)`; I guess the matrix acts with respect to that ordering of vertices.Thu, 13 Jan 2022 20:22:47 +0100https://ask.sagemath.org/question/60661/graph-automorphisms-as-permutation-matrices/?comment=60674#post-id-60674