Proof of Lemma (2.1), (13), p. 174 — inverse of the updated matrix A_k*; A_k* is positive definite
ProvedEllipsoidGLS.Rounded.inv_AstarLet , let be a symmetric positive definite real matrix and let be nonzero. Put and
the matrix update of the rounded ellipsoid method. Then is positive definite and
This explicit inverse is what the paper uses to control the smallest eigenvalue of the next matrix (Lemma (2.1)) and to verify that the new ellipsoid contains the retained part of the body (Lemma (2.3)).
Formalization Note Positive definiteness is Mathlib's Matrix.PosDef (over it includes symmetry), and is Mathlib's matrix inverse; the conclusion asserts the formula for the genuine inverse, since is shown nonsingular. The page states (13) for the step's matrix and cut vector ; here it is stated for an arbitrary positive definite and nonzero , which is the content of the computation.
import Mathlib import Definitions.Def_LinearOptimization_Ellipsoid import Definitions.Def_EllipsoidGLS_Rounded_Basic import Definitions.Def_EllipsoidGLS_Rounded_Run
namespace EllipsoidGLS.Rounded
open Matrix
theorem inv_Astar {n : ℕ} (hn : 2 ≤ n) (A : Matrix (Fin n) (Fin n) ℝ) (hA : A.PosDef)
(a : Fin n → ℝ) (ha : a ≠ 0) :
(Astar A a).PosDef ∧
(Astar A a)⁻¹ = (2 * (n : ℝ) ^ 2 / (2 * (n : ℝ) ^ 2 + 3)) •
(A⁻¹ + ((2 / ((n : ℝ) - 1)) * (a ⬝ᵥ A.mulVec a)⁻¹) • vecMulVec a a) := by sorry
end EllipsoidGLS.Rounded
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.