Cospectrality preserving graph modifications and eigenvector properties via walk equivalence of vertices

Abstract

Originating from spectral graph theory, cospectrality is a powerful generalization of exchange symmetry and can be applied to all real-valued symmetric matrices. Two vertices of an undirected graph with real edge weights are cospectral iff the underlying weighted adjacency matrix $M$ fulfills $[M^k{]}_{u,u}=[M^k{]}_{v,v}$ for all non-negative integer $k$, and as a result any eigenvector $\varphi$ of $M$ has (or, in the presence of degeneracies, can be chosen to have) definite parity on $u$ and $v$. We here show that the powers of a matrix with cospectral vertices induce further local relations on its eigenvectors, and also can be used to design cospectrality preserving modifications. To this end, we introduce the concept of \emph{walk equivalence} of cospectral vertices with respect to \emph{walk multiplets} which are special vertex subsets of a graph. Walk multiplets allow for systematic and flexible modifications of a graph with a given cospectral pair while preserving this cospectrality. The set of modifications includes the addition and removal of both vertices and edges, such that the underlying topology of the graph can be altered. In particular, we prove that any new vertex connected to a walk multiplet by suitable connection weights becomes a so-called unrestricted substitution point (USP), meaning that any arbitrary graph may be connected to it without breaking cospectrality. Also, suitable interconnections between walk multiplets within a graph are shown to preserve the associated cospectrality. Importantly, we demonstrate that the walk equivalence of cospectral vertices $u,v$ imposes a local structure on every eigenvector $\varphi$ obeying ${\varphi }_u=\pm {\varphi }_v\ne 0$ (in the case of degeneracies, a specific choice of the eigenvector basis is needed). Our work paves the way for flexibly exploiting hidden structural symmetries in the design of generic complex network-like systems.

References in corpus (11)

• Classical approach to the graph isomorphism problem using quantum walks
• Compact localized states and flat bands from local symmetry partitioning
• Universal $d=1$ flatband generator from compact localized states
• Orthogonal Sparse PCA and Covariance Estimation via Procrustes Reformulation
• Hidden Symmetries in Real and Theoretical Networks
• Strongly Cospectral Vertices
• Designing pretty good state transfer via isospectral reductions
• Nonlocal discrete continuity and invariant currents in locally symmetric effective Schrödinger arrays
• Quantum Control Theory for State Transformations: Dark States and their Enlightenment
• Non-Local Currents and the Structure of Eigenstates in Planar Discrete Systems with Local Symmetries
• How to Suppress Dark States in Quantum Networks and Bio-Engineered Structures

Cited by in corpus (8)

• Flat bands by latent symmetry
• Latent symmetry induced degeneracies
• Emergent non-Hermitian models
• Topological Anderson insulators by latent symmetry
• State Transfer in Latent-Symmetric Networks
• Eigenmodes of latent-symmetric quantum photonic networks
• Topological band insulators without translational symmetry
• Constructing Cospectral Vertices Through Orbits of Subgraphs