We now return to the applied part of "Applied Linear Algebra". Chapter 5 is all about solving problems of the sort: $$ \{\hbox{Evolution of }{\bf x}\} = A {\bf x}.$$ There are different kinds of evolution problems, but they all get solved in the same way if $A$ is diagonalizable:

1. Diagonalize $A$, and pick a basis $\mathcal{B}$ of eigenvectors.
2. Define ${\bf y} = [{\bf x}]_\mathcal{B}$.
3. Rewrite the equations in terms of the ${\bf y}$ variables. These will take the form $$ \{\hbox{Evolution of }y_i \} = \lambda_i y_i.$$
4. Solve the resulting equations one variable at a time.
5. Convert ${\bf x}(0)$ to ${\bf y}(0)$, convert ${\bf y}(0)$ to ${\bf y}(n)$ (or ${\bf y}(t)$, for continuous-time problems), and finally convert ${\bf y}(n)$ to ${\bf x}(n)$.

Section 5.1 is about first-order discrete-time evolution, also called difference equations, of the form $${\bf x}(n) = A {\bf x}(n-1).$$ In the first video, we see how to solve these when $A$ is diagonalizable. The general solution is $${\bf x}(n) = \sum_{i=1}^n c_i \lambda _i^n {\bf b}_i,$$ where the $c_i$'s are arbitrary constants and the ${\bf b}_i$'s are eigenvectors with eigenvalues $\lambda_i$.

When $A$ isn't diagonalizable, we have to do things a little differently. Instead of using a basis of eigenvectors (which doesn't exist), we use a basis of power vectors. Otherwise the procedure is the same, although going from ${\bf y}(0)$ to ${\bf y}(n)$ is a little more complicated than before. The second video shows how this works.

By the way, there is a simple closed-form solution to ${\bf x}(n) = A {\bf x}(n-1)$, namely ${\bf x}(n) = A^n {\bf x}(0)$. However, this expression is useless if we don't know how to compute $A^n$! If $A$ is diagonalizable, we do this by factorization: $$ A^n = P D^n P^{-1}.$$ The three factors correspond exactly to the three conversions $${\bf x}(0) \, {\mathop{\Longrightarrow}^{P^{-1}}} \, {\bf y}(0) \, {\mathop{\Longrightarrow}^{D^n}} \, {\bf y}(n) \, {\mathop{\Longrightarrow}^P} \, {\bf x}(n).$$ When $A$ isn't diagonalization, we find the matrix of $A^n$ in the $\mathcal{B}$ basis by studying how $A^n$ acts on eigenvectors and on power vectors, as explained in the videos for Section 4.9.