Skip to main content
Logo image

A First Course in Linear Algebra

Robert A. Beezer

Section SD Similarity and Diagonalization

This section’s topic will perhaps seem out of place at first, but we will make the connection soon with eigenvalues and eigenvectors. This is also our first look at one of the central ideas of Chapter R.
🔗

Subsection SM Similar Matrices

The notion of matrices being “similar” is a lot like saying two matrices are row-equivalent. Two similar matrices are not equal, but they share many important properties. This section, and later sections in Chapter R will be devoted in part to discovering just what these common properties are.
🔗
First, the main definition for this section.
🔗

Definition SIM. Similar Matrices.

Suppose A and B are two square matrices of size n. Then A and B are similar if there exists a nonsingular matrix of size n, S, such that S−1AS=B.
🔗
Equivalently, we can require that AS=SB.
🔗
🔗
We will say “A is similar to B via S” when we want to emphasize the role of S in the relationship between A and B. Also, it does not matter if we say A is similar to B, or B is similar to A. If one statement is true then so is the other, as can be seen by using S−1 in place of S (see Theorem SER for the careful proof). Finally, we will refer to S−1AS as a similarity transformation when we want to emphasize the way S changes A. OK, enough about language, let us build a few examples.
🔗

Example SMS5. Similar matrices of size 5.

If you wondered if there are examples of similar matrices, then it will not be hard to convince you they exist. Define
A=[−41−3−2212−13−2−41322−34−2−1−331−11−4]S=[12−11101−1−2−113−111−2−331−213−121].
Check that S is nonsingular and then compute
B=S−1AS=[10102−5−101003021−300−101−4−11−11][−41−3−2212−13−2−41322−34−2−1−331−11−4][12−11101−1−2−113−111−2−331−213−121]=[−10−27−29−80−25−26610−2−311−9−14−9−1−130−10−1113564919].
So by this construction, we know that A and B are similar.
Let us do that again.
🔗

Example SMS3. Similar matrices of size 3.

Define
A=[−13−8−4127424167]S=[112−2−1−31−20].
Check that S is nonsingular and then compute
B=S−1AS=[−6−4−1−3−2−1531][−13−8−4127424167][112−2−1−31−20]=[−10003000−1].
So by this construction, we know that A and B are similar. But before we move on, look at how pleasing the form of B is. Not convinced? Then consider that several computations related to B are especially easy. For example, in the spirit of Example DUTM, det(B)=(−1)(3)(−1)=3. Similarly, the characteristic polynomial is straightforward to compute by hand, pB(x)=(−1−x)(3−x)(−1−x)=−(x−3)(x+1)2 and since the result is already factored, the eigenvalues are transparently λ=3,−1. Finally, the eigenvectors of B are just the standard unit vectors (Definition SUV).
🔗

Subsection PSM Properties of Similar Matrices

Similar matrices share many properties and it is these theorems that justify the choice of the word “similar.” First we will show that similarity is an equivalence relation. Equivalence relations are important in the study of various algebras and can always be regarded as a kind of weak version of equality. Sort of alike, but not quite equal. The notion of two matrices being row-equivalent is an example of an equivalence relation we have been working with since the beginning of the course (see Exercise RREF.T11). Row-equivalent matrices are not equal, but they are a lot alike. For example, row-equivalent matrices have the same rank. Formally, an equivalence relation requires three conditions hold: reflexive, symmetric and transitive. We will illustrate these as we prove that similarity is an equivalence relation.
🔗

Proof.

To see that A is similar to A, we need only demonstrate a nonsingular matrix that effects a similarity transformation of A to A. In is nonsingular (since it row-reduces to the identity matrix, Theorem NMRRI). Then
AIn=A=InA
and we see that A is similar to A via the nonsingular matrix In.
If we assume that A is similar to B, then we know there is a nonsingular matrix S so that AS=SB by Definition SIM. By Theorem MIMI, S−1 is invertible, and by Theorem NI is therefore nonsingular. Then
BS−1=(S−1S)BS−1=S−1(SB)S−1=S−1(AS)S−1=S−1A(SS−1)=S−1A
and we see that B is similar to A via the nonsingular matrix S−1R.
If we assume that A is similar to B, and B is similar to C, then we know there are two nonsingular matrices, S and R, such that AS=SB and BR=RC, by Definition SIM. (Notice how we cannot presume S and R are the same matrix!) Since S and R are invertible, so too SR is invertible by Theorem SS and then nonsingular by Theorem NI. Then
A(SR)=(AS)R=(SB)R=S(BR)=S(RC)=(SR)C
so A is similar to C via the nonsingular matrix SR.
Here is another theorem that tells us exactly what sorts of properties similar matrices share.
🔗

