On Kemeny's constant and stochastic complement
Given a stochastic matrix P partitioned in four blocks Pij, i,j=1,2, Kemeny's constant κ(P) is expressed in terms of Kemeny's constants of the stochastic complements P1=P11+P12(I−P22)−1P21, and P2=P22+P21(I−P11)−1P12. Specific cases concerning periodic Markov chains and Kronecker products of stochastic matrices are investigated. Bounds to Kemeny's constant of perturbed matrices are given. Relying on these theoretical results, a divide-and-conquer algorithm for the efficient computation of Kemeny's constant of graphs is designed. Numerical experiments performed on real world problems show the high efficiency and reliability of this algorithm.
Authors
- Beatrice Meini (ORCID: https://orcid.org/0000-0003-3139-2513)
- Fabio Durastante (ORCID: https://orcid.org/0000-0002-1412-8289)
- Dario A. Bini (ORCID: https://orcid.org/0000-0002-5885-9411)
- Sooyeong Kim (ORCID: https://orcid.org/0000-0002-0281-7984)
Publication Details
- Journal
- Linear Algebra and its Applications
- Published
- 2024-09-06
- DOI
- https://doi.org/10.1016/j.laa.2024.09.001
- Citations
- 2
- Primary Topic
- Matrix Theory and Algorithms
- Type
- article
- Field-Weighted Citation Impact
- 0.72
Funders
- Istituto Nazionale di Alta Matematica "Francesco Severi"
- Fields Institute for Research in Mathematical Sciences
- Gruppo Nazionale per il Calcolo Scientifico
- Natural Sciences and Engineering Research Council of Canada