It is well known how to solve a system of linear equations $A{\bf x} = {\bf b}$, but how do we solve a system of linear inequalities $A{\bf x} \leq {\bf b}$?
For the applications I have in mind the most important questions are: (1) determining whether there are any solutions, and if so (2) finding the dimension of the solution set.
If it makes things any easier, the case ${\bf b} = {\bf 0}$ is of particular interest — how can we effectively compute the dimension of the polyhedral cone $A{\bf x} \leq {\bf 0}$?
This seems closely related to linear programming since we are asking to find the dimension of the feasible region. But just to be clear — we don't really care about finding any particular solutions, or optimizing an objective function; we only want to know the dimension of the feasible region. I am hoping that this is easier than linear programming in general.
I am especially interested in practical algorithms, but if you know any related theory that would be welcome as well.
Best Answer
Look into Fourier-Motzkin:
http://en.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_elimination