Proof.

Suppose that A and B are similar via S, so AS=SB. Let x≠0 be an eigenvector of B for the eigenvalue λ. Since S is nonsingular, Definition NM implies that Sx≠0. Furthermore
A(Sx)=(AS)x=(SB)x=S(Bx)=S(λx)=λ(Sx)
demonstrating that Sx is an eigenvector of A for λ. So every eigenvalue of B is an eigenvalue of A. Exchanging the roles of A and B (and employing the nonsingular matrix S−1) will show that every eigenvalue of A is an eigenvalue of B. So the eigenvalues of A and the eigenvalues of B are equal as sets (Definition SE).
Suppose that C={x1,x2,x3,…,xk} is a basis for the eigenspace of λ for the matrix B. Then each vector of the set D={Sx1,Sx2,Sx3,…,Sxk} is an eigenvector of A for λ, by the same argment in the previous paragraph. It is an exercise to show that because S is nonsingular, the linear independence of C implies the linear independence of D. Thus, by Theorem G we have
γB(λ)≤γA(λ).
Exchanging the roles of A and B gives the inequality in the other direction, implying equality of the geometric multiplicities.
To understand the algebraic multiplicities, it is necessary to consult the characteristic polynomials of the two matrices. The initial expression here looks contrived, but its purpose will be clear shortly.
det(S)(pA(x)−pB(x))=det(S)(det(A−xIn)−det(B−xIn))Definition CP=det(S)det(A−xIn)−det(S)det(B−xIn)Property DCN=det(A−xIn)det(S)−det(S)det(B−xIn)Property CMCN=det((A−xIn)S)−det(S(B−xIn))Theorem DRMM=det(AS−xS)−det(SB−xS)Theorem MMDAA=det(SB−xS)−det(SB−xS)Definition SIM=0Property AICN
Notice that the expressions in these equalities are scalar quantities, and nearly half of the theorems given as explanations are simply properties from Theorem PCNA. But the key step is the application of the multiplicative property of the determinant, Theorem DRMM, along with a setup using scalar commutativity, Property CMCN.
Because S is nonsingular, its determinant is nonzero (Theorem SMZD), and by Theorem ZPZF, we conclude that pA(x)−pB(x)=0. Since the characteristic polynomials of A and B are equal, they will factor identically, and the algebraic multiplicity of each eigenvalue will be the same for each matrix.
Be very careful with this theorem. It is tempting to think the converse is true, and argue that if two matrices have the same eigenvalues, then they are similar. Not so, as the following example illustrates. So do not think this theorem is a route to establishing that two matrices are similar.
🔗

Example EENS. Equal eigenvalues, not similar.

Define
A=[1101]B=[1001]
and check that
pA(x)=pB(x)=1−2x+x2=(x−1)2
and so A and B have equal characteristic polynomials. If the converse of Theorem SMEE were true, then A and B would be similar. Suppose this is the case. More precisely, suppose there is a nonsingular matrix S so that A=S−1BS.
Then
A=S−1BS=S−1I2S=S−1S=I2.
Clearly A≠I2 and this contradiction tells us that two matrices can have the same eigenvalues but not be similar. (Note that the geometric multiplicity of the eigenvalue of λ=1 is different for the two matrices. So strictly speaking this example does not prove that the converse of Theorem SMEE is false. We are simply cautioning against a frequent temptation.)

Sage SM. Similar Matrices.

It is quite easy to determine if two matrices are similar, using the matrix method .is_similar(). However, computationally this can be a very difficult proposition, so support in Sage is incomplete now, though it will always return a result for matrices with rational entries. Here are examples where the two matrices are, and are not, similar. Notice that the keyword option transformation=True will cause a pair to be returned, such that if the matrices are indeed similar, the matrix effecting the similarity transformation will be in the second slot of the pair.
Since we knew in advance these two matrices are similar, we requested the transformation matrix, so the output is a pair. The similarity matrix is a bit of a mess, so we will use three Sage routines to clean up trans. We convert the entries to numerical approximations, clip very small values (less than 10−5) to zero and then round to three decimal places. You can experiment printing just trans all by itself.
The matrix C is not similar to A (and hence not similar to B by Theorem SER), so we illustrate the return value when we do not request the similarity matrix (since it does not even exist).
🔗

Subsection D Diagonalization

Good things happen when a matrix is similar to a diagonal matrix. For example, the eigenvalues of the matrix are the entries on the diagonal of the diagonal matrix. And it can be a much simpler matter to compute high powers of the matrix. Diagonalizable matrices are also of interest in more abstract settings. Here are the relevant definitions, then our main theorem for this section.
🔗

