LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Bfgs trace and determinant identities give a matrix potential inequality

Statement

Let $B$ be SPD, $s \neq 0$ , and $y$ satisfy $d : = s^{T} y > 0$ . Let $B^{+}$ be the Hessian update of Bfgs curvature pairs and Hessian/inverse updates. Define $m_{s} : = \frac{s^{T} y}{∥ s ∥_{2}^{2}}, M_{s} : = \frac{∥ y ∥_{2}^{2}}{s^{T} y}, q : = \frac{s^{T} B s}{∥ s ∥_{2}^{2}}, η : = \frac{s^{T} B s}{∥ s ∥_{2} ∥ B s ∥_{2}} .$ Then $η > 0$ , $η \leq 1$ , and $tr (B^{+}) = tr (B) - \frac{∥ B s ∥_{2}^{2}}{s^{T} B s} + \frac{∥ y ∥_{2}^{2}}{s^{T} y}, \det (B^{+}) = \det (B) \frac{s^{T} y}{s^{T} B s} .$ The potential $ψ (B) : = tr (B) - \log \det (B)$ is well-defined and satisfies $ψ (B) \geq n$ . With $h (t) : = 1 - t + \log t$ for $t > 0$ , one has $h (t) \leq 0$ , with equality exactly at $t = 1$ ; $h$ is strictly increasing on $(0, 1)$ and strictly decreasing on $(1, \infty)$ , and $ψ (B^{+}) \leq ψ (B) + (M_{s} - \log m_{s} - 1) + h ⁣ (\frac{q}{η^{2}}) + \log η^{2} .$

Facts & Assumptions

Given: $B, s, y, d$ and the update in the Statement.

[F1]

Bfgs curvature pairs and Hessian/inverse updates: $B^{+} = B - B s s^{T} B / (s^{T} B s) + y y^{T} / (s^{T} y)$ .

[F2]

Bfgs updates preserve the secant equations, symmetry, and positive definiteness: $B^{+}$ is SPD whenever $B$ is SPD and $s^{T} y > 0$ .

[F3]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ and Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: for Euclidean vectors $u, v$ , $∣ u^{T} v ∣ \leq ∥ u ∥_{2} ∥ v ∥_{2}$ .

[F4]

A matrix admits a Cholesky factorisation with positive diagonal exactly when it is Hermitian positive definite, and that factor is unique: every real SPD matrix has a unique factorization $B = L L^{T}$ with $L$ lower triangular and positive diagonal.

[F5]

For same-sized finite square matrices over a commutative ring, $\det (A B) = \det (A) \det (B)$ and The determinant of a triangular matrix is the product of its diagonal entries: determinants multiply, and a triangular determinant is the product of its diagonal entries.

[F7]

For $n \geq 1$ , the determinant over a commutative ring by the Leibniz formula, and $∣ \det A ∣$ for a real matrix: the determinant is the Leibniz sum over permutations; applying the inverse permutation shows $\det (P^{T}) = \det (P)$ .

[F6]

The natural logarithm as the inverse of the exponential function and The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t: $\log$ is defined on $(0, \infty)$ and has derivative $1 / t$ there.

Proof

1.1F1algebra

The trace update follows by taking traces in [F1]: $tr (u v^{T}) = v^{T} u$ gives $tr (B s s^{T} B) = ∥ B s ∥_{2}^{2}$ and $tr (y y^{T}) = ∥ y ∥_{2}^{2}$ .

1.2givenF1F5F7algebraconstruct

For the determinant identity, choose an invertible matrix $P$ whose first column is $s$ ; such a basis extension is finite-dimensional. Put $B^{'} = P^{T} B P$ and $y^{'} = P^{T} y$ . Direct substitution into [F1], using $s^{'} = P^{- 1} s = e_{1}$ and the unchanged scalars $s^{T} B s$ and $s^{T} y$ , gives $B^{' +} = P^{T} B^{+} P$ . By [F5] and [F7], $\det (B^{' +}) / \det (B^{'}) = \det (B^{+}) / \det (B)$ , since both numerator and denominator acquire the same factor $\det (P)^{2}$ . In these coordinates write $B^{'} = (\begin{array}{cc} a & b^{T} \\ b & C \end{array}), y^{'} = (\begin{array}{c} d \\ z \end{array}), a = s^{T} B s, d = s^{T} y .$ The update becomes $B^{' +} = (\begin{array}{cc} d & z^{T} \\ z & C - b b^{T} / a + z z^{T} / d \end{array}) .$ The Schur complement $S : = C - b b^{T} / a$ is SPD: for each nonzero $v$ , substituting $(- b^{T} v / a, v)$ into the quadratic form of $B^{'}$ gives $v^{T} S v > 0$ . The factorizations $B^{'} = (\begin{array}{cc} 1 & 0 \\ b / a & I \end{array}) (\begin{array}{cc} a & b^{T} \\ 0 & S \end{array}), B^{' +} = (\begin{array}{cc} 1 & 0 \\ z / d & I \end{array}) (\begin{array}{cc} d & z^{T} \\ 0 & S \end{array})$ show $\det (B^{'}) = a \det (S)$ and $\det (B^{' +}) = d \det (S)$ : the lower factors have determinant $1$ by [F5], and the upper block factors have those determinants by expanding the Leibniz sum along their first columns. If $n = 1$ , take the empty Schur complement determinant to be $1$ . Therefore $\det (B^{+}) / \det (B) = d / a = s^{T} y / (s^{T} B s)$ .

1.3F4F6algebra

By [F4], write $B = L L^{T}$ with positive diagonal entries $l_{i i}$ . Then $tr (B) = \sum_{i \geq j} l_{i j}^{2}$ and $\det (B) = \prod_{i} l_{i i}^{2} > 0$ . Consequently $ψ (B) = \sum_{i > j} l_{i j}^{2} + \sum_{i} (l_{i i}^{2} - 2 \log l_{i i}) \geq n,$ because $u - 1 - \log u \geq 0$ for $u > 0$ . This scalar inequality follows from the derivative $1 - 1 / u$ , whose sign changes from negative to positive at $u = 1$ .

1.4givenF2F3F6algebra

For $h (t) = 1 - t + \log t$ , the derivative is $- 1 + 1 / t$ , positive for $0 < t < 1$ and negative for $t > 1$ , so $h (t) \leq h (1) = 0$ . Also $s^{T} B s > 0$ and $B s \neq 0$ , so $η > 0$ ; [F3] gives $η \leq 1$ .

2.1F1step 1.1step 1.2step 1.4algebra∎

Set $u : = q / η^{2}$ . From the definitions, $u = ∥ B s ∥_{2}^{2} / (s^{T} B s)$ . Steps 1.1 and 1.2 therefore give $ψ (B^{+}) = ψ (B) + M_{s} - u - \log m_{s} + \log q = ψ (B) + (M_{s} - \log m_{s} - 1) + h (u) + \log η^{2} .$ This is the asserted identity, hence the stated inequality by step 1.4.

Depends on

Used by

Dependency tree · two levels

50 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Jorge Nocedal and Stephen J. Wright, Numerical Optimization, 2nd ed. (standard reference, not scraped)
Dong C. Liu and Jorge Nocedal, On the limited memory BFGS method for large scale optimization (standard reference, not scraped)