Kirkland, Stephen J. and Neumann, Michael (2009) The Case of Equality in the Dobrushin–Deutsch–Zenger Bound. Linear Algebra and its Applications, 431 (12). pp. 23732394. ISSN 00243795
Download (322kB)

Abstract
Suppose that A=(ai,j) is an n×n real matrix with constant row sums μ. Then the Dobrushin–Deutsch–Zenger (DDZ) bound on the eigenvalues of A other than μ is given by Z(A) = 1 2 max 1_s,t_n n Xr=1 as,r − at,r . When A a transition matrix of a finite homogeneous Markov chain so that μ = 1, Z(A) is called the coefficient of ergodicity of the chain as it bounds the asymptotic rate of convergence, namely, max{_  _ 2 _(A) \ {1}} , of the iteration xTi = xT i−1A, to the stationary distribution vector of the chain. In this paper we study the structure of real matrices for which the DDZ bound is sharp. We apply our results to the study of the class of graphs for which the transition matrix arising from a random walk on the graph attains the bound. We also characterize the eigenvalues λ of A for which for some stochastic matrix A.
Item Type:  Article 

Additional Information:  Research supported in part by NSERC under grant OGP0138251. Research supported by NSA Grant No. 06G–232. 
Keywords:  Stochastic Matrices; Coefficient of Ergodicity; Graphs; Random Walks; Eigenvalues of Stochastic Matrices; 
Academic Unit:  Faculty of Science and Engineering > Research Institutes > Hamilton Institute 
Item ID:  2189 
Depositing User:  Professor Steve Kirkland 
Date Deposited:  13 Oct 2010 15:36 
Journal or Publication Title:  Linear Algebra and its Applications 
Publisher:  Elsevier 
Refereed:  No 
URI: 
Repository Staff Only(login required)
Item control page 
Downloads
Downloads per month over past year