Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The following question came up today during a discussion:

Suppose $A$ is an $n \times n$ real matrix. Is there some way to tell whether there exists an integer $q > 0$ such that $A^q$ is elementwise nonnegative? If so, can we compute this exponent $q$ quickly?

Thanks for your insights.

share|improve this question

3 Answers 3

Here is one case: Suppose $A$ has a unique eigenvalue $\lambda$ of greatest absolute value that has algebraic multiplicity 1, with left and right eigenvectors $u^T$ and $v$ having all entries nonzero, normalized so $u^T v = 1$. Since $A$ is a real matrix, its complex eigenvalues come in complex-conjugate pairs, so $\lambda$ must be real. Then $A^q = \lambda^q v u^T + o(|\lambda|^q)$ as $q \to \infty$. If all entries of $u^T$ and $v$ have the same sign, then all entries of $A^q$ are positive for all sufficiently large $q$ (if $\lambda > 0$) or all sufficiently large even $q$ (if $\lambda < 0$). If some entries of $u^T$ or $v$ have different signs, there will be entries of $A^q$ with different signs for all sufficiently large $q$, and therefore for all positive integers $q$ (if the elements of $A^q$ all have the same sign, so do the elements of $A^{kq}$ for all positive integers $k$).

EDIT: Here's a partial converse. By the Perron-Frobenius theorem, if $A^q$ has all its entries strictly positive, then $A^q$ has a positive eigenvalue $\mu$ which is greater in absolute value than all other eigenvalues, and is simple, with left and right eigenvectors $u^T$ and $v$ having all entries strictly positive. Since the eigenvalues of $A^q$ are the $q$'th powers of eigenvalues of $A$, there must be one eigenvalue $\lambda$ of $A$ with $\lambda^q = \mu$, also having left and right eigenvectors $u^T$ and $v$. Since $A$ is real and $\mu$ is a simple eigenvalue, $\lambda$ must be real, and we are in the situation of the previous paragraph.

Matters can be somewhat more complicated if $A^q$ is nonnegative but never all strictly positive.

share|improve this answer
    
Thanks for your answer and insights Robert. –  Suvrit Oct 18 '11 at 18:24
1  
I believe that the following is still open: given an $n\times n$ integer matrix $A$ and $1\leq i,j\leq n$, is it decidable whether there is some $q\geq 1$ for which $(A^q)_{ij}=0$? See citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.155.2606. This suggests that the question posed here might also not be known to be decidable, but I could be wrong about this. –  Richard Stanley Oct 18 '11 at 19:33

The paper "On an inverse problem for nonnegative and eventually nonnegative matrices" gives necessary and sufficient conditions on the spectrum of eventually nonnegative matrices. This is not a full answer to your question.

share|improve this answer
    
Thanks for the pointer! –  Suvrit Oct 18 '11 at 18:25

This paper is fairly interesting, and has reasonably extensive references:

http://www.mat.ub.edu/EMIS/journals/ELA/ela-articles/articles/vol9_pp255-269.pdf

share|improve this answer
    
Thanks for that pointer Igor. –  Suvrit Oct 18 '11 at 18:24

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.