# Hilbert basis (linear programming)

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.

## Definition

Hilbert basis visualization

Given a lattice ${\displaystyle L\subset \mathbb {Z} ^{d}}$ and a convex polyhedral cone with generators ${\displaystyle a_{1},\ldots ,a_{n}\in \mathbb {Z} ^{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 ${\displaystyle C\cap L}$. By Gordan's lemma this monoid is finitely generated, i.e., there exists a finite set of lattice points ${\displaystyle \{x_{1},\ldots ,x_{m}\}\subset C\cap L}$ such that every lattice point ${\displaystyle x\in C\cap L}$ is an integer conical combination of these points:

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