# Simple Linear Algebra/ Linear Programming Proof: Proving Existence of Vector that satisfies Properties Hi, I've proved parts a and parts b, but I'm confused on how to prove part c. I think it should really follow directly from parts a and parts b but I'm lost. In part c, are we assuming that $$x_j$$ is not a null variable or that $$x_j$$ is a null variable?

If $$x \in P$$ and $$x_j$$ is a null variable then there exists some $$p \in R^m$$ for which $$p'A \geq 0, p'b=0$$ and such that the jth component of $$p^TA$$ is positive. Then $$A^Tp>0$$ since $$(A^Tp)=(p^TA)^{T}$$ so we are done.

But what happens if $$x \in P$$ and $$x_j$$ is not a null variable? Then there exists some $$y \in P$$ for which $$y_j >0$$ then I don't what to do. I'm confused what to do.

I've set up the primal and dual pairs for parts a:

Primal:

max $$0^T x$$

$$Ax=b$$

$$x \geq 0$$

Dual:

min $$p^Tb$$

$$p^T A \geq 0$$

• I don't see how you proved part a. You seem to use the implication "$(A^T p)_j > 0 \Rightarrow x_j = 0$". Is that based on complementary slackness? If yes, that only tells something about an optimal $x$, not about all $x \in P$, right? I think you need a slightly different primal/dual pair. – LinAlg Nov 12 at 19:06
• For part $c$, there is no assumption on $x_j$ being a null variable. A different way of phrasing question $c$ is: Suppose $Ax =b, x\geq 0, A^Tp \geq 0, p^Tb=0$, show that $x_j > 0$ or $(A^Tp)_j > 0$. – LinAlg Nov 12 at 19:12