The case of equality in the Dobrushin-Deutsch-Zenger bound (Q1039746)

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.