Question

I need some help working with difference equations. I have to calculate A^100 if A is the Fibonacci matrix: (1st row)=1 1
(2nd row)=1 0
It's exercise 5.3.1 from G.Strang's "Linear Algebra and Applications", and I would also like some help with 5.3.2 and 5.3.20, if anyone has access to the book.

Answer 1

There might be some trick to find with the recurrence relation maybe, but systematically you can also diagonalize this matrix to raise it to a high exponent to get what you want.

Answer 2

There is an algorithm to calculate a matrix to a power. It requires eigendecomposition of your matrix.

Answer 3

Write \(\mathbf{A}=\mathbf{P\Lambda P}^{-1}\), where \(\mathbf{P}=\begin{bmatrix}\mathbf{p}&\tilde{\mathbf{p}}\end{bmatrix}\) is the matrix of the eigenvectors of \(\mathbf{A}\), and \(\mathbf{\Lambda}\) a diagonal matrix populated with the corresponding eigenvalues \(\lambda\) and \(\tilde{\lambda}\).

The eigenvalues \(\lambda_i\) themselves are given by
\[|\mathbf{A}-\lambda_i\mathbf{I}|=0\implies\lambda_i=\frac{1\pm\sqrt5}{2}\]Let \(\lambda\) be the eigenvalue with the positive root and \(\tilde\lambda\) the eigenvalue with the negative root.

The corresponding eigenvectors you'll find to be \(\mathbf{p}=\begin{bmatrix}\lambda\\1\end{bmatrix}\) and \(\tilde{\mathbf{p}}=\begin{bmatrix}\tilde\lambda\\1\end{bmatrix}\).

Now,
\[\mathbf{A}^2=\left(\mathbf{P\Lambda P}^{-1}\right)\left(\mathbf{P\Lambda P}^{-1}\right)=\mathbf{P\Lambda}^2\mathbf{P}^{-1}\]and more generally,
\[\mathbf{A}^n=\left(\mathbf{P\Lambda P}^{-1}\right)\cdots\left(\mathbf{P\Lambda P}^{-1}\right)=\mathbf{P\Lambda}^n\mathbf{P}^{-1}\]which means finding \(\mathbf{A}^{100}\) is a matter of computing the much simpler \(\mathbf{\Lambda}^{100}\). Simpler because
\[\mathbf{\Lambda}^n=\begin{bmatrix}\lambda&0\\0&\tilde\lambda\end{bmatrix}^n=\begin{bmatrix}\lambda^n&0\\0&{\tilde\lambda}^n\end{bmatrix}\]So, you have
\[\begin{align*}\mathbf{A}^n&=\begin{bmatrix}\lambda&\tilde\lambda\\1&1\end{bmatrix}\begin{bmatrix}\lambda^n&0\\0&\tilde\lambda^n\end{bmatrix}\begin{bmatrix}\lambda&\tilde\lambda\\1&1\end{bmatrix}^{-1}\\[1ex]&=\frac{1}{\lambda-\tilde\lambda}\begin{bmatrix}\lambda^{n+1}-\tilde\lambda^{n+1}&-\lambda\tilde\lambda(\lambda^n-\tilde\lambda^n)\\
\lambda^n-\tilde\lambda^n&\lambda\tilde\lambda^n-\lambda^n\tilde\lambda\end{bmatrix}\end{align*}\]which can be simplified further as the eigenvalues are algebraic conjugates:
\[\begin{cases}\lambda\tilde\lambda=-1\\\lambda+\tilde\lambda=1\\\lambda-\tilde\lambda=\sqrt5\end{cases}\]