Definition DIM. Diagonal Matrix.

Suppose that A is a square matrix. Then A is a diagonal matrix if [A]ij=0 whenever i≠j.
🔗
🔗

Definition DZM. Diagonalizable Matrix.

Suppose A is a square matrix. Then A is diagonalizable if A is similar to a diagonal matrix.
🔗
🔗

Example DAB. Diagonalization of Archetype B.

Archetype B has a 3×3 coefficient matrix
B=[−7−6−12557104]
and is similar to a diagonal matrix, as can be seen by the following computation with the nonsingular matrix S,
S−1BS=[−5−3−2321111]−1[−7−6−12557104][−5−3−2321111]=[−1−1−1231−1−21][−7−6−12557104][−5−3−2321111]=[−100010002].
Example SMS3 provides yet another example of a matrix that is subjected to a similarity transformation and the result is a diagonal matrix. Alright, just how would we find the magic matrix S that can be used in a similarity transformation to produce a diagonal matrix? Before you read the statement of the next theorem, you might study the eigenvalues and eigenvectors of Archetype B and compute the eigenvalues and eigenvectors of the matrix in Example SMS3.
🔗

Proof.

(⇐) 
Let S={x1,x2,x3,…,xn} be a linearly independent set of eigenvectors of A for the eigenvalues λ1,λ2,λ3,…,λn. Recall Definition SUV and define
R=[x1|x2|x3|…|xn]D=[λ100⋯00λ20⋯000λ3⋯0⋮⋮⋮⋮000⋯λn]=[λ1e1|λ2e2|λ3e3|…|λnen].
The columns of R are the vectors of the linearly independent set S and so by Theorem NMLIC the matrix R is nonsingular. We have
AR=A[x1|x2|x3|…|xn]=[Ax1|Ax2|Ax3|…|Axn]Definition MM=[λ1x1|λ2x2|λ3x3|…|λnxn]Definition EEM=[λ1Re1|λ2Re2|λ3Re3|…|λnRen]Definition MVP=[R(λ1e1)|R(λ2e2)|R(λ3e3)|…|R(λnen)]Theorem MMSMM=R[λ1e1|λ2e2|λ3e3|…|λnen]Definition MM=RD.
This says that A is similar to the diagonal matrix D via the nonsingular matrix R. Thus A is diagonalizable (Definition DZM).
(⇒) 
Suppose that A is diagonalizable, so there is a nonsingular matrix T of size n and a diagonal matrix E (recall Definition SUV)
T=[y1|y2|y3|…|yn]E=[d100⋯00d20⋯000d3⋯0⋮⋮⋮⋮000⋯dn]=[d1e1|d2e2|d3e3|…|dnen]
such that AT=TE.
Then consider,
[Ay1|Ay2|Ay3|…|Ayn]=A[y1|y2|y3|…|yn]Definition MM=AT=TEDefinition SIM=T[d1e1|d2e2|d3e3|…|dnen]=[T(d1e1)|T(d2e2)|T(d3e3)|…|T(dnen)]Definition MM=[d1Te1|d2Te2|d3Te3|…|dnTen]Theorem MMSMM=[d1y1|d2y2|d3y3|…|dnyn]Definition MVP.
This equality of matrices (Definition ME) allows us to conclude that the individual columns are equal vectors (Definition CVE). That is, Ayi=diyi for 1≤i≤n. In other words, yi is an eigenvector of A for the eigenvalue di, 1≤i≤n. (Why does yi≠0?). Because T is nonsingular, the set containing T’s columns, S={y1,y2,y3,…,yn}, is a linearly independent set (Theorem NMLIC). So the set S has all the required properties.
Notice that the proof of Theorem DC is constructive. To diagonalize a matrix, we need only locate n linearly independent eigenvectors. Then we can construct a nonsingular matrix using the eigenvectors as columns (R) so that R−1AR is a diagonal matrix (D). The entries on the diagonal of D will be the eigenvalues of the eigenvectors used to create R, in the same order as the eigenvectors appear in R. We illustrate this by diagonalizing some matrices.
🔗

Example DMS3. Diagonalizing a matrix of size 3.

