Suppose I have two systems of n homogeneous inequalities of k variables: A x ≥ 0 and B z ≥ 0 ,where both A and B are n × k matrices such that for any i = 1 , … , n, and j = 1 , … , k we have | a i j − b i j | ≤ ϵ, where ϵ &gt; 0 is very small.How close are solutions of systems of homogeneous linear inequalities with close coefficients?

Question

Suppose I have two systems of   n homogeneous inequalities of   k variables:  A  x  ≥  0 and   B  z  ≥  0  ,where both   A and   B are   n  ×  k matrices such that for any   i  =  1  ,  …  ,  n, and   j  =  1  ,  …  ,  k we have   |      a          i      j        −      b          i      j        |  ≤  ϵ, where   ϵ  &amp;gt;  0 is very small.How close are solutions of systems of homogeneous linear inequalities with close coefficients?

morssiden5g · Accepted Answer

Look at the case where   A has a large condition-number.Step 1. For example   A  =      (                            0                          1                                      u                          −          1                      )    ,  B  =      (                            −          2          u                          1                                      u                          −          1                      )   where u is a small   &amp;gt;  0 number; take       x    0    =  (  1  ,  0  ). Then   |  |      x    0    −      z    0    |  |  ≥  1.Step 2. The above example shows that   ϕ does not exist.Indeed, let   ϵ  &amp;gt;  0. If   u  =  ϵ  /  2, then   |      a          i      ,      j        −      b          i      ,      j        |  ≤  ϵ. One has   A      x    0    ≥  0  ,  |  |      x    0    |  |  =  1;   B  z  ≥  0 where   z  =  [  x  ,  y      ]    T   is equivalent to   u  x  ≥  y  ≥  2  u  x, that implies   x  ≤  0  ,  y  ≤  0. Thus, if   B      z    0    ≥  0, then   |  |      x    0    −      z    0    |  |  ≥  1 and finally   ϕ  (  ϵ  )  ≥  1.Step 3. I think that a correct formulation of your problem is as follows.Let   A  ∈      M          n      ,      k       where   rank  (  A  )  =  n  ≤  k. Show that there are   a  &amp;gt;  0 and a function   ϕ  :  t  ∈  (  0  ,  a  )  →  (  0  ,  +  ∞  ) that tends to   0 with   t, s.t. for every   B  ∈      M          n      ,      k        ,      x    0    ∈        R    k   satisfying   |  |  A  −  B  |  |  &amp;lt;  a  ,  A      x    0    ≥  0  ,  |  |      x    0    |  |  =  1, there is       z    0    ∈        R    k   s.t.   A      z    0    ≥  0  ,  |  |      x    0    −      z    0    |  |  ≤  ϕ  (  |  |  A  −  B  |  |  ).

Grimmingch · Accepted Answer

I see it now. Thank you.

Suppose I have two systems of n homogeneous inequalities of k variables: A x &#x2265

Answered question

Answer & Explanation

New Questions in Algebra I