1 Basics of Walks and Walk Counting

1.1 Definitions: walk, path, length, and endpoints

A walk in a graph is a sequence of vertices \(v_0,v_1,\dots,v_k\) such that each consecutive pair \((v_{i-1},v_i)\) is an edge. The length of the walk is \(k\). The vertices \(v_0\) and \(v_k\) are the endpoints.

A path is more restrictive: typically it is a walk with no repeated vertices (in a simple-graph setting). Walks allow repetition, so every path is a walk, but not conversely. Many recurrence relations for walk counts treat walks and paths differently, since the combinatorics of repetition differs.

1.2 Adjacency matrix viewpoint

For a graph \(G\) with \(n\) vertices, the adjacency matrix \(A\) is the \(n\times n\) matrix whose \((i,j)\) entry equals the number of edges from vertex \(i\) to vertex \(j\) (for a simple undirected graph, this is \(1\) or \(0\)).

A foundational fact is that matrix powers encode walk counts: for any vertices \(i,j\) and any integer \(k\ge 0\), the entry \((A^k)_{ij}\) equals the number of walks of length \(k\) from \(i\) to \(j\) (with the convention that \(A^0=I\), so \((A^0)_{ij}=1\) if \(i=j\) and \(0\) otherwise).

1.3 Counting walks between two vertices

Let \(w_k(i,j)\) denote the number of walks of length \(k\) from vertex \(i\) to vertex \(j\). Using the adjacency matrix: \[ w_k(i,j)=(A^k)_{ij}. \] The shift from length \(k\) to length \(k+1\) is immediate from multiplication by \(A\): \[ (A^{k+1})_{ij}=(A\cdot A^k)_{ij}=\sum_{\ell=1}^n A_{i\ell}\,(A^k)_{\ell j}. \] This sum corresponds to choosing the first edge \((i,\ell)\) and then following a walk of length \(k\) from \(\ell\) to \(j\).

1.4 Counting total walks of a given length

Total walk counts aggregate endpoints. Common choices include:

  • Total walks from a fixed start \(i\):

\[ \sum_{j=1}^n w_k(i,j) = (A^k\mathbf{1})_i, \] where \(\mathbf{1}\) is the all-ones vector.

  • Total walks ending at a fixed vertex \(j\):

\[ \sum_{i=1}^n w_k(i,j) = (\mathbf{1}^T A^k)_j. \]

  • Total walks over all ordered pairs:

\[ \sum_{i=1}^n\sum_{j=1}^n w_k(i,j)=\mathbf{1}^T A^k \mathbf{1}. \]

  • Number of closed walks of length \(k\) (from a vertex back to itself, summed over all vertices):

\[ \sum_{i=1}^n w_k(i,i)=\mathrm{tr}(A^k), \] where \(\mathrm{tr}\) is the trace.

Walk recurrences often arise by translating these aggregated counts into linear-algebra statements.

2 Walk Recurrence from Linear Algebra

2.1 Adjacency-driven recurrence: \(A^{k+1}=A\cdot A^k\)

The most basic recurrence is the operator identity: \[ A^{k+1}=A\cdot A^k. \] Interpreting this entrywise gives the corresponding relationship for walk counts: \[ w_{k+1}(i,j)=\sum_{\ell} A_{i\ell}\,w_k(\ell,j). \] This is a “next-step update rule”: to count walks of length \(k+1\), extend walks of length \(k\) by one edge from the starting side.

2.2 Vertex-to-vertex recurrence relations

Beyond the one-step matrix product, one can often eliminate intermediate matrices to obtain finite-order linear recurrences in \(k\). The existence of such recurrences is tied to the fact that powers of \(A\) live in a finite-dimensional vector space of matrices, and thus satisfy algebraic dependencies.

Concretely, there exist coefficients \(c_0,\dots,c_m\) (depending on \(G\)) such that for all sufficiently general \(k\), \[ w_{k+m}(i,j)=c_{m-1}w_{k+m-1}(i,j)+\cdots+c_0 w_k(i,j). \] The smallest such \(m\) depends on the minimal polynomial of \(A\) and, in some cases, on the endpoints \((i,j)\) through whether the corresponding sequence is “capturing” all eigenmodes.

2.3 Total-walk recurrence via traces and sums

For aggregated quantities, recurrence relations can be expressed using linear-algebra invariants:

  • Closed-walk counts satisfy

\[ \mathrm{tr}(A^{k+1})=\mathrm{tr}(A\cdot A^k). \] More importantly, \(\mathrm{tr}(A^k)\) is a linear combination of eigenvalue powers, which forces a finite recurrence once the eigenvalues satisfy an algebraic relation.

  • Total walks from or to a vertex are governed by vectors acted upon by \(A\):

