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.

I have a matrix $A \in \mathbb{R}^{n \times n}$ such that its elements are all non-negative values.

I know that for any $k$, $A^k$ has elements on the diagonal which are smaller or equal to 1.

Can I show that the largest eigenvalue of $A$ is smaller than 1? I am pretty sure that's true, but I am not completely sure.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

The largest eigenvalue could be equal to $1$ (e.g. if $A$ is upper triangular with at least one $1$ on the diagonal). It could be complex with absolute value $1$ (e.g. for a permutation matrix). But it can't be greater than $1$ in absolute value. This follows from the Perron-Frobenius theorem. First, replacing $A$ by $A^p$ if necessary, we can assume $A$ is aperiodic. Next, assume $A$ is irreducible (otherwise look at each irreducible component separately). If $\lambda$ is the Perron eigenvalue, there are positive vectors $u$ and $v$ such that $A^n - \lambda^n u v^T = o(\lambda^n)$. In particular, if $\lambda > 1$ every entry of $A^n$ goes to $+\infty$ as $n \to \infty$.

share|improve this answer
    
thank you very much! –  kloop Sep 30 '12 at 3:52
    
something is strange here: even if the diagonal elements of $A^k$ are larger than 1, but bounded, your proof still goes through. I find it quite odd. (Though, maybe it is impossible to have $A^k$ on the diagonal larger than 1, but bounded for all $k$, so it might be a vacuous statement.) –  kloop Sep 30 '12 at 16:45
    
also, what kind of constraint on the diagonal of $A$ might be required to show that the largest eigenvalue is strictly smaller than 1? What if the diagonal elements are strictly smaller than 1? –  kloop Sep 30 '12 at 17:21
    
For a nonnegative matrix $A$, $(A^n)_{jj} \ge (A_{jj})^n$. So if $A$ has a diagonal element $> 1$, that diagonal element in $A^n$ goes to $+\infty$ as $n \to \infty$. –  Robert Israel Sep 30 '12 at 18:48
    
The largest eigenvalue (in absolute value) is strictly less than $1$ iff the diagonal entries of $A^n$ all go to $0$ as $n \to \infty$. –  Robert Israel Sep 30 '12 at 18:52

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.