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.

Improve this question
$\endgroup$

5 Answers 5

Reset to default
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.

Improve this answer
$\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$
    – Richard Stanley
    Commented 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
    Commented 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$
    – Robert Israel
    Commented 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Doc not found. Can you update the link if possible? Thanks. $\endgroup$
    – 2rd_7
    Commented Nov 19, 2017 at 19:51
  • $\begingroup$ @2rd_7 Here you go. $\endgroup$
    – Igor Rivin
    Commented 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.

Improve this answer
$\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).

Improve this answer
$\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$
    – Jochen Glueck
    Commented Mar 3, 2018 at 9:42
  • $\begingroup$ Indeed; I always forget to leave that out! $\endgroup$
    – Pietro Paparella
    Commented 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$
    – Jochen Glueck
    Commented Mar 4, 2018 at 10:35
  • $\begingroup$ @JochenGlueck: see my new edit. $\endgroup$
    – Pietro Paparella
    Commented 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$
    – Jochen Glueck
    Commented 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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .