Kemeny's constant via matrix compression and eigenvalue interlacing
Abstract
Kemeny's constant quantifies the expected time for a random walk to reach a randomly chosen vertex, capturing global properties of a Markov chain. We develop a matrix-analytic framework for bounding Kemeny's constant of a finite connected weighted graph using degree-weighted compressions of the normalized adjacency matrix, pinching inequalities, and eigenvalue interlacing. Our main partition theorem gives lower bounds in terms of the compressed spectrum, with complete equality characterizations, and converts structural graph information into spectrally computable estimates. For instance, when applied to proper color partitions, the proposed method yields a sharp lower bound on Kemeny's constant in terms of the chromatic number K(G)≥ n−2+1/χ(G), which extends a bipartite bound of Ciardo, Dahl, and Kirkland (2022) to arbitrary chromatic number, and which is incomparable with the normalized Hoffman bound by Chung (1997). For unweighted graphs, we also characterize all equality cases of this bound. We further illustrate the power of the proposed matrix framework by deriving spectral bounds for NP-hard graph problems involving normalized cuts and conductance. Our results include an asymptotically sharp conductance bound, two-sided interlacing bounds from principal submatrices and quotient matrices, and estimates for the change in Kemeny's constant under connectivity-preserving deletion of multiple edges.
Related
- Comparison theorems for the minimum eigenvalue of a random positive-semidefinite matrix
- Nearest structured matrix having an eigenvalue with prescribed lower bounds of algebraic and geometric multiplicities
- Improved Inclusion-Exclusion Eigenvalue Localization Sets for Matrices and Matrix Polynomials
- A Framework Integrating the Dynamic Stiffness Matrix with Physics-Informed Neural Networks for Solving Eigenvalue Problems and Analysing Dynamic Response
- Wideband Directional ℋ2-Matrix Compression for the Electric Field Integral Equation with Geometry-Adaptive Cluster Trees
BibTeX
@misc{abiad2026kemenys,
title = {{Kemeny's constant via matrix compression and eigenvalue interlacing}},
author = {A. Abiad and Á. Carmona and A. M. Encinas and E. Ghorbani and M. J. Jiménez and Á. Samperio},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17481},
eprint = {2609.17481},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17481},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Kemeny's constant via matrix compression and eigenvalue interlacing
AU - A. Abiad
AU - Á. Carmona
AU - A. M. Encinas
AU - E. Ghorbani
AU - M. J. Jiménez
AU - Á. Samperio
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17481
UR - https://arxiv.org/abs/2609.17481
AB - Kemeny's constant quantifies the expected time for a random walk to reach a randomly chosen vertex, capturing global properties of a Markov chain. We develop a matrix-analytic framework for bounding Kemeny's constant of a finite connected weighted graph using degree-weighted compressions of the normalized adjacency matrix, pinching inequalities, and eigenvalue interlacing. Our main partition theorem gives lower bounds in terms of the compressed spectrum, with complete equality characterizations, and converts structural graph information into spectrally computable estimates. For instance, when applied to proper color partitions, the proposed method yields a sharp lower bound on Kemeny's constant in terms of the chromatic number K(G)≥ n−2+1/χ(G), which extends a bipartite bound of Ciardo, Dahl, and Kirkland (2022) to arbitrary chromatic number, and which is incomparable with the normalized Hoffman bound by Chung (1997). For unweighted graphs, we also characterize all equality cases of this bound. We further illustrate the power of the proposed matrix framework by deriving spectral bounds for NP-hard graph problems involving normalized cuts and conductance. Our results include an asymptotically sharp conductance bound, two-sided interlacing bounds from principal submatrices and quotient matrices, and estimates for the change in Kemeny's constant under connectivity-preserving deletion of multiple edges.
ER -