Consider the matrix
F=[−13−8−4127424167]
of Example CPMS3, Example EMS3 and Example ESMS3. F’s eigenvalues and eigenspaces are
λ=3EF(3)=⟨{[−12121]}⟩λ=−1EF(−1)=⟨{[−2310],[−1301]}⟩.
Define the matrix S to be the 3×3 matrix whose columns are the three basis vectors in the eigenspaces for F,
S=[−12−23−131210101].
Check that S is nonsingular (row-reduces to the identity matrix, Theorem NMRRI, or has a nonzero determinant, Theorem SMZD). Then the three columns of S are a linearly independent set (Theorem NMLIC). By Theorem DC we now know that F is diagonalizable. Furthermore, the construction in the proof of Theorem DC tells us that if we apply the matrix S to F in a similarity transformation, the result will be a diagonal matrix with the eigenvalues of F on the diagonal. The eigenvalues appear on the diagonal of the matrix in the same order as the eigenvectors appear in S. So,
S−1FS=[−12−23−131210101]−1[−13−8−4127424167][−12−23−131210101]=[642−3−1−1−6−4−1][−13−8−4127424167][−12−23−131210101]=[3000−1000−1].
Note that the above computations can be viewed two ways. The proof of Theorem DC tells us that the four matrices (F, S, F−1 and the diagonal matrix) will interact the way we have written the equation. Or as an example, we can actually perform the computations to verify what the theorem predicts.
The dimension of an eigenspace can be no larger than the algebraic multiplicity of the eigenvalue by Theorem ME. When every eigenvalue’s eigenspace is this large, then we can diagonalize the matrix, and only then. Three examples we have seen so far in this section, Example SMS5, Example DAB and Example DMS3, illustrate the diagonalization of a matrix, with varying degrees of detail about just how the diagonalization is achieved. However, in each case, you can verify that the geometric and algebraic multiplicities are equal for every eigenvalue. This is the substance of the next theorem.
🔗

Proof.

Suppose A has size n and k distinct eigenvalues, λ1,λ2,λ3,…,λk. Let Si={xi1,xi2,xi3,…,xiγA(λi)}, denote a basis for the eigenspace of λi, EA(λi), for 1≤i≤k. Then
S=S1∪S2∪S3∪⋯∪Sk
is a set of eigenvectors for A. A vector cannot be an eigenvector for two different eigenvalues (see Exercise EE.T20) so Si∩Sj=∅ whenever i≠j. In other words, S is a disjoint union of Si, 1≤i≤k.
(⇐) 
The size of S is
|S|=∑i=1kγA(λi)S disjoint union of Si=∑i=1kαA(λi)Hypothesis=nTheorem NEM.
We next show that S is a linearly independent set. So we will begin with a relation of linear dependence on S, using doubly-subscripted scalars and eigenvectors,
0=(a11x11+a12x12+⋯+a1γA(λ1)x1γA(λ1))+(a21x21+a22x22+⋯+a2γA(λ2)x2γA(λ2))+(a31x31+a32x32+⋯+a3γA(λ3)x3γA(λ3))+⋮(ak1xk1+ak2xk2+⋯+akγA(λk)xkγA(λk)).
Define the vectors yi, 1≤i≤k by
y1=(a11x11+a12x12+a13x13+⋯+a1γA(λ1)x1γA(λ1))y2=(a21x21+a22x22+a23x23+⋯+a2γA(λ2)x2γA(λ2))y3=(a31x31+a32x32+a33x33+⋯+a3γA(λ3)x3γA(λ3))⋮yk=(ak1xk1+ak2xk2+ak3xk3+⋯+akγA(λk)xkγA(λk)).
Then the relation of linear dependence becomes
0=y1+y2+y3+⋯+yk.
Since the eigenspace EA(λi) is closed under vector addition and scalar multiplication, yi∈EA(λi), 1≤i≤k. Thus, for each i, the vector yi is an eigenvector of A for λi, or is the zero vector. Recall that sets of eigenvectors whose eigenvalues are distinct form a linearly independent set by Theorem EDELI. Should any (or some) yi be nonzero, the previous equation would provide a nontrivial relation of linear dependence on a set of eigenvectors with distinct eigenvalues, contradicting Theorem EDELI. Thus yi=0, 1≤i≤k.
Each of the k equations, yi=0, is a relation of linear dependence on the corresponding set Si, a set of basis vectors for the eigenspace EA(λi), which is therefore linearly independent. From these relations of linear dependence on linearly independent sets we conclude that the scalars are all zero, more precisely, aij=0, 1≤j≤γA(λi) for 1≤i≤k. This establishes that our original relation of linear dependence on S has only the trivial relation of linear dependence, and hence S is a linearly independent set.
We have determined that S is a set of n linearly independent eigenvectors for A, and so by Theorem DC is diagonalizable.
(⇒) 
Now we assume that A is diagonalizable. Aiming for a contradiction (Proof Technique CD), suppose that there is at least one eigenvalue, say λt, such that γA(λt)≠αA(λt). By Theorem ME we must have γA(λt)<αA(λt), and γA(λi)≤αA(λi) for 1≤i≤k, i≠t.
Since A is diagonalizable, Theorem DC guarantees a set of n linearly independent vectors, all of which are eigenvectors of A. Let ni denote the number of eigenvectors in S that are eigenvectors for λi, and recall that a vector cannot be an eigenvector for two different eigenvalues (Exercise EE.T20). S is a linearly independent set, so the subset Si containing the ni eigenvectors for λi must also be linearly independent. Because the eigenspace EA(λi) has dimension γA(λi) and Si is a linearly independent subset in EA(λi), Theorem G tells us that ni≤γA(λi), for 1≤i≤k.
Putting all these facts together gives,
n=n1+n2+n3+⋯+nt+⋯+nkDefinition SU≤γA(λ1)+γA(λ2)+γA(λ3)+⋯+γA(λt)+⋯+γA(λk)Theorem G<αA(λ1)+αA(λ2)+αA(λ3)+⋯+αA(λt)+⋯+αA(λk)Theorem ME=nTheorem NEM.
This is a contradiction (we cannot have n<n!) and so our assumption that some eigenspace had less than full dimension was false.
Example SEE, Example CASE, Example ESMS3, Example ESMS4, Example DEMS5, Archetype B, Archetype F, Archetype K and Archetype L are all examples of matrices that are diagonalizable and that illustrate Theorem DMFE. While we have provided many examples of matrices that are diagonalizable, especially among the archetypes, there are many matrices that are not diagonalizable. Here is one now.
🔗

