There is some obvious relationship between the root solutions to a homogeneous difference equation (as a recurrence relation) and eigenvalues which I'm trying to see. I have read over the wiki article 3.2, 3.4 and the eigenvalues ($\lambda$ ) are hinted at as the roots, but I'm still not sure why these must be eigenvalues of some matrix, say $A_0$, and what the meaning of $A_0$ may be.
It seems that to solve a homogeneous linear difference equation we find the "characteristic polynomial" by simply factoring one difference equation. However, typically to find the "characteristic polynomial" I would solve the characteristic equation for some matrix,
$A_0 = \begin{pmatrix} 1 & 0 & 0\\
0 & -2 & 0 \\
0 & 0 & 3 \\
\end{pmatrix}$
$(A_0 – \lambda I)\mathbf x = \mathbf 0$,
then solve for the determinant equal to $0$, and then solve for each $\lambda$ e.g.
$ \det(A_0 – \lambda I) = 0$
$(1 – \lambda)(2 + \lambda)(3 – \lambda) = 0$
Now suppose this also happens to be a solution to some linear difference equation, and so here the characteristic polynomial is $\lambda^3 – 2\lambda^2 – 5\lambda + 6 = 0$, and the difference equation is.
$y_{k+3} – 2y_{k+2} – 5y_{k+1} + 6y_k = 0 $. Then, for example, $\lambda = 3$ is a solution for all k.
Now, given we have found this solution to this difference equation, how can we explain some special relationship to $A_0$, other than $\lambda = 3$ happens to be an eigenvalue of $A_0$? Is there any meaning to make of $A_0$?
(cf. 4.8, Linear Algebra 4th, D. Lay)
Best Answer
You have a mistake in your expansion of the characteristic polynomial, it should be $\lambda^3-2 \lambda^2-5 \lambda +6$.
To see the connection between this polynomial and the matrix $A_0$, it helps to reduce the difference equation down a first order equation in many variables.
Let $x_k^1 = y_k, x_k^2 = y_{k+1}, x_k^3 = y_{k+2}$. Then the difference equation becomes $$x_{k+1}^1 = x_k^2$$ $$x_{k+1}^2 = x_k^3$$ $$x_{k+1}^3 = -6 x_k^1 + 5 x_k^2 + 2 x_k^3,$$ or, in matrix terms, with $x_k = (x_k^1,x_k^2,x_k^3)^T$: $$ x_{k+1} = A x_k = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ -6 & 5 & 2 \end{bmatrix} x.$$ Note the connection between the characteristic polynomial coefficients and the bottom row of the matrix (this is called the controllable canonical form in control circles). If you work out the eigenvalues of $A$ you will find that they are $\{-2,1,3\}$. In fact, the characteristic polynomial of $A$ is $\lambda^3-2 \lambda^2-5 \lambda +6$. Hence $A$ is diagonalizable by some matrix $V$, and you have $A_0 = V^{-1} A V$, where $A_0$ has the form above.
They share the same characteristic polynomial because $\det (\lambda I - A_0) = \det (\lambda I - V^{-1} A V) = \det V^{-1} \det (\lambda I - A ) \det V = \det (\lambda I - A)$.
Relevant links: http://en.wikipedia.org/wiki/Companion_matrix http://en.wikipedia.org/wiki/State_space_representation#Canonical_realizations