Lower bound for the Perron eigen-value of a non-negative, irreducible, integer matrix

Rob10

New member
Joined
May 20, 2013
Messages
1
[FONT=MathJax_Math]A is a non-negative, integer, irreducible, [FONT=MathJax_Math]m[/FONT] by [FONT=MathJax_Math]m[/FONT] matrix. It is well known (Perron-Frobenius) that [FONT=MathJax_Math]A[/FONT] has a positive eigen value (denote it by [FONT=MathJax_Math]λ[/FONT]) with a positive eigen vector ([FONT=MathJax_Math]x[/FONT]). It is needed to prove that:[/FONT]
[FONT=MathJax_Math]x[FONT=MathJax_Math]m[/FONT][FONT=MathJax_Math]a[/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Main]/[/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Math]m[/FONT][FONT=MathJax_Math]i[/FONT][FONT=MathJax_Math]n[/FONT][FONT=MathJax_Main]≤[/FONT][FONT=MathJax_Math]λ[/FONT][FONT=MathJax_Math]m[/FONT][FONT=MathJax_Main]−[/FONT][FONT=MathJax_Main]1[/FONT][/FONT]
[FONT=MathJax_Math]x[FONT=MathJax_Math]m[/FONT][FONT=MathJax_Math]a[/FONT][FONT=MathJax_Math]x[/FONT] denotes the largest element of [FONT=MathJax_Math]x[/FONT], [FONT=MathJax_Math]x[/FONT][FONT=MathJax_Math]m[/FONT][FONT=MathJax_Math]i[/FONT][FONT=MathJax_Math]n[/FONT] denotes the smallest element of [FONT=MathJax_Math]x[/FONT].[/FONT]
I proved that when considering A as an adjacency matrix, where there is an edge from state [FONT=MathJax_Math]u to state [FONT=MathJax_Math]v[/FONT], the following holds:[/FONT]
[FONT=MathJax_Math]x[FONT=MathJax_Math]v[/FONT][FONT=MathJax_Main]≤[/FONT][FONT=MathJax_Math]λ[/FONT][FONT=MathJax_Math]x[/FONT][FONT=MathJax_Math]u[/FONT][/FONT]
(it was the hint in this question). I don't see how to proceed from here.
 
Found elsewhere online:

Well, I found the answer. It is easy to prove that \(\displaystyle x_v\,\leq \,\lambda x_u\) simply by writing down \(\displaystyle Ax\,=\, \lambda x.\) Now, since \(\displaystyle A\) is irreducible, there must exist a power \(\displaystyle k\, \leq\, m\) such that state \(\displaystyle u\) is connected to state \(\displaystyle v\) by a path of length \(\displaystyle k.\) \(\displaystyle A^k\) represents a graph with paths of length \(\displaystyle k\) between the states of the \(\displaystyle A\)-graph. This matrix has eigenvalue \(\displaystyle \lambda^k\) with eigenvector \(\displaystyle x.\) Thus, we must be able to find indices \(\displaystyle u\) and \(\displaystyle v\) such that \(\displaystyle u\) corresponds to \(\displaystyle x_{min}\) and \(\displaystyle v\) corresponds to \(\displaystyle x_{max}\) for some \(\displaystyle k\), so:

\(\displaystyle \frac{x_{max}}{x_{min}}\, \leq\, \lambda^k\, \leq\, \lambda^{m-1}\)
 
Top