Suppose I have an element-wise inequality: A x ≥ b, where A is a rectangular matrix with full row rank, and x and b are appropriately sized column vectors. I need to check if the inequality holds to branch some code I'm writing.If I (thin) LQ decompose A, I have:where L is a lower triangular square matrix of full rank and Q is an orthogonal matrix.As it turns out, I need to calculate L − 1 b anyway, so my first thought was to calculate it and just check: Q x ≥ L − 1 bHowever, this doesn't necessarily work, as depending on exactly how the matrix A was decomposed, it might change the ≥ in to a ≤. For example, if A = 1, and we decompose it as L = − 1, Q = − 1, multiplying both sides by L − 1 switches the direction of the inequality.Under what circumstances will multiplying both sides of an inquality system by a matrix not change the direction of the inequality? My intuitive guess is that as long as the eigenvalues of the matrix are positive (that is, the matrix is positive definite), the inequality direction won't change. But I'm not sure how to prove/disprove that.

Question

Suppose I have an element-wise inequality:   A  x  ≥  b, where   A is a rectangular matrix with full row rank, and   x and   b are appropriately sized column vectors. I need to check if the inequality holds to branch some code I&#039;m writing.If I (thin) LQ decompose   A, I have:where   L is a lower triangular square matrix of full rank and Q is an orthogonal matrix.As it turns out, I need to calculate       L          −      1        b anyway, so my first thought was to calculate it and just check:  Q  x  ≥      L          −      1        bHowever, this doesn&#039;t necessarily work, as depending on exactly how the matrix   A was decomposed, it might change the   ≥ in to a   ≤. For example, if   A  =  1, and we decompose it as   L  =  −  1,   Q  =  −  1, multiplying both sides by       L          −      1       switches the direction of the inequality.Under what circumstances will multiplying both sides of an inquality system by a matrix not change the direction of the inequality? My intuitive guess is that as long as the eigenvalues of the matrix are positive (that is, the matrix is positive definite), the inequality direction won&#039;t change. But I&#039;m not sure how to prove/disprove that.

sleuteleni7 · Accepted Answer

In order that  M  x  ≥  bimplies  x  ≥      M          −      1        b      M          −      1       has to be non-negative element-wise, i.e. all elements in       M          −      1       have to be non-negative. The prove that this suffices is easy.Positive eigenvalues cannot help here. To see this consider  A  =      (                            1                          10                                      0                          1                      )    ,         A          −      1        =      (                            1                          −          10                                      0                          1                      )    ,     x  =      (                            1                                      1                      )    ,     b  =      (                            1                                      −          1                      )    .Then  A  x  =      (                            11                                      1                      )    ≥  bbut  x  ≱      A          −      1        b  =      (                            11                                      −          1                      )    .

Suppose I have an element-wise inequality: A x ≥ b , where A is

Answered question

Answer & Explanation

New Questions in Algebra I