Example NDMS4. A non-diagonalizable matrix of size 4.

In Example EMMS4 the matrix
B=[−21−2−41214965−2−43−4510]
was determined to have characteristic polynomial
pB(x)=(x−1)(x−2)3
and an eigenspace for λ=2 of
EB(2)=⟨{[−121−121]}⟩.
So the geometric multiplicity of λ=2 is γB(2)=1, while the algebraic multiplicity is αB(2)=3. By Theorem DMFE, the matrix B is not diagonalizable.
Archetype A is the lone archetype with a square matrix that is not diagonalizable, as the algebraic and geometric multiplicities of the eigenvalue λ=0 differ. Example HMEM5 is another example of a matrix that cannot be diagonalized due to the difference between the geometric and algebraic multiplicities of λ=2, as is Example CEMS6 which has two complex eigenvalues, each with differing multiplicities. Likewise, Example EMMS4 has an eigenvalue with different algebraic and geometric multiplicities and so cannot be diagonalized.
🔗

Sage MD. Matrix Diagonalization.

The third way to get eigenvectors is the matrix method .eigenmatrix_right() (and the analogous .eigenmatrix_left()). It always returns two square matrices of the same size as the original matrix. The first matrix of the output is a diagonal matrix with the eigenvalues of the matrix filling the diagonal entries of the matrix. The second matrix has eigenvectors in the columns, in the same order as the corresponding eigenvalues. For a single eigenvalue, these columns/eigenvectors form a linearly independent set.
A careful reading of the previous paragraph suggests the question: what if we do not have enough eigenvectors to fill the columns of the second square matrix? When the geometric multiplicity does not equal the algebraic multiplicity, the deficit is met by inserting zero columns in the matrix of eigenvectors. Conversely, when the matrix is diagonalizable, by Theorem DMFE the geometric and algebraic multiplicities of each eigenvalue are equal, and the union of the bases of the eigenspaces provides a complete set of linearly independent vectors. So for a matrix A, Sage will output two matrices, D and S such that S−1AS=D.
We can rewrite the relation above as AS=SD. In the case of a non-diagonalizable matrix, the matrix of eigenvectors is singular (it has zero columns), but the relationship AS=SD still holds. Here are examples of the two scenarios, along with demonstrations of the matrix method is_diagonalizable().
Now for a matrix that is far from diagonalizable.

Proof.

If we collect a single eigenvector of A for each eigenvalue, then we will have a set of n vectors that Theorem EDELI guarantees is a linearly independent set. Then Theorem DC implies that A is diagonalizable.

Example DEHD. Distinct eigenvalues, hence diagonalizable.

