## Tuesday, July 30, 2013

### Characteristic polynomial - 3: recurrence is identical to its characteristic equation

It is surprising why the n-th order equation $x^n + c_1 x^{n-1} + \cdots + c_n = 0$ (and corresponding recurrence relation, $x_n + c_1 x_{n-1} + \cdots + c_n = 0$) has the characteristic polynomial of $\lambda^n + c_1 \lambda^{n-1} + \cdots + c_n = 0$?

I have investigated the second order $x^2 + c_1 x + c_2 = 0$:

$$\begin{bmatrix} x^2 \\ x \end{bmatrix} = \begin{bmatrix} -c_1 & -c_2 \\ 1 & 0 \end{bmatrix} \, \begin{bmatrix} x \\ 1 \end{bmatrix} = x\, \begin{bmatrix} x \\ 1 \end{bmatrix}$$

Here $\begin{bmatrix} -c_1 & -c_2 \\ 1 & 0 \end{bmatrix} \, \begin{bmatrix} x \\ 1 \end{bmatrix} = x \, \begin{bmatrix} x \\ 1 \end{bmatrix}$, which means that $x$ is an eigenvalue symbol, which is often denoted $\lambda$. Let's compute it by taking determinant

$$\begin{vmatrix} -c_1 - x & -c_2 \\ 1 & -x \end{vmatrix} = x (c_1+x) + c_2 = x^2 + c_1 x + c_2 = 0$$

Incredibly, it is exactly reproduces to the original recurrence equation. I can also do the same for the 3rd order equation, $x^3 + c_1 x^2 + c_2 x + c_3 = 0$:

$$\begin{bmatrix} x^3 \\ x^2 \\ x \end{bmatrix} = \begin{bmatrix} -c_1 & -c_2 & -c_3\\ 1 & 0 & 0 \\ 0 &1&0 \end{bmatrix} \, \begin{bmatrix} x^2 \\ x \\ 1 \end{bmatrix}$$. Take the determinant for characteristic polynomial:

$$\begin{vmatrix} -c_1 - x & -c_2 & -c_3\\ 1 & -x & 0 \\ 0&1&-x\end{vmatrix} = -\begin{vmatrix} -c_2 & -c_3 \\ 1 & -x \end{vmatrix} - x \begin{vmatrix} -c_1 - x & -c_3 \\ 0 & -x \end{vmatrix} =$$
$$= -c_2 x - c_3 - x^2(c_1-x) = (x^3 + c_1 x^2 + c_2 x + c_3)(-1) = 0$$

Again, received characteristic polynomial is exactly the original equation. I do not know how they prove this equality for arbitrary n, since the determinant computation turns out quite complex, despite a lot of zeros in the eigenmatrix. But, we see that recurrence relation, a polynomial and their characteristic polynomial are just the same things. This closes the issue I've started a long time ago.