Polyhedral
We work with a two mutually dual finite-dimensional vector spaces \( N \) and \( M \) over a linearly ordered field \( \Bbbk \). This means, we have a bilinear pairing \( \langle \cdot , \cdot \rangle \colon N \times M \to \Bbbk \) such that the induced maps \( M \to \operatorname{Hom}(N,\Bbbk ) \) and \( N \to \operatorname{Hom}(N,\Bbbk ) \) are both bijective (this is also known as a perfect pairing). Since \( \Bbbk \) is linearly ordered, we can define the non-negative scalars \(\Bbbk _{\geq 0} = \{ t \in \Bbbk \mid t \geq 0 \} \subseteq \Bbbk \). This is a semifield, i.e. a commutative semiring, in which every nonzero element has a multiplicative inverse.
A hyperplane is the perp space of a point.
A halfspace is the dual of a point. The dimension of the module the cone is a submodule of.
The dimension of a pointed cone.
A polyhedral cone is full-dimensional if its dimension is the same as the dimension of the ambient space.
The set of all \(k\)-dimensional faces of a polyheadral cone.
For each \(k\) gives the number of \(k\)-dimensional faces of a polyheadral cone.
0.1 Polyhedral cones
A pointed cone \( \sigma \subseteq N \) is a \( \Bbbk _{\geq 0} \)-submodule of \( N \).
A pointy cone \( \sigma \subseteq N \) is a \( \Bbbk _{\geq 0} \)-submodule of \( N \) that does not contain a nontrivial linear space.
For a set \( S \subseteq N \), the cone generated by \( S \) is the pointed cone
A pointed cone \( \sigma \subseteq N \) is called finitely generated, if \( \sigma = \operatorname{Cone}(S) \) for some finite set \( S \subseteq N \).
For a set \( S \subseteq M \), the dual cone of \( S \) is the pointed cone
Another word for finitely generated cone with a finitely generated canonical dual.
0.1.1 Examples
The zero-space \( \{ 0\} \subseteq N \) is a polyhedral cone.
If \( S \subseteq M \) is a finite \( \Bbbk \)-basis of \( M \), then \( \{ 0\} = (S \cup -S)^\vee \).
The full space is a polyhedral cone.
Any halfspace is a polyhedral cone.
Any linear subspace is a polyhedral cone.
If \( \sigma \subset N \) is finitely generated, then \( \sigma ^\vee \subset M \) is polyhedral.
Let \( \sigma = \operatorname{Cone}(S) \) for \( S \subseteq N \). We need to show \( \operatorname{Cone}(S)^\vee = S^\vee \). The inclusion “\( \subseteq \)” is obvious, as \( S \subseteq \operatorname{Cone}(S) \). The opposite inclusion can be shown by induction on the general element of \( \operatorname{Cone}(S) \).
If \( \sigma \subseteq N \) is polyhedral, then \( \sigma ^{\vee \vee } = \sigma \).
For any set \( S \subseteq N \) it is trivial to show \( S^{\vee \vee \vee } = S^{\vee } \). The claim follows since \( \sigma = S^{\vee } \) for a finite set \( S \subseteq N \).
If \( \sigma \subseteq N \) is a polyhedral cone and \( w \in N \), then \( \sigma + \operatorname{Cone}(\{ w\} ) \) is polyhedral too.
Write \( \sigma = S^{\vee } \) for a finite \( S \subseteq M \). Define
Note that \( T \) is finite. We claim \( S^{\vee } + \operatorname{Cone}(\{ w\} ) = T^{\vee } \). Clearly \( T \subseteq \operatorname{Cone}(S) \), hence \( S^{\vee } = \operatorname{Cone}(S)^{\vee } \subseteq T^{\vee } \). Also clear is \( w \in T^{\vee } \), hence \( S^{\vee } + \operatorname{Cone}(\{ w\} ) \subset T^{\vee } \). For the reverse inclusion, let \( v \in T^\vee \). We need to show \( v - uw \in S^\vee \) for some \( u \in \Bbbk _{\geq 0} \). If there is no \( y \in S \) with both \( \langle y, w \rangle {\lt} 0 \) and \( \langle y, v \rangle {\lt} 0 \), we can easily see that \( u = 0 \) works, i.e. \( T^{\vee } \subseteq S^{\vee } \). Otherwise, we set
which is then well-defined and non-negative. We need to show \( u \langle z, w \rangle \leq \langle z, v \rangle \) for all \( z \in S \). If \( \langle z, w \rangle {\lt} 0 \), this follows from maximality of \( u \). If \( \langle z, w \rangle = 0 \), the claim follows from \( z \in T \) and \( v \in T^{\vee } \). Lastly, assume \( \langle z, w \rangle {\gt} 0 \) and fix \( y \in S \) such that \( u = \frac{\langle y, v \rangle }{\langle y, w \rangle } \). In particular, \( \langle y, w \rangle {\lt} 0 \). Then the claim \( u \langle z, w \rangle \leq \langle z, v \rangle \) is equivalent to
But \( y \langle z, w \rangle - z \langle y, w \rangle \in T \), hence the claim follows from \( v \in T^{\vee } \).
If \( \sigma \in N \) is finitely generated, then it is polyhedral.
For a finite set \( S \subseteq N \), we have \( S^{\vee \vee } = \operatorname{Cone}(S) \).
A pointed cone \( \sigma \subseteq N \) is finitely generated iff it is polyhedral.
The implication “\( \Rightarrow \)” is Proposition 15. For the converse, assume \( \sigma = S^{\vee } \) for some finite \( S \subseteq M \). Then \( \operatorname{Cone}(S) \) is finitely generated, hence polyhedral by 15. Thus we find a finite \( T \subseteq N \) with \( \operatorname{Cone}(S) = T^\vee \). We obtain
where the last equality is due to 16. Thus \( \sigma \) is finitely generated.
If \( \sigma \subseteq N \) is polyhedral, then \( \sigma ^\vee \subseteq M \) is polyhedral too.
Every polyhedral cone can be written as the minkowski sum of a pointy cone and a linear subspace.
0.1.2 Operations
If \( \sigma \subseteq N \) is polyhedral and \(f : N -{\gt} M\) is a linear map, then \( f.map \sigma \subseteq M \) is polyhedral too.
If \( \sigma , \tau \subseteq N \) are polyhedral, then \( \sigma + \tau \) is polyhedral too.
If \( \sigma , \tau \subseteq N \) are polyhedral, the direct sum \( \sigma \oplus _p \tau \) is polyhedral too.
If \( \sigma , \tau \subseteq N \) are polyhedral, their join is polyhedral too.
If \( \sigma , \tau \subseteq N \) are polyhedral, then \( \sigma \cap \tau \) is polyhedral too.
If \( \sigma , \tau \subseteq N \) are polyhedral, then the cartesian product \( \sigma \prod \tau \) is polyhedral too.
For a set \(S \subseteq N\), the convex hull of \(S\) is
If \( \sigma , \tau \subseteq N \) are polyhedral, then the convex hull of the two is polyhedral too.
Polyhedral cones for a lattice under intersections and convex hulls (its the same lattice as on pointed cones).
0.1.3 Special cones
A simplicial cone \(\sigma \) is a polyhedral cone that can be generated by \(dim (\sigma )\) many generators.
0.1.4 Faces and the Face Lattice
We define faces of polyhedral cones. The main goal is the partial order relation on the set of faces and showing that there is a bijection between faces of \( \sigma \) and faces of \( \sigma ^{\vee } \).
For any subset \( A \subseteq M \), we define the perp space
which is a pointed cone in \( N \). We also write \( u^{\perp } := \{ u\} ^{\perp } \).
If \( A \subseteq M \) is closed under negation (for instance, \( A \subseteq M \) a \( \Bbbk \)-submodule), then \( A^{\perp } = A^{\vee } \).
\( A^{\perp } \subseteq A^{\vee } \) is clear. Let \( x \in A^{\vee } \) and \( a \in A \). then \( \langle x, a \rangle \geq 0 \) and \( -\langle x, a \rangle = \langle x, -a \rangle \geq 0 \). Hence \( \langle x, a \rangle = 0 \) and \( x \in A^{\perp } \).
A face of a pointed cone \( \sigma \subseteq N \) is the intersection of \( \sigma \) with some hyperplane \( u^{\perp } \) for \( u \in \sigma ^{\vee } \). We write \( \tau \preceq \sigma \) if \( \tau \) is a face of \( \sigma \) and \( \tau \prec \sigma \) if \( \tau \) is a proper face, i.e. \( \tau \preceq \sigma \) and \( \tau \neq \sigma \).
For any subset \( S \subseteq N \) and \( u \in S^{\vee } \), we have
Both inclusions should be a simple Span-induction.
A face of a polyhedral cone is polyhedral.
Use 33 and the fact that if \( S \) is finite, so is \( S \cap u^{\perp } \).
A polyhedral cone has only finitely many faces.
By 34, a face of a polyhedral cone \( \sigma = \operatorname{Cone}(S) \) is of the form \( \operatorname{Cone}(S') \) for some \( S' \subseteq S \). Being finite, \( S \) has only finitely many subsets, which shows the claim.
If \( \sigma \) is a pointed cone, then the intersection of two faces of \( \sigma \) is a again face of \( \sigma \).
Let \( \tau = \sigma \cap u^{\perp } \) and \( \tau ' = \sigma \cap \tau '^{\perp } \) be faces. We claim that \( \sigma \cap u^{\perp } \cap u'^{\perp } = \sigma \cap (u + u')^{\perp } \). The inclusion “\( \subseteq \)” is obvious. For the converse, suppose \( v \in \sigma \) with \( \langle v, u \rangle + \langle v, u' \rangle = 0 \). Since \( u, u' \in \sigma ^{\vee } \), both summands are nonnegative, hence \( \langle v, u \rangle = \langle v, u' \rangle = 0 \).
Let \( \tau \preceq \sigma \) be a face of a pointed cone. Then \( \tau ^{\vee } = \tau ^{\perp } + \sigma ^{\vee } \).
It’s easy to show that \( \tau = \operatorname{Span}_{\Bbbk }(\tau ) \cap \sigma ^{\vee } \). Dualising gives \( \tau ^{\vee } = \operatorname{Span}_{\Bbbk }(\tau )^{\vee } + \sigma ^{\vee } \). Apply 31 to get \( \operatorname{Span}_{\Bbbk }(\tau )^{\vee } = \operatorname{Span}_{\Bbbk }(\tau )^{\perp } = \tau ^{\perp } \).
A face of a face of a polyhedral cone \( \sigma \) is again a face of \( \sigma \).
Let \( \tau = \sigma \cap u^{\perp } \) with \( u \in \sigma ^{\vee } \) and \( \rho = \tau \cap v^{\perp } \) with \( v \in \tau ^{\vee } \). By 37, we can write \( v = v_1 + v_2 \) with \( v_1 \in \tau ^{\perp } \) and \( v_2 \in \sigma ^{\vee } \). Then \( u + v_2 \in \sigma ^{\vee } \) and we claim \( \rho = \sigma \cap (u + v_2)^{\perp } \). For “\( \subseteq \)”, let \( x \in \rho = \tau \cap v^{\perp } \). Since \( x \in \tau \), we get \( \langle x, u \rangle = 0 \) and \( \langle x, v_1 \rangle = 0 \). Since \( x \in v^{\perp } \), also \( \langle x, v \rangle = 0 \), which by \( v = v_1 + v_2 \) implies \( \langle x, v_2 \rangle = 0 \). In total, \( \langle x, u + v_2 \rangle = 0 \). For the converse, assume \( x \in \sigma \cap (u + v_2)^{\perp } \), i.e. \( \langle x, u \rangle + \langle x, v_2 \rangle = 0 \). Since both \( u, v_2 \in \sigma ^{\vee } \) and \( x \in \sigma \), both summands are nonnegative, hence \( \langle x, u \rangle = \langle x, v_2 \rangle = 0 \). This implies \( x \in \tau \), thus also \( \langle x, v_1 \rangle = 0 \). In total, \( \langle x, v \rangle = \langle x, v_1 \rangle + \langle x, v_2 \rangle = 0 \), thus \( x \in \rho \).
In particular, Lemma 38 establishes a partial order on the set of faces of a polyhedral cone \( \sigma \) (written \( \operatorname{faces}(\sigma ) \)). It is finite by 35.
Given a polyhedral cone, the partial order on its faces is a lattice. We call it the face lattice of the cone.
Top is the entire cone, bot is the empty cone.
Given a polyhedral cone, the partial order on its faces is graded.
The grading is given by the number of faces of this face.
Two polyhedral cones are combinatorially equivalent if there is an order isomorphism between their face lattices.
Face lattices of dual cones are dual to each other.
The face lattice of a face is isomorphic to a lower interval of the face lattice of a polyhedral cone.
Linear transformaions preserve combinatorial equivalence. There is an iso that should be provided
0.1.5 Polarity
For a pointed cone \( \sigma \), the polar cone of \( \sigma \) is the pointed cone
0.2 Polytopes
A polytope is a set that can be written as \(\operatorname{Conv}(S)\) for some finite set \(S\).