Determining existence of a solution for a system of linear inequalitiesI have a set of vectors v 1 , v 2 , . . . , v m ∈ R n and I want to know if there exists a nonzero vector x such that x ⋅ v i ≤ 0 for any i. This is the same as saying the equation x T V ≦ 0 has a nonzero solution, where V is an n × m matrix whose columns are v i .

Question

Determining existence of a solution for a system of linear inequalitiesI have a set of vectors         v    1    ,        v    2    ,  .  .  .  ,        v    m    ∈        R    n   and I want to know if there exists a nonzero vector   x such that   x  ⋅        v    i    ≤  0 for any   i. This is the same as saying the equation         x    T    V  ≦  0 has a nonzero solution, where   V is an   n  ×  m matrix whose columns are         v    i  .

Johnathan Morse · Accepted Answer

Sounds similar to Farkas&#039;s lemma. In order to prove that your problem has a solution, you must show that the problem  (  P  )    A      x    _    =      b    _    ,        x    _    ≥      0    _  has no solution (in your case       b    _    =      0    _   and   A  =  V). To this end, you can use the simplex method to verify that there is no admissible solution to problem (  (  P  )).Edit: this is how you use Linear Programming (LP) to determine if there is a feasible solution. Consider the LP problem  min  f  (      y    _    )  =  ∑      y    i        s  .  t  .  A      x    _    +      y    _    =      b    _          x    i    ≥  0  ,      y    i    ≥  0  ,      b    i    ≥  0Then, if (one of) the optimal solution(s) verifies   f  (      y    _    )  =  0, then that means that       y    i    =  0 for all i, that is, your original system is feasible. This is the first phase of the so called two-phases simplex method, where you try to determine an initial solution for a LP problem. Notice that this problem (the first phase) always has the trivial initial solution       y    _    =      b    _  .

Nickolas Taylor · Accepted Answer

An alternative approach based on Stiemke&#039;s theorem would involve the solution of a single somewhat larger LP.Solve the LP   max  zSubject to  V  y  =  0      y      i    ≥  z  ,  i  =  1  ,  2  ,  …  ,  nIf the optimal solution has   z  =  0, then   V  y  =  0,   y  &amp;gt;  0 has no solution.

Determining existence of a solution for a system of linear inequalities I have a set of vectors

Answered question

Answer & Explanation

New Questions in Algebra I