How close to uniform are Perron-Frobenius eigenvectors?

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.

• What do you mean by "useful bounds", and why is the "easy bound" not useful? Commented Feb 14, 2022 at 17:47
• Oh, it can be useful, but I was assuming people would have a battery of results better than something I thought of in the shower. Commented Feb 14, 2022 at 17:51
• (1) I think $A$ symmetric is necessary - i.e. it does help. Take a path, so the adjacency matrix has nonzero entries only on the diagonal, just above, and just below, and multiply all the entries just above the diagonal by $2$ and just below the diagonal by $1/2$. We have now multiplied the ratio between the first and last entry by $2^{n-1}$. (2) what is $|A|$ in the displayed equation? Commented Feb 14, 2022 at 23:42
• The operator norm. But don't trust that bound! A friend tekks me he just found a counterexample (not symmetric I think). My "proof" in the shower was most likely wrong (but then I may have forgotten a crucial detail). Commented Feb 15, 2022 at 7:06
• I believe the adjacency matrix of a depth $n$ binary tree gives a symmetric counterexample, as $\max_i v_i / \min_i v_i$ should be close to $\sqrt{2}^n$ but the row sums are bounded between $1$ and $3$. Commented Feb 15, 2022 at 12:21

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.

• Thank you for your response. Probably I am missing something here. I think the general solution of your recurrence relation is of the form $c_1a_1^i+c_2a_2^i$ (unless $\lambda=2\sqrt2$). Why then a polynomial? Commented Feb 16, 2022 at 3:56
• @IosifPinelis Well, the expression you give is certainly a polynomial function in $a_1$ and $a_2$. And $a_1$ and $a_2$ are polynomials in $\lambda$ and $\sqrt{\lambda^2-8}$. So the whole thing ends up a polynomial in $\lambda$ after some Galois-invariance removes the $\sqrt{\lambda^2-8}$ term. Commented Feb 16, 2022 at 4:12
• Thank you for your further response. Commented Feb 16, 2022 at 4:16
• Thanks. Trivial remark: "and the value at the leaf is given by" should be "and the value at the root is given by". Commented Feb 16, 2022 at 8:39

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:

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.