Let $\lambda_1,\dots,\lambda_d$ be complex numbers that constitute the spectrum of a nonnegative integer matrix, and $P_1,\dots, P_d$ be complex polynoms, such that the sequence $$u_n=\Sigma_{i=1}^d P_i(n)\lambda_i^n$$ takes only real nonnegative values, i.e. $u_n\geq0, \forall n\in\mathbb N$.

I'm interested in the possible behaviours of $u_n$, and more precisely I would like to show the existence of an integer $k$ such that each sequence $(u_{nk+r})_{n\in\mathbb N}$ for $0\leq r\leq k-1$ is asymptotically equivalent to some $a_r n^{b_r}c_r^n$, where $a_r,b_r,c_r$ are real nonnegative constants depending on $r$.

For instance, $b_r=0$ and/or $c_r=1$are interesting cases that can happen.

Any hint would be appreciated, thanks !

What I tried

So I know that for reducible matrices, Perron-Froebenius theorem tells us that there is a real positive eigenvalue $\rho$ of maximal module, and that the other eigenvalues of maximal module are $\rho e^{\frac{ir\pi}{k}}$ with $0<r<k$. It shoud prevent counter-examples like the one from Gerald Edgar, but I'm missing the last argument to conclude. There are two problems in my opinions:

1) here the matrix is not necessarily irreducible,

2) the other eigenvalues (the ones that are not of maximal module) can also play a part.

Here is the most detailed paper I could find giving information about such eigenvalues, but I don't see how to use this information: The spectra of nonnegative integer matrix via formal power series.

  • $\begingroup$ Why do you believe that this is the asymptotic behavior? $\endgroup$ Aug 10 '13 at 15:09
  • $\begingroup$ Because the constraint that $u_n$ is always nonnegative real is strong, and it seems that the only thing that can come from the complex part is linked with the roots of unity. But I'm having trouble formalizing it. $\endgroup$
    – Denis
    Aug 10 '13 at 15:11
  • 2
    $\begingroup$ Can you do this case? $u_n=3+((3+4i)/5)^n+((3-4i)/5)^n$ $\endgroup$ Aug 10 '13 at 16:31
  • $\begingroup$ @GeraldEdgar Thanks, it appears to be a counter-example. So I thought it would not be needed, but I'll add additional knowledge about the $\lambda_i$'s. $\endgroup$
    – Denis
    Aug 10 '13 at 16:52
  • $\begingroup$ Why have you got an open bounty on this when you have accepted an answer? $\endgroup$
    – Yemon Choi
    Aug 14 '13 at 4:14


Consider the matrix $$\begin{pmatrix} 7 & 8 & 4 & 4 & 0 \\ 0 & 7 & 4 & 4 & 0 \\ 4 & 4 & 7 & 8 & 0 \\ 4 & 4 & 0 & 7 & 0 \\ 0 & 0 & 0 & 0 & 5 \\ \end{pmatrix}$$ The eigenvalues are $3 \pm 4i$, $11 \pm 4 \sqrt{3}$ and $5$. So $$u_n = (3+4i)^n + (3-4i)^n + 3 \cdot 5^n + 0 \cdot (11+4 \sqrt{3})^n + 0 \cdot (11-4 \sqrt{3})^n$$ is of the required form but does not have the desired asymptotics. (Example found using the method of Geoff Robinson's answer here.)

Requiring that all the $P_i$ be nonzero doesn't help. Let $M$ be the above matrix and let $N$ be the $10 \times 10$ matrix with block form $$\begin{pmatrix} 0 & M^2 \\ \mathrm{Id} & 0 \end{pmatrix}.$$ The eigenvalues of $N$ are $\pm3 \pm 4 i$, $\pm 11 \pm 4 \sqrt{3}$ and $\pm 5$.

Now look at $$10000 \cdot \left( (11+4 \sqrt{3})^n + (-11-4 \sqrt{3})^n +(-11+4 \sqrt{3})^n +(11-4 \sqrt{3})^n \right) $$ $$+100 \cdot 5^n + (-5)^n + 2 ((3+4i)^n + (3-4i)^n) + ((-3+4i)^n + (-3-4i)^n)$$

Of course, the exact powers of $10$ don't matter. The point is that $10000$ is large enough to always make things positive for $n$ even. For $n$ odd, the first term vanishes and $100$ is large enough to make the remaining terms positive, but $(3+4i)^n$ is of the same magnitude as $5^n$, so you can't get an asymtotic of the sort you want.

  • $\begingroup$ Thank you very much! Indeed, my question was very related to the one you linked, because my polynoms come from $u_n=[A^n]_{i,j}$. Do you think this would change the picture? $\endgroup$
    – Denis
    Aug 12 '13 at 19:22

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.