How to transform a m-th order difference equation into a first order system of difference equations? 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?
 A: 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.)
A: So, basically:
1. I just redefine the m+1 variables in the m-th order LDE by m new variables z at time t.
2. The variables z at time t can be redefined by z variables at time t, but instead of t, we go one step back and use t-1.
3. The LDE can be written for $y_t$ as an equation of y of higher orders. 
4. We insert the z of time t-1 variables (from 2.) into the equation and basically get the first row of the solution matrix.
5. In order to compute the other rows we use the equations that are obtained in 2. to check for the relationship between the z variables of time t and the z variables of time t-1.
Also, can I assume that for any solution matrix there is a diagonal scheme from the second row onwards? And if there is no $y_t+1$ given, the number is always 1 on the diagonals?
Sorry for the non-mathematical expressions and notations above. I am quite new here and it would take ages to use the format equations. 
