most recent 30 from http://mathoverflow.net 2013-05-23T09:44:27Z http://mathoverflow.net/feeds/question/30476 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/30476/solving-a-system-of-linear-inequalities-what-is-the-dimension-of-the-solution Matthew Kahle 2010-07-04T02:16:41Z 2010-10-11T05:22:16Z

<p>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 <em>inequalities</em> $A{\bf x} \leq {\bf b}$?</p> <p>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.</p> <p>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}$?</p> <p>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.</p> <p>I am especially interested in practical algorithms, but if you know any related theory that would be welcome as well.</p>

http://mathoverflow.net/questions/30476/solving-a-system-of-linear-inequalities-what-is-the-dimension-of-the-solution/30477#30477 Joseph Malkevitch 2010-07-04T02:31:58Z 2010-07-04T02:31:58Z

<p>Look into Fourier-Motzkin:</p> <p><a href="http://en.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_elimination" rel="nofollow">http://en.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_elimination</a></p>

http://mathoverflow.net/questions/30476/solving-a-system-of-linear-inequalities-what-is-the-dimension-of-the-solution/30478#30478 supercooldave 2010-07-04T02:39:43Z 2010-07-04T02:39:43Z

<p>These <a href="http://www.lehigh.edu/~tkr2/teaching/ie418/lectures/Lecture4.pdf" rel="nofollow">notes</a> give you an answer to question 2, computing the dimension. </p>