14
$\begingroup$

We will call a matrix positive matrix if all elements in the matrix are positive, and we will denote the largest eigenvalue with $\lambda_{\max}$, what is exist because of the Perron–Frobenius theorem.

Theorem. Let $A$ be a positive square matrix. If any element increases in the matrix then $\lambda_{\max}$ increases.

My questions.

1) Is there a name for this theorem and can anybody say books or papers what refer to it?

2) How to prove it?

$\endgroup$
  • $\begingroup$ It's easy to show if $A$ and the increased matrix $A'$ are symmetric: In that case, $\lambda_{\max}$ is then the operator norm $\|A\|$ and analogously for $A'$. The eigenvector $v$ belonging to $\lambda_{\max}$ has all $v_i > 0$, so $\|A'\| \geq \lambda_{\max} + ((A' - A)v, v) > \lambda_{\max}$. $\endgroup$ – anomaly Aug 24 '14 at 13:25
9
+150
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Note that your nice result can be slightly improved. $\endgroup$ – Surb Dec 12 '15 at 16:23
6
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Almost all? Can you/or someone else say a book or paper which write about this theorem? $\endgroup$ – user153012 Aug 27 '14 at 8:55
  • $\begingroup$ You can find detailed proof of the following statement by the link from the answer. If $A$ is a complex matrix with Jordan basis $v_1,\ldots,v_n$ and eigenvalues satisfying $|\lambda_1|>|\lambda_i|$ for any $i\neq1$, then, any vector $b=c_1v_1+\ldots+c_nv_n$ with $c_1\neq0$ satisfies $v_1=\lim_{t\rightarrow\infty}b_t$ with $b_0=b$ and $b_{t+1}=\frac{Ab_t}{\|A b_t\|}$. From this we get $|\lambda_1|=\lim_{t\rightarrow\infty}\left(\|A^tb\|/\|b\|\right)^{1/t}$ for almost all $b$. $\endgroup$ – user2097 Aug 27 '14 at 14:16
  • $\begingroup$ In fact the user2097's proof works when $A>0,A'\geq A$. The condition $A>0$ is necessary so that $\lambda_{max}$ is a simple eigenvalue. Let $||.||$ be a norm on $\mathbb{R}^2$. I am not sure that $||[1,2]^T||\leq ||[1,3]^T||$. Thus, in order to show that $\rho(A')\geq \rho(A)$, it is better to choose a standard norm as $||.||_1$. $\endgroup$ – loup blanc Sep 9 '14 at 10:35
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ It's nice to know the quoted results. +1 $\endgroup$ – user1551 Dec 13 '15 at 1:19
  • $\begingroup$ Thank you for the answer and for the reference. +1. Unfortunately the book doesn't contain an exact proof for "how is it a corollary", and also doesn't for the theorem above these corollarys. However there are analogous results related to cones with proofs. $\endgroup$ – user153012 Dec 13 '15 at 11:56
1
$\begingroup$

Your property follows easily the Collatz-Wieland formula, which is proved on wikipedia. In fact, that wikipedia page proves everything from scratch and provides references. So it should contain everything you're asking for.

How to deduce your property from the Collatz-Wieland formula : let $A=(a_{ij})$ and $B=(b_{ij})$ be two positive matrices, such that $a_{ij} \leq b_{ij}$ for every $i,j$. Define the Collatz-Wieland functions

$$ f_A(x_1,x_2,\ldots,x_n)=\min_{1\leq i\leq n,x_i\neq 0}\frac{\sum_{j=1}^n a_{ij}x_j}{x_i}, \ f_B(x_1,x_2,\ldots,x_n)=\min_{1\leq i\leq n,x_i\neq 0}\frac{\sum_{j=1}^n b_{ij}x_j}{x_i} $$

We deduce $f_A(x)\leq f_B(x)$ for every $x$, so the Perron root of $A$ is smaller than the Perron root of $B$, by the Collatz-Wieland formula.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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