Cramer's-rule coefficient bound for a supporting inequality
ProvedKarpPapadimitriou.SmallFacial.cramer_boundinteger-programminglinear-algebrap2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polyhedral-combinatorics
Let and . Suppose an integral matrix has linearly independent rows, each entry of absolute value at most , and an integral vector has entries of absolute value at most . There is a nonzero integral normal satisfying . Its coordinates and the intercept obey
This is the coefficient estimate used at the end of the proof of Lemma 1.
Formalization Note The paper's rows can have magnitude , so that is the bound on entries of . The positive hypotheses on and cover the degenerate determinant case; the bound remains the paper's .
Preamble
import Mathlib import Definitions.Def_KarpPapadimitriou_SmallFacial_COP
Formal statement
namespace KarpPapadimitriou.SmallFacial
/-- pp. 6–7, proof of Lemma 1: bounded integral normals from `n-1` independent rows. -/
theorem cramer_bound (n x : ℕ) (hn : 1 ≤ n) (hx : 1 ≤ x)
(W : Matrix (Fin (n - 1)) (Fin n) ℤ) (v₀ : Fin n → ℤ)
(hW : LinearIndependent ℚ (fun i : Fin (n - 1) => fun j : Fin n => (W i j : ℚ)))
(hWb : ∀ i j, (W i j).natAbs ≤ 2 * x)
(hv : ∀ j, (v₀ j).natAbs ≤ x) :
∃ f : Fin n → ℤ,
f ≠ 0 ∧
(∀ i, (∑ j, W i j * f j) = 0) ∧
(∀ j, (f j).natAbs ≤ (2 * n * x) ^ n) ∧
(∑ j, f j * v₀ j).natAbs ≤ (2 * n * x) ^ n := by sorry
end KarpPapadimitriou.SmallFacial
Source
Karp & Papadimitriou, MIT/LCS/TM-154 (Feb. 1980), pp. 6–7, proof of Lemma 1, Cramer's-rule normal and final coefficient bound; https://dspace.mit.edu/server/api/core/bitstreams/eb122126-c312-4445-a8d2-153e3e7d285f/content
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.