4
$\begingroup$

The Perron-Frobenius theorem is about the largest eigenvalue and eigenvector of a non-negative (irreducible) matrix.

My question: Is there any estimation of the difference between the first and second largest eigenvalues, say an upper or a lower bound?

An general theory may be tough, so please feel free to add other conditions to limit our discussion.

$\endgroup$
4
$\begingroup$

There certainly isn't a useful one. Consider the matrices

$$A_\lambda=\left(\begin{array}{cc} \tfrac{1+\lambda} 2&\tfrac{1-\lambda} 2 \\ \tfrac{1-\lambda} 2 & \tfrac{1+\lambda} 2\end{array}\right)$$ for $\lambda\in(0,1)$

Then $A_\lambda$ is irreducible and has eigenvalues $1$ and $\lambda$.

For an irreducible Markov chain the second eigenvalue represents the rate that the chain converges to its invariant distribution. This can be incredible fast, or incredibly slow.

$\endgroup$
4
$\begingroup$

Well, if we limit our discussion to the weighted undirected graphs, there is Cheeger inequality which provides bounds for the 2nd eigenvalue in terms of other numerical characteristics of the graph: see e.g. here.

The result may still hold for weighted graphs directed graphs that are symmetrizable: namely, there exists a positive vector $\mu$ such that $A(x,y)\mu(x) = A(y,x)\mu(y)$, see in this very accessible lecture notes. Without this reversible/symmetrizable structure you don't have Green's theorem, so results are pretty weak.

As Tim has mentioned, though, there are no non-trivial bounds in general since the 2nd eigenvalue may be as close to the 1st one as one can imagine. So anyways, it all depends on a particular case. I don't know of any interesting estimates for the non-reversible case.

$\endgroup$
  • $\begingroup$ Thanks a lot! The Cheeger inequality seems to be only applicable for the Laplacian of a graph. Does there exist a similar result for other matrix? For example, the off-diagonal element is still $-1$ or $0$, but the diagonal element is not the degree of a vertex? $\endgroup$ – Tahet Jun 14 '13 at 10:06
  • $\begingroup$ @Tahet: how can it be $-1$ if we talk about non-negative matrices? Anyways, I updated the answer. $\endgroup$ – Ilya Jun 18 '13 at 12:56
  • $\begingroup$ Thanks for updating. Sorry, I used the language in your first note on Cheeger inequality. I just mean a non-negative matix has only off-diagonal elements $0$ or $1$. But the diagonal elements have no relation with the off-diagonal ones (Laplacians are thus counterexamples). Are there some results for them? $\endgroup$ – Tahet Jun 22 '13 at 15:01
0
$\begingroup$

I think if you have Doeblin-Fortet (or Lasota-Yorke sometimes) inequalities satisfied you can do some estimates.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.