# convergence rate of matrix product

Suppose you have a linear system like this:
$$\mathbf{x}[k+1] = \mathbf{D} \mathbf{x}[k]$$
where matrix $\mathbf{D}$ is diagonal. Assume its diagonal entries are real, greater than zero and less than one, but not necessarily distinct. Is it still technically correct to say that the convergence rate is determined by the largest value in $\mathbf{D}$? And what about non-diagonalizable matrices (when eigenvalues have multiplicity greater than one)?

-
It is technically correct to say that the convergence rate of $x[k]$ will be determined by the greatest eigenvalue of $D$ when $D$ is diagonal. I'm still suspicious about non-diagonal matrices. –  Patrick Da Silva May 27 '11 at 5:23
The last sentence might seem to imply that multiple eigenvalues is equivalent to non-diagonalizable : it's necessary but not sufficient condition mathoverflow.net/questions/23478/… –  leonbloy May 27 '11 at 14:45
The convergence rate depends on the starting point $x[0]$. If the component of $x[0]$ in the eigenspace of the largest eigenvalue is zero, one should look at the second largest eigenvalue, and so on. –  Did May 27 '11 at 17:59
@Didier: you are right. I was assuming $\mathbf{x}[0]$ is, say, random, so it's not aligned with any eigenvector w.h.p. –  ACAC May 27 '11 at 23:08

If the matrix is not diagonalizable, and the largest block in the Jordan normal form for the largest eigenvalue $\lambda$ is $m \times m$, then you can have $\|x[n]\| \sim C n^{m-1} \lambda^n$ as $n \to \infty$. This is because if $B$ is a matrix with $(B-\lambda I)^m = 0$ and $(B - \lambda I)^{m-1} \ne 0$, $B^n = (B-\lambda I+ \lambda I)^n = \sum_{k=0}^{m-1} {n \choose k} \lambda^{n-k} (B-\lambda I)^k$, and ${n \choose k}$ is a polynomial in $n$ of degree $k$.