4
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ What do you mean by "useful bounds", and why is the "easy bound" not useful? $\endgroup$ Commented Feb 14, 2022 at 17:47
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Feb 14, 2022 at 17:51
  • $\begingroup$ (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? $\endgroup$
    – Will Sawin
    Commented Feb 14, 2022 at 23:42
  • $\begingroup$ 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). $\endgroup$ Commented Feb 15, 2022 at 7:06
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Will Sawin
    Commented Feb 15, 2022 at 12:21

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Commented Feb 16, 2022 at 3:56
  • $\begingroup$ @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. $\endgroup$
    – Will Sawin
    Commented Feb 16, 2022 at 4:12
  • $\begingroup$ Thank you for your further response. $\endgroup$ Commented Feb 16, 2022 at 4:16
  • $\begingroup$ Thanks. Trivial remark: "and the value at the leaf is given by" should be "and the value at the root is given by". $\endgroup$ Commented Feb 16, 2022 at 8:39
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.