5
$\begingroup$

Let $A$ be a matrix that satisfies all the conditions of Perron- Frobenius theorem. From the theorem it is known that the entries of the eigenvector corresponding to the largest eigenvalue will be strictly positive. Are their any good lowerbounds known for these entries ? (Assuming that the eigenvector is normalized in some suitable way)

Imagining $A$ as some kind of a Markov chain, I would expect the lowerbound to depend on how the vertex corresponding to the entry in question is connected to other verticies (degree, weight of self-loops etc.). Any results along those lines would be very-helpful

$\endgroup$
  • $\begingroup$ Draw a weighted directed graph on $1,...,n$ where the weight on the edge $ij$ is $A_{ij}$. Now consider replacing all weights less than $\alpha$ by 0 and find the smallest $\alpha$ such that the PF conditions (of irreducibility) apply. Call that number $\mu(A)$ and let $\lambda(A)$ be the maximum row sum. Then the entries of the normalized PF eigenvector are at least something like $(\mu(A)/\lambda(A))^n$. This is not far from being sharp as you can see from the “ladder” Markov chain where you ascend with probability $\epsilon$ and fall off with probability $1-\epsilon$. $\endgroup$ – Anthony Quas May 10 '18 at 8:42
  • $\begingroup$ Can you point me towards some references that use these kind of constructions ? I'm afraid some of the details are not clear to me. $\endgroup$ – biryani May 10 '18 at 9:11
  • $\begingroup$ @AnthonyQuas: $\mu(A)$ is possibly the largest $\alpha$ such that the PF conditions (of irreducibility) apply. otherwise, $\mu(A)=0$, when $A$ is irreducible. Am I missing something? $\endgroup$ – Mahdi May 10 '18 at 10:11
3
$\begingroup$

This seems to be answered in the accepted answer to this question: The height of the Perron-Frobenius eigenvector

For convenience, here is the estimate:

enter image description here

$\endgroup$
  • $\begingroup$ This assume that all the entries of the matrix are positive. Is any result available for irreducible matrices ? $\endgroup$ – Anonymous Jan 12 at 5:53
0
$\begingroup$

Let $A \in\mathbb{R}^{n\times n}$.

Let $x_i,x_j$ be the minimum and maximum entry of the Perron vector (with some normalization).

Suppose first that $A$ is positive. Then, $$ x_i = \sum_k A_{ik}x_k \geq A_{ij}x_j \geq \min(A) x_j. $$

If $A$ is not positive but is irreducible, then there is a path of length $h\leq n-1$ from $i$ to $j$, hence $(A^h)_{ij} > \left(\operatorname{min_{nonzero}}(A)\right)^h$.

Moreover, you can bound for instance $x_j \geq \frac1n$, with the usual normalization $\sum x_k = 1$.

Putting everything together, $$ x_i \geq \frac1n \left(\operatorname{min_{nonzero}}(A)\right)^{n-1} $$

Not sure if one can do better than this.

$\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.