Appendix A, p. 20 β for an M-matrix A and every partition π, π: A_π regular, A_πβ»ΒΉ β₯ 0, A_πβ»ΒΉA_ππ β€ 0
ProvedPDASNewton.MMatrix.mmatrix_block_signslinear-algebram-matrixp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be an M-matrix: nonsingular, with for and entrywise. Let be any index set and its complement. Then the principal block is nonsingular and
both entrywise.
The paper takes these sign facts from Berman and Plemmons (p. 134); they are what makes every comparison argument of the proof of Theorem 3.2 work, and the invertibility guarantees that each step of the algorithm is well defined.
Formalization Note The nonsingularity of is stated as a conclusion because Lean's matrix inverse is zero on singular matrices; without it the sign conclusions would be empty. For the block is the empty matrix (determinant 1), and for the product has no columns.
Preamble
import Mathlib import Definitions.Def_PDASNewton_MMatrix_Setting open Filter Topology Matrix
Formal statement
namespace PDASNewton.MMatrix
theorem mmatrix_block_signs {n : β} (A : Matrix (Fin n) (Fin n) β) (hA : IsMMatrix A)
(S : Finset (Fin n)) :
IsUnit (principal A S).det β§ (β i j, 0 β€ (principal A S)β»ΒΉ i j) β§
β i j, ((principal A S)β»ΒΉ * offDiag A S) i j β€ 0 := by sorry
end PDASNewton.MMatrix
Source
HintermΓΌller, Ito, Kunisch, The primal-dual active set strategy as a semismooth Newton method, HAL hal-01660511v1, p. 20, Appendix A, proof of Theorem 3.2 (first sentence, citing [BP, p. 134])
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.