# How to show polyhedral cone of nonnegative vectors contains finitely generated cone?

Let $$P=\{x \in \mathbb{R}^n \mid Ax \geq b, x \geq 0 \}$$ be a nonempty polyhedron for matrix $$A \in \mathbb{R}^{m \times n}$$ and $$b \in \mathbb{R}^m$$.

According to Minkowski-Weyl theorem $$P$$ can be written as

$$P=\text{conv}(v_1,\cdots,v_p)+ \text{cone}(d_1,\cdots,d_l)$$ for some $$v_i \in \mathbb{R}^n$$ and $$d_j \in \mathbb{R}^n$$.

Let $$C=\{x \in \mathbb{R}^n \mid Ax \geq 0, x \geq 0 \}$$.

Show that $$\text{cone}(d_1,\cdots,d_l) \subseteq C$$.

The thing that that I cannot cope with is how to connect the finite number $$l$$ that can be any natural number with dimension of the matrix $$A$$.

I tried the following:

Let $$z \in \text{cone}(d_1,\cdots,d_l)$$, so there exist non-negative $$\mu_i$$'s such that

$$z= \sum_{i=1}^l \mu_id_i$$ where $$\mu_1,\mu_2,\cdots,\mu_l \geq 0$$.

We can write $$z$$ as the following:

$$z= \begin{bmatrix} d_1 & d_2 & \cdots & d_l \end{bmatrix} \begin{bmatrix} \mu_1 \\ \mu_2 \\ \cdots \\ \mu_l \end{bmatrix}$$

Now, we should come up with an $$m \times n$$ matrix $$A$$ for which we have $$Az \geq 0$$ and $$z \geq 0$$ to prove the claim. But the problem is we do not have $$z \geq 0$$ necessarily.

• The statement is not true for any choice of $v_i$, so you need to chose them appropriately. – LinAlg Dec 14 '18 at 22:27
• @ LinAlg: The statement is true because it says for some $v_i$ and $d_j$. Also, it does not say what $p$ and $l$ are. Maybe I am wrong who am using wrong number for $l$. – Sepide Dec 15 '18 at 0:22
• a proof by contradiction is easier here: what if $z$ is not in $C$? – LinAlg Dec 15 '18 at 0:59
• @LinAlg: How we can do that? – Sepide Dec 15 '18 at 4:13
• if $z$ does not satisfy $Az\geq 0$ or $z\geq 0$, moving in the direction of $z$ will violate a constraint of $P$ – LinAlg Dec 15 '18 at 16:19

We know that $$P$$ can be written as $$P=\operatorname{conv}(v_1,\cdots,v_p)+ \operatorname{cone}(d_1,\cdots,d_l)=V+D.$$ The set $$D$$ is a cone, hence, for every $$v\in V$$ and $$d\in D$$ we have that $$v+td\in P$$, $$\forall t\ge 0$$. That is $$A(v+td)\ge b,\quad v+td\ge 0,\quad\forall t\ge 0.$$ Now divide by $$t$$ and let $$t\to +\infty$$ \begin{align} \frac{1}{t}Av+Ad\ge\frac{1}{t}b\quad&\Rightarrow\quad Ad\ge 0,\\ \frac{1}{t}v+d\ge 0 \quad&\Rightarrow\quad d\ge 0. \end{align} Therefore, every $$d\in D$$ belongs to $$C$$.
• Could you help me show the reverse? I mean $C \subseteq \text{cone}(d_1,\cdots,d_l)$. It cannot be immediately observed from your proof to show the reverse, I am having trouble of producing $x \geq 0$? – Sepide Dec 15 '18 at 18:32