\[ A^{k+1}\mathbf{x}=A(A^k\mathbf{x}). \] Sequences like \(\mathbf{u}^T A^k \mathbf{v}\) similarly inherit finite recurrences from algebraic constraints on \(A\).

Thus, recurrence structure emerges both from operator multiplication and from global spectral dependencies.

2.4 Incorporating multiple starting/ending distributions

Instead of counting from a single vertex, one may weight vertices by a distribution. Let \(\alpha,\beta\in\mathbb{R}^n\) represent starting and ending weights. The weighted number of length-\(k\) walks is \[ S_k=\alpha^T A^k \beta. \] Using \(A^{k+1}=AA^k\) yields \[ S_{k+1}=\alpha^T A^{k+1}\beta=\alpha^T A\cdot A^k\beta. \] As \(k\) varies, \(S_k\) lies in a finite-dimensional space spanned by \(\alpha^T\) applied to powers of \(A\), so it satisfies a linear recurrence whose order is at most the dimension of that span (and ultimately bounded by the degree of the minimal polynomial of \(A\)).

3 Spectral Recurrences and Closed Forms

3.1 Eigen-decomposition and diagonalization (where applicable)

If \(A\) is diagonalizable over \(\mathbb{C}\), it can be written as \[ A=V\Lambda V^{-1}, \] where \(\Lambda\) is diagonal and contains eigenvalues \(\lambda_1,\dots,\lambda_n\). Then \[ A^k=V\Lambda^k V^{-1}, \] so each entry \((A^k)_{ij}\) is a linear combination of \(\lambda_r^k\) terms. Even when diagonalization is not available over the base field, a Jordan form still produces expressions involving \(\lambda^k\) possibly multiplied by polynomials in \(k\). In most recurrence discussions, diagonalizable cases give the cleanest “closed forms.”

3.2 Expressing walk counts with eigenvalues

Under diagonalization, \[ w_k(i,j)=(A^k)_{ij}=\sum_{r=1}^n c_r(i,j)\,\lambda_r^k, \] for coefficients \(c_r(i,j)\) determined by eigenvectors and endpoint locations.

For closed walks, \[ \mathrm{tr}(A^k)=\sum_{r=1}^n \lambda_r^k, \] counting multiplicities. This identity directly links recurrence behavior to the algebraic relations among eigenvalues.

3.3 Growth rates and dominant eigenvalue behavior

When eigenvalues have different magnitudes, the term with largest absolute value typically dominates for large \(k\). If \(\rho\) denotes the spectral radius (maximum \(\lambda\)), then asymptotically many walk counts behave like combinations of \(\rho^k\), scaled by coefficients depending on the relevant eigenspaces.

For irregular graphs, the dominant eigenvalue may reflect broader connectivity patterns, so recurrence sequences often show exponential growth with oscillations if eigenvalues are complex or negative.

3.4 From spectral data to finite-order recurrences

Because eigenvalues are roots of the characteristic polynomial, powers \(\lambda^k\) satisfy algebraic recurrences. If \[ p(\lambda)=\lambda^n+a_{n-1}\lambda^{n-1}+\cdots+a_0 \] is the characteristic polynomial, then each eigenvalue fulfills \[ \lambda^n=-a_{n-1}\lambda^{n-1}-\cdots-a_0. \] Multiplying by \(\lambda^k\) gives a relation among \(\lambda^{k+n}\) through \(\lambda^k\) terms. Summing the corresponding eigenmode expressions transfers the same recurrence to walk counts such as \(w_k(i,j)\) or \(\mathrm{tr}(A^k)\). The resulting recurrence order is at most \(n\), and often smaller when eigenvalues repeat or are algebraically constrained.

4 Recurrences via Characteristic Polynomials

4.1 Using the characteristic polynomial (Cayley–Hamilton)

The Cayley–Hamilton theorem asserts that \(A\) satisfies its own characteristic polynomial: \[ p(A)=A^n+a_{n-1}A^{n-1}+\cdots+a_0 I=0. \] Multiplying by \(A^k\) yields \[ A^{k+n}+a_{n-1}A^{k+n-1}+\cdots+a_0 A^k=0. \] Taking any entry \((i,j)\) produces a linear recurrence for \(w_k(i,j)\) with coefficients from the characteristic polynomial.

4.2 Deriving recurrence order and coefficients

