22. Diagonalization and Powers of A

<div id="text-container" class="style-scope ytd-channel-name"><a class="yt-simple-endpoint style-scope yt-formatted-string" spellcheck="false" href="https://www.youtube.com/channel/UCEBb1b_L6zDS3xTUrIALZOw">MIT OpenCourseWare</a></div>

</div>

2.21M subscribers</div>

<div id="subscribe-button" class="style-scope ytd-video-secondary-info-renderer">SUBSCRIBED

</div>

<div id="description" class="style-scope ytd-video-secondary-info-renderer">MIT 18.06 Linear Algebra, Spring 2005 Instructor: Gilbert Strang View the complete course: <a class="yt-simple-endpoint style-scope yt-formatted-string" spellcheck="false" href="https://www.youtube.com/redirect?q=http%3A%2F%2Focw.mit.edu%2F18-06S05&event=video_description&v=13r9QY6cmjc&redir_token=Lv_K5ZlDYVkcb1ibmwdtQSk0HEV8MTU3NjUzNzc4MEAxNTc2NDUxMzgw" target="blank" rel="nofollow">http://ocw.mit.edu/18-06S05</a> YouTube Playlist: <a class="yt-simple-endpoint style-scope yt-formatted-string" spellcheck="false" href="https://www.youtube.com/playlist?list=PLE7DDD91010BC51F8" rel="nofollow">https://www.youtube.com/playlist?list...</a> 22. Diagonalization and Powers of A License: Creative Commons BY-NC-SA More information at <a class="yt-simple-endpoint style-scope yt-formatted-string" spellcheck="false" href="https://www.youtube.com/redirect?q=https%3A%2F%2Focw.mit.edu%2Fterms&event=video_description&v=13r9QY6cmjc&redir_token=Lv_K5ZlDYVkcb1ibmwdtQSk0HEV8MTU3NjUzNzc4MEAxNTc2NDUxMzgw" target="blank" rel="nofollow">https://ocw.mit.edu/terms</a> More courses at <a class="yt-simple-endpoint style-scope yt-formatted-string" spellcheck="false" href="https://www.youtube.com/redirect?q=https%3A%2F%2Focw.mit.edu&event=video_description&v=13r9QY6cmjc&redir_token=Lv_K5ZlDYVkcb1ibmwdtQSk0HEV8MTU3NjUzNzc4MEAxNTc2NDUxMzgw" target="_blank" rel="nofollow">https://ocw.mit.edu</a></div>

