# Null Variable in linear programming

Let $$P=\{x\in\mathbb{R}^n|Ax=b,x\geq0\}$$ be a nonempty polyhedron, and let $$m$$ be the dimension of the vector $$b$$. We call $$x_j$$ a null variable if $$x_j=0$$ whenever $$x\in P$$. (b) prove that if $$x_j$$ is a null variable, then there exists some $$p\in\mathbb{R}^m$$ for which $$p'A\geq 0', p'b=0$$, and such that the $$j$$th component of $$p'A$$ is positive AND (c) if $$x_j$$ is not a null variable, then by definition, there exists some $$y\in P$$ for which $$y_j>0$$. Use the results in parts (a) and (b) to prove that there exist $$x\in P$$ and $$p\in\mathbb{R}^m$$ such that $$p'A\geq0', p'b=0, x+A'p>0$$

I did prove part (a) which was fairly easy to compute simply by multiplying $$p'$$ on the both sides of $$Ax=b$$. However I am struggling solving both (b) and (c). I am assuming $$p\in\mathbb{R}^m$$ is a dual variable and since $$x_j$$ is a null variable, $$j$$th constraint of dual can be removed. I also think that $$j$$th component of $$p'A$$ is positive because otherwise $$x\notin P$$, i.e. $$Ax\neq b$$. But I don't clearly see it. I am completely lost on part (c) as well. Any help would be very appreciated.

• Are you familiar with Farkas's lemma? – Misha Lavrov Nov 12 at 1:56
• @MishaLavrov Just a bit. I've learned the definition and some applications of farkas's lemma. – jackDanielle Nov 12 at 2:02
• This problem seems like another one of those applications. – Misha Lavrov Nov 12 at 2:12

For (a) and (b), the proof is similar to that of Farka's lemma. Hint: Consider the dual of the LP $$\max \, \left\{e_j'x : x \in P\right\}.$$
For (c), we can classify the indices into two groups, i.e. ones with null variables and the others without. For each $$j$$ such that $$x_j$$ is a null variable, we can find a $$p^j$$ such that the conditions are met. Now let $$p$$ be the sum of these $$p^j$$s. We have that $$p'A\ge 0', \quad p'b=0, \\ \quad (A'p)_j > 0, \; \forall j: x_j \, \text{is a null variable}.$$
Finally, for each $$i$$ such that $$x_i$$ is not a null variable, there exists $$y^i \in P$$ such that $$y^i_i > 0$$. Let y be the average of these $$y^i$$s. We have that $$y \in P \; \text{and} \; y_i > 0, \; \forall i: x_i \, \text{is not a null variable,}$$
and that $$y + A'p > 0$$.
$$y$$ and $$p$$ are as desired.
Note: If there are no null variables, we can simply set $$p=0$$. If all variables are null, any feasible $$y$$ will suffice.