An Inquiry-Based Introduction to Linear Algebra and Applications

Subsection Application: The Fibonacci Numbers

In 1202 Leonardo of Pisa (better known as Fibonacci) published Liber Abaci (roughly translated as The Book of Calculation), in which he constructed a mathematical model of the growth of a rabbit population. The problem Fibonacci considered is that of determining the number of pairs of rabbits produced in a given time period beginning with an initial pair of rabbits. Fibonacci made the assumptions that each pair of rabbits more than one month old produces a new pair of rabbits each month, and that no rabbits die. (We ignore any issues about that might arise concerning the gender of the offspring.) If we let \(F_n\) represent the number of rabbits in month \(n\text{,}\) Fibonacci produced the model

for \(n \geq 0\) where \(F_0 = 0\) and \(F_1 = 1\text{.}\) The resulting sequence

is a very famous sequence in mathematics and is called the Fibonacci sequence. This sequence is thought to model many natural phenomena such as number of seeds in a sunflower and anything which grows in a spiral form. It is so famous in fact that it has a journal devoted entirely to it. As a note, while Fibonacci's work Liber Abaci introduced this sequence to the western world, it had been described earlier Sanskrit texts going back as early as the sixth century.

By definition, the Fibonacci numbers are calculated by recursion. This is a very ineffective way to determine entries \(F_n\) for large \(n\text{.}\) Later in this section we will derive a fascinating and unexpected formula for the Fibonacci numbers using the idea of diagonalization.

Subsection Introduction

As we have seen when studying Markov processes, each state is dependent on the previous state. If \(\vx_0\) is the initial state and \(A\) is the transition matrix, then the \(n\)th state is found by \(A^n \vx_0\text{.}\) In these situations, and others, it is valuable to be able to quickly and easily calculate powers of a matrix. We explore a way to do that in this section.

Subsection Diagonalization

In Preview Activity 19.1 we saw how if we can powers of a matrix we can make predictions about the long-term behavior of some systems. In general, calculating powers of a matrix can be a very difficult thing, but there are times when the process is straightforward.

Activity 19.2 illustrates that calculating powers of square matrices whose only nonzero entries are along the diagonal is rather simple. In general, if

then

for any positive integer \(k\text{.}\) Recall that a diagonal matrix is a matrix whose only nonzero elements are along the diagonal (see Definition 8.6). In this section we will see that matrices that are similar to diagonal matrices have some very nice properties, and that diagonal matrices are useful in calculations of powers of matrices.

We can utilize the method of calculating powers of diagonal matrices to also easily calculate powers of other types of matrices.

As Activity 19.3 illustrates, to calculate the powers of a matrix of the form \(P^{-1}DP\) we only need determine the powers of the matrix \(D\text{.}\) If \(D\) is a diagonal matrix, this is especially straightforward.

Subsection Similar Matrices

Similar matrices play an important role in certain calculations. For example, Activity 19.3 showed that if we can write a square matrix \(A\) in the form \(A = P^{-1}DP\) for some invertible matrix \(P\) and diagonal matrix \(D\text{,}\) then finding the powers of \(A\) is straightforward. As we will see, the relation \(A = P^{-1}DP\) will imply that the matrices \(A\) and \(D\) share many properties.

Activity 19.4 suggests that similar matrices share some, but not all, properties. Note that if \(A = P^{-1}BP\text{,}\) then \(B = Q^{-1}AQ\) with \(Q = P^{-1}\text{.}\) So if \(A\) is similar to \(B\text{,}\) then \(B\) is similar to \(A\text{.}\) Similarly (no pun intended), since \(A = I^{-1}AI\) (where \(I\) is the identity matrix), then any square matrix is similar to itself. Also, if \(A = P^{-1}BP\) and \(B = M^{-1}CM\text{,}\) then \(A = (MP)^{-1}C(MP)\text{.}\) So if \(A\) is similar to \(B\) and \(B\) is similar to \(C\text{,}\) then \(A\) is similar to \(C\text{.}\) If you have studied relations, these three properties show that similarity is an equivalence relation on the set of all \(n \times n\) matrices. This is one reason why similar matrices share many important traits, as the next activity highlights.

We summarize some properties of similar matrices in the following theorem.

Subsection Similarity and Matrix Transformations

When a matrix is similar to a diagonal matrix, we can gain insight into the action of the corresponding matrix transformation. As an example, consider the matrix transformation \(T\) from \(\R^2\) to \(\R^2\) defined by \(T(\vx) = A \vx\text{,}\) where

We are interested in understanding what this matrix transformation does to vectors in \(\R^2\text{.}\) First we note that \(A\) has eigenvalues \(\lambda_1 = 2\) and \(\lambda_2 = 4\) with corresponding eigenvectors \(\vv_1 = \left[ \begin{array}{r} -1\\1 \end{array} \right]\) and \(\vv_2 = \left[ \begin{array}{c} 1\\1 \end{array} \right]\text{.}\) If we let \(P = [\vv_1 \ \vv_2]\text{,}\) then you can check that

and

where

Thus,

A simple calculation shows that

Let us apply \(T\) to the unit square whose sides are formed by the vectors \(\ve_1 = \left[ \begin{array}{c} 1 \\ 0 \end{array} \right]\) and \(\ve_2 = \left[ \begin{array}{c} 0 \\ 1 \end{array} \right]\) as shown in the first picture in Figure 19.3.

To apply \(T\) we first multiply \(\ve_1\) and \(\ve_2\) by \(P^{-1}\text{.}\) This gives us

So \(P^{-1}\) transforms the standard coordinate system into a coordinate system in which columns of \(P^{-1}\) determine the axes, as illustrated in the second picture in Figure 19.3. Applying \(D\) to the output scales by 2 in the first component and by \(4\) in the second component as depicted in the third picture in Figure 19.3. Finally, we apply \(P\) to translate back into the standard \(xy\) coordinate system as shown in the last picture in Figure 19.3. In this case, we can visualize that when we apply the transformation \(T\) to a vector in this system it is just scaled in the \(P^{-1}\ve_1-P^{-1}\ve_2\) system by the matrix \(D\text{.}\) Then the matrix \(P\) translates everything back to the standard \(xy\) coordinate system.

This geometric perspective provides another example of how having a matrix similar to a diagonal matrix informs us about the situation. In what follows we determine the conditions that determine when a matrix is similar to a diagonal matrix.

Subsection Diagonalization in General

In Preview Activity 19.1 and in the matrix transformation example we found that a matrix \(A\) was similar to a diagonal matrix whose columns were eigenvectors of \(A\text{.}\) This will work for a general \(n \times n\) matrix \(A\) as long as we can find an invertible matrix \(P\) whose columns are eigenvectors of \(A\text{.}\) More specifically, suppose \(A\) is an \(n \times n\) matrix with \(n\) linearly independent eigenvectors \(\vv_1\text{,}\) \(\vv_1\text{,}\) \(\ldots\text{,}\) \(\vv_n\) with corresponding eigenvalues \(\lambda_1\text{,}\) \(\lambda_1\text{,}\) \(\ldots\text{,}\) \(\lambda_n\) (not necessarily distinct). Let

Then

where

Since the columns of \(P\) are linearly independent, we know \(P\) is invertible, and so

In other words, a matrix \(A\) is diagonalizable if \(A\) is similar to a diagonal matrix.

It should be noted that there are square matrices that are not diagonalizable. For example, the matrix \(A = \left[ \begin{array}{cc} 1\amp 1 \\ 0\amp 1 \end{array} \right]\) has 1 as its only eigenvalue and the dimension of the eigenspace of \(A\) corresponding to the eigenvalue is one. Therefore, it will be impossible to find two linearly independent eigenvectors for \(A\text{.}\)

We showed previously that eigenvectors corresponding to distinct eigenvalue are always linearly independent, so if an \(n \times n\) matrix \(A\) has \(n\) distinct eigenvalues then \(A\) is diagonalizable. Activity 19.6 (b) shows that it is possible to diagonalize an \(n \times n\) matrix even if the matrix does not have \(n\) distinct eigenvalues. In general, we can diagonalize a matrix as long as the dimension of each eigenspace is equal to the multiplicity of the corresponding eigenvalue. In other words, a matrix is diagonalizable if the geometric multiplicity is the same is the algebraic multiplicity for each eigenvalue.

At this point we might ask one final question. We argued that if an \(n \times n\) matrix \(A\) has \(n\) linearly independent eigenvectors, then \(A\) is diagonalizable. It is reasonable to wonder if the converse is true — that is, if \(A\) is diagonalizable, must \(A\) have \(n\) linearly independent eigenvectors? The answer is yes, and you are asked to show this in Exercise 6. We summarize the result in the following theorem.

Subsection Examples

What follows are worked examples that use the concepts from this section.

Subsection Summary

• A matrix \(D = [d_{ij}]\) is a diagonal matrix if \(d_{ij} = 0\) whenever \(i \neq j\text{.}\)

• A matrix \(A\) is diagonalizable if there is an invertible matrix \(P\) so that \(P^{-1}AP\) is a diagonal matrix.

• Two matrices \(A\) and \(B\) are similar if there is an invertible matrix \(P\) so that

  \begin{equation*} B = P^{-1}AP\text{.} \end{equation*}

• Similar matrices have the same determinants, same characteristic polynomials, and same eigenvalues. Note that similar matrices do not necessarily have the same eigenvectors corresponding to the same eigenvalues.

• An \(n \times n\) matrix \(A\) is diagonalizable if and only if \(A\) has \(n\) linearly independent eigenvectors.

• When an \(n \times n\) matrix \(A\) is diagonalizable, then \(P = [ \vv_1 \ \vv_2 \ \vv_3 \ \cdots \ \vv_n]\) is invertible and \(P^{-1}AP\) is diagonal, where \(\vv_1\text{,}\) \(\vv_2\text{,}\) \(\ldots\text{,}\) \(\vv_n\) are \(n\) linearly independent eigenvectors for \(A\text{.}\)

• One use for diagonalization is that once we have diagonalized a matrix \(A\) we can quickly and easily compute powers of \(A\text{.}\) Diagonalization can also help us understand the actions of matrix transformations.

Subsection Project: Binet's Formula for the Fibonacci Numbers

We return to the Fibonacci sequence \(F_n\) where \(F_{n+2} = F_{n+1} + F_{n}\text{,}\) for \(n \geq 0\text{,}\) \(F_0 = 0\text{,}\) and \(F_1=1\text{.}\) Since \(F_{n+2}\) is determined by previous values \(F_{n+1}\) and \(F_n\text{,}\) the relation \(F_{n+2} = F_{n+1} + F_{n}\) is called a recurrence relation. The recurrence relation \(F_{n+2} = F_{n+1} + F_{n}\) is very time consuming to use to compute \(F_n\) for large values of \(n\text{.}\) It turns out that there is a fascinating formula that gives the \(n\)th term of the Fibonacci sequence directly, without using the relation \(F_{n+2} = F_{n+1} + F_{n}\text{.}\)

The matrix equation (19.5) shows us how to find the vectors \(\vx_n\) using powers of the matrix \(A\text{:}\)

So if we can somehow easily find the powers of the matrix \(A\text{,}\) then we can find a convenient formula for \(F_n\text{.}\) As we have seen, we know how to do this if \(A\) is diagonalizable

Now that we have the eigenvalues and know corresponding eigenvectors for \(A\text{,}\) we can return to the problem of diagonalizing \(A\text{.}\)

Now we can find a formula for the \(n\)th Fibonacci number.

Formula (19.6) is called Binet's formula. It is a very surprising formula in the fact that the expression on the right hand side of (19.6) is an integer for each positive integer \(n\text{.}\) Note that with Binet's formula we can quickly compute \(F_n\) for very large values of \(n\text{.}\) For example,

The number \(\varphi = \frac{1+\sqrt{5}}{2}\text{,}\) called the golden mean or golden ratio is intimately related to the Fibonacci sequence. Binet's formula provides a fascinating relationship between the Fibonacci numbers and the golden ratio. The golden ratio also occurs often in other areas of mathematics. It was an important number to the ancient Greek mathematicians who felt that the most aesthetically pleasing rectangles had sides in the ratio of \(\varphi:1\text{.}\)