Inversion of a matrix in a system of linear inequalitiesI would like to know if someone knows sufficient conditions on A ∈ R n × n and b ∈ R n such that for all x ∈ R n : A x ≤ b ⇒ x ≤ A − 1 b or x ≥ A − 1 b . A is assumed to be positive definite.

Question

Inversion of a matrix in a system of linear inequalitiesI would like to know if someone knows sufficient conditions on   A  ∈        R          n      ×      n       and   b  ∈        R      n   such that for all   x  ∈        R      n  :  A  x  ≤  b  ⇒  x  ≤      A          −      1        b   or   x  ≥      A          −      1        b  .  A is assumed to be positive definite.

Ullveruxqte · Accepted Answer

If   A is an M-matrix (all symmetric M-matrices are SPD but not all SPD matrices are M-matrices), then   A  z  ≥  0 implies   z  ≥  0. So if   y  :=      A          −      1        b, then   b  −  A  x  =  A  (  y  −  x  )  ≥  0 implies   y  −  x  ≥  0 and hence   x  ≤      A          −      1        b. This is simply due to the fact that M-matrices have nonnegative inverses.If   A is SPD,   A  x  ≤  b and   x for some   x means that   A  z  ≥  0 and   z  ≤  0 for some   z. But then       z    T    A  z is a sum of nonpositive numbers so       z    T    A  z  ≤  0. Since A is SPD, this is possible if only if   z  =  0, that is,   A  x  =  b.

Inversion of a matrix in a system of linear inequalities I would like to know if someone knows suff

Answered question

Answer & Explanation

New Questions in Algebra I