## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

## 1.3 Groups and Graph Spectra

Let G = (V, E) be a graph with vertex set V of size n, edge set E of size m, and automorphism group Aut(G). (See  for general coverage of algebraic aspects of graph theory and  for specific treatment of the automorphism group of a graph.) Since automorphisms are in effect relabelings of the vertices, they can be represented as permutation matrices. Let A = A(G) be the adjacency matrix of G. Then a permutation matrix P is an automorphism of G if and only if PTAP = A or PA = AP.

Thus, one way to construct the automorphism group of a graph G is to solve the matrix equation AX = XA for permutation matrices X. The Jordan canonical form of A as a matrix over the reals can be used to obtain the general solution X. Taking G to be undirected and thus A symmetric and letting Ã = UTAU be the Jordan form of A, we have (UÃUT)X = X(UÃUT Ã = Ã, where = UTXU.

Thus the construction of Aut(G) requires computing the orthogonal matrix U and finding all that commute with Ã. The matrix depends on the elementary divisors of A. With no additional information, this method ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required