Lemma 3 (i) — is a projection matrix
ProvedEffResSparsify.Sampling.lemma_3_ieffective-resistancep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1projectionspectral-graph-theory
Let be a connected weighted graph with positive edge weights, and let , where is the signed incidence matrix, the diagonal weight matrix and the pseudoinverse of the Laplacian . Then is an orthogonal projection matrix:
This is what lets spectral-norm approximation of control quadratic forms, the reduction behind Lemma 4.
Formalization Note The paper's "projection matrix" is read as an orthogonal projection; symmetry is stated as a conjunct because the paper uses it in part (iv).
Preamble
import Mathlib import Definitions.Def_EffResSparsify_Sampling_Defs
Formal statement
namespace EffResSparsify.Sampling
open Matrix
/-- Lemma 3 (i), p. 6: `Π = W^{1/2} B L⁺ Bᵀ W^{1/2}` is a projection matrix: it is idempotent
and symmetric. -/
theorem lemma_3_i {V E : Type} [Fintype V] [DecidableEq V] [Fintype E] [DecidableEq E]
(G : WGraph V E) (hG : G.IsConnected) :
G.projPi * G.projPi = G.projPi ∧ G.projPiᵀ = G.projPi := by sorry
end EffResSparsify.Sampling
Source
Spielman, Srivastava, Graph Sparsification by Effective Resistances, arXiv:0803.0929v4, p. 6, Lemma 3 (i)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.