Spectral analysis of non-Hermitian matrices and directed graphs

DOI10.1016/J.LAA.2020.06.008zbMATH Open1446.05038arXiv1812.04737OpenAlexW3035822444MaRDI QIDQ2197201FDOQ2197201

Authors: Edinah K. Gnang, James M. Murphy 

Publication date: 28 August 2020

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

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.

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

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

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)

Cites Work

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

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)