Graph Automorphisms as Permutation Matrices

asked 2022-01-13 18:29:46 +0100

mjsupina gravatar image

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!

edit retag flag offensive close merge delete

Comments

Compare list(W5) and list(C5); I guess the matrix acts with respect to that ordering of vertices.

rburing gravatar imagerburing ( 2022-01-13 20:22:47 +0100 )edit