MURAL - Maynooth University Research Archive Library



    The Case of Equality in the Dobrushin–Deutsch–Zenger Bound


    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

    [thumbnail of SK_dobrushin_final.pdf] PDF
    SK_dobrushin_final.pdf

    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
    Related URLs:
    URI: https://mu.eprints-hosting.org/id/eprint/2189
    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
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads