Similarity and Diagonalization

If you wondered if there are examples of similar matrices, then it will not be hard to convince you they exist. Define B=\begin{bmatrix} -4 & 1 & -3 & -2 & 2 \\ 1 & 2 & -1 & 3 & -2 \\ -4 & 1 & 3 & 2 & 2 \\ -3 & 4 & -2 & -1 & -3 \\ 3 & 1 & -1 & 1 & -4 \end{bmatrix} && S=\begin{bmatrix} 1 & 2 & -1 & 1 & 1 \\ 0 & 1 & -1 & -2 & -1 \\ 1 & 3 & -1 & 1 & 1 \\ -2 & -3 & 3 & 1 & -2 \\ 1 & 3 & -1 & 2 & 1\\ \end{bmatrix}

Check that $S$ is nonsingular and then compute &A=\similar{B}{S}\\ &= \begin{bmatrix} 10 & 1 & 0 & 2 & -5 \\ -1 & 0 & 1 & 0 & 0 \\ 3 & 0 & 2 & 1 & -3 \\ 0 & 0 & -1 & 0 & 1 \\ -4 & -1 & 1 & -1 & 1 \end{bmatrix} \begin{bmatrix} -4 & 1 & -3 & -2 & 2 \\ 1 & 2 & -1 & 3 & -2 \\ -4 & 1 & 3 & 2 & 2 \\ -3 & 4 & -2 & -1 & -3 \\ 3 & 1 & -1 & 1 & -4 \end{bmatrix} \begin{bmatrix} 1 & 2 & -1 & 1 & 1 \\ 0 & 1 & -1 & -2 & -1 \\ 1 & 3 & -1 & 1 & 1 \\ -2 & -3 & 3 & 1 & -2 \\ 1 & 3 & -1 & 2 & 1 \end{bmatrix}\\ &= \begin{bmatrix} -10 & -27 & -29 & -80 & -25 \\ -2 & 6 & 6 & 10 & -2 \\ -3 & 11 & -9 & -14 & -9 \\ -1 & -13 & 0 & -10 & -1 \\ 11 & 35 & 6 & 49 & 19 \end{bmatrix}

So by this construction, we know that $A$ and $B$ are similar.

has a $3\times 3$ coefficient matrix B= and is similar to a diagonal matrix, as can be seen by the following computation with the nonsingular matrix $S$, \similar{B}{S}&= \inverse{\begin{bmatrix}-5&-3&-2\\3&2&1\\1&1&1\end{bmatrix}}\begin{bmatrix}-5&-3&-2\\3&2&1\\1&1&1\end{bmatrix}\\ &=\begin{bmatrix}-1&-1&-1\\2&3&1\\-1&-2&1\end{bmatrix}\begin{bmatrix}-5&-3&-2\\3&2&1\\1&1&1\end{bmatrix}\\ &= \begin{bmatrix}-1&0&0\\0&1&0\\0&0&2\end{bmatrix}

The Fibonacci sequence is a sequence of integers defined recursively by a_0&=0 & a_1&=1 & a_{n+1}&=a_n+a_{n-1},\quad n\geq 1

So the initial portion of the sequence is $0,\,1,\,1,\,2,\,3,\,5,\,8,\,13,\,21,\,\ldots$. In this subsection we will illustrate an application of eigenvalues and diagonalization through the determination of a closed-form expression for an arbitrary term of this sequence.

To begin, verify that for any $n\geq 1$ the recursive statement above establishes the truth of the statement \colvector{a_n\\a_{n+1}} &= \begin{bmatrix}0&1\\1&1\end{bmatrix} \colvector{a_{n-1}\\a_n}

Let $A$ denote this $2\times 2$ matrix. Through repeated applications of the statement above we have \colvector{a_n\\a_{n+1}} & =A\colvector{a_{n-1}\\a_n} =A^2\colvector{a_{n-2}\\a_{n-1}} =A^3\colvector{a_{n-3}\\a_{n-2}} =\cdots =A^n\colvector{a_{0}\\a_{1}}

In preparation for working with this high power of $A$, not unlike in , we will diagonalize $A$. The characteristic polynomial of $A$ is $\charpoly{A}{x}=x^2-x-1$, with roots (the eigenvalues of $A$ by ) \rho&=\frac{1+\sqrt{5}}{2} & \delta&=\frac{1-\sqrt{5}}{2}

With two distinct eigenvalues, implies that $A$ is diagonalizable. It will be easier to compute with these eigenvalues once you confirm the following properties (all but the last can be derived from the fact that $\rho$ and $\delta$ are roots of the characteristic polynomial, in a factored or unfactored form) \rho+\delta&=1 & \rho\delta&=-1 & 1+\rho&=\rho^2 & 1+\delta&=\delta^2 & \rho-\delta&=\sqrt{5}

Then eigenvectors of $A$ (for $\rho$ and $\delta$, respectively) are &\colvector{1\\\rho} & &\colvector{1\\\delta} which can be easily confirmed, as we demonstrate for the eigenvector for $\rho$, \begin{bmatrix}0&1\\1&1\end{bmatrix}\colvector{1\\\rho} & =\colvector{\rho\\1+\rho} =\colvector{\rho\\\rho^2} =\rho\colvector{1\\\rho}

From the proof of we know $A$ can be diagonalized by a matrix $S$ with these eigenvectors as columns, giving $D=\inverse{S}AS$. We list $S$, $\inverse{S}$ and the diagonal matrix $D$, S&=\begin{bmatrix}1&1\\\rho&\delta\end{bmatrix} & \inverse{S}&=\frac{1}{\rho-\delta}\begin{bmatrix}-\delta&1\\\rho&-1\end{bmatrix} & D&=\begin{bmatrix}\rho&0\\0&\delta\end{bmatrix}

OK, we have everything in place now. The main step in the following is to replace $A$ by $SD\inverse{S}$. Here we go, \colvector{a_n\\a_{n+1}} &=A^n\colvector{a_{0}\\a_{1}}\\ &=\left(SD\inverse{S}\right)^n\colvector{a_{0}\\a_{1}}\\ &=SD\inverse{S}SD\inverse{S}SD\inverse{S}\cdots SD\inverse{S}\colvector{a_{0}\\a_{1}}\\ &=SDDD\cdots D\inverse{S}\colvector{a_{0}\\a_{1}}\\ &=SD^n\inverse{S}\colvector{a_{0}\\a_{1}}\\ &= \begin{bmatrix}1&1\\\rho&\delta\end{bmatrix} \begin{bmatrix}\rho&0\\0&\delta\end{bmatrix}^n \frac{1}{\rho-\delta}\begin{bmatrix}-\delta&1\\\rho&-1\end{bmatrix} \colvector{a_{0}\\a_{1}}\\ &= \frac{1}{\rho-\delta} \begin{bmatrix}1&1\\\rho&\delta\end{bmatrix} \begin{bmatrix}\rho^n&0\\0&\delta^n\end{bmatrix} \begin{bmatrix}-\delta&1\\\rho&-1\end{bmatrix} \colvector{0\\1}\\ &= \frac{1}{\rho-\delta} \begin{bmatrix}1&1\\\rho&\delta\end{bmatrix} \begin{bmatrix}\rho^n&0\\0&\delta^n\end{bmatrix} \colvector{1\\-1}\\ &= \frac{1}{\rho-\delta} \begin{bmatrix}1&1\\\rho&\delta\end{bmatrix} \colvector{\rho^n\\-\delta^n}\\ &= \frac{1}{\rho-\delta} \colvector{\rho^n-\delta^n\\\rho^{n+1}-\delta^{n+1}}

Performing the scalar multiplication and equating the first entries of the two vectors, we arrive at the closed form expression a_n&=\frac{1}{\rho-\delta}\left(\rho^n-\delta^n\right)\\ &=\frac{1}{\sqrt{5}} \left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)\\ &=\frac{1}{2^n\sqrt{5}} \left(\left(1+\sqrt{5}\right)^n-\left(1-\sqrt{5}\right)^n\right)

Notice that it does not matter whether we use the equality of the first or second entries of the vectors, we will arrive at the same formula, once in terms of $n$ and again in terms of $n+1$. Also, our definition clearly describes a sequence that will only contain integers, yet the presence of the irrational number $\sqrt{5}$ might make us suspicious. But no, our expression for $a^n$ will always yield an integer!

The Fibonacci sequence, and generalizations of it, have been extensively studied (Fibonacci lived in the 12th and 13th centuries). There are many ways to derive the closed-form expression we just found, and our approach may not be the most efficient route. But it is a nice demonstration of how diagonalization can be used to solve a problem outside the field of linear algebra.