A prototypical problem for transfer matrix calculations in combinatorics

Question

Let $G$ be a directed graph with self-loops on the positive integers: for every $n$, $G$ has the directed edges $(n,n)$ and $(n, n+1)$; additionally, if $n$ is even, $G$ has the directed edge $(n, n/2)$.

The prototypical question in transfer-matrix problems would be counting walks of $G$ starting from $1$. Since this is usually too hard in real applications, let's concentrate on simpler problems:

Q1. Let $G_k$ be the induced subgraph of $G$ on $1 \cdots k$. Does the largest eigenvalue of the adjacency matrix of $G_k$ converge to the exponential growth rate of walks on $G$?

Q2. Is there a similar convergence of eigenvectors, i.e. for a fixed index $m$ and $k \rightarrow \infty$, when the eigenvectors of $G_k$ are normalized such that their sum of elements is $1$, would its value on $m$ correspond to the frequency of $m$ appearing in a typical walk of $G$?

Q3. Assuming Q2, the limiting eigenvector $v$ has $v_{m+1}/v_{m}$ approaching $\alpha \approx 0.6747$. Is it possible to bound $\alpha$?

EDIT: The largest eigenvalue of truncated adjacency matrices does not necessarily converge to the exponential growth rate of walks. If $g_{n,k}$ is the number of walks of $G$ starting from $1$ whose elements are not larger than $k$, then the exponential growth rate is

$$\underset{n \rightarrow \infty }\lim \underset{k \rightarrow \infty }\lim (g_{n,k})^{1/n}$$

while the limit of the largest eigenvalues of $G_k$ is

$$\underset{k \rightarrow \infty }\lim \underset{n \rightarrow \infty }\lim (g_{n,k})^{1/n}$$

which are not necessarily equal.

For a concrete example, let $H$ be a directed graph on the positive integers: for every $n$, $H$ has the directed edges $(n, n-1)$ (for $n \neq 1$) and $(n, 2n)$.

The exponential growth rate of paths on $H$ is $2$. However, if $H$ is truncated to $H_k$, then the adjacency matrix of $H_k$ is equal to the transpose of that of $G_k$ minus the identity matrix, so the limit of the largest eigenvalues should be one less of that of $G_k$, namely $1.48214622\dots$.

A bit of OEISing gives the number table A274190 where the graph $G$ is modified to not contain the edges $(n,n)$, and its entry at row $n$ and column $k$ corresponds to walks starting from $1$ with length $\leq n$ and last element $k$. The row sum is A274184 and the limiting ratio is A274192, one less than the limiting ratio of $G$ if Q1 is true.

Answer 1

To answer your questions about the directed graph G and its subgraphs Gk, I asked Grok to write a quick Python script to build the adjacency matrix for Gk, compute its largest eigenvalue (the Perron root ρ_k), and the corresponding left Perron eigenvector (normalized to sum to 1). Here's a quick summary of the results and the answers to your questions (caveat that this is computational evidence of convergence vs. an analytical proof):

Q1: Convergence of the Largest Eigenvalue

Yes, the largest eigenvalue ρ_k of the adjacency matrix of Gk converges to the exponential growth rate ρ ≈ 2.4821462210 of the number of walks on the infinite graph G as k → ∞. The code computed ρ_k for increasing k values (10, 20, 50, 100, 200, 500), showing clear stabilization:

k	ρ_k
10	2.4655712319
20	2.4818130429
50	2.4821462182
100	2.4821462210
200	2.4821462210
500	2.4821462210

By k=100, ρ_k has converged to at least 10 decimal places, confirming that finite approximations approach the true growth rate ρ of walks on G.

Q2: Convergence of Eigenvectors

Yes, the left Perron eigenvectors of Gk (normalized to sum to 1) converge componentwise to a limiting vector v as k → ∞, where v_m represents the asymptotic frequency of visiting node m in long walks on G. The code computed the eigenvector for k=500 and compared the first 10 components with those for k=50, showing differences on the order of 10^{-9} or smaller (indicating rapid stabilization for fixed m):

m	v_m (k=50)	v_m (k=500)	Difference
1	0.1219649652	0.1219649618	3.34e-09
2	0.1807699119	0.1807699073	4.60e-09
3	0.1765054284	0.1765054241	4.30e-09
4	0.1459624761	0.1459624731	2.95e-09
5	0.1111399932	0.1111399913	1.90e-09
6	0.0808369413	0.0808369400	1.26e-09
7	0.0572222709	0.0572222706	2.37e-10
8	0.0398323035	0.0398323039	3.44e-10
9	0.0274329871	0.0274329876	4.99e-10
10	0.0187632445	0.0187632450	4.57e-10

The full first 10 components of the limiting v (from k=500) are:
v_1 ≈ 0.1219649618, v_2 ≈ 0.1807699073, v_3 ≈ 0.1765054241, v_4 ≈ 0.1459624731, v_5 ≈ 0.1111399913,
v_6 ≈ 0.0808369400, v_7 ≈ 0.0572222706, v_8 ≈ 0.0398323039, v_9 ≈ 0.0274329876, v_10 ≈ 0.0187632450.

