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. 2373-2394. ISSN 0024-3795

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:	http://www.sciencedirect.com/science/jou...
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads