Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3 — variational characterization of the Schur complement

Proved
PQNormIPM1352.Main.lemma_3

by mikedeng1 · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

convex-optimizationinterior-pointnumerical-linear-algebrap2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let A∈R(n1+n2)×(n1+n2)A \in \mathbb R^{(n_1+n_2)\times(n_1+n_2)}A∈R(n1​+n2​)×(n1​+n2​) be positive definite, with rows and columns partitioned into blocks S1,S2S_1, S_2S1​,S2​, and let

A∖S2=A(S1,S1)−A(S1,S2) A(S2,S2)−1A(S2,S1)(2)A\setminus S_2 = A(S_1,S_1) - A(S_1,S_2)\,A(S_2,S_2)^{-1}A(S_2,S_1) \tag{2}A∖S2​=A(S1​,S1​)−A(S1​,S2​)A(S2​,S2​)−1A(S2​,S1​)(2)

be its Schur complement with respect to S2S_2S2​. For any x1∈RS1x_1\in\mathbb R^{S_1}x1​∈RS1​,

x1⊤(A∖S2) x1=min⁡x2∈RS2(x1x2) ⁣⊤A(x1x2),x_1^\top(A\setminus S_2)\,x_1 = \min_{x_2\in\mathbb R^{S_2}}\begin{pmatrix}x_1\\x_2\end{pmatrix}^{\!\top} A\begin{pmatrix}x_1\\x_2\end{pmatrix},x1⊤​(A∖S2​)x1​=x2​∈RS2​min​(x1​x2​​)⊤A(x1​x2​​),

and the minimum is attained at x2=−A(S2,S2)−1A(S2,S1) x1x_2 = -A(S_2,S_2)^{-1}A(S_2,S_1)\,x_1x2​=−A(S2​,S2​)−1A(S2​,S1​)x1​.

It is used to lift the error bound of the Schur-complement solve to the full Hessian norm in Lemma 11.

Differences from the source:

  • encoding: A positive definite with A(S₂,S₂) invertible, blocks indexed by S₁, S₂ → A : Matrix (S₁ ⊕ S₂) (S₁ ⊕ S₂) ℝ positive definite, blocks by toBlocks; reason: A(S₂,S₂) is invertible because A is positive definite, so the source's invertibility assumption is implied
Preamble
import Mathlib
open Matrix
Formal statement
namespace PQNormIPM1352.Main

/-- **Lemma 3** (Pirazzini–Spielman, STOC 2027 #1352, p. 5; setting of §2.1.4, p. 4). Let
`A ∈ ℝ^{(S₁ ⊔ S₂) × (S₁ ⊔ S₂)}` be positive definite, with blocks `A(Sᵢ, Sⱼ)` and Schur complement
`A \ S₂ = A(S₁,S₁) − A(S₁,S₂) A(S₂,S₂)⁻¹ A(S₂,S₁)` (2). For every `x₁ ∈ ℝ^{S₁}`,
`x₁ᵀ (A \ S₂) x₁ = min_{x₂ ∈ ℝ^{S₂}} (x₁; x₂)ᵀ A (x₁; x₂)`, and the minimum is attained at
`x₂ = −A(S₂,S₂)⁻¹ A(S₂,S₁) x₁`. -/
theorem lemma_3 {S₁ S₂ : Type} [Fintype S₁] [Fintype S₂] [DecidableEq S₁] [DecidableEq S₂]
    (A : Matrix (S₁ ⊕ S₂) (S₁ ⊕ S₂) ℝ) (hA : A.PosDef) (x₁ : S₁ → ℝ) :
    IsLeast {t : ℝ | ∃ x₂ : S₂ → ℝ, t = Sum.elim x₁ x₂ ⬝ᵥ (A *ᵥ Sum.elim x₁ x₂)}
        (x₁ ⬝ᵥ ((A.toBlocks₁₁ - A.toBlocks₁₂ * A.toBlocks₂₂⁻¹ * A.toBlocks₂₁) *ᵥ x₁)) ∧
      Sum.elim x₁ (-(A.toBlocks₂₂⁻¹ * A.toBlocks₂₁) *ᵥ x₁) ⬝ᵥ
          (A *ᵥ Sum.elim x₁ (-(A.toBlocks₂₂⁻¹ * A.toBlocks₂₁) *ᵥ x₁)) =
        x₁ ⬝ᵥ ((A.toBlocks₁₁ - A.toBlocks₁₂ * A.toBlocks₂₂⁻¹ * A.toBlocks₂₁) *ᵥ x₁) := by sorry

end PQNormIPM1352.Main
Source
Marco Pirazzini, Daniel Spielman, A Fast and Accurate Algorithm for the p → q Norm of Sparse Non-Negative Matrices, STOC 2027 submission #1352 (October 2026), Lemma 3, printed p. 5 (PDF p. 6); setting §2.1.4, p. 4
Human review
  • Endorsed by Shuze Chen · Nov 11, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 11, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me