9
$\begingroup$

A rational convex polyehedral cone $\sigma\subseteq\mathbb R^n$ is a set of the form $$ \sigma=\operatorname{Cone}(u_1,\dots,u_k) := \left\{ \sum_{i=1}^k r_i u_i \,\Bigg|\, r_i\ge 0\right\}\subseteq\mathbb R^n,$$ where all $u_i\in\mathbb Z^n$.

I'm interested in what is really involved in proving the following statements:

  1. $\sigma^\vee = \{ v\in \mathbb R^n \,|\, \langle u,v\rangle \ge 0 \,\forall u\in\sigma\}$ is a rational convex polyhedral cone.
  2. $\sigma^{\vee \vee} = \sigma$.

I've seen proofs for both statements in the general (not necessarily rational) case using first the Hahn-Banach theoreom to proof the second statement and then use this to proof the first.

Do we really need to involve functional analysis for the proof (in finite dimensions and only for rational cones) or is it possible to somehow construct normal vectors of the facets of the cone that will generate the dual cone using only tools from convex/polyhedral geometry?

An elementary proof of this, not involving functional analysis, would allow a more 'down to earth' approach to start toric geometry, since these statements are needed to start working with affine toric varieties given from rational convex polyhedral cones $\sigma$ as $\operatorname{Spec}(\mathbb C[\sigma^\vee\cap\mathbb Z^n])$.

$\endgroup$
  • 2
    $\begingroup$ Would a proof using only Farkas' lemma satisfy you ? If so I or someone else can write it down (or I can leave you the pleasure of writing it out for yourself, it’s rather natural) $\endgroup$ – Ewan Delanoy Jan 12 '14 at 17:57
  • $\begingroup$ @EwanDelanoy: I'd like to see that proof indeed. But then the question still remains, what is involved in proving Farkas' lemma? $\endgroup$ – Christoph Jan 12 '14 at 21:55
  • $\begingroup$ Hahn-Banach theorem in finite dimension is trivial thing $\endgroup$ – Red shoes Jun 5 '18 at 6:36
9
+50
$\begingroup$

Indeed, all except perhaps property (2) can be proved without functional analysis. It leads to a completely deterministic algorithm to compute a basis for the dual cone (not a very good algorithm though as its complexity is exponential in the initial basis size).

In the sequel RCP is shorthand for “rational convex polyhedral cone”.

Nearly everything reduces to the iteration of the following lemma:

Fundamental lemma. Let $\sigma={\sf Cone}(u_1,\ldots,u_k)$ be a RPC cone. Let $w\in{{\mathbb Z}^d}$, and $\sigma_w=\lbrace x\in\sigma \,|\, \langle x,w\rangle\ \geq 0\rbrace$. Then $\sigma_w$ is again a RPC cone. In fact, a completely explicit generating set can be found, as follows. Let

$$ \begin{array}{lcl} I_{-} &=& \big\lbrace i \ \big|\ \langle u_i,w\rangle \ < 0 \big\rbrace \\ I_{0} &=& \big\lbrace i \ \big|\ \langle u_i,w\rangle \ = 0 \big\rbrace \\ I_{+} &=& \big\lbrace i \ \big|\ \langle u_i,w\rangle \ < 0 \big\rbrace \\ \end{array} $$

Then $\sigma_w={\sf Cone}({\cal F})$ where

$$ {\cal F}=\big\lbrace u_i\ \big|\ i \in I_0 \cup I_{+}\big\rbrace \cup \big\lbrace \langle u_j,w\rangle u_i-\langle u_i,w\rangle u_j\ \big| \ i \in I_{-}, j\in I_{+}\big\rbrace $$

To show this fundamental lemma we need another :

Lemma 1. Let $n,m \geq 1$ be two integers. Let $x_1,x_2,\ldots,x_n$ and $y_1,y_2,y_3, \ldots ,y_m$ be nonnegative numbers. Then the following are equivalent :

(i) $x_1+x_2+ \ldots +x_n \geq y_1+\ldots +y_m$

(ii) There exists nonnegative numbers $\xi_k(1\leq k\leq n)$ and $t_{ij}(1\leq i \leq n,1\leq j \leq n)$ such that $x_i=\xi_i+\sum_{j}t_{ij}$ for every $i$ and $y_j=\sum_{i}t_{ij}$ for every $j$.

Proof of lemma 1. The direction (ii)$\Rightarrow$(i) is easy because under the hypothesis of (ii) we have

$$ \big(\sum_{i} x_i\big)-\big(\sum_{j} y_j\big)= \big(\sum_{i} \xi_i\big) \geq 0 $$

Conversely, we are going to show (i)$\Rightarrow$(ii) by induction on $N=n+m$. The base case $N=2$ is easy : we have $x_1\geq y_1$ and need just take $\xi_1=0,t_{11}=y_1$.

Now suppose the property is true at level $N$ ; we are going to show it still holds at level $N+1$. So suppose $x_1+x_2+ \ldots +x_n \geq y_1+\ldots +y_m$ for some nonnegative numbers $x_1,x_2,\ldots,x_{n},y_1,y_2,\ldots,y_m$, with $n+m=N+1$. There are two cases.

Case 1. $x_n \geq y_m$. Then we can write $x_n=y_m+X_n$ where $X_n$ is nonnegative. We then have an inequality with one variable less : $x_1+x_2+\ldots+x_{n-1}+X_n \geq y_1+y_2+\ldots +y_{m-1}$ and we can apply the induction hypothesis.

