Polyhedral Fans

Introduction

Let $\mathbb{F}$ be an ordered field; the default is that $\mathbb{F}=\mathbb{Q}$ is the field of rational numbers and other fields are not yet supported everywhere in the implementation.

A nonempty finite collection $\mathcal{F}$ of (polyhedral) cones in $\mathbb{F}^n$, for $n$ fixed, is a (polyhedral) fan if

the set $\mathcal{F}$ is closed with respect to taking faces and
if $C,D\in\mathcal{F}$ then $C\cap D$ is a face of both, $C$ and $D$.

Auxiliary functions

ambient_dim — Method

ambient_dim(PF::PolyhedralFan)

Return the ambient dimension PF, which is the dimension of the embedding space.

This is equal to the dimension of the fan if and only if the fan is full-dimensional.

Examples

The normal fan of the 4-cube is embedded in the same ambient space.

julia> ambient_dim(normal_fan(cube(4)))
4

source

ambient_dim(TropV::TropicalVariety)

See ambient_dim(::PolyhedralComplex).

source

arrangement_polynomial — Function

arrangement_polynomial([ring::MPolyRing{<: FieldElem},] A::MatElem{<: FieldElem})

Given some $A\in\mathbb{F}^{n\times d},$ return the product of the linear forms corresponding to the rows.

Let $A$ be a $n\times d$ matrix with entries from a field $\mathbb{F}$. The rows of $A$ are the normal vectors for a hyperplane arrangement $\mathcal{A} = \{H_{1},\dots,H_{n}:H_{i}\subset \mathbb{F}^{d}\}.$ We have $H_{i} = V(\alpha_{i})$, where $\alpha_{i}\in\mathbb{F}[x_{1},\dots,x_{d}]$ is a linear form whose coefficients are the entries of the $i$th row.

Then we have $\cup_{H_{i}\in\mathcal{A}}H_{i} = V(\Pi^{n}_{i=1}\alpha_{i}).$

Optionally one can select to use columns instead of rows in the following way:

arrangement_polynomial(...  ; hyperplanes=:in_cols)

Example using standard ring and then custom ring.

