25
$\begingroup$

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.

$\endgroup$

5 Answers 5

14
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$ Oct 18, 2011 at 19:33
  • $\begingroup$ Could you please explicate the claim "since $A$ is real and $\mu$ is a simple eigenvalue, $\lambda$ must be real"? $\endgroup$
    – Hans
    Mar 4, 2018 at 23:02
  • $\begingroup$ Since $A$ is real, if $\lambda$ is an eigenvalue of $A$, so is $\overline{\lambda}$. Since $\left|\overline{\lambda}^q\right| = \left|\lambda^q\right| = \mu$, we must have $\overline{\lambda}^q = \mu$. But if $\overline{\lambda} \ne \lambda$, $A^q$ has at least two linearly independent eigenvectors for eigenvalue $\mu$, namely eigenvectors of $A$ for $\lambda$ and $\overline{\lambda}$. $\endgroup$ Mar 5, 2018 at 7:49
9
$\begingroup$

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

This link works:

http://repository.uwyo.edu/ela/vol9/iss1/21/

The paper is:

Naqvi, Sarah Carnochan; McDonald, Judith J., The combinatorial structure of eventually nonnegative matrices, Electron. J. Linear Algebra 9, 255-269 (2002). ZBL1039.15003.

$\endgroup$
2
  • $\begingroup$ Doc not found. Can you update the link if possible? Thanks. $\endgroup$
    – 2rd_7
    Nov 19, 2017 at 19:51
  • $\begingroup$ @2rd_7 Here you go. $\endgroup$
    – Igor Rivin
    Nov 19, 2017 at 22:15
8
$\begingroup$

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.

$\endgroup$
0
8
$\begingroup$

This answer gives some insight on eventually nonnegative matrices, which differs from the original question regarding power nonnegative matrices.

For results on power positive matrices, see Brauer [Duke Math. J. 28 1961 439–445; MR0130262]; for results on nonreal power nonnegative matrices see Tudisco et al. [Linear Algebra Appl. 471 (2015), 449–468; MR3314347].

The situation for the former is well-known for eventually positive matrices. Let $\rho(A)$ denote the spectral radius of $A$. Handelman [J. Operator Theory 6 (1981), no. 1, 55–74; MR0637001], Noutsos [Linear Algebra Appl. 412 (2006), no. 2-3, 132–153; MR2182957], and Johnson and Tarazaga [Positivity 8 (2004), no. 4, 327–338; MR2117663] showed that a real matrix $A$ is eventually positive if and only if $\rho(A)$ is a positive simple eigenvalue satisfying $$ |\lambda| < \rho(A) $$ for every $\lambda \in \sigma(A)$, and there are positive left and right eigenvectors $u$ and $v$ corresponding to $\rho(A)$ (this is known as the strong Perron Frobenius property).

It is also known that power index of $A$, which is the smallest positive integer $q$ such that $A^k$ is positive for all $k \ge q$ can be arbitrarily large. This is because, under very mild assumptions, arbitrarily large roots of eventually positive matrices remain eventually positive (see McDonald et al. [Matrix roots of eventually positive matrices. Linear Algebra Appl. 456 (2014), 122–137; MR3223894]). thm3.5

Another important work on eventually nonnegative matrices is by McDonald and Zaslavsky [A characterization of Jordan canonical forms which are similar to eventually nonnegative matrices with the properties of nonnegative matrices. Linear Algebra Appl. 372 (2003), 253–285; MR1999150].

It is, however, known that if $A$ is a primitive matrix, then $n^2 - 2n+2$ is a sharp upper bound on the index of primitivity (see Chapter 8 of Matrix Analysis by Horn & Johnson).

$\endgroup$
8
  • 3
    $\begingroup$ The characterisation you gave at the beginning of your answer is only correct for symmetric matrices; for non-symmetric matrices you also need to assume that the left eigenvector is positive. Consider the matrix $A := \begin{pmatrix} 2 & -1 \\ 2 & -1 \end{pmatrix}$; then $A$ has spectral radius $1$, this is a simple eigenvalue and $(1,1)$ is a corresponding right eigenvector. But $A$ is a projection and thus not eventually positive. $\endgroup$ Mar 3, 2018 at 9:42
  • $\begingroup$ Indeed; I always forget to leave that out! $\endgroup$ Mar 3, 2018 at 14:50
  • $\begingroup$ I think it's very good to have all the references you gave in an answer now; the literature on eventually positive matrices is of course very relevant here. Still, I don't see how what you wrote contradicts Robert Isreal's answer. $\endgroup$ Mar 4, 2018 at 10:35
  • $\begingroup$ @JochenGlueck: see my new edit. $\endgroup$ Mar 4, 2018 at 18:50
  • 1
    $\begingroup$ Is your concern about the sign of the entries of the left and right eigenvector? Robert Israel wrote that all entries of the left and the right eigenvector are non-zero and have all the same sign. That's equivalent to saying that the left and the right eigenvector are either both positive or both negative. But maybe I overlooked something or I'm misinterpreting something? $\endgroup$ Mar 4, 2018 at 20:10
0
$\begingroup$

If so, can we compute this exponent $q$ quickly?

The answer to this question should be `no'. Under mild conditions, a matrix will possess a $p$th root for all values of $p$. Thus, since an arbitrarily large matrix root can be taken, it follows that $q$ can be arbitrarily large.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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