Theorem about positive matrices

This is just a simple consequence of Perron-Frobenius theorem. We can prove something slightly more general:

Let $A,B$ be two nonnegative square matrices. If one of the following cases holds, then $\rho(A)<\rho(A+B)$:

  • $A$ is irreducible (in particular, when $A>0$ entrywise) and $B$ is nonzero;
  • $B$ is irreducible.

Let $(\rho(A),v)$ be a right Perron eigenpair of $A$ and $(\rho(A+B),w)$ be a left Perron eigenpair of the $A+B$. Then $$ \rho(A+B) w^Tv = w^T(A+B)v = \rho(A) w^Tv + w^TBv\tag{1} $$ and in turn $$ \left(\rho(A+B)-\rho(A)\right) w^Tv = w^TBv.\tag{2} $$ Now in case (a), both $v$ and $w$ positive (because $A$ and $A+B$ are irreducible). Hence $Bv$ is nonnegative but nonzero and $w^TBv,\ w^Tv$ are positive. So, $(2)$ gives $\rho(A+B)-\rho(A)>0$.

In case (b), $w>0$ because $A+B\ge0$ is irreducible. Hence $w^TB>0$ too because $B$ is irreducible. It follows that $w^TBv$ and $w^Tv$ are still positive (because $v$ is nonnegative but nonzero) and again, $(2)$ gives $\rho(A+B)-\rho(A)>0$.


For (almost) all positive vectors $x$, the Power iterations do work, and we have $$\lambda_\max=\lim_{k\rightarrow\infty}\left(\|A^kx\|/\|x\|\right)^{1/k}$$ which shows that $\lambda_\max$ can not decrease as entries of $A$ increase. If $A'$ is obtained from $A$ by increasing every entry, we get $A'>(1+\varepsilon)A>A$, and your result follows.


I recently came across the following (beautiful) result which is slightly improving the answer of @user1551. The following results come from the book Nonnegative Matrices in the Mathematical Sciences of Abraham Berman and Robert J. Plemmons:

Corollary 1.5 (p.27):
Let $A,B$ be nonnegative square matrices.
- If $0\leq A \leq B$, then $\rho(A)\leq \rho(B)$.
- If $0\leq A \leq B$, $A\neq B$ and $A+B$ is irreducible, then $\rho(A)<\rho(B)$.

Note 1: Here $A\leq B$ means $A_{i,j}\leq B_{i,j}$ for every $i,j$.

Note 2: If $0\leq A \leq B$, $A\neq B$ and $A+B$ is reducible, then both can occur, i.e. $\rho(A)=\rho(B)$ or $\rho(A)<\rho(B)$. Indeed, let $U,V,W\in\Bbb R^{2\times 2}$ with $$ U =\begin{pmatrix} 1& 0 \\ 0 & 1 \end{pmatrix}, \quad V =\begin{pmatrix} 1& 1 \\ 0 & 1 \end{pmatrix}, \quad W =\begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix}.$$ Then $U\leq V \leq W$, $U\neq V$, $V\neq W$, $U+V$ is reducible, $V+W$ is reducible and $\rho(U)=\rho(V)<\rho(W)$.

Note 3: The following result shows that the answer of @user1551 is implied by Corollary 1.5.

Corollary 1.10 (p.28):
Let $A,B$ be nonnegative square matrices. If $A$ is irreducible, then $A+B$ is irreducible.

Finally, to see how this also improves the answer to your question, note that the matrix $V$ above is reducible as well as the matrix $$V'=\begin{pmatrix}0 & 0 \\ \epsilon & 0 \end{pmatrix}.$$ However, Corollary 1.5 implies that $\rho(V)<\rho(V+V')$ be cause $V+V'$ is strictly positive (and thus irreducible).