https://hal.inria.fr/hal-01402827Avrachenkov, KonstantinKonstantinAvrachenkovMAESTRO - Models for the performance analysis and the control of networks - CRISAM - Inria Sophia Antipolis - Méditerranée - Inria - Institut National de Recherche en Informatique et en AutomatiqueEshragh, AliAliEshraghUoN - University of Newcastle [Australia]Filar, Jerzy A.Jerzy A.FilarFlinders University [Adelaide, Australia]On transition matrices of Markov chains corresponding to Hamiltonian cyclesHAL CCSD2016[INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI]Avrachenkov, Konstantin2016-11-25 11:21:482022-07-08 10:04:162016-11-25 11:27:22enJournal articleshttps://hal.inria.fr/hal-01402827/document10.1007/s10479-014-1642-2application/pdf1In this paper, we present some algebraic properties of a particular class of probability transition matrices, namely, Hamiltonian transition matrices. Each matrix P in this class corresponds to a Hamiltonian cycle in a given graph G on n nodes and to an irreducible, periodic, Markov chain. We show that a number of important matrices traditionally associated with Markov chains, namely, the stationary, fundamental, deviation and the hitting time matrix all have elegant expansions in the first n−1 powers of P , whose coefficients can be explicitly derived. We also consider the resolvent-like matrices associated with any given Hamiltonian cycle and its reverse cycle and prove an identity about the product of these matrices.