Hilbert basis (linear programming)

Last updated

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 Hilbert basis.gif
Hilbert basis visualization

Given a lattice and a convex polyhedral cone with generators

we consider the monoid . By Gordan's lemma, 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 .

Related Research Articles

<span class="mw-page-title-main">Basis (linear algebra)</span> Set of vectors used to define coordinates

In mathematics, a set B of vectors in a vector space V is called a basis if every element of V may be written in a unique way as a finite linear combination of elements of B. The coefficients of this linear combination are referred to as components or coordinates of the vector with respect to B. The elements of a basis are called basis vectors.

<span class="mw-page-title-main">Linear span</span> In linear algebra, generated subspace

In mathematics, the linear span (also called the linear hull or just span) of a set S of vectors (from a vector space), denoted span(S), is defined as the set of all linear combinations of the vectors in S. For example, two linearly independent vectors span a plane. The linear span can be characterized either as the intersection of all linear subspaces that contain S, or as the smallest subspace containing S. The linear span of a set of vectors is therefore a vector space itself. Spans can be generalized to matroids and modules.

In mathematics, a quadric or quadric surface (quadric hypersurface in higher dimensions), is a generalization of conic sections (ellipses, parabolas, and hyperbolas). It is a hypersurface (of dimension D) in a (D + 1)-dimensional space, and it is defined as the zero set of an irreducible polynomial of degree two in D + 1 variables; for example, D = 1 in the case of conic sections. When the defining polynomial is not absolutely irreducible, the zero set is generally not considered a quadric, although it is often called a degenerate quadric or a reducible quadric.

In the mathematical field of representation theory, a weight of an algebra A over a field F is an algebra homomorphism from A to F, or equivalently, a one-dimensional representation of A over F. It is the algebra analogue of a multiplicative character of a group. The importance of the concept, however, stems from its application to representations of Lie algebras and hence also to representations of algebraic and Lie groups. In this context, a weight of a representation is a generalization of the notion of an eigenvalue, and the corresponding eigenspace is called a weight space.

<span class="mw-page-title-main">Projective variety</span>

In algebraic geometry, a projective variety over an algebraically closed field k is a subset of some projective n-space over k that is the zero-locus of some finite family of homogeneous polynomials of n + 1 variables with coefficients in k, that generate a prime ideal, the defining ideal of the variety. Equivalently, an algebraic variety is projective if it can be embedded as a Zariski closed subvariety of .

<span class="mw-page-title-main">Modular group</span> Orientation-preserving mapping class group of the torus

In mathematics, the modular group is the projective special linear group of 2 × 2 matrices with integer coefficients and determinant 1. The matrices A and A are identified. The modular group acts on the upper-half of the complex plane by fractional linear transformations, and the name "modular group" comes from the relation to moduli spaces and not from modular arithmetic.

<span class="mw-page-title-main">Polynomial ring</span> Algebraic structure

In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates with coefficients in another ring, often a field.

In mathematics, complex multiplication (CM) is the theory of elliptic curves E that have an endomorphism ring larger than the integers. Put another way, it contains the theory of elliptic functions with extra symmetries, such as are visible when the period lattice is the Gaussian integer lattice or Eisenstein integer lattice.

In mathematics, a vertex operator algebra (VOA) is an algebraic structure that plays an important role in two-dimensional conformal field theory and string theory. In addition to physical applications, vertex operator algebras have proven useful in purely mathematical contexts such as monstrous moonshine and the geometric Langlands correspondence.

<span class="mw-page-title-main">Dual lattice</span>

In the theory of lattices, the dual lattice is a construction analogous to that of a dual vector space. In certain respects, the geometry of the dual lattice of a lattice is the reciprocal of the geometry of , a perspective which underlies many of its uses.

Verma modules, named after Daya-Nand Verma, are objects in the representation theory of Lie algebras, a branch of mathematics.

In mathematics, Schubert calculus is a branch of algebraic geometry introduced in the nineteenth century by Hermann Schubert, in order to solve various counting problems of projective geometry. It was a precursor of several more modern theories, for example characteristic classes, and in particular its algorithmic aspects are still of current interest. The phrase "Schubert calculus" is sometimes used to mean the enumerative geometry of linear subspaces, roughly equivalent to describing the cohomology ring of Grassmannians, and sometimes used to mean the more general enumerative geometry of nonlinear varieties. Even more generally, "Schubert calculus" is often understood to encompass the study of analogous questions in generalized cohomology theories.

<span class="mw-page-title-main">Convex cone</span> Mathematical set closed under positive linear combinations

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 positive scalar multiplication; that is, C is a cone if implies for every positive scalar s.

In mathematics, a Riesz space, lattice-ordered vector space or vector lattice is a partially ordered vector space where the order structure is a lattice.

<span class="mw-page-title-main">Ordered vector space</span> Vector space with a partial order

In mathematics, an ordered vector space or partially ordered vector space is a vector space equipped with a partial order that is compatible with the vector space operations.

In mathematics, specifically in combinatorial commutative algebra, a convex lattice polytope P is called normal if it has the following property: given any positive integer n, every lattice point of the dilation nP, obtained from P by scaling its vertices by the factor n and taking the convex hull of the resulting points, can be written as the sum of exactly n lattice points in P. This property plays an important role in the theory of toric varieties, where it corresponds to projective normality of the toric variety determined by P. Normal polytopes have popularity in algebraic combinatorics. These polytopes also represent the homogeneous case of the Hilbert bases of finite positive rational cones and the connection to algebraic geometry is that they define projectively normal embeddings of toric varieties.

In discrete mathematics, ideal lattices are a special class of lattices and a generalization of cyclic lattices. Ideal lattices naturally occur in many parts of number theory, but also in other areas. In particular, they have a significant place in cryptography. Micciancio defined a generalization of cyclic lattices as ideal lattices. They can be used in cryptosystems to decrease by a square root the number of parameters necessary to describe a lattice, making them more efficient. Ideal lattices are a new concept, but similar lattice classes have been used for a long time. For example, cyclic lattices, a special case of ideal lattices, are used in NTRUEncrypt and NTRUSign.

In abstract algebra, a branch of mathematics, an affine monoid is a commutative monoid that is finitely generated, and is isomorphic to a submonoid of a free abelian group . Affine monoids are closely connected to convex polyhedra, and their associated algebras are of much use in the algebraic study of these geometric objects.

In mathematics, and especially differential and algebraic geometry, K-stability is an algebro-geometric stability condition, for complex manifolds and complex algebraic varieties. The notion of K-stability was first introduced by Gang Tian and reformulated more algebraically later by Simon Donaldson. The definition was inspired by a comparison to geometric invariant theory (GIT) stability. In the special case of Fano varieties, K-stability precisely characterises the existence of Kähler–Einstein metrics. More generally, on any compact complex manifold, K-stability is conjectured to be equivalent to the existence of constant scalar curvature Kähler metrics.

<span class="mw-page-title-main">Representation theory of semisimple Lie algebras</span>

In mathematics, the representation theory of semisimple Lie algebras is one of the crowning achievements of the theory of Lie groups and Lie algebras. The theory was worked out mainly by E. Cartan and H. Weyl and because of that, the theory is also known as the Cartan–Weyl theory. The theory gives the structural description and classification of a finite-dimensional representation of a semisimple Lie algebra ; in particular, it gives a way to parametrize irreducible finite-dimensional representations of a semisimple Lie algebra, the result known as the theorem of the highest weight.

References