Using linear algebra (e.g. matrix) methods to solve a system of linear inequalities

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.

• this is what linear programming all about !! – alkabary Jun 3 '15 at 1:40
• Yeah, but I had trouble finding resources for solving this inequalities question numerically. Everyone seems to only want to talk about the $Ax=b$ case. – Izzhov Jun 3 '15 at 1:42
• A relevant article: Avis and Kaluzny, "Solving inequalities and proving Farkas's lemma made easy". – user21467 Jun 3 '15 at 2:07
• Like alkabary said: Linear Programming en.wikipedia.org/wiki/Linear_programming That doesn't mean Linear Algreba. Also en.wikipedia.org/wiki/Simplex_algorithm for a numerical method. – muaddib Jun 3 '15 at 2:08
• That's not what I'm looking for. That solves $Ax=b$ with each $x_i>0$. I'm looking for the solution of $Ax>b$, i.e. every element of $Ax$ is greater than every element of $b$. – Izzhov Jun 3 '15 at 2:12

1 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:

• Linear algebra is for $Ax=b$
• Linear programming is for $Ax=b$, where $x\geq0$

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

• The second thing you wrote is not what I'm looking for. $Ax=b$ with $x>0$ is not the same thing as $Ax>b$. Reread my question. – Izzhov Jun 3 '15 at 2:14
• I have already in my question repeated what you are asking for. Do you see that? I have not misread your question. These two equations are both forms of linear programming problem. You can convert from one form to another. Can you explain why you need the strict inequality in your application? – Gus Jun 3 '15 at 2:19
• I fail to see how you can convert from $Ax > b$ to $Ax = b$ with $x \geq 0$. I need the strict inequality because in my application, $b$ is actually zero on the right hand side, so if the equation were $Ax \geq 0$, it would be trivially solved by $x=0$. I'm mainly just trying to see if any solution exists to my problem, I'm not as interested in finding the whole space of solutions or finding a minimum or maximum among them. – Izzhov Jun 3 '15 at 2:22
• Also, in my original problem that I stated in the question. I don't want the constraint $x \geq 0$. $x$ may have negative entries in my problem. – Izzhov Jun 3 '15 at 2:25
• Let me state it a different way. If you give me $A,b$ corresponding to $Ax\geq b$, I can give you a $C,d$ such that a solution of $y$ in $Cy=d, y\geq 0$ corresponds to a solution of $x$ in your original problem. If you want to avoid the trivial solution, then solve $Ax \geq \epsilon\mathbf{1}$ where $\mathbf{1}$ is an appropriately sized vector of $1$s and $\epsilon$ is some very small number greater than zero. – Gus Jun 3 '15 at 2:32