How close to uniform are Perron-Frobenius eigenvectors?

Question

Let $A=(a_{i,j})$ be a square matrix with non-negative entries. (Assume $A$ is symmetric, if it helps.) Let $v$ be a Perron-Frobenius eigenvector. What do we need to assume about $A$ in order to have useful bounds on how "flat", or close to uniform, $v$ is?

One easy bound (for $v$ having strictly positive entries, as is implied by standard conditions) is given by $$\frac{\max_i v_i}{\min_i v_i} \leq \frac{|A|}{\min_i \sum_j a_{i,j}} \leq \frac{\max_i \sum_j a_{i,j}}{\min_i \sum_j a_{i,j}}.$$ EDIT: Actually, I no longer remember quite how I proved this "easy bound", which may not even be true.

Answer 1

Elaborating on my comment, at Iosif Pinelis's request.

The claimed bound is not right, even for symmetric matrices.

Let $G$ be a binary tree of depth $n$ - i.e. $2^n$ leaf nodes, connected in pairs to $2^{n-1}$ nodes one level up, and one root node on the $n$th level. Let $A$ be the adjacency matrix of $G$. The row sums of $A$ are all $1$, $2$, or $3$, so the right side of the bound is at most $3$.

Let's calculate the Perron-Frobenius eigenvector.

The Perron-Frobenius eigenvector takes the same value, say $1$, on the leaf nodes. For eigenvalue $\lambda$, it must take the value $\lambda$ on nodes one level up from the leaves, then $\lambda^2-2 $ on the next level, and so on.

If $V_i$ is the value on the $i$'th level up from the leaves then the eigenvector condition gives the recurrence relation $ \lambda V_i =2 V_{i-1} + V_{i+1}$, which gives $$V_i = \sqrt{2}^i U_i (\lambda/ 2\sqrt{2})$$ where $U_i$ is the Chebyshev polynomial of the second kind.

The equation is satisfied at the $n$th node if $V_{n+1}=0$, i.e. if $\lambda /2\sqrt{2}$ is equal to a root of the Chebyshev polynomial. The largest eigenvalue comes from the largest root, which is $\cos (\pi / (n+2))$, so $\lambda =2 \sqrt{2} \cos (\pi / (n+2))$, and the value at the root is given by $$\sqrt{2}^n U_n ( \cos(\pi/(n+2)) = \sqrt{2}^n \sin ( (n+1) \pi / (n+2)) / \sin ( \pi / (n+2) ) = \sqrt{2}^n .$$

So the left side can grow arbitrarily large with the right side bounded.

Answer 2

If $A$ is the adjacency matrix of a simple graph, then the quantity $\max_{i,j} v_j/v_i$ is sometimes called the "principal ratio", and is maximized by a kite graph. The bibliography of this linked paper of Tait and Tobin might be of interest.

I did a short mathscinet binge starting from Tait and Tobin and found the following results for more general non-negative matrices:

• Minc, Henryk: On the maximal eigenvector of a positive matrix.
• Ostrowski, A. M: On the eigenvector belonging to the maximal root of a non-negative matrix.
• Hartfiel, D. J: Bounds for eigenvalues and eigenvectors of a nonnegative matrix which involve a measure of irreducibility.
• Latham, Geoff A: A remark on Minc's maximal eigenvector bound for positive matrices.

Perhaps one of them suffices for your application? All of these bound the principal ratio of $A$ in terms of its entries; similar in spirit to the "easy bound" in the question.