Proposition 2.4 -- off-diagonal nonpositivity + diagonal dominance implies PSD
ProvedDiscreteConvex.CombinatorialB.prop_2_4_offdiag_diagdom_psddiscrete-convex-analysislinear-algebraquadratic-forms
A symmetric matrix with off-diagonal nonpositivity (2.9) and diagonal dominance (2.10) is positive semidefinite.
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.64, Proposition 2.4.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_CombinatorialB_OffDiagNonpos import Definitions.Def_DiscreteConvex_CombinatorialB_DiagDominance
Formal statement
/-!
Murota, *Discrete Convex Analysis*, SIAM 2003, p.64, Proposition 2.4, in
`DiscreteConvex.CombinatorialB`.
-/
namespace DiscreteConvex.CombinatorialB
/-- **Proposition 2.4.** A symmetric matrix `L` with off-diagonal nonpositivity (2.9) and
diagonal dominance (2.10) is positive semidefinite. -/
theorem prop_2_4_offdiag_diagdom_psd {V : Type*} [Fintype V] [DecidableEq V]
(L : Matrix V V ℝ) (hsymm : L.IsSymm) (h9 : OffDiagNonpos L) (h10 : DiagDominance L) :
L.PosSemidef := by sorry
end DiscreteConvex.CombinatorialB
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.64, Proposition 2.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.