App. F, p.27 — for zero-sum
ProvedBetheKS.appF_birkhoff_stepcombinatoricslinear-algebrap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a nonzero real matrix with zero row sums and zero column sums. Then
where . The paper derives it from Birkhoff's theorem, being doubly stochastic. In App. F it is applied to the expected centered confusion matrix of the rounding.
Differences from the source:
- generalization: r ≥ 2 the number of communities → every r; reason: the statement is about r × r matrices; r ≥ 2 is a special case
Preamble
import Mathlib set_option autoImplicit false
Formal statement
namespace BetheKS
/-- **App. F, proof of Theorem 2.3 (Birkhoff step)** — Dong, McKenzie, arXiv:2610.41802 (held version,
sha256 4da41e16…), p.27 (PDF p.28): for any nonzero real `r × r` matrix `D` with zero row and column
sums, `max_{τ ∈ S_r} ∑_b D_{τ(b), b} ≥ ‖D‖_F / r`.
**Formalization Note.** `‖D‖_F = (∑_{a,b} D_{ab}²)^{1/2}`; the maximum is a finite `sup'` over
`Equiv.Perm (Fin r)`. The statement is for every `r`. -/
theorem appF_birkhoff_step {r : ℕ} (D : Matrix (Fin r) (Fin r) ℝ) (hD : D ≠ 0)
(hrow : ∀ a, ∑ b, D a b = 0) (hcol : ∀ b, ∑ a, D a b = 0) :
Real.sqrt (∑ a, ∑ b, D a b ^ 2) / r ≤
Finset.univ.sup' Finset.univ_nonempty (fun τ : Equiv.Perm (Fin r) => ∑ b, D (τ b) b) := by sorry
end BetheKS
Source
Dong, McKenzie, Bethe Hessian Recovery through the Kesten–Stigum Regime, arXiv:2610.41802 (held version, sha256 4da41e16…), App. F, proof of Theorem 2.3, p.27 (PDF p.28), display "For any such nonzero matrix D"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.