From the relation above, one obtains for all \(k\ge 0\): \[ w_{k+n}(i,j)=-a_{n-1}w_{k+n-1}(i,j)-\cdots-a_0 w_k(i,j). \] Thus:

  • The order is bounded by \(n\).
  • The coefficients are determined entirely by the characteristic polynomial of \(A\).

If the minimal polynomial has smaller degree than \(n\), one can often reduce the order by using the minimal polynomial in place of the characteristic polynomial.

4.3 Examples with small graphs and resulting recurrences

For a graph whose adjacency matrix has characteristic polynomial of degree \(n\) with no repeated irreducible factors, the walk count sequences typically require order \(n\). On small graphs, this can be seen directly by computing \(A^k\) for a few \(k\) and fitting to a recurrence predicted by \(p(A)\).

For instance, graphs with low-degree characteristic polynomials yield explicit short recurrences, and the recurrence coefficients are read off from \(p\). This approach is often used in hand calculations and in verifying computational results.

4.4 Minimal polynomial and reduced recurrence order

The minimal polynomial \(m_A(x)\) is the monic polynomial of smallest degree with \(m_A(A)=0\). Repeating the Cayley–Hamilton argument with \(m_A\) yields a recurrence of order \(\deg(m_A)\).

Moreover, for specific sequences like \(w_k(i,j)= (A^k)_{ij}\), the effective order can sometimes drop further if the endpoints \((i,j)\) fail to excite certain eigen-directions. In practice, however, the minimal polynomial provides a general guaranteed bound.

5 Special Graph Classes

5.1 Regular graphs: simplified recurrences

In an \(r\)-regular undirected graph, each vertex has the same degree \(r\), and the all-ones vector \(\mathbf{1}\) is an eigenvector of \(A\) with eigenvalue \(r\). This yields simplifications for total walk counts: \[ A\mathbf{1}=r\mathbf{1}\quad\Rightarrow\quad A^k\mathbf{1}=r^k\mathbf{1}. \] Consequently, sequences like total walks from a vertex are often expressible as \(r^k\) plus corrections from other eigenvalues. The recurrence coefficients remain determined by the characteristic or minimal polynomial, but the dominant term and many aggregates become more transparent.

5.2 Trees: recurrence patterns by branching structure

Trees have acyclic underlying structure, but walks may revisit vertices, so walk counts still follow spectral and algebraic recurrences. Nevertheless, the tree’s branching structure often allows additional combinatorial descriptions: the number of walks of a fixed length from a root can be expressed via subtree contributions and dynamic programming.

Such methods can be combined with linear-algebra constraints to produce recurrence relations whose behavior reflects how degrees expand and contract along levels.

5.3 Bipartite graphs: parity-separated walk counts

In a bipartite graph with parts \(U\) and \(V\), walks alternate between parts. Therefore, walks of odd length go from \(U\) to \(V\) and from \(V\) to \(U\), while walks of even length remain within the same part.

At the matrix level, the adjacency matrix (after ordering vertices by parts) has a block off-diagonal form, which implies that even powers and odd powers separate:

  • \(A^{2t}\) connects vertices within the same part,
  • \(A^{2t+1}\) connects across parts.

As a result, recurrences for walk counts often split into two parity-specific sequences, effectively halving the “mixing” across lengths.

5.4 Directed graphs and walk recurrences with non-symmetric adjacency

For directed graphs, the adjacency matrix need not be symmetric. Walk counts from \(i\) to \(j\) are still given by \((A^k)_{ij}\), but diagonalization and eigenvalue properties can be more subtle over \(\mathbb{R}\). Recurrence relations from Cayley–Hamilton continue to hold because they rely only on polynomial identities satisfied by \(A\).

Depending on the structure, recurrences may show complex oscillations due to non-real eigenvalues, and growth rates correspond to the spectral radius of the directed adjacency operator.

6 Combinatorial Interpretations

6.1 Next-step extension principle (local update rule)

A walk of length \(k+1\) from \(i\) to \(j\) can be obtained by choosing the first step from \(i\) to some neighbor \(\ell\), then selecting a walk of length \(k\) from \(\ell\) to \(j\). This gives the local rule: \[ w_{k+1}(i,j)=\sum_{\ell\sim i} w_k(\ell,j), \] where \(\ell\sim i\) indicates adjacency (or more generally, nonzero edge multiplicity).

This “next-step” description is the combinatorial counterpart of multiplication by the adjacency matrix.

6.2 Decomposing walks by intermediate vertices

Another viewpoint decomposes a walk by an intermediate vertex at a chosen time \(t\). For \(0<t<k\), \[ w_k(i,j)=\sum_{v} w_t(i,v)\,w_{k-t}(v,j). \] This identity reflects concatenation: a length-\(k\) walk factors into a length-\(t\) prefix and a length-\((k-t)\) suffix that meet at \(v\).

