Theorem 2.7 -- off-diagonal nonpositivity + diagonal dominance iff translation submodularity
ProvedDiscreteConvex.CombinatorialB.theorem_2_7_offdiag_diagdom_iff_translation_submodulardiscrete-convex-analysissubmodular-functions
For a symmetric matrix : off-diagonal nonpositivity (2.9) together with diagonal dominance (2.10) holds if and only if has translation submodularity (SBF-natural[R]).
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, pp.65-66, Theorem 2.7.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_CombinatorialB_OffDiagNonpos import Definitions.Def_DiscreteConvex_CombinatorialB_DiagDominance import Definitions.Def_DiscreteConvex_CombinatorialB_QF import Definitions.Def_DiscreteConvex_CombinatorialB_TranslationSubmodular
Formal statement
/-!
Murota, *Discrete Convex Analysis*, SIAM 2003, pp.65-66, Theorem 2.7, in
`DiscreteConvex.CombinatorialB`.
-/
namespace DiscreteConvex.CombinatorialB
/-- **Theorem 2.7.** For a symmetric matrix `L`, off-diagonal nonpositivity (2.9) together with
diagonal dominance (2.10) is equivalent to translation submodularity (SBF-natural[R]) of
`g(p) = (1/2)p⊤Lp`. -/
theorem theorem_2_7_offdiag_diagdom_iff_translation_submodular {V : Type*} [Fintype V]
[DecidableEq V] (L : Matrix V V ℝ) (hsymm : L.IsSymm) :
(OffDiagNonpos L ∧ DiagDominance L) ↔ TranslationSubmodular (QF L) := by sorry
end DiscreteConvex.CombinatorialB
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, pp.65-66, Theorem 2.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.