# Relation Between Two $\mathcal{V}$-Representations of a Polyhedron

Suppose that a polyhedron $$P\subset\mathbb{R}^n$$ has two $$\mathcal{V}$$-representations \begin{align} P &= \text{conv}(\{x_1,...,x_k\})+\text{coni}(\{w_1,...,w_r\}) \\[4pt] &= \text{conv}(\{y_1,...,y_{\ell}\})+\text{coni}(\{v_1,...,v_s\}). \end{align} Here $$\text{conv}$$ is the convex combination: $$\text{conv}(S):=\left\{\sum_{j=1}^J\lambda_jx_j:x_j\in S,\,\lambda_j\ge 0,\,\sum_{j=1}^J\lambda_j=1,\,J\in\mathbb{N}\right\},$$ and $$\text{coni}$$ is the conic combination: $$\text{coni}(T):=\left\{\sum_{j=1}^J\theta_jw_j:w_j\in T,\,\theta_j\ge 0,\,J\in\mathbb{N}\right\}.$$ My question: What can we say about the relation between the points $$x_j,w_j,y_j,v_j$$ used in the two representations?

My attempt:

1. Relation between the $$x_i$$'s and $$y_j$$'s. It is possible that $$x_j\not\in\text{conv}(\{y_1,...,y_{\ell}\})$$, since \begin{align} &\quad\ \text{conv}(\{x_1,...,x_k,w_1,...,w_r\})+\text{coni}(\{w_1,...,w_r\}) \\ &=\text{conv}(\{x_1,...,x_k\})+\text{coni}(\{w_1,...,w_r\}). \end{align} The coefficients of $$w_1,...,w_r$$ in the convex combination can be absorbed into the conic combination.

2. Relation between the $$w_i$$'s and $$v_j$$'s. My intuition tells me that $$w_i\in\text{coni}(\{v_1,...,v_s\})$$ for each $$i$$, because the convex combination represents the bounded part of $$P$$, while the conic combination represents the unbounded part. However, I am unable to give a proof.

I have figured out the answer. It is true that $$w_i\in\text{coni}(\{v_1,...,v_s\})$$ for each $$i$$.
It suffices to prove that when $$P=\text{conv}(\{x_1,...,x_k\})+\text{coni}(\{w_1,...,w_r\})$$, its recession cone $$\text{recc}(P):=\{d\in\mathbb{R}^n:x+\theta d\in P\ \ \forall\,x\in P\ \ \forall\,\theta\ge 0\}$$ is given by $$\text{recc}(P)=\text{coni}(\{w_1,...,w_r\}).$$ The inclusion $$(\supset)$$ is obvious. To prove $$(\subset)$$, for every $$d\in\text{recc}(P)$$, for every $$\theta\ge 0$$, since $$x_1+\theta d\in P$$, then $$x_1+\theta d=\sum_{i=1}^k\lambda_i(\theta)x_i+\sum_{j=1}^r\mu_j(\theta)w_j,$$ where $$\lambda_i(\theta)\ge 0$$, $$\mu_j(\theta)\ge 0$$, and $$\sum_{i=1}^k\lambda_i(\theta)=1$$. Rearranging the terms, we obtain $$d=\frac{1}{\theta}\left(\sum_{i=1}^k\lambda_i(\theta)x_i-x_1\right)+\sum_{j=1}^r\frac{\mu_j(\theta)}{\theta}w_j.$$ For all $$\theta\ge 0$$ it holds that $$\left\|\sum_{i=1}^k\lambda_i(\theta)x_i-x_1\right\|_2\le \sum_{i=1}^k\|x_i\|_2,$$ so $$d=\lim_{\theta\to\infty}\sum_{j=1}^r\frac{\mu_j(\theta)}{\theta}w_j\in\text{coni}(\{w_1,...,w_r\})$$ by the closedness of the cone.