Proposition 2.6 -- off-diagonal nonpositivity iff submodularity of the quadratic form
ProvedDiscreteConvex.CombinatorialB.prop_2_6_offdiag_iff_submodulardiscrete-convex-analysissubmodular-functions
For a symmetric matrix , off-diagonal nonpositivity (2.9) is equivalent to submodularity (2.17) of .
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.65, Proposition 2.6.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_CombinatorialB_OffDiagNonpos import Definitions.Def_DiscreteConvex_CombinatorialB_QF import Definitions.Def_DiscreteConvex_CombinatorialB_Submodular
Formal statement
/-!
Murota, *Discrete Convex Analysis*, SIAM 2003, p.65, Proposition 2.6, in
`DiscreteConvex.CombinatorialB`.
-/
namespace DiscreteConvex.CombinatorialB
/-- **Proposition 2.6.** For a symmetric matrix `L`, off-diagonal nonpositivity (2.9) is
equivalent to submodularity (2.17) of the associated quadratic form `g(p) = (1/2)p⊤Lp`. -/
theorem prop_2_6_offdiag_iff_submodular {V : Type*} [Fintype V] [DecidableEq V]
(L : Matrix V V ℝ) (hsymm : L.IsSymm) :
OffDiagNonpos L ↔ Submodular (QF L) := by sorry
end DiscreteConvex.CombinatorialB
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.65, Proposition 2.6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.