We have a matrix $A\in\mathbb{R}^{m\times n}$ where $m>n$ ($m$ can be way much larger than $n$). The problem is to choose a vector $x\in\mathbb{R}^n$ such that every component of $b=Ax\in\mathbb{R}^m$ can be made as negative as possible. That is for any given vector $c\in\mathbb{R}^m$, we can choose $x\in\mathbb{R}^n$ such that $Ax<c$ component wise.
Since the range space of $A$ cannot have a dimension larger than $n$, the rows of $A$ needs to satisfy some conditions so that every component of $Ax$ can be made as negative as possible.
When $A=\begin{bmatrix}a_{11}\\ a_{21}\end{bmatrix}$, the condition is that $a_{11}$ and $a_{22}$ have the same sign. When the dimension goes higher, I was wondering what the conditions are. Is there a theorem/result for general cases?
An equivalent condition is that the only nonnegative vector in the null space of $A^T$ is $0$. See Gordan's theorem.
In practice, you can use linear programming software to decide if this is the case.