<div class="style-scope ytd-video-secondary-info-renderer">00:10
OK.
00:11
Shall we start?
00:11
This is the second lecture on eigenvalues.
00:15
So the first lecture was --
00:18
reached the key equation, A x equal lambda x.
00:22
x is the eigenvector and lambda's the eigenvalue.
00:27
Now to use that.
00:30
And the, the good way to, after we've found --
00:36
so, so job one is to find the eigenvalues
00:39
and find the eigenvectors.
00:41
Now after we've found them, what do we do with them?
00:44
Well, the good way to see that is diagonalize the matrix.
00:50
So the matrix is A.
00:52
And I want to show -- first of all,
00:55
this is like the basic fact.
00:57
This, this formula.
00:58
That's, that's the key to today's lecture.
01:03
This matrix A, I put its eigenvectors
01:06
in the columns of a matrix S.
01:09
So S will be the eigenvector matrix.
01:12
And I want to look at this magic combination S inverse A S.
01:19
So can I show you how that --
01:22
what happens there?
01:24
And notice, there's an S inverse.
01:27
We have to be able to invert this eigenvector matrix S.
01:33
So for that, we need n independent eigenvectors.
01:38
So that's the, that's the case.
01:41
OK.
01:42
So suppose we have n linearly independent eigenvectors
01:53
of A. Put them in the columns of this matrix S.
02:11
So I'm naturally going to call that the eigenvector matrix,
02:15
because it's got the eigenvectors in its columns.
02:18
And all I want to do is show you what happens
02:21
when you multiply A times S.
02:24
So A times S.
02:29
So this is A times the matrix with the first eigenvector
02:34
in its first column, the second eigenvector
02:37
in its second column, the n-th eigenvector in its n-th column.
02:42
And how I going to do this matrix multiplication?
02:46
Well, certainly I'll do it a column at a time.
02:49
And what do I get.
02:52
A times the first column gives me the first column
02:55
of the answer, but what is it?
02:57
That's an eigenvector.
03:00
A times x1 is equal to the lambda times the x1.
03:04
And that lambda's we're -- we'll call lambda one,
03:06
of course.
03:09
So that's the first column.
03:11
Ax1 is the same as lambda one x1.
03:14
A x2 is lambda two x2.
03:16
So on, along to in the n-th column we now how lambda n xn.
03:24
Looking good, but the next step is even
03:27
better.
03:28
So for the next step, I want to separate out
03:31
those eigenvalues, those, those multiplying numbers,
03:36
from the x-s.
03:38
So then I'll have just what I want.
03:41
OK.
03:42
So how, how I going to separate out?
03:44
So that, that number lambda one is
03:47
multiplying the first column.
03:49
So if I want to factor it out of the first column,
03:52
I better put --
03:55
here is going to be x1, and that's
03:58
going to multiply this matrix lambda
04:02
one in the first entry and all zeros.
04:05
Do you see that that, that's going to come out
04:08
right for the first column?
04:10
Because w- we remember how -- how we're going back to that
04:13
original punchline.
04:15
That if I want a number to multiply x1 then
04:21
I can do it by putting x1 in that column,
04:24
in the first column, and putting that number there.
04:27
Th- u- what I going to have here?
04:28
I'm going to have lambda --
04:30
I'm going to have x1, x2, ...
04:33
,xn.
04:34
These are going to be my columns again.
04:37
I'm getting S back again.
04:39
I'm getting S back again.
04:41
But now what's it multiplied by, on the right it's
04:44
multiplied by?
04:48
If I want lambda n xn in the last column, how do I do it?
04:54
Well, the last column here will be --
04:57
I'll take the last column, use these coefficients,
05:02
put the lambda n down there, and it
05:05
will multiply that n-th column and give me lambda n xn.
05:09
There, there you see matrix multiplication just working
05:13
for us.
05:14
So I started with A S.
05:17
I wrote down what it meant, A times each eigenvector.
05:21
That gave me lambda time the eigenvector.
05:23
And then when I peeled off the lambdas,
05:25
they were on the right-hand side, so I've got S, my matrix,
05:30
back again.
05:31
And this matrix, this diagonal matrix, the eigenvalue matrix,
05:45
and I call it capital lambda.
05:49
Using capital letters for matrices and lambda
05:52
to prompt me that it's, that it's
05:54
eigenvalues that are in there.
05:56
So you see that the eigenvalues are just
05:58
sitting down that diagonal?
06:01
If I had a column x2 here, I would want the lambda two
06:07
in the two two position, in the diagonal position,
06:10
to multiply that x2 and give me the lambda two x2.
06:15
That's my formula.
06:16
A S is S lambda.
06:23
OK.
06:23
That's the -- you see, it's just a calculation.
06:27
Now -- I mentioned, and I have to mention again,
06:31
this business about n independent eigenvectors.
06:37
As it stands, this is all fine, whether --
06:40
I mean, I could be repeating the same eigenvector, but --
06:43
I'm not interested in that.
06:45
I want to be able to invert S, and that's where this comes in.
06:50
This n independent eigenvectors business
06:53
comes in to tell me that that matrix is invertible.
06:56
So let me, on the next board, write down what I've got.
07:01
A S equals S lambda.
07:06
And now I'm, I can multiply on the left by S inverse.
07:11
So this is really --
07:17
I can do that, provided S is invertible.
07:20
Provided my assumption of n independent eigenvectors is
07:26
satisfied.
07:27
And I mentioned at the end of last time, and I'll say again,
07:31
that there's a small number of matrices for --
07:35
that don't have n independent eigenvectors.
07:38
So I've got to discuss that, that technical point.
07:42
But the great -- the most matrices that we see have n di-
07:48
n independent eigenvectors, and we can diagonalize.
07:51
This is diagonalization.
07:54
I could also write it, and I often will,
07:57
the other way round.
07:59
If I multiply on the right by S inverse,
08:03
if I took this equation at the top and multiplied on the right
08:06
by S inverse, I could --
08:08
I would have A left here.
08:10
Now S inverse is coming from the right.
08:15
So can you keep those two straight?
08:18
A multiplies its eigenvectors, that's how I keep them
08:21
straight.
08:21
So A multiplies S.
08:24
A multiplies S.
08:26
And then this S inverse makes the whole thing diagonal.
08:30
And this is another way of saying the same thing,
08:33
putting the Ss on the other side of the equation.
08:36
A is S lambda S inverse.
08:40
So that's the, that's the new factorization.
08:44
That's the replacement for L U from elimination or Q R for --
08:50
from Gram-Schmidt.
08:52
And notice that the matrix -- so it's, it's a matrix times
08:56
a diagonal matrix times the inverse of the first one.
09:00
It's, that's the combination that we'll
09:02
see throughout this chapter.
09:05
This combination with an S and an S inverse.
09:09
OK.
09:10
Can I just begin to use that?
09:14
For example, what about A squared?
09:17
What are the eigenvalues and eigenvectors of A squared?
09:20
That's a straightforward question with a,
09:23
with an absolutely clean answer.
09:25
So let me, let me consider A squared.
09:28
So I start with A x equal lambda x.
09:33
And I'm headed for A squared.
09:36
So let me multiply both sides by A.
09:38
That's one way to get A squared on the left.
09:41
So -- I should write these if-s in here.
09:46
If A x equals lambda x, then I multiply by A,
09:51
so I get A squared x equals -- well, I'm multiplying by A,
09:56
so that's lambda A x.
09:58
That lambda was a number, so I just put it on the left.
10:02
And what do I -- tell me how to make that look better.
10:06
What have I got here for if, if A
10:10
has the eigenvalue lambda and eigenvector
10:13
x, what's up with A squared?
10:16
A squared x, I just multiplied by A,
10:18
but now for Ax I'm going to substitute lambda x.
10:23
So I've got lambda squared x.
10:28
So from that simple calculation, I --
10:31
my conclusion is that the eigenvalues of A squared are
10:37
lambda squared.
10:39
And the eigenvectors --
10:40
I always think about both of
10:41
those.
10:42
What can I say about the eigenvalues?
10:44
They're squared.
10:45
What can I say about the eigenvectors?
10:48
They're the same.
10:49
The same x as in -- as for A.
10:54
Now let me see that also from this formula.
11:00
How can I see what A squared is looking like from this formula?
11:05
So let me -- that was one way to do it.
11:08
Let me do it by just taking A squared from that.
11:12
A squared is S lambda S inverse -- that's A --
11:18
times S lambda S inverse -- that's A, which is?
11:25
This is the beauty of eigenvalues, eigenvectors.
11:30
Having that S inverse and S is the identity,
11:34
so I've got S lambda squared S inverse.
11:40
Do you see what that's telling me?
11:43
It's, it's telling me the same thing that I just learned here,
11:46
but in the -- in a matrix form.
11:49
It's telling me that the S is the same,
11:52
the eigenvectors are the same, but the eigenvalues
11:57
are squared.
11:58
Because this is -- what's lambda squared?
12:01
That's still diagonal.
12:02
It's got little lambda one squared,
12:05
lambda two squared, down to lambda n
12:07
squared o- on that diagonal.
12:09
Those are the eigenvalues, as we just learned, of A squared.
12:13
OK.
12:14
So -- somehow those eigenvalues and eigenvectors are really
12:19
giving you a way to --
12:25
see what's going on inside a matrix.
12:29
Of course I can continue that for --
12:32
to the K-th power, A to the K-th power.
12:36
If I multiply, if I have K of these together,
12:39
do you see how S inverse S will keep canceling
12:42
in the, in the inside?
12:44
I'll have the S outside at the far left,
12:48
and lambda will be in there K times, and S inverse.
12:54
So what's that telling me?
12:56
That's telling me that the eigenvalues
12:59
of A, of A to the K-th power are the K-th powers.
13:04
The eigenvalues of A cubed are the cubes of the eigenvalues of
13:08
A. And the eigenvectors are the same, the same.
13:15
OK.
13:15
In other words, eigenvalues and eigenvectors
13:20
give a great way to understand the powers of a matrix.
13:25
If I take the square of a matrix,
13:28
or the hundredth power of a matrix,
13:30
the pivots are all over the place.
13:34
L U, if I multiply L U times L U times L U times L U
13:39
a hundred times, I've got a hundred L Us.
13:44
I can't do anything with them.
13:46
But when I multiply S lambda S inverse by itself,
13:50
when I look at the eigenvector picture a hundred times,
13:54
I get a hundred or ninety-nine of these guys canceling out
13:59
inside, and I get A to the hundredth
14:03
is S lambda to the hundredth S inverse.
14:05
I mean, eigenvalues tell you about powers
14:09
of a matrix in a way that we had no way to approach previously.
14:16
For example, when does --
14:21
when do the powers of a matrix go to zero?
14:24
I would call that matrix stable, maybe.
14:29
So I could write down a theorem.
14:31
I'll write it as a theorem just to use that word
14:36
to emphasize that here I'm getting this great fact
14:40
from this eigenvalue picture.
14:42
OK.
14:43
A to the K approaches zero as K goes, as K gets bigger if what?
14:53
What's the w- how can I tell, for a matrix A,
14:57
if its powers go to zero?
15:02
What's -- somewhere inside that matrix is that information.
15:07
That information is not present in the pivots.
15:11
It's present in the eigenvalues.
15:13
What do I need for the -- to know that if I take higher
15:17
and higher powers of A, that this matrix gets smaller
15:20
and smaller?
15:21
Well, S and S inverse are not moving.
15:24
So it's this guy that has to get small.
15:26
And that's easy to -- to understand.
15:29
The requirement is all eigenvalues --
15:35
so what is the requirement?
15:38
The eigenvalues have to be less than one.
15:41
Now I have to wrote that absolute value,
15:45
because those eigenvalues could be negative,
15:48
they could be complex numbers.
15:50
So I'm taking the absolute value.
15:53
If all of those are below one.
15:56
That's, in fact, we practically see why.
16:05
And let me just say that I'm operating on one assumption
16:13
here, and I got to keep remembering
16:15
that that assumption is still present.
16:18
That assumption was that I had a full set of,
16:21
of n independent eigenvectors.
16:24
If I don't have that, then this approach is not working.
16:30
So again, a pure eigenvalue approach, eigenvector approach,
16:37
needs n independent eigenvectors.
16:40
If we don't have n independent eigenvectors,
16:42
we can't diagonalize the matrix.
16:46
We can't get to a diagonal matrix.
16:50
This diagonalization is only possible
16:55
if S inverse makes sense.
16:58
OK.
16:59
Can I, can I follow up on that point now?
17:02
So you see why -- what we get and, and why we want it,
17:07
because we get information about the powers of a matrix just
17:11
immediately from the eigenvalues.
17:14
OK.
17:15
Now let me follow up on this, business of which matrices
17:22
are diagonalizable.
17:25
Sorry about that long word.
17:28
So a matrix is, is sure -- so here's, here's the main point.
17:32
A is sure to be --
17:37
to have N independent eigenvectors and, and be --
17:50
now here comes that word -- diagonalizable if, if --
18:00
so we might as well get the nice case out in the open.
18:05
The nice case is when -- if all the lambdas are different.
18:19
That means, that means no repeated eigenvalues.
18:30
OK.
18:32
That's the nice case.
18:34
If my matrix, and most -- if I do a random matrix in Matlab
18:39
and compute its eigenvalues --
18:43
so if I computed if I took eig of rand of ten ten, gave,
18:55
gave that Matlab command, the --
18:58
we'd get a random ten by ten matrix,
19:01
we would get a list of its ten eigenvalues,
19:03
and they would be different.
19:08
They would be distinct is the best word.
19:10
I would have -- a random matrix will have ten distinct --
19:13
a ten by ten matrix will have ten distinct eigenvalues.
19:18
And if it does, the eigenvectors are automatically independent.
19:25
So that's a nice fact.
19:26
I'll refer you to the text for the proof.
19:29
That, that A is sure to have n independent eigenvectors
19:36
if the eigenvalues are different, if.
19:41
If all the, if all eigenvalues are different.
19:43
It's just if some lambdas are repeated,
19:47
then I have to look more closely.
19:50
If an eigenvalue is repeated, I have to look, I have to count,
19:55
I have to check.
19:56
Has it got -- say it's repeated three times.
19:59
So what's a possibility for the --
20:02
so here is the, here is the repeated possibility.
20:11
And, and let me emphasize the conclusion.
20:16
That if I have repeated eigenvalues, I may or may not,
20:21
I may or may not have, have n independent eigenvectors.
20:35
I might.
20:35
I, I, you know, this isn't a completely negative case.
20:41
The identity matrix --
20:43
suppose I take the ten by ten identity matrix.
20:46
What are the eigenvalues of that matrix?
20:50
So just, just take the easiest matrix, the identity.
20:55
If I look for its eigenvalues, they're all ones.
21:00
So that eigenvalue one is repeated ten times.
21:04
But there's no shortage of eigenvectors for the identity
21:07
matrix.
21:08
In fact, every vector is an eigenvector.
21:10
So I can take ten independent vectors.
21:13
Oh, well, what happens to everything --
21:16
if A is the identity matrix, let's
21:18
just think that one through in our head.
21:21
If A is the identity matrix, then it's
21:27
got plenty of eigenvectors.
21:28
I choose ten independent vectors.
21:30
They're the columns of S.
21:32
And, and what do I get from S inverse A S?
21:37
I get I again, right?
21:39
If A is the identity -- and of course that's the correct
21:42
lambda.
21:43
The matrix was already diagonal.
21:46
So if the matrix is already diagonal,
21:48
then the, the lambda is the same as the matrix.
21:53
A diagonal matrix has got its eigenvalues
21:56
sitting right there in front of you.
21:59
Now if it's triangular, the eigenvalues
22:01
are still sitting there, but so let's
22:04
take a case where it's triangular.
22:08
Suppose A is like, two one two zero.
22:17
So there's a case that's going to be trouble.
22:23
There's a case that's going to be trouble.
22:25
First of all, what are the --
22:26
I mean, we just --
22:29
if we start with a matrix, the first thing
22:31
we do, practically without thinking
22:32
is compute the eigenvalues and eigenvectors.
22:36
OK.
22:36
So what are the eigenvalues?
22:38
You can tell me right away what they are.
22:41
They're two and two, right.
22:43
It's a triangular matrix, so when I do this determinant,
22:47
shall I do this determinant of A minus lambda I?
22:51
I'll get this two minus lambda one zero two minus lambda,
22:59
right?
23:01
I take that determinant, so I make those into vertical bars
23:06
to mean determinant.
23:09
And what's the determinant?
23:10
It's two minus lambda squared.
23:13
What are the roots?
23:14
Lambda equal two twice.
23:17
So the eigenvalues are lambda equals two and two.
23:22
OK, fine.
23:23
Now the next step, find the eigenvectors.
23:26
So I look for eigenvectors, and what do I find for this guy?
23:31
Eigenvectors for this guy, when I
23:33
subtract two minus the identity, so A minus two
23:38
I has zeros here.
23:45
And I'm looking for the null space.
23:48
What's, what are the eigenvectors?
23:50
They're the -- the null space of A minus lambda I.
23:56
The null space is only one dimensional.
23:59
This is a case where I don't have enough eigenvectors.
24:03
My algebraic multiplicity is two.
24:07
I would say, when I see, when I count
24:10
how often the eigenvalue is repeated,
24:16
that's the algebraic multiplicity.
24:18
That's the multiplicity, how many times
24:20
is it the root of the polynomial?
24:22
My polynomial is two minus lambda squared.
24:28
It's a double root.
24:30
So my algebraic multiplicity is two.
24:33
But the geometric multiplicity, which looks for vectors,
24:37
looks for eigenvectors, and -- which means the null space
24:42
of this thing, and the only eigenvector is one
24:46
zero.
24:47
That's in the null space.
24:50
Zero one is not in the null space.
24:52
The null space is only one dimensional.
24:54
So there's a matrix, my -- this A or the original A,
24:58
that are not diagonalizable.
25:02
I can't find two independent eigenvectors.
25:06
There's only one.
25:08
OK.
25:08
So that's the case that I'm --
25:11
that's a case that I'm not really handling.
25:15
For example, when I wrote down up here
25:19
that the powers went to zero if the eigenvalues were below one,
25:24
I didn't really handle that case of repeated eigenvalues,
25:29
because my reasoning was based on this formula.
25:33
And this formula is based on n independent eigenvectors.
25:36
OK.
25:36
Just to say then, there are some matrices that we're, that,
25:45
that we don't cover through diagonalization,
25:48
but the great majority we do.
25:51
OK.
25:51
And we, we're always OK if we have
25:54
different distinct eigenvalues.
25:56
OK, that's the, like, the typical case.
26:02
Because for each eigenvalue there's
26:04
at least one eigenvector.
26:07
The algebraic multiplicity here is one for every eigenvalue
26:11
and the geometric multiplicity is one.
26:14
There's one eigenvector.
26:15
And they are independent.
26:17
OK.
26:18
OK.
26:21
Now let me come back to the important case, when,
26:26
when we're OK.
26:27
The important case, when we are diagonalizable.
26:31
Let me, look at --
26:38
so -- let me solve this equation.
26:46
The equation will be each --
26:49
I start with some -- start with a given vector u0.
27:02
And then my equation is at every step,
27:06
I multiply what I have by A.
27:11
That, that equation ought to be simple to handle.
27:19
And I'd like to be able to solve it.
27:21
How would I find -- if I start with a vector u0 and I multiply
27:26
by A a hundred times, what have I got?
27:31
Well, I could certainly write down a formula for the answer,
27:35
so what, what -- so u1 is A u0.
27:42
And u2 is -- what's u2 then?
27:45
u2, I multiply -- u2 I get from u1 by another multiplying by A,
27:52
so I've got A twice.
27:55
And my formula is uk, after k steps,
28:02
I've multiplied by A k times the original u0.
28:07
You see what I'm doing?
28:11
The next section is going to solve systems
28:14
of differential equations.
28:17
I'm going to have derivatives.
28:19
This section is the nice one.
28:23
It solves difference equations.
28:26
I would call that a difference equation.
28:28
It's -- at first order, I would call that a first-order system,
28:33
because it connects only -- it only goes up one level.
28:40
And I -- it's a system because these are vectors
28:43
and that's a matrix.
28:45
And the solution is just that.
28:48
OK.
28:49
But, that's a nice formula.
28:55
That's the, like, the most compact formula
28:57
I could ever get. u100 would be A to the one hundred u0.
29:01
But how would I actually find u100?
29:06
How would I find -- how would I discover what u100 is?
29:11
Let me, let me show you how.
29:16
Here's the idea.
29:18
If -- so to solve, to really solve -- shall I say,
29:23
to really solve --
29:26
to really solve it, I would take this initial vector u0
29:34
and I would write it as a combination of eigenvectors.
29:39
To really solve, write u nought as a combination,
29:47
say certain amount of the first eigenvector
29:50
plus a certain amount of the second eigenvector
29:53
plus a certain amount of the last eigenvector.
30:01
Now multiply by A.
30:04
You want to -- you got to see the magic of eigenvectors
30:07
working here.
30:08
Multiply by A.
30:10
So Au0 is what?
30:13
So A times that.
30:16
A times -- so what's A --
30:18
I can separate it out into n separate pieces,
30:21
and that's the whole point.
30:23
That each of those pieces is going in its own merry way.
30:28
Each of those pieces is an eigenvector,
30:31
and when I multiply by A, what does this piece become?
30:35
So that's some amount of the first --
30:38
let's suppose the eigenvectors are normalized to be unit
30:41
vectors.
30:44
So that says what the eigenvector is.
30:48
It's a --
30:51
And I need some multiple of it to produce u0.
30:55
OK.
30:56
Now when I multiply by A, what do I get?
30:59
I get c1, which is just a factor, times Ax1,
31:04
but Ax1 is lambda one x1.
31:10
When I multiply this by A, I get c2 lambda two x2.
31:17
And here I get cn lambda n xn.
31:20
And suppose I multiply by A to the hundredth power now.
31:27
Can we, having done it, multiplied by A, let's
31:30
multiply by A to the hundredth.
31:32
What happens to this first term when I multiply by A to the one
31:36
hundredth?
31:38
It's got that factor lambda to the hundredth.
31:41
That's the key.
31:42
That -- that's what I mean by going its own merry way.
31:48
It, it is pure eigenvector.
31:52
It's exactly in a direction where multiplication by A
31:55
just brings in a scalar factor, lambda one.
31:59
So a hundred times brings in this a hundred times.
32:02
Hundred times lambda two, hundred times lambda n.
32:06
Actually, we're -- what are we seeing here?
32:08
We're seeing, this same, lambda capital
32:15
lambda to the hundredth as in the, as in the diagonalization.
32:19
And we're seeing the S matrix, the,
32:22
the matrix S of eigenvectors.
32:24
That's what this has got to -- this has got to amount to.
32:29
A lambda to the hundredth power times an S times this vector c
32:40
that's telling us how much of each one
32:43
is in the original thing.
32:45
So if, if I had to really find the hundredth power,
32:49
I would take u0, I would expand it as a combination
32:54
of eigenvectors -- this is really S,
32:57
the eigenvector matrix, times c, the, the coefficient vector.
33:04
And then I would immediately then,
33:07
by inserting these hundredth powers of eigenvalues,
33:10
I'd have the answer.
33:15
So -- huh, there must be --
33:17
oh, let's see, OK.
33:20
It's -- so, yeah.
33:22
So if u100 is A to the hundredth times u0, and u0 is S c --
33:30
then you see this formula is just this formula,
33:36
which is the way I would actually get hold of this,
33:40
of this u100, which is --
33:44
let me put it here.
33:47
u100.
33:48
The way I would actually get hold of that, see what,
33:51
what the solution is after a hundred steps, would be --
33:57
expand the initial vector into eigenvectors and let each
34:05
eigenvector go its own way, multiplying by a hundred at --
34:10
by lambda at every step, and therefore by lambda
34:13
to the hundredth power after a hundred steps.
34:16
Can I do an example?
34:18
So that's the formulas.
34:20
Now let me take an example.
34:22
I'll use the Fibonacci sequence as an example.
34:29
So, so Fibonacci example.
34:39
You remember the Fibonacci numbers?
34:43
If we start with one and one as F0 -- oh,
34:48
I think I start with zero, maybe.
34:50
Let zero and one be the first ones.
34:54
So there's F0 and F1, the first two Fibonacci numbers.
34:58
Then what's the rule for Fibonacci numbers?
35:02
Ah, they're the sum.
35:04
The next one is the sum of those, so it's one.
35:08
The next one is the sum of those, so it's two.
35:11
The next one is the sum of those, so it's three.
35:14
Well, it looks like one two three four five,
35:16
but somehow it's not going to do that way.
35:19
The next one is five, right.
35:21
Two and three makes five.
35:22
The next one is eight.
35:26
The next one is thirteen.
35:28
And the one hundredth Fibonacci number is what?
35:35
That's my question.
35:37
How could I get a formula for the hundredth number?
35:40
And, for example, how could I answer the question,
35:44
how fast are they growing?
35:47
How fast are those Fibonacci numbers growing?
35:52
They're certainly growing.
35:54
It's not a stable case.
35:56
Whatever the eigenvalues of whatever matrix it is,
35:59
they're not smaller than one.
36:00
These numbers are growing.
36:02
But how fast are they growing?
36:04
The answer lies in the eigenvalue.
36:10
So I've got to find the matrix, so let me write down
36:12
the Fibonacci rule.
36:17
F(k+2) = F(k+1)+F k, right?
36:25
Now that's not in my --
36:28
I want to write that as uk plus one and Auk.
36:32
But right now what I've got is a single equation, not a system,
36:38
and it's second-order.
36:41
It's like having a second-order differential equation
36:44
with second derivatives.
36:45
I want to get first derivatives.
36:47
Here I want to get first differences.
36:49
So the way, the way to do it is to introduce uk will be
36:55
a vector --
36:57
see, a small trick.
37:01
Let uk be a vector, F(k+1) and Fk.
37:08
So I'm going to get a two by two system, first order,
37:12
instead of a one -- instead of a scalar system, second order,
37:16
by a simple trick.
37:18
I'm just going to add in an equation F(k+1) equals F(k+1).
37:22
That will be my second equation.
37:28
Then this is my system, this is my unknown,
37:33
and what's my one step equation?
37:38
So, so now u(k+1), that's -- so u(k+1) is the left side,
37:45
and what have I got here on the right side?
37:47
I've got some matrix multiplying uk.
37:52
Can you, do -- can you see that all right?
37:56
if you can see it, then you can tell me what the matrix is.
37:59
Do you see that I'm taking my system here.
38:02
I artificially made it into a system.
38:06
I artificially made the unknown into a vector.
38:10
And now I'm ready to look at and see what the matrix
38:14
is.
38:15
So do you see the left side, u(k+1) is F(k+2) F(k+1),
38:20
that's just what I want.
38:21
On the right side, this remember, this uk here --
38:25
let me for the moment put it as F(k+1) Fk.
38:29
So what's the matrix?
38:33
Well, that has a one and a one, and that has a one and a zero.
38:41
There's the matrix.
38:43
Do you see that that gives me the right-hand side?
38:47
So there's the matrix A.
38:52
And this is our friend uk.
38:56
So we've got -- so that simple trick --
39:00
changed the second-order scalar problem
39:03
to a first-order system.
39:05
Two b- u- with two unknowns.
39:08
With a matrix.
39:10
And now what do I do?
39:13
Well, before I even think, I find its eigenvalues
39:16
and eigenvectors.
39:18
So what are the eigenvalues and eigenvectors of that matrix?
39:23
Let's see.
39:24
I always -- first let me just, like, think for a minute.
39:29
It's two by two, so this shouldn't be impossible to do.
39:35
Let's do it.
39:37
OK.
39:37
So my matrix, again, is one one one zero.
39:46
It's symmetric, by the way.
39:49
So what I will eventually know about symmetric matrices
39:56
is that the eigenvalues will come out real.
39:59
I won't get any complex numbers here.
40:02
And the eigenvectors, once I get those,
40:06
actually will be orthogonal.
40:08
But two by two, I'm more interested in what
40:11
the actual numbers are.
40:13
What do I know about the two numbers?
40:16
Well, should do you want me to find
40:18
this determinant of A minus
40:19
lambda I?
40:20
Sure.
40:23
So it's the determinant of one minus lambda one one zero,
40:27
right?
40:31
Minus lambda, yes.
40:33
God.
40:33
OK.
40:38
OK.
40:40
There'll be two eigenvalues.
40:42
What will -- tell me again what I know about the two
40:45
eigenvalues before I go any further.
40:47
Tell me something about these two eigenvalues.
40:49
What do they add up to?
40:51
Lambda one plus lambda two is?
40:55
Is the same as the trace down the diagonal of the matrix.
41:02
One and zero is one.
41:04
So lambda one plus lambda two should come out to be one.
41:08
And lambda one times lambda one times lambda two
41:10
should come out to be the determinant, which
41:13
is minus one.
41:15
So I'm expecting the eigenvalues to add to one
41:18
and to multiply to minus one.
41:20
But let's just see it happen here.
41:22
If I multiply this out, I get -- that times that'll be a lambda
41:26
squared minus lambda minus one.
41:30
Good.
41:33
Lambda squared minus lambda minus one.
41:36
Actually, I -- you see the b- compare that with the original
41:43
equation that I started with.
41:48
F(k+2) - F(k+1)-Fk is zero.
41:49
The recursion that -- that the Fibonacci numbers satisfy is
42:00
somehow showing up directly here for the eigenvalues when we set
42:05
that to zero.
42:06
WK.
42:06
Let's solve.
42:09
Well, I would like to be able to factor that, that quadratic,
42:14
but I'm better off to use the quadratic formula.
42:17
Lambda is -- let's see.
42:19
Minus b is one plus or minus the square root of b squared,
42:25
which is one, minus four times that times that,
42:30
which is plus four, over two.
42:37
So that's the square root of five.
42:42
So the eigenvalues are lambda one is one half of one
42:50
plus square root of five, and lambda two is one half of one
42:57
minus square root of five.
42:59
And sure enough, they -- those add up to one and they multiply
43:04
to give minus one.
43:06
OK.
43:07
Those are the two eigenvalues.
43:09
How -- what are those numbers approximately?
43:12
Square root of five, well, it's more than two
43:18
but less than three.
43:19
Hmm.
43:19
It'd be nice to know these numbers.
43:25
I think, I think that -- so that number comes out bigger than
43:30
one, right?
43:30
That's right.
43:31
This number comes out bigger than one.
43:35
It's about one point six one eight or something.
43:42
Not exactly, but.
43:44
And suppose it's one point six.
43:48
Just, like, I think so.
43:52
Then what's lambda two?
43:54
Is, is lambda two positive or negative?
43:57
Negative, right, because I'm -- it's, obviously negative,
44:01
and I knew that the -- so it's minus --
44:07
and they add up to one, so minus point six one eight, I guess.
44:16
OK.
44:17
A- and some more.
44:17
Those are the two eigenvalues.
44:18
One eigenvalue bigger than one, one eigenvalue smaller than
44:19
one.
44:20
Actually, that's a great situation to be in.
44:22
Of course, the eigenvalues are different,
44:25
so there's no doubt whatever -- is this matrix diagonalizable?
44:32
Is this matrix diagonalizable, that original matrix A?
44:35
Sure.
44:35
We've got two distinct eigenvalues
44:38
and we can find the eigenvectors in a moment.
44:44
But they'll be independent, we'll be diagonalizable.
44:46
And now, you, you can already answer my very first question.
44:54
How fast are those Fibonacci numbers increasing?
44:59
How -- those -- they're increasing,
45:01
right?
45:01
They're not doubling at every step.
45:03
Let me -- let's look again at these numbers.
45:07
Five, eight, thirteen, it's not obvious.
45:09
The next one would be twenty-one, thirty-four.
45:14
So to get some idea of what F one hundred is,
45:20
can you give me any --
45:21
I mean the crucial number --
45:24
so it -- these -- it's approximately --
45:32
what's controlling the growth of these Fibonacci numbers?
45:37
It's the eigenvalues.
45:39
And which eigenvalue is controlling that growth?
45:43
The big one.
45:43
So F100 will be approximately some constant, c1 I guess,
45:50
times this lambda one, this one plus square root of five
45:56
over two, to the hundredth power.
46:01
And the two hundredth F -- in other words, the eigenvalue --
46:04
the Fibonacci numbers are growing by about that factor.
46:08
Do you see that we, we've got precise information about the,
46:13
about the Fibonacci numbers out of the eigenvalues?
46:18
OK.
46:18
And again, why is that true?
46:21
Let me go over to this board and s- show what I'm doing here.
46:26
The -- the original initial value is some combination
46:30
of eigenvectors.
46:35
And then when we start -- when we start going out the theories
46:39
of Fibonacci numbers, when we start multiplying by A
46:42
a hundred times, it's this lambda one to the hundredth.
46:45
This term is, is the one that's taking over.
46:51
It's -- I mean, that's big, like one point six to the hundredth
46:54
power.
46:55
The second term is practically nothing, right?
47:00
The point six, or minus point six, to the hundredth power
47:04
is an extremely small, extremely small number.
47:08
So this is -- there're only two terms,
47:11
because we're two by two.
47:13
This number is -- this piece of it is there,
47:16
but it's, it's disappearing, where this piece is there
47:21
and it's growing and controlling everything.
47:23
So, so really the -- we're doing, like,
47:27
problems that are evolving.
47:29
We're doing dynamic u- instead of Ax=b,
47:33
that's a static problem.
47:35
We're now we're doing dynamics.
47:36
A, A squared, A cubed, things are evolving in
47:39
time.
47:40
And the eigenvalues are the crucial, numbers.
47:44
OK.
47:45
I guess to complete this, I better
47:52
write down the eigenvectors.
47:56
So we should complete the, the whole process
47:59
by finding the eigenvectors.
48:01
OK, well, I have to -- up in the corner, then,
48:03
I have to look at A minus lambda I.
48:07
So A minus lambda I is this one minus lambda one one and minus
48:15
lambda.
48:16
And now can we spot an eigenvector out of that?
48:19
That's, that's, for these two lambdas,
48:23
this matrix is singular.
48:27
I guess the eigenvector -- two by two ought to be, I mean,
48:30
easy.
48:31
So if I know that this matrix is singular,
48:33
then u- seems to me the eigenvector
48:37
has to be lambda and one, because that multiplication
48:41
will give me the zero.
48:43
And this multiplication gives me -- better give me also zero.
48:47
Do you see why it does?
48:48
This is the minus lambda squared plus lambda plus one.
48:52
It's the thing that's zero because these lambdas are
48:56
special.
48:56
There's the eigenvector.
48:58
x1 is lambda one one, and x2 is lambda two one.
49:07
I did that as a little trick that was available in the two
49:12
by two case.
49:14
So now I finally have to --
49:17
oh, I have to take the initial u0 now.
49:20
So to complete this example entirely,
49:22
I have to say, OK, what was u0?
49:26
u0 was F1 F0.
49:28
So u0, the starting vector is F1 F0, and those were one and
49:40
zero.
49:43
So I have to use that vector.
49:47
So I have to look for, for a multiple
49:50
of the first eigenvector and the second to produce u0,
49:56
the one zero
49:58
vector.
49:58
This is what will find c1 and c2, and then I'm done.
50:05
Do you -- so let me instead of, in the last five seconds,
50:10
grinding out a formula, let me repeat the idea.
50:14
Because I'd really -- it's the idea that's central.
50:19
When things are evolving in time --
50:21
let me come back to this board, because the ideas are here.
50:25
When things are evolving in time by a first-order system,
50:30
starting from an original u0, the key
50:34
is find the eigenvalues and eigenvectors of A.
50:39
That will tell -- those eigenvectors --
50:41
the eigenvalues will already tell you what's happening.
50:46
Is the solution blowing up, is it
50:48
going to zero, what's it doing.
50:51
And then to, to find out exactly a formula,
50:56
you have to take your u0 and write it
50:59
as a combination of eigenvectors and then
51:03
follow each eigenvector separately.
51:05
And that's really what this formula, the formula for, --
51:10
that's what the formula for A to the K is doing.
51:15
So remember that formula for A to the K
51:17
is S lambda to the K S inverse.
51:21
OK.
51:22
That's, that's difference equations.
51:24
And you just have to -- so the, the homework will give some
51:33
examples, different from Fibonacci, to follow through.
51:41
And next time will be differential equations.
51:48
Thanks.</div>

</div>

22. Diagonalization and Powers of A

Attachments