Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem A.5, p. 210 — positive curvature on a conjugate basis of the full Krylov space forces H positive definite

Proved
TruncNewton.NegCurv.theorem_A_5

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

conjugacyeigenspacekrylov-subspacep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1positive-definite

Let HHH be a symmetric linear operator on Rn\mathbb{R}^nRn with the standard inner product (⋅,⋅)(\cdot,\cdot)(⋅,⋅), and for a real λ\lambdaλ let E(λ,H)={v:Hv=λv}E(\lambda,H)=\{v: Hv=\lambda v\}E(λ,H)={v:Hv=λv} (A.21). Let g∈Rng\in\mathbb{R}^ng∈Rn have a nonzero projection on each eigenspace of HHH, and let kkk be the number of distinct eigenvalues of HHH. Let d0,…,dk−1d_0,\dots,d_{k-1}d0​,…,dk−1​ be vectors such that

(di,Hdj)=0  (i≠j),(di,Hdi)>0,i,j=0,1,…,k−1,(d_i,Hd_j)=0\ \ (i\ne j),\qquad (d_i,Hd_i)>0,\qquad i,j=0,1,\dots,k-1,(di​,Hdj​)=0  (i=j),(di​,Hdi​)>0,i,j=0,1,…,k−1,

and

[d0,…,dk−1]=[g,Hg,…,Hk−1g].(A.23)[d_0,\dots,d_{k-1}]=[g,Hg,\dots,H^{k-1}g]. \tag{A.23}[d0​,…,dk−1​]=[g,Hg,…,Hk−1g].(A.23)

Then HHH is positive definite: (v,Hv)>0(v,Hv)>0(v,Hv)>0 for every v≠0v\ne0v=0.

The theorem is the linear-algebra core of Theorem 2.4: an HHH-conjugate family with positive curvature that spans the Krylov space of a vector meeting every eigenspace certifies positive definiteness.

Formalization Note The vectors did_idi​ are arbitrary, not necessarily CG directions, as on the page. "ggg has a nonzero projection on each eigenspace" is stated as: for every eigenvalue μ\muμ there is vvv with Hv=μvHv=\mu vHv=μv and (g,v)≠0(g,v)\ne0(g,v)=0; for symmetric HHH the orthogonal projection of ggg onto E(μ,H)E(\mu,H)E(μ,H) is nonzero exactly when ggg is not orthogonal to E(μ,H)E(\mu,H)E(μ,H). The number of distinct eigenvalues is the cardinality of {μ:∃v≠0, Hv=μv}\{\mu : \exists v\ne0,\ Hv=\mu v\}{μ:∃v=0, Hv=μv}, a finite set for an operator on a finite-dimensional space. The page prints the range "i≠j, i=0,…,k−1i\ne j,\ i=0,\dots,k-1i=j, i=0,…,k−1" in (A.22) with jjj's range implicit; it is read as i,j<ki,j<ki,j<k.

Preamble
import Mathlib
import Definitions.Def_TruncNewton_NegCurv_Setting
Formal statement
namespace TruncNewton.NegCurv

theorem theorem_A_5 {n : ℕ}
    (H : EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n)) (hH : IsSelfAdjoint H)
    (g : EuclideanSpace ℝ (Fin n))
    (hg : ∀ μ : ℝ, (∃ v, v ≠ 0 ∧ H v = μ • v) → ∃ v, H v = μ • v ∧ inner ℝ g v ≠ 0)
    (k : ℕ) (hk : k = Set.ncard {μ : ℝ | ∃ v, v ≠ 0 ∧ H v = μ • v})
    (d : ℕ → EuclideanSpace ℝ (Fin n))
    (hconj : ∀ i j, i < k → j < k → i ≠ j → inner ℝ (d i) (H (d j)) = 0)
    (hpos : ∀ i, i < k → 0 < inner ℝ (d i) (H (d i)))
    (hspan : Submodule.span ℝ (d '' Set.Iio k) =
      Submodule.span ℝ ((fun i => (H ^ i) g) '' Set.Iio k)) :
    ∀ v, v ≠ 0 → 0 < inner ℝ v (H v) := by sorry

end TruncNewton.NegCurv
Source
Dembo and Steihaug, Truncated-Newton algorithms for large-scale unconstrained optimization, Math. Programming 26 (1983), p. 210, Theorem A.5, (A.21)–(A.23)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 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