Hilbert basis (linear programming)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.


Hilbert basis visualization

Given a lattice and a convex polyhedral cone with generators

we consider the monoid . By Gordan's lemma this monoid is finitely generated, i.e., there exists a finite set of lattice points such that every lattice point is an integer conical combination of these points:

The cone C is called pointed, if implies . In this case there exists a unique minimal generating set of the monoid - the Hilbert basis of C. It is given by set of irreducible lattice points: An element is called irreducible if it can not be written as the sum of two non-zero elements, i.e., implies or .