In Example DEMS5 the matrix
H=[1518−86−5531−1−30−45−4−2−43−4617−14152630−128−10]
has characteristic polynomial
pH(x)=x(x−2)(x−1)(x+1)(x+3)
and so is a 5×5 matrix with 5 distinct eigenvalues.
By Theorem DED we know H must be diagonalizable. But just for practice, we exhibit a diagonalization. The matrix S contains eigenvectors of H as columns, one from each eigenspace, guaranteeing linear independent columns and thus the nonsingularity of S. Notice that we are using the versions of the eigenvectors from Example DEMS5 that have integer entries. The diagonal matrix has the eigenvalues of H in the same order that their respective eigenvectors appear as the columns of S. With these matrices, verify computationally that S−1HS=D.
S=[21−111−1020−1−202−1−2−4−10−2−122121]D=[−300000−1000000000001000002].
Note that there are many different ways to diagonalize H. We could replace eigenvectors by nonzero scalar multiples, or we could rearrange the order of the eigenvectors as the columns of S (which would subsequently reorder the eigenvalues along the diagonal of D).
Archetype B is another example of a matrix that has as many distinct eigenvalues as its size, and is hence diagonalizable by Theorem DED.
🔗
Powers of a diagonal matrix are easy to compute, and when a matrix is diagonalizable, it is almost as easy. We could state a theorem here perhaps, but we will settle instead for an example that makes the point just as well.
🔗

Example HPDM. High power of a diagonalizable matrix.

Suppose that
A=[190613−33−1−9−2121−41221−362−14−28]
and we wish to compute A20. Normally this would require 19 matrix multiplications, but since A is diagonalizable, we can simplify the computations substantially.
First, we diagonalize A. With
S=[1−12−1−23−331133−21−40]
we find
D=S−1AS=[−61−3−602−2−33012−1−111][190613−33−1−9−2121−41221−362−14−28][1−12−1−23−331133−21−40]=[−1000000000200001].
Now we find an alternate expression for A20,
A20=AAA…A=InAInAInAIn…InAIn=(SS−1)A(SS−1)A(SS−1)A(SS−1)…(SS−1)A(SS−1)=S(S−1AS)(S−1AS)(S−1AS)…(S−1AS)S−1=SDDD…DS−1=SD20S−1
and since D is a diagonal matrix, powers are much easier to compute,
=S[−1000000000200001]20S−1=S[(−1)200000(0)200000(2)200000(1)20]S−1=[1−12−1−23−331133−21−40][1000000000104857600001][−61−3−602−2−33012−1−111]=[6291451220971484194297−9437175−5−3145719−62914419437175−231457286291453−12582900−2−4194298−8388596].
Notice how we effectively replaced the twentieth power of A by the twentieth power of D, and how a high power of a diagonal matrix is just a collection of powers of scalars on the diagonal. The price we pay for this simplification is the need to diagonalize the matrix (by computing eigenvalues and eigenvectors) and finding the inverse of the matrix of eigenvectors. And we still need to do two matrix products. But the higher the power, the greater the savings.
🔗

Subsection FS Fibonacci Sequences

Example FSCF. Fibonacci sequence, closed form.

The Fibonacci sequence is a sequence of integers defined recursively by
a0=0a1=1an+1=an+an−1,n≥1.
So the initial portion of the sequence is 0,1,1,2,3,5,8,13,21,…. 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≥1 the recursive statement above establishes the truth of the statement
[anan+1]=[0111][an−1an].
Let A denote this 2×2 matrix. Through repeated applications of the statement above we have
[anan+1]=A[an−1an]=A2[an−2an−1]=A3[an−3an−2]=⋯=An[a0a1].
In preparation for working with this high power of A, not unlike in Example HPDM, we will diagonalize A. The two distinct eigenvalues of A arise as roots of the polynomial x2−x−1, and are
ρ=1+52δ=1−52.
With two distinct eigenvalues, Theorem DED 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 ρ and δ are roots of the polynomial, in a factored or unfactored form)
ρ+δ=1ρδ=−11+ρ=ρ21+δ=δ2ρ−δ=5.
Then eigenvectors of A (for ρ and δ, respectively) are
[1ρ][1δ]
which can be easily confirmed, as we demonstrate for the eigenvector for ρ,
[0111][1ρ]=[ρ1+ρ]=[ρρ2]=ρ[1ρ].
From the proof of Theorem DC we know A can be diagonalized by a matrix S with these eigenvectors as columns, giving D=S−1AS. We list S, S−1 and the diagonal matrix D,
S=[11ρδ]S−1=1ρ−δ[−δ1ρ−1]D=[ρ00δ].
OK, we have everything in place now. The main step in the following is to replace A by SDS−1. Here we go,
[anan+1]=An[a0a1]=(SDS−1)n[a0a1]=SDS−1SDS−1SDS−1⋯SDS−1[a0a1]=SDDD⋯DS−1[a0a1]=SDnS−1[a0a1]=[11ρδ][ρ00δ]n1ρ−δ[−δ1ρ−1][a0a1]=1ρ−δ[11ρδ][ρn00δn][−δ1ρ−1][01]=1ρ−δ[11ρδ][ρn00δn][1−1]=1ρ−δ[11ρδ][ρn−δn]=1ρ−δ[ρn−δnρn+1−δn+1].
Performing the scalar multiplication and equating the first entries of the two vectors, we arrive at the closed form expression
an=1ρ−δ(ρn−δn)=15((1+52)n−(1−52)n)=12n5((1+5)n−(1−5)n).
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 5 might make us suspicious. But no, our expression for an 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.
We close this section with a comment about an important upcoming theorem that we prove in Chapter R. A consequence of Theorem OD is that every Hermitian matrix (Definition HM) is diagonalizable (Definition DZM), and the similarity transformation that accomplishes the diagonalization uses a unitary matrix (Definition UM). This means that for every Hermitian matrix of size n there is a basis of Cn that is composed entirely of eigenvectors for the matrix and also forms an orthonormal set (Definition ONS). Notice that for matrices with only real entries, we only need the hypothesis that the matrix is symmetric (Definition SYM) to reach this conclusion (Example ESMS4). Can you imagine a prettier basis for use with a matrix? I cannot.
🔗
These results in Section OD explain much of our recurring interest in orthogonality, and make the section a high point in your study of linear algebra. A precise statement of this diagonalization result applies to a slightly broader class of matrices, known as “normal” matrices (Definition NRML), which are matrices that commute with their adjoints. With this expanded category of matrices, the result becomes an equivalence (Proof Technique E). See Theorem OD and Theorem OBNM in Section OD for all the details.
🔗
🔗

