Skip to main content
edited body
Source Link
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 leafroot 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.

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 leaf 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.

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.

Source Link
Will Sawin
  • 148.4k
  • 9
  • 324
  • 563

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 leaf 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.