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.

Definition

Given a lattice $L\subset\mathbb^d$ and a convex polyhedral cone with generators $a_1,\ldots,a_n\in\mathbb^d$

:$C=\\subset\mathbb^d,$

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

:$x=\lambda_1 x_1+\ldots+\lambda_m x_m, \quad\lambda_1,\ldots,\lambda_m\in\mathbb, \lambda_1,\ldots,\lambda_m\geq0.$

The cone ''C'' is called pointed if $x,-x\in C$ implies $x=0$. In this case there exists a unique minimal generating set of the monoid $C\cap L$—the Hilbert basis of ''C''. It is given by the set of irreducible lattice points: An element $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$ implies $y=0$ or $z=0$.

References

*
*
*
*

Linear programming
Discrete geometry
Eponyms in geometry

{{mathapplied-stub