Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$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).

share|improve this question
    
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 3

up vote 7 down vote accepted

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.

share|improve this answer
    
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$.

share|improve this answer
    
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. $

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.