Spectral analysis of non-Hermitian matrices and directed graphs

DOI10.1016/J.LAA.2020.06.008MaRDI QIDQ2197201zbMATH OpenOpenAlexFDO

Authors Edinah K. Gnang, James M. Murphy

Publication date 28 August 2020

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.04737

zbMATH Keywords

spectral graph theorydirected graphsindependent setsnon-Hermitian matrices

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Directed graphs (digraphs), tournaments (05C20) Eigenvalues, singular values, and eigenvectors (15A18) Inequalities involving eigenvalues and eigenvectors (15A42)

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.

Recommendations

• Spectral properties of matrices associated with some directed graphs
• Some spectral properties of the non-backtracking matrix of a graph
• Hermitian normalized Laplacian matrix for directed networks
• Non self-adjoint Laplacians on a directed graph
• On the spectra of general random mixed graphs

Cites work

• scientific article; zbMATH DE number 47926 (Why is no real title available?)
• scientific article; zbMATH DE number 1943822 (Why is no real title available?)
• scientific article; zbMATH DE number 867649 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• scientific article; zbMATH DE number 2232233 (Why is no real title available?)
• Diffusion maps
• Diffusion wavelets
• Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process
• Geometric diffusions as a tool for harmonic analysis and structure definition of data: diffusion maps
• Hoffman's coclique bound for normal regular digraphs, and nonsymmetric association schemes
• Interlacing for weighted graphs using the normalized Laplacian
• Isoperimetric numbers of graphs
• Laplacians and the Cheeger inequality for directed graphs
• Magnetic eigenmaps for the visualization of directed networks
• Normalized graph Laplacians for directed graphs
• On the spectra of nonsymmetric Laplacian matrices
• Predator-Prey Patterns
• Representation of functions on big data associated with directed graphs
• Sharp bounds on the spectral radius of nonnegative matrices and digraphs
• Spectra of digraphs
• Sum-product estimates via directed expanders
• Vertex-frequency analysis on graphs
• Wavelets on graphs via spectral graph theory

Cited in

(2)

• Spectral properties of matrices associated with some directed graphs
• Geometric and spectral analysis on weighted digraphs

This page was built for publication: Spectral analysis of non-Hermitian matrices and directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197201)