Extensions and applications of equitable decompositions for graphs with symmetries

We extend the theory of equitable decompositions introduced in [2], where it was shown that if a graph has a particular type of symmetry, i.e. a uniform or basic automorphism ϕ, it is possible to use ϕ to decompose a matrix M appropriately associated with the graph. The result is a number of strictly smaller matrices whose collective eigenvalues are the same as the eigenvalues of the original matrix M. We show here that a large class of automorphisms, which we refer to as separable, can be realized as a sequence of basic automorphisms, allowing us to equitably decompose M over any such automorphism. We also show that not only can a matrix M be decomposed but that the eigenvectors of M can also be equitably decomposed. Additionally, we prove under mild conditions that if a matrix M is equitably decomposed the resulting divisor matrix, which is the divisor matrix of the associated equitable partition, will have the same spectral radius as the original matrix M. Last, we describe how an equitable decomposition effects the Gershgorin region Γ(M) of a matrix M, which can be used to localize the eigenvalues of M. We show that the Gershgorin region of an equitable decomposition of M is contained in the Gershgorin region Γ(M) of the original matrix. We demonstrate on a real-world network that by a sequence of equitable decompositions it is possible to significantly reduce the size of a matrix Gershgorin region.