# Understanding why the roots of homogeneous difference equation must be eigenvalues

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)

-
You're considering the wrong matrix. The matrix you should be looking at is the Frobenius companion matrix. For your example recursion, that would be $$\begin{pmatrix} 2 & -5 & 6 \\ 1 & 0 & 0 \\ 0 & 1 & 0\end{pmatrix}$$ Repeatedly left-multiplying that to a vector is equivalent to running your recursion relation, with the starting values being the components of your vector. –  Ｊ. Ｍ. Aug 4 '12 at 16:05
Okay, so this Frobenius matrix must be correct matrix to consider. Still, I have seen (e.g. wikipedia) a lot of mention of the characteristic polynomial, which as far as I know in the context of matrices, we would find from the characteristic equation $(A_0 - \lambda I)\mathbf x = \mathbf 0$. It is my understanding that the characteristic polynomial is a result of the eigenvalues of $A_0$ first. I'm not really sure how to construct a Frobenius matrix without finding the characteristic polynomial and eigenvalues first. –  mathStudent Aug 4 '12 at 21:01
Well, if you already have the linear recurrence relation to begin with, you just load the coefficients of that recurrence relation into the matrix. The characteristic polynomial of both the linear recurrence and the companion matrix are, not coincidentally, the same polynomial. –  Ｊ. Ｍ. Aug 5 '12 at 2:57

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)$.

-
+1 nice answer. $2x_3^k$ or $2x_k^3$? –  mathStudent Aug 4 '12 at 18:04
Fixed it thanks! –  copper.hat Aug 4 '12 at 19:01
The "controllable canonical form" in copper's answer is what other people would call a (Frobenius) companion matrix. –  Ｊ. Ｍ. Aug 4 '12 at 19:03
As an aside, this intimate relationship between the Frobenius companion matrix and linear recurrences is the basis for Bernoulli's method for finding the dominant real root of a polynomial. See this, for instance. –  Ｊ. Ｍ. Aug 5 '12 at 5:26
I think my first encounter with companion matrices was as a 'state-space' method of implementing a transfer function on an analog computer. As a vaguely related comment, Francis was completely unaware of the impact of the QR algorithm until Golub met him in 2007. –  copper.hat Aug 5 '12 at 5:50

The roots are eigenvalues. What is the operator they are eigenvalues of? It is the shift operator.

Consider the vector space $V$ of sequences $a_0, a_1, a_2, ...$ (say of complex numbers). Define the left shift operator

$$S(a)_i = a_{i+1}.$$

In other words, $S$ takes input a sequence $a_0, a_1, a_2, ...$ and returns the sequence $a_1, a_2, a_3, ...$. Now we need the following three fundamental observations.

Observation 1: The linear homogeneous recurrence with characteristic polynomial $p$ is precisely described by the equation $p(S) a = 0$. In other words, the sequences satisfying such a linear recurrence are precisely the sequences in the kernel of $p(S)$.

Observation 1.5: The shift operator $S$ acts on the space of solutions to any equation of the form $p(S)a = 0$.

Observation 2: Over the complex numbers, we can factor $p(S) = \prod (S - \lambda_i)$. Thus if $(S - \lambda_i) a = 0$, or equivalently if $a$ is an eigenvector of $S$ with eigenvalue $\lambda_i$, then $p(S) a = 0$.

Observation 3: $(S - \lambda_i) a = 0$ if and only if $a_n = c \lambda_i^n$ for some constant $c$.

$S$ resembles in some sense the differentiation operator, which it is sent to if one sends $V$ to the space of formal power series via

$$(a_0, a_1, a_2, ...) \mapsto \sum_{n=0}^{\infty} \frac{a_n}{n!} x^n.$$

Thus everything above applies (at least formally) to linear homogeneous ODEs with constant coefficients and their characteristic polynomials as well. The corresponding eigenvectors are the functions $e^{\lambda_i x}$.

-