Skip to main content
2 of 2
edited body
Denis Serre
  • 52.3k
  • 10
  • 146
  • 300

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.

Will Sawin
  • 148.4k
  • 9
  • 324
  • 563