Intrinsic definition of a cone in a normal fan

Question

Let $P\subseteq \mathbb{R}^n$ be a full dimensional polytope. Let us assume that $P$ has a facet description with the following inequalities: $$ \left<x,u_F\right> \geq -a_F$$ where $u_F\in \mathbb{R}^n$ and $a_F\in \mathbb{R}$ for each facet $F$ of the polytope.

In other words, $P$ is the bounded intersection of the halfspaces $H_{u_F,-a_F}^+$. For each $Q$ face of $P$ we define the cone $$\sigma_Q := \operatorname{Cone}(u_F: F \text{ facet, } F\supseteq Q)$$

What I want is to prove that $$\sigma_Q = \{u\in \mathbb{R}^n : \left<x,u\right> \leq \left<y,u\right> \text{ for all } x\in Q, y\in P\}$$

My thoughts: It is easy to prove one of the inclusions. For the other, I wanted to use (one of the many versions of) Farkas Lemma.

If $u\in \mathbb{R}^n$ satisfies $\left<x,u\right>\leq \left<y,u\right>$ for each $x\in Q$ and $y\in P$, in particular, there exists a face $Q'$ of $P$ such that $Q' = P \cap H_{u,a}$ for certain $a=\left<x,u\right>$ for any $x\in Q$ (this value is independent of $x\in Q$), also $Q\subseteq Q'$ and $P\subseteq H_{u,a}^+$. I tried to use Farkas Lemma II (see Ziegler's book). So, to conclude that $u\in \sigma_Q$, I need to prove that there cannot exist a vector $m\in \mathbb{R}^n$ with the property that: $$\left<m,u_F\right> \geq 0 \text{ for all facets } F\supseteq Q'$$ and simultaneously $$\left<m,u\right> < 0.$$

To get a contradiction I think it suffices to show that one can find a point $x\in P\smallsetminus Q'$ such that $x = q - \lambda m$ for a $q\in Q'$ and $\lambda > 0$.

In that case, $x\in P\smallsetminus Q'$ implies that for some facet $F$ with $F\supseteq Q'$ it has to be: $\left<x,u_F\right> > -a_F$, which yields $\left<q,u_F\right> - \lambda\left<m,u_F\right> > -a_F$. The fact that $q\in Q'$ implies that $\left<q,u_F\right> = -a_F$, from where it follows $\lambda\left<m,u_F\right> < 0$ and $\lambda > 0$ yields $\left<m,u_F\right> < 0$ which is the desired contradiction. I am having trouble to prove the existence of such an $x$.

Of course, a different approach to prove this is also welcome!

Answer 1

Let's name $\sigma_1 = \operatorname{cone}(u_F : F \text{ facet}, Q \subset F)$ and $\sigma_2 = \operatorname{cone} (\{y-x : x \in Q, y \in P\})$

As you noticed, $\sigma_1 \subset \sigma_2^{\vee}$ is obvious, so only the second direction is interesting.

Notice that the problem is translation invariant, so choosing appropriate coordinates we can assume that $0 \in \operatorname{relint}(Q)$ the point in the relative interior. Using this assumption we can see that $\sigma_2 = \operatorname{cone}(P)$ where $P$ interpreted as a set of vectors. Indeed, $\operatorname{cone}(P) \subset \sigma_2$ is the implication of $x-0 \in \sigma_2$ and $\sigma_2 \subset \operatorname{cone}(P)$ is the implication of $y \in \operatorname{cone}(P), -x \in \operatorname{cone}(P)$ for any $y \in P, x \in Q$. Notice that $-x \in \operatorname{cone}(P)$ is the consequence of the $0 \in \operatorname{relint}(Q)$.

Using all those reductions the problem now is to check that the obvious inclusion $\sigma_1 \subset \operatorname{cone}(P)^{\vee} $ is in fact equality. Suppose it is not, so there is a functional $\phi \in \operatorname{cone}(P)^{\vee}$ such that it is not in $\sigma_1$. Let $A$ be the matrix in which all $u_F, F \supset Q$ written by columns, $Ax = \phi, x \geq 0$ have no solutions, by Farkas II there is a vector $v$ such that $(v,u_F) \geq 0$ for every facet $F \supset Q$ but $(v,\phi) < 0$ so $v \not \in \operatorname{cone}(P)$.

Let $U = \{x \in \mathbb R^n : (u_F,x) + a_F >0, F \not \supset Q\}$ this is the open set which contains $0$ and I claim that

$$U \cap P = U \cap \{x \in \mathbb R^n : (u_F,x) \geq 0, F \supset Q\}$$ indeed, H-polytope $P$ could be defined by $P=\{x \in \mathbb R^n :(u_F,x) + a_F \geq 0, F \text{ is facet}\}$ part of equations are satisfied by restricting to $U$ and part of them satisfied explicitly. Notice that $a_F = 0$ for $F \supset Q$, because $0 \in F$ in that case.

Returning to the point $v$ such that $(v,u_F) \geq 0, F \supset Q$ and $v \not \in \operatorname{cone}(P)$. Since $U$ is open and contains $0$ there is $t \in \mathbb R_{>0}$ such that $tv \in U$, because $tv$ satisfying all the inequalities $(u_F,tv) = t(u_F,v) \geq 0, F \supset Q$ we have $tv \in U \cap P$ so $tv \in P$, but Farkas II says that $tv \not \in \operatorname{cone}(P)$ (since $v \not \in \operatorname{cone}(P)$) this is the contradiction.