Q3: Bounding α

Assuming Q2 holds, the ratio v_{m+1}/v_m approaches α ≈ 0.6747 in the limiting eigenvector v. Yes, it is possible to bound α. From the converged ρ ≈ 2.4821462210 (at k=500), α ≈ 1/(ρ - 1) ≈ 0.6746972639.

• Upper bound on α: Since ρ_k < ρ for finite k (as Gk is an induced subgraph), ρ_{500} provides a lower bound on ρ, yielding α < 1/(ρ_{500} - 1) ≈ 0.6746972639.
• Lower bound on α: The code Grok built used variational methods (Rayleigh quotients) to bound ρ from above. The uniform test vector gave an upper bound ρ ≤ 2.498, so α > 1/(2.498 - 1) ≈ 0.667556. (The geometric test vector gave ρ ≤ 2.2051946648, but this leads to a looser lower bound α > ≈0.829875, which is inconsistent with the approximation and thus discarded as a poor test vector for this purpose.) Tighter lower bounds could be obtained with better test vectors or analytical methods, e.g., 0.674 < α < 0.675 by refining approximations.

If you're interested, I can do another quick run with a larger k (it's a super fast calculation).

Answer 2

This answer concerns Q1, showing convergence of the largest eigenvalues of $G_{k}$ to the exponential growth rate of walks on the infinite graph. For the infinite graph, let $g(n,m)$ be the number of walks of length $n\geq0$ starting at $1$ and ending at $m$ (possibly going to vertices higher than $m$ before ending at $m$). Considering arcs arriving at vertex $m>1$ gives $g(n,m)=g(n-1,m-1)+g(n-1,n)+g(n-1,2m)$, and we have the starting conditions $g(0,1)=1;$ $g(0,m)=0,m>1;$ $g(1,1)=1;$ $g(n,1)=g(n-1,1)+g(n-1,2),~n>1$.

Evaluating the first few rows with a recursive procedure gives the following table (rows indexed by $n$, columns indexed by $m$).

$$ \begin{array}{c|ccccccc} & 1 & 2 & 3 & 4 & 5 & 6 & 7\\\hline 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\ 2 & 2 & 2 & 1 & 0 & 0 & 0 & 0\\ 3 & 4 & 4 & 3 & 1 & 0 & 0 & 0\\ 4 & 8 & 9 & 7 & 4 & 1 & 0 & 0\\ 5 & 17 & 21 & 16 & 11 & 5 & 1 & 0\\ 6 & 38 & 49 & 38 & 27 & 16 & 6 & 1 \end{array} $$

The row sums give the sequence

$$ r=(1,2,5,12,29,71,175,432,1066,2630,6493,16049,39715,98361,243723,604043,1497223,3711420,9200960,22812509,...), $$

whose exponential growth rate is of interest. This may be evaluated as $\lim_{n\rightarrow\infty}r(n)/r(n-1)$. For example, an estimate (determined from the algorithm below) is $r(500)/r(499)=2.482146221045796473951094418$ (differing in the last two digits from $r(499)/r(498)$).

Now consider the finite graph $G_{k}$. As usual, the number of walks of length $n$ between vertices $i$ and $j$ is given by the $i,j$ entry of $(A_{k})^{n}$, where $A_{k}$ is the adjacency matrix. The number of walks of length $n$ from vertex $1$ to $m$, $m=1,\ldots,k$ is the first row of $(A_{k})^{n}$. The lower Hessenberg form means that successive powers increase the number of nonzero superdiagonals by $1$ and the first row first becomes all nonzero at $n=k-1$. These first rows are in agreement with those in the table above for the infinite graph, since one cannot progress beyond vertex $k$ with a walk of length less than $k$. Therefore the row sums of the first rows of the powers $(A_{k})^{n}$, $n=1,\ldots,k-1$ agree with the row sums for the infinite graph. For higher powers the number of walks departs from the number with that length in the infinite graph, of course being lower, $$ r_{k}(n)=r(n),~0\leq n\leq k-1 $$ $$ r_{k}(n)\leq r(n),~n>k-1 $$ For example for $k=10$ the row sums are

$$ r_{10} =(1,2,5,12,29,71,175,432,1066,2630,6492,16037,39634,97953,242006,597634,1475223,3640313,8981042,22154279,...), $$ showing agreement to $n=9$ $(2630)$.

The growth rates for the sequences for each $k$ can be found using a generating function approach. We mark walk steps with $z$, then $(zA_{k})^{n}$ enumerates walks of length $n$, and for all lengths we have $\sum_{n=0}^{\infty} (zA_{k})^{n}=(I_{k}-zA_{k})^{-1}$, where $I_{k}$ is the $k\times k$ identity matrix. We want the sum of the first row, so the generating function is $e_{1}^{T}(I_{k}-zA_{k})^{-1}e$, where $e$ is the all-ones vector and $e_{1}=[1,0,0...0]$. Expanding as a power series gives a series with the coefficients above. For a rational function generating function as here, the growth rate is found as the reciprocal of the distance of the nearest pole from the origin on the positive real axis. To evaluate this note that $$ e_{1}^{T}(I_{k}-zA_{k})^{-1}e=\frac{e_{1}^{T}\operatorname{Adj}(I_{k}-zA_{k})e}{\det(I_{k}-zA_{k})} $$

