<blockquote>
  <p>How can this system be solved without using linear programming?</p>
</blockquote>

<p>It cannot.</p>

<p>Your problem is the linear feasibility problem in the standard form, with an extra condition that the constraint matrix is sparse.  Now note:</p>

<p>(1) It is well-known that linear programming is equivalent to the linear feasibility problem in the standard form.</p>

<p>(2) You can easily convert a linear feasibility problem in the standard form to one with the extra condition that each row of the constraint matrix has at most three nonzero elements.  For example, decompose <i>w</i>−<i>x</i>+<i>y</i>−<i>z</i>=<i>b</i> into <i>w</i>+<i>y</i>−<i>t</i>=0 and <i>t</i>−<i>x</i>−<i>z</i>=<i>b</i>, where <i>t</i> is a fresh nonnegative variable.  (The detail is left as an exercise.)</p>

<p>These together mean that an algorithm for your problem can be used to solve the linear programming.  Equivalently, you cannot hope for an essentially simpler algorithm for your problem than an algorithm for linear programming.</p>

CC BY-SA 3.0
2012-07-18T22:05:47.803Z
2012-07-19T10:57:31.383Z
2012-07-19T10:57:31.383Z
Tsuyoshi Ito
<p>Consider the following system of inequalities:</p>

<p>$Ax=b$;
$x\geq 0$;</p>

<p>A is a $m\times n$ (non-square) and sparse matrix in which some part of entries are rational. a) How feasibility of this system can be checked without using linear programming? 
b) Is the ellipsoid method useful for checking feasibility of the corresponding polyhedral?</p>

CC BY-SA 3.0
2012-07-18T17:49:28.577Z
In general (for arbitrary $A$), your problem is equivalent to linear programming.
Mahdi Cheraghchi
CC BY-SA 3.0
2012-07-18T17:57:04.727Z
Yes, it seems so. But, I need something fast.
Star
CC BY-SA 3.0
2012-07-18T19:18:22.443Z
Why would you use linear programming to do this? Did you mean factorization ([QR](https://en.wikipedia.org/wiki/Qr_factorization), [LU](https://en.wikipedia.org/wiki/Lu_factorization))?
Gopi
CC BY-SA 3.0
2012-07-18T19:57:07.487Z
This forum is dedicated to Theoretical Computer Science question. Maybe you should try asking your question on [cs.se] where it may be more welcolmed by the community?
Gopi
CC BY-SA 3.0
2012-07-19T04:55:08.737Z
@Gopi this IS linear programming, factorization won't help by itself.
Sasho Nikolov
CC BY-SA 3.0
2012-07-19T08:18:05.980Z
Wait, you wish to find x? Not maximize or minize something? I would do $A=QR$, then $Rx=Q^{\star}b$, then you have a triangular system to solve to find the $x_i$'s? (With the constraint $x \geq 0$, but indeed, then this constraint is not necessarily respected because the factorization is not unique. My bad)
Gopi
CC BY-SA 3.0
2012-07-19T15:29:35.193Z
@Gopi you were *this* close to a strongly polynomial time algorithm for linear programming ;)
Sasho Nikolov
CC BY-SA 3.0
2012-07-20T08:38:21.977Z
@SashoNikolov, Easy! =)
Gopi
<ds.algorithms><optimization><linear-algebra><linear-programming>
Solving a system of linear inequations
Star
# Solving a system of linear inequations

(Asked by: username_0 on 2012-07-18)

Consider the following system of inequalities:

$Ax=b$;
$x\geq 0$;

A is a $m\times n$ (non-square) and sparse matrix in which some part of entries are rational. a) How feasibility of this system can be checked without using linear programming?
b) Is the ellipsoid method useful for checking feasibility of the corresponding polyhedral?

**Tags:** ds.algorithms, optimization, linear-algebra, linear-programming

> **Comments:**
> **username_1**: In general (for arbitrary $A$), your problem is equivalent to linear programming.  
> **username_0**: Yes, it seems so. But, I need something fast.  
> **username_2**: Why would you use linear programming to do this? Did you mean factorization ([QR](https://en.wikipedia.org/wiki/Qr_factorization), [LU](https://en.wikipedia.org/wiki/Lu_factorization))?  
> **username_2**: This forum is dedicated to Theoretical Computer Science question. Maybe you should try asking your question on [cs.se] where it may be more welcolmed by the community?  
> **username_3**: @username_2 this IS linear programming, factorization won't help by itself.  
> **username_2**: Wait, you wish to find x? Not maximize or minize something? I would do $A=QR$, then $Rx=Q^{\star}b$, then you have a triangular system to solve to find the $x_i$'s? (With the constraint $x \geq 0$, but indeed, then this constraint is not necessarily respected because the factorization is not unique. My bad)  
> **username_3**: @username_2 you were *this* close to a strongly polynomial time algorithm for linear programming ;)  
> **username_2**: @SashoNikolov, Easy! =)  

---

## 1 answers

### Answer by username_4 on 2012-07-18. Score: 9

> How can this system be solved without using linear programming?

It cannot.

Your problem is the linear feasibility problem in the standard form, with an extra condition that the constraint matrix is sparse. Now note:

(1) It is well-known that linear programming is equivalent to the linear feasibility problem in the standard form.

(2) You can easily convert a linear feasibility problem in the standard form to one with the extra condition that each row of the constraint matrix has at most three nonzero elements. For example, decompose *w*−*x*+*y*−*z*=*b* into *w*+*y*−*t*=0 and *t*−*x*−*z*=*b*, where *t* is a fresh nonnegative variable. (The detail is left as an exercise.)

These together mean that an algorithm for your problem can be used to solve the linear programming. Equivalently, you cannot hope for an essentially simpler algorithm for your problem than an algorithm for linear programming.


---

