Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|cite|improve this question
Why do you believe that this is the asymptotic behavior? – Noah Schweber Aug 10 '13 at 15:09
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. – Denis Aug 10 '13 at 15:11
Can you do this case? $u_n=3+((3+4i)/5)^n+((3-4i)/5)^n$ – Gerald Edgar Aug 10 '13 at 16:31
@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. – Denis Aug 10 '13 at 16:52
Why have you got an open bounty on this when you have accepted an answer? – Yemon Choi Aug 14 '13 at 4:14

1 Answer 1

up vote 1 down vote accepted


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.

share|cite|improve this answer
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? – Denis Aug 12 '13 at 19:22

Your Answer


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.