julia> A = matrix(QQ,[1 2 5//2; 0 0 1; 2 3 2; 1//2 3 5; 3 1 2; 7 8 1])
[   1   2   5//2]
[   0   0      1]
[   2   3      2]
[1//2   3      5]
[   3   1      2]
[   7   8      1]

julia> factor(arrangement_polynomial(A))
(1//4) * (2*x1 + 3*x2 + 2*x3) * (7*x1 + 8*x2 + x3) * (x1 + 6*x2 + 10*x3) * (2*x1 + 4*x2 + 5*x3) * x3 * (3*x1 + x2 + 2*x3)

julia> R,_ = polynomial_ring(QQ, [:x, :y, :z])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])

julia> factor(arrangement_polynomial(R, A))
(1//4) * (2*x + 3*y + 2*z) * (7*x + 8*y + z) * (x + 6*y + 10*z) * (2*x + 4*y + 5*z) * z * (3*x + y + 2*z)

To use the columns instead, proceed in the following way:

julia> A = matrix(QQ,[1 0 2 1//2 3 7;2 0 3 3 1 8;5//2 1 2 5 2 1]);

julia> factor(arrangement_polynomial(A; hyperplanes=:in_cols))
(1//4) * (2*x1 + 3*x2 + 2*x3) * (7*x1 + 8*x2 + x3) * (x1 + 6*x2 + 10*x3) * (2*x1 + 4*x2 + 5*x3) * x3 * (3*x1 + x2 + 2*x3)

source

dim — Method

dim(PF::PolyhedralFan)

Return the dimension of PF.

Examples

This fan in the plane contains a 2-dimensional cone and is thus 2-dimensional itself.

julia> PF = polyhedral_fan(incidence_matrix([[1, 2], [3]]), [1 0; 0 1; -1 -1]);

julia> dim(PF)
2

source

f_vector — Method

f_vector(PF::PolyhedralFan)

Compute the vector $(f₁,f₂,...,f_{dim(PF)-1})$ where $f_i$ is the number of faces of $PF$ of dimension $i$.

Examples

The f-vector of the normal fan of a polytope is the reverse of the f-vector of the polytope.

julia> c = cube(3)
Polytope in ambient dimension 3

julia> f_vector(c)
3-element Vector{ZZRingElem}:
 8
 12
 6


julia> nfc = normal_fan(c)
Polyhedral fan in ambient dimension 3

julia> f_vector(nfc)
3-element Vector{ZZRingElem}:
 6
 12
 8

source

is_complete — Method

is_complete(PF::PolyhedralFan)

Determine whether PF is complete, i.e. its support, the set-theoretic union of its cones, covers the whole space.

Examples

Normal fans of polytopes are complete.

julia> is_complete(normal_fan(cube(3)))
true

source

is_pointed — Method

is_pointed(PF::PolyhedralFan)

Determine whether PF is pointed, i.e. all its cones are pointed.

Examples

The normal fan of a non-fulldimensional polytope is not pointed.

julia> C = convex_hull([0 0; 1 0])
Polyhedron in ambient dimension 2

julia> is_fulldimensional(C)
false

julia> nf = normal_fan(C)
Polyhedral fan in ambient dimension 2

julia> is_pointed(nf)
false

julia> lineality_dim(nf)
1

source

is_regular — Method

is_regular(PF::PolyhedralFan)

Determine whether PF is regular, i.e. the normal fan of a polytope.

Examples

This fan is not complete and thus not regular.

julia> PF = polyhedral_fan(incidence_matrix([[1, 2], [3]]), [1 0; 0 1; -1 -1]);

julia> is_regular(PF)
false

source

is_simplicial — Method

is_simplicial(PF::PolyhedralFan)

Determine whether PF is simplicial, i.e. every cone should be generated by a basis of the ambient space.

Examples

The normal_fan of the cube is simplicial, while the face_fan is not.

julia> is_simplicial(normal_fan(cube(3)))
true

julia> is_simplicial(face_fan(cube(3)))
false

source

is_smooth — Method

is_smooth(PF::PolyhedralFan{QQFieldElem})

Determine whether PF is smooth.

Examples

Even though the cones of this fan cover the positive orthant together, one of these und thus the whole fan is not smooth.

julia> PF = polyhedral_fan(incidence_matrix([[1, 2], [2, 3]]), [0 1; 2 1; 1 0]);

julia> is_smooth(PF)
false

source

lineality_dim — Method

lineality_dim(PF::PolyhedralFan)

Return the dimension of the lineality space of the polyhedral fan PF, i.e. the dimension of the largest linear subspace.

Examples

The dimension of the lineality space is zero if and only if the fan is pointed.

julia> C = convex_hull([0 0; 1 0])
Polyhedron in ambient dimension 2

julia> is_fulldimensional(C)
false

julia> nf = normal_fan(C)
Polyhedral fan in ambient dimension 2

julia> is_pointed(nf)
false

julia> lineality_dim(nf)
1

source

lineality_space — Method

lineality_space(PF::PolyhedralFan)

Return a non-redundant matrix whose rows are generators of the lineality space of PF.

Examples

This fan consists of two cones, one containing all the points with $y ≤ 0$ and one containing all the points with $y ≥ 0$. The fan's lineality is the common lineality of these two cones, i.e. in $x$-direction.

julia> PF = polyhedral_fan(incidence_matrix([[1, 2, 3], [3, 4, 1]]), [1 0; 0 1; -1 0; 0 -1])
Polyhedral fan in ambient dimension 2

julia> lineality_space(PF)
1-element SubObjectIterator{RayVector{QQFieldElem}}:
 [1, 0]

source

maximal_cones — Method

maximal_cones(PF::PolyhedralFan)

Return the maximal cones of PF.

Optionally IncidenceMatrix can be passed as a first argument to return the incidence matrix specifying the maximal cones of PF. In that case, the indices refer to the output of rays_modulo_lineality(Cone).

Examples

Here we ask for the the number of rays for each maximal cone of the face fan of the 3-cube and use that maximal_cones returns an iterator.

julia> PF = face_fan(cube(3));

julia> for c in maximal_cones(PF)
         println(n_rays(c))
       end
4
4
4
4
4
4

julia> maximal_cones(IncidenceMatrix, PF)
6×8 IncidenceMatrix
[1, 3, 5, 7]
[2, 4, 6, 8]
[1, 2, 5, 6]
[3, 4, 7, 8]
[1, 2, 3, 4]
[5, 6, 7, 8]

source

cones — Method

cones(PF::PolyhedralFan, cone_dim::Int)

Return an iterator over the cones of PF of dimension cone_dim.

Examples

The 12 edges of the 3-cube correspond to the 2-dimensional cones of its face fan:

julia> PF = face_fan(cube(3));

julia> cones(PF, 2)
12-element SubObjectIterator{Cone{QQFieldElem}}:
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3

source

cones — Method

cones(PF::PolyhedralFan)

Return the ray indices of all non-zero-dimensional cones in a polyhedral fan.

Examples

julia> PF = face_fan(cube(2))
Polyhedral fan in ambient dimension 2

julia> cones(PF)
8×4 IncidenceMatrix
[1, 3]
[2, 4]
[1, 2]
[3, 4]
[1]
[3]
[2]
[4]

source

n_maximal_cones — Method

n_maximal_cones(PF::PolyhedralFan)

Return the number of maximal cones of PF.

Examples

The cones given in this construction are non-redundant. Thus there are two maximal cones.

julia> PF = polyhedral_fan(incidence_matrix([[1, 2], [3]]), [1 0; 0 1; -1 -1]);

julia> n_maximal_cones(PF)
2

source

n_cones — Method

n_cones(PF::PolyhedralFan)

Return the number of cones of PF.

Examples

The cones given in this construction are non-redundant. There are six cones in this fan.

julia> PF = polyhedral_fan(incidence_matrix([[1, 2], [3]]), [1 0; 0 1; -1 -1])
Polyhedral fan in ambient dimension 2

julia> n_cones(PF)
4

source

n_rays — Method

n_rays(PF::PolyhedralFan)

Return the number of rays of PF.

Examples

The 3-cube has 8 vertices. Accordingly, its face fan has 8 rays.

julia> n_rays(face_fan(cube(3)))
8

source

rays — Method

rays([as::Type{T} = RayVector,] PF::PolyhedralFan)

Return the rays of PF. The rays are defined to be the one-dimensional faces of its cones, so if PF has lineality, there are no rays.

Polyhedral Fans

Introduction

Construction

Auxiliary functions