Case 2. $y_m \geq x_n$. Then we can write $y_m=x_n+Y_m$ where $Y_m$ is nonnegative. We then have an inequality with one variable less : $x_1+x_2+\ldots+x_{n-1} \geq y_1+y_2+\ldots +y_{m-1}+Y_m$ and we can apply the induction hypothesis.

This concludes the proof of lemma 1.

Proof of fundamental lemma from lemma 1. Let $\tau={\sf Cone}({\cal F})$. As all vectors in $\cal F$ are nonnegative linear combinations of the $u_i$, whose scalar product with $w$ is nonnegative, we have ${\cal F} \subseteq \sigma_w$ and hence $\tau \subseteq \sigma_w$. Conversely, let $v\in\sigma_w$. Let us put $n=|I_+|,m=|I_{-}|,p=I_{0}$. Reordering the $u_i$ if necessary, we may assume without loss that $I_+=[1,n],I_-=[n+1,n+m],I_0=[n+m,d]$. Then, there are nonnegative coefficients $a_1,a_2,\ldots, a_n,b_1,b_2,\ldots, b_m,c_1,c_2, \ldots, c_p$ such that

$$ v=\sum_{i=1}^{n} a_iu_i- \sum_{j=1}^{m} b_ju_{n+j}+ \sum_{k=1}^{p} c_ku_{n+m+k} \tag{1} $$

Then, the condition $\langle v,w\rangle \geq 0$ can be expressed as

$$ \sum_{i=1}^{n} a_i\langle u_i,w\rangle- \sum_{j=1}^{m} b_j\langle u_{n+j},w\rangle \geq 0 \tag{2} $$

Or, if we put $x_i=a_i\langle u_i,w\rangle$ and $y_j=b_j\langle u_{n+j},w\rangle $,

$$ \sum_{i=1}^{n} x_i- \sum_{j=1}^{m} y_j \geq 0 \tag{3} $$

This is the hypothesis of (i) in lemma 1, so let $\xi_k(1\leq k\leq n)$ and $t_{ij}(1\leq i \leq n,1\leq j \leq n)$ as in (ii) of this lemma. We then have

$$ \begin{array}{lcl} a_i&=&\frac{\xi_i+\sum_{j}t_{ij}}{\langle u_i,w\rangle } (1\leq i\leq n),\\ b_j&=&\frac{\xi_i+\sum_{i}t_{ij}}{\langle u_{n+j},w\rangle } (1\leq j\leq m) \end{array} \tag{4} $$

If we put $z_i=\frac{\xi_i}{\langle u_i,w\rangle }$ and $s_{ij}=\frac{t_{ij}}{\langle u_i,w\rangle\,|\langle u_{n+j},w\rangle|}$, we then have

$$ v=\sum_{i=1}^n z_i u_i +\sum_{i=1}^n \sum_{j=1}^m s_{ij}(\langle u_{n+j},w\rangle u_i-\langle u_i,w\rangle u_{n+j})+ \sum_{k=1}^{p} c_ku_k \tag{5} $$

which is plainly an element of $\tau$. This concludes the proof of the fundamental lemma.

Proof of property (1) from fundamental lemma Notice that ${\cal C}_0={\mathbb R}^d$ is itself a RCP cone (it can be written as ${\sf Cone}(e_1,-e_1,e_2,-e_2, \ldots ,e_d,-e_d)$ where $(e_1,e_2,\ldots ,e_d)$) is the canonical basis of ${\mathbb R}^d$). Then, let

$$ {\cal C}_i=\lbrace v\in {\mathbb R}^d \ | \ \langle v,u_j\rangle \ \geq 0 \ (1\leq j \leq i)\rbrace $$

Iterating the fundamental lemma, we see successively that ${\cal C}_0, {\cal C}_1,\ldots,$ are all RCP cones. In the end ${\sigma}^\vee={\cal C}_k$ is a RCP cone.

$\endgroup$
  • $\begingroup$ Thank you very much for that detailed proof, Ewan! To summarize what you did: You first show that intersecting a RPC with a half space gives you back another RPC, by giving explicit generators. Then you construct $\sigma^\vee$ by successively intersecting $\mathbb R^d$ with half spaces giving by the generators of $\sigma$, so you get an RPC. May I ask where you got the ideas for that proof? And can we proof property (2) from Farkas' Lemma, that suggests proving Farkas' Lemma is done by functional analysis? $\endgroup$ – Christoph Jan 14 '14 at 14:10
  • $\begingroup$ @ChristophPegel I think it is very likely that property (2) can be proved in a completely elementary way, though my proof is still incomplete. The RPC appearing in the fundamental lemma, i.e. intersecting $({\mathbb R}_+)^d$ with one inequality, is in some sense universal, and since (2) holds for it, there should be a way to deduce (2) for all RPCs. $\endgroup$ – Ewan Delanoy Jan 14 '14 at 14:31
  • $\begingroup$ Thank you again for your effort, you got the bounty :) $\endgroup$ – Christoph Jan 18 '14 at 11:57
  • 2
    $\begingroup$ @ChristophPegel By the way, Ziegler’s book “Lectures on Polytopes” contains a proof of both (1) and (2) without functional analysis $\endgroup$ – Ewan Delanoy Jan 18 '14 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.