The Hilbert basis of a
convex cone
In linear algebra, a ''cone''—sometimes called a linear cone for distinguishing it from other sorts of cones—is a subset of a vector space that is closed under scalar multiplication; that is, is a cone if x\in C implies sx\in C for every .
W ...
''C'' is a minimal set of integer
vector
Vector most often refers to:
*Euclidean vector, a quantity with a magnitude and a direction
*Vector (epidemiology), an agent that carries and transmits an infectious pathogen into another living organism
Vector may also refer to:
Mathematic ...
s such that every integer vector in ''C'' is a
conical combination Given a finite number of vectors x_1, x_2, \dots, x_n in a real vector space, a conical combination, conical sum, or weighted sum''Convex Analysis and Minimization Algorithms'' by Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal, 1993, pp. 101, 102 ...
of the vectors in the Hilbert basis with integer coefficients.
Definition
Given a
lattice and a convex polyhedral cone with generators
:
we consider the
monoid
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
Monoid ...
. By
Gordan's lemma Gordan's lemma is a lemma in convex geometry and algebraic geometry. It can be stated in several ways.
* Let A be a matrix of integers. Let M be the set of non-negative integer solutions of A \cdot x = 0. Then there exists a finite subset of vector ...
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 the 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
.
References
*
*
*
*
Linear programming
Discrete geometry
{{mathapplied-stub