Sandbox:DavidKohler/Alon try 1/Theorem 3.5

The following theorem generalizes what is sometimes known as Shannon's algorithm which states that for a finite graph G, the Perron-Frobenius eigenvalue can be computed as being the smallest positive real root of z in the equation det(I−A_Gz) = 0. We show here how to extend this result for an infinite variable-length graph.

Statement

Theorem 3.5

Let G be a strongly connected variable-length graph on a countable number of vertices and edges. Then the following are equal: (1) The reciprocal of λ1(G), the Perron-Frobenius value of G. (2) The radius of convergence of any entry of MG(z), the walk matrix of G. If G has a finite number of vertices, then the above two are also equal to the following: (3) The supremum of positive values of z such that ZG(z), the adjacency matrix of G, converges (in each entry) and has largest eigenvalue less than 1. (4) The supremum of positive values of z such that ZG(z), the adjacency matrix of G, converges and such that det(I−ZG(y))>0 for all y with 0 < y < z. If G has a finite number of vertices, and if the entries of ZG(z), the adjacency matrix of G, are all rational functions of z, then the four above quantities also equal: (5) The smallest positive solution of the equation det(I−ZG(z))=0.

Proof

(1) = (2)

Recall that the Perron-Frobenius value, λ₁(G ), of a variable-length graph is defined by

$\lambda _{1}(G)=\limsup _{k\rightarrow \infty }(c_{G}(u,v;k)^{1/k}$

where c_G(u,v; k) denotes the number of walks of length k from vertex u to vertex v. Recall as well that the walk matrix, M_G(z ) of the variable-length graph G is the matrix whose (u,v) entry is given by:

$(M_{G}(z))_{u,v}=\sum _{k\geq 0}c_{G}(u,v;k)z^{k}$

Thus it is clear that the radius of convergence of any entry of the walk matrix is the reciprocal of the Perron-Frobenius value.

(2) = (3)

Consider a non-negative matrix B, then the geometric series I+B+B²+... converges if and only if the largest eigenvalue of the matrix B is less than 1. (proof?)

Hence the radius of convergence of any entry of the walk matrix M_G(z )=I+Z_G(z)+Z_G(z)²+... is the supremum of the values of z which guarantees that the adjacency matrix converges in each entry and that the geometric series converges.

(3) = (4)

• why is it true that if λ₁(G) > 1 then det(I-Z_G(z)) > 0??
• The function λ₁ is continuous in z.

out of both of those, we get the desired result.