The Hilbert basis of a convex cone C is a minimal set of integer vectors such that every integer vector in C is a conical combination of the vectors in the Hilbert basis with integer coefficients.
Given a lattice [math]\displaystyle{ L\subset\mathbb{Z}^d }[/math] and a convex polyhedral cone with generators [math]\displaystyle{ a_1,\ldots,a_n\in\mathbb{Z}^d }[/math]
we consider the monoid [math]\displaystyle{ C\cap L }[/math]. By Gordan's lemma, this monoid is finitely generated, i.e., there exists a finite set of lattice points [math]\displaystyle{ \{x_1,\ldots,x_m\}\subset C\cap L }[/math] such that every lattice point [math]\displaystyle{ x\in C\cap L }[/math] is an integer conical combination of these points:
The cone C is called pointed if [math]\displaystyle{ x,-x\in C }[/math] implies [math]\displaystyle{ x=0 }[/math]. In this case there exists a unique minimal generating set of the monoid [math]\displaystyle{ C\cap L }[/math]—the Hilbert basis of C. It is given by the set of irreducible lattice points: An element [math]\displaystyle{ x\in C\cap L }[/math] is called irreducible if it can not be written as the sum of two non-zero elements, i.e., [math]\displaystyle{ x=y+z }[/math] implies [math]\displaystyle{ y=0 }[/math] or [math]\displaystyle{ z=0 }[/math].
Original source: https://en.wikipedia.org/wiki/Hilbert basis (linear programming).
Read more |