This is part of Exercise 10, Section 8.4 of Using Algebraic Geometry by Cox et. al.

Let $\vec{w}\in \mathbb{R}^n_{\ge 0}$ (positive orthant) such that $\vec{\beta}_j\cdot \vec{w}>0$ for $j=1,\dots,k$, where $\vec{\beta}_j\in \mathbb{Z}^n$. Show that such a vector $\vec{w}$ exists if and only if the origin is not in the convex hull of the set of all $\vec{\beta}_j$, together with the standard basis vectors $\vec{e}_i$ in $\mathbb{R}^n$.

I showed the "only if" part by contradiction. Suppose such a $\vec{w}$ exists and the origin is in the convex hull. Then there exists $\lambda_j, \mu_i\ge 0$ and $\sum\lambda_j+\sum\mu_i=1$, such that $$\lambda_1\vec{\beta}_1+\cdots+\lambda_k\vec{\beta}_k+\mu_1\vec{e}_1+\cdots+\mu_n\vec{e}_n=0.$$ Expanding the components gives \begin{align*} &\beta_{11}\lambda_1+\cdots+\beta_{k1}\lambda_k+\mu_1=0,\\ &\beta_{12}\lambda_1+\cdots+\beta_{k2}\lambda_k+\mu_2=0,\\ &\cdots\\ &\beta_{1n}\lambda_1+\cdots+\beta_{kn}\lambda_k+\mu_n=0. \end{align*} Let the coefficient matrix be $B_{k\times n}$. Then this system of equations can be written as $B\Lambda=-I_n U$. The equations for $\beta\cdot \vec{w}>0$ can be written as \begin{align*} &\beta_{11}w_1+\cdots+\beta_{1n}w_n-v_1=0,\\ &\cdots\\ &\beta_{k1}w_1+\cdots+\beta_{kn}w_n-v_k=0, \end{align*} where $v_j>0$ for all $j$. This system can be written as $B^T\vec{w}=I_k\mathbf{v}$ or $\vec{w}^TB=\mathbf{v}^TI_k$. Combining the two systems, we obtain $$-\vec{w}^TU=\vec{w}^TB\Lambda=\mathbf{v}^T\Lambda.$$ Recall that $w_j>0, v_j>0$ for all $j$, $\mu_j, \lambda_i\ge 0$ for all $i,j$. So we must have $U=0$ and $\Lambda=0$, a contradiction.

I couldn't figure out the "if" part by any means. I know that any linear combination of $\vec{\beta}_j$ with positive coefficients must have a negative component. Or conversely, if using contradiction with assumption such $\vec{w}$ does not exists, then for any positive linear combination of the components of $\vec{\beta}_j$, at least one of them is negative. But neither of them lead to anywhere.

Any help or suggestion would be appreciated!

  • 1
    $\begingroup$ Have you looked at Farkas' lemma? The first statement on Wikipedia with A = [B I; e' e'] seems to do the trick. $\endgroup$ – LinAlg Feb 21 '18 at 2:35
  • $\begingroup$ @LinAlg: Yes, that solves it! Thank you! $\endgroup$ – KittyL Feb 21 '18 at 15:54
  • $\begingroup$ That means that without using Farkas' lemma, you would have needed a separating hyperplane argument (similar to the proof of Farkas lemma), and those are always hard to come up with :) $\endgroup$ – LinAlg Feb 21 '18 at 16:00
  • $\begingroup$ @LinAlg: Yes, I see that. I'll try to read the proof of Farkas lemma. But knowing this lemma is very helpful! $\endgroup$ – KittyL Feb 21 '18 at 16:24

Your Answer

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

Browse other questions tagged or ask your own question.