Using linear algebra, how is the Binet formula (for finding the nth Fibonacci number) derived? If possible, please refrain from any type of proof besides linear algebra. So, using the recursion formula $F_{n+1} = F_{n-1} + F_n$, for $n\gt 1$, and where $F_0 = 0$ and $F_1 = 1$, and the Fibonacci matrix, derive the golden ratio and ultimately the Binet formula. 

The Fibonacci numbers are defined by a second-order linear recurrence equation:
$$F_{n+2} = F_{n+1} + F_n$$
This means we can treat the solution of $F_n$ in terms of $n$ as a problem in linear algebra involving only $2$-dimensional vectors. In some sense, what we are doing is modelling this as a dynamical process on a $2$-dimensional state space.
Let $V = \mathbb{R}^2$. We define a linear operator $T : V \to V$ by
$$T(x, y) = (y, x + y)$$
Notice that $T(F_{n}, F_{n+1}) = (F_{n+1}, F_{n+2})$, so you can think of $V$ as being a sliding $2$-entry window on the Fibonacci sequence and $T$ as the operator which advances the window along the Fibonacci sequence. The initial conditions $F_0 = 0, F_1 = 1$ then imply that
$$T^n(0, 1) = (F_n, F_{n+1})$$
so all we need to do to find $F_n$ in terms of $n$ is to find an effective way to compute iterates of the operator $T$!
Now, we get our hands dirty and represent $T$ as a matrix:
$$T = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$$
Imagine if we could somehow find an invertible matrix $P$ and a diagonal matrix $D$ such that $T = P D P^{-1}$; then, by matrix algebra, we would have $T^n = P D^n P^{-1}$, and it is easy to compute powers of diagonal matrices. The theory of eigenvectors and eigenvalues gives us one way to find such a factorisation of $T$. Notice that 
$$\det (T - x I) = \det (P(D - x I)P^{-1}) = (\det P)(\det (D - x I))(\det P^{-1}) = \det (D - x I)$$
but a simple calculation shows
$$\det (D - x I) = \det \begin{pmatrix} \lambda_1 - x & 0 \\ 0 & \lambda_2 - x \end{pmatrix} = (\lambda_1 - x)(\lambda_2 - x)$$
so whatever $\lambda_1$ and $\lambda_2$ are, they must be the zeros of the polynomial
$$\det (T - x I) = \det \begin{pmatrix} -x & 1 \\ 1 & 1 - x \end{pmatrix} = x^2 - x - 1$$
which, surprise surprise, is the minimal polynomial of the golden ratio. So let $\lambda_1 = \frac{1}{2} (1 + \sqrt{5})$ and $\lambda_2 = \frac{1}{2} (1 - \sqrt{5})$. These are the eigenvalues of $T$. By construction, $\det (T - \lambda_1 I) = \det (T - \lambda_2 I) = 0$, so there must be non-zero vectors $\begin{pmatrix} x_1 \\ y_1 \end{pmatrix}$ and $\begin{pmatrix} x_2 \\ y_2 \end{pmatrix}$ such that
$$
T
\begin{pmatrix} x_1 \\ y_1 \end{pmatrix} = 
\lambda_1 \begin{pmatrix} x_1 \\ y_1 \end{pmatrix}
$$
$$
T
\begin{pmatrix} x_2 \\ y_2 \end{pmatrix} = 
\lambda_2 \begin{pmatrix} x_2 \\ y_2 \end{pmatrix}
$$
These vectors are called the eigenvectors of $T$. I leave you to verify that $x_1 = \lambda_1 - 1$, $y_1 = 1$, $x_2 = \lambda_2 - 1$, $y_2 = 1$ works, but there are other solutions.
Define the matrix $P$ by
$$P = \begin{pmatrix} x_1 & x_2 \\ y_1 & y_2 \end{pmatrix}$$
Notice that
$$\begin{pmatrix} x \\ y \end{pmatrix} = 
\alpha_1 \begin{pmatrix} x_1 \\ y_1 \end{pmatrix} +
\alpha_2 \begin{pmatrix} x_2 \\ y_2 \end{pmatrix} = 
P \begin{pmatrix} \alpha_1 \\ \alpha_2 \end{pmatrix}$$
so by linearity we have
$$T \begin{pmatrix} x \\ y \end{pmatrix} = 
\lambda_1 \alpha_1 \begin{pmatrix} x_1 \\ y_1 \end{pmatrix} +
\lambda_2 \alpha_2 \begin{pmatrix} x_2 \\ y_2 \end{pmatrix} = 
P \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix} \begin{pmatrix} \alpha_1 \\ \alpha_2 \end{pmatrix}$$
but we can invert $P$ to find $\alpha_1$ and $\alpha_2$ in terms of $x$ and $y$, so we have obtained the desired factorisation of $T$ as $P D P^{-1}$ with $D$ diagonal. Putting everything together, we get the formula
$$T^n = P \begin{pmatrix} {\lambda_1}^n & 0 \\ 0 & {\lambda_2}^n \end{pmatrix} P^{-1}$$
and applying this to the vector $\begin{pmatrix} 0 \\ 1 \end{pmatrix}$ gives Binet's formula.
