Spectral Analysis for Non-Hermitian Matrices and Directed Graphs

2018/12/11 by Gnang, Edinah K., Murphy, James M.
#FOS: Mathematics #Spectral Theory (math.SP)

paper · doi:10.48550/arxiv.1812.04737

Abstract

We generalize classical results in spectral graph theory and linear algebra more broadly, from the case where the underlying matrix is Hermitian to the case where it is non-Hermitian. New admissibility conditions are introduced to replace the Hermiticity condition. We prove new variational estimates of the Rayleigh quotient for non-Hermitian matrices. As an application, a new Delsarte-Hoffman-type bound on the size of the largest independent set in a directed graph is developed. Our techniques consist in quantifying the impact of breaking the Hermitian symmetry of a matrix and are broadly applicable.

Related

• Spectral Properties of Matrices Associated with Some Directed Graphs
• Spectral properties of the non-backtracking matrix of a graph
• Spectral Bounds for Directed Graphs Via Asymmetric Matrices: Applications to Toughness
• An Extension of the Rayleigh Quotient to the Spectral Radius of Asymmetric Nonnegative Matrices
• Unsolved Problems in Spectral Graph Theory