4

Under what conditions on $A$ does $Ax \geq Ay $ imply $x \geq y$?

In the context of a larger proof, I have an upper triangular matrix $A$ and two nonzero vectors $x$ and $y$. I have shown that $Ax \geq Ay $, and it seems that this implies $x \geq y$ if $A$ is nonsingular and its entries are nonnegative.

However, I wonder if I can make a stronger statement here. In particular, even if $A$ is singular, if its entries are nonnegative and $x$ and $y$ are not in the nullspace, then I believe the statement holds. Alternative, if $A$ is nonsingular and has large, positive constants on the diagonal, then negative entries in the triangular region make no difference to $Ax$.

This leads me to suspect that a sufficient condition is that $A$ is positive definite. Then $A$ "behaves like" a positive scalar, in the sense that we can multiply by $A^{-1}$ on both sides of $Ax \geq Ay$ to obtain the statement. Is this the case? How do I show this formally?

Max
  • 1,257

1 Answers1

2

(This answer assumes $A$ is a square matrix.)

By linearity, its equivalent to ask when $Ax \geq 0$ implies $x\geq 0.$ If $A$ is invertible then it is equivalent to ask when $x\geq 0$ implies $A^{-1}x\geq 0$. And in fact if your matrix $A$ has this property, it must be invertible! As it fails to be invertible then there's some $x$ so that $x\neq 0$ but $Ax = 0.$ So $Ax = 0 \geq 0$ implies $x \geq 0.$ But then $-x \leq 0,$ but $A(-x) = -Ax = -0 \geq 0$ still, so we get again that $-x \geq 0,$ contradicting that $x \neq 0.$

This last question about the inverse is easier to answer. For $e_i$ the standard basis vectors of $\mathbb{R}^n,$ since $e_i \geq 0$ we need $A^{-1}e_i \geq 0$ for this to be true. And indeed, if $A^{-1}e_i \geq 0$ for each $i$ then the matrix $A$ has this property, as for any $v = \sum_i \lambda_i e_i$ if $v \geq 0$ then $A^{-1}v = \sum_i \lambda_i A^{-1}e_i \geq 0$ clearly, since each $\lambda_i\geq 0.$

In particular, your positive definite conjecture is false! Take $A = \begin{pmatrix} 3 & 2 \\ 2 & 3\end{pmatrix}.$ Then $A$ is positive definite, but $A^{-1}(1,0) = (3/5, -2/5)$ is not positive.

  • 1
    So, in short, if $A$ is invertible and the entries of $A^{-1}$ are nonnegative, then $Ax \geq 0 \implies x \geq 0$? (Noting that $A^{-1} e_i = A_{.i}^{-1}$). – Max May 15 '21 at 01:30
  • (Perhaps you meant to write "As if it fails to be invertible then...") – Calvin Khor May 15 '21 at 01:43