Show that system $Ax\geq 0,$ and $A^Ty=0, y\geq 0$ has solution satisfies $Ax+y>0$.

Question

Let $A$ be a $m\times n$ real matrix. Show that system

(I): $Ax\geq 0,$

(II): $A^Ty=0, y\geq 0$

has solution satisfies $Ax+y>0$.

I have no idea to prove above claim. Can you give me a hint? Thanks

Answer 1

Here's one way to do it using LP duality.

For any $m$-dimensional vector $y$, the support of $y$ is the set $supp(y):=\{j\in[m]\,:\,y_j\neq 0\}$. Note that, if $y, y'$ are two feasible solutions for $(II)$, then also $y+y'$ is a feasible solution, and $supp(y+y')=supp(y)\cup supp(y')$. This shows that there exists a feasible solution $\bar y$ to $(II)$ such that $supp(\bar y)$ is inclusion-wise maximum. (Note that according to this definition $\bar y$ is the zero vector iff $(II)$ has no non-zero solution, in which case $supp(\bar y)=\emptyset$.)

Let $b$ be the $m$ dimensional vector such that $b_i=0$ for $i\in supp(\bar y)$, and $b_i=1$ for $i\in [m]\setminus supp(\bar y)$. Consider now the primal-dual pair of problems

• (P) $\min \{0\,:\,Ax\geq b\}$
• (D) $\max \{b^T y\,:\,A^T y=0,\, y\geq 0\}$

Observe that (D) is always feasible ($y=0$ is a feasible solution), and by definition of $\bar y$ and of $b$ every feasible solution to (D) must have support disjoint from $b$, which implies that $b^T y=0$ for all feasible solutions. This shows that (D) has an optimal value (namely, $0$), so by strong duality also (P) has an optimal solution. In particular, this implies that (P) is feasible. Let $\bar x$ be a feasible solution to (P). We have $A\bar x+\bar y\geq b+\bar y>0$.