I'm trying to understand the solution to this question in Bertsimas 4.29: Question: Let $a_1,....a_m$ be some vectors in $R^n$ with $m>n+1$. Suppose that the system of inequalities, $a_i'x \geq b_i,i=1,....m$ does not have any solutions. Show that we can choose $n+1$ of these inequalities, so that the resulting system of inequalities has no solutions.
The solution given is:
Questions:
Questions:
Why is the polyhedron, $P$ considered with the transposes $A^Tp=0, b^Tp=1$ as opposed to $p^TA=0^T$
Why does theorem 4.7 imply that if $x$ is a solution to the subsystem we must have $0^T x=0 \leq -1$? I also don't get how this is implied by $\hat{p}^T A=0^T, \hat{p}^T b=1, p \geq 0$. Theorem 4.7 is given as:
Where does the $-1$ come from in the inequality $0 \leq -1$ is my main question. Thank you.
Notice that $p^TA = 0^T \iff A^Tp=0$, these two conditions are equivalent, so it doesn't matter if we consider its transpose or not.
To use theorem $4.7$,
Notice that $\hat{p}^T(-A)=0^T$, here in theorem $4.7$, $c=0$. We also have $p\ge 0$, and $\hat{p}^T(-b) =-1 \le -1$, here $d=-1$. That is part $(b)$ of condition $4.7$ holds, then we conclude that result for part $(a)$ holds
If $\hat{x}$ is a solution to the subsystem, then $(-A)x\le (-b)$, hence we have $c'x=0 \le d = -1$ which is a contradiction.