Analysis of Complex Networks

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 [3] for general coverage of algebraic aspects of graph theory and [12] 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 P^TAP = 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 à = U^TAU be the Jordan form of A, we have (UÃU^T)X = X(UÃU^T à = Ã, where = U^TXU.

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 ...