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

Improve this question
$\endgroup$
3
  • $\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
    Commented May 10, 2018 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
    Commented May 10, 2018 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 - Free Palestine
    Commented May 10, 2018 at 10:11

2 Answers 2

Reset to default
6
$\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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This assume that all the entries of the matrix are positive. Is any result available for irreducible matrices ? $\endgroup$
    – user131734
    Commented Jan 12, 2019 at 5:53
1
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .