Convex rational polyhedral cones#

This module was designed as a part of framework for toric varieties (variety, fano_variety). While the emphasis is on strictly convex cones, non-strictly convex cones are supported as well. Work with distinct lattices (in the sense of discrete subgroups spanning vector spaces) is supported. The default lattice is ToricLattice \(N\) of the appropriate dimension. The only case when you must specify lattice explicitly is creation of a 0-dimensional cone, where dimension of the ambient space cannot be guessed.

AUTHORS:

  • Andrey Novoseltsev (2010-05-13): initial version.

  • Andrey Novoseltsev (2010-06-17): substantial improvement during review by Volker Braun.

  • Volker Braun (2010-06-21): various spanned/quotient/dual lattice computations added.

  • Volker Braun (2010-12-28): Hilbert basis for cones.

  • Andrey Novoseltsev (2012-02-23): switch to PointCollection container.

EXAMPLES:

Use Cone() to construct cones:

sage: octant = Cone([(1,0,0), (0,1,0), (0,0,1)])
sage: halfspace = Cone([(1,0,0), (0,1,0), (-1,-1,0), (0,0,1)])
sage: positive_xy = Cone([(1,0,0), (0,1,0)])
sage: four_rays = Cone([(1,1,1), (1,-1,1), (-1,-1,1), (-1,1,1)])

>>> from sage.all import *
>>> octant = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(1))])
>>> halfspace = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (-Integer(1),-Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(1))])
>>> positive_xy = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0))])
>>> four_rays = Cone([(Integer(1),Integer(1),Integer(1)), (Integer(1),-Integer(1),Integer(1)), (-Integer(1),-Integer(1),Integer(1)), (-Integer(1),Integer(1),Integer(1))])

For all of the cones above we have provided primitive generating rays, but in fact this is not necessary - a cone can be constructed from any collection of rays (from the same space, of course). If there are non-primitive (or even non-integral) rays, they will be replaced with primitive ones. If there are extra rays, they will be discarded. Of course, this means that Cone() has to do some work before actually constructing the cone and sometimes it is not desirable, if you know for sure that your input is already “good”. In this case you can use options check=False to force Cone() to use exactly the directions that you have specified and normalize=False to force it to use exactly the rays that you have specified. However, it is better not to use these possibilities without necessity, since cones are assumed to be represented by a minimal set of primitive generating rays. See Cone() for further documentation on construction.

Once you have a cone, you can perform numerous operations on it. The most important ones are, probably, ray accessing methods:

sage: rays = halfspace.rays()
sage: rays
N( 0,  0, 1),
N( 0,  1, 0),
N( 0, -1, 0),
N( 1,  0, 0),
N(-1,  0, 0)
in 3-d lattice N
sage: rays.set()
frozenset({N(-1, 0, 0), N(0, -1, 0), N(0, 0, 1), N(0, 1, 0), N(1, 0, 0)})
sage: rays.matrix()
[ 0  0  1]
[ 0  1  0]
[ 0 -1  0]
[ 1  0  0]
[-1  0  0]
sage: rays.column_matrix()
[ 0  0  0  1 -1]
[ 0  1 -1  0  0]
[ 1  0  0  0  0]
sage: rays(3)
N(1, 0, 0)
in 3-d lattice N
sage: rays[3]
N(1, 0, 0)
sage: halfspace.ray(3)
N(1, 0, 0)

>>> from sage.all import *
>>> rays = halfspace.rays()
>>> rays
N( 0,  0, 1),
N( 0,  1, 0),
N( 0, -1, 0),
N( 1,  0, 0),
N(-1,  0, 0)
in 3-d lattice N
>>> rays.set()
frozenset({N(-1, 0, 0), N(0, -1, 0), N(0, 0, 1), N(0, 1, 0), N(1, 0, 0)})
>>> rays.matrix()
[ 0  0  1]
[ 0  1  0]
[ 0 -1  0]
[ 1  0  0]
[-1  0  0]
>>> rays.column_matrix()
[ 0  0  0  1 -1]
[ 0  1 -1  0  0]
[ 1  0  0  0  0]
>>> rays(Integer(3))
N(1, 0, 0)
in 3-d lattice N
>>> rays[Integer(3)]
N(1, 0, 0)
>>> halfspace.ray(Integer(3))
N(1, 0, 0)

The method rays() returns a PointCollection with the \(i\)-th element being the primitive integral generator of the \(i\)-th ray. It is possible to convert this collection to a matrix with either rows or columns corresponding to these generators. You may also change the default output_format() of all point collections to be such a matrix.

If you want to do something with each ray of a cone, you can write

sage: for ray in positive_xy: print(ray)
N(1, 0, 0)
N(0, 1, 0)

>>> from sage.all import *
>>> for ray in positive_xy: print(ray)
N(1, 0, 0)
N(0, 1, 0)

There are two dimensions associated to each cone - the dimension of the subspace spanned by the cone and the dimension of the space where it lives:

sage: positive_xy.dim()
2
sage: positive_xy.lattice_dim()
3

>>> from sage.all import *
>>> positive_xy.dim()
2
>>> positive_xy.lattice_dim()
3

You also may be interested in this dimension:

sage: dim(positive_xy.linear_subspace())
0
sage: dim(halfspace.linear_subspace())
2

>>> from sage.all import *
>>> dim(positive_xy.linear_subspace())
0
>>> dim(halfspace.linear_subspace())
2

Or, perhaps, all you care about is whether it is zero or not:

sage: positive_xy.is_strictly_convex()
True
sage: halfspace.is_strictly_convex()
False

>>> from sage.all import *
>>> positive_xy.is_strictly_convex()
True
>>> halfspace.is_strictly_convex()
False

You can also perform these checks:

sage: positive_xy.is_simplicial()
True
sage: four_rays.is_simplicial()
False
sage: positive_xy.is_smooth()
True

>>> from sage.all import *
>>> positive_xy.is_simplicial()
True
>>> four_rays.is_simplicial()
False
>>> positive_xy.is_smooth()
True

You can work with subcones that form faces of other cones:

sage: # needs sage.graphs
sage: face = four_rays.faces(dim=2)[0]
sage: face
2-d face of 3-d cone in 3-d lattice N
sage: face.rays()
N(-1, -1, 1),
N(-1,  1, 1)
in 3-d lattice N
sage: face.ambient_ray_indices()
(2, 3)
sage: four_rays.rays(face.ambient_ray_indices())
N(-1, -1, 1),
N(-1,  1, 1)
in 3-d lattice N

>>> from sage.all import *
>>> # needs sage.graphs
>>> face = four_rays.faces(dim=Integer(2))[Integer(0)]
>>> face
2-d face of 3-d cone in 3-d lattice N
>>> face.rays()
N(-1, -1, 1),
N(-1,  1, 1)
in 3-d lattice N
>>> face.ambient_ray_indices()
(2, 3)
>>> four_rays.rays(face.ambient_ray_indices())
N(-1, -1, 1),
N(-1,  1, 1)
in 3-d lattice N

If you need to know inclusion relations between faces, you can use

sage: # needs sage.graphs
sage: L = four_rays.face_lattice()
sage: [len(s) for s in L.level_sets()]
[1, 4, 4, 1]
sage: face = L.level_sets()[2][0]
sage: face.rays()
N(1,  1, 1),
N(1, -1, 1)
in 3-d lattice N
sage: L.hasse_diagram().neighbors_in(face)
[1-d face of 3-d cone in 3-d lattice N,
 1-d face of 3-d cone in 3-d lattice N]

>>> from sage.all import *
>>> # needs sage.graphs
>>> L = four_rays.face_lattice()
>>> [len(s) for s in L.level_sets()]
[1, 4, 4, 1]
>>> face = L.level_sets()[Integer(2)][Integer(0)]
>>> face.rays()
N(1,  1, 1),
N(1, -1, 1)
in 3-d lattice N
>>> L.hasse_diagram().neighbors_in(face)
[1-d face of 3-d cone in 3-d lattice N,
 1-d face of 3-d cone in 3-d lattice N]

Warning

The order of faces in level sets of the face lattice may differ from the order of faces returned by faces(). While the first order is random, the latter one ensures that one-dimensional faces are listed in the same order as generating rays.

When all the functionality provided by cones is not enough, you may want to check if you can do necessary things using polyhedra corresponding to cones:

sage: four_rays.polyhedron()
A 3-dimensional polyhedron in ZZ^3 defined as
the convex hull of 1 vertex and 4 rays

>>> from sage.all import *
>>> four_rays.polyhedron()
A 3-dimensional polyhedron in ZZ^3 defined as
the convex hull of 1 vertex and 4 rays

And of course you are always welcome to suggest new features that should be added to cones!

REFERENCES:

sage.geometry.cone.Cone(rays, lattice=None, check=True, normalize=True)[source]#

Construct a (not necessarily strictly) convex rational polyhedral cone.

INPUT:

  • rays – a list of rays. Each ray should be given as a list or a vector convertible to the rational extension of the given lattice. May also be specified by a Polyhedron_base object;

  • lattice – ToricLattice, \(\ZZ^n\), or any other object that behaves like these. If not specified, an attempt will be made to determine an appropriate toric lattice automatically;

  • check – by default the input data will be checked for correctness (e.g. that all rays have the same number of components) and generating rays will be constructed from rays. If you know that the input is a minimal set of generators of a valid cone, you may significantly decrease construction time using check=False option;

  • normalize – you can further speed up construction using normalize=False option. In this case rays must be a list of immutable primitive rays in lattice. In general, you should not use this option, it is designed for code optimization and does not give as drastic improvement in speed as the previous one.

OUTPUT:

  • convex rational polyhedral cone determined by rays.

EXAMPLES:

Let’s define a cone corresponding to the first quadrant of the plane (note, you can even mix objects of different types to represent rays, as long as you let this function to perform all the checks and necessary conversions!):

sage: quadrant = Cone([(1,0), [0,1]])
sage: quadrant
2-d cone in 2-d lattice N
sage: quadrant.rays()
N(1, 0),
N(0, 1)
in 2-d lattice N

>>> from sage.all import *
>>> quadrant = Cone([(Integer(1),Integer(0)), [Integer(0),Integer(1)]])
>>> quadrant
2-d cone in 2-d lattice N
>>> quadrant.rays()
N(1, 0),
N(0, 1)
in 2-d lattice N

If you give more rays than necessary, the extra ones will be discarded:

sage: Cone([(1,0), (0,1), (1,1), (0,1)]).rays()
N(0, 1),
N(1, 0)
in 2-d lattice N

>>> from sage.all import *
>>> Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1)), (Integer(1),Integer(1)), (Integer(0),Integer(1))]).rays()
N(0, 1),
N(1, 0)
in 2-d lattice N

However, this work is not done with check=False option, so use it carefully!

sage: Cone([(1,0), (0,1), (1,1), (0,1)], check=False).rays()
N(1, 0),
N(0, 1),
N(1, 1),
N(0, 1)
in 2-d lattice N

>>> from sage.all import *
>>> Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1)), (Integer(1),Integer(1)), (Integer(0),Integer(1))], check=False).rays()
N(1, 0),
N(0, 1),
N(1, 1),
N(0, 1)
in 2-d lattice N

Even worse things can happen with normalize=False option:

sage: Cone([(1,0), (0,1)], check=False, normalize=False)
Traceback (most recent call last):
...
AttributeError: 'tuple' object has no attribute 'parent'...

>>> from sage.all import *
>>> Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1))], check=False, normalize=False)
Traceback (most recent call last):
...
AttributeError: 'tuple' object has no attribute 'parent'...

You can construct different “not” cones: not full-dimensional, not strictly convex, not containing any rays:

sage: one_dimensional_cone = Cone([(1,0)])
sage: one_dimensional_cone.dim()
1
sage: half_plane = Cone([(1,0), (0,1), (-1,0)])
sage: half_plane.rays()
N( 0, 1),
N( 1, 0),
N(-1, 0)
in 2-d lattice N
sage: half_plane.is_strictly_convex()
False
sage: origin = Cone([(0,0)])
sage: origin.rays()
Empty collection
in 2-d lattice N
sage: origin.dim()
0
sage: origin.lattice_dim()
2

>>> from sage.all import *
>>> one_dimensional_cone = Cone([(Integer(1),Integer(0))])
>>> one_dimensional_cone.dim()
1
>>> half_plane = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1)), (-Integer(1),Integer(0))])
>>> half_plane.rays()
N( 0, 1),
N( 1, 0),
N(-1, 0)
in 2-d lattice N
>>> half_plane.is_strictly_convex()
False
>>> origin = Cone([(Integer(0),Integer(0))])
>>> origin.rays()
Empty collection
in 2-d lattice N
>>> origin.dim()
0
>>> origin.lattice_dim()
2

You may construct the cone above without giving any rays, but in this case you must provide lattice explicitly:

sage: origin = Cone([])
Traceback (most recent call last):
...
ValueError: lattice must be given explicitly if there are no rays!
sage: origin = Cone([], lattice=ToricLattice(2))
sage: origin.dim()
0
sage: origin.lattice_dim()
2
sage: origin.lattice()
2-d lattice N

>>> from sage.all import *
>>> origin = Cone([])
Traceback (most recent call last):
...
ValueError: lattice must be given explicitly if there are no rays!
>>> origin = Cone([], lattice=ToricLattice(Integer(2)))
>>> origin.dim()
0
>>> origin.lattice_dim()
2
>>> origin.lattice()
2-d lattice N

However, the trivial cone in n dimensions has a predefined constructor for you to use:

sage: origin = cones.trivial(2)
sage: origin.rays()
Empty collection
in 2-d lattice N

>>> from sage.all import *
>>> origin = cones.trivial(Integer(2))
>>> origin.rays()
Empty collection
in 2-d lattice N

Of course, you can also provide lattice in other cases:

sage: L = ToricLattice(3, "L")
sage: c1 = Cone([(1,0,0),(1,1,1)], lattice=L)
sage: c1.rays()
L(1, 0, 0),
L(1, 1, 1)
in 3-d lattice L

>>> from sage.all import *
>>> L = ToricLattice(Integer(3), "L")
>>> c1 = Cone([(Integer(1),Integer(0),Integer(0)),(Integer(1),Integer(1),Integer(1))], lattice=L)
>>> c1.rays()
L(1, 0, 0),
L(1, 1, 1)
in 3-d lattice L

Or you can construct cones from rays of a particular lattice:

sage: ray1 = L(1,0,0)
sage: ray2 = L(1,1,1)
sage: c2 = Cone([ray1, ray2])
sage: c2.rays()
L(1, 0, 0),
L(1, 1, 1)
in 3-d lattice L
sage: c1 == c2
True

>>> from sage.all import *
>>> ray1 = L(Integer(1),Integer(0),Integer(0))
>>> ray2 = L(Integer(1),Integer(1),Integer(1))
>>> c2 = Cone([ray1, ray2])
>>> c2.rays()
L(1, 0, 0),
L(1, 1, 1)
in 3-d lattice L
>>> c1 == c2
True

When the cone in question is not strictly convex, the standard form for the “generating rays” of the linear subspace is “basis vectors and their negatives”, as in the following example:

sage: plane = Cone([(1,0), (0,1), (-1,-1)])
sage: plane.rays()
N( 0,  1),
N( 0, -1),
N( 1,  0),
N(-1,  0)
in 2-d lattice N

>>> from sage.all import *
>>> plane = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1)), (-Integer(1),-Integer(1))])
>>> plane.rays()
N( 0,  1),
N( 0, -1),
N( 1,  0),
N(-1,  0)
in 2-d lattice N

The cone can also be specified by a Polyhedron_base:

sage: p = plane.polyhedron()
sage: Cone(p)
2-d cone in 2-d lattice N
sage: Cone(p) == plane
True

>>> from sage.all import *
>>> p = plane.polyhedron()
>>> Cone(p)
2-d cone in 2-d lattice N
>>> Cone(p) == plane
True
class sage.geometry.cone.ConvexRationalPolyhedralCone(rays=None, lattice=None, ambient=None, ambient_ray_indices=None, PPL=None)[source]#

Bases: IntegralRayCollection, Container, ConvexSet_closed, ConvexRationalPolyhedralCone

Create a convex rational polyhedral cone.

Warning

This class does not perform any checks of correctness of input nor does it convert input into the standard representation. Use Cone() to construct cones.

Cones are immutable, but they cache most of the returned values.

INPUT:

The input can be either:

  • rays – list of immutable primitive vectors in lattice;

  • lattice – ToricLattice, \(\ZZ^n\), or any other object that behaves like these. If None, it will be determined as parent() of the first ray. Of course, this cannot be done if there are no rays, so in this case you must give an appropriate lattice directly.

or (these parameters must be given as keywords):

  • ambient – ambient structure of this cone, a bigger cone or a fan, this cone must be a face of ambient;

  • ambient_ray_indices – increasing list or tuple of integers, indices of rays of ambient generating this cone.

In both cases, the following keyword parameter may be specified in addition:

  • PPL – either None (default) or a C_Polyhedron representing the cone. This serves only to cache the polyhedral data if you know it already. The constructor does not make a copy so the PPL object should not be modified afterwards.

OUTPUT:

  • convex rational polyhedral cone.

Note

Every cone has its ambient structure. If it was not specified, it is this cone itself.

Hilbert_basis()[source]#

Return the Hilbert basis of the cone.

Given a strictly convex cone \(C\subset \RR^d\), the Hilbert basis of \(C\) is the set of all irreducible elements in the semigroup \(C\cap \ZZ^d\). It is the unique minimal generating set over \(\ZZ\) for the integral points \(C\cap \ZZ^d\).

If the cone \(C\) is not strictly convex, this method finds the (unique) minimal set of lattice points that need to be added to the defining rays of the cone to generate the whole semigroup \(C\cap \ZZ^d\). But because the rays of the cone are not unique nor necessarily minimal in this case, neither is the returned generating set (consisting of the rays plus additional generators).

See also semigroup_generators() if you are not interested in a minimal set of generators.

OUTPUT:

EXAMPLES:

The following command ensures that the output ordering in the examples below is independent of TOPCOM, you don’t have to use it:

sage: PointConfiguration.set_engine('internal')

>>> from sage.all import *
>>> PointConfiguration.set_engine('internal')

We start with a simple case of a non-smooth 2-dimensional cone:

sage: Cone([(1,0), (1,2)]).Hilbert_basis()
N(1, 0),
N(1, 2),
N(1, 1)
in 2-d lattice N

>>> from sage.all import *
>>> Cone([(Integer(1),Integer(0)), (Integer(1),Integer(2))]).Hilbert_basis()
N(1, 0),
N(1, 2),
N(1, 1)
in 2-d lattice N

Two more complicated example from GAP/toric:

sage: Cone([[1,0], [3,4]]).dual().Hilbert_basis()
M(0,  1),
M(4, -3),
M(1,  0),
M(2, -1),
M(3, -2)
in 2-d lattice M
sage: cone = Cone([[1,2,3,4], [0,1,0,7], [3,1,0,2], [0,0,1,0]]).dual()
sage: cone.Hilbert_basis()           # long time
M(10,  -7,  0,  1),
M(-5,  21,  0, -3),
M( 0,  -2,  0,  1),
M(15, -63, 25,  9),
M( 2,  -3,  0,  1),
M( 1,  -4,  1,  1),
M( 4,  -4,  0,  1),
M(-1,   3,  0,  0),
M( 1,  -5,  2,  1),
M( 3,  -5,  1,  1),
M( 6,  -5,  0,  1),
M( 3, -13,  5,  2),
M( 2,  -6,  2,  1),
M( 5,  -6,  1,  1),
M( 8,  -6,  0,  1),
M( 0,   1,  0,  0),
M(-2,   8,  0, -1),
M(10, -42, 17,  6),
M( 7, -28, 11,  4),
M( 5, -21,  9,  3),
M( 6, -21,  8,  3),
M( 5, -14,  5,  2),
M( 2,  -7,  3,  1),
M( 4,  -7,  2,  1),
M( 7,  -7,  1,  1),
M( 0,   0,  1,  0),
M( 1,   0,  0,  0),
M(-1,   7,  0, -1),
M(-3,  14,  0, -2)
in 4-d lattice M

>>> from sage.all import *
>>> Cone([[Integer(1),Integer(0)], [Integer(3),Integer(4)]]).dual().Hilbert_basis()
M(0,  1),
M(4, -3),
M(1,  0),
M(2, -1),
M(3, -2)
in 2-d lattice M
>>> cone = Cone([[Integer(1),Integer(2),Integer(3),Integer(4)], [Integer(0),Integer(1),Integer(0),Integer(7)], [Integer(3),Integer(1),Integer(0),Integer(2)], [Integer(0),Integer(0),Integer(1),Integer(0)]]).dual()
>>> cone.Hilbert_basis()           # long time
M(10,  -7,  0,  1),
M(-5,  21,  0, -3),
M( 0,  -2,  0,  1),
M(15, -63, 25,  9),
M( 2,  -3,  0,  1),
M( 1,  -4,  1,  1),
M( 4,  -4,  0,  1),
M(-1,   3,  0,  0),
M( 1,  -5,  2,  1),
M( 3,  -5,  1,  1),
M( 6,  -5,  0,  1),
M( 3, -13,  5,  2),
M( 2,  -6,  2,  1),
M( 5,  -6,  1,  1),
M( 8,  -6,  0,  1),
M( 0,   1,  0,  0),
M(-2,   8,  0, -1),
M(10, -42, 17,  6),
M( 7, -28, 11,  4),
M( 5, -21,  9,  3),
M( 6, -21,  8,  3),
M( 5, -14,  5,  2),
M( 2,  -7,  3,  1),
M( 4,  -7,  2,  1),
M( 7,  -7,  1,  1),
M( 0,   0,  1,  0),
M( 1,   0,  0,  0),
M(-1,   7,  0, -1),
M(-3,  14,  0, -2)
in 4-d lattice M

Not a strictly convex cone:

sage: wedge = Cone([(1,0,0), (1,2,0), (0,0,1), (0,0,-1)])
sage: sorted(wedge.semigroup_generators())
[N(0, 0, -1), N(0, 0, 1), N(1, 0, 0), N(1, 1, 0), N(1, 2, 0)]
sage: wedge.Hilbert_basis()
N(1, 2,  0),
N(1, 0,  0),
N(0, 0,  1),
N(0, 0, -1),
N(1, 1,  0)
in 3-d lattice N

>>> from sage.all import *
>>> wedge = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(1),Integer(2),Integer(0)), (Integer(0),Integer(0),Integer(1)), (Integer(0),Integer(0),-Integer(1))])
>>> sorted(wedge.semigroup_generators())
[N(0, 0, -1), N(0, 0, 1), N(1, 0, 0), N(1, 1, 0), N(1, 2, 0)]
>>> wedge.Hilbert_basis()
N(1, 2,  0),
N(1, 0,  0),
N(0, 0,  1),
N(0, 0, -1),
N(1, 1,  0)
in 3-d lattice N

Not full-dimensional cones are ok, too (see Issue #11312):

sage: Cone([(1,1,0), (-1,1,0)]).Hilbert_basis()
N( 1, 1, 0),
N(-1, 1, 0),
N( 0, 1, 0)
in 3-d lattice N

>>> from sage.all import *
>>> Cone([(Integer(1),Integer(1),Integer(0)), (-Integer(1),Integer(1),Integer(0))]).Hilbert_basis()
N( 1, 1, 0),
N(-1, 1, 0),
N( 0, 1, 0)
in 3-d lattice N

ALGORITHM:

The primal Normaliz algorithm, see [Normaliz].

Hilbert_coefficients(point, solver, verbose=None, integrality_tolerance=0)[source]#

Return the expansion coefficients of point with respect to Hilbert_basis().

INPUT:

  • point – a lattice() point in the cone, or something that can be converted to a point. For example, a list or tuple of integers.

  • solver – (default: None) Specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

  • verbose – integer (default: 0). Sets the level of verbosity of the LP solver. Set to 0 by default, which means quiet.

  • integrality_tolerance – parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

OUTPUT:

A \(\ZZ\)-vector of length len(self.Hilbert_basis()) with nonnegative components.

Note

Since the Hilbert basis elements are not necessarily linearly independent, the expansion coefficients are not unique. However, this method will always return the same expansion coefficients when invoked with the same argument.

EXAMPLES:

sage: cone = Cone([(1,0), (0,1)])
sage: cone.rays()
N(1, 0),
N(0, 1)
in 2-d lattice N
sage: cone.Hilbert_coefficients([3,2])
(3, 2)

>>> from sage.all import *
>>> cone = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> cone.rays()
N(1, 0),
N(0, 1)
in 2-d lattice N
>>> cone.Hilbert_coefficients([Integer(3),Integer(2)])
(3, 2)

A more complicated example:

sage: N = ToricLattice(2)
sage: cone = Cone([N(1,0), N(1,2)])
sage: cone.Hilbert_basis()
N(1, 0),
N(1, 2),
N(1, 1)
in 2-d lattice N
sage: cone.Hilbert_coefficients(N(1,1))
(0, 0, 1)

>>> from sage.all import *
>>> N = ToricLattice(Integer(2))
>>> cone = Cone([N(Integer(1),Integer(0)), N(Integer(1),Integer(2))])
>>> cone.Hilbert_basis()
N(1, 0),
N(1, 2),
N(1, 1)
in 2-d lattice N
>>> cone.Hilbert_coefficients(N(Integer(1),Integer(1)))
(0, 0, 1)

The cone need not be strictly convex:

sage: N = ToricLattice(3)
sage: cone = Cone([N(1,0,0), N(1,2,0), N(0,0,1), N(0,0,-1)])
sage: cone.Hilbert_basis()
N(1, 2,  0),
N(1, 0,  0),
N(0, 0,  1),
N(0, 0, -1),
N(1, 1,  0)
in 3-d lattice N
sage: cone.Hilbert_coefficients(N(1,1,3))
(0, 0, 3, 0, 1)

>>> from sage.all import *
>>> N = ToricLattice(Integer(3))
>>> cone = Cone([N(Integer(1),Integer(0),Integer(0)), N(Integer(1),Integer(2),Integer(0)), N(Integer(0),Integer(0),Integer(1)), N(Integer(0),Integer(0),-Integer(1))])
>>> cone.Hilbert_basis()
N(1, 2,  0),
N(1, 0,  0),
N(0, 0,  1),
N(0, 0, -1),
N(1, 1,  0)
in 3-d lattice N
>>> cone.Hilbert_coefficients(N(Integer(1),Integer(1),Integer(3)))
(0, 0, 3, 0, 1)
Z_operators_gens()[source]#

Compute minimal generators of the Z-operators on this cone.

The Z-operators on a cone generalize the Z-matrices over the nonnegative orthant. They are simply negations of the cross_positive_operators_gens().

OUTPUT:

A list of \(n\)-by-\(n\) matrices where \(n\) is the ambient dimension of this cone. Each matrix \(L\) in the list has the property that \(s(L(x)) \le 0\) whenever \((x,s)\) is an element of this cone’s discrete_complementarity_set().

The returned matrices generate the cone of Z-operators on this cone; that is,

  • Any nonnegative linear combination of the returned matrices is a Z-operator on this cone.

  • Every Z-operator on this cone is some nonnegative linear combination of the returned matrices.

See also

cross_positive_operators_gens(), lyapunov_like_basis(), positive_operators_gens()

REFERENCES:

adjacent()[source]#

Return faces adjacent to self in the ambient face lattice.

Two distinct faces \(F_1\) and \(F_2\) of the same face lattice are adjacent if all of the following conditions hold:

  • \(F_1\) and \(F_2\) have the same dimension \(d\);

  • \(F_1\) and \(F_2\) share a facet of dimension \(d-1\);

  • \(F_1\) and \(F_2\) are facets of some face of dimension \(d+1\), unless \(d\) is the dimension of the ambient structure.

OUTPUT:

EXAMPLES:

sage: # needs sage.graphs
sage: octant = Cone([(1,0,0), (0,1,0), (0,0,1)])
sage: octant.adjacent()
()
sage: one_face = octant.faces(1)[0]
sage: len(one_face.adjacent())
2
sage: one_face.adjacent()[1]
1-d face of 3-d cone in 3-d lattice N

>>> from sage.all import *
>>> # needs sage.graphs
>>> octant = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(1))])
>>> octant.adjacent()
()
>>> one_face = octant.faces(Integer(1))[Integer(0)]
>>> len(one_face.adjacent())
2
>>> one_face.adjacent()[Integer(1)]
1-d face of 3-d cone in 3-d lattice N

Things are a little bit subtle with fans, as we illustrate below.

First, we create a fan from two cones in the plane:

sage: fan = Fan(cones=[(0,1), (1,2)],
....:           rays=[(1,0), (0,1), (-1,0)])
sage: cone = fan.generating_cone(0)
sage: len(cone.adjacent())                                                  # needs sage.graphs
1

>>> from sage.all import *
>>> fan = Fan(cones=[(Integer(0),Integer(1)), (Integer(1),Integer(2))],
...           rays=[(Integer(1),Integer(0)), (Integer(0),Integer(1)), (-Integer(1),Integer(0))])
>>> cone = fan.generating_cone(Integer(0))
>>> len(cone.adjacent())                                                  # needs sage.graphs
1

The second generating cone is adjacent to this one. Now we create the same fan, but embedded into the 3-dimensional space:

sage: fan = Fan(cones=[(0,1), (1,2)],
....:           rays=[(1,0,0), (0,1,0), (-1,0,0)])
sage: cone = fan.generating_cone(0)
sage: len(cone.adjacent())                                                  # needs sage.graphs
1

>>> from sage.all import *
>>> fan = Fan(cones=[(Integer(0),Integer(1)), (Integer(1),Integer(2))],
...           rays=[(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (-Integer(1),Integer(0),Integer(0))])
>>> cone = fan.generating_cone(Integer(0))
>>> len(cone.adjacent())                                                  # needs sage.graphs
1

The result is as before, since we still have:

sage: fan.dim()
2

>>> from sage.all import *
>>> fan.dim()
2

Now we add another cone to make the fan 3-dimensional:

sage: fan = Fan(cones=[(0,1), (1,2), (3,)],
....:           rays=[(1,0,0), (0,1,0), (-1,0,0), (0,0,1)])
sage: cone = fan.generating_cone(0)
sage: len(cone.adjacent())                                                  # needs sage.graphs
0

>>> from sage.all import *
>>> fan = Fan(cones=[(Integer(0),Integer(1)), (Integer(1),Integer(2)), (Integer(3),)],
...           rays=[(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (-Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(0),Integer(1))])
>>> cone = fan.generating_cone(Integer(0))
>>> len(cone.adjacent())                                                  # needs sage.graphs
0

Since now cone has smaller dimension than fan, it and its adjacent cones must be facets of a bigger one, but since cone in this example is generating, it is not contained in any other.

ambient()[source]#

Return the ambient structure of self.

OUTPUT:

  • cone or fan containing self as a face.

EXAMPLES:

sage: cone = Cone([(1,2,3), (4,6,5), (9,8,7)])
sage: cone.ambient()
3-d cone in 3-d lattice N
sage: cone.ambient() is cone
True

sage: # needs sage.graphs
sage: face = cone.faces(1)[0]
sage: face
1-d face of 3-d cone in 3-d lattice N
sage: face.ambient()
3-d cone in 3-d lattice N
sage: face.ambient() is cone
True

>>> from sage.all import *
>>> cone = Cone([(Integer(1),Integer(2),Integer(3)), (Integer(4),Integer(6),Integer(5)), (Integer(9),Integer(8),Integer(7))])
>>> cone.ambient()
3-d cone in 3-d lattice N
>>> cone.ambient() is cone
True

>>> # needs sage.graphs
>>> face = cone.faces(Integer(1))[Integer(0)]
>>> face
1-d face of 3-d cone in 3-d lattice N
>>> face.ambient()
3-d cone in 3-d lattice N
>>> face.ambient() is cone
True
ambient_ray_indices()[source]#

Return indices of rays of the ambient structure generating self.

OUTPUT:

  • increasing tuple of integers.

EXAMPLES:

sage: quadrant = Cone([(1,0), (0,1)])
sage: quadrant.ambient_ray_indices()
(0, 1)
sage: quadrant.facets()[1].ambient_ray_indices()                            # needs sage.graphs
(1,)

>>> from sage.all import *
>>> quadrant = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> quadrant.ambient_ray_indices()
(0, 1)
>>> quadrant.facets()[Integer(1)].ambient_ray_indices()                            # needs sage.graphs
(1,)
an_affine_basis()[source]#

Return points in self that form a basis for the affine hull.

EXAMPLES:

sage: quadrant = Cone([(1,0), (0,1)])
sage: quadrant.an_affine_basis()
[(0, 0), (1, 0), (0, 1)]
sage: ray = Cone([(1, 1)])
sage: ray.an_affine_basis()
[(0, 0), (1, 1)]
sage: line = Cone([(1,0), (-1,0)])
sage: line.an_affine_basis()
[(1, 0), (0, 0)]

>>> from sage.all import *
>>> quadrant = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> quadrant.an_affine_basis()
[(0, 0), (1, 0), (0, 1)]
>>> ray = Cone([(Integer(1), Integer(1))])
>>> ray.an_affine_basis()
[(0, 0), (1, 1)]
>>> line = Cone([(Integer(1),Integer(0)), (-Integer(1),Integer(0))])
>>> line.an_affine_basis()
[(1, 0), (0, 0)]
cartesian_product(other, lattice=None)[source]#

Return the Cartesian product of self with other.

INPUT:

  • other – a cone;

  • lattice – (optional) the ambient lattice for the Cartesian product cone. By default, the direct sum of the ambient lattices of self and other is constructed.

OUTPUT:

EXAMPLES:

sage: c = Cone([(1,)])
sage: c.cartesian_product(c)
2-d cone in 2-d lattice N+N
sage: _.rays()
N+N(1, 0),
N+N(0, 1)
in 2-d lattice N+N

>>> from sage.all import *
>>> c = Cone([(Integer(1),)])
>>> c.cartesian_product(c)
2-d cone in 2-d lattice N+N
>>> _.rays()
N+N(1, 0),
N+N(0, 1)
in 2-d lattice N+N
contains(*args)[source]#

Check if a given point is contained in self.

INPUT:

  • anything. An attempt will be made to convert all arguments into a single element of the ambient space of self. If it fails, False will be returned.

OUTPUT:

  • True if the given point is contained in self, False otherwise.

EXAMPLES:

sage: c = Cone([(1,0), (0,1)])
sage: c.contains(c.lattice()(1,0))
True
sage: c.contains((1,0))
True
sage: c.contains((1,1))
True
sage: c.contains(1,1)
True
sage: c.contains((-1,0))
False
sage: c.contains(c.dual_lattice()(1,0))  # random output (warning)
False
sage: c.contains(c.dual_lattice()(1,0))
False
sage: c.contains(1)
False
sage: c.contains(1/2, sqrt(3))                                              # needs sage.symbolic
True
sage: c.contains(-1/2, sqrt(3))                                             # needs sage.symbolic
False

>>> from sage.all import *
>>> c = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> c.contains(c.lattice()(Integer(1),Integer(0)))
True
>>> c.contains((Integer(1),Integer(0)))
True
>>> c.contains((Integer(1),Integer(1)))
True
>>> c.contains(Integer(1),Integer(1))
True
>>> c.contains((-Integer(1),Integer(0)))
False
>>> c.contains(c.dual_lattice()(Integer(1),Integer(0)))  # random output (warning)
False
>>> c.contains(c.dual_lattice()(Integer(1),Integer(0)))
False
>>> c.contains(Integer(1))
False
>>> c.contains(Integer(1)/Integer(2), sqrt(Integer(3)))                                              # needs sage.symbolic
True
>>> c.contains(-Integer(1)/Integer(2), sqrt(Integer(3)))                                             # needs sage.symbolic
False
cross_positive_operators_gens()[source]#

Compute minimal generators of the cross-positive operators on this cone.

Any positive operator \(P\) on this cone will have \(s(P(x)) \ge 0\) whenever \(x\) is an element of this cone and \(s\) is an element of its dual. By contrast, the cross-positive operators need only satisfy that property on the discrete_complementarity_set(); that is, when \(x\) and \(s\) are “cross” (orthogonal).

The cross-positive operators (on some fixed cone) themselves form a closed convex cone. This method computes and returns the generators of that cone as a list of matrices.

Cross-positive operators are also called exponentially-positive, since they become positive operators when exponentiated. Other equivalent names are resolvent-positive, essentially-positive, and quasimonotone.

OUTPUT:

A list of \(n\)-by-\(n\) matrices where \(n\) is the ambient dimension of this cone. Each matrix \(L\) in the list has the property that \(s(L(x)) \ge 0\) whenever \((x,s)\) is an element of this cone’s discrete_complementarity_set().

The returned matrices generate the cone of cross-positive operators on this cone; that is,

  • Any nonnegative linear combination of the returned matrices is cross-positive on this cone.

  • Every cross-positive operator on this cone is some nonnegative linear combination of the returned matrices.

See also

lyapunov_like_basis(), positive_operators_gens(), Z_operators_gens()

REFERENCES:

EXAMPLES:

Cross-positive operators on the nonnegative orthant are negations of Z-matrices; that is, matrices whose off-diagonal elements are nonnegative:

sage: K = cones.nonnegative_orthant(2)
sage: K.cross_positive_operators_gens()
[
[0 1]  [0 0]  [1 0]  [-1  0]  [0 0]  [ 0  0]
[0 0], [1 0], [0 0], [ 0  0], [0 1], [ 0 -1]
]
sage: K = Cone([(1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1)])
sage: all(c[i][j] >= 0 for c in K.cross_positive_operators_gens()
....:                  for i in range(c.nrows())
....:                  for j in range(c.ncols())
....:                  if i != j)
True

>>> from sage.all import *
>>> K = cones.nonnegative_orthant(Integer(2))
>>> K.cross_positive_operators_gens()
[
[0 1]  [0 0]  [1 0]  [-1  0]  [0 0]  [ 0  0]
[0 0], [1 0], [0 0], [ 0  0], [0 1], [ 0 -1]
]
>>> K = Cone([(Integer(1),Integer(0),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(0),Integer(1))])
>>> all(c[i][j] >= Integer(0) for c in K.cross_positive_operators_gens()
...                  for i in range(c.nrows())
...                  for j in range(c.ncols())
...                  if i != j)
True

The trivial cone in a trivial space has no cross-positive operators:

sage: K = cones.trivial(0)
sage: K.cross_positive_operators_gens()
[]

>>> from sage.all import *
>>> K = cones.trivial(Integer(0))
>>> K.cross_positive_operators_gens()
[]

Every operator is a cross-positive operator on the ambient vector space:

sage: K = Cone([(1,), (-1,)])
sage: K.is_full_space()
True
sage: K.cross_positive_operators_gens()
[[1], [-1]]

sage: K = Cone([(1,0), (-1,0), (0,1), (0,-1)])
sage: K.is_full_space()
True
sage: K.cross_positive_operators_gens()
[
[1 0]  [-1  0]  [0 1]  [ 0 -1]  [0 0]  [ 0  0]  [0 0]  [ 0  0]
[0 0], [ 0  0], [0 0], [ 0  0], [1 0], [-1  0], [0 1], [ 0 -1]
]

>>> from sage.all import *
>>> K = Cone([(Integer(1),), (-Integer(1),)])
>>> K.is_full_space()
True
>>> K.cross_positive_operators_gens()
[[1], [-1]]

>>> K = Cone([(Integer(1),Integer(0)), (-Integer(1),Integer(0)), (Integer(0),Integer(1)), (Integer(0),-Integer(1))])
>>> K.is_full_space()
True
>>> K.cross_positive_operators_gens()
[
[1 0]  [-1  0]  [0 1]  [ 0 -1]  [0 0]  [ 0  0]  [0 0]  [ 0  0]
[0 0], [ 0  0], [0 0], [ 0  0], [1 0], [-1  0], [0 1], [ 0 -1]
]

A non-obvious application is to find the cross-positive operators on the right half-plane [Or2018b]:

sage: K = Cone([(1,0), (0,1), (0,-1)])
sage: K.cross_positive_operators_gens()
[
[1 0]  [-1  0]  [0 0]  [ 0  0]  [0 0]  [ 0  0]
[0 0], [ 0  0], [1 0], [-1  0], [0 1], [ 0 -1]
]

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1)), (Integer(0),-Integer(1))])
>>> K.cross_positive_operators_gens()
[
[1 0]  [-1  0]  [0 0]  [ 0  0]  [0 0]  [ 0  0]
[0 0], [ 0  0], [1 0], [-1  0], [0 1], [ 0 -1]
]

Cross-positive operators on a subspace are Lyapunov-like and vice-versa:

sage: K = Cone([(1,0), (-1,0), (0,1), (0,-1)])
sage: K.is_full_space()
True
sage: lls = span(vector(l.list())
....:            for l in K.lyapunov_like_basis())
sage: cs  = span(vector(c.list())
....:            for c in K.cross_positive_operators_gens())
sage: cs == lls
True

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0)), (-Integer(1),Integer(0)), (Integer(0),Integer(1)), (Integer(0),-Integer(1))])
>>> K.is_full_space()
True
>>> lls = span(vector(l.list())
...            for l in K.lyapunov_like_basis())
>>> cs  = span(vector(c.list())
...            for c in K.cross_positive_operators_gens())
>>> cs == lls
True
discrete_complementarity_set()[source]#

Compute a discrete complementarity set of this cone.

A discrete complementarity set of a cone is the set of all orthogonal pairs \((x,s)\) where \(x\) is in some fixed generating set of the cone, and \(s\) is in some fixed generating set of its dual. The generators chosen for this cone and its dual are simply their rays().

OUTPUT:

A tuple of pairs \((x,s)\) such that,

  • \(x\) and \(s\) are nonzero.

  • \(s(x)\) is zero.

  • \(x\) is one of this cone’s rays().

  • \(s\) is one of the rays() of this cone’s dual().

REFERENCES:

EXAMPLES:

Pairs of standard basis elements form a discrete complementarity set for the nonnegative orthant:

sage: K = cones.nonnegative_orthant(2)
sage: K.discrete_complementarity_set()
((N(1, 0), M(0, 1)), (N(0, 1), M(1, 0)))

>>> from sage.all import *
>>> K = cones.nonnegative_orthant(Integer(2))
>>> K.discrete_complementarity_set()
((N(1, 0), M(0, 1)), (N(0, 1), M(1, 0)))

If a cone consists of a single ray, then the second components of a discrete complementarity set for that cone should generate the orthogonal complement of the ray:

sage: K = Cone([(1,0)])
sage: K.discrete_complementarity_set()
((N(1, 0), M(0, 1)), (N(1, 0), M(0, -1)))
sage: K = Cone([(1,0,0)])
sage: K.discrete_complementarity_set()
((N(1, 0, 0), M(0, 1, 0)),
 (N(1, 0, 0), M(0, -1, 0)),
 (N(1, 0, 0), M(0, 0, 1)),
 (N(1, 0, 0), M(0, 0, -1)))

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0))])
>>> K.discrete_complementarity_set()
((N(1, 0), M(0, 1)), (N(1, 0), M(0, -1)))
>>> K = Cone([(Integer(1),Integer(0),Integer(0))])
>>> K.discrete_complementarity_set()
((N(1, 0, 0), M(0, 1, 0)),
 (N(1, 0, 0), M(0, -1, 0)),
 (N(1, 0, 0), M(0, 0, 1)),
 (N(1, 0, 0), M(0, 0, -1)))

When a cone is the entire space, its dual is the trivial cone, so the only discrete complementarity set for it is empty:

sage: K = Cone([(1,0), (-1,0), (0,1), (0,-1)])
sage: K.is_full_space()
True
sage: K.discrete_complementarity_set()
()

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0)), (-Integer(1),Integer(0)), (Integer(0),Integer(1)), (Integer(0),-Integer(1))])
>>> K.is_full_space()
True
>>> K.discrete_complementarity_set()
()

Likewise for trivial cones, whose duals are the entire space:

sage: cones.trivial(0).discrete_complementarity_set()
()

>>> from sage.all import *
>>> cones.trivial(Integer(0)).discrete_complementarity_set()
()
dual()[source]#

Return the dual cone of self.

OUTPUT:

EXAMPLES:

sage: cone = Cone([(1,0), (-1,3)])
sage: cone.dual().rays()
M(0, 1),
M(3, 1)
in 2-d lattice M

>>> from sage.all import *
>>> cone = Cone([(Integer(1),Integer(0)), (-Integer(1),Integer(3))])
>>> cone.dual().rays()
M(0, 1),
M(3, 1)
in 2-d lattice M

Now let’s look at a more complicated case:

sage: cone = Cone([(-2,-1,2), (4,1,0), (-4,-1,-5), (4,1,5)])
sage: cone.is_strictly_convex()
False
sage: cone.dim()
3
sage: cone.dual().rays()
M(7, -18, -2),
M(1,  -4,  0)
in 3-d lattice M
sage: cone.dual().dual() is cone
True

>>> from sage.all import *
>>> cone = Cone([(-Integer(2),-Integer(1),Integer(2)), (Integer(4),Integer(1),Integer(0)), (-Integer(4),-Integer(1),-Integer(5)), (Integer(4),Integer(1),Integer(5))])
>>> cone.is_strictly_convex()
False
>>> cone.dim()
3
>>> cone.dual().rays()
M(7, -18, -2),
M(1,  -4,  0)
in 3-d lattice M
>>> cone.dual().dual() is cone
True

We correctly handle the degenerate cases:

sage: N = ToricLattice(2)
sage: Cone([], lattice=N).dual().rays()  # empty cone
M( 1,  0),
M(-1,  0),
M( 0,  1),
M( 0, -1)
in 2-d lattice M
sage: Cone([(1,0)], lattice=N).dual().rays()  # ray in 2d
M(1,  0),
M(0,  1),
M(0, -1)
in 2-d lattice M
sage: Cone([(1,0),(-1,0)], lattice=N).dual().rays()  # line in 2d
M(0,  1),
M(0, -1)
in 2-d lattice M
sage: Cone([(1,0),(0,1)], lattice=N).dual().rays()  # strictly convex cone
M(0, 1),
M(1, 0)
in 2-d lattice M
sage: Cone([(1,0),(-1,0),(0,1)], lattice=N).dual().rays()  # half space
M(0, 1)
in 2-d lattice M
sage: Cone([(1,0),(0,1),(-1,-1)], lattice=N).dual().rays()  # whole space
Empty collection
in 2-d lattice M

>>> from sage.all import *
>>> N = ToricLattice(Integer(2))
>>> Cone([], lattice=N).dual().rays()  # empty cone
M( 1,  0),
M(-1,  0),
M( 0,  1),
M( 0, -1)
in 2-d lattice M
>>> Cone([(Integer(1),Integer(0))], lattice=N).dual().rays()  # ray in 2d
M(1,  0),
M(0,  1),
M(0, -1)
in 2-d lattice M
>>> Cone([(Integer(1),Integer(0)),(-Integer(1),Integer(0))], lattice=N).dual().rays()  # line in 2d
M(0,  1),
M(0, -1)
in 2-d lattice M
>>> Cone([(Integer(1),Integer(0)),(Integer(0),Integer(1))], lattice=N).dual().rays()  # strictly convex cone
M(0, 1),
M(1, 0)
in 2-d lattice M
>>> Cone([(Integer(1),Integer(0)),(-Integer(1),Integer(0)),(Integer(0),Integer(1))], lattice=N).dual().rays()  # half space
M(0, 1)
in 2-d lattice M
>>> Cone([(Integer(1),Integer(0)),(Integer(0),Integer(1)),(-Integer(1),-Integer(1))], lattice=N).dual().rays()  # whole space
Empty collection
in 2-d lattice M
embed(cone)[source]#

Return the cone equivalent to the given one, but sitting in self as a face.

You may need to use this method before calling methods of cone that depend on the ambient structure, such as ambient_ray_indices() or facet_of(). The cone returned by this method will have self as ambient. If cone does not represent a valid cone of self, ValueError exception is raised.

Note

This method is very quick if self is already the ambient structure of cone, so you can use without extra checks and performance hit even if cone is likely to sit in self but in principle may not.

INPUT:

OUTPUT:

  • a cone, equivalent to cone but sitting inside self.

EXAMPLES:

Let’s take a 3-d cone on 4 rays:

sage: c = Cone([(1,0,1), (0,1,1), (-1,0,1), (0,-1,1)])

>>> from sage.all import *
>>> c = Cone([(Integer(1),Integer(0),Integer(1)), (Integer(0),Integer(1),Integer(1)), (-Integer(1),Integer(0),Integer(1)), (Integer(0),-Integer(1),Integer(1))])

Then any ray generates a 1-d face of this cone, but if you construct such a face directly, it will not “sit” inside the cone:

sage: ray = Cone([(0,-1,1)])
sage: ray
1-d cone in 3-d lattice N
sage: ray.ambient_ray_indices()
(0,)
sage: ray.adjacent()                                                        # needs sage.graphs
()
sage: ray.ambient()
1-d cone in 3-d lattice N

>>> from sage.all import *
>>> ray = Cone([(Integer(0),-Integer(1),Integer(1))])
>>> ray
1-d cone in 3-d lattice N
>>> ray.ambient_ray_indices()
(0,)
>>> ray.adjacent()                                                        # needs sage.graphs
()
>>> ray.ambient()
1-d cone in 3-d lattice N

If we want to operate with this ray as a face of the cone, we need to embed it first:

sage: # needs sage.graphs
sage: e_ray = c.embed(ray)
sage: e_ray
1-d face of 3-d cone in 3-d lattice N
sage: e_ray.rays()
N(0, -1, 1)
in 3-d lattice N
sage: e_ray is ray
False
sage: e_ray.is_equivalent(ray)
True
sage: e_ray.ambient_ray_indices()
(3,)
sage: e_ray.adjacent()
(1-d face of 3-d cone in 3-d lattice N,
 1-d face of 3-d cone in 3-d lattice N)
sage: e_ray.ambient()
3-d cone in 3-d lattice N

>>> from sage.all import *
>>> # needs sage.graphs
>>> e_ray = c.embed(ray)
>>> e_ray
1-d face of 3-d cone in 3-d lattice N
>>> e_ray.rays()
N(0, -1, 1)
in 3-d lattice N
>>> e_ray is ray
False
>>> e_ray.is_equivalent(ray)
True
>>> e_ray.ambient_ray_indices()
(3,)
>>> e_ray.adjacent()
(1-d face of 3-d cone in 3-d lattice N,
 1-d face of 3-d cone in 3-d lattice N)
>>> e_ray.ambient()
3-d cone in 3-d lattice N

Not every cone can be embedded into a fixed ambient cone:

sage: c.embed(Cone([(0,0,1)]))
Traceback (most recent call last):
...
ValueError: 1-d cone in 3-d lattice N is not a face
of 3-d cone in 3-d lattice N!
sage: c.embed(Cone([(1,0,1), (-1,0,1)]))                                    # needs sage.graphs
Traceback (most recent call last):
...
ValueError: 2-d cone in 3-d lattice N is not a face
of 3-d cone in 3-d lattice N!

>>> from sage.all import *
>>> c.embed(Cone([(Integer(0),Integer(0),Integer(1))]))
Traceback (most recent call last):
...
ValueError: 1-d cone in 3-d lattice N is not a face
of 3-d cone in 3-d lattice N!
>>> c.embed(Cone([(Integer(1),Integer(0),Integer(1)), (-Integer(1),Integer(0),Integer(1))]))                                    # needs sage.graphs
Traceback (most recent call last):
...
ValueError: 2-d cone in 3-d lattice N is not a face
of 3-d cone in 3-d lattice N!
face_lattice()[source]#

Return the face lattice of self.

This lattice will have the origin as the bottom (we do not include the empty set as a face) and this cone itself as the top.

OUTPUT:

EXAMPLES:

Let’s take a look at the face lattice of the first quadrant:

sage: quadrant = Cone([(1,0), (0,1)])
sage: L = quadrant.face_lattice()                                           # needs sage.combinat sage.graphs
sage: L                                                                     # needs sage.combinat sage.graphs
Finite lattice containing 4 elements with distinguished linear extension

>>> from sage.all import *
>>> quadrant = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> L = quadrant.face_lattice()                                           # needs sage.combinat sage.graphs
>>> L                                                                     # needs sage.combinat sage.graphs
Finite lattice containing 4 elements with distinguished linear extension

To see all faces arranged by dimension, you can do this:

sage: for level in L.level_sets(): print(level)                             # needs sage.combinat sage.graphs
[0-d face of 2-d cone in 2-d lattice N]
[1-d face of 2-d cone in 2-d lattice N,
 1-d face of 2-d cone in 2-d lattice N]
[2-d cone in 2-d lattice N]

>>> from sage.all import *
>>> for level in L.level_sets(): print(level)                             # needs sage.combinat sage.graphs
[0-d face of 2-d cone in 2-d lattice N]
[1-d face of 2-d cone in 2-d lattice N,
 1-d face of 2-d cone in 2-d lattice N]
[2-d cone in 2-d lattice N]

For a particular face you can look at its actual rays…

sage: face = L.level_sets()[1][0]                                           # needs sage.combinat sage.graphs
sage: face.rays()                                                           # needs sage.combinat sage.graphs
N(1, 0)
in 2-d lattice N

>>> from sage.all import *
>>> face = L.level_sets()[Integer(1)][Integer(0)]                                           # needs sage.combinat sage.graphs
>>> face.rays()                                                           # needs sage.combinat sage.graphs
N(1, 0)
in 2-d lattice N

… or you can see the index of the ray of the original cone that corresponds to the above one:

sage: face.ambient_ray_indices()                                            # needs sage.combinat sage.graphs
(0,)
sage: quadrant.ray(0)
N(1, 0)

>>> from sage.all import *
>>> face.ambient_ray_indices()                                            # needs sage.combinat sage.graphs
(0,)
>>> quadrant.ray(Integer(0))
N(1, 0)

An alternative to extracting faces from the face lattice is to use faces() method:

sage: face is quadrant.faces(dim=1)[0]                                      # needs sage.combinat sage.graphs
True

>>> from sage.all import *
>>> face is quadrant.faces(dim=Integer(1))[Integer(0)]                                      # needs sage.combinat sage.graphs
True

The advantage of working with the face lattice directly is that you can (relatively easily) get faces that are related to the given one:

sage: face = L.level_sets()[1][0]                                           # needs sage.combinat sage.graphs
sage: D = L.hasse_diagram()                                                 # needs sage.combinat sage.graphs
sage: sorted(D.neighbors(face))                                             # needs sage.combinat sage.graphs
[0-d face of 2-d cone in 2-d lattice N,
 2-d cone in 2-d lattice N]

>>> from sage.all import *
>>> face = L.level_sets()[Integer(1)][Integer(0)]                                           # needs sage.combinat sage.graphs
>>> D = L.hasse_diagram()                                                 # needs sage.combinat sage.graphs
>>> sorted(D.neighbors(face))                                             # needs sage.combinat sage.graphs
[0-d face of 2-d cone in 2-d lattice N,
 2-d cone in 2-d lattice N]

However, you can achieve some of this functionality using facets(), facet_of(), and adjacent() methods:

sage: # needs sage.graphs
sage: face = quadrant.faces(1)[0]
sage: face
1-d face of 2-d cone in 2-d lattice N
sage: face.rays()
N(1, 0)
in 2-d lattice N
sage: face.facets()
(0-d face of 2-d cone in 2-d lattice N,)
sage: face.facet_of()
(2-d cone in 2-d lattice N,)
sage: face.adjacent()
(1-d face of 2-d cone in 2-d lattice N,)
sage: face.adjacent()[0].rays()
N(0, 1)
in 2-d lattice N

>>> from sage.all import *
>>> # needs sage.graphs
>>> face = quadrant.faces(Integer(1))[Integer(0)]
>>> face
1-d face of 2-d cone in 2-d lattice N
>>> face.rays()
N(1, 0)
in 2-d lattice N
>>> face.facets()
(0-d face of 2-d cone in 2-d lattice N,)
>>> face.facet_of()
(2-d cone in 2-d lattice N,)
>>> face.adjacent()
(1-d face of 2-d cone in 2-d lattice N,)
>>> face.adjacent()[Integer(0)].rays()
N(0, 1)
in 2-d lattice N

Note that if cone is a face of supercone, then the face lattice of cone consists of (appropriate) faces of supercone:

sage: # needs sage.combinat sage.graphs
sage: supercone = Cone([(1,2,3,4), (5,6,7,8),
....:                   (1,2,4,8), (1,3,9,7)])
sage: supercone.face_lattice()
Finite lattice containing 16 elements with distinguished linear extension
sage: supercone.face_lattice().top()
4-d cone in 4-d lattice N
sage: cone = supercone.facets()[0]
sage: cone
3-d face of 4-d cone in 4-d lattice N
sage: cone.face_lattice()
Finite poset containing 8 elements with distinguished linear extension
sage: cone.face_lattice().bottom()
0-d face of 4-d cone in 4-d lattice N
sage: cone.face_lattice().top()
3-d face of 4-d cone in 4-d lattice N
sage: cone.face_lattice().top() == cone
True

>>> from sage.all import *
>>> # needs sage.combinat sage.graphs
>>> supercone = Cone([(Integer(1),Integer(2),Integer(3),Integer(4)), (Integer(5),Integer(6),Integer(7),Integer(8)),
...                   (Integer(1),Integer(2),Integer(4),Integer(8)), (Integer(1),Integer(3),Integer(9),Integer(7))])
>>> supercone.face_lattice()
Finite lattice containing 16 elements with distinguished linear extension
>>> supercone.face_lattice().top()
4-d cone in 4-d lattice N
>>> cone = supercone.facets()[Integer(0)]
>>> cone
3-d face of 4-d cone in 4-d lattice N
>>> cone.face_lattice()
Finite poset containing 8 elements with distinguished linear extension
>>> cone.face_lattice().bottom()
0-d face of 4-d cone in 4-d lattice N
>>> cone.face_lattice().top()
3-d face of 4-d cone in 4-d lattice N
>>> cone.face_lattice().top() == cone
True
faces(dim=None, codim=None)[source]#

Return faces of self of specified (co)dimension.

INPUT:

  • dim – integer, dimension of the requested faces;

  • codim – integer, codimension of the requested faces.

Note

You can specify at most one parameter. If you don’t give any, then all faces will be returned.

OUTPUT:

  • if either dim or codim is given, the output will be a tuple of cones;

  • if neither dim nor codim is given, the output will be the tuple of tuples as above, giving faces of all existing dimensions. If you care about inclusion relations between faces, consider using face_lattice() or adjacent(), facet_of(), and facets().

EXAMPLES:

Let’s take a look at the faces of the first quadrant:

sage: quadrant = Cone([(1,0), (0,1)])
sage: quadrant.faces()                                                      # needs sage.graphs
((0-d face of 2-d cone in 2-d lattice N,),
 (1-d face of 2-d cone in 2-d lattice N,
  1-d face of 2-d cone in 2-d lattice N),
 (2-d cone in 2-d lattice N,))
sage: quadrant.faces(dim=1)                                                 # needs sage.graphs
(1-d face of 2-d cone in 2-d lattice N,
 1-d face of 2-d cone in 2-d lattice N)
sage: face = quadrant.faces(dim=1)[0]                                       # needs sage.graphs

>>> from sage.all import *
>>> quadrant = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> quadrant.faces()                                                      # needs sage.graphs
((0-d face of 2-d cone in 2-d lattice N,),
 (1-d face of 2-d cone in 2-d lattice N,
  1-d face of 2-d cone in 2-d lattice N),
 (2-d cone in 2-d lattice N,))
>>> quadrant.faces(dim=Integer(1))                                                 # needs sage.graphs
(1-d face of 2-d cone in 2-d lattice N,
 1-d face of 2-d cone in 2-d lattice N)
>>> face = quadrant.faces(dim=Integer(1))[Integer(0)]                                       # needs sage.graphs

Now you can look at the actual rays of this face…

sage: face.rays()                                                           # needs sage.graphs
N(1, 0)
in 2-d lattice N

>>> from sage.all import *
>>> face.rays()                                                           # needs sage.graphs
N(1, 0)
in 2-d lattice N

… or you can see indices of the rays of the original cone that correspond to the above ray:

sage: face.ambient_ray_indices()                                            # needs sage.graphs
(0,)
sage: quadrant.ray(0)
N(1, 0)

>>> from sage.all import *
>>> face.ambient_ray_indices()                                            # needs sage.graphs
(0,)
>>> quadrant.ray(Integer(0))
N(1, 0)

Note that it is OK to ask for faces of too small or high dimension:

sage: quadrant.faces(-1)                                                    # needs sage.graphs
()
sage: quadrant.faces(3)                                                     # needs sage.graphs
()

>>> from sage.all import *
>>> quadrant.faces(-Integer(1))                                                    # needs sage.graphs
()
>>> quadrant.faces(Integer(3))                                                     # needs sage.graphs
()

In the case of non-strictly convex cones even faces of small non-negative dimension may be missing:

sage: # needs sage.graphs
sage: halfplane = Cone([(1,0), (0,1), (-1,0)])
sage: halfplane.faces(0)
()
sage: halfplane.faces()
((1-d face of 2-d cone in 2-d lattice N,),
 (2-d cone in 2-d lattice N,))
sage: plane = Cone([(1,0), (0,1), (-1,-1)])
sage: plane.faces(1)
()
sage: plane.faces()
((2-d cone in 2-d lattice N,),)

>>> from sage.all import *
>>> # needs sage.graphs
>>> halfplane = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1)), (-Integer(1),Integer(0))])
>>> halfplane.faces(Integer(0))
()
>>> halfplane.faces()
((1-d face of 2-d cone in 2-d lattice N,),
 (2-d cone in 2-d lattice N,))
>>> plane = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1)), (-Integer(1),-Integer(1))])
>>> plane.faces(Integer(1))
()
>>> plane.faces()
((2-d cone in 2-d lattice N,),)
facet_normals()[source]#

Return inward normals to facets of self.

Note

  1. For a not full-dimensional cone facet normals will specify hyperplanes whose intersections with the space spanned by self give facets of self.

  2. For a not strictly convex cone facet normals will be orthogonal to the linear subspace of self, i.e. they always will be elements of the dual cone of self.

  3. The order of normals is random, but consistent with facets().

OUTPUT:

If the ambient lattice() of self is a toric lattice, the facet normals will be elements of the dual lattice. If it is a general lattice (like ZZ^n) that does not have a dual() method, the facet normals will be returned as integral vectors.

EXAMPLES:

sage: cone = Cone([(1,0), (-1,3)])
sage: cone.facet_normals()
M(0, 1),
M(3, 1)
in 2-d lattice M

>>> from sage.all import *
>>> cone = Cone([(Integer(1),Integer(0)), (-Integer(1),Integer(3))])
>>> cone.facet_normals()
M(0, 1),
M(3, 1)
in 2-d lattice M

Now let’s look at a more complicated case:

sage: cone = Cone([(-2,-1,2), (4,1,0), (-4,-1,-5), (4,1,5)])
sage: cone.is_strictly_convex()
False
sage: cone.dim()
3
sage: cone.linear_subspace().dimension()
1
sage: lsg = (QQ^3)(cone.linear_subspace().gen(0)); lsg
(1, 1/4, 5/4)
sage: cone.facet_normals()
M(7, -18, -2),
M(1,  -4,  0)
in 3-d lattice M
sage: [lsg*normal for normal in cone.facet_normals()]
[0, 0]

>>> from sage.all import *
>>> cone = Cone([(-Integer(2),-Integer(1),Integer(2)), (Integer(4),Integer(1),Integer(0)), (-Integer(4),-Integer(1),-Integer(5)), (Integer(4),Integer(1),Integer(5))])
>>> cone.is_strictly_convex()
False
>>> cone.dim()
3
>>> cone.linear_subspace().dimension()
1
>>> lsg = (QQ**Integer(3))(cone.linear_subspace().gen(Integer(0))); lsg
(1, 1/4, 5/4)
>>> cone.facet_normals()
M(7, -18, -2),
M(1,  -4,  0)
in 3-d lattice M
>>> [lsg*normal for normal in cone.facet_normals()]
[0, 0]

A lattice that does not have a dual() method:

sage: Cone([(1,1),(0,1)], lattice=ZZ^2).facet_normals()
(-1, 1),
( 1, 0)
in Ambient free module of rank 2
over the principal ideal domain Integer Ring

>>> from sage.all import *
>>> Cone([(Integer(1),Integer(1)),(Integer(0),Integer(1))], lattice=ZZ**Integer(2)).facet_normals()
(-1, 1),
( 1, 0)
in Ambient free module of rank 2
over the principal ideal domain Integer Ring

We correctly handle the degenerate cases:

sage: N = ToricLattice(2)
sage: Cone([], lattice=N).facet_normals()  # empty cone
Empty collection
in 2-d lattice M
sage: Cone([(1,0)], lattice=N).facet_normals()  # ray in 2d
M(1, 0)
in 2-d lattice M
sage: Cone([(1,0),(-1,0)], lattice=N).facet_normals()  # line in 2d
Empty collection
in 2-d lattice M
sage: Cone([(1,0),(0,1)], lattice=N).facet_normals()  # strictly convex cone
M(0, 1),
M(1, 0)
in 2-d lattice M
sage: Cone([(1,0),(-1,0),(0,1)], lattice=N).facet_normals()  # half space
M(0, 1)
in 2-d lattice M
sage: Cone([(1,0),(0,1),(-1,-1)], lattice=N).facet_normals()  # whole space
Empty collection
in 2-d lattice M

>>> from sage.all import *
>>> N = ToricLattice(Integer(2))
>>> Cone([], lattice=N).facet_normals()  # empty cone
Empty collection
in 2-d lattice M
>>> Cone([(Integer(1),Integer(0))], lattice=N).facet_normals()  # ray in 2d
M(1, 0)
in 2-d lattice M
>>> Cone([(Integer(1),Integer(0)),(-Integer(1),Integer(0))], lattice=N).facet_normals()  # line in 2d
Empty collection
in 2-d lattice M
>>> Cone([(Integer(1),Integer(0)),(Integer(0),Integer(1))], lattice=N).facet_normals()  # strictly convex cone
M(0, 1),
M(1, 0)
in 2-d lattice M
>>> Cone([(Integer(1),Integer(0)),(-Integer(1),Integer(0)),(Integer(0),Integer(1))], lattice=N).facet_normals()  # half space
M(0, 1)
in 2-d lattice M
>>> Cone([(Integer(1),Integer(0)),(Integer(0),Integer(1)),(-Integer(1),-Integer(1))], lattice=N).facet_normals()  # whole space
Empty collection
in 2-d lattice M
facet_of()[source]#

Return cones of the ambient face lattice having self as a facet.

OUTPUT:

EXAMPLES:

sage: # needs sage.graphs
sage: octant = Cone([(1,0,0), (0,1,0), (0,0,1)])
sage: octant.facet_of()
()
sage: one_face = octant.faces(1)[0]
sage: len(one_face.facet_of())
2
sage: one_face.facet_of()[1]
2-d face of 3-d cone in 3-d lattice N

>>> from sage.all import *
>>> # needs sage.graphs
>>> octant = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(1))])
>>> octant.facet_of()
()
>>> one_face = octant.faces(Integer(1))[Integer(0)]
>>> len(one_face.facet_of())
2
>>> one_face.facet_of()[Integer(1)]
2-d face of 3-d cone in 3-d lattice N

While fan is the top element of its own cone lattice, which is a variant of a face lattice, we do not refer to cones as its facets:

sage: fan = Fan([octant])                                                   # needs sage.graphs
sage: fan.generating_cone(0).facet_of()                                     # needs sage.graphs
()

>>> from sage.all import *
>>> fan = Fan([octant])                                                   # needs sage.graphs
>>> fan.generating_cone(Integer(0)).facet_of()                                     # needs sage.graphs
()

Subcones of generating cones work as before:

sage: one_cone = fan(1)[0]                                                  # needs sage.graphs
sage: len(one_cone.facet_of())                                              # needs sage.graphs
2

>>> from sage.all import *
>>> one_cone = fan(Integer(1))[Integer(0)]                                                  # needs sage.graphs
>>> len(one_cone.facet_of())                                              # needs sage.graphs
2
facets()[source]#

Return facets (faces of codimension 1) of self.

OUTPUT:

EXAMPLES:

sage: quadrant = Cone([(1,0), (0,1)])
sage: quadrant.facets()                                                     # needs sage.graphs
(1-d face of 2-d cone in 2-d lattice N,
 1-d face of 2-d cone in 2-d lattice N)

>>> from sage.all import *
>>> quadrant = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> quadrant.facets()                                                     # needs sage.graphs
(1-d face of 2-d cone in 2-d lattice N,
 1-d face of 2-d cone in 2-d lattice N)
incidence_matrix()[source]#

Return the incidence matrix.

Note

The columns correspond to facets/facet normals in the order of facet_normals(), the rows correspond to the rays in the order of rays().

EXAMPLES:

sage: octant = Cone([(1,0,0), (0,1,0), (0,0,1)])
sage: octant.incidence_matrix()
[0 1 1]
[1 0 1]
[1 1 0]

sage: halfspace = Cone([(1,0,0), (0,1,0), (-1,-1,0), (0,0,1)])
sage: halfspace.incidence_matrix()
[0]
[1]
[1]
[1]
[1]

>>> from sage.all import *
>>> octant = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(1))])
>>> octant.incidence_matrix()
[0 1 1]
[1 0 1]
[1 1 0]

>>> halfspace = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (-Integer(1),-Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(1))])
>>> halfspace.incidence_matrix()
[0]
[1]
[1]
[1]
[1]
interior()[source]#

Return the interior of self.

OUTPUT:

EXAMPLES:

sage: c = Cone([(1,0,0), (0,1,0)]); c
2-d cone in 3-d lattice N
sage: c.interior()
The empty polyhedron in ZZ^3

sage: origin = cones.trivial(2); origin
0-d cone in 2-d lattice N
sage: origin.interior()
The empty polyhedron in ZZ^2

sage: K = cones.nonnegative_orthant(2); K
2-d cone in 2-d lattice N
sage: K.interior()
Relative interior of 2-d cone in 2-d lattice N

sage: K2 = Cone([(1,0),(-1,0),(0,1),(0,-1)]); K2
2-d cone in 2-d lattice N
sage: K2.interior() is K2
True

>>> from sage.all import *
>>> c = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0))]); c
2-d cone in 3-d lattice N
>>> c.interior()
The empty polyhedron in ZZ^3

>>> origin = cones.trivial(Integer(2)); origin
0-d cone in 2-d lattice N
>>> origin.interior()
The empty polyhedron in ZZ^2

>>> K = cones.nonnegative_orthant(Integer(2)); K
2-d cone in 2-d lattice N
>>> K.interior()
Relative interior of 2-d cone in 2-d lattice N

>>> K2 = Cone([(Integer(1),Integer(0)),(-Integer(1),Integer(0)),(Integer(0),Integer(1)),(Integer(0),-Integer(1))]); K2
2-d cone in 2-d lattice N
>>> K2.interior() is K2
True
interior_contains(*args)[source]#

Check if a given point is contained in the interior of self.

For a cone of strictly lower-dimension than the ambient space, the interior is always empty. You probably want to use relative_interior_contains() in this case.

INPUT:

  • anything. An attempt will be made to convert all arguments into a single element of the ambient space of self. If it fails, False will be returned.

OUTPUT:

  • True if the given point is contained in the interior of self, False otherwise.

EXAMPLES:

sage: c = Cone([(1,0), (0,1)])
sage: c.contains((1,1))
True
sage: c.interior_contains((1,1))
True
sage: c.contains((1,0))
True
sage: c.interior_contains((1,0))
False

>>> from sage.all import *
>>> c = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> c.contains((Integer(1),Integer(1)))
True
>>> c.interior_contains((Integer(1),Integer(1)))
True
>>> c.contains((Integer(1),Integer(0)))
True
>>> c.interior_contains((Integer(1),Integer(0)))
False
intersection(other)[source]#

Compute the intersection of two cones.

INPUT:

OUTPUT:

This raises ValueError if the ambient space dimensions are not compatible.

EXAMPLES:

sage: cone1 = Cone([(1,0), (-1, 3)])
sage: cone2 = Cone([(-1,0), (2, 5)])
sage: cone1.intersection(cone2).rays()
N(-1, 3),
N( 2, 5)
in 2-d lattice N

>>> from sage.all import *
>>> cone1 = Cone([(Integer(1),Integer(0)), (-Integer(1), Integer(3))])
>>> cone2 = Cone([(-Integer(1),Integer(0)), (Integer(2), Integer(5))])
>>> cone1.intersection(cone2).rays()
N(-1, 3),
N( 2, 5)
in 2-d lattice N

The intersection can also be expressed using the operator &:

sage: (cone1 & cone2).rays()
N(-1, 3),
N( 2, 5)
in 2-d lattice N

>>> from sage.all import *
>>> (cone1 & cone2).rays()
N(-1, 3),
N( 2, 5)
in 2-d lattice N

It is OK to intersect cones living in sublattices of the same ambient lattice:

sage: N = cone1.lattice()
sage: Ns = N.submodule([(1,1)])
sage: cone3 = Cone([(1,1)], lattice=Ns)
sage: I = cone1.intersection(cone3)
sage: I.rays()
N(1, 1)
in Sublattice <N(1, 1)>
sage: I.lattice()
Sublattice <N(1, 1)>

>>> from sage.all import *
>>> N = cone1.lattice()
>>> Ns = N.submodule([(Integer(1),Integer(1))])
>>> cone3 = Cone([(Integer(1),Integer(1))], lattice=Ns)
>>> I = cone1.intersection(cone3)
>>> I.rays()
N(1, 1)
in Sublattice <N(1, 1)>
>>> I.lattice()
Sublattice <N(1, 1)>

But you cannot intersect cones from incompatible lattices without explicit conversion:

sage: cone1.intersection(cone1.dual())
Traceback (most recent call last):
...
ValueError: 2-d lattice N and 2-d lattice M
have different ambient lattices!
sage: cone1.intersection(Cone(cone1.dual().rays(), N)).rays()
N(3, 1),
N(0, 1)
in 2-d lattice N

>>> from sage.all import *
>>> cone1.intersection(cone1.dual())
Traceback (most recent call last):
...
ValueError: 2-d lattice N and 2-d lattice M
have different ambient lattices!
>>> cone1.intersection(Cone(cone1.dual().rays(), N)).rays()
N(3, 1),
N(0, 1)
in 2-d lattice N

An intersection with a polyhedron returns a polyhedron:

sage: cone = Cone([(1,0), (-1,0), (0,1)])
sage: p = polytopes.hypercube(2)
sage: cone & p
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices
sage: sorted(_.vertices_list())
[[-1, 0], [-1, 1], [1, 0], [1, 1]]

>>> from sage.all import *
>>> cone = Cone([(Integer(1),Integer(0)), (-Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> p = polytopes.hypercube(Integer(2))
>>> cone & p
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices
>>> sorted(_.vertices_list())
[[-1, 0], [-1, 1], [1, 0], [1, 1]]
is_compact()[source]#

Checks if the cone has no rays.

OUTPUT:

  • True if the cone has no rays, False otherwise.

EXAMPLES:

sage: c0 = cones.trivial(3)
sage: c0.is_trivial()
True
sage: c0.nrays()
0

>>> from sage.all import *
>>> c0 = cones.trivial(Integer(3))
>>> c0.is_trivial()
True
>>> c0.nrays()
0
is_empty()[source]#

Return whether self is the empty set.

Because a cone always contains the origin, this method returns False.

EXAMPLES:

sage: trivial_cone = cones.trivial(3)
sage: trivial_cone.is_empty()
False

>>> from sage.all import *
>>> trivial_cone = cones.trivial(Integer(3))
>>> trivial_cone.is_empty()
False
is_equivalent(other)[source]#

Check if self is “mathematically” the same as other.

INPUT:

  • other – cone.

OUTPUT:

  • True if self and other define the same cones as sets of points in the same lattice, False otherwise.

There are three different equivalences between cones \(C_1\) and \(C_2\) in the same lattice:

  1. They have the same generating rays in the same order. This is tested by C1 == C2.

  2. They describe the same sets of points. This is tested by C1.is_equivalent(C2).

  3. They are in the same orbit of \(GL(n,\ZZ)\) (and, therefore, correspond to isomorphic affine toric varieties). This is tested by C1.is_isomorphic(C2).

EXAMPLES:

sage: cone1 = Cone([(1,0), (-1, 3)])
sage: cone2 = Cone([(-1,3), (1, 0)])
sage: cone1.rays()
N( 1, 0),
N(-1, 3)
in 2-d lattice N
sage: cone2.rays()
N(-1, 3),
N( 1, 0)
in 2-d lattice N
sage: cone1 == cone2
False
sage: cone1.is_equivalent(cone2)
True

>>> from sage.all import *
>>> cone1 = Cone([(Integer(1),Integer(0)), (-Integer(1), Integer(3))])
>>> cone2 = Cone([(-Integer(1),Integer(3)), (Integer(1), Integer(0))])
>>> cone1.rays()
N( 1, 0),
N(-1, 3)
in 2-d lattice N
>>> cone2.rays()
N(-1, 3),
N( 1, 0)
in 2-d lattice N
>>> cone1 == cone2
False
>>> cone1.is_equivalent(cone2)
True
is_face_of(cone)[source]#

Check if self forms a face of another cone.

INPUT:

  • cone – cone.

OUTPUT:

  • True if self is a face of cone, False otherwise.

EXAMPLES:

sage: quadrant = Cone([(1,0), (0,1)])
sage: cone1 = Cone([(1,0)])
sage: cone2 = Cone([(1,2)])
sage: quadrant.is_face_of(quadrant)
True
sage: cone1.is_face_of(quadrant)
True
sage: cone2.is_face_of(quadrant)
False

>>> from sage.all import *
>>> quadrant = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> cone1 = Cone([(Integer(1),Integer(0))])
>>> cone2 = Cone([(Integer(1),Integer(2))])
>>> quadrant.is_face_of(quadrant)
True
>>> cone1.is_face_of(quadrant)
True
>>> cone2.is_face_of(quadrant)
False

Being a face means more than just saturating a facet inequality:

sage: octant = Cone([(1,0,0), (0,1,0), (0,0,1)])
sage: cone = Cone([(2,1,0),(1,2,0)])
sage: cone.is_face_of(octant)
False

>>> from sage.all import *
>>> octant = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(1))])
>>> cone = Cone([(Integer(2),Integer(1),Integer(0)),(Integer(1),Integer(2),Integer(0))])
>>> cone.is_face_of(octant)
False
is_full_dimensional()[source]#

Check if this cone is solid.

A cone is said to be solid if it has nonempty interior. That is, if its extreme rays span the entire ambient space.

An alias is is_full_dimensional().

OUTPUT:

True if this cone is solid, and False otherwise.

See also

is_proper()

EXAMPLES:

The nonnegative orthant is always solid:

sage: quadrant = cones.nonnegative_orthant(2)
sage: quadrant.is_solid()
True
sage: octant = Cone([(1,0,0), (0,1,0), (0,0,1)])
sage: octant.is_solid()
True

>>> from sage.all import *
>>> quadrant = cones.nonnegative_orthant(Integer(2))
>>> quadrant.is_solid()
True
>>> octant = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(1))])
>>> octant.is_solid()
True

However, if we embed the two-dimensional nonnegative quadrant into three-dimensional space, then the resulting cone no longer has interior, so it is not solid:

sage: quadrant = Cone([(1,0,0), (0,1,0)])
sage: quadrant.is_solid()
False

>>> from sage.all import *
>>> quadrant = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0))])
>>> quadrant.is_solid()
False
is_full_space()[source]#

Check if this cone is equal to its ambient vector space.

An alias is is_universe().

OUTPUT:

True if this cone equals its entire ambient vector space and False otherwise.

EXAMPLES:

A single ray in two dimensions is not equal to the entire space:

sage: K = Cone([(1,0)])
sage: K.is_full_space()
False

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0))])
>>> K.is_full_space()
False

Neither is the nonnegative orthant:

sage: K = cones.nonnegative_orthant(2)
sage: K.is_full_space()
False

>>> from sage.all import *
>>> K = cones.nonnegative_orthant(Integer(2))
>>> K.is_full_space()
False

The right half-space contains a vector subspace, but it is still not equal to the entire space:

sage: K = Cone([(1,0), (-1,0), (0,1)])
sage: K.is_full_space()
False

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0)), (-Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> K.is_full_space()
False

However, if we allow conic combinations of both axes, then the resulting cone is the entire two-dimensional space:

sage: K = Cone([(1,0), (-1,0), (0,1), (0,-1)])
sage: K.is_full_space()
True

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0)), (-Integer(1),Integer(0)), (Integer(0),Integer(1)), (Integer(0),-Integer(1))])
>>> K.is_full_space()
True
is_isomorphic(other)[source]#

Check if self is in the same \(GL(n, \ZZ)\)-orbit as other.

INPUT:

  • other – cone.

OUTPUT:

  • True if self and other are in the same \(GL(n, \ZZ)\)-orbit, False otherwise.

There are three different equivalences between cones \(C_1\) and \(C_2\) in the same lattice:

  1. They have the same generating rays in the same order. This is tested by C1 == C2.

  2. They describe the same sets of points. This is tested by C1.is_equivalent(C2).

  3. They are in the same orbit of \(GL(n,\ZZ)\) (and, therefore, correspond to isomorphic affine toric varieties). This is tested by C1.is_isomorphic(C2).

EXAMPLES:

sage: cone1 = Cone([(1,0), (0, 3)])
sage: m = matrix(ZZ, [(1, -5), (-1, 4)]) # a GL(2,ZZ)-matrix
sage: cone2 = Cone( m*r for r in cone1.rays() )
sage: cone1.is_isomorphic(cone2)
True

sage: cone1 = Cone([(1,0), (0, 3)])
sage: cone2 = Cone([(-1,3), (1, 0)])
sage: cone1.is_isomorphic(cone2)
False

>>> from sage.all import *
>>> cone1 = Cone([(Integer(1),Integer(0)), (Integer(0), Integer(3))])
>>> m = matrix(ZZ, [(Integer(1), -Integer(5)), (-Integer(1), Integer(4))]) # a GL(2,ZZ)-matrix
>>> cone2 = Cone( m*r for r in cone1.rays() )
>>> cone1.is_isomorphic(cone2)
True

>>> cone1 = Cone([(Integer(1),Integer(0)), (Integer(0), Integer(3))])
>>> cone2 = Cone([(-Integer(1),Integer(3)), (Integer(1), Integer(0))])
>>> cone1.is_isomorphic(cone2)
False
is_proper()[source]#

Check if this cone is proper.

A cone is said to be proper if it is closed, convex, solid, and contains no lines. This cone is assumed to be closed and convex; therefore it is proper if it is solid and contains no lines.

OUTPUT:

True if this cone is proper, and False otherwise.

See also

is_strictly_convex(), is_solid()

EXAMPLES:

The nonnegative orthant is always proper:

sage: quadrant = cones.nonnegative_orthant(2)
sage: quadrant.is_proper()
True
sage: octant = Cone([(1,0,0), (0,1,0), (0,0,1)])
sage: octant.is_proper()
True

>>> from sage.all import *
>>> quadrant = cones.nonnegative_orthant(Integer(2))
>>> quadrant.is_proper()
True
>>> octant = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(1))])
>>> octant.is_proper()
True

However, if we embed the two-dimensional nonnegative quadrant into three-dimensional space, then the resulting cone no longer has interior, so it is not solid, and thus not proper:

sage: quadrant = Cone([(1,0,0), (0,1,0)])
sage: quadrant.is_proper()
False

>>> from sage.all import *
>>> quadrant = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0))])
>>> quadrant.is_proper()
False

Likewise, a half-space contains at least one line, so it is not proper:

sage: halfspace = Cone([(1,0), (0,1), (-1,0)])
sage: halfspace.is_proper()
False

>>> from sage.all import *
>>> halfspace = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1)), (-Integer(1),Integer(0))])
>>> halfspace.is_proper()
False
is_relatively_open()[source]#

Return whether self is relatively open.

OUTPUT:

Boolean.

EXAMPLES:

sage: K = cones.nonnegative_orthant(3)
sage: K.is_relatively_open()
False

sage: K1 = Cone([(1,0), (-1,0)]); K1
1-d cone in 2-d lattice N
sage: K1.is_relatively_open()
True

>>> from sage.all import *
>>> K = cones.nonnegative_orthant(Integer(3))
>>> K.is_relatively_open()
False

>>> K1 = Cone([(Integer(1),Integer(0)), (-Integer(1),Integer(0))]); K1
1-d cone in 2-d lattice N
>>> K1.is_relatively_open()
True
is_simplicial()[source]#

Check if self is simplicial.

A cone is called simplicial if primitive vectors along its generating rays form a part of a rational basis of the ambient space.

OUTPUT:

  • True if self is simplicial, False otherwise.

EXAMPLES:

sage: cone1 = Cone([(1,0), (0, 3)])
sage: cone2 = Cone([(1,0), (0, 3), (-1,-1)])
sage: cone1.is_simplicial()
True
sage: cone2.is_simplicial()
False

>>> from sage.all import *
>>> cone1 = Cone([(Integer(1),Integer(0)), (Integer(0), Integer(3))])
>>> cone2 = Cone([(Integer(1),Integer(0)), (Integer(0), Integer(3)), (-Integer(1),-Integer(1))])
>>> cone1.is_simplicial()
True
>>> cone2.is_simplicial()
False
is_smooth()[source]#

Check if self is smooth.

A cone is called smooth if primitive vectors along its generating rays form a part of an integral basis of the ambient space. Equivalently, they generate the whole lattice on the linear subspace spanned by the rays.

OUTPUT:

  • True if self is smooth, False otherwise.

EXAMPLES:

sage: cone1 = Cone([(1,0), (0, 1)])
sage: cone2 = Cone([(1,0), (-1, 3)])
sage: cone1.is_smooth()
True
sage: cone2.is_smooth()
False

>>> from sage.all import *
>>> cone1 = Cone([(Integer(1),Integer(0)), (Integer(0), Integer(1))])
>>> cone2 = Cone([(Integer(1),Integer(0)), (-Integer(1), Integer(3))])
>>> cone1.is_smooth()
True
>>> cone2.is_smooth()
False

The following cones are the same up to a \(SL(2,\ZZ)\) coordinate transformation:

sage: Cone([(1,0,0), (2,1,-1)]).is_smooth()
True
sage: Cone([(1,0,0), (2,1,1)]).is_smooth()
True
sage: Cone([(1,0,0), (2,1,2)]).is_smooth()
True

>>> from sage.all import *
>>> Cone([(Integer(1),Integer(0),Integer(0)), (Integer(2),Integer(1),-Integer(1))]).is_smooth()
True
>>> Cone([(Integer(1),Integer(0),Integer(0)), (Integer(2),Integer(1),Integer(1))]).is_smooth()
True
>>> Cone([(Integer(1),Integer(0),Integer(0)), (Integer(2),Integer(1),Integer(2))]).is_smooth()
True
is_solid()[source]#

Check if this cone is solid.

A cone is said to be solid if it has nonempty interior. That is, if its extreme rays span the entire ambient space.

An alias is is_full_dimensional().

OUTPUT:

True if this cone is solid, and False otherwise.

See also

is_proper()

EXAMPLES:

The nonnegative orthant is always solid:

sage: quadrant = cones.nonnegative_orthant(2)
sage: quadrant.is_solid()
True
sage: octant = Cone([(1,0,0), (0,1,0), (0,0,1)])
sage: octant.is_solid()
True

>>> from sage.all import *
>>> quadrant = cones.nonnegative_orthant(Integer(2))
>>> quadrant.is_solid()
True
>>> octant = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(1))])
>>> octant.is_solid()
True

However, if we embed the two-dimensional nonnegative quadrant into three-dimensional space, then the resulting cone no longer has interior, so it is not solid:

sage: quadrant = Cone([(1,0,0), (0,1,0)])
sage: quadrant.is_solid()
False

>>> from sage.all import *
>>> quadrant = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0))])
>>> quadrant.is_solid()
False
is_strictly_convex()[source]#

Check if self is strictly convex.

A cone is called strictly convex if it does not contain any lines.

OUTPUT:

  • True if self is strictly convex, False otherwise.

EXAMPLES:

sage: cone1 = Cone([(1,0), (0, 1)])
sage: cone2 = Cone([(1,0), (-1, 0)])
sage: cone1.is_strictly_convex()
True
sage: cone2.is_strictly_convex()
False

>>> from sage.all import *
>>> cone1 = Cone([(Integer(1),Integer(0)), (Integer(0), Integer(1))])
>>> cone2 = Cone([(Integer(1),Integer(0)), (-Integer(1), Integer(0))])
>>> cone1.is_strictly_convex()
True
>>> cone2.is_strictly_convex()
False
is_trivial()[source]#

Checks if the cone has no rays.

OUTPUT:

  • True if the cone has no rays, False otherwise.

EXAMPLES:

sage: c0 = cones.trivial(3)
sage: c0.is_trivial()
True
sage: c0.nrays()
0

>>> from sage.all import *
>>> c0 = cones.trivial(Integer(3))
>>> c0.is_trivial()
True
>>> c0.nrays()
0
is_universe()[source]#

Check if this cone is equal to its ambient vector space.

An alias is is_universe().

OUTPUT:

True if this cone equals its entire ambient vector space and False otherwise.

EXAMPLES:

A single ray in two dimensions is not equal to the entire space:

sage: K = Cone([(1,0)])
sage: K.is_full_space()
False

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0))])
>>> K.is_full_space()
False

Neither is the nonnegative orthant:

sage: K = cones.nonnegative_orthant(2)
sage: K.is_full_space()
False

>>> from sage.all import *
>>> K = cones.nonnegative_orthant(Integer(2))
>>> K.is_full_space()
False

The right half-space contains a vector subspace, but it is still not equal to the entire space:

sage: K = Cone([(1,0), (-1,0), (0,1)])
sage: K.is_full_space()
False

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0)), (-Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> K.is_full_space()
False

However, if we allow conic combinations of both axes, then the resulting cone is the entire two-dimensional space:

sage: K = Cone([(1,0), (-1,0), (0,1), (0,-1)])
sage: K.is_full_space()
True

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0)), (-Integer(1),Integer(0)), (Integer(0),Integer(1)), (Integer(0),-Integer(1))])
>>> K.is_full_space()
True
lineality()[source]#

Return the lineality of this cone.

The lineality of a cone is the dimension of the largest linear subspace contained in that cone.

OUTPUT:

A nonnegative integer; the dimension of the largest subspace contained within this cone.

REFERENCES:

EXAMPLES:

The lineality of the nonnegative orthant is zero, since it clearly contains no lines:

sage: K = cones.nonnegative_orthant(3)
sage: K.lineality()
0

>>> from sage.all import *
>>> K = cones.nonnegative_orthant(Integer(3))
>>> K.lineality()
0

However, if we add another ray so that the entire \(x\)-axis belongs to the cone, then the resulting cone will have lineality one:

sage: K = Cone([(1,0,0), (-1,0,0), (0,1,0), (0,0,1)])
sage: K.lineality()
1

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0),Integer(0)), (-Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(1))])
>>> K.lineality()
1

If our cone is all of \(\mathbb{R}^{2}\), then its lineality is equal to the dimension of the ambient space (i.e. two):

sage: K = Cone([(1,0), (-1,0), (0,1), (0,-1)])
sage: K.is_full_space()
True
sage: K.lineality()
2
sage: K.lattice_dim()
2

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0)), (-Integer(1),Integer(0)), (Integer(0),Integer(1)), (Integer(0),-Integer(1))])
>>> K.is_full_space()
True
>>> K.lineality()
2
>>> K.lattice_dim()
2

Per the definition, the lineality of the trivial cone in a trivial space is zero:

sage: K = cones.trivial(0)
sage: K.lineality()
0

>>> from sage.all import *
>>> K = cones.trivial(Integer(0))
>>> K.lineality()
0
linear_subspace()[source]#

Return the largest linear subspace contained inside of self.

OUTPUT:

  • subspace of the ambient space of self.

EXAMPLES:

sage: halfplane = Cone([(1,0), (0,1), (-1,0)])
sage: halfplane.linear_subspace()
Vector space of degree 2 and dimension 1 over Rational Field
Basis matrix:
[1 0]

>>> from sage.all import *
>>> halfplane = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1)), (-Integer(1),Integer(0))])
>>> halfplane.linear_subspace()
Vector space of degree 2 and dimension 1 over Rational Field
Basis matrix:
[1 0]
lines()[source]#

Return lines generating the linear subspace of self.

OUTPUT:

  • tuple of primitive vectors in the lattice of self giving directions of lines that span the linear subspace of self. These lines are arbitrary, but fixed. If you do not care about the order, see also line_set().

EXAMPLES:

sage: halfplane = Cone([(1,0), (0,1), (-1,0)])
sage: halfplane.lines()
N(1, 0)
in 2-d lattice N
sage: fullplane = Cone([(1,0), (0,1), (-1,-1)])
sage: fullplane.lines()
N(0, 1),
N(1, 0)
in 2-d lattice N

>>> from sage.all import *
>>> halfplane = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1)), (-Integer(1),Integer(0))])
>>> halfplane.lines()
N(1, 0)
in 2-d lattice N
>>> fullplane = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1)), (-Integer(1),-Integer(1))])
>>> fullplane.lines()
N(0, 1),
N(1, 0)
in 2-d lattice N
lyapunov_like_basis()[source]#

Compute a basis of Lyapunov-like transformations on this cone.

A linear transformation \(L\) is said to be Lyapunov-like on this cone if \(L(x)\) and \(s\) are orthogonal for every pair \((x,s)\) in its discrete_complementarity_set(). The set of all such transformations forms a vector space, namely the Lie algebra of the automorphism group of this cone.

OUTPUT:

A list of matrices forming a basis for the space of all Lyapunov-like transformations on this cone.

See also

cross_positive_operators_gens(), positive_operators_gens(), Z_operators_gens()

REFERENCES:

EXAMPLES:

Every transformation is Lyapunov-like on the trivial cone:

sage: K = cones.trivial(2)
sage: M = MatrixSpace(K.lattice().base_field(), K.lattice_dim())
sage: list(M.basis()) == K.lyapunov_like_basis()
True

>>> from sage.all import *
>>> K = cones.trivial(Integer(2))
>>> M = MatrixSpace(K.lattice().base_field(), K.lattice_dim())
>>> list(M.basis()) == K.lyapunov_like_basis()
True

And by duality, every transformation is Lyapunov-like on the ambient space:

sage: K = Cone([(1,0), (-1,0), (0,1), (0,-1)])
sage: K.is_full_space()
True
sage: M = MatrixSpace(K.lattice().base_field(), K.lattice_dim())
sage: list(M.basis()) == K.lyapunov_like_basis()
True

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0)), (-Integer(1),Integer(0)), (Integer(0),Integer(1)), (Integer(0),-Integer(1))])
>>> K.is_full_space()
True
>>> M = MatrixSpace(K.lattice().base_field(), K.lattice_dim())
>>> list(M.basis()) == K.lyapunov_like_basis()
True

However, in a trivial space, there are no non-trivial linear maps, so there can be no Lyapunov-like basis:

sage: K = cones.trivial(0)
sage: K.lyapunov_like_basis()
[]

>>> from sage.all import *
>>> K = cones.trivial(Integer(0))
>>> K.lyapunov_like_basis()
[]

The Lyapunov-like transformations on the nonnegative orthant are diagonal matrices:

sage: K = cones.nonnegative_orthant(1)
sage: K.lyapunov_like_basis()
[[1]]

sage: K = cones.nonnegative_orthant(2)
sage: K.lyapunov_like_basis()
[
[1 0]  [0 0]
[0 0], [0 1]
]

sage: K = cones.nonnegative_orthant(3)
sage: K.lyapunov_like_basis()
[
[1 0 0]  [0 0 0]  [0 0 0]
[0 0 0]  [0 1 0]  [0 0 0]
[0 0 0], [0 0 0], [0 0 1]
]

>>> from sage.all import *
>>> K = cones.nonnegative_orthant(Integer(1))
>>> K.lyapunov_like_basis()
[[1]]

>>> K = cones.nonnegative_orthant(Integer(2))
>>> K.lyapunov_like_basis()
[
[1 0]  [0 0]
[0 0], [0 1]
]

>>> K = cones.nonnegative_orthant(Integer(3))
>>> K.lyapunov_like_basis()
[
[1 0 0]  [0 0 0]  [0 0 0]
[0 0 0]  [0 1 0]  [0 0 0]
[0 0 0], [0 0 0], [0 0 1]
]

Only the identity matrix is Lyapunov-like on the pyramids defined by the one- and infinity-norms [RNPA2011]:

sage: l31 = Cone([(1,0,1), (0,-1,1), (-1,0,1), (0,1,1)])
sage: l31.lyapunov_like_basis()
[
[1 0 0]
[0 1 0]
[0 0 1]
]

sage: l3infty = Cone([(0,1,1), (1,0,1), (0,-1,1), (-1,0,1)])
sage: l3infty.lyapunov_like_basis()
[
[1 0 0]
[0 1 0]
[0 0 1]
]

>>> from sage.all import *
>>> l31 = Cone([(Integer(1),Integer(0),Integer(1)), (Integer(0),-Integer(1),Integer(1)), (-Integer(1),Integer(0),Integer(1)), (Integer(0),Integer(1),Integer(1))])
>>> l31.lyapunov_like_basis()
[
[1 0 0]
[0 1 0]
[0 0 1]
]

>>> l3infty = Cone([(Integer(0),Integer(1),Integer(1)), (Integer(1),Integer(0),Integer(1)), (Integer(0),-Integer(1),Integer(1)), (-Integer(1),Integer(0),Integer(1))])
>>> l3infty.lyapunov_like_basis()
[
[1 0 0]
[0 1 0]
[0 0 1]
]
lyapunov_rank()[source]#

Compute the Lyapunov rank of this cone.

The Lyapunov rank of a cone is the dimension of the space of its Lyapunov-like transformations — that is, the length of a lyapunov_like_basis(). Equivalently, the Lyapunov rank is the dimension of the Lie algebra of the automorphism group of the cone.

OUTPUT:

A nonnegative integer representing the Lyapunov rank of this cone.

If the ambient space is trivial, then the Lyapunov rank will be zero. On the other hand, if the dimension of the ambient vector space is \(n > 0\), then the resulting Lyapunov rank will be between \(1\) and \(n^2\) inclusive. If this cone is_proper(), then that upper bound reduces from \(n^2\) to \(n\). A Lyapunov rank of \(n-1\) is not possible (by Lemma 6 [Or2017]) in either case.

ALGORITHM:

Algorithm 3 [Or2017] is used. Every closed convex cone is isomorphic to a Cartesian product of a proper cone, a subspace, and a trivial cone. The Lyapunov ranks of the subspace and trivial cone are easy to compute. Essentially, we “peel off” those easy parts of the cone and compute their Lyapunov ranks separately. We then compute the rank of the proper cone by counting a lyapunov_like_basis() for it. Summing the individual ranks gives the Lyapunov rank of the original cone.

REFERENCES:

EXAMPLES:

The Lyapunov rank of the nonnegative orthant is the same as the dimension of the ambient space [RNPA2011]:

sage: positives = cones.nonnegative_orthant(1)
sage: positives.lyapunov_rank()
1
sage: quadrant = cones.nonnegative_orthant(2)
sage: quadrant.lyapunov_rank()
2
sage: octant = cones.nonnegative_orthant(3)
sage: octant.lyapunov_rank()
3

>>> from sage.all import *
>>> positives = cones.nonnegative_orthant(Integer(1))
>>> positives.lyapunov_rank()
1
>>> quadrant = cones.nonnegative_orthant(Integer(2))
>>> quadrant.lyapunov_rank()
2
>>> octant = cones.nonnegative_orthant(Integer(3))
>>> octant.lyapunov_rank()
3

A vector space of dimension \(n\) has Lyapunov rank \(n^{2}\) [Or2017]:

sage: Q5 = VectorSpace(QQ, 5)
sage: gs = Q5.basis() + [-r for r in Q5.basis()]
sage: K = Cone(gs)
sage: K.lyapunov_rank()
25

>>> from sage.all import *
>>> Q5 = VectorSpace(QQ, Integer(5))
>>> gs = Q5.basis() + [-r for r in Q5.basis()]
>>> K = Cone(gs)
>>> K.lyapunov_rank()
25

A pyramid in three dimensions has Lyapunov rank one [RNPA2011]:

sage: l31 = Cone([(1,0,1), (0,-1,1), (-1,0,1), (0,1,1)])
sage: l31.lyapunov_rank()
1
sage: l3infty = Cone([(0,1,1), (1,0,1), (0,-1,1), (-1,0,1)])
sage: l3infty.lyapunov_rank()
1

>>> from sage.all import *
>>> l31 = Cone([(Integer(1),Integer(0),Integer(1)), (Integer(0),-Integer(1),Integer(1)), (-Integer(1),Integer(0),Integer(1)), (Integer(0),Integer(1),Integer(1))])
>>> l31.lyapunov_rank()
1
>>> l3infty = Cone([(Integer(0),Integer(1),Integer(1)), (Integer(1),Integer(0),Integer(1)), (Integer(0),-Integer(1),Integer(1)), (-Integer(1),Integer(0),Integer(1))])
>>> l3infty.lyapunov_rank()
1

A ray in \(n\) dimensions has Lyapunov rank \(n^{2} - n + 1\) [Or2017]:

sage: K = Cone([(1,0,0,0,0)])
sage: K.lyapunov_rank()
21
sage: K.lattice_dim()**2 - K.lattice_dim() + 1
21

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0),Integer(0),Integer(0),Integer(0))])
>>> K.lyapunov_rank()
21
>>> K.lattice_dim()**Integer(2) - K.lattice_dim() + Integer(1)
21

A subspace of dimension \(m\) in an \(n\)-dimensional ambient space has Lyapunov rank \(n^{2} - m(n - m)\) [Or2017]:

sage: e1 = vector(QQ, [1,0,0,0,0])
sage: e2 = vector(QQ, [0,1,0,0,0])
sage: z = (0,0,0,0,0)
sage: K = Cone([e1, -e1, e2, -e2, z, z, z])
sage: K.lyapunov_rank()
19
sage: K.lattice_dim()**2 - K.dim()*K.codim()
19

>>> from sage.all import *
>>> e1 = vector(QQ, [Integer(1),Integer(0),Integer(0),Integer(0),Integer(0)])
>>> e2 = vector(QQ, [Integer(0),Integer(1),Integer(0),Integer(0),Integer(0)])
>>> z = (Integer(0),Integer(0),Integer(0),Integer(0),Integer(0))
>>> K = Cone([e1, -e1, e2, -e2, z, z, z])
>>> K.lyapunov_rank()
19
>>> K.lattice_dim()**Integer(2) - K.dim()*K.codim()
19

Lyapunov rank is additive on a product of proper cones [RNPA2011]:

sage: l31 = Cone([(1,0,1), (0,-1,1), (-1,0,1), (0,1,1)])
sage: octant = Cone([(1,0,0), (0,1,0), (0,0,1)])
sage: K = l31.cartesian_product(octant)
sage: K.lyapunov_rank()
4
sage: l31.lyapunov_rank() + octant.lyapunov_rank()
4

>>> from sage.all import *
>>> l31 = Cone([(Integer(1),Integer(0),Integer(1)), (Integer(0),-Integer(1),Integer(1)), (-Integer(1),Integer(0),Integer(1)), (Integer(0),Integer(1),Integer(1))])
>>> octant = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(1))])
>>> K = l31.cartesian_product(octant)
>>> K.lyapunov_rank()
4
>>> l31.lyapunov_rank() + octant.lyapunov_rank()
4

Two linearly-isomorphic cones have the same Lyapunov rank [RNPA2011]. A cone linearly-isomorphic to the nonnegative octant will have Lyapunov rank 3:

sage: K = Cone([(1,2,3), (-1,1,0), (1,0,6)])
sage: K.lyapunov_rank()
3

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(2),Integer(3)), (-Integer(1),Integer(1),Integer(0)), (Integer(1),Integer(0),Integer(6))])
>>> K.lyapunov_rank()
3

Lyapunov rank is invariant under dual() [RNPA2011]:

sage: K = Cone([(2,2,4), (-1,9,0), (2,0,6)])
sage: K.lyapunov_rank() == K.dual().lyapunov_rank()
True

>>> from sage.all import *
>>> K = Cone([(Integer(2),Integer(2),Integer(4)), (-Integer(1),Integer(9),Integer(0)), (Integer(2),Integer(0),Integer(6))])
>>> K.lyapunov_rank() == K.dual().lyapunov_rank()
True
max_angle(other=None, exact=True, epsilon=0)[source]#

Return the maximal angle between self and other.

The maximal angle between two closed convex cones is the unique largest angle formed by any two unit-norm vectors in those cones. In pathological cases, this computation can fail.

If it fails when exact is True and if each of the cones is_strictly_convex(), then a second attempt will be made using inexact arithmetic. (This sometimes avoids the problem noted in [Or2024]). If the computation fails when the cones are not strictly convex or when exact is False, a ValueError is raised.

INPUT:

  • other – (default: None) a rational, polyhedral convex cone

  • exact – (default: True) whether or not to use exact rational arithmetic instead of floating point computations; beware that True is not guaranteed to avoid floating point computations if the algorithm runs into trouble in rational arithmetic

  • epsilon – (default: 0) the tolerance to use when making comparisons

Warning

Using inexact arithmetic (exact=False) is faster, but this computation is only known to be stable when both of the cones are strictly convex (or when one of them is the entire space, but the maximal angle is obviously \(\pi\) in that case).

OUTPUT:

A triple \(\left( \theta_{\max}, u, v \right)\) containing:

  • the maximal angle \(\theta_{\max}\) between self and other

  • a vector \(u\) in self that achieves the maximal angle

  • a vector \(v\) in other that achieves the maximal angle

If other is None (the default), then the maximal angle within this cone (between this cone and itself) is returned.

If an eigenspace of dimension greater than one is encountered and if the corresponding angle cannot be ruled out as a maximum, the behavior of this function depends on exact:

  • If exact is True and if both self and other are strictly convex, then the algorithm will fall back to inexact arithmetic. In that case, the returned angle and vectors will be over sage.rings.real_double.RDF.

  • If exact is False or if either cone is not strictly convex, then a ValueError is raised to indicate that we have failed; i.e. we cannot say with certainty what the maximal angle is.

REFERENCES:

ALGORITHM:

Algorithm 3 in [Or2020] is used. If a potentially-maximal angle corresponds to an eigenspace of dimension two or more, we sometimes fall back to inexact arithmetic which has the effect of perturbing the cones. That this will not affect the answer too much is one conclusion of [Or2024].

EXAMPLES:

The maximal angle in a single ray is zero:

sage: K = random_cone(min_rays=1, max_rays=1, max_ambient_dim=5)
sage: K.max_angle()[0]
0

>>> from sage.all import *
>>> K = random_cone(min_rays=Integer(1), max_rays=Integer(1), max_ambient_dim=Integer(5))
>>> K.max_angle()[Integer(0)]
0

The maximal angle in the nonnegative octant is \(\pi/2\):

sage: K = cones.nonnegative_orthant(3)
sage: K.max_angle()[0]
1/2*pi

>>> from sage.all import *
>>> K = cones.nonnegative_orthant(Integer(3))
>>> K.max_angle()[Integer(0)]
1/2*pi

The maximal angle between the nonnegative quintant and the Schur cone of dimension 5 is about \(0.8524 \pi\). The same result can be obtained faster using inexact arithmetic, but only confidently so because we already know the answer:

sage: # long time
sage: P = cones.nonnegative_orthant(5)
sage: Q = cones.schur(5)
sage: actual = P.max_angle(Q)[0]
sage: expected = 0.8524*pi
sage: bool( (actual - expected).abs() < 0.0001 )
True
sage: actual = P.max_angle(Q,exact=False)[0]
sage: bool( (actual - expected).abs() < 0.0001 )
True

>>> from sage.all import *
>>> # long time
>>> P = cones.nonnegative_orthant(Integer(5))
>>> Q = cones.schur(Integer(5))
>>> actual = P.max_angle(Q)[Integer(0)]
>>> expected = RealNumber('0.8524')*pi
>>> bool( (actual - expected).abs() < RealNumber('0.0001') )
True
>>> actual = P.max_angle(Q,exact=False)[Integer(0)]
>>> bool( (actual - expected).abs() < RealNumber('0.0001') )
True

The maximal angle within the Schur cone is known explicitly via Gourion and Seeger’s Proposition 2 [GS2010]:

sage: n = 3
sage: K = cones.schur(n)
sage: bool(K.max_angle()[0] == ((n-1)/n)*pi)
True

>>> from sage.all import *
>>> n = Integer(3)
>>> K = cones.schur(n)
>>> bool(K.max_angle()[Integer(0)] == ((n-Integer(1))/n)*pi)
True

Sage can’t prove that the actual and expected results are equal in the next two cases without a little nudge in the right direction, and, moreover, it’s crashy about it:

sage: n = 4
sage: K = cones.schur(n)
sage: actual = K.max_angle()[0].simplify()._sympy_()._sage_()
sage: expected = ((n-1)/n)*pi
sage: bool( actual == expected )
True
sage: n = 5
sage: K = cones.schur(n)
sage: actual = K.max_angle()[0].simplify()._sympy_()._sage_()
sage: expected = ((n-1)/n)*pi
sage: bool( actual == expected )
True

>>> from sage.all import *
>>> n = Integer(4)
>>> K = cones.schur(n)
>>> actual = K.max_angle()[Integer(0)].simplify()._sympy_()._sage_()
>>> expected = ((n-Integer(1))/n)*pi
>>> bool( actual == expected )
True
>>> n = Integer(5)
>>> K = cones.schur(n)
>>> actual = K.max_angle()[Integer(0)].simplify()._sympy_()._sage_()
>>> expected = ((n-Integer(1))/n)*pi
>>> bool( actual == expected )
True

When there’s a unit norm vector in self whose negation is in other, they form a maximal angle of \(\pi\):

sage: P = Cone([(5,1), (1,-1)])
sage: Q = Cone([(-1,0), (-1,0)])
sage: P.max_angle(Q)[0]
pi

>>> from sage.all import *
>>> P = Cone([(Integer(5),Integer(1)), (Integer(1),-Integer(1))])
>>> Q = Cone([(-Integer(1),Integer(0)), (-Integer(1),Integer(0))])
>>> P.max_angle(Q)[Integer(0)]
pi
orthogonal_sublattice(*args, **kwds)[source]#

The sublattice (in the dual lattice) orthogonal to the sublattice spanned by the cone.

Let \(M=\) self.dual_lattice() be the lattice dual to the ambient lattice of the given cone \(\sigma\). Then, in the notation of [Ful1993], this method returns the sublattice

\[M(\sigma) \stackrel{\text{def}}{=} \sigma^\perp \cap M \subset M\]

INPUT:

  • either nothing or something that can be turned into an element of this lattice.

OUTPUT:

  • if no arguments were given, a toric sublattice, otherwise the corresponding element of it.

EXAMPLES:

sage: c = Cone([(1,1,1), (1,-1,1), (-1,-1,1), (-1,1,1)])
sage: c.orthogonal_sublattice()
Sublattice <>
sage: c12 = Cone([(1,1,1), (1,-1,1)])
sage: c12.sublattice()
Sublattice <N(1, 1, 1), N(0, -1, 0)>
sage: c12.orthogonal_sublattice()
Sublattice <M(1, 0, -1)>

>>> from sage.all import *
>>> c = Cone([(Integer(1),Integer(1),Integer(1)), (Integer(1),-Integer(1),Integer(1)), (-Integer(1),-Integer(1),Integer(1)), (-Integer(1),Integer(1),Integer(1))])
>>> c.orthogonal_sublattice()
Sublattice <>
>>> c12 = Cone([(Integer(1),Integer(1),Integer(1)), (Integer(1),-Integer(1),Integer(1))])
>>> c12.sublattice()
Sublattice <N(1, 1, 1), N(0, -1, 0)>
>>> c12.orthogonal_sublattice()
Sublattice <M(1, 0, -1)>
plot(**options)[source]#

Plot self.

INPUT:

OUTPUT:

  • a plot.

EXAMPLES:

sage: quadrant = Cone([(1,0), (0,1)])
sage: quadrant.plot()                                                       # needs sage.plot sage.symbolic
Graphics object consisting of 9 graphics primitives

>>> from sage.all import *
>>> quadrant = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> quadrant.plot()                                                       # needs sage.plot sage.symbolic
Graphics object consisting of 9 graphics primitives
polyhedron(**kwds)[source]#

Return the polyhedron associated to self.

Mathematically this polyhedron is the same as self.

OUTPUT:

EXAMPLES:

sage: quadrant = Cone([(1,0), (0,1)])
sage: quadrant.polyhedron()
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull
of 1 vertex and 2 rays
sage: line = Cone([(1,0), (-1,0)])
sage: line.polyhedron()
A 1-dimensional polyhedron in ZZ^2 defined as the convex hull
of 1 vertex and 1 line

>>> from sage.all import *
>>> quadrant = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> quadrant.polyhedron()
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull
of 1 vertex and 2 rays
>>> line = Cone([(Integer(1),Integer(0)), (-Integer(1),Integer(0))])
>>> line.polyhedron()
A 1-dimensional polyhedron in ZZ^2 defined as the convex hull
of 1 vertex and 1 line

Here is an example of a trivial cone (see Issue #10237):

sage: origin = Cone([], lattice=ZZ^2)
sage: origin.polyhedron()
A 0-dimensional polyhedron in ZZ^2 defined as the convex hull
of 1 vertex

>>> from sage.all import *
>>> origin = Cone([], lattice=ZZ**Integer(2))
>>> origin.polyhedron()
A 0-dimensional polyhedron in ZZ^2 defined as the convex hull
of 1 vertex
positive_operators_gens(K2=None)[source]#

Compute minimal generators of the positive operators on this cone.

A linear operator on a cone is positive if the image of the cone under the operator is a subset of the cone. This concept can be extended to two cones: the image of the first cone under a positive operator is a subset of the second cone, which may live in a different space.

The positive operators (on one or two fixed cones) themselves form a closed convex cone. This method computes and returns the generators of that cone as a list of matrices.

INPUT:

  • K2 – (default: self) the codomain cone; the image of this cone under the returned generators is a subset of K2.

OUTPUT:

A list of \(m\)-by-\(n\) matrices where \(m\) is the ambient dimension of K2 and \(n\) is the ambient dimension of this cone. Each matrix \(P\) in the list has the property that \(P(x)\) is an element of K2 whenever \(x\) is an element of this cone.

The returned matrices generate the cone of positive operators from this cone to K2; that is,

  • Any nonnegative linear combination of the returned matrices sends elements of this cone to K2.

  • Every positive operator on this cone (with respect to K2) is some nonnegative linear combination of the returned matrices.

ALGORITHM:

Computing positive operators directly is difficult, but computing their dual is straightforward using the generators of Berman and Gaiha. We construct the dual of the positive operators, and then return the dual of that, which is guaranteed to be the desired positive operators because everything is closed, convex, and polyhedral.

See also

cross_positive_operators_gens(), lyapunov_like_basis(), Z_operators_gens()

REFERENCES:

EXAMPLES:

Positive operators on the nonnegative orthant are nonnegative matrices:

sage: K = Cone([(1,)])
sage: K.positive_operators_gens()
[[1]]

sage: K = Cone([(1,0), (0,1)])
sage: K.positive_operators_gens()
[
[1 0]  [0 1]  [0 0]  [0 0]
[0 0], [0 0], [1 0], [0 1]
]

>>> from sage.all import *
>>> K = Cone([(Integer(1),)])
>>> K.positive_operators_gens()
[[1]]

>>> K = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> K.positive_operators_gens()
[
[1 0]  [0 1]  [0 0]  [0 0]
[0 0], [0 0], [1 0], [0 1]
]

The trivial cone in a trivial space has no positive operators:

sage: K = cones.trivial(0)
sage: K.positive_operators_gens()
[]

>>> from sage.all import *
>>> K = cones.trivial(Integer(0))
>>> K.positive_operators_gens()
[]

Every operator is positive on the trivial cone:

sage: K = cones.trivial(1)
sage: K.positive_operators_gens()
[[1], [-1]]

sage: K = cones.trivial(2)
sage: K.is_trivial()
True
sage: K.positive_operators_gens()
[
[1 0]  [-1  0]  [0 1]  [ 0 -1]  [0 0]  [ 0  0]  [0 0]  [ 0  0]
[0 0], [ 0  0], [0 0], [ 0  0], [1 0], [-1  0], [0 1], [ 0 -1]
]

>>> from sage.all import *
>>> K = cones.trivial(Integer(1))
>>> K.positive_operators_gens()
[[1], [-1]]

>>> K = cones.trivial(Integer(2))
>>> K.is_trivial()
True
>>> K.positive_operators_gens()
[
[1 0]  [-1  0]  [0 1]  [ 0 -1]  [0 0]  [ 0  0]  [0 0]  [ 0  0]
[0 0], [ 0  0], [0 0], [ 0  0], [1 0], [-1  0], [0 1], [ 0 -1]
]

Every operator is positive on the ambient vector space:

sage: K = Cone([(1,), (-1,)])
sage: K.is_full_space()
True
sage: K.positive_operators_gens()
[[1], [-1]]

sage: K = Cone([(1,0), (-1,0), (0,1), (0,-1)])
sage: K.is_full_space()
True
sage: K.positive_operators_gens()
[
[1 0]  [-1  0]  [0 1]  [ 0 -1]  [0 0]  [ 0  0]  [0 0]  [ 0  0]
[0 0], [ 0  0], [0 0], [ 0  0], [1 0], [-1  0], [0 1], [ 0 -1]
]

>>> from sage.all import *
>>> K = Cone([(Integer(1),), (-Integer(1),)])
>>> K.is_full_space()
True
>>> K.positive_operators_gens()
[[1], [-1]]

>>> K = Cone([(Integer(1),Integer(0)), (-Integer(1),Integer(0)), (Integer(0),Integer(1)), (Integer(0),-Integer(1))])
>>> K.is_full_space()
True
>>> K.positive_operators_gens()
[
[1 0]  [-1  0]  [0 1]  [ 0 -1]  [0 0]  [ 0  0]  [0 0]  [ 0  0]
[0 0], [ 0  0], [0 0], [ 0  0], [1 0], [-1  0], [0 1], [ 0 -1]
]

A non-obvious application is to find the positive operators on the right half-plane [Or2018b]:

sage: K = Cone([(1,0), (0,1), (0,-1)])
sage: K.positive_operators_gens()
[
[1 0]  [0 0]  [ 0  0]  [0 0]  [ 0  0]
[0 0], [1 0], [-1  0], [0 1], [ 0 -1]
]

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1)), (Integer(0),-Integer(1))])
>>> K.positive_operators_gens()
[
[1 0]  [0 0]  [ 0  0]  [0 0]  [ 0  0]
[0 0], [1 0], [-1  0], [0 1], [ 0 -1]
]
random_element(ring=Integer Ring)[source]#

Return a random element of this cone.

All elements of a convex cone can be represented as a nonnegative linear combination of its generators. A random element is thus constructed by assigning random nonnegative weights to the generators of this cone. By default, these weights are integral and the resulting random element will live in the same lattice as the cone.

The random nonnegative weights are chosen from ring which defaults to ZZ. When ring is not ZZ, the random element returned will be a vector. Only the rings ZZ and QQ are currently supported.

INPUT:

  • ring – (default: ZZ) the ring from which the random generator weights are chosen; either ZZ or QQ.

OUTPUT:

Either a lattice element or vector contained in both this cone and its ambient vector space. If ring is ZZ, a lattice element is returned; otherwise a vector is returned. If ring is neither ZZ nor QQ, then a NotImplementedError is raised.

EXAMPLES:

The trivial element () is always returned in a trivial space:

sage: K = cones.trivial(0)
sage: K.random_element()
N()
sage: K.random_element(ring=QQ)
()

>>> from sage.all import *
>>> K = cones.trivial(Integer(0))
>>> K.random_element()
N()
>>> K.random_element(ring=QQ)
()

A random element of the trivial cone in a nontrivial space is zero:

sage: K = cones.trivial(3)
sage: K.random_element()
N(0, 0, 0)
sage: K.random_element(ring=QQ)
(0, 0, 0)

>>> from sage.all import *
>>> K = cones.trivial(Integer(3))
>>> K.random_element()
N(0, 0, 0)
>>> K.random_element(ring=QQ)
(0, 0, 0)

A random element of the nonnegative orthant should have all components nonnegative:

sage: K = cones.nonnegative_orthant(3)
sage: all(x >= 0 for x in K.random_element())
True
sage: all(x >= 0 for x in K.random_element(ring=QQ))
True

>>> from sage.all import *
>>> K = cones.nonnegative_orthant(Integer(3))
>>> all(x >= Integer(0) for x in K.random_element())
True
>>> all(x >= Integer(0) for x in K.random_element(ring=QQ))
True

If ring is not ZZ or QQ, an error is raised:

sage: K = Cone([(1,0), (0,1)])
sage: K.random_element(ring=RR)
Traceback (most recent call last):
...
NotImplementedError: ring must be either ZZ or QQ.

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> K.random_element(ring=RR)
Traceback (most recent call last):
...
NotImplementedError: ring must be either ZZ or QQ.
relative_interior()[source]#

Return the relative interior of self.

OUTPUT:

EXAMPLES:

sage: c = Cone([(1,0,0), (0,1,0)]); c
2-d cone in 3-d lattice N
sage: c.relative_interior()
Relative interior of 2-d cone in 3-d lattice N

sage: origin = cones.trivial(2); origin
0-d cone in 2-d lattice N
sage: origin.relative_interior() is origin
True

sage: K1 = Cone([(1,0), (-1,0)]); K1
1-d cone in 2-d lattice N
sage: K1.relative_interior() is K1
True

sage: K2 = Cone([(1,0),(-1,0),(0,1),(0,-1)]); K2
2-d cone in 2-d lattice N
sage: K2.relative_interior() is K2
True

>>> from sage.all import *
>>> c = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0))]); c
2-d cone in 3-d lattice N
>>> c.relative_interior()
Relative interior of 2-d cone in 3-d lattice N

>>> origin = cones.trivial(Integer(2)); origin
0-d cone in 2-d lattice N
>>> origin.relative_interior() is origin
True

>>> K1 = Cone([(Integer(1),Integer(0)), (-Integer(1),Integer(0))]); K1
1-d cone in 2-d lattice N
>>> K1.relative_interior() is K1
True

>>> K2 = Cone([(Integer(1),Integer(0)),(-Integer(1),Integer(0)),(Integer(0),Integer(1)),(Integer(0),-Integer(1))]); K2
2-d cone in 2-d lattice N
>>> K2.relative_interior() is K2
True
relative_interior_contains(*args)[source]#

Check if a given point is contained in the relative interior of self.

For a full-dimensional cone the relative interior is simply the interior, so this method will do the same check as interior_contains(). For a strictly lower-dimensional cone, the relative interior is the cone without its facets.

INPUT:

  • anything. An attempt will be made to convert all arguments into a single element of the ambient space of self. If it fails, False will be returned.

OUTPUT:

  • True if the given point is contained in the relative interior of self, False otherwise.

EXAMPLES:

sage: c = Cone([(1,0,0), (0,1,0)])
sage: c.contains((1,1,0))
True
sage: c.relative_interior_contains((1,1,0))
True
sage: c.interior_contains((1,1,0))
False
sage: c.contains((1,0,0))
True
sage: c.relative_interior_contains((1,0,0))
False
sage: c.interior_contains((1,0,0))
False

>>> from sage.all import *
>>> c = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0))])
>>> c.contains((Integer(1),Integer(1),Integer(0)))
True
>>> c.relative_interior_contains((Integer(1),Integer(1),Integer(0)))
True
>>> c.interior_contains((Integer(1),Integer(1),Integer(0)))
False
>>> c.contains((Integer(1),Integer(0),Integer(0)))
True
>>> c.relative_interior_contains((Integer(1),Integer(0),Integer(0)))
False
>>> c.interior_contains((Integer(1),Integer(0),Integer(0)))
False
relative_orthogonal_quotient(supercone)[source]#

The quotient of the dual spanned lattice by the dual of the supercone’s spanned lattice.

In the notation of [Ful1993], if supercone = \(\rho > \sigma\) = self is a cone that contains \(\sigma\) as a face, then \(M(\rho)\) = supercone.orthogonal_sublattice() is a saturated sublattice of \(M(\sigma)\) = self.orthogonal_sublattice(). This method returns the quotient lattice. The lifts of the quotient generators are \(\dim(\rho)-\dim(\sigma)\) linearly independent M-lattice lattice points that, together with \(M(\rho)\), generate \(M(\sigma)\).

OUTPUT:

If we call the output Mrho, then

  • Mrho.cover() == self.orthogonal_sublattice(), and

  • Mrho.relations() == supercone.orthogonal_sublattice().

Note

  • \(M(\sigma) / M(\rho)\) has no torsion since the sublattice \(M(\rho)\) is saturated.

  • In the codimension one case, (a lift of) the generator of \(M(\sigma) / M(\rho)\) is chosen to be positive on \(\sigma\).

EXAMPLES:

sage: # needs sage.graphs
sage: rho = Cone([(1,1,1,3), (1,-1,1,3), (-1,-1,1,3), (-1,1,1,3)])
sage: rho.orthogonal_sublattice()
Sublattice <M(0, 0, 3, -1)>
sage: sigma = rho.facets()[1]
sage: sigma.orthogonal_sublattice()
Sublattice <M(0, 1, 1, 0), M(0, 0, 3, -1)>
sage: sigma.is_face_of(rho)
True
sage: Q = sigma.relative_orthogonal_quotient(rho); Q
1-d lattice, quotient
of Sublattice <M(0, 1, 1, 0), M(0, 0, 3, -1)>
by Sublattice <M(0, 0, 3, -1)>
sage: Q.gens()
(M[0, 1, 1, 0],)

>>> from sage.all import *
>>> # needs sage.graphs
>>> rho = Cone([(Integer(1),Integer(1),Integer(1),Integer(3)), (Integer(1),-Integer(1),Integer(1),Integer(3)), (-Integer(1),-Integer(1),Integer(1),Integer(3)), (-Integer(1),Integer(1),Integer(1),Integer(3))])
>>> rho.orthogonal_sublattice()
Sublattice <M(0, 0, 3, -1)>
>>> sigma = rho.facets()[Integer(1)]
>>> sigma.orthogonal_sublattice()
Sublattice <M(0, 1, 1, 0), M(0, 0, 3, -1)>
>>> sigma.is_face_of(rho)
True
>>> Q = sigma.relative_orthogonal_quotient(rho); Q
1-d lattice, quotient
of Sublattice <M(0, 1, 1, 0), M(0, 0, 3, -1)>
by Sublattice <M(0, 0, 3, -1)>
>>> Q.gens()
(M[0, 1, 1, 0],)

Different codimension:

sage: # needs sage.graphs
sage: rho = Cone([[1,-1,1,3],[-1,-1,1,3]])
sage: sigma = rho.facets()[0]
sage: sigma.orthogonal_sublattice()
Sublattice <M(1, 0, 2, -1), M(0, 1, 1, 0), M(0, 0, 3, -1)>
sage: rho.orthogonal_sublattice()
Sublattice <M(0, 1, 1, 0), M(0, 0, 3, -1)>
sage: sigma.relative_orthogonal_quotient(rho).gens()
(M[-1, 0, -2, 1],)

>>> from sage.all import *
>>> # needs sage.graphs
>>> rho = Cone([[Integer(1),-Integer(1),Integer(1),Integer(3)],[-Integer(1),-Integer(1),Integer(1),Integer(3)]])
>>> sigma = rho.facets()[Integer(0)]
>>> sigma.orthogonal_sublattice()
Sublattice <M(1, 0, 2, -1), M(0, 1, 1, 0), M(0, 0, 3, -1)>
>>> rho.orthogonal_sublattice()
Sublattice <M(0, 1, 1, 0), M(0, 0, 3, -1)>
>>> sigma.relative_orthogonal_quotient(rho).gens()
(M[-1, 0, -2, 1],)

Sign choice in the codimension one case:

sage: sigma1 = Cone([(1, 2, 3), (1, -1, 1), (-1, 1, 1), (-1, -1, 1)])  # 3d
sage: sigma2 = Cone([(1, 1, -1), (1, 2, 3), (1, -1, 1), (1, -1, -1)])  # 3d
sage: rho = sigma1.intersection(sigma2)
sage: rho.relative_orthogonal_quotient(sigma1).gens()
(M[-5, -2, 3],)
sage: rho.relative_orthogonal_quotient(sigma2).gens()
(M[5, 2, -3],)

>>> from sage.all import *
>>> sigma1 = Cone([(Integer(1), Integer(2), Integer(3)), (Integer(1), -Integer(1), Integer(1)), (-Integer(1), Integer(1), Integer(1)), (-Integer(1), -Integer(1), Integer(1))])  # 3d
>>> sigma2 = Cone([(Integer(1), Integer(1), -Integer(1)), (Integer(1), Integer(2), Integer(3)), (Integer(1), -Integer(1), Integer(1)), (Integer(1), -Integer(1), -Integer(1))])  # 3d
>>> rho = sigma1.intersection(sigma2)
>>> rho.relative_orthogonal_quotient(sigma1).gens()
(M[-5, -2, 3],)
>>> rho.relative_orthogonal_quotient(sigma2).gens()
(M[5, 2, -3],)
relative_quotient(subcone)[source]#

The quotient of the spanned lattice by the lattice spanned by a subcone.

In the notation of [Ful1993], let \(N\) be the ambient lattice and \(N_\sigma\) the sublattice spanned by the given cone \(\sigma\). If \(\rho < \sigma\) is a subcone, then \(N_\rho\) = rho.sublattice() is a saturated sublattice of \(N_\sigma\) = self.sublattice(). This method returns the quotient lattice. The lifts of the quotient generators are \(\dim(\sigma)-\dim(\rho)\) linearly independent primitive lattice points that, together with \(N_\rho\), generate \(N_\sigma\).

OUTPUT:

Note

  • The quotient \(N_\sigma / N_\rho\) of spanned sublattices has no torsion since the sublattice \(N_\rho\) is saturated.

  • In the codimension one case, the generator of \(N_\sigma / N_\rho\) is chosen to be in the same direction as the image \(\sigma / N_\rho\)

EXAMPLES:

sage: sigma = Cone([(1,1,1,3),(1,-1,1,3),(-1,-1,1,3),(-1,1,1,3)])
sage: rho   = Cone([(-1, -1, 1, 3), (-1, 1, 1, 3)])
sage: sigma.sublattice()
Sublattice <N(1, 1, 1, 3), N(0, -1, 0, 0), N(-1, -1, 0, 0)>
sage: rho.sublattice()
Sublattice <N(-1, -1, 1, 3), N(0, 1, 0, 0)>
sage: sigma.relative_quotient(rho)
1-d lattice, quotient
of Sublattice <N(1, 1, 1, 3), N(0, -1, 0, 0), N(-1, -1, 0, 0)>
by Sublattice <N(1, 0, -1, -3), N(0, 1, 0, 0)>
sage: sigma.relative_quotient(rho).gens()
(N[1, 0, 0, 0],)

>>> from sage.all import *
>>> sigma = Cone([(Integer(1),Integer(1),Integer(1),Integer(3)),(Integer(1),-Integer(1),Integer(1),Integer(3)),(-Integer(1),-Integer(1),Integer(1),Integer(3)),(-Integer(1),Integer(1),Integer(1),Integer(3))])
>>> rho   = Cone([(-Integer(1), -Integer(1), Integer(1), Integer(3)), (-Integer(1), Integer(1), Integer(1), Integer(3))])
>>> sigma.sublattice()
Sublattice <N(1, 1, 1, 3), N(0, -1, 0, 0), N(-1, -1, 0, 0)>
>>> rho.sublattice()
Sublattice <N(-1, -1, 1, 3), N(0, 1, 0, 0)>
>>> sigma.relative_quotient(rho)
1-d lattice, quotient
of Sublattice <N(1, 1, 1, 3), N(0, -1, 0, 0), N(-1, -1, 0, 0)>
by Sublattice <N(1, 0, -1, -3), N(0, 1, 0, 0)>
>>> sigma.relative_quotient(rho).gens()
(N[1, 0, 0, 0],)

More complicated example:

sage: rho = Cone([(1, 2, 3), (1, -1, 1)])
sage: sigma = Cone([(1, 2, 3), (1, -1, 1), (-1, 1, 1), (-1, -1, 1)])
sage: N_sigma = sigma.sublattice()
sage: N_sigma
Sublattice <N(1, 2, 3), N(1, -1, 1), N(-1, -1, -2)>
sage: N_rho = rho.sublattice()
sage: N_rho
Sublattice <N(1, -1, 1), N(1, 2, 3)>
sage: sigma.relative_quotient(rho).gens()
(N[-1, -1, -2],)
sage: N = rho.lattice()
sage: N_sigma == N.span(N_rho.gens() + tuple(q.lift()
....:            for q in sigma.relative_quotient(rho).gens()))
True

>>> from sage.all import *
>>> rho = Cone([(Integer(1), Integer(2), Integer(3)), (Integer(1), -Integer(1), Integer(1))])
>>> sigma = Cone([(Integer(1), Integer(2), Integer(3)), (Integer(1), -Integer(1), Integer(1)), (-Integer(1), Integer(1), Integer(1)), (-Integer(1), -Integer(1), Integer(1))])
>>> N_sigma = sigma.sublattice()
>>> N_sigma
Sublattice <N(1, 2, 3), N(1, -1, 1), N(-1, -1, -2)>
>>> N_rho = rho.sublattice()
>>> N_rho
Sublattice <N(1, -1, 1), N(1, 2, 3)>
>>> sigma.relative_quotient(rho).gens()
(N[-1, -1, -2],)
>>> N = rho.lattice()
>>> N_sigma == N.span(N_rho.gens() + tuple(q.lift()
...            for q in sigma.relative_quotient(rho).gens()))
True

Sign choice in the codimension one case:

sage: sigma1 = Cone([(1, 2, 3), (1, -1, 1), (-1, 1, 1), (-1, -1, 1)])  # 3d
sage: sigma2 = Cone([(1, 1, -1), (1, 2, 3), (1, -1, 1), (1, -1, -1)])  # 3d
sage: rho = sigma1.intersection(sigma2)
sage: rho.sublattice()
Sublattice <N(1, -1, 1), N(1, 2, 3)>
sage: sigma1.relative_quotient(rho)
1-d lattice, quotient
of Sublattice <N(1, 2, 3), N(1, -1, 1), N(-1, -1, -2)>
by Sublattice <N(1, 2, 3), N(0, 3, 2)>
sage: sigma1.relative_quotient(rho).gens()
(N[-1, -1, -2],)
sage: sigma2.relative_quotient(rho).gens()
(N[0, 2, 1],)

>>> from sage.all import *
>>> sigma1 = Cone([(Integer(1), Integer(2), Integer(3)), (Integer(1), -Integer(1), Integer(1)), (-Integer(1), Integer(1), Integer(1)), (-Integer(1), -Integer(1), Integer(1))])  # 3d
>>> sigma2 = Cone([(Integer(1), Integer(1), -Integer(1)), (Integer(1), Integer(2), Integer(3)), (Integer(1), -Integer(1), Integer(1)), (Integer(1), -Integer(1), -Integer(1))])  # 3d
>>> rho = sigma1.intersection(sigma2)
>>> rho.sublattice()
Sublattice <N(1, -1, 1), N(1, 2, 3)>
>>> sigma1.relative_quotient(rho)
1-d lattice, quotient
of Sublattice <N(1, 2, 3), N(1, -1, 1), N(-1, -1, -2)>
by Sublattice <N(1, 2, 3), N(0, 3, 2)>
>>> sigma1.relative_quotient(rho).gens()
(N[-1, -1, -2],)
>>> sigma2.relative_quotient(rho).gens()
(N[0, 2, 1],)
semigroup_generators()[source]#

Return generators for the semigroup of lattice points of self.

OUTPUT:

  • a PointCollection of lattice points generating the semigroup of lattice points contained in self.

Note

No attempt is made to return a minimal set of generators, see Hilbert_basis() for that.

EXAMPLES:

The following command ensures that the output ordering in the examples below is independent of TOPCOM, you don’t have to use it:

sage: PointConfiguration.set_engine('internal')

>>> from sage.all import *
>>> PointConfiguration.set_engine('internal')

We start with a simple case of a non-smooth 2-dimensional cone:

sage: Cone([(1,0), (1,2)]).semigroup_generators()
N(1, 1),
N(1, 0),
N(1, 2)
in 2-d lattice N

>>> from sage.all import *
>>> Cone([(Integer(1),Integer(0)), (Integer(1),Integer(2))]).semigroup_generators()
N(1, 1),
N(1, 0),
N(1, 2)
in 2-d lattice N

A non-simplicial cone works, too:

sage: cone = Cone([(3,0,-1), (1,-1,0), (0,1,0), (0,0,1)])
sage: sorted(cone.semigroup_generators())
[N(0, 0, 1), N(0, 1, 0), N(1, -1, 0), N(1, 0, 0), N(3, 0, -1)]

>>> from sage.all import *
>>> cone = Cone([(Integer(3),Integer(0),-Integer(1)), (Integer(1),-Integer(1),Integer(0)), (Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(1))])
>>> sorted(cone.semigroup_generators())
[N(0, 0, 1), N(0, 1, 0), N(1, -1, 0), N(1, 0, 0), N(3, 0, -1)]

GAP’s toric package thinks this is challenging:

sage: cone = Cone([[1,2,3,4], [0,1,0,7], [3,1,0,2], [0,0,1,0]]).dual()
sage: len(cone.semigroup_generators())
2806

>>> from sage.all import *
>>> cone = Cone([[Integer(1),Integer(2),Integer(3),Integer(4)], [Integer(0),Integer(1),Integer(0),Integer(7)], [Integer(3),Integer(1),Integer(0),Integer(2)], [Integer(0),Integer(0),Integer(1),Integer(0)]]).dual()
>>> len(cone.semigroup_generators())
2806

The cone need not be strictly convex:

sage: halfplane = Cone([(1,0), (2,1), (-1,0)])
sage: sorted(halfplane.semigroup_generators())
[N(-1, 0), N(0, 1), N(1, 0)]
sage: line = Cone([(1,1,1), (-1,-1,-1)])
sage: sorted(line.semigroup_generators())
[N(-1, -1, -1), N(1, 1, 1)]
sage: wedge = Cone([(1,0,0), (1,2,0), (0,0,1), (0,0,-1)])
sage: sorted(wedge.semigroup_generators())
[N(0, 0, -1), N(0, 0, 1), N(1, 0, 0), N(1, 1, 0), N(1, 2, 0)]

>>> from sage.all import *
>>> halfplane = Cone([(Integer(1),Integer(0)), (Integer(2),Integer(1)), (-Integer(1),Integer(0))])
>>> sorted(halfplane.semigroup_generators())
[N(-1, 0), N(0, 1), N(1, 0)]
>>> line = Cone([(Integer(1),Integer(1),Integer(1)), (-Integer(1),-Integer(1),-Integer(1))])
>>> sorted(line.semigroup_generators())
[N(-1, -1, -1), N(1, 1, 1)]
>>> wedge = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(1),Integer(2),Integer(0)), (Integer(0),Integer(0),Integer(1)), (Integer(0),Integer(0),-Integer(1))])
>>> sorted(wedge.semigroup_generators())
[N(0, 0, -1), N(0, 0, 1), N(1, 0, 0), N(1, 1, 0), N(1, 2, 0)]

Nor does it have to be full-dimensional (see Issue #11312):

sage: Cone([(1,1,0), (-1,1,0)]).semigroup_generators()
N( 0, 1, 0),
N( 1, 1, 0),
N(-1, 1, 0)
in 3-d lattice N

>>> from sage.all import *
>>> Cone([(Integer(1),Integer(1),Integer(0)), (-Integer(1),Integer(1),Integer(0))]).semigroup_generators()
N( 0, 1, 0),
N( 1, 1, 0),
N(-1, 1, 0)
in 3-d lattice N

Neither full-dimensional nor simplicial:

sage: A = matrix([(1, 3, 0), (-1, 0, 1), (1, 1, -2), (15, -2, 0)])
sage: A.elementary_divisors()
[1, 1, 1, 0]
sage: cone3d = Cone([(3,0,-1), (1,-1,0), (0,1,0), (0,0,1)])
sage: rays = (A*vector(v) for v in cone3d.rays())
sage: gens = Cone(rays).semigroup_generators(); sorted(gens)
[N(-2, -1, 0, 17),
 N(0, 1, -2, 0),
 N(1, -1, 1, 15),
 N(3, -4, 5, 45),
 N(3, 0, 1, -2)]
sage: set(map(tuple,gens)) == set(tuple(A*r) for r in cone3d.semigroup_generators())
True

>>> from sage.all import *
>>> A = matrix([(Integer(1), Integer(3), Integer(0)), (-Integer(1), Integer(0), Integer(1)), (Integer(1), Integer(1), -Integer(2)), (Integer(15), -Integer(2), Integer(0))])
>>> A.elementary_divisors()
[1, 1, 1, 0]
>>> cone3d = Cone([(Integer(3),Integer(0),-Integer(1)), (Integer(1),-Integer(1),Integer(0)), (Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(1))])
>>> rays = (A*vector(v) for v in cone3d.rays())
>>> gens = Cone(rays).semigroup_generators(); sorted(gens)
[N(-2, -1, 0, 17),
 N(0, 1, -2, 0),
 N(1, -1, 1, 15),
 N(3, -4, 5, 45),
 N(3, 0, 1, -2)]
>>> set(map(tuple,gens)) == set(tuple(A*r) for r in cone3d.semigroup_generators())
True

ALGORITHM:

If the cone is not simplicial, it is first triangulated. Each simplicial subcone has the integral points of the spaned parallelotope as generators. This is the first step of the primal Normaliz algorithm, see [Normaliz]. For each simplicial cone (of dimension \(d\)), the integral points of the open parallelotope

\[par \langle x_1, \dots, x_d \rangle = \ZZ^n \cap \left\{ q_1 x_1 + \cdots +q_d x_d :~ 0 \leq q_i < 1 \right\}\]

are then computed [BK2001].

Finally, the union of the generators of all simplicial subcones is returned.

solid_restriction()[source]#

Return a solid representation of this cone in terms of a basis of its sublattice().

We define the solid restriction of a cone to be a representation of that cone in a basis of its own sublattice. Since a cone’s sublattice is just large enough to hold the cone (by definition), the resulting solid restriction is_solid(). For convenience, the solid restriction lives in a new lattice (of the appropriate dimension) and not actually in the sublattice object returned by sublattice().

OUTPUT:

A solid cone in a new lattice having the same dimension as this cone’s sublattice().

EXAMPLES:

The nonnegative quadrant in the plane is left after we take its solid restriction in space:

sage: K = Cone([(1,0,0), (0,1,0)])
sage: K.solid_restriction().rays()
N(0, 1),
N(1, 0)
in 2-d lattice N

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0))])
>>> K.solid_restriction().rays()
N(0, 1),
N(1, 0)
in 2-d lattice N

The solid restriction of a single ray has the same representation regardless of the ambient space:

sage: K = Cone([(1,0)])
sage: K.solid_restriction().rays()
N(1)
in 1-d lattice N
sage: K = Cone([(1,1,1)])
sage: K.solid_restriction().rays()
N(1)
in 1-d lattice N

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0))])
>>> K.solid_restriction().rays()
N(1)
in 1-d lattice N
>>> K = Cone([(Integer(1),Integer(1),Integer(1))])
>>> K.solid_restriction().rays()
N(1)
in 1-d lattice N

The solid restriction of the trivial cone lives in a trivial space:

sage: K = cones.trivial(0)
sage: K.solid_restriction()
0-d cone in 0-d lattice N
sage: K = cones.trivial(4)
sage: K.solid_restriction()
0-d cone in 0-d lattice N

>>> from sage.all import *
>>> K = cones.trivial(Integer(0))
>>> K.solid_restriction()
0-d cone in 0-d lattice N
>>> K = cones.trivial(Integer(4))
>>> K.solid_restriction()
0-d cone in 0-d lattice N

The solid restriction of a solid cone is itself:

sage: K = Cone([(1,1),(1,2)])
sage: K.solid_restriction() is K
True

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(1)),(Integer(1),Integer(2))])
>>> K.solid_restriction() is K
True
strict_quotient()[source]#

Return the quotient of self by the linear subspace.

We define the strict quotient of a cone to be the image of this cone in the quotient of the ambient space by the linear subspace of the cone, i.e. it is the “complementary part” to the linear subspace.

OUTPUT:

  • cone.

EXAMPLES:

sage: halfplane = Cone([(1,0), (0,1), (-1,0)])
sage: ssc = halfplane.strict_quotient()
sage: ssc
1-d cone in 1-d lattice N
sage: ssc.rays()
N(1)
in 1-d lattice N
sage: line = Cone([(1,0), (-1,0)])
sage: ssc = line.strict_quotient()
sage: ssc
0-d cone in 1-d lattice N
sage: ssc.rays()
Empty collection
in 1-d lattice N

>>> from sage.all import *
>>> halfplane = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1)), (-Integer(1),Integer(0))])
>>> ssc = halfplane.strict_quotient()
>>> ssc
1-d cone in 1-d lattice N
>>> ssc.rays()
N(1)
in 1-d lattice N
>>> line = Cone([(Integer(1),Integer(0)), (-Integer(1),Integer(0))])
>>> ssc = line.strict_quotient()
>>> ssc
0-d cone in 1-d lattice N
>>> ssc.rays()
Empty collection
in 1-d lattice N

The quotient of the trivial cone is trivial:

sage: K = cones.trivial(0)
sage: K.strict_quotient()
0-d cone in 0-d lattice N
sage: K = Cone([(0,0,0,0)])
sage: K.strict_quotient()
0-d cone in 4-d lattice N

>>> from sage.all import *
>>> K = cones.trivial(Integer(0))
>>> K.strict_quotient()
0-d cone in 0-d lattice N
>>> K = Cone([(Integer(0),Integer(0),Integer(0),Integer(0))])
>>> K.strict_quotient()
0-d cone in 4-d lattice N
sublattice(*args, **kwds)[source]#

The sublattice spanned by the cone.

Let \(\sigma\) be the given cone and \(N=\) self.lattice() the ambient lattice. Then, in the notation of [Ful1993], this method returns the sublattice

\[N_\sigma \stackrel{\text{def}}{=} \mathop{span}( N\cap \sigma )\]

INPUT:

  • either nothing or something that can be turned into an element of this lattice.

OUTPUT:

  • if no arguments were given, a toric sublattice, otherwise the corresponding element of it.

Note

  • The sublattice spanned by the cone is the saturation of the sublattice generated by the rays of the cone.

  • If you only need a \(\QQ\)-basis, you may want to try the basis() method on the result of rays().

  • The returned lattice points are usually not rays of the cone. In fact, for a non-smooth cone the rays do not generate the sublattice \(N_\sigma\), but only a finite index sublattice.

EXAMPLES:

sage: cone = Cone([(1, 1, 1), (1, -1, 1), (-1, -1, 1), (-1, 1, 1)])
sage: cone.rays().basis()
N( 1,  1, 1),
N( 1, -1, 1),
N(-1, -1, 1)
in 3-d lattice N
sage: cone.rays().basis().matrix().det()
-4
sage: cone.sublattice()
Sublattice <N(1, 1, 1), N(0, -1, 0), N(-1, -1, 0)>
sage: matrix( cone.sublattice().gens() ).det()
-1

>>> from sage.all import *
>>> cone = Cone([(Integer(1), Integer(1), Integer(1)), (Integer(1), -Integer(1), Integer(1)), (-Integer(1), -Integer(1), Integer(1)), (-Integer(1), Integer(1), Integer(1))])
>>> cone.rays().basis()
N( 1,  1, 1),
N( 1, -1, 1),
N(-1, -1, 1)
in 3-d lattice N
>>> cone.rays().basis().matrix().det()
-4
>>> cone.sublattice()
Sublattice <N(1, 1, 1), N(0, -1, 0), N(-1, -1, 0)>
>>> matrix( cone.sublattice().gens() ).det()
-1

Another example:

sage: c = Cone([(1,2,3), (4,-5,1)])
sage: c
2-d cone in 3-d lattice N
sage: c.rays()
N(1,  2, 3),
N(4, -5, 1)
in 3-d lattice N
sage: c.sublattice()
Sublattice <N(4, -5, 1), N(1, 2, 3)>
sage: c.sublattice(5, -3, 4)
N(5, -3, 4)
sage: c.sublattice(1, 0, 0)
Traceback (most recent call last):
...
TypeError: element [1, 0, 0] is not in free module

>>> from sage.all import *
>>> c = Cone([(Integer(1),Integer(2),Integer(3)), (Integer(4),-Integer(5),Integer(1))])
>>> c
2-d cone in 3-d lattice N
>>> c.rays()
N(1,  2, 3),
N(4, -5, 1)
in 3-d lattice N
>>> c.sublattice()
Sublattice <N(4, -5, 1), N(1, 2, 3)>
>>> c.sublattice(Integer(5), -Integer(3), Integer(4))
N(5, -3, 4)
>>> c.sublattice(Integer(1), Integer(0), Integer(0))
Traceback (most recent call last):
...
TypeError: element [1, 0, 0] is not in free module
sublattice_complement(*args, **kwds)[source]#

A complement of the sublattice spanned by the cone.

In other words, sublattice() and sublattice_complement() together form a \(\ZZ\)-basis for the ambient lattice().

In the notation of [Ful1993], let \(\sigma\) be the given cone and \(N=\) self.lattice() the ambient lattice. Then this method returns

\[N(\sigma) \stackrel{\text{def}}{=} N / N_\sigma\]

lifted (non-canonically) to a sublattice of \(N\).

INPUT:

  • either nothing or something that can be turned into an element of this lattice.

OUTPUT:

  • if no arguments were given, a toric sublattice, otherwise the corresponding element of it.

EXAMPLES:

sage: C2_Z2 = Cone([(1,0), (1,2)])     # C^2/Z_2
sage: c1, c2 = C2_Z2.facets()                                               # needs sage.graphs
sage: c2.sublattice()                                                       # needs sage.graphs
Sublattice <N(1, 2)>
sage: c2.sublattice_complement()                                            # needs sage.graphs
Sublattice <N(0, 1)>

>>> from sage.all import *
>>> C2_Z2 = Cone([(Integer(1),Integer(0)), (Integer(1),Integer(2))])     # C^2/Z_2
>>> c1, c2 = C2_Z2.facets()                                               # needs sage.graphs
>>> c2.sublattice()                                                       # needs sage.graphs
Sublattice <N(1, 2)>
>>> c2.sublattice_complement()                                            # needs sage.graphs
Sublattice <N(0, 1)>

A more complicated example:

sage: c = Cone([(1,2,3), (4,-5,1)])
sage: c.sublattice()
Sublattice <N(4, -5, 1), N(1, 2, 3)>
sage: c.sublattice_complement()
Sublattice <N(2, -3, 0)>
sage: m = matrix( c.sublattice().gens() + c.sublattice_complement().gens() )
sage: m
[ 4 -5  1]
[ 1  2  3]
[ 2 -3  0]
sage: m.det()
-1

>>> from sage.all import *
>>> c = Cone([(Integer(1),Integer(2),Integer(3)), (Integer(4),-Integer(5),Integer(1))])
>>> c.sublattice()
Sublattice <N(4, -5, 1), N(1, 2, 3)>
>>> c.sublattice_complement()
Sublattice <N(2, -3, 0)>
>>> m = matrix( c.sublattice().gens() + c.sublattice_complement().gens() )
>>> m
[ 4 -5  1]
[ 1  2  3]
[ 2 -3  0]
>>> m.det()
-1
sublattice_quotient(*args, **kwds)[source]#

The quotient of the ambient lattice by the sublattice spanned by the cone.

INPUT:

  • either nothing or something that can be turned into an element of this lattice.

OUTPUT:

EXAMPLES:

sage: # needs sage.graphs
sage: C2_Z2 = Cone([(1,0), (1,2)])     # C^2/Z_2
sage: c1, c2 = C2_Z2.facets()
sage: c2.sublattice_quotient()
1-d lattice, quotient of 2-d lattice N by Sublattice <N(1, 2)>
sage: N = C2_Z2.lattice()
sage: n = N(1,1)
sage: n_bar = c2.sublattice_quotient(n); n_bar
N[1, 1]
sage: n_bar.lift()
N(1, 1)
sage: vector(n_bar)
(-1)

>>> from sage.all import *
>>> # needs sage.graphs
>>> C2_Z2 = Cone([(Integer(1),Integer(0)), (Integer(1),Integer(2))])     # C^2/Z_2
>>> c1, c2 = C2_Z2.facets()
>>> c2.sublattice_quotient()
1-d lattice, quotient of 2-d lattice N by Sublattice <N(1, 2)>
>>> N = C2_Z2.lattice()
>>> n = N(Integer(1),Integer(1))
>>> n_bar = c2.sublattice_quotient(n); n_bar
N[1, 1]
>>> n_bar.lift()
N(1, 1)
>>> vector(n_bar)
(-1)
class sage.geometry.cone.IntegralRayCollection(rays, lattice)[source]#

Bases: SageObject, Hashable, Iterable

Create a collection of integral rays.

Warning

No correctness check or normalization is performed on the input data. This class is designed for internal operations and you probably should not use it directly.

This is a base class for convex rational polyhedral cones and fans.

Ray collections are immutable, but they cache most of the returned values.

INPUT:

  • rays – list of immutable vectors in lattice;

  • lattice – ToricLattice, \(\ZZ^n\), or any other object that behaves like these. If None, it will be determined as parent() of the first ray. Of course, this cannot be done if there are no rays, so in this case you must give an appropriate lattice directly. Note that None is not the default value - you always must give this argument explicitly, even if it is None.

OUTPUT:

  • collection of given integral rays.

ambient_dim()[source]#

Return the dimension of the ambient lattice of self.

An alias is ambient_dim().

OUTPUT:

  • integer.

EXAMPLES:

sage: c = Cone([(1,0)])
sage: c.lattice_dim()
2
sage: c.dim()
1

>>> from sage.all import *
>>> c = Cone([(Integer(1),Integer(0))])
>>> c.lattice_dim()
2
>>> c.dim()
1
ambient_vector_space(base_field=None)[source]#

Return the ambient vector space.

It is the ambient lattice (lattice()) tensored with a field.

INPUT:

  • base_field – (default: the rationals) a field.

EXAMPLES:

sage: c = Cone([(1,0)])
sage: c.ambient_vector_space()
Vector space of dimension 2 over Rational Field
sage: c.ambient_vector_space(AA)                                            # needs sage.rings.number_field
Vector space of dimension 2 over Algebraic Real Field

>>> from sage.all import *
>>> c = Cone([(Integer(1),Integer(0))])
>>> c.ambient_vector_space()
Vector space of dimension 2 over Rational Field
>>> c.ambient_vector_space(AA)                                            # needs sage.rings.number_field
Vector space of dimension 2 over Algebraic Real Field
cartesian_product(other, lattice=None)[source]#

Return the Cartesian product of self with other.

INPUT:

  • other – an IntegralRayCollection;

  • lattice – (optional) the ambient lattice for the result. By default, the direct sum of the ambient lattices of self and other is constructed.

OUTPUT:

By the Cartesian product of ray collections \((r_0, \dots, r_{n-1})\) and \((s_0, \dots, s_{m-1})\) we understand the ray collection of the form \(((r_0, 0), \dots, (r_{n-1}, 0), (0, s_0), \dots, (0, s_{m-1}))\), which is suitable for Cartesian products of cones and fans. The ray order is guaranteed to be as described.

EXAMPLES:

sage: c = Cone([(1,)])
sage: c.cartesian_product(c)    # indirect doctest
2-d cone in 2-d lattice N+N
sage: _.rays()
N+N(1, 0),
N+N(0, 1)
in 2-d lattice N+N

>>> from sage.all import *
>>> c = Cone([(Integer(1),)])
>>> c.cartesian_product(c)    # indirect doctest
2-d cone in 2-d lattice N+N
>>> _.rays()
N+N(1, 0),
N+N(0, 1)
in 2-d lattice N+N
codim()[source]#

Return the codimension of self.

The codimension of a collection of rays (of a cone/fan) is the difference between the dimension of the ambient space and the dimension of the subspace spanned by those rays (of the cone/fan).

OUTPUT:

A nonnegative integer representing the codimension of self.

See also

dim(), lattice_dim()

EXAMPLES:

The codimension of the nonnegative orthant is zero, since the span of its generators equals the entire ambient space:

sage: K = cones.nonnegative_orthant(3)
sage: K.codim()
0

>>> from sage.all import *
>>> K = cones.nonnegative_orthant(Integer(3))
>>> K.codim()
0

However, if we remove a ray so that the entire cone is contained within the \(x\)-\(y\) plane, then the resulting cone will have codimension one, because the \(z\)-axis is perpendicular to every element of the cone:

sage: K = Cone([(1,0,0), (0,1,0)])
sage: K.codim()
1

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0))])
>>> K.codim()
1

If our cone is all of \(\mathbb{R}^{2}\), then its codimension is zero:

sage: K = Cone([(1,0), (-1,0), (0,1), (0,-1)])
sage: K.is_full_space()
True
sage: K.codim()
0

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0)), (-Integer(1),Integer(0)), (Integer(0),Integer(1)), (Integer(0),-Integer(1))])
>>> K.is_full_space()
True
>>> K.codim()
0

And if the cone is trivial in any space, then its codimension is equal to the dimension of the ambient space:

sage: K = cones.trivial(0)
sage: K.lattice_dim()
0
sage: K.codim()
0

sage: K = cones.trivial(1)
sage: K.lattice_dim()
1
sage: K.codim()
1

