Say we have the equation $Ax>b$, where $A$ is an M-by-N matrix, $b$ is a known vector of length N, x is an unknown vector of length N, and the inequality sign means that each element of $Ax$ is greater than the corresponding element of $b$. Is there some linear-algebra-based method, such as e.g. some modification of LU decomposition or something similar, that would be amenable to programming on a computer and which would allow me to generically solve this system for $x$, given numerical values for $A$ and $b$? I will also accept any method of determining merely whether a solution exists, if not any solutions themselves.
EDIT: I should clarify that I'm mainly working with matrices with N and M both less than 10, so an exact method that works analogously to e.g. LU decomposition will probably be faster than an iterative method.
Best Answer
LU decomposition is effectively doing book-keeping of Gaussian elimination. The analog of Gaussian elimination for solving a linear system of inequalities is Fourier-Motzkin elimination. This procedure is not useful in practice.
You are asking for $Ax>b$, but it might be easier to think about it in the following way:
Somehow adding that inequality gives you a leap in difficulty and expressiveness.
If you are looking to implement something yourself, you will almost surely have to learn about the Simplex Method. The Simplex Tableu gives an easy way to code a naive implementation.
To see how to convert your problem into the standard form $Ax=b$ with $x\geq 0$, see http://ocw.mit.edu/courses/sloan-school-of-management/15-053-optimization-methods-in-management-science-spring-2013/tutorials/MIT15_053S13_tut06.pdf