Eigenvalue Spacings of Transition Matrices Associated to Directed Graphs

This thesis develops new spectral techniques to analyze the convergence behaviour of finite, discrete-time, time-homogeneous Markov chains and explores their applications to directed graphs. We derive an explicit expression for the error term in the convergence theorem in terms of the eigenvalues of the transition matrix. This expression reveals that the convergence behaviour is governed not only by the spectral gap but also by the spacings between eigenvalues. Interpreting the transition matrix as describing a random walk on a directed graph, we use the error term to obtain a new spectral upper bound on the diameter of the directed graph. Finally, we establish several variations of the Expander Mixing Lemma for directed graphs, further illustrating how eigenvalue structure controls combinatorial properties.

Department dc:contributor.department

Mathematics and Statistics

Year dc:date.issued

2026

Author dc:creator

• Carter, Rebecca

Advisors dc:contributor.supervisor

• Murty , M. Ram
• Taylor, Peter

• spectral graph theory
• discrete Markov chains
• directed graphs
• random walks
• eigenvalue spacings
• rate of convergence
• graph diameter

Statement dc:rights

• Attribution 4.0 International

Licence dc:rights.uri

• http://creativecommons.org/licenses/by/4.0/

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1974/36303

OAI identifier oai:identifier

oai:queensu.scholaris.ca:1974/36303