Content deleted Content added
m Open access bot: hdl updated in citation with #oabot. |
Link suggestions feature: 2 links added. |
||
| (3 intermediate revisions by 2 users not shown) | |||
Line 1:
The '''Hilbert basis''' of a [[convex cone]] ''C'' is a minimal set of integer [[vector (mathematics)|vector]]s in ''C'' such that every [[integer]] vector in ''C'' is a [[conical combination]] of the vectors in the Hilbert basis with integer coefficients.
== Definition ==
[[File:Hilbert basis.gif|thumb|Hilbert basis visualization. Two rays in the plane define an infinite cone of all the points lying between them. The unique Hilbert basis points of the cone are circled in yellow. Every integer point in the cone can be written as a sum of these basis elements. As you change the cone by moving one of the rays, the Hilbert basis also changes.]]
Given a [[Lattice (group)|lattice]] <math>L\subset\mathbb{Z}^d</math> and a convex polyhedral cone with generators <math>a_1,\ldots,a_n\in\mathbb{Z}^d</math>
:<math>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,</math>
we consider the [[monoid]] <math>C\cap L</math>. By [[Gordan's lemma]], this monoid is finitely generated, i.e., there exists a [[finite set]] of lattice points <math>\{x_1,\ldots,x_m\}\subset C\cap L</math> such that every lattice point <math>x\in C\cap L</math> is an integer conical combination of these points:
:<math> x=\lambda_1 x_1+\ldots+\lambda_m x_m, \quad\lambda_1,\ldots,\lambda_m\in\mathbb{Z}, \lambda_1,\ldots,\lambda_m\geq0.</math>
Line 22:
[[Category:Linear programming]]
[[Category:Discrete geometry]]
[[Category:Eponyms in geometry]]
| |||