2018/09/18 by Amanda Francis, Francis, Amanda, Dallas Smith +3
Computer Science · Mathematics · #Advanced Topics in Algebra #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.1809.07186
openalex publication_date 2018/09/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Using the theory of equitable decompositions it is possible to decompose a matrix M appropriately associated with a given graph. The result is a collection of smaller matrices whose collective eigenvalues are the same as the eigenvalues of the original matrix M. This is done by decomposing the matrix over a graph symmetry. Previously it was shown that a matrix can be equitably decomposed over any uniform, basic, or separable automorphism. Here we extend this theory to show that it is possible to equitably decompose a matrix over any automorphism of a graph, without restriction. Moreover, we give a step-by-step procedure which can be used to generate such a decomposition. We also 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.