Exploring Symmetries to Decompose Matrices and Graphs Preserving the Spectrum

Abstract

Given a special kind of symmetric matrix, we present a decomposition technique that preserves its spectrum. We transform this result into an algorithm for graphs. The algorithm disconnects the graph, resulting in smaller matrices, reducing the complexity of computing the graph spectrum. This technique may be seen as a unified approach of several decomposition techniques present in the literature for different instances of matrices and classes of graphs. As an application, we use the algorithm for three classes of graphs: threshold graphs, generalized Bethe trees, and multifan graphs, obtaining expressions for their spectra, for various matrices.