Extensions and applications of equitable decompositions for graphs with symmetries
| Autor: | Benjamin Webb, Dallas Smith, Derek Sorensen, Amanda Francis |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Numerical Analysis
Mathematics::Combinatorics Algebra and Number Theory Spectral radius 010102 general mathematics 010103 numerical & computational mathematics Automorphism 01 natural sciences Separable space Combinatorics Gershgorin circle theorem Matrix (mathematics) Computer Science::Discrete Mathematics Homogeneous space FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Partition (number theory) Combinatorics (math.CO) Geometry and Topology 05C50 0101 mathematics Eigenvalues and eigenvectors Mathematics |
| Zdroj: | Linear Algebra and its Applications. 532:432-462 |
| ISSN: | 0024-3795 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect