I have a problem that asks for following:
Consider the in-homogenous linear difference equation $y_t-4y_t+2y_{t-3}=4^t$. Write the LDE as a system of first-order LDEs.
The solution is given: define $z_{1,t}= y_t$, $z_{2,t}= y_{t-1}$, $z_{3,t}= y_{t-2}$ and also $z_{2,t}= z_{1,t-1}$, $z_{3,t}= z_{1,t-1}$.
The equation above is $z_{1,t}=y_t=4y_t-2y_{t-3}+4^t=4z_{1,t-1}-2z_{3,t-1}+4^t$.
Yielding to the difference equation with matrix A:
$$ \begin{matrix} 4& 0 & -2 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{matrix} $$
And vectors: at the left hand side $(z_{1,t},z_{2,t},z_{3,t})^T$ and at the right hand side A is multiplied with vector $(z_{1,t-1},z_{2,t-1},z_{3,t-1})^T$ and $(4^t,0,0)^T$ is added.
So, I know the solution is given. But I don't really understand what we did here. I really don't get it right now. Can someone help and explain to me why and how the variables are replaced by also giving an intuitive explanation?
The core idea here is to take a system that we don't know how to handle and turn it into a system that we do. For instance, let's say we're given the 'system' $a_n=2a_{n-1}$. Then clearly the solution to this difference equation is $a_n=2^na_0$. What if we had a system like $a_n=a_{n-1}+b_{n-1}$, $b_n=b_{n-1}-a_{n-1}$? Well, in this case the answer is a little less obvious, but we might think to write it as $\vec{a}_n=M\vec{a}_{n-1}$, where we define $\vec{a}_n=\begin{bmatrix}a_n\\b_n\end{bmatrix}$ as a vector holding both components, and $M=\begin{bmatrix}1&1\\-1&1\end{bmatrix}$ as the 'transformation matrix' that we multiply by one entry to get the next. This lets us see that $\vec{a}_n=M\vec{a}_{n-1}=M\cdot(M\vec{a}_{n-2})=\ldots=M^n\vec{a}_0$, much like in the one-dimensional case.
But here we have a recurrence relation that's not linear, but in just one variable, so this same framework doesn't work! What do do? Well, if we could find some vector of variables $\vec{y}_n$ so that there was a linear transformation $M$ taking $\vec{y}_{n-1}$ to $\vec{y}_n$, then we could apply the matrix method to it. Now, $y_{n-2}$ isn't a 'single step' from $y_n$, but it is a single step from $y_{n-1}$; if we think about defining a new sequence $z_n$ by $z_n=y_{n-1}$, then $z_{n-1}=y_{n-2}$. Likewise, if we say $w_n=y_{n-2}$, then $w_{n-1}= y_{n-3}$. Of course, this $w$ isn't cleanly defined in terms of a single step from $y$, but it is defined as a 'single step' from $z$; we can declare instead that $w_n=z_{n-1}$, so that $w_{n-1}=z_{n-2} = y_{n-3}$. Now, our original equation $y_n=4y_{n-1}-2y_{n-3}+4^n$ can be written as a linear expression in terms from the 'previous step' $n-1$: $y_n=4y_{n-1}-2w_{n-1}+4^n$. But this isn't enough by itself - there's a $w$ on one side of this, but we still need to say where $w$ comes from! Fortunately, we've already done this — and done it in the definition. We have $w_n=z_{n-1}$, and similarly $z_n=y_{n-1}$. These are very simple linear relations, but they're still linear relations. This allows us to say that $\vec{y}_n=M\vec{y}_{n-1}+4^n$, where we define $\vec{y}_n=\begin{bmatrix}y_n\\z_n\\w_n\end{bmatrix}$ and $M=\begin{bmatrix}4&0&-2\\1&0&0\\0&1&0\end{bmatrix}$. (Try multiplying $M$ by $\vec{y}_{n-1}$ yourself to see what equations you get by equating elements.)