Reading Questions SD Reading Questions

1. Equivalence Relation.

What is an equivalence relation?
🔗
🔗

2. Characterization of Diagonalizable.

State a condition that is equivalent to a matrix being diagonalizable, but is not the definition.
🔗
🔗

3. Calculate a Diagonalization.

Find a diagonal matrix similar to
🔗
A=[−58−47].
🔗
🔗
🔗

Exercises SD Exercises

C20.

Consider the matrix A below. First, show that A is diagonalizable by computing the geometric multiplicities of the eigenvalues and quoting the relevant theorem. Second, find a diagonal matrix D and a nonsingular matrix S so that S−1AS=D. (See Exercise EE.C21 for some of the necessary computations.)
🔗
A=[18−1533−15−48−66−99−1695−69−4]
🔗
Solution.
Using a calculator, we find that A has three distinct eigenvalues, λ=3,2,−1, with λ=2 having algebraic multiplicity two, αA(2)=2. The eigenvalues λ=3,−1 have algebraic multiplicity one, and so by Theorem ME we can conclude that their geometric multiplicities are one as well. Together with the computation of the geometric multiplicity of λ=2 from Exercise EE.C21, we know
γA(3)=αA(3)=1γA(2)=αA(2)=2γA(−1)=αA(−1)=1.
This satisfies the hypotheses of Theorem DMFE, and so we can conclude that A is diagonalizable.
A calculator will give us four eigenvectors of A, the two for λ=2 being linearly independent presumably. Or, by hand, we could find basis vectors for the three eigenspaces. For λ=3,−1 the eigenspaces have dimension one, and so any eigenvector for these eigenvalues will be multiples of the ones we use below. For λ=2 there are many different bases for the eigenspace, so your answer could vary. Our eigenvectors are the basis vectors we would have obtained if we had actually constructed a basis in Exercise EE.C21 rather than just computing the dimension.
By the construction in the proof of Theorem DC, the required matrix S has columns that are four linearly independent eigenvectors of A and the diagonal matrix has the eigenvalues on the diagonal (in the same order as the eigenvectors in S). Here are the pieces, “doing” the diagonalization,
[−10−36−2−1−10001−31101]−1[18−1533−15−48−66−99−1695−69−4][−10−36−2−1−10001−31101]=[300002000020000−1].
🔗

C21.

