Matrix algorithms
The catalogue's first page explains what each entry shows.
Chapter 8 · Triangular systems all chapters
Definitions, theorems and lemmas
Corollary 8.11
μ-form for lower triangular M-matrices and
b ≥ 0.Lean statement
theorem higham8_11_mmatrix_forwardSub_relative_error (fp : FPModel) (n : ℕ) (L L_inv : Fin n → Fin n → ℝ) (x b : Fin n → ℝ) (hLT : ∀ i j : Fin n, i.val < j.val → L i j = 0) (hL_diag_pos : ∀ i : Fin n, 0 < L i i) (hL_offdiag : ∀ i j : Fin n, j.val < i.val → L i j ≤ 0) (hInv : IsInverse n L L_inv) (hTx : ∀ i, ∑ j : Fin n, L i j * x j = b i) (hb : ∀ i, 0 ≤ b i) (hn : gammaValid fp n) (hn1 : gammaValid fp (n + 1)) (h2n : gammaValid fp (2 * n)) : let x_hat := fl_forwardSub fp n L b (∀ i, 0 ≤ x i) ∧ (∀ i, 0 ≤ x_hat i) ∧ (∀ i, |x i - x_hat i| ≤ mu fp n i.val * |x i|)higham8_
11_ · 1 more declaration under this itemmmatrix_ forward Sub_ relative_ error Lemma 8.2
Row-spec form for Algorithm 8.1.
Lean statement
theorem higham8_2_backSub_row_spec (fp : FPModel) (n : ℕ) (U : Fin n → Fin n → ℝ) (b : Fin n → ℝ) (hU : ∀ i, U i i ≠ 0) (hn : gammaValid fp n) : BackSubRowSpec fp n U b (fl_backSub fp n U b)higham8_
2_ · 3 more declarations under this itemback Sub_ row_ spec Lemma 8.4
Lemma 8.4 (Higham, 2nd ed., §8.1): order-independent backward error of
ŷ = fl((∑ wᵢ)/bₖ)when then-term sum is evaluated in any order (encoded by an arbitrary summation treet). With the distinguished summandw p(Higham'sc) kept unperturbed,bₖ ŷ (1 + θ₀) = ∑ᵢ wᵢ (1 + θᵢ)with every|θ| ≤ γ_nandθ p = 0. Unlikehigham8_5_backSub_backward_error, which fixes the repository evaluation order, this is the sharp order-independent statement underlying Theorem 8.5. It is proved from the pivot-normalised summation-tree backward errorSumTree.backward_error_pivot.Lean statement
theorem higham8_4_anyOrder_backwardError (fp : FPModel) {n : ℕ} (t : SumTree n) (ht : gammaValid fp n) (w : Fin n → ℝ) (p : Fin n) (bk : ℝ) (hbk : bk ≠ 0) : ∃ (θ₀ : ℝ) (θ : Fin n → ℝ), |θ₀| ≤ gamma fp n ∧ θ p = 0 ∧ (∀ i, |θ i| ≤ gamma fp n) ∧ bk * fp.fl_div (t.eval fp w) bk * (1 + θ₀) = ∑ i : Fin n, w i * (1 + θ i)higham8_
4_ · 1 more declaration under this itemany Order_ backward Error Lemma 8.6
Diagonal-dominance bound for
|U⁻¹||U|.Lean statement
theorem higham8_6_inv_abs_mul_bound_diagDom (n : ℕ) (U U_inv : Fin n → Fin n → ℝ) (hDD : IsDiagDominantUpper n U) (hInv : IsInverse n U U_inv) : ∀ i j : Fin n, i.val ≤ j.val → ∑ k : Fin n, |U_inv i k| * |U k j| ≤ 2 ^ (j.val - i.val)higham8_
6_ · 1 more declaration under this iteminv_ abs_ mul_ bound_ diag Dom Lemma 8.9
Inequality part:
cond(T,x) ≤ cond(M(T),x)once|T⁻¹| ≤ M(T)⁻¹andM(T)⁻¹ ≥ 0are known.Lean statement
theorem higham8_9_condAtSolution_le_comparisonMatrix (n : ℕ) (hn : 0 < n) (T T_inv M_inv : Fin n → Fin n → ℝ) (x : Fin n → ℝ) (habsInv : ∀ i j : Fin n, |T_inv i j| ≤ M_inv i j) (hM_nonneg : ∀ i j : Fin n, 0 ≤ M_inv i j) : ch7SkeelCondAtSolutionInf n hn T T_inv x ≤ ch7SkeelCondAtSolutionInf n hn (comparisonMatrix n T) M_inv xhigham8_
9_ · 3 more declarations under this itemcond At Solution_ le_ comparison Matrix Theorem 8.3
Algorithm 8.1 with Higham's row-specific constants.
Lean statement
theorem higham8_3_backSub_backward_error (fp : FPModel) (n : ℕ) (U : Fin n → Fin n → ℝ) (b : Fin n → ℝ) (hU : ∀ i, U i i ≠ 0) (hUT : ∀ i j : Fin n, j.val < i.val → U i j = 0) (hn : gammaValid fp n) : ∃ ΔU : Fin n → Fin n → ℝ, (∀ i, |ΔU i i| ≤ gamma fp (n - i.val) * |U i i|) ∧ (∀ i j, i.val < j.val → |ΔU i j| ≤ gamma fp (j.val - i.val) * |U i j|) ∧ (∀ i j, j.val < i.val → ΔU i j = 0) ∧ ∀ i, ∑ j : Fin n, (U i j + ΔU i j) * fl_backSub fp n U b j = b ihigham8_
3_ · 1 more declaration under this itemback Sub_ backward_ error Theorem 8.5
Upper-triangular back-substitution specialization.
Lean statement
theorem higham8_5_backSub_backward_error (fp : FPModel) (n : ℕ) (U : Fin n → Fin n → ℝ) (b : Fin n → ℝ) (hU : ∀ i, U i i ≠ 0) (hUT : ∀ i j : Fin n, j.val < i.val → U i j = 0) (hn : gammaValid fp n) : ∃ ΔU : Fin n → Fin n → ℝ, (∀ i j, |ΔU i j| ≤ gamma fp n * |U i j|) ∧ ∀ i, ∑ j : Fin n, (U i j + ΔU i j) * fl_backSub fp n U b j = b ihigham8_
5_ · 5 more declarations under this itemback Sub_ backward_ error Theorem 8.7
Componentwise forward error under condition (8.5).
Lean statement
theorem higham8_7_backSub_forward_error_diagDom (fp : FPModel) (n : ℕ) (U U_inv : Fin n → Fin n → ℝ) (x b : Fin n → ℝ) (hDD : IsDiagDominantUpper n U) (hInv : IsInverse n U U_inv) (hTx : ∀ i, ∑ j : Fin n, U i j * x j = b i) (hn : gammaValid fp n) : let x_hat := fl_backSub fp n U b ∀ i : Fin n, |x i - x_hat i| ≤ 2 ^ (n - i.val) * gamma fp n * Finset.sup' (Finset.univ.filter (fun j : Fin n => i.val ≤ j.val)) ⟨i, by simp [Finset.mem_filter]⟩ (fun j => |x_hat j|)higham8_
7_ · 1 more declaration under this itemback Sub_ forward_ error_ diag Dom Theorem 8.10
Formalized with Higham's exact
μrecurrence rather than an informalO(u^2)abbreviation.Lean statement
theorem higham8_10_forwardSub_forward_error_mu_bound (fp : FPModel) (n : ℕ) (L L_inv M_inv : Fin n → Fin n → ℝ) (x b : Fin n → ℝ) (hL_diag : ∀ i : Fin n, L i i ≠ 0) (hLT : ∀ i j : Fin n, i.val < j.val → L i j = 0) (hInv : IsInverse n L L_inv) (hM_RInv : IsRightInverse n (comparisonMatrix n L) M_inv) (hM_inv_lt : ∀ i j : Fin n, i.val < j.val → M_inv i j = 0) (hTx : ∀ i, ∑ j : Fin n, L i j * x j = b i) (hn : gammaValid fp n) (hn1 : gammaValid fp (n + 1)) : let x_hat := fl_forwardSub fp n L b let y := fun i => ∑ j : Fin n, M_inv i j * |b j| ∀ i : Fin n, |x i - x_hat i| ≤ mu fp n i.val * y ihigham8_
10_ · 1 more declaration under this itemforward Sub_ forward_ error_ mu_ bound Theorem 8.12
First comparison-matrix inverse inequality.
Lean statement
theorem higham8_12_abs_inv_le_comparison_inv (n : ℕ) (U U_inv M_inv : Fin n → Fin n → ℝ) (hUT : ∀ i j : Fin n, j.val < i.val → U i j = 0) (hU_diag : ∀ i : Fin n, U i i ≠ 0) (hInv : IsInverse n U U_inv) (hM_RInv : IsRightInverse n (comparisonMatrix n U) M_inv) (hM_inv_ut : ∀ i j : Fin n, j.val < i.val → M_inv i j = 0) : ∀ i j : Fin n, |U_inv i j| ≤ M_inv i jhigham8_
12_ · 8 more declarations under this itemabs_ inv_ le_ comparison_ inv Theorem 8.14
Packaged
∞/1/2norm chains in the source notation using the minimum diagonal magnitude.Lean statement
theorem higham8_14_full_norm_chain (n : ℕ) (hn : 0 < n) (U U_inv M_inv W_inv : Fin n → Fin n → ℝ) (i0 : Fin n) {β : ℝ} (hUT : ∀ i j : Fin n, j.val < i.val → U i j = 0) (hU_diag : ∀ i : Fin n, U i i ≠ 0) (hInv : IsInverse n U U_inv) (hM_RInv : IsRightInverse n (comparisonMatrix n U) M_inv) (hW_RInv : IsRightInverse n (higham8_12_WMatrix n U) W_inv) (hβ : 0 ≤ β) (hβ1 : β ≤ 1) (hβ_bound : ∀ i j : Fin n, i.val < j.val → |U i j| ≤ β * |U i i|) : let α : ℝ := Finset.inf' Finset.univ ⟨i0, Finset.mem_univ i0⟩ (fun k : Fin n => |U k k|) (1 / α ≤ infNorm U_inv ∧ infNorm U_inv ≤ infNorm M_inv ∧ infNorm M_inv ≤ infNorm W_inv ∧ infNorm W_inv ≤ infNorm (higham8_12_ZInvFormula n α β) ∧ infNorm (higham8_12_ZInvFormula n α β) ≤ (1 / α) * (2 : ℝ) ^ (n - 1)) ∧ (1 / α ≤ oneNorm U_inv ∧ oneNorm U_inv ≤ oneNorm M_inv ∧ oneNorm M_inv ≤ oneNorm W_inv ∧ oneNorm W_inv ≤ oneNorm (higham8_12_ZInvFormula n α β) ∧ oneNorm (higham8_12_ZInvFormula n α β) ≤ (1 / α) * (2 : ℝ) ^ (n - 1)) ∧ (1 / α ≤ complexMatrixOp2 (realRectToCMatrix U_inv) ∧ complexMatrixOp2 (realRectToCMatrix U_inv) ≤ complexMatrixOp2 (realRectToCMatrix M_inv) ∧ complexMatrixOp2 (realRectToCMatrix M_inv) ≤ complexMatrixOp2 (realRectToCMatrix W_inv) ∧ complexMatrixOp2 (realRectToCMatrix W_inv) ≤ complexMatrixOp2 (realRectToCMatrix (higham8_12_ZInvFormula n α β)) ∧ complexMatrixOp2 (realRectToCMatrix (higham8_12_ZInvFormula n α β)) ≤ (1 / α) * (2 : ℝ) ^ (n - 1))higham8_
14_ · 5 more declarations under this itemfull_ norm_ chain
Equations and other results
Equation (8.14)
Producer bridge. The literal rounded fan-in executor has exactly the source's perturbation-tree form. In addition to constructing all five perturbations, the theorem exposes certified local envelopes. The two composite envelopes retain the harmless higher-order terms explicitly: the matrix-product residual plus the backward error of the subsequent matrix-vector action. This theorem removes the former gap between the symbolic
(8.14)expression and an actual sequence offl_matMul/fl_matVecoperations.Lean statement
theorem higham8_14_fanIn7Executor_eq_roundedApply (fp : FPModel) (n : ℕ) (M1 M2 M3 M4 M5 M6 M7 : Fin n → Fin n → ℝ) (b : Fin n → ℝ) (hn : gammaValid fp n) : ∃ Δ1 Δ32 Δ54 Δ76 Δ7654 : Fin n → Fin n → ℝ, higham8_14_fanIn7Executor fp n M1 M2 M3 M4 M5 M6 M7 b = higham8_14_fanIn7RoundedApply n M1 M2 M3 M4 M5 M6 M7 Δ1 Δ32 Δ54 Δ76 Δ7654 b ∧ (∀ i j, |Δ1 i j| ≤ gamma fp n * |M1 i j|) ∧ (∀ i j, |Δ32 i j| ≤ gamma fp n * (∑ k : Fin n, |M3 i k| * |M2 k j|) + gamma fp n * |fl_matMul fp n n n M3 M2 i j|) ∧ (∀ i j, |Δ54 i j| ≤ gamma fp n * (∑ k : Fin n, |M5 i k| * |M4 k j|)) ∧ (∀ i j, |Δ76 i j| ≤ gamma fp n * (∑ k : Fin n, |M7 i k| * |M6 k j|)) ∧ (∀ i j, |Δ7654 i j| ≤ gamma fp n * (∑ k : Fin n, |fl_matMul fp n n n M7 M6 i k| * |fl_matMul fp n n n M5 M4 k j|) + gamma fp n * |fl_matMul fp n n n (fl_matMul fp n n n M7 M6) (fl_matMul fp n n n M5 M4) i j|)higham8_
14_ · 1 more declaration under this itemfan In7Executor_ eq_ rounded Apply Equation (8.17)
Literal-executor all-orders backward-error form. The actual
(8.14)executor and(8.16)residual norm bound construct a rank-one backward perturbation with the corresponding explicit raw envelope.Lean statement
theorem higham8_17_fanIn7Executor_backward_error_bound (fp : FPModel) (n : ℕ) (L M1 M2 M3 M4 M5 M6 M7 : Fin n → Fin n → ℝ) (b : Fin n → ℝ) (hn : gammaValid fp n) (hsolve : matMulVec n L (higham8_13_fanIn7Apply n M1 M2 M3 M4 M5 M6 M7 b) = b) (j0 : Fin n) (hxj0 : higham8_14_fanIn7Executor fp n M1 M2 M3 M4 M5 M6 M7 b j0 ≠ 0) : ∃ ΔL : Fin n → Fin n → ℝ, matMulVec n (fun i j => L i j + ΔL i j) (higham8_14_fanIn7Executor fp n M1 M2 M3 M4 M5 M6 M7 b) = b ∧ infNorm ΔL ≤ infNormVec (matMulVec n (absMatrix n L) (fun k => ((1 + gamma fp n) ^ 7 - 1) * higham8_18_fanIn7AbsApply n M1 M2 M3 M4 M5 M6 M7 b k)) / |higham8_14_fanIn7Executor fp n M1 M2 M3 M4 M5 M6 M7 b j0|higham8_
17_ · 1 more declaration under this itemfan In7Executor_ backward_ error_ bound Equation (8.18)
Literal-executor all-orders form. The actual seven rounded operations satisfy the source's product-of-absolute-matrices forward envelope. The exact coefficient
(1+γₙ)^7-1retains all higher-order terms; its first-order term is7γₙ, matching the source'sd'ₙ u + O(u²)form. No relative perturbation of an intermediate product is assumed, so exact cancellation inM3*M2,M5*M4, orM7*M6is allowed.Lean statement
theorem higham8_18_fanIn7Executor_forward_componentwise_bound (fp : FPModel) (n : ℕ) (M1 M2 M3 M4 M5 M6 M7 : Fin n → Fin n → ℝ) (b : Fin n → ℝ) (hn : gammaValid fp n) : ∀ i : Fin n, |higham8_14_fanIn7Executor fp n M1 M2 M3 M4 M5 M6 M7 b i - higham8_13_fanIn7Apply n M1 M2 M3 M4 M5 M6 M7 b i| ≤ ((1 + gamma fp n) ^ 7 - 1) * higham8_18_fanIn7AbsApply n M1 M2 M3 M4 M5 M6 M7 b ihigham8_
18_ · 2 more declarations under this itemfan In7Executor_ forward_ componentwise_ bound Equation (8.19)
Literal-executor relative
∞-norm form.Lean statement
theorem higham8_19_fanIn7Executor_forward_relative_infNorm_bound (fp : FPModel) (n : ℕ) (M1 M2 M3 M4 M5 M6 M7 : Fin n → Fin n → ℝ) (b : Fin n → ℝ) (hn : gammaValid fp n) (hx : 0 < infNormVec (higham8_13_fanIn7Apply n M1 M2 M3 M4 M5 M6 M7 b)) : infNormVec (fun i => higham8_14_fanIn7Executor fp n M1 M2 M3 M4 M5 M6 M7 b i - higham8_13_fanIn7Apply n M1 M2 M3 M4 M5 M6 M7 b i) / infNormVec (higham8_13_fanIn7Apply n M1 M2 M3 M4 M5 M6 M7 b) ≤ infNormVec (fun i => ((1 + gamma fp n) ^ 7 - 1) * higham8_18_fanIn7AbsApply n M1 M2 M3 M4 M5 M6 M7 b i) / infNormVec (higham8_13_fanIn7Apply n M1 M2 M3 M4 M5 M6 M7 b)higham8_
19_ · 1 more declaration under this itemfan In7Executor_ forward_ relative_ inf Norm_ bound
Chapter 9 · LU factorization and linear equations all chapters
Theorem 9.1
Theorem 9.1 support, uniqueness of an exact LU certificate once the pivots are nonzero. The proof follows the Doolittle recurrences column by column: previous columns of
Land rows ofUdetermine the next row ofU, then the nonzero pivot determines the next column ofL. This is still only the uniqueness half of Theorem 9.1; it does not construct factors from leading principal minors.Lean statement
theorem higham9_1_lu_unique_of_pivots_ne_zero {n : ℕ} {A L₁ U₁ L₂ U₂ : Fin n → Fin n → ℝ} (hLU₁ : LUFactSpec n A L₁ U₁) (hLU₂ : LUFactSpec n A L₂ U₂) (hU₁diag : ∀ k : Fin n, U₁ k k ≠ 0) : L₁ = L₂ ∧ U₁ = U₂higham9_
1_ · 10 more declarations under this itemlu_ unique_ of_ pivots_ ne_ zero Theorem 9.3
Generic LU backward-error-certificate form.
Lean statement
theorem higham9_3_lu_backward_error_gamma (fp : FPModel) (n : ℕ) (A L_hat U_hat : Fin n → Fin n → ℝ) (hn : gammaValid fp n) (hLU : LUBackwardError n A L_hat U_hat (gamma fp n)) : ∃ ΔA : Fin n → Fin n → ℝ, (∀ i j, |ΔA i j| ≤ gamma fp n * ∑ k : Fin n, |L_hat i k| * |U_hat k j|) ∧ (∀ i j, ∑ k : Fin n, L_hat i k * U_hat k j = A i j + ΔA i j)higham9_
3_ · 37 more declarations under this itemlu_ backward_ error_ gamma Theorem 9.5
Source-shaped max-entry growth-factor form. This removes the free norm-growth bridge hypothesis from
higham9_5_wilkinson_source_bound_of_growth_bridge: a bound on Higham's max-entry growth factor for the finalU_hatimplies the required∞-norm bridge by elementary row-sum/max-entry inequalities.Lean statement
theorem higham9_5_wilkinson_source_bound_of_entry_growth (fp : FPModel) (n : ℕ) (hn_pos : 0 < n) (A L_hat U_hat : Fin n → Fin n → ℝ) (b : Fin n → ℝ) (ρ : ℝ) (hAmax : 0 < maxEntryNorm hn_pos A) (hρ : 0 ≤ ρ) (hρU : growthFactorEntry hn_pos A U_hat hAmax ≤ ρ) (hL_diag : ∀ i : Fin n, L_hat i i ≠ 0) (hU_diag : ∀ i : Fin n, U_hat i i ≠ 0) (hLU : LUBackwardError n A L_hat U_hat (gamma fp n)) (hn : gammaValid fp n) (hn3 : gammaValid fp (3 * n)) (hL_bound : ∀ i j : Fin n, |L_hat i j| ≤ 1) : let y_hat := fl_forwardSub fp n L_hat b let x_hat := fl_backSub fp n U_hat y_hat ∃ ΔA : Fin n → Fin n → ℝ, (infNorm ΔA ≤ (↑n) ^ 2 * gamma fp (3 * n) * ρ * infNorm A) ∧ (∀ i, ∑ j : Fin n, (A i j + ΔA i j) * x_hat j = b i)higham9_
5_ · 21 more declarations under this itemwilkinson_ source_ bound_ of_ entry_ growth Theorem 9.8
Real max-entry
ρ ≥ θbridge. If the final pivot supplies Higham's inverse-entry witness|u|⁻¹ ≤ βand|u|is bounded by the largest entry reached inU, thengrowthFactorEntry A U ≥ (αβ)⁻¹.Lean statement
theorem higham9_8_growth_factor_ge_theta_real {n : ℕ} (hn : 0 < n) (A A_inv U : Fin n → Fin n → ℝ) (hA : 0 < maxEntryNorm hn A) (hAinv : 0 < maxEntryNorm hn A_inv) (u : ℝ) (hu_pos : 0 < |u|) (hu_entry : |u| ≤ maxEntryNorm hn U) (hu_inv_le : |u|⁻¹ ≤ maxEntryNorm hn A_inv) : 1 / (maxEntryNorm hn A * maxEntryNorm hn A_inv) ≤ growthFactorEntry hn A U hAhigham9_
8_ · 28 more declarations under this itemgrowth_ factor_ ge_ theta_ real Theorem 9.9
Column diagonally dominant nonsingular matrices in dimensions one and two have exact no-pivot LU factors with unit-bounded lower entries and max-entry growth factor at most
2. This packages the explicit1 by 1base case with the verified2 by 2endpoint, matching the small-dimension closure pattern used for the Wilkinson/Foster growth families elsewhere in this chapter.Lean statement
theorem higham9_9_colDiagDominant_exists_LUFactSpec_growthFactorEntry_le_two_of_le_two {n : ℕ} (hn : 0 < n) (hle : n ≤ 2) (A : Fin n → Fin n → ℝ) (hDD : IsDiagDominant n A) (hdet : Matrix.det (Matrix.of A : Matrix (Fin n) (Fin n) ℝ) ≠ 0) : ∃ L U : Fin n → Fin n → ℝ, LUFactSpec n A L U ∧ (∀ i j : Fin n, |L i j| ≤ 1) ∧ ∃ hAmax : 0 < maxEntryNorm hn A, growthFactorEntry hn A U hAmax ≤ 2higham9_
9_ · 25 more declarations under this itemcol Diag Dominant_ exists_ LUFact Spec_ growth Factor Entry_ le_ two_ of_ le_ two Theorem 9.15
Componentwise LU perturbation identity.
Lean statement
theorem higham9_15_lu_perturbation_identity (n : ℕ) (A L U δA δL δU : Fin n → Fin n → ℝ) (hLU : ∀ i j, ∑ k : Fin n, L i k * U k j = A i j) (hPerturbed : ∀ i j, ∑ k : Fin n, (L i k + δL i k) * (U k j + δU k j) = A i j + δA i j) : ∀ i j, δA i j = ∑ k : Fin n, L i k * δU k j + ∑ k : Fin n, δL i k * U k j + ∑ k : Fin n, δL i k * δU k jhigham9_
15_ · 127 more declarations under this itemlu_ perturbation_ identity
Chapter 10 · Cholesky factorization all chapters
Lemma 10.10
Lemma 10.10 / equation (10.16) in honest form: the perturbed Schur complement equals the unperturbed one plus Higham's first-order term
Ē = E₂₂ − E₂₁MA₁₂ − A₂₁ME₁₂ + A₂₁ME₁₁MA₁₂plus a remainder that is entrywise bounded by an explicit polynomial timesε²— the exact statement behind the source'sS(A+E) = S(A) + Ē + O(‖E‖²). The leading-block inverses enter through genuine inverse equations (M A₁₁ = 1up to the resolvent identity), not assumed bounds on the conclusion.Lean statement
theorem higham10_10_schur_complement_perturbation {k m : ℕ} (A11 E11 M X : Matrix (Fin k) (Fin k) ℝ) (A21 E21 : Matrix (Fin m) (Fin k) ℝ) (A12 E12 : Matrix (Fin k) (Fin m) ℝ) (A22 E22 : Matrix (Fin m) (Fin m) ℝ) (hM : M * A11 = 1) (hXi : (A11 + E11) * X = 1) (α μ χ ε : ℝ) (hα : 0 ≤ α) (hμ : 0 ≤ μ) (hχ : 0 ≤ χ) (hε : 0 ≤ ε) (hA21 : ∀ i j, |A21 i j| ≤ α) (hA12 : ∀ i j, |A12 i j| ≤ α) (hE21 : ∀ i j, |E21 i j| ≤ ε) (hE12 : ∀ i j, |E12 i j| ≤ ε) (hE11 : ∀ i j, |E11 i j| ≤ ε) (hMb : ∀ i j, |M i j| ≤ μ) (hXb : ∀ i j, |X i j| ≤ χ) : ∃ R : Matrix (Fin m) (Fin m) ℝ, (A22 + E22) - (A21 + E21) * X * (A12 + E12) = (A22 - A21 * M * A12) + (E22 - E21 * M * A12 - A21 * M * E12 + A21 * (M * E11 * M) * A12) + R ∧ ∀ i j : Fin m, |R i j| ≤ ((k : ℝ) ^ 2 * μ + (k : ℝ) ^ 6 * α ^ 2 * μ ^ 2 * χ + 2 * ((k : ℝ) ^ 4 * α * μ * χ) + (k : ℝ) ^ 4 * μ * χ * ε) * ε ^ 2higham10_
10_ · 2 more declarations under this itemschur_ complement_ perturbation Lemma 10.11
Source-strength pivot preservation. The finite no-ties and nonbreakdown hypotheses alone produce a positive radius. Any perturbation whose operator 2-norm is at most that radius preserves all first-
rpivots, for bothA + EandA - E.Lean statement
theorem higham10_11_cp_pivot_sequence_stable_of_noTies_two_sided {n : ℕ} (hn : 0 < n) (A : Fin n → Fin n → ℝ) (r : ℕ) (hpivot : ∀ t : ℕ, t < r → 0 < cpState hn A t (cpPivot hn A t) (cpPivot hn A t)) (hnoTies : Higham10_11NoTies hn A r) : ∃ ε₀ : ℝ, 0 < ε₀ ∧ ∀ E : Fin n → Fin n → ℝ, opNorm2 E ≤ ε₀ → (∀ s : ℕ, s < r → cpPivot hn A s = cpPivot hn (fun i j => A i j + E i j) s) ∧ (∀ s : ℕ, s < r → cpPivot hn A s = cpPivot hn (fun i j => A i j - E i j) s)higham10_
11_ · 7 more declarations under this itemcp_ pivot_ sequence_ stable_ of_ no Ties_ two_ sided Lemma 10.12
Lemma 10.12 core (Higham §10.3): for a positive semidefinite block matrix with leading block
A₁₁inverted in action byM, the solve vectorWv = M A₁₂ vsatisfiesλ_min(A₁₁) ‖Wv‖₂² ≤ vᵀ A₂₂ v— the quadratic-form content ofWᵀ A₁₁ W ⪯ A₂₂, sharpened through the Rayleigh bound. Choosingu = −Wvin the block-split quadratic form gives(Wv)ᵀA₁₁(Wv) ≤ vᵀA₂₂v; Rayleigh converts the left side.Lean statement
theorem higham10_12_psd_w_action_bound {k m : ℕ} (hk : 0 < k) (A : Fin (k + m) → Fin (k + m) → ℝ) (hPSD : IsPosSemiDef (k + m) A) (M : Fin k → Fin k → ℝ) (hSym : IsSymmetricFiniteMatrix (fun i j : Fin k => A (Fin.castAdd m i) (Fin.castAdd m j))) (hMinv : ∀ (w : Fin k → ℝ) (i : Fin k), ∑ j : Fin k, A (Fin.castAdd m i) (Fin.castAdd m j) * (∑ t : Fin k, M j t * w t) = w i) (v : Fin m → ℝ) : finiteMinEigenvalue hk (fun i j : Fin k => A (Fin.castAdd m i) (Fin.castAdd m j)) hSym * vecNorm2Sq (fun i : Fin k => ∑ t : Fin k, M i t * (∑ j : Fin m, A (Fin.castAdd m t) (Fin.natAdd k j) * v j)) ≤ ∑ i : Fin m, ∑ j : Fin m, v i * A (Fin.natAdd k i) (Fin.natAdd k j) * v jhigham10_
12_ · 2 more declarations under this itempsd_ w_ action_ bound Lemma 10.13
Complete-pivoting bound on
‖W‖_F²with Higham's(n−r)(4^r−1)/3constant, in honest form: for anr × rupper-triangular blockUwith positive diagonal whose rows are pivot-dominated on and right of the diagonal — exactly what complete pivoting guarantees via the (10.13) column-tail invariant (tail_invariant_entry_leapplied to the factor frompsd_pivoted_cholesky_exists_tail) — the solutionWofU W = Bwith pivot-dominated right-hand columnsB(the border blockR₁₂) satisfies∑_{i,j} W i j ² ≤ m (4^r − 1)/3,m = n − rborder columns.Lean statement
theorem higham10_13_complete_pivoting_w_bound {r m : ℕ} (U : Fin r → Fin r → ℝ) (B W : Fin r → Fin m → ℝ) (hupper : ∀ i j : Fin r, j.val < i.val → U i j = 0) (hdiag_pos : ∀ i : Fin r, 0 < U i i) (hentry : ∀ i j : Fin r, i.val ≤ j.val → |U i j| ≤ U i i) (hB : ∀ (i : Fin r) (j : Fin m), |B i j| ≤ U i i) (hsolve : ∀ (i : Fin r) (j : Fin m), ∑ k : Fin r, U i k * W k j = B i j) : ∑ j : Fin m, ∑ i : Fin r, W i j ^ 2 ≤ (m : ℝ) * (((4 : ℝ) ^ r - 1) / 3)higham10_
13_ · 2 more declarations under this itemcomplete_ pivoting_ w_ bound Theorem 10.1
Existence of the Cholesky factorization for real SPD matrices.
Lean statement
theorem higham10_1_cholesky_existence (n : ℕ) (A : Fin n → Fin n → ℝ) (hSPD : IsSymPosDef n A) : ∃ R : Fin n → Fin n → ℝ, higham10_1_CholeskyFactSpec n A Rhigham10_
1_ · 2 more declarations under this itemcholesky_ existence Theorem 10.3
R_hat^T R_hat = A + ΔA, with|ΔA| <= γ_{n+1} |R_hat^T| |R_hat|componentwise.Lean statement
theorem higham10_3_cholesky_backward_error (fp : FPModel) (n : ℕ) (A R_hat : Fin n → Fin n → ℝ) (hn1 : gammaValid fp (n + 1)) (hChol : higham10_2_CholeskyBackwardError n A R_hat (gamma fp (n + 1))) : ∃ ΔA : Fin n → Fin n → ℝ, (∀ i j, |ΔA i j| ≤ gamma fp (n + 1) * ∑ k : Fin n, |R_hat k i| * |R_hat k j|) ∧ (∀ i j, ∑ k : Fin n, R_hat k i * R_hat k j = A i j + ΔA i j)higham10_
3_ · 2 more declarations under this itemcholesky_ backward_ error Theorem 10.4
Cholesky factorization plus the two triangular solves gives
(A + ΔA)x_hat = b, with Higham's absorbedγ_{3n+1}componentwise bound.Lean statement
theorem higham10_4_cholesky_solve_backward_error (fp : FPModel) (n : ℕ) (A R_hat : Fin n → Fin n → ℝ) (b : Fin n → ℝ) (hR_diag : ∀ i : Fin n, R_hat i i ≠ 0) (hChol : higham10_2_CholeskyBackwardError n A R_hat (gamma fp (n + 1))) (hn1 : gammaValid fp (n + 1)) (hn3 : gammaValid fp (3 * n + 1)) : let R_hatT := fun i j : Fin n => R_hat j i let y_hat := fl_forwardSub fp n R_hatT b let x_hat := fl_backSub fp n R_hat y_hat ∃ ΔA : Fin n → Fin n → ℝ, (∀ i j, |ΔA i j| ≤ gamma fp (3 * n + 1) * ∑ k : Fin n, |R_hat k i| * |R_hat k j|) ∧ (∀ i, ∑ j : Fin n, (A i j + ΔA i j) * x_hat j = b i)higham10_
4_ · 1 more declaration under this itemcholesky_ solve_ backward_ error Theorem 10.6
Actual source closure. For an SPD input, a successful concrete Algorithm 10.2 run and its two concrete rounded triangular solves produce Higham's displayed scaled forward error bound with
ε = n γ_(3n+1) / (1 - γ_(n+1))and the literal spectral condition number ofH = D⁻¹ A D⁻¹. No factorization-error, solve-error, inverse-action, or operator-norm certificate is an input to this theorem.Lean statement
theorem higham10_6_actual_source_closed (fp : FPModel) (n : ℕ) (hn : 0 < n) (A : Fin n → Fin n → ℝ) (b x : Fin n → ℝ) (hSPD : IsSymPosDef n A) (hn1 : gammaValid fp (n + 1)) (hn3 : gammaValid fp (3 * n + 1)) (hgamma1 : gamma fp (n + 1) < 1) (hsuccess : ∀ j : Fin n, 0 < fl_cholPivot fp n A j) (hAx : matMulVec n A x = b) (hsmall : higham10SourceKappa2 A * ((n : ℝ) * (gamma fp (3 * n + 1) / (1 - gamma fp (n + 1)))) < 1) : let Rhat := fl_cholesky fp n A let yhat := fl_forwardSub fp n (fun i j : Fin n => Rhat j i) b let xhat := fl_backSub fp n Rhat yhat vecNorm2 (fun i => Real.sqrt (A i i) * xhat i - Real.sqrt (A i i) * x i) ≤ higham10SourceKappa2 A * ((n : ℝ) * (gamma fp (3 * n + 1) / (1 - gamma fp (n + 1)))) / (1 - higham10SourceKappa2 A * ((n : ℝ) * (gamma fp (3 * n + 1) / (1 - gamma fp (n + 1))))) * vecNorm2 (fun i => Real.sqrt (A i i) * x i)higham10_
6_ · 3 more declarations under this itemactual_ source_ closed Theorem 10.7
Theorem 10.7 (Demmel), exact source threshold for the concrete Algorithm 10.2 run (Higham, p. 200). If
λ_min(D⁻¹AD⁻¹) > n γ_{n+1}/(1-γ_{n+1}), every raw rounded Cholesky pivot is positive. No run-level or stage-level certificate is assumed: all defect bounds are constructed from the preceding pivots.Lean statement
theorem higham10_7_fl_cholesky_success_source (fp : FPModel) (n : ℕ) (hn0 : 0 < n) (A : Fin n → Fin n → ℝ) (hsym : ∀ i l : Fin n, A i l = A l i) (hAdiag : ∀ i : Fin n, 0 < A i i) (hn1 : gammaValid fp (n + 1)) (hγ1 : gamma fp (n + 1) < 1) (hH_sym : IsSymmetricFiniteMatrix (fun i l : Fin n => A i l / (Real.sqrt (A i i) * Real.sqrt (A l l)))) (hthresh : (n : ℝ) * (gamma fp (n + 1) / (1 - gamma fp (n + 1))) < finiteMinEigenvalue hn0 (fun i l : Fin n => A i l / (Real.sqrt (A i i) * Real.sqrt (A l l))) hH_sym) : ∀ j : Fin n, 0 < fl_cholPivot fp n A jhigham10_
7_ · 10 more declarations under this itemfl_ cholesky_ success_ source Theorem 10.14
Equation (10.22), literal family form. For a family of floating-point models whose unit roundoff tends to zero, this theorem bounds the operator 2-norm of the matrix produced by the literal truncated Cholesky executor. The leading coefficient is exactly the one in the book, and the remainder is the uniform family-level
O(u²)predicate. The hypotheses below are explicit small-roundoff radii ongammaand the actual source error; none assumes a bound on the final residual or trailing Schur block.Lean statement
theorem higham10_14_equation_10_22_family_of_success {ι : Type*} {l : Filter ι} {r s : ℕ} (F : ι → FPModel) (U : RoundoffFamily ι l) (hunit : ∀ t, (F t).u = U.unit t) (A : Fin (r + s) → Fin (r + s) → ℝ) (hr0 : 0 < r) (hPSD : IsPosSemiDef (r + s) A) (hrank : (Matrix.of A).rank = r) (hA11 : IsSymPosDef r (higham10_14_block11 A)) (hsuccess : ∀ t, ∀ q : Fin (r + s), q.val < r → 0 < fl_cholPivot (F t) (r + s) A q) (hhalf : ∀ t, ((r + 1 : ℕ) : ℝ) * U.unit t ≤ 1 / 2) (hgammaRadius : ∀ t, (r : ℝ) * gamma (F t) (r + 1) ≤ 1 / 2) (hlinearAbsorb : ∀ t, (gamma (F t) (r + 1) / (1 - (r : ℝ) * gamma (F t) (r + 1))) * ((r + s : ℕ) : ℝ) * (complexMatrixOp2 (realRectToCMatrix (higham10_14_W A)) + 1) ^ 2 ≤ 1 / 4) (hquadraticAbsorb : ∀ t, (gamma (F t) (r + 1) / (1 - (r : ℝ) * gamma (F t) (r + 1))) * ((r + s : ℕ) : ℝ) * higham10_14_schurQuadraticCoeff A * complexMatrixOp2 (realRectToCMatrix (higham10_14_sourceError (F t) A r (Nat.le_add_right r s))) ≤ 1 / 4) (hEone : ∀ t, complexMatrixOp2 (realRectToCMatrix (higham10_14_sourceError (F t) A r (Nat.le_add_right r s))) ≤ 1) (hinvRadius : ∀ t, complexMatrixOp2 (realRectToCMatrix (nonsingInv r (higham10_14_block11 A))) * complexMatrixOp2 (realRectToCMatrix (higham10_14_sourceError (F t) A r (Nat.le_add_right r s))) ≤ 1 / 2) : FamilyFirstOrderLe l U.unit (fun t => 2 * (r : ℝ) * gamma (F t) (r + 1) * complexMatrixOp2 (realRectToCMatrix A) * (complexMatrixOp2 (realRectToCMatrix (higham10_14_W A)) + 1) ^ 2) (fun t => complexMatrixOp2 (realRectToCMatrix (higham10_14_actualResidual (F t) A)))higham10_
14_ · 5 more declarations under this itemequation_ 10_ 22_ family_ of_ success
Chapter 11 · Symmetric indefinite and skew-symmetric systems all chapters
Definitions, theorems and lemmas
Algorithm 11.1
Bunch-Parlett α is a root of 4α² − α − 1 = 0. This algebraic identity characterizes α = (1 + √17)/8 as the solution that minimizes the worst-case element growth.
Lean statement
theorem bunch_parlett_alpha_root : 4 * bunchParlettAlpha ^ 2 - bunchParlettAlpha - 1 = 0bunch_
parlett_ · 1 more declaration under this itemalpha_ root Algorithm 11.2
Theorem 11.4 / Algorithm 11.2 cases-(1)/(2) scalar Schur-growth dispatch: the two branches accepting the leading scalar pivot
a₁₁share the same normalized one-step growth factor. Case-(2) obtains its active-row majorant from the explicit row-maximum side condition.Lean statement
theorem higham11_4_bunch_kaufman_case1_or_case2_schur_growth_source_factor_of_row_max_le (b ci cj a11 arr ω1 ωr Amax : ℝ) (hω1 : 0 < ω1) (hωr_le : ωr ≤ ω1) (hcase : higham11_2_BunchKaufmanPartialPivotCase higham11_1_bunchParlettAlpha a11 arr ω1 ωr BunchKaufmanCase.case1 ∨ higham11_2_BunchKaufmanPartialPivotCase higham11_1_bunchParlettAlpha a11 arr ω1 ωr BunchKaufmanCase.case2) (hb : |b| ≤ Amax) (hci : |ci| ≤ ω1) (hcj : |cj| ≤ ω1) (hω1_Amax : ω1 ≤ Amax) : |b - ci * cj / a11| ≤ (1 + higham11_1_bunchParlettAlpha⁻¹) * Amaxhigham11_
4_ · 11 more declarations under this itembunch_ kaufman_ case1_ or_ case2_ schur_ growth_ source_ factor_ of_ row_ max_ le Algorithm 11.6
The tridiagonal pivoting parameter satisfies
alpha^2 + alpha - 1 = 0.Lean statement
theorem bunch_tridiagonal_alpha_root : bunchTridiagonalAlpha ^ 2 + bunchTridiagonalAlpha - 1 = 0bunch_
tridiagonal_ · 18 more declarations under this itemalpha_ root Algorithm 11.9
Skew 2×2 multiplier bound (Higham §11.3). For Bunch's skew-symmetric pivoting, the row of
CE⁻¹has entries−a_{i2}/a₂₁, a_{i1}/a₂₁; since the pivota₂₁is the largest-magnitude entry (|c| ≤ |a₂₁|), each multiplier — and hence every entry ofL— is bounded by 1. Derived, not assumed.Lean statement
theorem skew_twoByTwo_multiplier_bound (c a : ℝ) (ha : a ≠ 0) (hc : |c| ≤ |a|) : |c / a| ≤ 1skew_
two · 5 more declarations under this itemBy Two_ multiplier_ bound Theorem 11.3
All-1×1-pivot (σ = id) case, printed first-order strength. For a symmetric input whose rounded all-1×1-pivot block-LDLᵀ path has nonzero successive pivots (and, at each stage, matching active first row/column), under the smallness
n·u ≤ 1/100there are computed factorsL̂, D̂and backward-error matricesΔA₁, ΔA₂withL̂D̂L̂ᵀ = A + ΔA₁,|ΔAₖ| ≤ p(n)·u·(|A| + |L̂||D̂||L̂ᵀ|), the printed Higham (11.5) envelope with linear polynomialp(n) = 20 n. Everything is derived from the floating-point model.Lean statement
theorem higham11_3_block_ldlt_all_oneByOne_printed (fp : FPModel) (hval : gammaValid fp 3) (n : ℕ) (A : Fin n → Fin n → ℝ) (hsmall : (n : ℝ) * fp.u ≤ 1 / 100) (hp : FlAllOneSymmetricPivots fp n A) : ∃ L D ΔA1 ΔA2 : Fin n → Fin n → ℝ, (∀ i j, |ΔA1 i j| ≤ higham11_3_printedFirstOrderBound n A L D id (pPoly n) fp.u i j) ∧ (∀ i j, |ΔA2 i j| ≤ higham11_3_printedFirstOrderBound n A L D id (pPoly n) fp.u i j) ∧ (∀ i j, (∑ k₁, ∑ k₂, L i k₁ * D k₁ k₂ * L j k₂) = A i j + ΔA1 i j)higham11_
3_ · 38 more declarations under this itemblock_ ldlt_ all_ one By One_ printed Theorem 11.8
Theorem 11.8 product-size dependency: an
AasenSpecsupplies the structural zeros needed to turn a uniform exact outer-factor entry cap into(n-1)row and column sum majorants.Lean statement
theorem higham11_8_aasen_outer_factor_row_col_sum_majorants_of_AasenSpec_entry_bound (n : ℕ) (hn : 1 < n) (A L T : Fin n → Fin n → ℝ) (σ : Fin n → Fin n) (κ : ℝ) (hspec : higham11_8_AasenSpec n A L T σ) (hentry : ∀ i j : Fin n, |L i j| ≤ κ) : (∀ i : Fin n, (∑ j : Fin n, |L i j|) ≤ ((n - 1 : ℕ) : ℝ) * κ) ∧ (∀ j : Fin n, (∑ i : Fin n, |L i j|) ≤ ((n - 1 : ℕ) : ℝ) * κ)higham11_
8_ · 176 more declarations under this itemaasen_ outer_ factor_ row_ col_ sum_ majorants_ of_ Aasen Spec_ entry_ bound
Equations and other results
Equation (11.1)
Exact all-1×1 block-LDLᵀ factorization existence (Higham eqs (11.1)/(11.2), the no-2×2-pivot / root-free
LDLᵀcase). IfAis symmetric and every successive Schur-complement pivot is nonzero (AllOnePivots), there exist factorsL, Dwith∑ L·D·Lᵀ = A— the exactPAPᵀ = LDLᵀrecursion (withP = I) underlying Theorem 11.3, obtained by iteratingblockLDLT_assemble_step.Lean statement
theorem exact_blockLDLT_all_oneByOne : ∀ (n : ℕ) (A : Fin n → Fin n → ℝ), (∀ i j, A i j = A j i) → AllOnePivots n A → ∃ L D : Fin n → Fin n → ℝ, ∀ I J, (∑ k₁, ∑ k₂, L I k₁ * D k₁ k₂ * L J k₂) = A I Jexact_
block · 2 more declarations under this itemLDLT_ all_ one By One Equation (11.4)
Self-contained 2×2 complete-pivoting element growth (Higham §11.1.1, eq. (11.4)). Combining
twoByTwo_inverse_entry_boundswithtwoByTwo_schur_growth: the Schur entry formed with the actual inverse of the pivot blockE, namelyE⁻¹ = d⁻¹[[e₂₂,−e₂₁],[−e₂₁,e₁₁]], is bounded by(1 + 2/(1−α))·μ₀using only the pivot-block data and the entry boundμ₀— no inverse-entry bounds are assumed.Lean statement
theorem twoByTwo_schur_growth_of_block (b ci1 ci2 cj1 cj2 e11 e22 e21 μ0 μ1 α K : ℝ) (hμ1 : 0 ≤ μ1) (hα0 : 0 ≤ α) (hα1 : α < 1) (hμ : 0 < μ0) (he11 : |e11| ≤ μ1) (he22 : |e22| ≤ μ1) (he21 : e21 ^ 2 = μ0 ^ 2) (hμ1α : μ1 ≤ α * μ0) (hK : (1 - α ^ 2) * μ0 * K = 1) (hb : |b| ≤ μ0) (hci1 : |ci1| ≤ μ0) (hci2 : |ci2| ≤ μ0) (hcj1 : |cj1| ≤ μ0) (hcj2 : |cj2| ≤ μ0) : |b - (ci1 * (e22 / (e11 * e22 - e21 ^ 2) * cj1 + -(e21 / (e11 * e22 - e21 ^ 2)) * cj2) + ci2 * (-(e21 / (e11 * e22 - e21 ^ 2)) * cj1 + e11 / (e11 * e22 - e21 ^ 2) * cj2))| ≤ (1 + 2 / (1 - α)) * μ0two
By · 1 more declaration under this itemTwo_ schur_ growth_ of_ block Equation (11.6)
Equation (11.6) verified algebraically:
A = L D L^Tforε ≠ 0.Lean statement
theorem higham11_6_partialPivotExample_factorization (ε : ℝ) (hε : ε ≠ 0) : ∀ i j : Fin 3, ∑ k₁ : Fin 3, ∑ k₂ : Fin 3, higham11_6_partialPivotExampleL ε i k₁ * higham11_6_partialPivotExampleD ε k₁ k₂ * higham11_6_partialPivotExampleL ε j k₂ = higham11_6_partialPivotExampleA ε i jEquation (11.11)
First diagonal recovery. For
H = T Lᵀin anAasenSpec, the first diagonalHentry is the first tridiagonal diagonal entry ofT.Lean statement
theorem higham11_11_AasenSpec_identity_aasenH_diagonal_eq_T_of_zero (n : ℕ) (A L T : Fin n → Fin n → ℝ) (σ : Fin n → Fin n) (hspec : higham11_8_AasenSpec n A L T σ) (i : Fin n) (hi0 : i.val = 0) : higham11_10_aasenH n T L i i = T i ihigham11_
11_ · 3 more declarations under this itemAasen Spec_ identity_ aasen H_ diagonal_ eq_ T_ of_ zero Equation (11.12)
Equation (11.12) derivation: the Aasen diagonal equation holds for any
A = L·HwithLunit lower triangular. Exact-arithmetic identity behind the Aasen recurrence (not the fl analysis):A i i = ∑_{j<i} L i j · H j i + H i i, by unit-lower-triangularity ofL.Lean statement
theorem higham11_12_aasen_diagonal_equation_of_product (n : ℕ) (A L H : Fin n → Fin n → ℝ) (hLdiag : ∀ i, L i i = 1) (hLupper : ∀ i j : Fin n, i.val < j.val → L i j = 0) (hprod : ∀ i k : Fin n, (∑ j, L i j * H j k) = A i k) : higham11_12_aasenDiagonalEquation n A L Hhigham11_
12_ · 3 more declarations under this itemaasen_ diagonal_ equation_ of_ product Equation (11.13)
Equation (11.13) derivation: the Aasen subdiagonal equation holds for any
A = L·HwithLunit lower triangular. Fork = i+1,A k i = ∑_{j≤i} L k j · H j i + H k i.Lean statement
theorem higham11_13_aasen_subdiagonal_equation_of_product (n : ℕ) (A L H : Fin n → Fin n → ℝ) (hLdiag : ∀ i, L i i = 1) (hLupper : ∀ i j : Fin n, i.val < j.val → L i j = 0) (hprod : ∀ i k : Fin n, (∑ j, L i j * H j k) = A i k) : higham11_13_aasenSubdiagonalEquation n A L Hhigham11_
13_ · 3 more declarations under this itemaasen_ subdiagonal_ equation_ of_ product Equation (11.14)
Equation (11.14) derivation: for
A = L·HwithLunit lower triangular andHbanded (H j i = 0forj > i+1, e.g. fromhigham11_10_aasenH_band), the below-diagonal next-column entries ofLareL k next = (A k i − ∑_{j≤i} L k j·H j i) / H next i(next = i+1,k ≥ i+2), provided the pivotH next i ≠ 0. Exact-arithmetic Aasen recurrence, toward Thm 11.8.Lean statement
theorem higham11_14_aasen_next_column_of_product (n : ℕ) (A L H : Fin n → Fin n → ℝ) (hHband : ∀ i j : Fin n, i.val + 1 < j.val → H j i = 0) (hprod : ∀ k i : Fin n, (∑ j, L k j * H j i) = A k i) (hHnz : ∀ i next : Fin n, next.val = i.val + 1 → H next i ≠ 0) : higham11_14_aasenNextColumnEquation n A L Hhigham11_
14_ · 13 more declarations under this itemaasen_ next_ column_ of_ product Equation (11.15)
Equation (11.15) exact solve-chain bridge, unpermuted case. If the exact Aasen product is
A = L T Lᵀand the three exact solves in the chain are satisfied with identity permutation, then the resultingxsolvesA x = b. This is the algebraic base that the later rounded solve-chain perturbation must approximate.Lean statement
theorem higham11_15_aasenSolveChain_identity_solve_of_product (n : ℕ) (A L T : Fin n → Fin n → ℝ) (b z y w x : Fin n → ℝ) (hprod : ∀ i j : Fin n, (∑ k₁ : Fin n, ∑ k₂ : Fin n, L i k₁ * T k₁ k₂ * L j k₂) = A i j) (hchain : higham11_15_aasenSolveChain n (fun i j => if i = j then 1 else 0) L T b z y w x) : ∀ i : Fin n, ∑ j : Fin n, A i j * x j = b ihigham11_
15_ · 9 more declarations under this itemaasen Solve Chain_ identity_ solve_ of_ product
Chapter 12 · Iterative refinement all chapters
Definitions, theorems and lemmas
Theorem 12.3
Theorem 12.3 / equation (12.10) (Higham, 2nd ed., printed p. 235), with the asymptotic remainder
qdisplayed exactly rather than hidden behindO(u). The source's later statementq = O(u)needs a parameterized regularity hypothesis fort; this theorem proves the finite identity from which that asymptotic interpretation is obtained. HeregTerm,hTerm,tAtX, andtAtYstand for the corresponding source quantities at the computed correction, original solution, and corrected solution.Lean statement
theorem higham12_10_exact_q_bound (n : ℕ) (A : Fin n → Fin n → ℝ) (x_hat d_hat : Fin n → ℝ) (b r r_hat : Fin n → ℝ) (f2 : Fin n → ℝ) (y : Fin n → ℝ) (u : ℝ) (gTerm hTerm tAtX tAtY : Fin n → ℝ) (hr : ∀ i : Fin n, r i = b i - ∑ j : Fin n, A i j * x_hat j) (hy : ∀ i : Fin n, y i = x_hat i + d_hat i + f2 i) (hf1 : ∀ i : Fin n, |r_hat i - ∑ j : Fin n, A i j * d_hat j| ≤ u * (gTerm i + hTerm i)) (hDeltaR : ∀ i : Fin n, |r_hat i - r i| ≤ u * tAtX i) (hf2 : ∀ j : Fin n, |f2 j| ≤ u * (|x_hat j| + |d_hat j|)) : ∀ i : Fin n, |b i - ∑ j : Fin n, A i j * y j| ≤ u * (hTerm i + tAtY i + ∑ j : Fin n, |A i j| * |y j|) + u * (tAtX i - tAtY i + gTerm i + ∑ j : Fin n, |A i j| * (|x_hat j| - |y j| + |d_hat j|))higham12_
10_ · 3 more declarations under this itemexact_ q_ bound Theorem 12.4
Theorem 12.4 / equation (12.22) (Higham, 2nd ed., printed pp. 236-238): an exact conditional companion with the printed two-gamma conclusion. The source's sufficient-condition function is approximate; here the needed componentwise dominance inequality remains an explicit hypothesis, so this is not the solver-derived endpoint.
Lean statement
theorem higham12_4_conditional_two_gamma_bound (n : ℕ) (fp : FPModel) (A : Fin n → Fin n → ℝ) (x_hat d_hat r_hat : Fin n → ℝ) (DeltaA_solve : Fin n → Fin n → ℝ) (mu nu : ℝ) (omega : Fin n → ℝ) (b : Fin n → ℝ) (r : Fin n → ℝ) (hr : ∀ i : Fin n, r i = b i - ∑ j : Fin n, A i j * x_hat j) (hres : ∀ i : Fin n, |r_hat i - r i| ≤ nu * |r i| + omega i) (hsolve : ∀ i : Fin n, ∑ j : Fin n, (A i j + DeltaA_solve i j) * d_hat j = r_hat i) (hDeltaA : ∀ i j : Fin n, |DeltaA_solve i j| ≤ mu * |A i j|) (y : Fin n → ℝ) (hy : ∀ i : Fin n, y i = x_hat i + d_hat i) (hmu_nonneg : 0 ≤ mu) (hnu_nonneg : 0 ≤ nu) (homega_nonneg : ∀ i : Fin n, 0 ≤ omega i) (hdom : ∀ i : Fin n, mu * ∑ j : Fin n, |A i j| * |d_hat j| + nu * |r i| + omega i ≤ (2 * gamma fp (n + 1)) * ∑ j : Fin n, |A i j| * |y j|) : ∀ i : Fin n, |b i - ∑ j : Fin n, A i j * y j| ≤ (2 * gamma fp (n + 1)) * ∑ j : Fin n, |A i j| * |y j|higham12_
4_ · 2 more declarations under this itemconditional_ two_ gamma_ bound
Equations and other results
Equation (12.2)
Equation (12.2) residual perturbation bound after rewriting
x_i = x + (x_i - x). This is the exact algebraic component of the displayed bound; the residual computation model supplieshDelta.Lean statement
theorem higham12_2_residual_delta_bound (n : ℕ) (A : Fin n → Fin n → ℝ) (x x_i b DeltaR : Fin n → ℝ) (u gammaBar : ℝ) (hu : 0 ≤ u) (hc : 0 ≤ (1 + u) * gammaBar) (hAx : ∀ i : Fin n, ∑ j : Fin n, A i j * x j = b i) (hDelta : ∀ i : Fin n, |DeltaR i| ≤ u * |b i - ∑ j : Fin n, A i j * x_i j| + (1 + u) * gammaBar * (|b i| + ∑ j : Fin n, |A i j| * |x_i j|)) : ∀ i : Fin n, |DeltaR i| ≤ (u + (1 + u) * gammaBar) * ∑ j : Fin n, |A i j| * |x j - x_i j| + 2 * (1 + u) * gammaBar * ∑ j : Fin n, |A i j| * |x j|Equation (12.4)
Equations (12.4)-(12.5) exact forward-error identity of one refinement step. With computed residual
rc = (b - A x_i) + Δr, correctiondsolving(A + ΔA) d = rc, and rounded updatey = x_i + d + Δx, the corrected forward error satisfies exactlyA (y - x) = Δr - ΔA·d + A·Δx. This is the exact, inverse-free core of the recurrence (12.5) (before the source's asymptoticF_i,G_i,O(u^2)estimates).Lean statement
theorem higham12_5_forward_error_identity (n : ℕ) (A DeltaA : Fin n → Fin n → ℝ) (x x_i d DeltaR DeltaX rc y b : Fin n → ℝ) (hAx : ∀ i : Fin n, ∑ j : Fin n, A i j * x j = b i) (hrc : ∀ i : Fin n, rc i = (b i - ∑ j : Fin n, A i j * x_i j) + DeltaR i) (hsolve : ∀ i : Fin n, ∑ j : Fin n, (A i j + DeltaA i j) * d j = rc i) (hy : ∀ i : Fin n, y i = x_i i + d i + DeltaX i) : ∀ i : Fin n, ∑ j : Fin n, A i j * (y j - x j) = DeltaR i - (∑ j : Fin n, DeltaA i j * d j) + (∑ j : Fin n, A i j * DeltaX j)higham12_
5_ · 1 more declaration under this itemforward_ error_ identity Equation (12.5)
Uniform steady-state consequence of the Chapter 12 contraction skeleton.
Lean statement
theorem higham12_forward_error_steady_state (a : ℕ → ℝ) (eta tau : ℝ) (heta_nonneg : 0 ≤ eta) (heta_lt : eta < 1) (htau_nonneg : 0 ≤ tau) (hstep : ∀ k, a (k + 1) ≤ eta * a k + tau) (ha0 : 0 ≤ a 0) : ∀ k, a k ≤ a 0 + tau / (1 - eta)higham12_
forward_ · 1 more declaration under this itemerror_ steady_ state
Chapter 13 · Block LU factorization all chapters
Definitions, theorems and lemmas
Algorithm 13.1
Exact output check for partitioned outer-product LU. If the algorithm's displayed steps hold --
A₁₁ = L₁₁ U₁₁,L₁₁ U₁₂ = A₁₂,L₂₁ U₁₁ = A₂₁,S = A₂₂ - L₂₁ U₁₂, and the recursive call returnsS = L₂₂ U₂₂-- then the assembled block factors multiply to the original matrix.Lean statement
theorem higham13_algorithm13_1_partitioned_lu_reconstructs {m n α : Type*} [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n] [CommRing α] (L11 U11 A11 : Matrix m m α) (U12 A12 : Matrix m n α) (L21 A21 : Matrix n m α) (L22 U22 S A22 : Matrix n n α) (h11 : L11 * U11 = A11) (h12 : L11 * U12 = A12) (h21 : L21 * U11 = A21) (hSfact : L22 * U22 = S) (hSdef : S = A22 - L21 * U12) : Matrix.fromBlocks A11 A12 A21 A22 = Matrix.fromBlocks L11 0 L21 L22 * Matrix.fromBlocks U11 U12 0 U22higham13_
algorithm13_ · 2 more declarations under this item1_ partitioned_ lu_ reconstructs Algorithm 13.3
Exact output check for block LU recursion. With
U₁₁ = A₁₁,U₁₂ = A₁₂,L₂₁ A₁₁ = A₂₁,S = A₂₂ - L₂₁ A₁₂, and recursive factorsS = L₂₂ U₂₂, the assembled block LU factors multiply to the original matrix.Lean statement
theorem higham13_algorithm13_3_block_lu_reconstructs {m n α : Type*} [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n] [CommRing α] (A11 : Matrix m m α) (A12 : Matrix m n α) (L21 A21 : Matrix n m α) (L22 U22 S A22 : Matrix n n α) (h21 : L21 * A11 = A21) (hSfact : L22 * U22 = S) (hSdef : S = A22 - L21 * A12) : Matrix.fromBlocks A11 A12 A21 A22 = Matrix.fromBlocks 1 0 L21 L22 * Matrix.fromBlocks A11 A12 0 U22higham13_
algorithm13_ · 188 more declarations under this item3_ block_ lu_ reconstructs Algorithm 13.4
Exact output check for recursively partitioned LU. The first recursive call supplies
[A₁₁; A₂₁] = [L₁₁; L₂₁] U₁₁, the triangular solve suppliesL₁₁ U₁₂ = A₁₂, and the second recursive call suppliesS = L₂₂ U₂₂; after formingS = A₂₂ - L₂₁ U₁₂, the assembled block factors multiply to the original matrix.Lean statement
theorem higham13_algorithm13_4_recursive_partitioned_lu_reconstructs {n α : Type*} [Fintype n] [DecidableEq n] [CommRing α] (L11 U11 A11 U12 A12 L21 A21 L22 U22 S A22 : Matrix n n α) (h11 : L11 * U11 = A11) (h21 : L21 * U11 = A21) (h12 : L11 * U12 = A12) (hSfact : L22 * U22 = S) (hSdef : S = A22 - L21 * U12) : Matrix.fromBlocks A11 A12 A21 A22 = Matrix.fromBlocks L11 0 L21 L22 * Matrix.fromBlocks U11 U12 0 U22higham13_
algorithm13_ · 1 more declaration under this item4_ recursive_ partitioned_ lu_ reconstructs Lemma 13.9
For a source-ordered SPD block matrix,
||A₂₁ A₁₁⁻¹||₂ <= sqrt(κ₂(A)). The leading inverse is modeled by the repository canonical inverse of the leading principal block, andκ₂(A)is the exact productkappa2 A (nonsingInv (r+s) A). The proof chooses a Cholesky factor from SPD, identifiesA₁₁⁻¹withR₁₁⁻¹R₁₁⁻ᵀ, and feeds the exact-kappa2Cholesky route.Lean statement
theorem higham13_lemma13_9_cholesky_route_rectOpNorm2Le_from_spd_leading_nonsingInv_kappa2 {r s : ℕ} [Nonempty (Fin r)] (A : Fin (r + s) → Fin (r + s) → ℝ) (A22 : Fin s → Fin s → ℝ) (A21 : Fin s → Fin r → ℝ) (hA22_block : A22 = fun i j : Fin s => A (finSumFinEquiv (Sum.inr i : Fin r ⊕ Fin s)) (finSumFinEquiv (Sum.inr j : Fin r ⊕ Fin s))) (hA21_block : A21 = fun (i : Fin s) (j : Fin r) => A (finSumFinEquiv (Sum.inr i : Fin r ⊕ Fin s)) (finSumFinEquiv (Sum.inl j : Fin r ⊕ Fin s))) (hSPD : IsSymPosDef (r + s) A) : rectOpNorm2Le (rectMatMul A21 (nonsingInv r (fun i j : Fin r => A (finSumFinEquiv (Sum.inl i : Fin r ⊕ Fin s)) (finSumFinEquiv (Sum.inl j : Fin r ⊕ Fin s))))) (Real.sqrt (kappa2 A (nonsingInv (r + s) A)))higham13_
lemma13_ · 4 more declarations under this item9_ cholesky_ route_ rect Op Norm2Le_ from_ spd_ leading_ nonsing Inv_ kappa2 Lemma 13.10
Lemma 13.10 proof route: the SPD Schur complement inherits the full matrix's operator-2 certificate. This combines the Loewner bound
S <= A22, the trailing-principal-block operator certificate||A22||_2 <= ||A||_2, and the PSD Schur-complement fact. It closes the||S||_2half of the source condition-number bound; the inverse half||S^{-1}||_2 <= ||A^{-1}||_2remains separate.Lean statement
theorem higham13_lemma13_10_schur_opNorm2Le_of_full_operator_bound {r s : Type*} [Fintype r] [Fintype s] [DecidableEq r] [Nonempty s] (A11 : Matrix r r ℝ) (A21 : Matrix s r ℝ) (A22 : Matrix s s ℝ) {normA : ℝ} (hFull : (Matrix.fromBlocks A11 A21.transpose A21 A22).PosDef) (hA : finiteOpNorm2Le (fun i j : r ⊕ s => (Matrix.fromBlocks A11 A21.transpose A21 A22) i j) normA) : finiteOpNorm2Le (fun i j : s => (A22 - A21 * A11⁻¹ * A21.transpose) i j) normAhigham13_
lemma13_ · 4 more declarations under this item10_ schur_ op Norm2Le_ of_ full_ operator_ bound Theorem 13.2
A uniform block matrix has a unique block LU factorization if and only if its first
mleading principal block submatrices are nonsingular. For a matrix indexed byFin (m+1), this is the source condition on the firstmleading block prefixes, i.e. all prefixes except the whole matrix.Lean statement
theorem BlockLUFactSpec.existsUnique_iff_leadingPrincipalBlockNonsingular13_2 {m r : ℕ} (A : Fin (m + 1) → Fin (m + 1) → (Fin r → Fin r → ℝ)) : (∃ L U : Fin (m + 1) → Fin (m + 1) → (Fin r → Fin r → ℝ), BlockLUFactSpec (m + 1) r A L U ∧ ∀ L' U' : Fin (m + 1) → Fin (m + 1) → (Fin r → Fin r → ℝ), BlockLUFactSpec (m + 1) r A L' U' → L' = L ∧ U' = U) ↔ LeadingPrincipalBlockNonsingular13_2 Aexists
Unique_ · 11 more declarations under this itemiff_ leading Principal Block Nonsingular13_ 2 Theorem 13.5
Theorem 13.5 / equation (13.7) for an actual recursively computed partitioned LU execution. The conclusion exposes both the assembled matrix residual and the advertised first-order backward-error bound.
Lean statement
theorem higham13_theorem13_5_eq13_7_from_computation {ι : Type} [Fintype ι] {m : ℕ} {u c₁ c₂ c₃ normA normL normU normDeltaA : ℝ} {A DeltaA Lhat Uhat : Matrix ι ι ℝ} (hcomp : PartitionedLUComputationFirstOrder u c₁ c₂ c₃ m normA normL normU normDeltaA A DeltaA Lhat Uhat) (hu : 0 ≤ u) (hc₁ : 0 ≤ c₁) (hc₂ : 0 ≤ c₂) (hc₃ : 0 ≤ c₃) : (Lhat * Uhat = A + DeltaA) ∧ FirstOrderLe u (u * (blockErrorDelta m * normA + blockErrorTheta c₁ c₂ c₃ m * normL * normU)) normDeltaAhigham13_
theorem13_ · 6 more declarations under this item5_ eq13_ 7_ from_ computation Theorem 13.7
Source-facing Euclidean column-BDD endpoint. The initial
diagInvtable states the printed quantity||A_jj^{-1}||_2^{-1}. From full nonsingularity and this BDD condition, the theorem constructs the complete Algorithm 13.3 pivot sequence, the concrete block LU factors, and block diagonal dominance of every active Schur complement.Lean statement
theorem higham13_theorem13_7_algorithm13_3_opNorm2_column {m r : ℕ} (hr : 0 < r) (A : Fin m → Fin m → Matrix (Fin r) (Fin r) ℝ) (diagInv : Fin m → Matrix (Fin r) (Fin r) ℝ) (hA : BlockMatrixNonsingular A) (hDiagRight : ∀ j : Fin m, IsRightInverse r (A j j) (diagInv j)) (hDom : IsBlockDiagDomCol m (fun i j => opNorm2 (A i j)) (fun j => (opNorm2 (diagInv j))⁻¹)) : ∃ pivotInv : ℕ → Matrix (Fin r) (Fin r) ℝ, (∀ k : ℕ, ∀ hk : k < m, IsRightInverse r (higham13_algorithm13_3_schurStageMatrixBlock A pivotInv k ⟨k, hk⟩ ⟨k, hk⟩) (pivotInv k)) ∧ BlockLUFactSpec m r A (higham13_algorithm13_3_lowerFromMatrixStages A pivotInv) (higham13_algorithm13_3_upperFromMatrixStages A pivotInv) ∧ SchurStageActiveColumnDom13_7 (fun k i j => opNorm2 (higham13_algorithm13_3_schurStageMatrixBlock A pivotInv k i j)) (fun k j => matMulVecLowerNorm2 hr (higham13_algorithm13_3_schurStageMatrixBlock A pivotInv k j j))higham13_
theorem13_ · 27 more declarations under this item7_ algorithm13_ 3_ op Norm2_ column Theorem 13.8
Source-facing Euclidean column-BDD endpoint. Under exactly the nonsingularity and BDD data used by Theorem 13.7, this constructs the block LU factors and proves the printed active-stage growth estimate
||A_ij^(k)||_2 <= 2 * max_ij ||A_ij||_2.Lean statement
theorem higham13_theorem13_8_algorithm13_3_opNorm2_column {m r : ℕ} (hm : 0 < m) (hr : 0 < r) (A : Fin m → Fin m → Matrix (Fin r) (Fin r) ℝ) (diagInv : Fin m → Matrix (Fin r) (Fin r) ℝ) (hA : BlockMatrixNonsingular A) (hDiagRight : ∀ j : Fin m, IsRightInverse r (A j j) (diagInv j)) (hDom : IsBlockDiagDomCol m (fun i j => opNorm2 (A i j)) (fun j => (opNorm2 (diagInv j))⁻¹)) (normMax : ℝ) (hMax : ∀ i j : Fin m, opNorm2 (A i j) ≤ normMax) : ∃ pivotInv : ℕ → Matrix (Fin r) (Fin r) ℝ, BlockLUFactSpec m r A (higham13_algorithm13_3_lowerFromMatrixStages A pivotInv) (higham13_algorithm13_3_upperFromMatrixStages A pivotInv) ∧ ∀ k : ℕ, ∀ i j : Fin m, k ≤ m → k ≤ i.val → k ≤ j.val → opNorm2 (higham13_algorithm13_3_schurStageMatrixBlock A pivotInv k i j) ≤ 2 * normMaxhigham13_
theorem13_ · 26 more declarations under this item8_ algorithm13_ 3_ op Norm2_ column
Equations and other results
Equation (13.2)
One exact block LU step with Schur complement. For an invertible leading block
A₁₁, the 2-by-2 block matrix factors as[[I,0],[A₂₁ A₁₁^{-1},I]] * [[A₁₁,A₁₂],[0,S]], whereS = A₂₂ - A₂₁ A₁₁^{-1} A₁₂.Lean statement
theorem higham13_eq13_2_block_lu_step {m n α : Type*} [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n] [CommRing α] (A11 : Matrix m m α) (A12 : Matrix m n α) (A21 : Matrix n m α) (A22 : Matrix n n α) [Invertible A11] : Matrix.fromBlocks A11 A12 A21 A22 = Matrix.fromBlocks 1 0 (A21 * ⅟A11) 1 * Matrix.fromBlocks A11 A12 0 (A22 - A21 * ⅟A11 * A12)Equation (13.4)
Source-facing unpacking of the matrix-multiplication first-order model.
Lean statement
theorem higham13_eq13_4_from_matmul_spec {m n p : Type*} [Fintype n] (u c₁ normA normB normDelta : ℝ) (A : Matrix m n ℝ) (B : Matrix n p ℝ) (Chat DeltaC : Matrix m p ℝ) (h : MatMulFirstOrderSpec u c₁ normA normB normDelta A B Chat DeltaC) : Chat = A * B + DeltaC ∧ MatMulFirstOrderBound u c₁ normA normB normDeltahigham13_
eq13_ · 2 more declarations under this item4_ from_ matmul_ spec Equation (13.5)
Source-facing unpacking of the left triangular-solve first-order model.
Lean statement
theorem higham13_eq13_5_from_triangular_solve_spec {m p : Type*} [Fintype m] (u c₂ normT normXhat normDeltaB : ℝ) (T : Matrix m m ℝ) (B DeltaB Xhat : Matrix m p ℝ) (h : TriangularSolveFirstOrderSpec u c₂ normT normXhat normDeltaB T B DeltaB Xhat) : T * Xhat = B + DeltaB ∧ TriangularSolveFirstOrderBound u c₂ normT normXhat normDeltaBhigham13_
eq13_ · 3 more declarations under this item5_ from_ triangular_ solve_ spec Equation (13.6)
Source-facing unpacking of the block-level LU first-order model.
Lean statement
theorem higham13_eq13_6_from_local_lu_spec {r : Type*} [Fintype r] (u c₃ normLhat normUhat normDeltaA : ℝ) (A DeltaA Lhat Uhat : Matrix r r ℝ) (h : LocalLUFirstOrderSpec u c₃ normLhat normUhat normDeltaA A DeltaA Lhat Uhat) : Lhat * Uhat = A + DeltaA ∧ LocalLUFirstOrderBound u c₃ normLhat normUhat normDeltaAhigham13_
eq13_ · 1 more declaration under this item6_ from_ local_ lu_ spec Equation (13.10)
Source-facing unpacking of the computed subtraction residual model.
Lean statement
theorem higham13_eq13_10_from_subtraction_spec {m p : Type*} (u normA normComputed normF : ℝ) (A Computed F Shat : Matrix m p ℝ) (h : SubtractionFirstOrderSpec u normA normComputed normF A Computed F Shat) : Shat = A - Computed + F ∧ normF ≤ u * (normA + normComputed)higham13_
eq13_ · 1 more declaration under this item10_ from_ subtraction_ spec Equation (13.14)
Source-facing unpacking of the Algorithm 13.3 step-2 block-solve model.
Lean statement
theorem higham13_eq13_14_from_block_solve_spec {r s : Type*} [Fintype r] (u c₄ normLhat21 normA11 normE21 : ℝ) (Lhat21 A21 E21 : Matrix s r ℝ) (A11 : Matrix r r ℝ) (h : BlockSolveFirstOrderSpec u c₄ normLhat21 normA11 normE21 Lhat21 A21 E21 A11) : Lhat21 * A11 = A21 + E21 ∧ BlockSolveFirstOrderBound u c₄ normLhat21 normA11 normE21Equation (13.15)
Source-facing unpacking of the diagonal-block solve model used in block back substitution.
Lean statement
theorem higham13_eq13_15_from_diagonal_block_solve_spec {r p : Type*} [Fintype r] (u c₅ normUii normDeltaUii : ℝ) (Uii DeltaUii : Matrix r r ℝ) (Xhat D : Matrix r p ℝ) (h : DiagonalBlockSolveFirstOrderSpec u c₅ normUii normDeltaUii Uii DeltaUii Xhat D) : (Uii + DeltaUii) * Xhat = D ∧ DiagonalBlockSolveFirstOrderBound u c₅ normUii normDeltaUiihigham13_
eq13_ · 10 more declarations under this item15_ from_ diagonal_ block_ solve_ spec Equation (13.18)
Min-step abstraction. Higham's proof uses the reverse triangle inequality to pass from
min_{‖x‖=1} ‖A_jj x‖ - ctomin_{‖x‖=1} ‖(A_jj - A_j1 A_11^{-1} A_1j) x‖. This lemma records that normed-space step without choosing a concrete subordinate matrix norm.Lean statement
theorem higham13_eq13_18_min_lower_bound {E : Type*} [SeminormedAddCommGroup E] (diag perturb schur : E → E) (diagMin schurMin perturbBound : ℝ) (hDiagMin : ∀ x : E, ‖x‖ = 1 → diagMin ≤ ‖diag x‖) (hSchurMin : ∃ x : E, ‖x‖ = 1 ∧ schurMin = ‖schur x‖) (hPerturb : ∀ x : E, ‖x‖ = 1 → ‖perturb x‖ ≤ perturbBound) (hSchur : ∀ x : E, schur x = diag x - perturb x) : diagMin - perturbBound ≤ schurMinhigham13_
eq13_ · 12 more declarations under this item18_ min_ lower_ bound Equation (13.19)
Packaged from its two displayed inequalities.
Lean statement
theorem higham13_eq13_19 {m : ℕ} (blockNorm : Fin m → Fin m → ℝ) (normA : ℝ) (hLower : ∀ i j : Fin m, blockNorm i j ≤ normA) (hUpper : normA ≤ blockNormSum13_19 blockNorm) : BlockNormComparison13_19 blockNorm normAhigham13_
eq13_ · 4 more declarations under this item19 Equation (13.20)
Exact 2-by-2 partition display. Higham switches here to the entrywise max norm and writes
A = [[A₁₁, A₁₂], [A₂₁, A₂₂]]. In Mathlib this is exactly thefromBlocksreconstruction from the four canonical block projections.Lean statement
theorem higham13_eq13_20_partition {r s α : Type*} (A : Matrix (r ⊕ s) (r ⊕ s) α) : A = Matrix.fromBlocks A.toBlocks₁₁ A.toBlocks₁₂ A.toBlocks₂₁ A.toBlocks₂₂Equation (13.22)
Higham, 2nd ed., Chapter 13, Problem 13.4 and equation (13.22): for a matrix with at least two blocks, one exact Algorithm 13.3 pivot table supplies every recursive parent/suffix inverse obligation and yields the exact source
n * rho^3 * kappa(A) * ‖A‖product bound.Lean statement
theorem higham13_problem13_4_eq13_22_exists_blockLUFact_succ_of_pivot_right_inverse {m r n : ℕ} (hr : 0 < r) (A : Fin ((m + 1) + 1) → Fin ((m + 1) + 1) → Matrix (Fin r) (Fin r) ℝ) (pivotInv : ℕ → Matrix (Fin r) (Fin r) ℝ) (hPivotRight : ∀ k : ℕ, ∀ hk : k < (m + 1) + 1, IsRightInverse r (higham13_algorithm13_3_schurStageMatrixBlock A pivotInv k ⟨k, hk⟩ ⟨k, hk⟩) (pivotInv k)) (hdet : Matrix.det (blockMatrixFirstSplitFlat A : Matrix (Fin (r + (m + 1) * r)) (Fin (r + (m + 1) * r)) ℝ) ≠ 0) (hFulln : (((((m + 1) + 1) * r : ℕ) : ℝ) ≤ (n : ℝ))) : ∃ L U : Fin ((m + 1) + 1) → Fin ((m + 1) + 1) → Matrix (Fin r) (Fin r) ℝ, BlockLUFactSpec ((m + 1) + 1) r A L U ∧ blockMaxNorm (Nat.succ_pos (m + 1)) hr L * blockMaxNorm (Nat.succ_pos (m + 1)) hr U ≤ (n : ℝ) * (growthFactorEntry (Nat.add_pos_left hr ((m + 1) * r)) (blockMatrixFirstSplitFlat A) (higham13_algorithm13_3_matrixStageHistoryGrowthMatrix (Nat.add_pos_left hr ((m + 1) * r)) (Nat.succ_pos (m + 1)) hr A pivotInv) (maxEntryNorm_pos_of_det_ne_zero (Nat.add_pos_left hr ((m + 1) * r)) (blockMatrixFirstSplitFlat A) hdet)) ^ 3 * (maxEntryNormRect (Nat.add_pos_left hr ((m + 1) * r)) (Nat.add_pos_left hr ((m + 1) * r)) (blockMatrixFirstSplitFlat A) * maxEntryNormRect (Nat.add_pos_left hr ((m + 1) * r)) (Nat.add_pos_left hr ((m + 1) * r)) (nonsingInv (r + (m + 1) * r) (blockMatrixFirstSplitFlat A))) * maxEntryNormRect (Nat.add_pos_left hr ((m + 1) * r)) (Nat.add_pos_left hr ((m + 1) * r)) (blockMatrixFirstSplitFlat A)higham13_
problem13_ · 93 more declarations under this item4_ eq13_ 22_ exists_ block LUFact_ succ_ of_ pivot_ right_ inverse Equation (13.23)
Source closure. For a point-row diagonally dominant matrix on which exact block Algorithm 13.3 succeeds, the scalar no-pivot producer supplies the
ρ ≤ 2history bound; the scalar/block active-stage bridge above transfers it to the global recursive Problem 13.4 aggregation. No growth, factor-norm, or target-scale premise is required from the caller.Lean statement
theorem higham13_problem13_4_eq13_23_exists_blockLUFact_succ_of_pointRow {m r n : ℕ} (hr : 0 < r) (A : Fin ((m + 1) + 1) → Fin ((m + 1) + 1) → Matrix (Fin r) (Fin r) ℝ) (pivotInv : ℕ → Matrix (Fin r) (Fin r) ℝ) (hPivotRight : ∀ k : ℕ, ∀ hk : k < (m + 1) + 1, IsRightInverse r (higham13_algorithm13_3_schurStageMatrixBlock A pivotInv k ⟨k, hk⟩ ⟨k, hk⟩) (pivotInv k)) (hRow : IsRowDiagDominant (((m + 1) + 1) * r) (blockMatrixFlatFin A)) (hdet : Matrix.det (blockMatrixFirstSplitFlat A : Matrix (Fin (r + (m + 1) * r)) (Fin (r + (m + 1) * r)) ℝ) ≠ 0) (hFulln : (((((m + 1) + 1) * r : ℕ) : ℝ) ≤ (n : ℝ))) : ∃ L U : Fin ((m + 1) + 1) → Fin ((m + 1) + 1) → Matrix (Fin r) (Fin r) ℝ, BlockLUFactSpec ((m + 1) + 1) r A L U ∧ blockMaxNorm (Nat.succ_pos (m + 1)) hr L * blockMaxNorm (Nat.succ_pos (m + 1)) hr U ≤ 8 * (n : ℝ) * (maxEntryNormRect (Nat.add_pos_left hr ((m + 1) * r)) (Nat.add_pos_left hr ((m + 1) * r)) (blockMatrixFirstSplitFlat A) * maxEntryNormRect (Nat.add_pos_left hr ((m + 1) * r)) (Nat.add_pos_left hr ((m + 1) * r)) (nonsingInv (r + (m + 1) * r) (blockMatrixFirstSplitFlat A))) * maxEntryNormRect (Nat.add_pos_left hr ((m + 1) * r)) (Nat.add_pos_left hr ((m + 1) * r)) (blockMatrixFirstSplitFlat A)higham13_
problem13_ · 143 more declarations under this item4_ eq13_ 23_ exists_ block LUFact_ succ_ of_ point Row Equation (13.24)
For the concrete Algorithm 13.3 factors of an SPD block matrix. No factor-norm premises are assumed: the two bounds and their printed product consequence are derived from SPD via Lemmas 13.9--13.10.
Lean statement
theorem higham13_eq13_24_algorithm13_3_spd {m r : ℕ} (hr : 0 < r) (A : Fin m → Fin m → Matrix (Fin r) (Fin r) ℝ) (hSPD : IsSymPosDef (m * r) (blockMatrixFlatFin A)) : ∃ pivotInv : ℕ → Matrix (Fin r) (Fin r) ℝ, (∀ k : ℕ, ∀ hk : k < m, IsRightInverse r (higham13_algorithm13_3_schurStageMatrixBlock A pivotInv k ⟨k, hk⟩ ⟨k, hk⟩) (pivotInv k)) ∧ BlockLUFactSpec m r A (higham13_algorithm13_3_lowerFromMatrixStages A pivotInv) (higham13_algorithm13_3_upperFromMatrixStages A pivotInv) ∧ opNorm2 (blockMatrixFlatFin (higham13_algorithm13_3_lowerFromMatrixStages A pivotInv)) ≤ 1 + (m : ℝ) * Real.sqrt (kappa2 (blockMatrixFlatFin A) (nonsingInv (m * r) (blockMatrixFlatFin A))) ∧ opNorm2 (blockMatrixFlatFin (higham13_algorithm13_3_upperFromMatrixStages A pivotInv)) ≤ Real.sqrt (m : ℝ) * opNorm2 (blockMatrixFlatFin A) ∧ opNorm2 (blockMatrixFlatFin (higham13_algorithm13_3_lowerFromMatrixStages A pivotInv)) * opNorm2 (blockMatrixFlatFin (higham13_algorithm13_3_upperFromMatrixStages A pivotInv)) ≤ Real.sqrt (m : ℝ) * (1 + (m : ℝ) * Real.sqrt (kappa2 (blockMatrixFlatFin A) (nonsingInv (m * r) (blockMatrixFlatFin A)))) * opNorm2 (blockMatrixFlatFin A)higham13_
eq13_ · 1 more declaration under this item24_ algorithm13_ 3_ spd Equation (13.25)
As the exact first-order composition of Theorem 13.6 with equation (13.24).
Lean statement
theorem higham13_eq13_25_spd_firstOrder_from_eq13_24 (err u c_n normA normLU kappa : ℝ) (m : ℕ) (hm : 0 < m) (hu : 0 ≤ u) (hc : 0 ≤ c_n) (hA : 0 ≤ normA) (hErr : FirstOrderLe u (c_n * u * (normA + normLU)) err) (hLU : normLU ≤ Real.sqrt (m : ℝ) * (1 + (m : ℝ) * Real.sqrt kappa) * normA) : FirstOrderLe u (c_n * Real.sqrt (m : ℝ) * u * normA * (2 + (m : ℝ) * Real.sqrt kappa)) errhigham13_
eq13_ · 7 more declarations under this item25_ spd_ first Order_ from_ eq13_ 24 Equation (13.26)
Problem 13.4 partition display. This is the same four-block partition as (13.20), with the additional source assumption that the leading block is nonsingular. The nonsingularity is recorded as an
Invertiblehypothesis for downstream Schur-complement and condition-number work; the display itself is againfromBlocks.Lean statement
theorem higham13_eq13_26_partition {r s α : Type*} [Fintype r] [DecidableEq r] [Semiring α] (A : Matrix (r ⊕ s) (r ⊕ s) α) [Invertible A.toBlocks₁₁] : A = Matrix.fromBlocks A.toBlocks₁₁ A.toBlocks₁₂ A.toBlocks₂₁ A.toBlocks₂₂
Problems and exercises
Problem 13.1
Problem 13.1 (Higham, 2nd ed., Chapter 13, p. 257), column-dominant block-tridiagonal LU step, in norm-level form. For a block tridiagonal
A = L UwithLandUblock bidiagonal andU_{i-1,i} = A_{i-1,i}, the local subordinate-norm estimate‖L_{i,i-1}‖ ≤ ‖A_{i,i-1}‖ ‖U_{i-1,i-1}^{-1}‖, together with the inherited column block diagonal dominance bound‖A_{i,i-1}‖ ‖U_{i-1,i-1}^{-1}‖ ≤ 1, gives the source bounds‖L_{i,i-1}‖ ≤ 1and‖U_{ii}‖ ≤ ‖A_{ii}‖ + ‖A_{i-1,i}‖.Lean statement
theorem higham13_problem13_1_column_step_bounds (ellNorm uDiagNorm aDiagNorm aLowerNorm aUpperNorm uPrevInvNorm : ℝ) (hEll : ellNorm ≤ aLowerNorm * uPrevInvNorm) (hColDom : aLowerNorm * uPrevInvNorm ≤ 1) (hUDiag : uDiagNorm ≤ aDiagNorm + ellNorm * aUpperNorm) (hUpperNonneg : 0 ≤ aUpperNorm) : ellNorm ≤ 1 ∧ uDiagNorm ≤ aDiagNorm + aUpperNormProblem 13.2
Problem 13.2 (Higham, 2nd ed., Chapter 13, p. 257): for the 1-norm and infinity norm, point diagonal dominance and block diagonal dominance do not imply each other. The 1-norm statements use column diagonal dominance and block-column dominance; the infinity-norm statements use row diagonal dominance and block-row dominance.
Lean statement
theorem higham13_problem13_2_incomparability : (IsDiagDominant 4 higham13_problem13_2_point_col_not_block_col_matrix ∧ ¬ IsBlockDiagDomCol 2 higham13_problem13_2_point_col_not_block_col_blockNormOne higham13_problem13_2_point_col_not_block_col_invDiagOne) ∧ (IsBlockDiagDomCol 2 higham13_problem13_2_block_not_point_blockNormOne higham13_problem13_2_block_not_point_invDiagOne ∧ ¬ IsDiagDominant 4 higham13_problem13_2_block_not_point_matrix) ∧ (IsRowDiagDominant 4 higham13_problem13_2_point_row_not_block_row_matrix ∧ ¬ IsBlockDiagDomRow 2 higham13_problem13_2_point_row_not_block_row_blockNormInf higham13_problem13_2_point_row_not_block_row_invDiagInf) ∧ (IsBlockDiagDomRow 2 higham13_problem13_2_block_not_point_blockNormInf higham13_problem13_2_block_not_point_invDiagInf ∧ ¬ IsRowDiagDominant 4 higham13_problem13_2_block_not_point_matrix)higham13_
problem13_ · 8 more declarations under this item2_ incomparability Problem 13.4
Source-indexed exact-κ bounds with
rhoinstantiated as the formal max-entry growth factor. This specializeshigham13_problem13_4_maxEntry_bounds_from_source_schur_growth_exact_kappaby deriving the source Schur-growth premise fromgrowthFactorEntry. The remaining mathematical source obligation is the concrete GE/stage bookkeeping certificate||S||_max <= ||U||_maxfor the growth-factor matrixU.Lean statement
theorem higham13_problem13_4_maxEntry_bounds_from_source_growthFactorEntry_exact_kappa {r s : ℕ} (hr : 0 < r) (hs : 0 < s) (hN : 0 < r + s) (A U : Fin (r + s) → Fin (r + s) → ℝ) (A11 : Matrix (Fin r) (Fin r) ℝ) (A12 : Matrix (Fin r) (Fin s) ℝ) (A21 : Matrix (Fin s) (Fin r) ℝ) (A22 : Matrix (Fin s) (Fin s) ℝ) [Invertible A11] [Invertible (A22 - A21 * ⅟A11 * A12)] [Invertible (Matrix.fromBlocks A11 A12 A21 A22)] (hA11_block : A11 = fun i j : Fin r => A (finSumFinEquiv (Sum.inl i : Fin r ⊕ Fin s)) (finSumFinEquiv (Sum.inl j : Fin r ⊕ Fin s))) (hA12_block : A12 = fun (i : Fin r) (j : Fin s) => A (finSumFinEquiv (Sum.inl i : Fin r ⊕ Fin s)) (finSumFinEquiv (Sum.inr j : Fin r ⊕ Fin s))) (hA21_block : A21 = fun (i : Fin s) (j : Fin r) => A (finSumFinEquiv (Sum.inr i : Fin r ⊕ Fin s)) (finSumFinEquiv (Sum.inl j : Fin r ⊕ Fin s))) (hA22_block : A22 = fun i j : Fin s => A (finSumFinEquiv (Sum.inr i : Fin r ⊕ Fin s)) (finSumFinEquiv (Sum.inr j : Fin r ⊕ Fin s))) (hApos : 0 < maxEntryNorm hN A) (n : ℕ) (hsn : (s : ℝ) ≤ (n : ℝ)) (hS_le_U : maxEntryNormRect hs hs (A22 - A21 * ⅟A11 * A12) ≤ maxEntryNorm hN U) : maxEntryNormRect hs hr ((A21 * ⅟A11 : Matrix (Fin s) (Fin r) ℝ)) ≤ (n : ℝ) * growthFactorEntry hN A U hApos * (maxEntryNormRect hN hN A * maxEntryNormRect hN hN (nonsingInv (r + s) A)) ∧ maxEntryNormRect hs hs (A22 - A21 * ⅟A11 * A12) * maxEntryNormRect hs hs ((⅟(A22 - A21 * ⅟A11 * A12)) : Matrix (Fin s) (Fin s) ℝ) ≤ growthFactorEntry hN A U hApos * (maxEntryNormRect hN hN A * maxEntryNormRect hN hN (nonsingInv (r + s) A))higham13_
problem13_ · 66 more declarations under this item4_ max Entry_ bounds_ from_ source_ growth Factor Entry_ exact_ kappa Problem 13.5
Problem 13.5 (Higham, 2nd ed., Chapter 13, p. 258): if
A = [[A11, A12], [A21, A22]]is point diagonally dominant by columns on the leading block columns andA11_invis a right inverse ofA11, then‖A21 A11⁻¹‖₁ ≤ 1. The nonsingularity assumption onA11is represented by the explicit right-inverse equationA11 * A11_inv = I, matching the repository's function-matrix API.Lean statement
theorem higham13_problem13_5_oneNormRect_bound {r s : ℕ} (A11 : Fin r → Fin r → ℝ) (A21 : Fin s → Fin r → ℝ) (A11_inv : Fin r → Fin r → ℝ) (hdom : ∀ j : Fin r, higham13_problem13_5_columnOff A11 j + higham13_problem13_5_trailingCol A21 j ≤ |A11 j j|) (hright : ∀ i j : Fin r, ∑ k : Fin r, A11 i k * A11_inv k j = if i = j then 1 else 0) : oneNormRect (rectMatMul A21 A11_inv) ≤ 1higham13_
problem13_ · 3 more declarations under this item5_ one Norm Rect_ bound Problem 13.7
Schur determinant identity. For a block matrix
X = [[A, B], [C, D]]with invertible leading blockA, Mathlib's Schur complement determinant theorem givesdet X = det A * det (D - C A^{-1} B).Lean statement
theorem higham13_problem13_7_det_schur {m n α : Type*} [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n] [CommRing α] (A : Matrix m m α) (B : Matrix m n α) (C : Matrix n m α) (D : Matrix n n α) [Invertible A] : (Matrix.fromBlocks A B C D).det = A.det * (D - C * ⅟A * B).dethigham13_
problem13_ · 1 more declaration under this item7_ det_ schur Problem 13.8
Block inverse formula around an invertible leading block. This is the standard inverse formula expressed in terms of the Schur complement
D - C A^{-1} B.Lean statement
theorem higham13_problem13_8_block_inverse {m n α : Type*} [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n] [CommRing α] (A : Matrix m m α) (B : Matrix m n α) (C : Matrix n m α) (D : Matrix n n α) [Invertible A] [Invertible (D - C * ⅟A * B)] [Invertible (Matrix.fromBlocks A B C D)] : ⅟(Matrix.fromBlocks A B C D) = Matrix.fromBlocks (⅟A + ⅟A * B * ⅟(D - C * ⅟A * B) * C * ⅟A) (-(⅟A * B * ⅟(D - C * ⅟A * B))) (-(⅟(D - C * ⅟A * B) * C * ⅟A)) (⅟(D - C * ⅟A * B))Problem 13.9
Resolvent identity:
(I - A B)^{-1} = I + A (I - B A)^{-1} B. The proof verifies that the displayed right-hand side is a right inverse ofI - A B; theInvertiblehypotheses record the nonsingularity conditions under which the inverses are interpreted.Lean statement
theorem higham13_problem13_9_resolvent_identity {m n α : Type*} [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n] [CommRing α] (A : Matrix m n α) (B : Matrix n m α) [Invertible (1 - A * B : Matrix m m α)] [Invertible (1 - B * A : Matrix n n α)] : ⅟(1 - A * B) = 1 + A * ⅟(1 - B * A) * Bhigham13_
problem13_ · 1 more declaration under this item9_ resolvent_ identity
Chapter 15 · Condition-number estimation all chapters
Definitions, theorems and lemmas
Algorithm 15.3
Algorithm 15.3 — full printed guarantee (Higham §15.3, Algorithm 15.3, p. 292), bundling both printed conclusions for the computed pair
(γ, x):γ ≤ ‖A‖₁and‖Ax‖₁ = γ‖x‖₁.Lean statement
theorem H15_Algorithm15_3_spec {n : ℕ} (hn : 0 < n) (A : Fin n → Fin n → ℝ) (fuel : ℕ) : H15_Algorithm15_3_gamma hn A fuel ≤ oneNorm A ∧ oneNormVec (fun i => ∑ j : Fin n, A i j * H15_Algorithm15_3_x hn A fuel j) = H15_Algorithm15_3_gamma hn A fuel * oneNormVec (H15_Algorithm15_3_x hn A fuel)H15_
Algorithm15_ · 3 more declarations under this item3_ spec Algorithm 15.4
Algorithm 15.4 — exact returned-ratio guarantee (Higham §15.3, Algorithm 15.4, p. 293). The estimator returns the maximum of its power-method estimate and the alternating-vector estimate. If the power arm wins,
H15_Algorithm15_3_stored_gamma_realizedsupplies the normalized iterate at which that stored estimate was computed. If the alternating arm wins, takew = lapackAltVecdirectly. Thus in either branch there are genuine vectorswandv = A wsatisfying the printed equality‖v‖₁ / ‖w‖₁ = γ, together withγ ≤ ‖A‖₁.Lean statement
theorem H15_Algorithm15_4_exact_ratio_witness {n : ℕ} (hn : 0 < n) (A : Fin n → Fin n → ℝ) : ∃ (w v : Fin n → ℝ), (∀ i, v i = ∑ j : Fin n, A i j * w j) ∧ oneNormVec v / oneNormVec w = H15_Algorithm15_4_gamma hn A ∧ H15_Algorithm15_4_gamma hn A ≤ oneNorm AH15_
Algorithm15_ · 4 more declarations under this item4_ exact_ ratio_ witness Algorithm 15.5
Algorithm 15.5 solves
U y = d. Immediate fromlinpackDbeing defined as the residualU y; recorded to match the book's step "solveU y = d".Lean statement
theorem linpackY_solves {n : ℕ} (U : Fin n → Fin n → ℝ) (sgn : Fin n → (Fin n → ℝ) → ℝ) : matMulVec n U (linpackY U sgn) = linpackD U sgnlinpack
Y_ · 2 more declarations under this itemsolves Theorem 15.6
Theorem 15.6 (Dixon), closed source-shaped endpoint. For a certified inverse
B = A⁻¹, a positive integerk, andθ > 1, the actual inverse Gram matrix isBᵀB = (AAᵀ)⁻¹; the left powered inequality holds for every unit vector; and the right powered inequality holds for a uniform sphere point with probability at least1 - 0.8 * θ^(-k/2) * sqrt n. The powered event is exactly the nonnegative2k-th-power form of display (15.7):‖B‖₂ ≤ θ * (xᵀ(BᵀB)^k x)^(1/(2k)).Lean statement
theorem higham15_6_dixon_closed (d k : ℕ) (hk : 0 < k) (A B : Fin (d + 1) → Fin (d + 1) → ℝ) (hR : IsRightInverse (d + 1) A B) (hL : IsLeftInverse (d + 1) A B) (θ : ℝ) (hθ : 1 < θ) : IsInverse (d + 1) (matMul (d + 1) A (matTranspose A)) (matMul (d + 1) (matTranspose B) B) ∧ (∀ x : OrthogonalSphere (d + 1), finiteQuadraticForm (matPow (d + 1) (matMul (d + 1) (matTranspose B) B) k) (WithLp.ofLp (x : EuclideanSpace ℝ (Fin (d + 1)))) ≤ opNorm2 B ^ (2 * k)) ∧ ENNReal.ofReal (1 - ((4 : ℝ) / 5) * Real.sqrt (d + 1) * θ ^ (-(k : ℝ) / 2 : ℝ)) ≤ standardGaussianDirectionMeasure d {x : OrthogonalSphere (d + 1) | opNorm2 B ^ (2 * k) ≤ (θ ^ k) ^ 2 * finiteQuadraticForm (matPow (d + 1) (matMul (d + 1) (matTranspose B) B) k) (WithLp.ofLp (x : EuclideanSpace ℝ (Fin (d + 1))))}higham15_
6_ · 4 more declarations under this itemdixon_ closed Theorem 15.9
Theorem 15.9 (Ikebe; Higham, §15.6, p. 300), at its printed structural strength. For a nonempty irreducible tridiagonal matrix
A, any matrix carrying the actual certificateA * A_inv = Ihas the rank-one inverse representationA_inv i j = x i * y jfori ≤ j, andA_inv i j = p i * q jfori ≥ j. No LU factorization, pivot-nonzero premise, inverse-entry formula, or target-bearing rank condition is assumed.Lean statement
theorem H15_Theorem15_9_of_irreducible_rightInverse {n : ℕ} (hn : 0 < n) (T : TridiagData n) (A_inv : Fin n → Fin n → ℝ) (hIrred : IsIrreducibleTridiag T) (hRight : IsRightInverse n (tridiag_to_matrix T) A_inv) : ∃ (x y p q : Fin n → ℝ), (∀ i j : Fin n, i.val ≤ j.val → A_inv i j = x i * y j) ∧ (∀ i j : Fin n, j.val ≤ i.val → A_inv i j = p i * q j)H15_
Theorem15_ · 1 more declaration under this item9_ of_ irreducible_ right Inverse
Equations and other results
Equation (15.1)
For nonnegative diagonal scaling, the infinity norm of
|A⁻¹|dequals the matrix infinity norm ofA⁻¹D.Lean statement
theorem cond_norm_identity (n : ℕ) (_hn : 0 < n) (A_inv : Fin n → Fin n → ℝ) (d : Fin n → ℝ) (hd : ∀ i, 0 ≤ d i) : infNormVec (fun i => ∑ j : Fin n, |A_inv i j| * d j) = infNorm (fun i j => A_inv i j * d j)cond_
norm_ · 2 more declarations under this itemidentity
Chapter 16 · The Sylvester equation all chapters
Equation (16.2)
Higham, 2nd ed., Chapter 16.1, equations (16.2)-(16.3), diagonal case: a positive uniform gap
|a_i - b_j| >= sigmamakes the square vec/Kronecker Sylvester coefficient nonsingular.Lean statement
theorem sylvesterVecCoeff_diagonal_det_ne_zero_of_entrywise_abs_ge (n : Nat) (a b : Fin n -> Real) (sigma : Real) (hsigma : 0 < sigma) (hgap : forall i j, sigma <= |a i - b j|) : (sylvesterVecCoeff n n (Matrix.diagonal a) (Matrix.diagonal b)).det ≠ 0sylvester
Vec · 180 more declarations under this itemCoeff_ diagonal_ det_ ne_ zero_ of_ entrywise_ abs_ ge Equation (16.4)
Higham, 2nd ed., Chapter 16.2, equations (16.4)-(16.8), converse two-by-two spectral certificate: a nonnegative real discriminant for the adjacent real Schur block gives a concrete real eigenline. This is the algebraic obstruction to treating such a block as a genuine irreducible real
2 x 2block.Lean statement
theorem sylvesterTwoColumnRealSchurBlock_exists_real_eigenvector_of_disc_nonneg (n : Nat) (T : RMatFn n n) (p q : Fin n) (hdisc : 0 ≤ (T p p - T q q) ^ 2 + 4 * T p q * T q p) : exists x : Fin 2 -> Real, x ≠ 0 ∧ exists nu : Real, Matrix.mulVec (sylvesterTwoColumnRealSchurBlock n T p q) x = fun k => nu * x ksylvester
Two · 230 more declarations under this itemColumn Real Schur Block_ exists_ real_ eigenvector_ of_ disc_ nonneg Equation (16.9)
Higham, 2nd ed., Chapter 16.2, equation (16.9), conditional exact residual-bound transport. Any Schur-coordinate Frobenius residual bound transfers unchanged to the reconstructed original-coordinate iterate.
Lean statement
theorem frobNormRect_sylvesterResidualRect_le_of_schur_transform (m n : Nat) (U R A : RMatFn m m) (V S B : RMatFn n n) (C Y : RMatFn m n) (rho : Real) (hU : IsOrthogonal m U) (hV : IsOrthogonal n V) (hA : A = rectMatMul U (rectMatMul R (matTranspose U))) (hB : B = rectMatMul V (rectMatMul S (matTranspose V))) (hres : frobNormRect (sylvesterResidualRect m n R S (rectMatMul (matTranspose U) (rectMatMul C V)) Y) <= rho) : frobNormRect (sylvesterResidualRect m n A B C (rectMatMul U (rectMatMul Y (matTranspose V)))) <= rhofrob
Norm · 18 more declarations under this itemRect_ sylvester Residual Rect_ le_ of_ schur_ transform Equation (16.15)
Source-facing two-sided Sylvester eta/xi infimum bound from SVD data.
Lean statement
theorem sylvesterBackwardErrorInf_two_sided_sqrt_xiSq_of_svdOptimalPerturbations (n : Nat) (A B C Y U V : Fin n -> Fin n -> Real) (sigma : Fin n -> Real) (alpha beta gamma : Real) (hSVD : IsSVD n Y U V sigma) (halpha : 0 < alpha) (hbeta : 0 < beta) (hgamma : 0 < gamma) (hpos : forall i j : Fin n, 0 < alpha ^ 2 * sigma j ^ 2 + beta ^ 2 * sigma i ^ 2 + gamma ^ 2) : Real.sqrt (xiSq n (svdResidual n U V (sylvesterResidual n A B C Y)) sigma alpha beta gamma / 3) <= sylvesterBackwardErrorInf n A B C Y alpha beta gamma ∧ sylvesterBackwardErrorInf n A B C Y alpha beta gamma <= Real.sqrt (xiSq n (svdResidual n U V (sylvesterResidual n A B C Y)) sigma alpha beta gamma)sylvester
Backward · 28 more declarations under this itemError Inf_ two_ sided_ sqrt_ xi Sq_ of_ svd Optimal Perturbations Equation (16.16)
ξ² is nonneg when all denominators are positive.
Lean statement
lemma xiSq_nonneg {n : ℕ} (R_tilde : Fin n → Fin n → ℝ) (σ : Fin n → ℝ) (α β γ : ℝ) (hpos : ∀ i j : Fin n, 0 < α ^ 2 * σ j ^ 2 + β ^ 2 * σ i ^ 2 + γ ^ 2) : 0 ≤ xiSq n R_tilde σ α β γEquation (16.21)
Lyapunov eta infimum bounded by the mu-scaled relative residual.
Lean statement
theorem lyapunovBackwardErrorInf_le_mu_relative_residual_of_symmetric_spectral (n : Nat) (A C Y U : Fin n -> Fin n -> Real) (lam : Fin n -> Real) (alpha gamma lamStar : Real) (hY : Y = matMul n U (matMul n (diagMatrix lam) (matTranspose U))) (hU : IsOrthogonal n U) (hC : IsSymmetricFiniteMatrix C) (hYsym : IsSymmetricFiniteMatrix Y) (hpos : forall i j : Fin n, 0 < 2 * alpha ^ 2 * (lam i ^ 2 + lam j ^ 2) + gamma ^ 2) (hLam : forall i : Fin n, lamStar ^ 2 <= lam i ^ 2) (hDenom : 0 < 4 * alpha ^ 2 * lamStar ^ 2 + gamma ^ 2) (hScale : 0 < 2 * alpha * frobNorm Y + gamma) : lyapunovBackwardErrorInf n A C Y alpha gamma <= lyapunovAmplificationMu alpha gamma (frobNorm Y) lamStar * (frobNorm (lyapunovResidual n A C Y) / (2 * alpha * frobNorm Y + gamma))lyapunov
Backward · 49 more declarations under this itemError Inf_ le_ mu_ relative_ residual_ of_ symmetric_ spectral Equation (16.23)
Higham, 2nd ed., Section 16.3-16.4, equations (16.23)-(16.24): a positive lower bound on the exact infimum model of
sep(A,B)instantiates the structured first-orderPsicertificate through the safe reciprocal condition value1 / sigma.Lean statement
theorem sylvesterPsi_of_pos_le_sylvesterSepInf_isPsiFirstOrderBound (n : Nat) (A B X : Fin n -> Fin n -> Real) (alpha beta gamma sigma : Real) (halpha : 0 < alpha) (hbeta : 0 < beta) (hgamma : 0 < gamma) (hsigma : 0 < sigma) (hX : 0 < frobNorm X) (hle : sigma <= sylvesterSepInf n A B) : SylvesterPsiFirstOrderBound n A B X alpha beta gamma (sylvesterPsi_of_inverseOpBound n X alpha beta gamma (1 / sigma))sylvester
Psi_ · 60 more declarations under this itemof_ pos_ le_ sylvester Sep Inf_ is Psi First Order Bound Equation (16.25)
Higham, 2nd ed., Chapter 16.3, equations (16.25)-(16.26): a Sylvester operator sigma-min certificate makes the vectorized coefficient map injective.
Lean statement
theorem sylvesterVecCoeff_mulVec_injective_of_operator_sigmaMin (n : Nat) (A B : Fin n -> Fin n -> Real) (sigma : Real) (hsigma : 0 < sigma) (hSigmaMin : forall Y : Fin n -> Fin n -> Real, sigma * frobNorm Y <= frobNorm (sylvesterOp n A B Y)) : Function.Injective (Matrix.mulVec (sylvesterVecCoeff n n A B))sylvester
Vec · 50 more declarations under this itemCoeff_ mul Vec_ injective_ of_ operator_ sigma Min Equation (16.26)
Higham, 2nd ed., Chapter 16.2.1 and 16.3, equations (16.26)-(16.27): under a positive Lyapunov operator sigma-min certificate, zero exact Lyapunov residual norm certifies that the residual-zero candidate is the unique exact solution. Scope: exact arithmetic and certificate transfer only. This removes the separate
SepLowerBoundassumption from the residual-zero uniqueness route; it does not construct the sigma-min certificate or model rounded residual arithmetic.Lean statement
theorem lyapunov_solution_eq_of_residual_norm_zero_sigmaMin (n : Nat) (A C X Xhat : Fin n -> Fin n -> Real) (sigma : Real) (hsigma : 0 < sigma) (hSigmaMin : forall Y : Fin n -> Fin n -> Real, sigma * frobNorm Y <= frobNorm (lyapunovOp n A Y)) (hExact : forall i j, lyapunovOp n A X i j = C i j) (hResidual : frobNorm (lyapunovResidual n A C Xhat) = 0) : forall i j, X i j = Xhat i jlyapunov_
solution_ · 125 more declarations under this itemeq_ of_ residual_ norm_ zero_ sigma Min Equation (16.27)
Higham, 2nd ed., Chapter 16.3, equation (16.27): a finite Gram-eigenvalue lower bound for the printed Lyapunov vec/Kronecker coefficient instantiates the Lyapunov condition certificate with inverse-operator constant
1 / sqrt(lam).Lean statement
theorem lyapunovCond_of_vecCoeff_gram_eigenvalues_isLyapunovConditionFirstOrderBound (n : Nat) (A X : Fin n -> Fin n -> Real) (alpha gamma lam : Real) (halpha : 0 < alpha) (hgamma : 0 < gamma) (hlam : 0 < lam) (hX : 0 < frobNorm X) (hEig : forall p : Prod (Fin n) (Fin n), lam <= finiteHermitianEigenvalues (finiteMatrixGram (lyapunovVecCoeff n A)) (isSymmetricFiniteMatrix_finiteMatrixGram (lyapunovVecCoeff n A)) p) : LyapunovConditionFirstOrderBound n A X alpha gamma (lyapunovCond_of_inverseOpBound n X alpha gamma (1 / Real.sqrt lam))lyapunov
Cond_ · 71 more declarations under this itemof_ vec Coeff_ gram_ eigenvalues_ is Lyapunov Condition First Order Bound Equation (16.29)
Higham, 2nd ed., Chapter 16.4, equation (16.29): source-numbered alias for the strict real-quasi-Schur shifted determinant-discharge practical residual endpoint.
Lean statement
theorem H16_eq16_29_realQuasiSchur_strictBlockMap_shifted_computed_residual_certificate (m n : Nat) (U R A : RMatFn m m) (V S B : RMatFn n n) (pA : Fin m -> Nat) (pB : Fin n -> Nat) (C X Xhat Rhat Ru : RMatFn m n) (hU : IsOrthogonal m U) (hV : IsOrthogonal n V) (hA : A = rectMatMul U (rectMatMul R (matTranspose U))) (hB : B = rectMatMul V (rectMatMul S (matTranspose V))) (hpAmono : Monotone pA) (hpAcard : forall c : Nat, (Finset.univ.filter (fun i : Fin m => pA i = c)).card <= 2) (hRstrict : forall i j : Fin m, pA j < pA i -> R i j = 0) (hpBmono : Monotone pB) (hpBcard : forall c : Nat, (Finset.univ.filter (fun j : Fin n => pB j = c)).card <= 2) (hpBstrict : forall {i j : Fin n}, j < i -> pB j < pB i) (hSstrict : forall i j : Fin n, pB j < pB i -> S i j = 0) (hshift : forall k : Fin n, Not (Matrix.det (sylvesterTriangularShiftedCoeff m R (S k k)) = 0)) (hX : IsSylvesterSolutionRect m n A B C X) (hBudget : IsSylvesterComputedResidualBudget m n A B C Xhat Rhat Ru) (hXhat : 0 < sylvesterMaxEntryNormRect m n Xhat) : sylvesterMaxEntryNormRect m n (fun i j => X i j - Xhat i j) / sylvesterMaxEntryNormRect m n Xhat <= sylvesterVecMaxNorm m n (sylvesterPracticalBudgetVec m n (sylvesterVecCoeffNonsingInvAbs m n A B) Rhat Ru) / sylvesterMaxEntryNormRect m n XhatH16_
eq16_ · 88 more declarations under this item29_ real Quasi Schur_ strict Block Map_ shifted_ computed_ residual_ certificate Equation (16.30)
The residual for equation (16.30) is zero exactly when the generalized Sylvester equation holds.
Lean statement
theorem generalizedSylvesterAXB_CXD_residual_zero_iff_solution (m n : Nat) (A C : RMatFn m m) (B D : RMatFn n n) (E X : RMatFn m n) : (forall i j, generalizedSylvesterAXB_CXD_residual m n A C B D E X i j = 0) <-> IsGeneralizedSylvesterAXB_CXD_Solution m n A C B D E XEquation (16.31)
Higham, 2nd ed., Chapter 16.5, equation (16.31): the two residuals vanish exactly when the coupled generalized Sylvester equations hold.
Lean statement
theorem generalizedSylvesterPair_residual_zero_iff_solution (m n : Nat) (A D : RMatFn m m) (B E : RMatFn n n) (C F0 X Y : RMatFn m n) : ((forall i j, generalizedSylvesterPairResidualLeft m n A B C X Y i j = 0) ∧ (forall i j, generalizedSylvesterPairResidualRight m n D E F0 X Y i j = 0)) <-> IsGeneralizedSylvesterPairSolution m n A D B E C F0 X YEquation (16.32)
The residual for equation (16.32) is zero exactly when the Riccati source equation holds.
Lean statement
theorem riccatiResidual_zero_iff_solution (m n : Nat) (A : RMatFn m m) (B : RMatFn n n) (F : RMatFn n m) (G X : RMatFn m n) : (forall i j, riccatiResidual m n A B F G X i j = 0) <-> IsRiccatiSolution m n A B F G X
Chapter 17 · Stationary iterative methods all chapters
Equation (17.3)
Finite-sum closed form for the source-sign computed stationary iteration.
Lean statement
theorem sourceComputedIteration_finite_sum (n : ℕ) (M N M_inv : Fin n → Fin n → ℝ) (b : Fin n → ℝ) (x_hat ξ : ℕ → Fin n → ℝ) (hLeft : IsLeftInverse n M M_inv) (hIter : SourceComputedIteration n M N b x_hat ξ) (m : ℕ) : ∀ i, x_hat (m + 1) i = matMulVec n (matPow n (iterMatrix n M_inv N) (m + 1)) (x_hat 0) i + ∑ k ∈ Finset.range (m + 1), matMulVec n (matPow n (iterMatrix n M_inv N) k) (matMulVec n M_inv (fun j => b j - ξ (m - k) j)) isource
Computed · 1 more declaration under this itemIteration_ finite_ sum Equation (17.4)
An exact solution of
Ax = bis a fixed point of the stationary affine mapx ↦ Gx + M⁻¹b, whereG = M⁻¹N.Lean statement
theorem stationary_solution_fixed_point (n : ℕ) (A M N M_inv : Fin n → Fin n → ℝ) (hS : SplittingSpec n A M N M_inv) (b x : Fin n → ℝ) (hAx : ∀ i, ∑ j : Fin n, A i j * x j = b i) : ∀ i, x i = matMulVec n (iterMatrix n M_inv N) x i + matMulVec n M_inv b istationary_
solution_ · 1 more declaration under this itemfixed_ point Equation (17.5)
Finite-sum forward-error recurrence for the source-sign computed stationary iteration.
Lean statement
theorem sourceComputedIteration_error_finite_sum (n : ℕ) (A M N M_inv : Fin n → Fin n → ℝ) (hS : SplittingSpec n A M N M_inv) (b x : Fin n → ℝ) (hAx : ∀ i, ∑ j : Fin n, A i j * x j = b i) (x_hat : ℕ → (Fin n → ℝ)) (ξ : ℕ → (Fin n → ℝ)) (hIter : SourceComputedIteration n M N b x_hat ξ) (m : ℕ) : ∀ i, x i - x_hat (m + 1) i = matMulVec n (matPow n (iterMatrix n M_inv N) (m + 1)) (fun j => x j - x_hat 0 j) i + ∑ k ∈ Finset.range (m + 1), matMulVec n (matPow n (iterMatrix n M_inv N) k) (matMulVec n M_inv (ξ (m - k))) iEquation (17.8)
Eq. 17.8 (Normwise forward bound): ‖e_{m+1}‖∞ ≤ q^{m+1}·‖e₀‖∞ + μ·‖M⁻¹‖∞/(1−q) where q ≥ ‖G‖∞ and μ ≥ ‖ξ_k‖∞ for all k. Proved by induction from
normwise_one_step_boundusing geometric contraction.Lean statement
theorem normwise_forward_bound (n : ℕ) (hn : 0 < n) (A M N M_inv : Fin n → Fin n → ℝ) (hS : SplittingSpec n A M N M_inv) (b x : Fin n → ℝ) (hAx : ∀ i, ∑ j : Fin n, A i j * x j = b i) (x_hat : ℕ → (Fin n → ℝ)) (ξ : ℕ → (Fin n → ℝ)) (hIter : ComputedIteration n M N b x_hat ξ) (q : ℝ) (hq : 0 ≤ q) (hq1 : q < 1) (hG : infNorm (iterMatrix n M_inv N) ≤ q) (μ : ℝ) (hμ : 0 ≤ μ) (hξ_bound : ∀ k, infNormVec (ξ k) ≤ μ) (m : ℕ) : infNormVec (fun i => x i - x_hat (m + 1) i) ≤ q ^ (m + 1) * infNormVec (fun i => x i - x_hat 0 i) + μ * infNorm M_inv / (1 - q)Equation (17.10)
|ξ_k,i| ≤ c_n u(1+θ_x) ∑_j (|M_{ij}|+|N_{ij}|)|x_j|.
Lean statement
theorem local_error_simplified (n : ℕ) (M N : Fin n → Fin n → ℝ) (b x : Fin n → ℝ) (hAx : ∀ i, ∑ j : Fin n, (M i j - N i j) * x j = b i) (x_hat : ℕ → (Fin n → ℝ)) (ξ : ℕ → (Fin n → ℝ)) (cn_u θ_x : ℝ) (hcn : 0 ≤ cn_u) (_hθ : 0 ≤ θ_x) (hx_bound : ∀ k i, |x_hat k i| ≤ θ_x * |x i|) (hLocal : LocalErrorBound n M N b x_hat ξ cn_u) : ∀ k i, |ξ k i| ≤ cn_u * (1 + θ_x) * ∑ j : Fin n, (|M i j| + |N i j|) * |x j|Equation (17.16)
Eq. 17.16 (Jacobi): |M| + |N| = |A| for M = diag(A), N = diag(A) − A.
Lean statement
theorem jacobi_splitting_abs (n : ℕ) (A : Fin n → Fin n → ℝ) (M N : Fin n → Fin n → ℝ) (hM : ∀ i j, M i j = if i = j then A i i else 0) (hN : ∀ i j, N i j = M i j - A i j) : ∀ i j, |M i j| + |N i j| = |A i j|jacobi_
splitting_ · 2 more declarations under this itemabs Equation (17.17)
Eq. 17.17 (SOR): |M| + |N| ≤ f(ω)|A| where f(ω) = (1+|1−ω|)/ω.
Lean statement
theorem sor_splitting_bound (n : ℕ) (A : Fin n → Fin n → ℝ) (ω : ℝ) (hω_pos : 0 < ω) (D L U : Fin n → Fin n → ℝ) (hDecomp : ∀ i j, A i j = D i j + L i j + U i j) (hD : ∀ i j, i ≠ j → D i j = 0) (hL : ∀ i j, j.val ≥ i.val → L i j = 0) (hU : ∀ i j, j.val ≤ i.val → U i j = 0) (M_sor N_sor : Fin n → Fin n → ℝ) (hM : ∀ i j, M_sor i j = (1 / ω) * (D i j + ω * L i j)) (hN : ∀ i j, N_sor i j = (1 / ω) * ((1 - ω) * D i j - ω * U i j)) : ∀ i j, |M_sor i j| + |N_sor i j| ≤ ((1 + |1 - ω|) / ω) * |A i j|sor_
splitting_ · 3 more declarations under this itembound Equation (17.18)
AG = HA: Since A = M − N, both sides equal N − NM⁻¹N.
Lean statement
theorem AG_eq_HA (n : ℕ) (A M N M_inv : Fin n → Fin n → ℝ) (hS : SplittingSpec n A M N M_inv) : matMul n A (iterMatrix n M_inv N) = matMul n (dualIterMatrix n N M_inv) AAG_
eq_ · 4 more declarations under this itemHA Equation (17.19)
Eq. 17.19 (Normwise residual bound): ‖r_{m+1}‖∞ ≤ q^{m+1}·‖r₀‖∞ + μ·‖I−H‖∞/(1−q) where q ≥ ‖H‖∞ and μ ≥ ‖ξ_k‖∞ for all k. Derived by induction from
normwise_one_step_residual_boundusing geometric contraction.Lean statement
theorem normwise_residual_bound (n : ℕ) (hn : 0 < n) (A M N M_inv : Fin n → Fin n → ℝ) (hS : SplittingSpec n A M N M_inv) (b x : Fin n → ℝ) (hAx : ∀ i, ∑ j : Fin n, A i j * x j = b i) (x_hat : ℕ → (Fin n → ℝ)) (ξ : ℕ → (Fin n → ℝ)) (hIter : ComputedIteration n M N b x_hat ξ) (q : ℝ) (hq : 0 ≤ q) (hq1 : q < 1) (hH : infNorm (dualIterMatrix n N M_inv) ≤ q) (μ : ℝ) (hμ : 0 ≤ μ) (hξ_bound : ∀ k, infNormVec (ξ k) ≤ μ) (m : ℕ) : infNormVec (fun i => b i - ∑ j, A i j * x_hat (m + 1) j) ≤ q ^ (m + 1) * infNormVec (fun i => b i - ∑ j, A i j * x_hat 0 j) + μ * infNorm (matSub_id n (dualIterMatrix n N M_inv)) / (1 - q)normwise_
residual_ · 3 more declarations under this itembound Equation (17.21)
Exact stationary iterates for a consistent singular system satisfy the same finite affine unrolling
x_{m+1} = G^{m+1} x_0 + sum_{k=0}^m G^k M⁻¹ b. The proof uses only the nonsingularity ofM, not nonsingularity ofA, which is precisely why the identity remains valid at the start of the singular-system analysis.Lean statement
theorem singular_stationary_iterate_finite_sum (n : ℕ) (A M N M_inv : Fin n → Fin n → ℝ) (hS : SplittingSpec n A M N M_inv) (b : Fin n → ℝ) (x_seq : ℕ → Fin n → ℝ) (hIter : SourceComputedIteration n M N b x_seq (fun _ _ => 0)) (m : ℕ) : ∀ i, x_seq (m + 1) i = matMulVec n (matPow n (iterMatrix n M_inv N) (m + 1)) (x_seq 0) i + ∑ k ∈ Finset.range (m + 1), matMulVec n (matPow n (iterMatrix n M_inv N) k) (matMulVec n M_inv b) isingular_
stationary_ · 1 more declaration under this itemiterate_ finite_ sum Equation (17.29)
Finite normwise surface: a uniform local-error norm bound
||ξ_t||∞ ≤ μbounds||S_m||∞byμ sum ||G^k E M⁻¹||∞. The source's displayedc_n u(1+gamma_x)(||M||∞+||N||∞)||x||∞is obtained by instantiatingμwith the normwise local-error estimate.Lean statement
theorem singularErrorSourceTerm_norm_bound (n : ℕ) (hn : 0 < n) (G E M_inv : Fin n → Fin n → ℝ) (ξ : ℕ → Fin n → ℝ) (μ : ℝ) (hμ : 0 ≤ μ) (hξ : ∀ t : ℕ, infNormVec (ξ t) ≤ μ) (m : ℕ) : infNormVec (singularErrorSourceTerm n G E M_inv ξ m) ≤ μ * singularErrorSourceNormSum n G E M_inv msingular
Error · 4 more declarations under this itemSource Term_ norm_ bound
Chapter 18 · Matrix powers all chapters
Theorem 18.1
Theorem 18.1 (Higham–Knight), complex Jordan data, limit form, abstract error model — Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., §18.2, Theorem 18.1 (pp. 347–348). Let
Abe a REALn×nmatrix (the computed iteration is a floating-point object, hence real, matching the book's setting) with COMPLEX Jordan-form similarity data:X·X⁻¹ = Iover ℂ (as the vector actionIsComplexMatrixRightInverse),X⁻¹  X = Jfor the real-cast i j = ((A i j : ℝ) : ℂ),Jupper bidiagonal with‖J_{ii}‖ ≤ ρ < 1, superdiagonal moduli ≤ 1, all other entries zero, and every run of consecutive nonzero superdiagonal entries of length ≤t − 1(max Jordan block size ≤t, viacJordanRunLength); all1 ≤ t. Under the Higham–Knight condition (18.13)4t·c·κ∞(X)·‖A‖∞ < (1−ρ)^t,κ∞(X) := complexMatrixInfNorm X * complexMatrixInfNorm X_inv, every real computed-power sequencevwith per-step componentwise budgetc(ComputedMatPowVec, eqs (18.10)–(18.11)) satisfies‖v_m‖∞ → 0. Scope: complex Jordan data as hypothesis (every complex matrix has one; JNF existence itself is not formalized — Mathlib lacks it); this is the full generality of the printed statement for a real input matrixA. No assumed contraction/absorption hypothesis: the absorbing similarity is PROVED from the Jordan data (complex_jordan_similarity_absorbs, δ-scaling construction with the(1+1/m)^m < e < 4optimisation).Lean statement
theorem higham_18_1_complex_jordan_tendsto (n : ℕ) (A : Fin n → Fin n → ℝ) (X X_inv J : CMatrix n n) (hXr : IsComplexMatrixRightInverse X X_inv) (hsim : complexMatrixMul X_inv (complexMatrixMul (fun i j => ((A i j : ℝ) : ℂ)) X) = J) (hshape : ∀ i j : Fin n, (j : ℕ) ≠ (i : ℕ) → (j : ℕ) ≠ (i : ℕ) + 1 → J i j = 0) (ρ : ℝ) (hρ0 : 0 ≤ ρ) (hρ1 : ρ < 1) (hdiagbd : ∀ i, ‖J i i‖ ≤ ρ) (hsup : ∀ i j : Fin n, (j : ℕ) = (i : ℕ) + 1 → ‖J i j‖ ≤ 1) (t : ℕ) (ht1 : 1 ≤ t) (hrun : ∀ k, cJordanRunLength n J k ≤ t - 1) (v : ℕ → (Fin n → ℝ)) (c : ℝ) (hc : 0 ≤ c) (hComp : ComputedMatPowVec n A v c) (hCond : 4 * (t : ℝ) * c * (complexMatrixInfNorm X * complexMatrixInfNorm X_inv) * infNorm A < (1 - ρ) ^ t) : Filter.Tendsto (fun m => infNormVec (v m)) Filter.atTop (nhds 0)higham_
18_ · 5 more declarations under this item1_ complex_ jordan_ tendsto
Chapter 19 · QR factorization all chapters
Definitions, theorems and lemmas
Theorem 19.4
Householder QR backward error for a tall rectangular matrix, stated with the public Split 3B source-facing name. For
A : R^(m x n)with0 < nandn <= m, the concrete zero-aware Householder QR panel algorithm returns an upper-trapezoidalR_hatand an exact orthogonal witnessQsuch thatA + dA = Q R_hat, with each perturbation column bounded bygamma_tilde fp m ntimes the corresponding input column norm.Lean statement
theorem householder_qr_backward_error (fp : FPModel) (m n : Nat) (A : Fin m -> Fin n -> Real) (hn : 0 < n) (hnm : n <= m) (hvalid : gammaValid fp (n * householderConstructApplyGammaIndex m)) : HouseholderQRBackwardError m n A (fl_householderQRPanel_Q fp m n A) (fl_householderQRPanel_R fp m n A) (gamma_tilde fp m n)householder_
qr_ · 1 more declaration under this itembackward_ error Theorem 19.10
Givens QR backward error for a tall rectangular matrix, stated with the public Split 3B source-facing name. For
A : R^(m x n)with0 < nandn <= m, the concrete staged Givens QR algorithm returns an upper-trapezoidalR_hatand an exact orthogonal witnessQsuch thatA + dA = Q R_hat, with each perturbation column bounded by the repository's conservativegamma_tilde fp m ntimes the corresponding input column norm.Lean statement
theorem givens_qr_backward_error (fp : FPModel) (m n : Nat) (A : Fin m -> Fin n -> Real) (_hn : 0 < n) (_hnm : n <= m) (hvalid : gammaValid fp 8) : GivensQRBackwardError m n A (Classical.choose (fl_givensQRStageFold_sequence_columnFrob_backward_error_uniform fp m n A (givensQRStageCount m n) hvalid)) (fl_givensQRStageFold fp m n (givensQRStageCount m n) A) (gamma_tilde fp m n)givens_
qr_ · 3 more declarations under this itembackward_ error
Equations and other results
Equation (19.7)
Columnwise rectangular matrix plus right-hand-side accumulation. This is the source-faithful Householder QR shape: each matrix column, and the right-hand side, may have its own rounded perturbation matrix at each step. The exact reflector sequence
P kis common, so the final representation still uses one theoretical orthogonal factorQ, while the perturbation bounds are columnwise.Lean statement
theorem rect_orthogonal_columnwise_vector_sequence_geometric (m n r : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ) (A_hat : ℕ → Fin m → Fin n → ℝ) (b_hat : ℕ → Fin m → ℝ) (P : ℕ → Fin m → Fin m → ℝ) (ΔPA : ℕ → Fin n → Fin m → Fin m → ℝ) (ΔPb : ℕ → Fin m → Fin m → ℝ) (c : ℝ) (hc : 0 ≤ c) (hInitA : A_hat 0 = A) (hInitb : b_hat 0 = b) (hP : ∀ k, k < r → IsOrthogonal m (P k)) (hΔPA : ∀ k, k < r → ∀ j : Fin n, frobNorm (ΔPA k j) ≤ c) (hΔPb : ∀ k, k < r → frobNorm (ΔPb k) ≤ c) (hNextA : ∀ k, k < r → ∀ i j, A_hat (k + 1) i j = matMulVec m (fun a b => P k a b + ΔPA k j a b) (fun a => A_hat k a j) i) (hNextb : ∀ k, k < r → b_hat (k + 1) = matMulVec m (fun a b => P k a b + ΔPb k a b) (b_hat k)) : ∃ (Q : Fin m → Fin m → ℝ) (ΔA : Fin m → Fin n → ℝ) (Δb : Fin m → ℝ), IsOrthogonal m Q ∧ (∀ i j, A_hat r i j = matMulRectLeft (matTranspose Q) (fun a b => A a b + ΔA a b) i j) ∧ (∀ i, b_hat r i = matMulVec m (matTranspose Q) (fun a => b a + Δb a) i) ∧ (∀ j : Fin n, vecNorm2 (fun i => ΔA i j) ≤ ((1 + c) ^ r - 1) * vecNorm2 (fun i => A i j)) ∧ vecNorm2 Δb ≤ ((1 + c) ^ r - 1) * vecNorm2 bEquation (19.8)
If each local step coefficient is already bounded by
gamma k, the residual accumulation overrsteps is bounded bygamma (r*k). This is the formal version of absorbing repeated first-order localgammabounds into one larger Highamgammaterm.Lean statement
lemma residualAccumBound_gamma_le_gamma_mul (fp : FPModel) (k : ℕ) : ∀ r : ℕ, gammaValid fp (r * k) → residualAccumBound (gamma fp k) r ≤ gamma fp (r * k)Equation (19.11)
Equation
(19.11)/Theorem 19.4 columnwise backward-error form, using the public source-facing theorem name.Lean statement
theorem eq19_11_columnwise_backward_error (fp : FPModel) (m n : Nat) (A : Fin m -> Fin n -> Real) (hn : 0 < n) (hnm : n <= m) (hvalid : gammaValid fp (n * householderConstructApplyGammaIndex m)) : HouseholderQRBackwardError m n A (fl_householderQRPanel_Q fp m n A) (fl_householderQRPanel_R fp m n A) (gamma_tilde fp m n)Equation (19.12)
Equation
(19.12)componentwise backward-error form, exposed as a source-labeled wrapper around the componentwise Theorem 19.4 surface.Lean statement
theorem eq19_12_componentwise_backward_error (fp : FPModel) (m n : Nat) (A : Fin m -> Fin n -> Real) (hn : 0 < n) (hnm : n <= m) (hvalid : gammaValid fp (n * householderConstructApplyGammaIndex m)) : HouseholderQRComponentwiseBackwardError m n A (fl_householderQRPanel_Q fp m n A) (fl_householderQRPanel_R fp m n A) (gamma_tilde fp m n * frobNorm A) ((m : Real) * gamma_tilde fp m n)Equation (19.25)
Equation
(19.25)source row for the concrete staged Givens QR path. This packages the verified columnwise sequence perturbation bound under the conservative coefficientH19.Theorem19_10.gamma_tilde. The exact printed-constant comparison remains a separate audit from this source-row wrapper.Lean statement
theorem eq19_25_columnwise_perturbation_bound (fp : FPModel) (m n : Nat) (A : Fin m -> Fin n -> Real) (hn : 0 < n) (hnm : n <= m) (hvalid : gammaValid fp 8) : Exists fun Q : Fin m -> Fin m -> Real => GivensQRBackwardError m n A Q (fl_givensQRStageFold fp m n (givensQRStageCount m n) A) (gamma_tilde fp m n)eq19_
25_ · 3 more declarations under this itemcolumnwise_ perturbation_ bound Equation (19.32)
Source-stage matrix recurrence
A_k = A_{k+1} R_kbehind Higham equation (19.32), with the current stage norm required to be nonzero.Lean statement
theorem sourceStage_matrix_recurrence {m n : Nat} (A : Fin m -> Fin n -> Real) (k : Fin n) (hdiag : Ne (gsColumnNorm2 (stageVectors A k.val k)) 0) : sourceStage A k.val = matMulRect m n n (sourceStage A (k.val + 1)) (stepR A k)Equation (19.33)
Iterated source-stage recurrence behind the product term in Higham equation (19.33).
Lean statement
theorem sourceStage_initial_matrix_recurrence {m n : Nat} (A : Fin m -> Fin n -> Real) {t : Nat} (ht : t <= n) (hdiag : forall k : Fin n, k.val < t -> Ne (gsColumnNorm2 (stageVectors A k.val k)) 0) : A = matMulRect m n n (sourceStage A t) (stepRProduct A t)
Chapter 20 · The least-squares problem all chapters
Definitions, theorems and lemmas
Lemma 20.6
The rank-one projector from equation (20.22) is a vector 2-norm contraction.
Lean statement
theorem lsLemma20_6Projector_vecNorm2Sq_le {m : ℕ} (s : Fin m → ℝ) (hsq : vecNorm2Sq s ≠ 0) (v : Fin m → ℝ) : vecNorm2Sq (matMulVec m (lsLemma20_6Projector s) v) ≤ vecNorm2Sq vls
Lemma20_ · 29 more declarations under this item6Projector_ vec Norm2Sq_ le Theorem 20.2
Paired source-facing augmented-system form. The hypotheses keep the printed full-rank assumptions for both
AandA + DeltaA; the proof uses full column rank ofAto construct the inverse block in (20.6) and then combines the already proved relative bounds (20.9) and (20.10).Lean statement
theorem lsAugmentedTheorem20_2_relative_bounds_full_column_rank {m n : ℕ} (νx : CVec n → ℝ) (hνx : IsComplexVectorNorm νx) (habsx : IsAbsoluteComplexVectorNorm νx) (νr : CVec m → ℝ) (hνr : IsComplexVectorNorm νr) (habsr : IsAbsoluteComplexVectorNorm νr) (A : Fin m → Fin n → ℝ) (DeltaA E : Fin m → Fin n → ℝ) (Deltab f b : Fin m → ℝ) (r s : Fin m → ℝ) (x y : Fin n → ℝ) (eps : ℝ) (hA : Function.Injective (rectMatMulVec A)) (_hApert : Function.Injective (rectMatMulVec (fun i j => A i j + DeltaA i j))) (hExact : LSAugmentedSystem A b (0 : Fin n → ℝ) r x) (hPert : LSAugmentedSystem (fun i j => A i j + DeltaA i j) (fun i => b i + Deltab i) (0 : Fin n → ℝ) s y) (heps : 0 ≤ eps) (hE : ∀ i j, 0 ≤ E i j) (hf : ∀ i, 0 ≤ f i) (hxnorm_pos : 0 < νx (realVecToComplex x)) (hrnorm_pos : 0 < νr (realVecToComplex r)) (hDeltaA : ∀ i j, |DeltaA i j| ≤ eps * E i j) (hDeltab : ∀ i, |Deltab i| ≤ eps * f i) : (νx (realVecToComplex (fun j => x j - y j)) / νx (realVecToComplex x) ≤ (eps * (νx (realVecToComplex (lsAugmentedEq20_8LeftMajorant (lsAplusOfGramNonsingInv A) (lsComponentwiseDataMajorant E f y))) + νx (realVecToComplex (lsAugmentedEq20_8RightMajorant (lsGramNonsingInv A) (lsComponentwiseTransposeMajorant E s))))) / νx (realVecToComplex x)) ∧ (νr (realVecToComplex (fun i => r i - s i)) / νr (realVecToComplex r) ≤ (eps * (νr (realVecToComplex (lsAugmentedEq20_7LeftMajorant A (lsAplusOfGramNonsingInv A) (lsComponentwiseDataMajorant E f y))) + νr (realVecToComplex (lsAugmentedEq20_7RightMajorant (lsAplusOfGramNonsingInv A) (lsComponentwiseTransposeMajorant E s))))) / νr (realVecToComplex r))ls
Augmented · 28 more declarations under this itemTheorem20_ 2_ relative_ bounds_ full_ column_ rank
Equations and other results
Equation (20.3)
Using Higham's residual sign convention, the augmented system is equivalent to the rectangular normal equations.
Lean statement
theorem LSAugmentedNormalSystem.iff_rectLSNormalEquations {m n : ℕ} (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ) (x : Fin n → ℝ) : LSAugmentedNormalSystem A b (lsResidualHigham A b x) x ↔ RectLSNormalEquations A b xEquation (20.4)
Equation (20.4) with
s = b + Deltab - (A + DeltaA)yis equivalent to the normal equations for the perturbed least-squares problem.Lean statement
theorem LSPerturbedAugmentedSystem.iff_rectLSNormalEquations {m n : ℕ} (A DeltaA : Fin m → Fin n → ℝ) (b Deltab : Fin m → ℝ) (y : Fin n → ℝ) : LSPerturbedAugmentedSystem A DeltaA b Deltab (lsResidualHigham (fun i j => A i j + DeltaA i j) (fun i => b i + Deltab i) y) y ↔ RectLSNormalEquations (fun i j => A i j + DeltaA i j) (fun i => b i + Deltab i) yiff_
rect · 2 more declarations under this itemLSNormal Equations Equation (20.15b)
Transpose action of the transformed QR block
[R; 0]on[h; d₂]:[R^T 0] [h; d₂] = R^T h.Lean statement
theorem lsQRTallBlock_transpose_mulVec_append {n k : ℕ} (R : Fin n → Fin n → ℝ) (h : Fin n → ℝ) (d2 : Fin k → ℝ) : (fun j : Fin n => ∑ i : Fin (n + k), lsQRTallBlock R i j * Fin.append h d2 i) = fun j : Fin n => ∑ i : Fin n, R i j * h iEquation (20.17)
The scaled augmented coefficient matrix
C(alpha) = [[alpha I, A], [A^T, 0]]is symmetric.Lean statement
theorem lsScaledAugmentedMatrix_symmetric {m n : ℕ} (alpha : ℝ) (A : Fin m → Fin n → ℝ) : IsSymmetricFiniteMatrix (lsScaledAugmentedMatrix alpha A)ls
Scaled · 12 more declarations under this itemAugmented Matrix_ symmetric Equation (20.22)
The two projector blocks in equation (20.22), here
PandI-P, add to the identity.Lean statement
theorem lsLemma20_6Projector_add_complement {m : ℕ} (s : Fin m → ℝ) (i j : Fin m) : lsLemma20_6Projector s i j + lsLemma20_6ProjectorComplement s i j = idMatrix m i jEquation (20.24)
Consistency consequence: the local full-row-rank condition makes the equality constraint
B x = dfeasible for every right-hand sided.Lean statement
theorem LSEFullRowRank.exists_feasible {p n : ℕ} {B : Fin p → Fin n → ℝ} (hB : LSEFullRowRank B) (d : Fin p → ℝ) : ∃ x : Fin n → ℝ, LSEFeasible B d xexists_
feasible · 10 more declarations under this item
Chapter 21 · Underdetermined systems all chapters
Lemma 21.2
Frobenius-norm form of the printed perturbation bound for the source-case single perturbation.
Lean statement
theorem higham21_lemma21_2_single_perturbation_frob_bound {m n : ℕ} (x : Fin n → ℝ) (DeltaA1 DeltaA2 : Fin m → Fin n → ℝ) : frobNormRect (undetLemma21_2SinglePerturbation x DeltaA1 DeltaA2) ≤ Real.sqrt (frobNormRect DeltaA1 ^ 2 + frobNormRect DeltaA2 ^ 2)higham21_
lemma21_ · 44 more declarations under this item2_ single_ perturbation_ frob_ bound Theorem 21.1
Source-facing relative asymptotic form. The displayed remainder ratio is explicitly
O(t^2), and the accompanying inequality is the exact meaning of the source's first-order coefficient plus quadratic remainder.Lean statement
theorem higham21_theorem21_1_relative_asymptotic_bound_of_gram_det_ne_zero {m n : Nat} (nu : CVec n -> Real) (hnu : IsComplexVectorNorm nu) (habs : IsAbsoluteComplexVectorNorm nu) (A DeltaA E : Fin m -> Fin n -> Real) (b Deltab f : Fin m -> Real) (rho beta : Real) (hdet : Not (Matrix.det (rectGram A : Matrix (Fin m) (Fin m) Real) = 0)) (hdet_t : forall t, |t| <= rho -> Not (Matrix.det (rectGram (higham21Eq21_7ScaledMatrix A DeltaA t) : Matrix (Fin m) (Fin m) Real) = 0)) (hb : Not (b = 0)) (hE : forall i j, 0 <= E i j) (hf : forall i, 0 <= f i) (hDeltaA : forall i j, abs (DeltaA i j) <= E i j) (hDeltab : forall i, abs (Deltab i) <= f i) (hrho : 0 < rho) (hbeta : 0 <= beta) (hG_t_inv : forall t, |t| <= rho -> frobNorm (undetGramNonsingInv (higham21Eq21_7ScaledMatrix A DeltaA t)) <= beta) : let x := rectMatMulVec (undetAplusOfGramNonsingInv A) b let remainderRatio : Real -> Real := fun t => nu (realVecToComplex (higham21Eq21_7ExactRemainder A DeltaA b Deltab (undetGramNonsingInv A) (undetGramNonsingInv (higham21Eq21_7ScaledMatrix A DeltaA t)) t)) / nu (realVecToComplex x) And (remainderRatio =O[nhds 0] (fun t : Real => t ^ 2)) (forall t, |t| <= rho -> nu (realVecToComplex (fun j => higham21Eq21_7PerturbedSolution A DeltaA b Deltab (undetGramNonsingInv (higham21Eq21_7ScaledMatrix A DeltaA t)) t j - higham21Eq21_7BaseSolution A b (undetGramNonsingInv A) j)) / nu (realVecToComplex x) <= |t| * ((nu (realVecToComplex (higham21Theorem21_1NullspaceMajorant A E b)) + nu (realVecToComplex (higham21Theorem21_1DataMajorant A E b f))) / nu (realVecToComplex x)) + remainderRatio t)higham21_
theorem21_ · 23 more declarations under this item1_ relative_ asymptotic_ bound_ of_ gram_ det_ ne_ zero Theorem 21.4
The printed full-row-rank and small-condition hypotheses construct the entire concrete Householder domain, including computed triangular nonbreakdown.
Lean statement
theorem Higham21QMethodFullRowRankComputedQRDomain.of_source_smallness {m k : Nat} (fp : FPModel) (A : Fin m -> Fin (m + k) -> Real) (hm : 0 < m) (hfull : lsRealRectColRank (finiteTranspose A) = m) (hvalid : gammaValid fp (Higham21QMethodRoundedGammaIndex m k)) (hCondSmall : gamma fp (Higham21QMethodRoundedGammaIndex m k) * higham21Cond2With A (undetAplusOfGramNonsingInv A) < 1) : Higham21QMethodFullRowRankComputedQRDomain m k fp Aof_
source_ · 45 more declarations under this itemsmallness
Chapter 22 · Vandermonde systems all chapters
Corollary 22.5
Higham (22.22): for four nodes (
n = 3), the generic factor product specializes to the six displayed factorsU₀ U₁ U₂ L₂ L₁ L₀. The entries of these factors are the definitions immediately preceding (22.17), so this theorem is the source-label bridge for the displayed four-by-four example rather than a second factorization assumption.Lean statement
theorem higham22_eq22_22_four_node_six_factor (theta beta gamma : ℕ → ℂ) (alpha : Fin 4 → ℂ) : higham22Algorithm22_2FactorProduct theta beta gamma alpha = ((higham22StageIIUpperFactor theta beta gamma alpha 0 * higham22StageIIUpperFactor theta beta gamma alpha 1) * higham22StageIIUpperFactor theta beta gamma alpha 2) * (higham22StageILowerFactor alpha 2 * (higham22StageILowerFactor alpha 1 * higham22StageILowerFactor alpha 0))higham22_
eq22_ · 3 more declarations under this item22_ four_ node_ six_ factor
Chapter 28 · A gallery of test matrices all chapters
Definitions, theorems and lemmas
Theorem 28.1
Stewart's concrete Gaussian Householder producer has exactly normalized Haar law in every dimension.
Lean statement
theorem stewartOrthogonalGroupLaw_eq_normalizedOrthogonalHaar (n : ℕ) : stewartOrthogonalGroupLaw n = normalizedOrthogonalHaar nstewart
Orthogonal · 1 more declaration under this itemGroup Law_ eq_ normalized Orthogonal Haar
Equations and other results
Equation (28.1)
The factor-derived inverse has exactly the entries printed in (28.1).
Lean statement
theorem factorInverseGram_eq_hilbertInverseFormula (n : ℕ) : hilbertCholeskyFactorInverse n * (hilbertCholeskyFactorInverse n).transpose = hilbertInverseFormula nfactor
Inverse · 2 more declarations under this itemGram_ eq_ hilbert Inverse Formula Equation (28.3)
Generic factorization bridge:
Hₙ = RᵀRfor the printed upper-triangular factor.Lean statement
theorem hilbertMatrix_eq_choleskyGram (n : ℕ) : hilbertMatrix n = (hilbertCholeskyFactor n).transpose * hilbertCholeskyFactor nhilbert
Matrix_ · 2 more declarations under this itemeq_ cholesky Gram