Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
8  
There's a standard reduction which shows your question (1), testing whether there is a solution to a set of linear inequalities, is just as hard as finding the optimum, i.e., as hard as linear programming. Your question (2) is equivalent to both of these questions, since you can answer it by repeatedly solving a linear programming problem. As for practical algorithms, there are tons of linear programming packages out there. The best ones are expensive, but there are some decent free ones, and many mathematical software packages like MATLAB, Maple, Mathematica, have reasonable ones. –  Peter Shor Jul 17 '10 at 19:22
5  
Continuing my previous comment, if you want to see the reduction, question (1) is called the feasibility problem for linear programming, and you should be able to find the proof that it's equivalent to lienar programming by googling or looking in linear programming textbooks. –  Peter Shor Jul 17 '10 at 19:25
1  
Thanks Peter, that's helpful! –  Matthew Kahle Jul 23 '10 at 0:25
1  
to go along with Peter Shor's answer, may I also suggest using Octave or Scilab, which are open-source software packages with the same capabilities as Matlab and Mathematica (and also able to run some of the same Matlab scripts and functions with minimal changes) –  sleepless in beantown Oct 11 '10 at 5:46

2 Answers 2

These notes give you an answer to question 2, computing the dimension.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.