The case of equality in the Dobrushin-Deutsch-Zenger bound
type: Item
instance of: scholarly article
title: The case of equality in the Dobrushin-Deutsch-Zenger bound
zbMATH Open document ID: 1181.15025
author: M. Neumann
author: S. J. Kirkland
published in: Linear Algebra and its Applications
publication date: 2009-11-23T00:00:00Z
review text: Let \(A=(a_{i,j})\) be an \(n\times n\) real matrix with constant row sums \(\mu\). Motivated by the inclusion domains for the nontrivial eigenvalues of stochastic matrices established by \textit{E. Deutsch} and \textit{C. Zenger} [Numer. Math. 18, 182--192 (1971; Zbl 0243.15017)] and to the study on the central limit theorem for non-stationary Markov chains by \textit{R. L. Dobrushin} [Teor. Veroyatn. Primen. 1, 72--89 (1956); 365--425 (1957); ibid. 3, 477 (1958; Zbl 0093.15001)], the authors called the Dobrushin-Deutsch-Zenger bound on the eigenvalues of \(A\) other than \(\mu\) to \[ \mathcal{Z}(A):= \tfrac 12 \max_{1\leq s,t\leq n}\sum_{r=1}^{n}\left| a_{s,r}-a_{t,r}\right|. \] This is a technical paper where the authors study the properties and structure of nonnegative, stochastic, and irreducible matrices \(A\) for which equality holds in \[ \max_{1\neq\lambda\in\sigma (A)}|\lambda |\leq \mathcal{Z}(A) \] and apply these 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. A characterization of the eigenvalues \(\lambda\) of \(A\) for which \(|\lambda| = \mathcal{Z}(A)\), for some stochastic matrix \(A\). Many numerical examples are discussed in detail.
Mathematics Subject Classification ID: 15A42
Mathematics Subject Classification ID: 60G50
Mathematics Subject Classification ID: 60F05
Mathematics Subject Classification ID: 15B51
Mathematics Subject Classification ID: 15B48
zbMATH DE Number: 5637032
zbMATH Keywords: stochastic matrices
zbMATH Keywords: coefficient of ergodicity
zbMATH Keywords: graphs
zbMATH Keywords: random walks
zbMATH Keywords: eigenvalues
zbMATH Keywords: nonnegative matrices
zbMATH Keywords: central limit theorem
zbMATH Keywords: non-stationary Markov chains
zbMATH Keywords: numerical examples
reviewed by: C. M.da Fonseca
MaRDI profile type: Publication
full work available at URL: j.laa.2009.03.028
OpenAlex ID: W2075293395
cites work: Generalized inverses. Theory and applications.
cites work: Q4326384
cites work: Q4002435
cites work: Q5691133
cites work: An improved upper bound for Laplacian graph eigenvalues
cites work: A characterization on graphs which achieve the upper bound for the largest Laplacian eigenvalue of graphs.
cites work: Inclusion domains for the eigenvalues of stochastic matrices
cites work: Q5834412
cites work: Q5834413
cites work: Q3269536
cites work: Convergence Analysis of a PageRank Updating Algorithm by Langville and Meyer
cites work: Q5805016
cites work: On a bound on algebraic connectivity: the case of equality
cites work: The Role of the Group Generalized Inverse in the Theory of Finite Markov Chains
cites work: Q4039989
cites work: Q5643915
cites work: An always nontrivial upper bound for Laplacian graph eigenvalues
cites work: Non-negative matrices and Markov chains. 2nd ed
cites work: Q5342712
DOI: 10.1016/J.LAA.2009.03.028
description: scientific article; zbMATH DE number 5637032