  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.
