How to check whether feasible solutions for linear programs do exist?

Question

For a linear program, how to decide whether there exists a feasible solution without solving it?

For $Ax \le b$, is there any sufficient and/or necessary condition represented by matrix $A$ and vector $b$ to decide the existence of a feasible solution without solving the problem?

Answer 1

You can use the following result:

Theorem (Farkas lemma, 1894): Let $A\in\mathbb{R}^{m\times n}$ and $b\in\mathbb{R}^m$. Then $Ax\le b$ has a solution if and only if $A^Ty=0$, $y\ge 0$, $b^Ty<0$ has no solution.

Corollary: In other words, $A^Ty=0$, $y\ge 0$ $\Rightarrow$ $b^Ty\ge 0$.