Lemma 3 (ii) —
ProvedEffResSparsify.Sampling.lemma_3_iieffective-resistancep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1projectionspectral-graph-theory
Let be a connected weighted graph with positive edge weights, with incidence matrix , diagonal weight matrix and . Then and have the same column space in :
In particular acts as the identity on , the weighted cut space, which is the property Lemma 4 uses.
Preamble
import Mathlib import Definitions.Def_EffResSparsify_Sampling_Defs
Formal statement
namespace EffResSparsify.Sampling
open Matrix
/-- Lemma 3 (ii), p. 6: `im(Π) = im(W^{1/2} B)`. -/
theorem lemma_3_ii {V E : Type} [Fintype V] [DecidableEq V] [Fintype E] [DecidableEq E]
(G : WGraph V E) (hG : G.IsConnected) :
LinearMap.range (Matrix.toLin' G.projPi) =
LinearMap.range (Matrix.toLin' (G.sqrtWeightMatrix * G.incidence)) := by sorry
end EffResSparsify.Sampling
Source
Spielman, Srivastava, Graph Sparsification by Effective Resistances, arXiv:0803.0929v4, p. 6, Lemma 3 (ii)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.