Such decompositions lead to convolution-like formulas and are useful for generating functions and for proving recurrence relations by induction.

6.3 Relation to powers of adjacency and convolution-like behavior

The matrix product behind walk concatenation corresponds exactly to these decompositions. In matrix form, \[ A^k = A^t A^{k-t}. \] Entrywise, the multiplication rule is a weighted sum over intermediate vertices, matching the combinatorial factorization.

This perspective helps interpret recurrences not merely as algebraic artifacts but as statements about how walk segments combine.

6.4 Avoiding overcounting: distinguishing walks vs paths

Because walks may repeat vertices, any combinatorial recurrence based on splitting at intermediate points must count repetitions consistently. A decomposition formula for walks is straightforward because concatenating two walk segments always yields a valid walk, even if it revisits vertices.

For paths, however, concatenation generally fails to preserve the “no repeated vertices” constraint without additional tracking of visited sets. Hence, recurrence methods based on adjacency matrix powers naturally apply to walks rather than paths, and extra combinatorial machinery is required to treat path counts.

7 Practical Computation and Verification

7.1 Computing walk counts using matrix powers

Direct computation uses \(w_k(i,j)=(A^k)_{ij}\). For small graphs or small \(k\), one can compute \(A^k\) via repeated multiplication or fast exponentiation. Complexity grows quickly with \(k\) and with matrix size, but it provides a reliable baseline for small instances.

7.2 Efficient recurrence evaluation without full matrix powers

When a finite recurrence is known (from characteristic or minimal polynomials), walk sequences can be computed using only earlier values rather than forming \(A^k\). This is especially useful for large \(k\).

Operationally, one:

  1. Computes initial walk counts for \(k=0,1,\dots,m-1\).
  2. Applies the recurrence

\[ w_{k+m}=\sum_{r=0}^{m-1} c_r\, w_{k+r} \] for subsequent \(k\). This reduces both time and memory compared with explicit matrix powers.

7.3 Numerical stability and exact arithmetic considerations

Computations of eigenvalues or characteristic polynomials may introduce floating-point errors. For exact recurrence coefficients, it is often preferable to work with rational integers (e.g., via exact characteristic polynomial computation and integer arithmetic).

For recurrence evaluation, stability depends on how coefficients grow and whether cancellations occur. In contexts requiring exact walk counts, using modular arithmetic or exact integer linear recurrence techniques can avoid rounding issues.

7.4 Validating recurrence formulas on test graphs

A standard verification strategy is:

  • Choose a family of graphs with known structure (cycles, complete graphs, grids, small trees).
  • Compute walk counts for a range of \(k\).
  • Check whether the computed sequences satisfy the recurrence predicted by the characteristic or minimal polynomial.

Consistency across multiple endpoints \((i,j)\) or multiple aggregate quantities (e.g., trace-based closed walks) increases confidence that the recurrence has been derived correctly.

8.1 Dynamic processes on graphs (walk-based propagation)

Many network dynamics can be phrased in terms of walk counts. For example, linear propagation models where influence spreads along edges in discrete time steps use exactly the operator \(A\) (or a related normalized form). The number of possible influence paths after \(k\) steps corresponds to walk counts, making recurrence relations relevant for analyzing how quickly effects disperse.

8.2 Connections to graph spectra and isospectrality checks

Spectral recurrence principles connect walk growth and closed-walk counts to eigenvalues. Since \(\mathrm{tr}(A^k)\) sums eigenvalue powers, matching \(\mathrm{tr}(A^k)\) for enough values of \(k\) can give strong evidence of shared spectral structure. This is one way walk recurrences support spectral comparisons, including checks for whether two graphs may be isospectral.

Generating functions encode walk counts as coefficients. The relation to adjacency powers implies that walk generating functions often have rational forms determined by characteristic polynomials in the finite-dimensional setting. Recurrences then correspond to linear differential or difference equations satisfied by these generating functions.

These methods are widely used in enumerative combinatorics, where counting walks acts as a tractable proxy for counting more constrained objects like self-avoiding walks.

Although recurrences here are purely combinatorial/algebraic, they also inform probabilistic interpretations. In a simple random walk, transition probabilities after \(k\) steps relate to normalized adjacency powers, so walk recurrences translate into recurrences for transition probabilities or expected counts of visits.

Quantities derived from counting—such as measures of reachability, expected number of returns, or moment-like statistics—inherit similar recurrence-driven structure.