3

I have a problem understanding a passage in Norris' book. If you have access to it, it's page 8. Here is the relevant text:

More generally, the following method may in principle be used to find a formula for $p^{(n)}(i,j)$ for any $M$-state chain and any states $i$ and $j$.

(i) Compute the eigenvalues $\lambda_1, ... , \lambda_M$ of $P$ by solving the characteristic equation.

(ii) If the eigenvalues are distinct then $p^{(n)}(i,j)$ has the form (of a polynomial) for some constants $a_1$, ... , $a_M$ (depending on i and j).

If an eigenvalue $\lambda$ is repeated (once, say) then the general form includes the term $(an+b) \lambda^n$.

The last bit is where I don't understand. Doing the computations by hand it appears to me that regardless of how many times an eigenvalue is repeated in the diagonal form of $P$, you still end up with a series of coefficients depending exclusively on $i$ and $j$, and a polynomial of the form:

$a_1 * \lambda_1^n + ... + (a_j + a_{j+1} + ... a_{j+m}) * \lambda^n + ... + a_M * \lambda_M^n$

Instead, the book seems to suggest that the correct form would be:

$a_1 * \lambda_1^n + ... + (a_j + a_{j+1} * n + ... a_{j+m} * n^m) * \lambda^n + ... + a_M * \lambda_M^n$

Which is it, and why?

Chival
  • 1,047
user68080
  • 47
  • 4
  • 1
    The standard response will involve the Jordan form which involves far too much machinery to develop in full in a posting. That said, if you know what a minimal polynomial is, I think there's a much shorter way to get to an answer to your question in bold. – user8675309 Feb 03 '20 at 19:57

1 Answers1

3

The latter form (with powers of $n$ up to one less than the multiplicity of the eigenvalue) is necessary in general, though there are certainly many cases in practice where the simpler form suffices. The difference reveals itself in the Jordan normal form of the matrix in question: matrix elements of $A^n$ will have terms like $n^m \lambda^n$ if and only if $A$'s Jordan normal form contains a Jordan block of size $\ge m+1$ corresponding to eigenvalue $\lambda$.

A simple example is just $$ A=\left(\begin{matrix} 2& 1 \\ 0 & 2\end{matrix}\right), $$ which is already in Jordan normal form; you should be able to verify that $$ A^n = \left(\begin{matrix}2^n & n2^{n-1} \\ 0 & 2^n\end{matrix}\right). $$

mjqxxxx
  • 41,358