Determine if the matrix A below is diagonalizable. If the matrix is diagonalizable, then find a diagonal matrix D that is similar to A, and provide the invertible matrix S that performs the similarity transformation. You should use your calculator to find the eigenvalues of the matrix, but try only using the row-reducing function of your calculator to assist with finding eigenvectors.
🔗
A=[19924−3−27−29−68111132617718]
🔗
Solution.
A calculator will provide the eigenvalues λ=2,2,1,0, so we can reconstruct the characteristic polynomial as
pA(x)=(x−2)2(x−1)x
so the algebraic multiplicities of the eigenvalues are
αA(2)=2αA(1)=1αA(0)=1.
Now compute eigenspaces by hand, obtaining null spaces for each of the three eigenvalues by constructing the correct singular matrix (Theorem EMNS),
A−2I4=[−19924−3−29−29−68111112617716]→RREF[100−320115200000000]EA(2)=N(A−2I4)=⟨{[32−5201],[0−110]}⟩=⟨{[3−502],[0−110]}⟩A−1I4=[09924−3−28−29−68111122617717]→RREF[100−53010133001−530000]EA(1)=N(A−I4)=⟨{[53−133531]}⟩=⟨{[5−1353]}⟩A−0I4=[19924−3−27−29−68111132617718]→RREF[100−30105001−20000]EA(0)=N(A)=⟨{[3−521]}⟩.
From this we can compute the dimensions of the eigenspaces to obtain the geometric multiplicities,
γA(2)=2γA(1)=1γA(0)=1.
For each eigenvalue, the algebraic and geometric multiplicities are equal and so by Theorem DMFE we now know that A is diagonalizable. The construction in Theorem DC suggests we form a matrix whose columns are eigenvectors of A
S=[3053−5−1−13−501522031].
Since det(S)=−1≠0, we know that S is nonsingular (Theorem SMZD), so the columns of S are a set of 4 linearly independent eigenvectors of A. By the proof of Theorem SMZD we know
S−1AS=[2000020000100000]
is a diagonal matrix with the eigenvalues of A along the diagonal, in the same order as the associated eigenvectors appear as columns of S.
🔗

C22.

Consider the matrix A below. Find the eigenvalues of A using a calculator and use these to construct the characteristic polynomial of A, pA(x). State the algebraic multiplicity of each eigenvalue. Find all of the eigenspaces for A by computing expressions for null spaces, only using your calculator to row-reduce matrices. State the geometric multiplicity of each eigenvalue. Is A diagonalizable? If not, explain why. If so, find a diagonal matrix D that is similar to A.
🔗
A=[1925305−23−30−35−579101−3−4−5−1]
🔗
Solution.
A calculator will report λ=0 as an eigenvalue of algebraic multiplicity of 2, and λ=−1 as an eigenvalue of algebraic multiplicity 2 as well. Since eigenvalues are roots of the characteristic polynomial (Theorem EMRCP) we have the factored version
pA(x)=(x−0)2(x−(−1))2=x2(x2+2x+1)=x4+2x3+x2.
The eigenspaces are then
λ=0A−(0)I4=[1925305−23−30−35−579101−3−4−5−1]→RREF[10−5−5015400000000]EA(0)=N(C−(0)I4)=⟨{[5−510],[5−401]}⟩λ=−1A−(−1)I4=[2025305−23−29−35−579111−3−4−50]→RREF[10−14012−300000000]EA(−1)=N(C−(−1)I4)=⟨{[1−210],[−4301]}⟩.
Each eigenspace above is described by a spanning set obtained through an application of Theorem BNS and so is a basis for the eigenspace. In each case the dimension, and therefore the geometric multiplicity, is 2.
For each of the two eigenvalues, the algebraic and geometric multiplicities are equal. Theorem DMFE says that in this situation the matrix is diagonalizable. We know from Theorem DC that when we diagonalize A the diagonal matrix will have the eigenvalues of A on the diagonal (in some order). So we can claim that
D=[0000000000−10000−1].
🔗

T15.

Suppose that A and B are similar matrices of size n. Prove that A3 and B3 are similar matrices. Generalize.
🔗
Solution.
By Definition SIM we know that there is a nonsingular matrix S so that AS=SB. Then
A3S=A2AS=A2SB=AASB=ASBB=ASB2=SBB2=SB3
So A3 is similar to B3 (via the matrix S).
More generally, if A is similar to B, and m is a non-negative integer, then Am is similar to Bm. This can be proved carefully using induction (Proof Technique I).
🔗

T16.

Suppose that A and B are similar matrices, with A nonsingular. Prove that B is nonsingular, and that A−1 is similar to B−1.
🔗
Solution.
There is a nonsingular matrix S such that AS=SB. With our hypothesis that A is nonsingular, Theorem NPNF says AS is nonsingular. Then SB is nonsingular, and the “other half” of Theorem NPNF says B is nonsingular.
With B nonsingular, Theorem NI allows us to employ B−1. Use Theorem SS twice to see
B−1S−1=(SB)−1=(AS)−1=S−1A−1
So by Definition SIM, A−1 is similar to B−1.
🔗

T17.

Suppose that B is a nonsingular matrix. Prove that AB is similar to BA.
🔗
Solution.
The nonsingular matrix B will provide the desired similarity transformation,
(BA)B=B(AB).
Done. That was almost too easy!
🔗
🔗
You have attempted 1 of 4 activities on this page.
🔗
PrevTopNext