Approximate upper bound on eigenvalues of $I-A$ where $A$ is a sparse matrix wherein each row sums to 1.0

166 Views Asked by At

Suppose $A$ is a large matrix with the following properties:

  1. $A$ is $n\times n$
  2. $A$ is sparse (with each row having at most 8 non-zero coefficients, regardless of $n$)
  3. $A$'s diagonal has only zeros.
  4. Each row of $A$ sums to 1.0 (i.e. $A$ transforms each element to the weighted average of 8 "neighbors" in some sense)
  5. FWIW: Non-zero coefficients in $A$ are "typically" not very far from $\frac{1}{8}$ but could in principle be anywhere in $\mathbb{R}$.

What is a good way (criterion/algorithm) to find an upper bound on the magnitude of the eigenvalues of $I-A$?

In particular I seek to find $s\in\mathbb{R}$ that guarantees that $\lim_{n\rightarrow\infty}(\frac{A-I}{s})^n=0$ (even if $s$ is, say, up to 200% of the largest eigenvalue).

Could property 4 perhaps allow us to set $s$ to the greatest magnitude of any coefficient in $A$?