Consider the following recurrence relation : $$X_{k+4} = X_{k+3} + X_{k+1} - X_k$$ $1)$ Find the transition matrix $A$ corresponding to the recurrence relation.
$2)$ Show that $A$ is not diagonalizable.
The transition matrix $A$ that I found was: \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ -1 & 1 & 0 & 1 \end{pmatrix} However, I can't easily find the eigenvalues of $A$. Therefore, I think that the $A$ that I got is wrong. Could someone explain how to properly get the $A$ matrix?
Define $z_k$ to be the vector $$ z_k = \pmatrix{z_k^1\\z_{k}^2\\z_k^3\\z_k^4} = \pmatrix{x_{k}\\x_{k+1}\\x_{k+2}\\x_{k+3}} $$ (note: the superscripts are not exponents). We can express your recurrence relation as the following system of first-order relations: $$ \begin{cases}z_{k+1}^1 = z_k^2\\ z_{k+1}^2 = z_k^3\\ z_{k+1}^3 = z_k^4\\ z_{k+1}^4 = - z_k^1 + z_k^2 + z_k^4 \end{cases} \implies z_{k+1} = \pmatrix{0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ -1&1&0&1 } z_k. $$ Your matrix was correct! You should compute the characteristic polynomial of the matrix to be $$ p(x) = x^4 - x^3 - x + 1 = (x-1)^2(x^2 + x + 1). $$ In order to show that the matrix fails to be diagonalizable, it suffices to check that $M - I$ has a nullspace of dimension $1$, even though the eigenvalue $\lambda = 1$ has algebraic multiplicity $2$.