We examine repeated iteration of various matrices from a graphical view, plotting each iterate vector for numerous randomly chosen initial values.
Then we examine a specific matrix and how why it generates the Fibonacci sequence.
\documentclass{beamer}
%
% Choose how your presentation looks.
%
% For more themes, color themes and font themes, see:
% http://deic.uab.es/~iblanes/beamer_gallery/index_by_theme.html
%
\mode<presentation>
{
\usetheme{default} % or try Darmstadt, Madrid, Warsaw, ...
\usecolortheme{albatross} % or try albatross, beaver, crane, ...
\usefonttheme{default} % or try serif, structurebold, ...
\setbeamertemplate{navigation symbols}{}
\setbeamertemplate{caption}[numbered]
}
\usepackage[english]{babel}
\usepackage[utf8x]{inputenc}
\title[Your Short Title]{Producing the Fibonacci Numbers by Repeated Iteration of a Matrix}
\author{Tyler Murphy}
\institute{Boise State University}
\date{18 Dec 2013}
\begin{document}
\begin{frame}
\titlepage
\end{frame}
% Uncomment these lines for an automatically generated outline.
\begin{frame}{Outline}
\tableofcontents
\end{frame}
\section{Introduction}
\subsection{Motivation}
\subsection{Key Terminology}
\begin{frame}{Motivation}
\begin{itemize}
\item Matrices are simple, effective ways to represent a system of equations. However, sometimes we are not interested in what happens in a system in the short term. We want to analyze trends and see where things are going.
\item To this end, we want to see what happens after the system repeats itself over time.
\end{itemize}
For our purposes we will be looking at the repeated iteration of a 2x2 matrix:
\[ \left[ \begin{array}{c}
x_{n+1} \\
y_{n+1}
\end{array} \right]
=
\left[ \begin{array}{cc}
a & b \\
c & d
\end{array} \right]
\left[ \begin{array}{c}
x_{n} \\
y_{n}
\end{array} \right]\]
\end{frame}
\begin{frame}
\begin{block}{Key Terminology}
\begin{itemize}
\item \textbf{Determinant} = the difference in the product of the two diagonals.
\item \textbf{Iteration} = Repetition of a process.
\item \textbf{Eigenvectors}, $v$ are vectors such that when multiplied by a matrix A, they yield a multiple of that vector. That multiple is called the \textbf{eigenvalue}, $\lambda$.
\[
Av = \lambda v
\]
\end{itemize}
\end{block}
\end{frame}
\section{Some Graphical Examples of Iterations}
\subsection{Markov}
\begin{frame}{Graphical Examples}
\begin{itemize}
\item A Markov matrix is a matrix whose columns add up to 1.
\item Consider matrix A = \[\left[ \begin{array}{cc}
0.8 & 0.3 \\
0.2 & 0.7
\end{array} \right]\] under iteration for 10,000 pairs of randomly chosen initial conditions.
\end{itemize}
% Commands to include a figure:
\begin{figure}
\includegraphics[width=2in]{markov.JPG}
\caption{\label{fig:1}Repeated iterates ($x_n.y_n)$ of a markov matrix A}
\end{figure}
\end{frame}
\subsection{Matrix of Det less than 1}
\begin{frame}{Graphical examples}
\begin{itemize}
\item Now we investigate a matrix with a positive determinant $< 1$.
\item Consider matrix A = \[\left[ \begin{array}{cc}
1 & \frac{1}{10} \\
\frac{99}{100} & 1
\end{array} \right]\] under iteration for 10,000 pairs of randomly chosen initial conditions.
\end{itemize}
% Commands to include a figure:
\begin{figure}
\includegraphics[width=2in]{iteration1.JPG}
\caption{\label{fig:2}Repeated iterates ($x_n.y_n)$ of a matrix A}
\end{figure}
\end{frame}
\subsection{Matrix of Det less than 1}
\begin{frame}{Graphical examples}
\begin{itemize}
\item Now we investigate a matrix with a positive determinant $> 1$.
\item Consider matrix A = \[\left[ \begin{array}{cc}
1 & -1 \\
1 & 1
\end{array} \right]\] under iteration for 10,000 pairs of randomly chosen initial conditions.
\end{itemize}
% Commands to include a figure:
\begin{figure}
\includegraphics[width=2in]{iteration3.JPG}
\caption{\label{fig:3}Repeated iterates ($x_n.y_n)$ of a matrix A}
\end{figure}
\end{frame}
\begin{frame}{Graphical Examples}
\begin{itemize}
\item Now consider a matrix A = \[\left[ \begin{array}{cc}
1 & 1 \\
1 & 0
\end{array} \right]\] under iteration of initial values [1,0]
\end{itemize}
% Commands to include a figure:
\begin{figure}
\includegraphics[width=2in]{fibonacci.JPG}
\caption{\label{fig:4}Repeated iterates of a matrix A beginning at [1,0]}
\end{figure}
We see that this matrix generates the fibonacci sequence. But why?
\end{frame}
\section{Fibonacci Application}
\begin{frame}{Fibonacci Sequence}
\begin{itemize}
\item The fibonacci Sequence is something we are all familiar with.
\item 1,1,2,3,5,8,13,21,34 ...
\item Each term is the sum of the previous two terms, with the first two terms being 1.
\item We can generalize this by saying that $F_{n+1} = F_{n} + F_{n-1}$.
\item But what if you want to find the $n^th$ term? It would be very tedious to have to generate the entire sequence just to get where you want to be.
\item To that end, we can use the iteration of a matrix and the fact that this matrix is diagonalizable.
\end{itemize}
\end{frame}
\begin{frame}{Fibonacci Generation}
First consider how this matrix was generated. A matrix is just a simple way of writing a system of equations.
\[ \left[\begin{array}{c} F_{n+1} \\
F_n
\end{array} \right] =
\left[\begin{array}{ccc} F_n &+& F_{n+1}\\
F_n & &
\end{array}\right]
\]
Which we can translate to:
\[ \left[\begin{array}{c} F_{n+1} \\
F_n
\end{array} \right] =
\left[\begin{array}{cc} 1 & 1 \\
1 & 0
\end{array}\right]
\left[\begin{array}{c}
F_n\\
F_{n+1}
\end{array}\right]
\]
\end{frame}
\subsection{Constructing the Fibonnaci Sequence through Matrix iteration}
\begin{frame}{Fibonacci Generation}
\begin{itemize}
\item Let's test a few examples to make sure this is working properly.
\item Consider: \[ \left[\begin{array}{c} F_1 \\
F_0
\end{array} \right] =
\left[\begin{array}{c}
1\\
0
\end{array}\right] \]
\item \[ \left[\begin{array}{c} F_2 \\
F_1
\end{array} \right] =
\left[\begin{array}{cc} 1 & 1 \\
1 & 0
\end{array}\right]
\left[\begin{array}{c}
1\\
0
\end{array}\right] =
\left[\begin{array}{c}
1\\
1
\end{array}\right]
\]
\item \[ \left[\begin{array}{c} F_3 \\
F_2
\end{array} \right] =
\left[\begin{array}{cc} 1 & 1 \\
1 & 0
\end{array}\right]
\left[\begin{array}{c}
1\\
1
\end{array}\right] =
\left[\begin{array}{c}
2\\
1
\end{array}\right] \]
\item \[ \left[\begin{array}{c} F_{n+1} \\
F_n
\end{array} \right] =
\left[\begin{array}{cc} 1 & 1 \\
1 & 0
\end{array}\right]^n
\left[\begin{array}{c}
1\\
0
\end{array}\right] \]
\end{itemize}
\end{frame}
\begin{frame}{Finding the Eigenvalues}
\begin{itemize}
\item Since computing each power of the matrix can be time consuming and lengthy, we first diagonalize the matrix with the use of its \emph{eigenvectors} and \emph{eigenvalues}
\item First we compute the eigenvalues, $\lambda$, of the matrix in the following manner:
\end{itemize}
\begin{equation} \begin{vmatrix} 1-\lambda & 1 \\
1 & 0-\lambda
\end{vmatrix} = (1-\lambda)(-\lambda)-1 = 0.
\end{equation}
\begin{align}
\lambda^2 - \lambda - 1 &= 0
\end{align}
Solving (2) we get:
\begin{align}
\lambda &= \frac{1\pm \sqrt{1-4(1)(-1)}}{2(1)} = \frac{1 \pm \sqrt{5}}{2}
\end{align}
\end{frame}
\begin{frame}{Finding the Eigenvectors}
Now we can use the eigenvalues to solve for the eigenvectors.
\[
\left[\begin{array}{cc}
1-\frac{1+\sqrt{5}}{2} & 1\\
1 & -\frac{1+\sqrt{5}}{2}
\end{array}\right]
\rightarrow
\left[\begin{array}{cc}
\frac{1-\sqrt{5}}{2} & 1\\
1 & -\frac{1+\sqrt{5}}{2}
\end{array}\right]
\rightarrow
\]
\[
\left[\begin{array}{cc}
1 & -\frac{1+\sqrt{5}}{2}\\
\frac{1-\sqrt{5}}{2} & 1
\end{array}\right]
\rightarrow
\left[\begin{array}{cc}
1 & -\frac{1+\sqrt{5}}{2}\\
0 & 0
\end{array}\right]
\]
Which gives us, for $\lambda_1, \vec{x_1}$ = \[\left[\begin{array}{c}
\frac{1+\sqrt{5}}{2}\\
1
\end{array}\right]
\]
Repeating this process for $\lambda_2$, we get $\vec{x_2}$ = \[\left[\begin{array}{c}
\frac{1-\sqrt{5}}{2}\\
1
\end{array}\right]
\]
\end{frame}
\begin{frame}{Diagonalizing $A = SDS^{-1}$}
We can now place $\vec{x_1}, \vec{x_2}$ into a matrix, $S$ = \[\left[\begin{array}{cc}
\frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2}\\
1 & 1
\end{array}\right]
\]
Matrix $D$ is the diagonal matrix whose entries are the eigenvalues whose position corresponds to the column of their corresponding eigenvector in $S$. So $D$ = \[\left[\begin{array}{cc}
\frac{1+\sqrt{5}}{2} & 0 \\
0 & \frac{1-\sqrt{5}}{2}
\end{array}\right]
\]
\end{frame}
\begin{frame}{Diagonalizing $A = SDS^{-1}$}
Now recall that
\begin{align}
\left[\begin{array}{c} F_{n+1} \\
F_n
\end{array} \right] &= A^n
\left[\begin{array}{c}
1\\
0
\end{array}\right] \hspace{-2cm}&= (SDS^{-1})^n\left[\begin{array}{c}
1\\
0
\end{array}\right]
\end{align}
\begin{align}
& & \hspace{10mm}= SD^nS^{-1}\left[\begin{array}{c}
1\\
0
\end{array}\right]
\end{align}
\end{frame}
\begin{frame}{Computing the Final Formula}
Now we substitute our values for $S, D$, and $S^{-1}$.
\[ \left[\begin{array}{c} F_{n+1} \\
F_n
\end{array} \right] =\]
\[
\left[\begin{array}{cc}
\frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2}\\
1 & 1
\end{array}\right]
\left[\begin{array}{cc}
(\frac{1+\sqrt{5}}{2})^n & 0\\
0 & (\frac{1-\sqrt{5}}{2})^n
\end{array}\right]
\left[\begin{array}{cc}
\frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2}\\
1 & 1
\end{array}\right]^{-1}
\left[\begin{array}{c}
1\\
0
\end{array}\right]
\]
\[= \frac{1}{\sqrt{5}}
\left[\begin{array}{cc}
\frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2}\\
1 & 1
\end{array}\right]
\left[\begin{array}{cc}
(\frac{1+\sqrt{5}}{2})^n & 0\\
0 & (\frac{1-\sqrt{5}}{2})^n
\end{array}\right]
\left[\begin{array}{cc}
1 & -(\frac{1-\sqrt{5}}{2})\\
-1 & \frac{1+\sqrt{5}}{2}
\end{array}\right]
\left[\begin{array}{c}
1\\
0
\end{array}\right]
\]
\end{frame}
\begin{frame}{Finalizing the Fibonacci formula}
Computing the matrix multiplication we get:
\begin{align}
\left[\begin{array}{c}
F_{n+1}\\
F_n
\end{array}\right] &=\frac{1}{\sqrt{5}}\left[\begin{array}{c}
(\frac{1+\sqrt{5}}{2})^{n+1}-(\frac{1-\sqrt{5}}{2})^{n+1}\\
(\frac{1+\sqrt{5}}{2})^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}
\end{array}\right]
\end{align}
And so,
\begin{align}
F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right]
\end{align}
\end{frame}
\section{conclusion}
\begin{frame}{Conclusion}
\begin{itemize}
\item As we have seen, Matrix iteration has lots of interesting and practical applications. Of the practical side specifically are Markov matrices which are used in modeling population migration, manufacturing, economic trends, and many other areas where there is a finite supply involved and trends are sought.
\item Matrix iteration also has application in the mathematical world in helping to create formulas to find specific values in a sequence, like the Fibonacci and Gibonacci numbers.
\end{itemize}
\begin{block}{Further Study}
\begin{itemize}
\item Examine limiting trends of matrices under iteration given a randomly chosen initializing vector.
\item What is the slope of the line of convergence of a matrix? How does this relate to the eigenvectors and eigenvalues?
\item Under what condition does a matrix fail to converge?
\item What initial values cause a matrix to stay fixed?
\end{itemize}
\end{block}
\end{frame}
\end{document}