Bounds for eigenvalues of certain stochastic matrices |
| |
Authors: | HJ Landau AM Odlyzko |
| |
Institution: | Bell Laboratories Murray Hill, New Jersey 07974, USA |
| |
Abstract: | We consider the class of stochastic matrices M generated in the following way from graphs: if G is an undirected connected graph on n vertices with adjacency matrix A, we form M from A by dividing the entries in each row of A by their row sum. Being stochastic, M has the eigenvalue λ=1 and possibly also an eigenvalue λ=-1. We prove that the remaining eigenvalues of M lie in the disk ¦λ¦?1–n-3, and show by examples that the order of magnitude of this estimate is best possible. In these examples, G has a bar-bell structure, in which n/3 of the vertices are arranged along a line, with n/3 vertices fully interconnected at each end. We also obtain better bounds when either the diameter of G or the maximal degree of a vertex is restricted. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|