Powers of the adjacency matrix count walks
ProvedFamousTheorems.adjacency_matrix_power_counts_walks_7aPowers of the adjacency matrix count walks. Let be a finite simple graph with adjacency matrix . For all vertices and every , the entry of is the number of walks of length from to in .
This is the basic link between graph theory and linear algebra. It leads to spectral graph theory, where eigenvalues of control walk counts. It gives the number of closed walks as , the number of triangles as , and the use of eigenvalues to study expansion and random walks.
Formalization note. Mathlib's SimpleGraph.adjMatrix_pow_apply_eq_card_walk. G.adjMatrix α is the adjacency matrix with entries in any semiring , and the count of walks is cast into .
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem adjacency_matrix_power_counts_walks_7a {α V : Type*} {G : SimpleGraph V} [DecidableRel G.Adj] [Fintype V] [DecidableEq V] [Semiring α]
(n : ℕ) (u v : V) : (G.adjMatrix α ^ n) u v = Fintype.card {p : G.Walk u v | p.length = n} := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `SimpleGraph.adjMatrix_pow_apply_eq_card_walk`. Proof here reduces to that Mathlib result.