The random-walk matrix and its symmetrization: entries and similarity #
Helpers for the rate bound (Survey, Section 7.2, Theorem 33): the entries of P = D⁻¹A, the
identification of Pᵗ with the t-step transition probabilities transW and of the averaging
dynamics with Pᵗ x, and the similarity P = D^{-1/2} N D^{1/2} with
N = D^{-1/2} A D^{-1/2} when every degree is positive. On a d-regular graph both P and N
are the transition matrix A / d of the core (Dynamics.transitionMatrix, used by the
strong-reconstruction part, AVG-2), and λ is the core's λ_G = max {λ₂, |λₙ|}
(walkLambda_eq_lambdaG).
The entries of P = D⁻¹A: P u v = 1 / d(u) if u ~ v, 0 otherwise.
Pᵗ(u, v) is the t-step transition probability transW G t u v.
The averaging dynamics is x⁽ᵗ⁾ = Pᵗ x⁽⁰⁾.
The entries of N = D^{-1/2} A D^{-1/2}.
D^{1/2} D^{-1/2} = I when every degree is positive.
P = D^{-1/2} N D^{1/2} when every degree is positive.
Pᵗ = D^{-1/2} Nᵗ D^{1/2} when every degree is positive.
The entries of Pᵗ through Nᵗ: Pᵗ(u, v) = d(u)^{-1/2} Nᵗ(u, v) d(v)^{1/2}.
P and N have the same characteristic polynomial when every degree is positive.
Regular graphs #
On a d-regular graph, the transition matrix A / d is P = D⁻¹A.
On a d-regular graph, N = D^{-1/2} A D^{-1/2} is the transition matrix A / d.
On a d-regular graph, λ = max {|λ₂|, |λₙ|} of Theorem 33 is λ_G = max {λ₂, |λₙ|}
(Dynamics.lambdaG): both are read off the sorted spectrum of N = A / d, and the two maxima
agree since λₙ ≤ λ₂.