Let $z_{\min}$ be the smallest root of the polynomial $\det(I_{k}-zA_{k})$, then $1/z_{\min}$ is the maximum root of $\det(tI_{k}-A_{k})$, $t=1/z$, i.e., the maximum eigenvalue of $A_{k}$ gives the exponential growth rate of walks starting from 1; the same asymptotics apply as for walks between any two vertices $i$ and $j$. The maximum eigenvalues form a monotone increasing sequence as $k$ increases. To see this, note that for nonnegative matrices, the spectral radius of a principal submatrix must be less than or equal to that of the matrix, so $\rho(A_{k})\leq\rho(A_{k+1})$, where in this case the spectral radius is the maximum eigenvalue. The maximum row sum of each of the matrices is $3$, which is an upper bound for the spectral radius, and so a limit exists for the monotone sequence.

To show this limit is the growth rate on the infinite graph, consider the algorithm for generating $r(n)/r(n-1)$ for arbitrary $n$ based on the above-noted agreement between $r$ and $r_{k}$. Choose $k=n+1$. Then $r(n)=e_{1}^{T}\left( A_{k}\right)^{n}e$, or $r(n)$ is the first entry of $\left(A_{k}\right)^{n}e=u_{n}$; similarly for $r(n-1)$ (using the same $k$). In the power method for finding the largest eigenvalue, one chooses an initial vector $x_{0}$ and iterates $x_{j+1}:=A_{k}x_{j}$ to find the eigenvector corresponding to the largest eigenvalue. If we choose $x_{0}=e$ and omit the customary renormalization during the iterations, then $r(n-1)$ and $r(n)$ are the first entries of the $(n-1)$ th and $n$th iteration eigenvectors $u_{n-1}$ and $u_n$. Since $u_{n}=Au_{n-1}\approx\lambda_{\max}u_{n-1}$, $r(n)/r(n-1)$ is an estimate of $\lambda_{\max}$ for $A_{n+1}$.The value of $r(500)/r(499)$ was given above; $\lambda_{\max}$ for $A_{501}$ is $2.482146221045796473951094505$ (a difference of $10^{-25}$).

So the sequence of $r(n)/r(n-1)$ that gives the growth rate on the infinite grap is essentially the same as the sequence of (approximate) maximum eigenvalues of the $A_{k}$, and has the same limit.

Notes:

1. The argument needs work for a formal proof. The approximations to the maximum eigenvalues presumably become sufficiently more accurate at higher $n$.

2. The power method requires the maximum eigenvalue to be greater in magnitude that the others. In addition to irreducibility, the nonzero diagonal entries make it also primitive, which is sufficient for this. The initial vector $x_{0}$ cannot be orthogonal to the left eigenvector for $\lambda_{\max}$; since both these vectors are positive this is also satisfied.

3. The success of the method relies on the key facts that the adjacency matrix is lower Hessenberg, and that one cannot progress beyond vertex $k$ with a walk of length less than $k$ on $G$. Neither of these are true for the graph $H$ given by the OP.

Edit: Here's an elaboration about note 3.

We want to know the maximum power we can raise $A_{k}$ by and still have the first row agree with the number of walks on the infinite lattice. For $G$, one cannot progress beyond vertex $k$ with a walk of length less than $k$, and any of the walks from $1$ to $m$, $m<k$ is the same on $G_{k}$ as on the infinite graph; the number of these walks is correctly given by the first row of $(A_{k})^{k-1}$. This is related to the fact that the matrix is lower Hessenberg: the furthest forward one can step from vertex $i$ is to vertex $i+1$. The first row of $(A_{k})^{k}$ fails to count the walk $1\rightarrow 2\rightarrow\ldots\rightarrow k+1$ on $G$. Therefore to calculate $r(n)/r(n-1),$ we need $A_{k}$, $k>n$. If we choose $k=n+1$ then we evaluate $\left( A_{n+1}\right) ^{n}$ and use the $n$th iteration to approximate the eigenvector in the power method. We could choose larger $k$ but then $\left(A_{k}\right) ^{n}$ would give a poorer estimate of the eigenvector.

For $H$, the largest vertex we can reach with walks of length $n$ is $2^{n}$, with the walk $1\rightarrow 2\rightarrow 4\rightarrow 8\ldots\rightarrow 2^{n}$. Therefore to calculate $r(n)/r(n-1)$, we need $A_{k}$, $k>2^{n}$. If we choose $k=2^{n}+1$ then we evaluate $\left( A_{2^{n}+1}\right) ^{n}$ and use $n$ iterations to approximate the eigenvector in the power method. However, the $n$th approximation is likely a poor estimate for a matrix of size $2^{n+1}$, and certainly this estimate will get worse in the limit of large $n$.