Walk-Sums, Continued Fractions and Unique Factorisation on Digraphs
arXiv:1202.5523
Abstract
We show that the series of all walks between any two vertices of any (possibly weighted) directed graph is given by a universal continued fraction of finite depth and breadth involving the simple paths and simple cycles of . A simple path is a walk forbidden to visit any vertex more than once. We obtain an explicit formula giving this continued fraction. Our results are based on an equivalent to the fundamental theorem of arithmetic: we demonstrate that arbitrary walks on factorize uniquely into nesting products of simple paths and simple cycles, where nesting is a product operation between walks that we define. We show that the simple paths and simple cycles are the prime elements of the set of all walks on equipped with the nesting product. We give an algorithm producing the prime factorization of individual walks, and obtain a recursive formula producing the prime factorization of sets of walks. Our results have already found applications in machine learning, matrix computations and quantum mechanics.
arXiv commentUpdated with links between nesting and loop-erasing. Still under review (!)
References in corpus (4)
Cited by in corpus (9)
- An Exact Formulation of the Time-Ordered Exponential using Path-Sums
- Convergence Analysis of Distributed Inference with Vector-Valued Gaussian Belief Propagation
- Algebraic combinatorics on trace monoids: extending number theory to walks on graphs
- A Lanczos-like method for non-autonomous linear ordinary differential equations
- Realizable cycle structures in digraphs
- Relations between connected and self-avoiding walks in a digraph
- An Explicit Bound for Dynamical Localisation in an Interacting Many-Body System
- A co-preLie structure from chronological loop erasure in graph walks
- Exact Inference on Gaussian Graphical Models of Arbitrary Topology using Path-Sums