Hilbert basis (linear programming)

The Hilbert basis of a convex cone C is a minimal set of integer vectors in C such that every integer vector in C is a conical combination of the vectors in the Hilbert basis with integer coefficients.

Given a lattice L ⊂ Z d {\displaystyle L\subset \mathbb {Z} ^{d}} and a convex polyhedral cone with generators a 1 , … , a n ∈ Z d {\displaystyle a_{1},\ldots ,a_{n}\in \mathbb {Z} ^{d}}

C = { λ 1 a 1 + … + λ n a n ∣ λ 1 , … , λ n ≥ 0 , λ 1 , … , λ n ∈ R } ⊂ R d , {\displaystyle C=\{\lambda _{1}a_{1}+\ldots +\lambda _{n}a_{n}\mid \lambda _{1},\ldots ,\lambda _{n}\geq 0,\lambda _{1},\ldots ,\lambda _{n}\in \mathbb {R} \}\subset \mathbb {R} ^{d},}

we consider the monoid C ∩ L {\displaystyle C\cap L} . By Gordan's lemma, this monoid is finitely generated, i.e., there exists a finite set of lattice points { x 1 , … , x m } ⊂ C ∩ L {\displaystyle \{x_{1},\ldots ,x_{m}\}\subset C\cap L} such that every lattice point x ∈ C ∩ L {\displaystyle x\in C\cap L} is an integer conical combination of these points:

x = λ 1 x 1 + … + λ m x m , λ 1 , … , λ m ∈ Z , λ 1 , … , λ m ≥ 0. {\displaystyle x=\lambda _{1}x_{1}+\ldots +\lambda _{m}x_{m},\quad \lambda _{1},\ldots ,\lambda _{m}\in \mathbb {Z} ,\lambda _{1},\ldots ,\lambda _{m}\geq 0.}

The cone C is called pointed if x , − x ∈ C {\displaystyle x,-x\in C} implies x = 0 {\displaystyle x=0} . In this case there exists a unique minimal generating set of the monoid C ∩ L {\displaystyle C\cap L} —the Hilbert basis of C. It is given by the set of irreducible lattice points: An element x ∈ C ∩ L {\displaystyle x\in C\cap L} is called irreducible if it can not be written as the sum of two non-zero elements, i.e., x = y + z {\displaystyle x=y+z} implies y = 0 {\displaystyle y=0} or z = 0 {\displaystyle z=0} .

• Bruns, Winfried; Gubeladze, Joseph; Henk, Martin; Martin, Alexander; Weismantel, Robert (1999), "A counterexample to an integer analogue of Carathéodory's theorem", Journal für die reine und angewandte Mathematik, 1999 (510): 179–185, doi:10.1515/crll.1999.045
• Cook, William John; Fonlupt, Jean; Schrijver, Alexander (1986), "An integer analogue of Carathéodory's theorem", Journal of Combinatorial Theory, Series B, 40 (1): 63–70, doi:10.1016/0095-8956(86)90064-X
• Eisenbrand, Friedrich; Shmonin, Gennady (2006), "Carathéodory bounds for integer cones", Operations Research Letters, 34 (5): 564–568, doi:10.1016/j.orl.2005.09.008
• D. V. Pasechnik (2001). "On computing the Hilbert bases via the Elliott—MacMahon algorithm". Theoretical Computer Science. 263 (1–2): 37–46. doi:10.1016/S0304-3975(00)00229-2. hdl:10220/8240.