Hilbert basis (linear programming)

In linear programming, a Hilbert basis for a convex cone C is an integer cone basis: 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.

Definition

A set $A=\{a_1,\ldots,a_n\}$ of integer vectors is a Hilbert basis of its convex cone

$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}\}$

if every integer vector from C belongs to the integer convex cone of A:

$\{ \alpha_1 a_1 + \ldots + \alpha_n a_n \mid \alpha_1,\ldots,\alpha_n \geq 0, \alpha_1,\ldots,\alpha_n \in\mathbb{Z}\},$

and no vector from A belongs to the integer convex cone of the others.