Is $\{v\in\mathbb{R^m} |v^TA≤c^T\}$ empty? So I have to determine if the next proposition is true or false.
If $\forall M<0$, $\exists$ $u\in\{x\in\mathbb{R^n}|Ax=b,x\geq0 \}$such that $c^Tu< M$ then $\{v\in\mathbb{R^m} |v^TA≤c^T\}$ is empty.
But I don't know how to start. Any ideas might be helpful.
 A: If you are familiar with duality theorems. (Suppose not, refer to the other answer)
Consider the primal problem:
$$\min c^Tx$$
subject to
$$Ax=b$$
$$x \ge 0$$
The corresponding dual problem is
$$\max v^Tb$$
subject to $$v^TA \le c^T$$
If the primal problem is unbounded, then we know that by weak duality that the dual problem is infeasible.
A: The implication is true. For the sake of contradiction, suppose that $v\in\mathbb R^{\mathbb m}$ is such that $$v^{\mathsf T}A\leq c^{\mathsf T}.\tag{$\spadesuit$}$$ Let $M$ be a negative number of sufficient magnitude such that $$M<v^{\mathsf T}b.\tag{$\clubsuit$}$$ By the premise, there exists some $u\in\mathbb R^{\mathbb n}$ such that $Au=b$, $u\geq 0$, and $c^{\mathsf T}u<M$. Since $u\geq 0$, right-multiplying both sides of ($\spadesuit$) by it will preserve the inequality: $$v^{\mathsf T}Au\leq c^{\mathsf T}u.$$ But since $Au=b$ and $c^{\mathsf T} u<M$, one obtains $$v^{\mathsf T}b <M,$$ which contradicts ($\clubsuit$).
A: Proof by contrapositive:
Suppose $v \in \mathbb{R}^m$ satisfies $v^\top A \preceq c^\top$.
If $u$ satisfies $Au=b$ and $u \succeq 0$, then
$$v^\top b \overset{Au=b}{=} v^\top A u \overset{v^\top A \preceq c^\top;\; u \succeq 0}{\le} c^\top u.$$
So if $M < v^\top b$ we cannot have $c^\top u < M$.
