Geometric multiplicity of unitary non-backtracking eigenvalues

Publication date 4 May 2022

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Eigenvalues, singular values, and eigenvectors (15A18) Special matrices (15B99)

Abstract: We completely characterize the conditions under which a complex unitary number is an eigenvalue of the non-backtracking matrix of an undirected graph. Further, we provide a closed formula to compute its geometric multiplicity and describe an algorithm to compute this multiplicity without making a single matrix computation. The algorithm has time complexity that is linear in the size of the graph.

This page was built for publication: Geometric multiplicity of unitary non-backtracking eigenvalues

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