# What kind of matrix $A$ satisfies $Ax\geq 0\Rightarrow x\geq 0$?

$A\in \mathbb{R}^{n\times n}$ is an n-by-n matrix. $x=(x_1,x_2,\ldots ,x_n)\in \mathbb{R}^n$ is a vector. $x\geq 0$ means $x_i\geq 0,\forall i$.

Q1: When $A$ satisfies what conditions, $\forall x\in\mathbb{R}^n ,x\geq 0\Rightarrow Ax\geq 0$?

Q2: When $A$ satisfies what conditions, $\forall x\in\mathbb{R}^n ,Ax\geq 0\Rightarrow x\geq 0$?

Q1 is solved by Martin Argerami(The matrix's entries are all positive). But what are the matrices in Q2?

In Q2, the answer is not "entries all positive". The counterexample is $A=\begin{pmatrix} 1 & 1 \\ 1 & 1\end{pmatrix}$, $A\begin{pmatrix} -1 \\ 2 \end{pmatrix}\geq 0$.

Let's see an example $A=\begin{pmatrix} 2 & -1 \\ -1 & 2 \end{pmatrix}$.$A\begin{pmatrix} x \\ y \end{pmatrix} \geq 0\Rightarrow x\geq 0,y\geq 0$. So $A$ is in answer to Q2. What general properties of matrix $A$ would ensure Q2 be satisfied?

Another obvious class of matrix in Q2 is diagnoal matrices with positive diagonal entries.

Q2 is settled by Robert Israel($A^{-1}$ has entries all positive).

• Maybe try using $z = x-y$, so $z \geq 0 \Rightarrow Az \geq 0$? – Stefan Nov 16 '12 at 21:02
• I'm asking matrix A must satisfy what conditions so that $x\geq 0\Rightarrow Ax\geq 0$. – user33869 Nov 16 '12 at 21:06

## 3 Answers

For $Ax \ge 0$ implies $x \ge 0$, a necessary and sufficient condition is that $A$ is invertible and all elements of $A^{-1}$ are nonnegative.

Proof: If all elements of $A^{-1}$ are nonnegative, then $Ax \ge 0$ implies $x = A^{-1} (A x) \ge 0$.

Conversely, if $A$ is not invertible, there is $v \ne 0$ with $Av = 0$, and either $v$ or $-v$ has a negative entry but $Av = A(-v) = 0 \ge 0$. If $A$ is invertible and $(A^{-1})_{ij} < 0$, then take $x = A^{-1} e_j$ so that $x_i < 0$, but $A x = e_j \ge 0$.

EDIT: to the added question about diagonally dominant matrices, the answer is no. For example, $$\pmatrix{2& 1\cr 0& 2\cr}$$ is diagonally dominant, but its inverse has a negative entry.

• I just realized that. Your explanation is very helpful. Thank you. – user33869 Nov 16 '12 at 22:26
• This kind of matrix is actually well known. They are called M matrix. But I didn't find anyone characterizing M matrix like here how you did. – user33869 Nov 17 '12 at 3:33

If you question is which matrices $A$ will make $Ax\geq0$ for every $x\geq0$, then the answer is all matrices such that all their entries are nonnegative (we can write that as $A\geq0$).

Indeed, if $Ax\geq0$, for all $x$, then let $e_j=(0,\ldots,0,1,0,\ldots,0)$ where the $1$ is in the $j^{\rm th}$ place. Then $0\leq Ae_j=(a_{1j},a_{2j},\ldots,a_{nj})$, so every entry in the column $j$ of $A$ is non-negative. As $j$ was arbitrary, $A\geq0$.

Conversely, if $A\geq0$ and $x\geq0$, then the $j^{\rm th}$ entry of $Ax$ is $\sum_{k}a_{jk}x_k$. As every term in the sum is non-negative, so is the sum. So every entry of $Ax$ is non-negative, i.e. $Ax\geq0$.

• Thank you. Your answer is perfect. But I realize I'm not asking what I really want to ask so I add a slightly different question. – user33869 Nov 16 '12 at 22:09
• Indeed, the second question looks a lot more interesting than the first. – Martin Argerami Nov 16 '12 at 22:16

Let $A_i= (A_{i1}, \cdots ,A_{in})$ the $i=1,\dots, n$ line of $A$. Then multiplication matrix ruler $Ax=(\langle A_{i1},x \rangle , \cdots ,\langle A_{in},x \rangle)$. Here $\langle , \rangle$ is the inner product of $\mathbb{R}$. Then $Ax\geq 0$ if, only if, $\langle A_{i1},x \rangle \geq 0, \cdots ,\langle A_{in},x \rangle \geq 0.$

• Well, of course this is correct. Let me ask you another question, how is this type of matrix related to positive definite matrix? – user33869 Nov 16 '12 at 21:13