sage: K = cones.trivial(2)
sage: K.lattice_dim()
2
sage: K.codim()
2

>>> from sage.all import *
>>> K = cones.trivial(Integer(0))
>>> K.lattice_dim()
0
>>> K.codim()
0

>>> K = cones.trivial(Integer(1))
>>> K.lattice_dim()
1
>>> K.codim()
1

>>> K = cones.trivial(Integer(2))
>>> K.lattice_dim()
2
>>> K.codim()
2
codimension()[source]#

Return the codimension of self.

The codimension of a collection of rays (of a cone/fan) is the difference between the dimension of the ambient space and the dimension of the subspace spanned by those rays (of the cone/fan).

OUTPUT:

A nonnegative integer representing the codimension of self.

See also

dim(), lattice_dim()

EXAMPLES:

The codimension of the nonnegative orthant is zero, since the span of its generators equals the entire ambient space:

sage: K = cones.nonnegative_orthant(3)
sage: K.codim()
0

>>> from sage.all import *
>>> K = cones.nonnegative_orthant(Integer(3))
>>> K.codim()
0

However, if we remove a ray so that the entire cone is contained within the \(x\)-\(y\) plane, then the resulting cone will have codimension one, because the \(z\)-axis is perpendicular to every element of the cone:

sage: K = Cone([(1,0,0), (0,1,0)])
sage: K.codim()
1

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0))])
>>> K.codim()
1

If our cone is all of \(\mathbb{R}^{2}\), then its codimension is zero:

sage: K = Cone([(1,0), (-1,0), (0,1), (0,-1)])
sage: K.is_full_space()
True
sage: K.codim()
0

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0)), (-Integer(1),Integer(0)), (Integer(0),Integer(1)), (Integer(0),-Integer(1))])
>>> K.is_full_space()
True
>>> K.codim()
0

And if the cone is trivial in any space, then its codimension is equal to the dimension of the ambient space:

sage: K = cones.trivial(0)
sage: K.lattice_dim()
0
sage: K.codim()
0

sage: K = cones.trivial(1)
sage: K.lattice_dim()
1
sage: K.codim()
1

sage: K = cones.trivial(2)
sage: K.lattice_dim()
2
sage: K.codim()
2

>>> from sage.all import *
>>> K = cones.trivial(Integer(0))
>>> K.lattice_dim()
0
>>> K.codim()
0

>>> K = cones.trivial(Integer(1))
>>> K.lattice_dim()
1
>>> K.codim()
1

>>> K = cones.trivial(Integer(2))
>>> K.lattice_dim()
2
>>> K.codim()
2
dim()[source]#

Return the dimension of the subspace spanned by rays of self.

OUTPUT:

  • integer.

EXAMPLES:

sage: c = Cone([(1,0)])
sage: c.lattice_dim()
2
sage: c.dim()
1

>>> from sage.all import *
>>> c = Cone([(Integer(1),Integer(0))])
>>> c.lattice_dim()
2
>>> c.dim()
1
dual_lattice()[source]#

Return the dual of the ambient lattice of self.

OUTPUT:

  • lattice. If possible (that is, if lattice() has a dual() method), the dual lattice is returned. Otherwise, \(\ZZ^n\) is returned, where \(n\) is the dimension of lattice().

EXAMPLES:

sage: c = Cone([(1,0)])
sage: c.dual_lattice()
2-d lattice M
sage: Cone([], ZZ^3).dual_lattice()
Ambient free module of rank 3
over the principal ideal domain Integer Ring

>>> from sage.all import *
>>> c = Cone([(Integer(1),Integer(0))])
>>> c.dual_lattice()
2-d lattice M
>>> Cone([], ZZ**Integer(3)).dual_lattice()
Ambient free module of rank 3
over the principal ideal domain Integer Ring
lattice()[source]#

Return the ambient lattice of self.

OUTPUT:

  • lattice.

EXAMPLES:

sage: c = Cone([(1,0)])
sage: c.lattice()
2-d lattice N
sage: Cone([], ZZ^3).lattice()
Ambient free module of rank 3
over the principal ideal domain Integer Ring

>>> from sage.all import *
>>> c = Cone([(Integer(1),Integer(0))])
>>> c.lattice()
2-d lattice N
>>> Cone([], ZZ**Integer(3)).lattice()
Ambient free module of rank 3
over the principal ideal domain Integer Ring
lattice_dim()[source]#

Return the dimension of the ambient lattice of self.

An alias is ambient_dim().

OUTPUT:

  • integer.

EXAMPLES:

sage: c = Cone([(1,0)])
sage: c.lattice_dim()
2
sage: c.dim()
1

>>> from sage.all import *
>>> c = Cone([(Integer(1),Integer(0))])
>>> c.lattice_dim()
2
>>> c.dim()
1
nrays()[source]#

Return the number of rays of self.

OUTPUT:

  • integer.

EXAMPLES:

sage: c = Cone([(1,0), (0,1)])
sage: c.nrays()
2

>>> from sage.all import *
>>> c = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> c.nrays()
2
plot(**options)[source]#

Plot self.

INPUT:

OUTPUT:

  • a plot.

EXAMPLES:

sage: quadrant = Cone([(1,0), (0,1)])
sage: quadrant.plot()                                                       # needs sage.plot sage.symbolic
Graphics object consisting of 9 graphics primitives

>>> from sage.all import *
>>> quadrant = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> quadrant.plot()                                                       # needs sage.plot sage.symbolic
Graphics object consisting of 9 graphics primitives
ray(n)[source]#

Return the n-th ray of self.

INPUT:

  • n – integer, an index of a ray of self. Enumeration of rays starts with zero.

OUTPUT:

  • ray, an element of the lattice of self.

EXAMPLES:

sage: c = Cone([(1,0), (0,1)])
sage: c.ray(0)
N(1, 0)

>>> from sage.all import *
>>> c = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> c.ray(Integer(0))
N(1, 0)
rays(*args)[source]#

Return (some of the) rays of self.

INPUT:

  • ray_list – a list of integers, the indices of the requested rays. If not specified, all rays of self will be returned.

OUTPUT:

EXAMPLES:

sage: c = Cone([(1,0), (0,1), (-1, 0)])
sage: c.rays()
N( 0, 1),
N( 1, 0),
N(-1, 0)
in 2-d lattice N
sage: c.rays([0, 2])
N( 0, 1),
N(-1, 0)
in 2-d lattice N

>>> from sage.all import *
>>> c = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1)), (-Integer(1), Integer(0))])
>>> c.rays()
N( 0, 1),
N( 1, 0),
N(-1, 0)
in 2-d lattice N
>>> c.rays([Integer(0), Integer(2)])
N( 0, 1),
N(-1, 0)
in 2-d lattice N

You can also give ray indices directly, without packing them into a list:

sage: c.rays(0, 2)
N( 0, 1),
N(-1, 0)
in 2-d lattice N

>>> from sage.all import *
>>> c.rays(Integer(0), Integer(2))
N( 0, 1),
N(-1, 0)
in 2-d lattice N
span(base_ring=None)[source]#

Return the span of self.

INPUT:

  • base_ring – (default: from lattice) the base ring to use

    for the generated module.

OUTPUT:

A module spanned by the generators of self.

EXAMPLES:

The span of a single ray is a one-dimensional sublattice:

sage: K1 = Cone([(1,)])
sage: K1.span()
Sublattice <N(1)>
sage: K2 = Cone([(1,0)])
sage: K2.span()
Sublattice <N(1, 0)>

>>> from sage.all import *
>>> K1 = Cone([(Integer(1),)])
>>> K1.span()
Sublattice <N(1)>
>>> K2 = Cone([(Integer(1),Integer(0))])
>>> K2.span()
Sublattice <N(1, 0)>

The span of the nonnegative orthant is the entire ambient lattice:

sage: K = cones.nonnegative_orthant(3)
sage: K.span() == K.lattice()
True

>>> from sage.all import *
>>> K = cones.nonnegative_orthant(Integer(3))
>>> K.span() == K.lattice()
True

By specifying a base_ring, we can obtain a vector space:

sage: K = Cone([(1,0,0),(0,1,0),(0,0,1)])
sage: K.span(base_ring=QQ)
Vector space of degree 3 and dimension 3 over Rational Field
Basis matrix:
[1 0 0]
[0 1 0]
[0 0 1]

>>> from sage.all import *
>>> K = Cone([(Integer(1),Integer(0),Integer(0)),(Integer(0),Integer(1),Integer(0)),(Integer(0),Integer(0),Integer(1))])
>>> K.span(base_ring=QQ)
Vector space of degree 3 and dimension 3 over Rational Field
Basis matrix:
[1 0 0]
[0 1 0]
[0 0 1]
sage.geometry.cone.classify_cone_2d(ray0, ray1, check=True)[source]#

Return \((d,k)\) classifying the lattice cone spanned by the two rays.

INPUT:

  • ray0, ray1 – two primitive integer vectors. The generators of the two rays generating the two-dimensional cone.

  • check – boolean (default: True). Whether to check the input rays for consistency.

OUTPUT:

A pair \((d,k)\) of integers classifying the cone up to \(GL(2, \ZZ)\) equivalence. See Proposition 10.1.1 of [CLS2011] for the definition. We return the unique \((d,k)\) with minimal \(k\), see Proposition 10.1.3 of [CLS2011].

EXAMPLES:

sage: ray0 = vector([1,0])
sage: ray1 = vector([2,3])
sage: from sage.geometry.cone import classify_cone_2d
sage: classify_cone_2d(ray0, ray1)
(3, 2)

sage: ray0 = vector([2,4,5])
sage: ray1 = vector([5,19,11])
sage: classify_cone_2d(ray0, ray1)
(3, 1)

sage: m = matrix(ZZ, [(19, -14, -115), (-2, 5, 25), (43, -42, -298)])
sage: m.det()   # check that it is in GL(3,ZZ)
-1
sage: classify_cone_2d(m*ray0, m*ray1)
(3, 1)

>>> from sage.all import *
>>> ray0 = vector([Integer(1),Integer(0)])
>>> ray1 = vector([Integer(2),Integer(3)])
>>> from sage.geometry.cone import classify_cone_2d
>>> classify_cone_2d(ray0, ray1)
(3, 2)

>>> ray0 = vector([Integer(2),Integer(4),Integer(5)])
>>> ray1 = vector([Integer(5),Integer(19),Integer(11)])
>>> classify_cone_2d(ray0, ray1)
(3, 1)

>>> m = matrix(ZZ, [(Integer(19), -Integer(14), -Integer(115)), (-Integer(2), Integer(5), Integer(25)), (Integer(43), -Integer(42), -Integer(298))])
>>> m.det()   # check that it is in GL(3,ZZ)
-1
>>> classify_cone_2d(m*ray0, m*ray1)
(3, 1)
sage.geometry.cone.integral_length(v)[source]#

Compute the integral length of a given rational vector.

INPUT:

  • v – any object which can be converted to a list of rationals

OUTPUT:

Rational number \(r`\) such that v = r * u, where u is the primitive integral vector in the direction of v.

EXAMPLES:

sage: from sage.geometry.cone import integral_length
sage: integral_length([1, 2, 4])
1
sage: integral_length([2, 2, 4])
2
sage: integral_length([2/3, 2, 4])
2/3

>>> from sage.all import *
>>> from sage.geometry.cone import integral_length
>>> integral_length([Integer(1), Integer(2), Integer(4)])
1
>>> integral_length([Integer(2), Integer(2), Integer(4)])
2
>>> integral_length([Integer(2)/Integer(3), Integer(2), Integer(4)])
2/3
sage.geometry.cone.is_Cone(x)[source]#

Check if x is a cone.

INPUT:

  • x – anything.

OUTPUT:

  • True if x is a cone and False otherwise.

EXAMPLES:

sage: from sage.geometry.cone import is_Cone
sage: is_Cone(1)
doctest:warning...
DeprecationWarning: is_Cone is deprecated, use isinstance instead
See https://github.com/sagemath/sage/issues/34307 for details.
False
sage: quadrant = Cone([(1,0), (0,1)])
sage: quadrant
2-d cone in 2-d lattice N
sage: is_Cone(quadrant)
True

>>> from sage.all import *
>>> from sage.geometry.cone import is_Cone
>>> is_Cone(Integer(1))
doctest:warning...
DeprecationWarning: is_Cone is deprecated, use isinstance instead
See https://github.com/sagemath/sage/issues/34307 for details.
False
>>> quadrant = Cone([(Integer(1),Integer(0)), (Integer(0),Integer(1))])
>>> quadrant
2-d cone in 2-d lattice N
>>> is_Cone(quadrant)
True
sage.geometry.cone.normalize_rays(rays, lattice)[source]#

Normalize a list of rational rays: make them primitive and immutable.

INPUT:

  • rays – list of rays which can be converted to the rational extension of lattice;

  • lattice – ToricLattice, \(\ZZ^n\), or any other object that behaves like these. If None, an attempt will be made to determine an appropriate toric lattice automatically.

OUTPUT:

  • list of immutable primitive vectors of the lattice in the same directions as original rays.

EXAMPLES:

sage: from sage.geometry.cone import normalize_rays
sage: normalize_rays([(0, 1), (0, 2), (3, 2), (5/7, 10/3)], None)
[N(0, 1), N(0, 1), N(3, 2), N(3, 14)]
sage: L = ToricLattice(2, "L")
sage: normalize_rays([(0, 1), (0, 2), (3, 2), (5/7, 10/3)], L.dual())
[L*(0, 1), L*(0, 1), L*(3, 2), L*(3, 14)]
sage: ray_in_L = L(0,1)
sage: normalize_rays([ray_in_L, (0, 2), (3, 2), (5/7, 10/3)], None)
[L(0, 1), L(0, 1), L(3, 2), L(3, 14)]
sage: normalize_rays([(0, 1), (0, 2), (3, 2), (5/7, 10/3)], ZZ^2)
[(0, 1), (0, 1), (3, 2), (3, 14)]
sage: normalize_rays([(0, 1), (0, 2), (3, 2), (5/7, 10/3)], ZZ^3)
Traceback (most recent call last):
...
TypeError: cannot convert (0, 1) to
Vector space of dimension 3 over Rational Field!
sage: normalize_rays([], ZZ^3)
[]

>>> from sage.all import *
>>> from sage.geometry.cone import normalize_rays
>>> normalize_rays([(Integer(0), Integer(1)), (Integer(0), Integer(2)), (Integer(3), Integer(2)), (Integer(5)/Integer(7), Integer(10)/Integer(3))], None)
[N(0, 1), N(0, 1), N(3, 2), N(3, 14)]
>>> L = ToricLattice(Integer(2), "L")
>>> normalize_rays([(Integer(0), Integer(1)), (Integer(0), Integer(2)), (Integer(3), Integer(2)), (Integer(5)/Integer(7), Integer(10)/Integer(3))], L.dual())
[L*(0, 1), L*(0, 1), L*(3, 2), L*(3, 14)]
>>> ray_in_L = L(Integer(0),Integer(1))
>>> normalize_rays([ray_in_L, (Integer(0), Integer(2)), (Integer(3), Integer(2)), (Integer(5)/Integer(7), Integer(10)/Integer(3))], None)
[L(0, 1), L(0, 1), L(3, 2), L(3, 14)]
>>> normalize_rays([(Integer(0), Integer(1)), (Integer(0), Integer(2)), (Integer(3), Integer(2)), (Integer(5)/Integer(7), Integer(10)/Integer(3))], ZZ**Integer(2))
[(0, 1), (0, 1), (3, 2), (3, 14)]
>>> normalize_rays([(Integer(0), Integer(1)), (Integer(0), Integer(2)), (Integer(3), Integer(2)), (Integer(5)/Integer(7), Integer(10)/Integer(3))], ZZ**Integer(3))
Traceback (most recent call last):
...
TypeError: cannot convert (0, 1) to
Vector space of dimension 3 over Rational Field!
>>> normalize_rays([], ZZ**Integer(3))
[]
sage.geometry.cone.random_cone(lattice=None, min_ambient_dim=0, max_ambient_dim=None, min_rays=0, max_rays=None, strictly_convex=None, solid=None)[source]#

Generate a random convex rational polyhedral cone.

Lower and upper bounds may be provided for both the dimension of the ambient space and the number of generating rays of the cone. If a lower bound is left unspecified, it defaults to zero. Unspecified upper bounds will be chosen randomly, unless you set solid, in which case they are chosen a little more wisely.

You may specify the ambient lattice for the returned cone. In that case, the min_ambient_dim and max_ambient_dim parameters are ignored.

You may also request that the returned cone be strictly convex (or not). Likewise you may request that it be (non-)solid.

Warning

If you request a large number of rays in a low-dimensional space, you might be waiting for a while. For example, in three dimensions, it is possible to obtain an octagon raised up to height one (all z-coordinates equal to one). But in practice, we usually generate the entire three-dimensional space with six rays before we get to the eight rays needed for an octagon. We therefore have to throw the cone out and start over from scratch. This process repeats until we get lucky.

We also refrain from “adjusting” the min/max parameters given to us when a (non-)strictly convex or (non-)solid cone is requested. This means that it may take a long time to generate such a cone if the parameters are chosen unwisely.

For example, you may want to set min_rays close to min_ambient_dim if you desire a solid cone. Or, if you desire a non-strictly-convex cone, then they all contain at least two generating rays. So that might be a good candidate for min_rays.

INPUT:

  • lattice (default: random) – A ToricLattice object in which the returned cone will live. By default a new lattice will be constructed with a randomly-chosen rank (subject to min_ambient_dim and max_ambient_dim).

  • min_ambient_dim (default: zero) – A nonnegative integer representing the minimum dimension of the ambient lattice.

  • max_ambient_dim (default: random) – A nonnegative integer representing the maximum dimension of the ambient lattice.

  • min_rays (default: zero) – A nonnegative integer representing the minimum number of generating rays of the cone.

  • max_rays (default: random) – A nonnegative integer representing the maximum number of generating rays of the cone.

  • strictly_convex (default: random) – Whether or not to make the returned cone strictly convex. Specify True for a strictly convex cone, False for a non-strictly-convex cone, or None if you don’t care.

  • solid (default: random) – Whether or not to make the returned cone solid. Specify True for a solid cone, False for a non-solid cone, or None if you don’t care.

OUTPUT:

A new, randomly generated cone.

A ValueError will be thrown under the following conditions:

  • Any of min_ambient_dim, max_ambient_dim, min_rays, or max_rays are negative.

  • max_ambient_dim is less than min_ambient_dim.

  • max_rays is less than min_rays.

  • Both max_ambient_dim and lattice are specified.

  • min_rays is greater than four but max_ambient_dim is less than three.

  • min_rays is greater than four but lattice has dimension less than three.

  • min_rays is greater than two but max_ambient_dim is less than two.

  • min_rays is greater than two but lattice has dimension less than two.

  • min_rays is positive but max_ambient_dim is zero.

  • min_rays is positive but lattice has dimension zero.

  • A trivial lattice is supplied and a non-strictly-convex cone is requested.

  • A non-strictly-convex cone is requested but max_rays is less than two.

  • A solid cone is requested but max_rays is less than min_ambient_dim.

  • A solid cone is requested but max_rays is less than the dimension of lattice.

  • A non-solid cone is requested but max_ambient_dim is zero.

  • A non-solid cone is requested but lattice has dimension zero.

  • A non-solid cone is requested but min_rays is so large that it guarantees a solid cone.

ALGORITHM:

First, a lattice is determined from min_ambient_dim and max_ambient_dim (or from the supplied lattice).

Then, lattice elements are generated one at a time and added to a cone. This continues until either the cone meets the user’s requirements, or the cone is equal to the entire space (at which point it is futile to generate more).

We check whether or not the resulting cone meets the user’s requirements; if it does, it is returned. If not, we throw it away and start over. This process repeats indefinitely until an appropriate cone is generated.

EXAMPLES:

Generate a trivial cone in a trivial space:

sage: random_cone(max_ambient_dim=0, max_rays=0)
0-d cone in 0-d lattice N

>>> from sage.all import *
>>> random_cone(max_ambient_dim=Integer(0), max_rays=Integer(0))
0-d cone in 0-d lattice N

We can predict the ambient dimension when min_ambient_dim == max_ambient_dim:

sage: K = random_cone(min_ambient_dim=4, max_ambient_dim=4)
sage: K.lattice_dim()
4

>>> from sage.all import *
>>> K = random_cone(min_ambient_dim=Integer(4), max_ambient_dim=Integer(4))
>>> K.lattice_dim()
4

Likewise for the number of rays when min_rays == max_rays:

sage: K = random_cone(min_rays=3, max_rays=3)
sage: K.nrays()
3

>>> from sage.all import *
>>> K = random_cone(min_rays=Integer(3), max_rays=Integer(3))
>>> K.nrays()
3

If we specify a lattice, then the returned cone will live in it:

sage: L = ToricLattice(5, "L")
sage: K = random_cone(lattice=L)
sage: K.lattice() is L
True

>>> from sage.all import *
>>> L = ToricLattice(Integer(5), "L")
>>> K = random_cone(lattice=L)
>>> K.lattice() is L
True

We can also request a strictly convex cone:

sage: K = random_cone(max_ambient_dim=8, max_rays=10,
....:                 strictly_convex=True)
sage: K.is_strictly_convex()
True

>>> from sage.all import *
>>> K = random_cone(max_ambient_dim=Integer(8), max_rays=Integer(10),
...                 strictly_convex=True)
>>> K.is_strictly_convex()
True

Or one that isn’t strictly convex:

sage: K = random_cone(min_ambient_dim=5, min_rays=2,
....:                 strictly_convex=False)
sage: K.is_strictly_convex()
False

>>> from sage.all import *
>>> K = random_cone(min_ambient_dim=Integer(5), min_rays=Integer(2),
...                 strictly_convex=False)
>>> K.is_strictly_convex()
False

An example with all parameters set:

sage: K = random_cone(min_ambient_dim=4, max_ambient_dim=7,
....:                 min_rays=2, max_rays=10,
....:                 strictly_convex=False, solid=True)
sage: 4 <= K.lattice_dim() and K.lattice_dim() <= 7
True
sage: 2 <= K.nrays() and K.nrays() <= 10
True
sage: K.is_strictly_convex()
False
sage: K.is_solid()
True

>>> from sage.all import *
>>> K = random_cone(min_ambient_dim=Integer(4), max_ambient_dim=Integer(7),
...                 min_rays=Integer(2), max_rays=Integer(10),
...                 strictly_convex=False, solid=True)
>>> Integer(4) <= K.lattice_dim() and K.lattice_dim() <= Integer(7)
True
>>> Integer(2) <= K.nrays() and K.nrays() <= Integer(10)
True
>>> K.is_strictly_convex()
False
>>> K.is_solid()
True