1
00:00:01,540 --> 00:00:03,910
The following content is
provided under a Creative
2
00:00:03,910 --> 00:00:05,300
Commons license.
3
00:00:05,300 --> 00:00:07,510
Your support will help
MIT OpenCourseWare
4
00:00:07,510 --> 00:00:11,600
continue to offer high-quality
educational resources for free.
5
00:00:11,600 --> 00:00:14,140
To make a donation or to
view additional materials
6
00:00:14,140 --> 00:00:18,100
from hundreds of MIT courses,
visit MIT OpenCourseWare
7
00:00:18,100 --> 00:00:18,990
at ocw.mit.edu.
8
00:00:22,674 --> 00:00:24,590
JAMES W. SWAN: Let's go
ahead and get started.
9
00:00:27,470 --> 00:00:31,550
I hope everybody
saw the correction
10
00:00:31,550 --> 00:00:35,667
to a typo in homework 1 that
was posted on Stellar last night
11
00:00:35,667 --> 00:00:36,500
and sent out to you.
12
00:00:36,500 --> 00:00:39,140
That's going to happen
from time to time.
13
00:00:39,140 --> 00:00:42,020
We have four course staff
that review all the problems.
14
00:00:42,020 --> 00:00:45,389
We try to look through it for
any issues or ambiguities.
15
00:00:45,389 --> 00:00:47,180
But from time to time,
we'll miss something
16
00:00:47,180 --> 00:00:48,800
and try to make a correction.
17
00:00:48,800 --> 00:00:50,660
The TAs gave a hint
that would have let you
18
00:00:50,660 --> 00:00:52,800
solve the problem as written.
19
00:00:52,800 --> 00:00:56,440
But that's more
difficult than what
20
00:00:56,440 --> 00:00:57,700
we had intended for you guys.
21
00:00:57,700 --> 00:01:00,740
We don't want to give you a
homework assignment that's
22
00:01:00,740 --> 00:01:01,932
punishing.
23
00:01:01,932 --> 00:01:03,640
We want to give you
an assignment that'll
24
00:01:03,640 --> 00:01:04,420
help you learn.
25
00:01:04,420 --> 00:01:07,490
Some people in this class that
are very good at programming
26
00:01:07,490 --> 00:01:09,420
have apparently
already completed
27
00:01:09,420 --> 00:01:10,630
that problem with the hint.
28
00:01:10,630 --> 00:01:13,300
But it's easier, as
originally intended.
29
00:01:13,300 --> 00:01:15,310
And the correction resets that.
30
00:01:15,310 --> 00:01:17,452
So maybe you'll
see the distinction
31
00:01:17,452 --> 00:01:18,910
between those things
and understand
32
00:01:18,910 --> 00:01:22,100
why one version of the problem
is much easier than another.
33
00:01:22,100 --> 00:01:24,940
But we try to respond
as quickly as possible
34
00:01:24,940 --> 00:01:27,212
when we notice a typo like
that so that we can set
35
00:01:27,212 --> 00:01:28,420
you guys on the right course.
36
00:01:32,110 --> 00:01:35,320
So we've got two lectures
left discussing linear algebra
37
00:01:35,320 --> 00:01:37,630
before we move on
to other topics.
38
00:01:37,630 --> 00:01:41,050
We're still going to talk about
transformations of matrices.
39
00:01:41,050 --> 00:01:43,270
We looked at one type
of transformation
40
00:01:43,270 --> 00:01:45,855
we could utilize for solving
systems of equations.
41
00:01:45,855 --> 00:01:47,230
Today, we'll look
at another one,
42
00:01:47,230 --> 00:01:49,170
the eigenvalue decomposition.
43
00:01:49,170 --> 00:01:51,670
And on Monday, we'll look at
another one called the singular
44
00:01:51,670 --> 00:01:53,470
value decomposition.
45
00:01:53,470 --> 00:01:55,680
Before jumping right in,
I want to take a minute
46
00:01:55,680 --> 00:01:59,020
and see if there are any
questions that I can answer,
47
00:01:59,020 --> 00:02:02,110
anything that's been
unclear so far that I
48
00:02:02,110 --> 00:02:05,140
can try to reemphasize
or focus on for you.
49
00:02:08,672 --> 00:02:10,880
I was told the office hours
are really well-attended.
50
00:02:10,880 --> 00:02:13,640
So hopefully, you're
getting an opportunity
51
00:02:13,640 --> 00:02:16,677
to ask any pressing questions
during the office hours
52
00:02:16,677 --> 00:02:18,260
or you're meeting
with the instructors
53
00:02:18,260 --> 00:02:20,780
after class to ask
anything that was unclear.
54
00:02:20,780 --> 00:02:24,920
We want to make sure that
we're answering those questions
55
00:02:24,920 --> 00:02:26,030
in a timely fashion.
56
00:02:26,030 --> 00:02:27,760
This course moves at
a pretty quick pace.
57
00:02:27,760 --> 00:02:31,160
We don't want anyone
to get left behind.
58
00:02:31,160 --> 00:02:34,160
Speaking of getting left behind,
we ran out of time a little bit
59
00:02:34,160 --> 00:02:36,770
at the end of
lecture on Wednesday.
60
00:02:36,770 --> 00:02:37,370
That's OK.
61
00:02:37,370 --> 00:02:38,927
There were a lot
of good questions
62
00:02:38,927 --> 00:02:40,010
that came up during class.
63
00:02:40,010 --> 00:02:42,110
And one topic that we
didn't get to discuss
64
00:02:42,110 --> 00:02:46,220
is formal systems
for doing reordering
65
00:02:46,220 --> 00:02:47,660
in systems of equations.
66
00:02:47,660 --> 00:02:49,560
We saw that reordering
is important.
67
00:02:49,560 --> 00:02:53,600
In fact, it's essential for
solving certain problems
68
00:02:53,600 --> 00:02:55,140
via Gaussian elimination.
69
00:02:55,140 --> 00:02:56,880
You won't be able to solve them.
70
00:02:56,880 --> 00:03:00,327
Either you'll incur a
large numerical error
71
00:03:00,327 --> 00:03:01,910
because you didn't
do pivoting-- you'd
72
00:03:01,910 --> 00:03:04,520
like to do pivoting in order to
minimize the numerical error--
73
00:03:04,520 --> 00:03:08,390
or you need to reorder in
order to minimize fill-in.
74
00:03:08,390 --> 00:03:10,850
As an example, I've
solved a research problem
75
00:03:10,850 --> 00:03:13,220
where there was something
like 40 million equations
76
00:03:13,220 --> 00:03:16,610
and unknowns, a system of
partial differential equations.
77
00:03:16,610 --> 00:03:19,460
And if you reorder
those equations,
78
00:03:19,460 --> 00:03:22,470
then you can solve via Gaussian
elimination pretty readily.
79
00:03:22,470 --> 00:03:25,775
But if you don't,
well-- my PC had--
80
00:03:25,775 --> 00:03:28,205
I don't know-- like,
192 gigabytes of RAM.
81
00:03:31,370 --> 00:03:33,950
The elimination on that
matrix will fill the memory
82
00:03:33,950 --> 00:03:36,980
of that PC up in 20 minutes.
83
00:03:36,980 --> 00:03:38,800
And you'll be stuck.
84
00:03:38,800 --> 00:03:40,100
It won't proceed after that.
85
00:03:40,100 --> 00:03:42,620
So it's the difference
between getting a solution
86
00:03:42,620 --> 00:03:45,440
and writing a publication
about the research problem
87
00:03:45,440 --> 00:03:48,440
you're interested in and not.
88
00:03:48,440 --> 00:03:49,700
So how do you do reordering?
89
00:03:49,700 --> 00:03:52,534
Well, we use a process
called permutation.
90
00:03:52,534 --> 00:03:54,200
There's a certain
class of matrix called
91
00:03:54,200 --> 00:03:56,140
a permutation matrix that can--
92
00:03:56,140 --> 00:03:58,520
its action, multiplying
another matrix,
93
00:03:58,520 --> 00:04:01,380
can swap rows or columns.
94
00:04:01,380 --> 00:04:03,740
And here's an example
of a permutation matrix
95
00:04:03,740 --> 00:04:09,740
whose intention is to swap
row 1 and 2 of a matrix.
96
00:04:09,740 --> 00:04:14,280
So here, it looks like
identity, except rather
97
00:04:14,280 --> 00:04:17,420
than having 1, 1 on the first
two elements of the diagonal,
98
00:04:17,420 --> 00:04:20,209
I have 0, 1 and 1, 0.
99
00:04:20,209 --> 00:04:23,330
Here's an example where I take
that sort of a matrix, which
100
00:04:23,330 --> 00:04:26,417
should swap rows 1 and 2, and
I multiply it by a vector.
101
00:04:26,417 --> 00:04:28,250
If you do this matrix
vector multiplication,
102
00:04:28,250 --> 00:04:31,490
you'll see initially, the
vector was x1, x2, x3.
103
00:04:31,490 --> 00:04:34,100
But the product
will be x2, x1, x3.
104
00:04:34,100 --> 00:04:37,250
It swapped two rows
in that vector.
105
00:04:37,250 --> 00:04:39,090
Of course, a vector is
just a matrix, right?
106
00:04:39,090 --> 00:04:42,320
It's an N by 1 matrix.
107
00:04:42,320 --> 00:04:47,720
So P times A is the same
as a matrix whose columns
108
00:04:47,720 --> 00:04:49,880
are P times each of
the columns of A.
109
00:04:49,880 --> 00:04:52,160
That's what this
notation indicates here.
110
00:04:52,160 --> 00:04:55,560
And we know that
P times a vector,
111
00:04:55,560 --> 00:04:59,390
which is the column from A,
will swap two rows in A, right?
112
00:04:59,390 --> 00:05:01,740
So the product here
will be all the rows
113
00:05:01,740 --> 00:05:05,630
of A, the different rows
of AA superscript R,
114
00:05:05,630 --> 00:05:08,090
with row 1 and 2
swapped with each other.
115
00:05:08,090 --> 00:05:11,750
So permutation, multiplication
by the special type
116
00:05:11,750 --> 00:05:17,090
of matrix, a permutation
matrix, does reordering of rows.
117
00:05:17,090 --> 00:05:20,260
If I want to swap columns,
I multiply my matrix
118
00:05:20,260 --> 00:05:23,350
from the right, IP transpose.
119
00:05:23,350 --> 00:05:26,170
So if I want to
swap column 1 and 2,
120
00:05:26,170 --> 00:05:28,300
I multiply A from the
right by P transpose.
121
00:05:28,300 --> 00:05:30,570
How can I show that
that swaps columns?
122
00:05:30,570 --> 00:05:33,100
Well, A times P
transpose is the same
123
00:05:33,100 --> 00:05:36,760
as P times A
transpose transpose.
124
00:05:36,760 --> 00:05:38,620
P swaps rows.
125
00:05:38,620 --> 00:05:41,170
So it's swapping rows
of A transpose, which
126
00:05:41,170 --> 00:05:43,510
is like swapping columns of A.
127
00:05:43,510 --> 00:05:46,210
So we had some
identities associated
128
00:05:46,210 --> 00:05:48,040
with matrix-matrix
multiplication
129
00:05:48,040 --> 00:05:49,312
and their transposes.
130
00:05:49,312 --> 00:05:51,520
And you can use that to work
out how this permutation
131
00:05:51,520 --> 00:05:53,750
matrix will swap
columns instead of rows
132
00:05:53,750 --> 00:05:56,110
if I multiply from the
right instead of the left.
133
00:05:58,810 --> 00:06:00,340
Here's an important
concept to know.
134
00:06:00,340 --> 00:06:05,750
Permutation matrices are-- would
refer to as unitary matrices.
135
00:06:05,750 --> 00:06:07,270
They're transposed.
136
00:06:07,270 --> 00:06:09,490
It's also they're inverse.
137
00:06:09,490 --> 00:06:13,060
So P times P
transpose is identity.
138
00:06:13,060 --> 00:06:15,940
If I swap the rows and
then I swap them back,
139
00:06:15,940 --> 00:06:18,634
I get back what I had before.
140
00:06:18,634 --> 00:06:20,050
So there are lots
of matrices that
141
00:06:20,050 --> 00:06:22,240
have this property
that they're unitary.
142
00:06:22,240 --> 00:06:24,820
We'll see some today.
143
00:06:24,820 --> 00:06:27,430
But permutation matrices are
one class, maybe the simplest
144
00:06:27,430 --> 00:06:28,840
class, of unitary matrices.
145
00:06:28,840 --> 00:06:31,630
They're just doing row
or column swaps, right?
146
00:06:31,630 --> 00:06:33,810
That's their job.
147
00:06:33,810 --> 00:06:37,480
And so if I have some reordering
of the equations or rows
148
00:06:37,480 --> 00:06:40,120
of my system of
equations that I want,
149
00:06:40,120 --> 00:06:43,490
that's going to be indicated by
a permutation matrix-- say, P1.
150
00:06:43,490 --> 00:06:45,040
And I would multiply
my entire system
151
00:06:45,040 --> 00:06:48,100
of-- both sides of my
system of equations by P1.
152
00:06:48,100 --> 00:06:49,940
That would reorder the rows.
153
00:06:49,940 --> 00:06:52,030
If I have some
reordering of the columns
154
00:06:52,030 --> 00:06:56,140
or the unknowns in my problem, I
would use a similar permutation
155
00:06:56,140 --> 00:06:57,610
matrix, P2.
156
00:06:57,610 --> 00:07:00,200
Of course, P2 transpose
times P2 is identity.
157
00:07:00,200 --> 00:07:03,010
So this product
here does nothing
158
00:07:03,010 --> 00:07:04,210
to the system of equations.
159
00:07:04,210 --> 00:07:05,590
It just swaps the unknown.
160
00:07:05,590 --> 00:07:08,681
So there's a formal system for
doing this sort of swapping.
161
00:07:08,681 --> 00:07:10,930
There are a couple other
slides that are in your notes
162
00:07:10,930 --> 00:07:12,330
from last time that
you can look at
163
00:07:12,330 --> 00:07:13,871
and I'm happy to
answer questions on.
164
00:07:13,871 --> 00:07:16,230
We don't have time
to go into detail.
165
00:07:16,230 --> 00:07:19,870
It discusses the actual
methodology, the simplest
166
00:07:19,870 --> 00:07:22,360
possible methodology, for
doing this kind of reordering
167
00:07:22,360 --> 00:07:23,230
or swapping.
168
00:07:23,230 --> 00:07:25,190
So this is a form
of preconditioning.
169
00:07:27,820 --> 00:07:29,590
If it's preconditioning
for pivoting,
170
00:07:29,590 --> 00:07:32,090
it's designed to
minimize numerical error.
171
00:07:32,090 --> 00:07:37,300
If it's preconditioning in order
to minimize fill-in instead,
172
00:07:37,300 --> 00:07:40,510
that's meant to make the problem
solvable on your computer.
173
00:07:40,510 --> 00:07:42,404
But it's a form
of preconditioning
174
00:07:42,404 --> 00:07:43,320
a system of equations.
175
00:07:43,320 --> 00:07:46,770
And we discussed
preconditioning before.
176
00:07:46,770 --> 00:07:49,650
So now we know how to
solve systems of equations.
177
00:07:49,650 --> 00:07:51,750
It's always done via
Gaussian elimination
178
00:07:51,750 --> 00:07:53,280
if we want an exact solution.
179
00:07:53,280 --> 00:07:55,770
There are lots of variants
on Gaussian elimination
180
00:07:55,770 --> 00:07:56,730
that we can utilize.
181
00:07:56,730 --> 00:07:59,021
You're studying one of them
in your homework assignment
182
00:07:59,021 --> 00:08:01,800
now, where you know the matrix
is banded with some bandwidth.
183
00:08:01,800 --> 00:08:05,070
So you don't do elimination
on an entire full matrix.
184
00:08:05,070 --> 00:08:08,280
You do it on a sparse matrix
whose structure you understand.
185
00:08:08,280 --> 00:08:11,070
We discussed sparse
matrices and a little bit
186
00:08:11,070 --> 00:08:14,500
about reordering
and now permutation.
187
00:08:14,500 --> 00:08:18,140
I feel like my diffusion
example last time
188
00:08:18,140 --> 00:08:19,540
wasn't especially clear.
189
00:08:19,540 --> 00:08:24,580
So let me give you a different
example of diffusion.
190
00:08:24,580 --> 00:08:26,680
You guys know Plinko?
191
00:08:26,680 --> 00:08:28,780
Have you seen The
Price Is Right?
192
00:08:28,780 --> 00:08:30,400
This is a game where
you drop a chip
193
00:08:30,400 --> 00:08:33,030
into a board with pegs in it.
194
00:08:33,030 --> 00:08:36,000
It's a model of diffusion.
195
00:08:36,000 --> 00:08:38,200
The Plinko chip falls
from level to level.
196
00:08:38,200 --> 00:08:38,840
It hits a peg.
197
00:08:38,840 --> 00:08:42,549
And it can go left or it can go
right with equal probability.
198
00:08:46,310 --> 00:08:48,800
So the Plinko chip
diffuses as it falls down.
199
00:08:48,800 --> 00:08:49,880
This guy's excited.
200
00:08:49,880 --> 00:08:51,480
[LAUGHTER]
201
00:08:51,480 --> 00:08:53,950
He just won $10,000.
202
00:08:53,950 --> 00:08:57,345
[LAUGHTER]
203
00:08:59,780 --> 00:09:02,330
There's a sparse
matrix that describes
204
00:09:02,330 --> 00:09:05,810
how the probability
of finding the Plinko
205
00:09:05,810 --> 00:09:14,300
chip in a certain cell
evolves from level to level.
206
00:09:14,300 --> 00:09:16,370
It works the same way the
cellular automata model
207
00:09:16,370 --> 00:09:18,560
I showed you last time works.
208
00:09:18,560 --> 00:09:23,340
If the chip is in a particular
cell, then at the next level,
209
00:09:23,340 --> 00:09:25,780
there's a 50/50 chance
that I'll go to the left
210
00:09:25,780 --> 00:09:26,780
or I'll go to the right.
211
00:09:26,780 --> 00:09:28,430
It looks like this, right?
212
00:09:28,430 --> 00:09:32,120
If the chip is here, there's
a 50/50 chance I'll go here
213
00:09:32,120 --> 00:09:33,000
or I'll go there.
214
00:09:33,000 --> 00:09:35,810
So if the probability was
1 that I was in this cell,
215
00:09:35,810 --> 00:09:39,170
then at the next level,
it'll be half and a half.
216
00:09:39,170 --> 00:09:42,350
And at the next level, those
halves will split again.
217
00:09:42,350 --> 00:09:46,820
So the probability that I'm in
a particular cell at level i
218
00:09:46,820 --> 00:09:48,579
is this Pi.
219
00:09:48,579 --> 00:09:50,870
And the probability that I'm
in a particular cell level
220
00:09:50,870 --> 00:09:53,240
i plus 1 is this Pi plus one.
221
00:09:53,240 --> 00:09:56,700
And there's some
sparse matrix A which
222
00:09:56,700 --> 00:09:58,350
spreads that probability out.
223
00:09:58,350 --> 00:10:01,075
It splits it into
my neighbors 50/50.
224
00:10:03,690 --> 00:10:06,240
Here's a simulation of Plinko.
225
00:10:06,240 --> 00:10:09,060
So I started with
the probability 1
226
00:10:09,060 --> 00:10:10,540
in the center cell.
227
00:10:10,540 --> 00:10:15,410
And as I go through different
levels, I get split 50/50.
228
00:10:15,410 --> 00:10:20,220
And you see a binomial or almost
Gaussian distribution spread
229
00:10:20,220 --> 00:10:22,060
as I go through
more and more levels
230
00:10:22,060 --> 00:10:24,060
until it's equally probable
that I could wind up
231
00:10:24,060 --> 00:10:25,170
in any one of the cells.
232
00:10:28,010 --> 00:10:30,920
You can think about
it this way, right?
233
00:10:30,920 --> 00:10:37,180
The probability
at level i plus 1
234
00:10:37,180 --> 00:10:41,410
that the chip is in cell
N is inherited 50/50
235
00:10:41,410 --> 00:10:43,286
from its two neighbors, right?
236
00:10:43,286 --> 00:10:45,660
There's some probability that
was in these two neighbors.
237
00:10:45,660 --> 00:10:49,660
I would inherit half
of that probability.
238
00:10:49,660 --> 00:10:52,990
It would be split by these pegs.
239
00:10:52,990 --> 00:10:57,730
The sparse matrix that
represents this operation
240
00:10:57,730 --> 00:11:00,170
has two diagonals.
241
00:11:00,170 --> 00:11:02,950
And on each of those
diagonals is a half.
242
00:11:02,950 --> 00:11:07,000
And you can build that matrix
using the spdiags command.
243
00:11:07,000 --> 00:11:12,300
It says that there's going to
be two diagonal components which
244
00:11:12,300 --> 00:11:14,190
are equal to a half.
245
00:11:14,190 --> 00:11:16,000
And their position
is going to be
246
00:11:16,000 --> 00:11:20,040
one on either side of
the central diagonal.
247
00:11:20,040 --> 00:11:23,670
That's going to indicate that
I pass this probability, 50/50,
248
00:11:23,670 --> 00:11:25,680
to each of my neighbors.
249
00:11:25,680 --> 00:11:28,350
And then successive
multiplications by A
250
00:11:28,350 --> 00:11:29,990
will split this probability.
251
00:11:29,990 --> 00:11:31,740
And we'll see the
simulation that tells us
252
00:11:31,740 --> 00:11:33,540
how probable it is
to find the Plinko
253
00:11:33,540 --> 00:11:35,140
chip in a particular column.
254
00:11:35,140 --> 00:11:35,640
Yes?
255
00:11:35,640 --> 00:11:39,077
AUDIENCE: [INAUDIBLE]
256
00:11:41,050 --> 00:11:42,670
JAMES W. SWAN: Yeah.
257
00:11:42,670 --> 00:11:45,110
So in diffusion in general?
258
00:11:45,110 --> 00:11:48,283
AUDIENCE: Well, in this
instance in particular because
259
00:11:48,283 --> 00:11:50,490
[INAUDIBLE]
260
00:11:50,490 --> 00:11:51,690
JAMES W. SWAN: Well, OK.
261
00:11:51,690 --> 00:11:53,070
That's fair enough.
262
00:11:53,070 --> 00:11:57,030
This is one particular model
of the Plinko board, which
263
00:11:57,030 --> 00:12:02,324
sort of imagines alternating
cells that I'm falling through.
264
00:12:02,324 --> 00:12:03,990
We could construct
an alternative model,
265
00:12:03,990 --> 00:12:06,990
if we wanted to, that didn't
have that part of the picture,
266
00:12:06,990 --> 00:12:07,490
OK?
267
00:12:10,192 --> 00:12:12,150
So that's a matrix that
looks like this, right?
268
00:12:12,150 --> 00:12:15,440
The central diagonal is 0.
269
00:12:15,440 --> 00:12:17,330
Most of the
off-diagonal components
270
00:12:17,330 --> 00:12:20,020
here are 0 and 1
above and 1 below.
271
00:12:20,020 --> 00:12:22,095
I get a half and a half.
272
00:12:22,095 --> 00:12:23,720
And if I'm careful--
somebody mentioned
273
00:12:23,720 --> 00:12:25,460
I need boundary conditions.
274
00:12:25,460 --> 00:12:27,710
When the Plinko chip
gets to the edge,
275
00:12:27,710 --> 00:12:30,530
it doesn't fall out of the game.
276
00:12:30,530 --> 00:12:32,090
It gets reflected back in.
277
00:12:32,090 --> 00:12:34,850
So maybe we have to choose some
special values for a couple
278
00:12:34,850 --> 00:12:36,100
of elements of this matrix.
279
00:12:36,100 --> 00:12:38,030
But this is a sparse matrix.
280
00:12:38,030 --> 00:12:39,849
It has a sparse structure.
281
00:12:39,849 --> 00:12:42,140
It models a diffusion problem,
just like we saw before.
282
00:12:42,140 --> 00:12:44,030
Most of physics is
local, like this, right?
283
00:12:44,030 --> 00:12:46,280
I just need to know what's
going on with my neighbors.
284
00:12:46,280 --> 00:12:47,780
And I spread the
probability out.
285
00:12:47,780 --> 00:12:51,740
I get this nice
diffusion problem.
286
00:12:51,740 --> 00:12:53,780
So it looks like this.
287
00:12:53,780 --> 00:12:55,280
Here's something to notice.
288
00:12:55,280 --> 00:13:00,500
After many levels or cycles, I
multiply by A many, many times.
289
00:13:00,500 --> 00:13:04,044
This probability distribution
always seems to flatten out.
290
00:13:04,044 --> 00:13:04,835
It becomes uniform.
291
00:13:07,690 --> 00:13:11,350
It turns out there are even
special distributions for which
292
00:13:11,350 --> 00:13:14,740
A times A times
that distribution is
293
00:13:14,740 --> 00:13:16,100
equal to that distribution.
294
00:13:16,100 --> 00:13:17,980
You can see it at the end here.
295
00:13:17,980 --> 00:13:19,840
This is one of those
special distributions
296
00:13:19,840 --> 00:13:26,140
where the probability is equal
in every other cell, right?
297
00:13:26,140 --> 00:13:28,240
And at the next level,
it all gets passed down.
298
00:13:28,240 --> 00:13:31,925
That's one multiplication by--
it all gets spread by 50%.
299
00:13:31,925 --> 00:13:33,550
And the next
multiplication, everything
300
00:13:33,550 --> 00:13:35,422
gets spread by 50% again.
301
00:13:35,422 --> 00:13:36,880
And I recover the
same distribution
302
00:13:36,880 --> 00:13:40,430
that I had before, this
uniform distribution.
303
00:13:40,430 --> 00:13:44,290
That's a special distribution
for which A times A times P
304
00:13:44,290 --> 00:13:47,170
is equal to P. And
this distribution
305
00:13:47,170 --> 00:13:53,500
is one of the eigenvectors
of this matrix A times A.
306
00:13:53,500 --> 00:13:57,070
It's a particular vector
that when I multiply it
307
00:13:57,070 --> 00:14:03,070
by this matrix AA, I
get that vector back.
308
00:14:03,070 --> 00:14:04,420
It happens to be unstretched.
309
00:14:04,420 --> 00:14:06,730
So this vector points
in some direction.
310
00:14:06,730 --> 00:14:08,650
I transform it by the matrix.
311
00:14:08,650 --> 00:14:12,430
And I get back something that
points in the same direction.
312
00:14:12,430 --> 00:14:16,030
That's the definition of this
thing called an eigenvector.
313
00:14:16,030 --> 00:14:18,700
And this will be the subject
that we focus on today.
314
00:14:22,920 --> 00:14:25,110
So eigenvectors of a matrix--
315
00:14:25,110 --> 00:14:28,340
they're special vectors that
are stretched on multiplication
316
00:14:28,340 --> 00:14:29,630
by the matrix.
317
00:14:29,630 --> 00:14:31,250
So they're transformed.
318
00:14:31,250 --> 00:14:34,152
But they're only transformed
into a stretched form
319
00:14:34,152 --> 00:14:35,360
of whatever they were before.
320
00:14:35,360 --> 00:14:37,190
They point in a direction.
321
00:14:37,190 --> 00:14:38,780
You transform them
by the matrix.
322
00:14:38,780 --> 00:14:40,550
And you get something that
points in the same direction,
323
00:14:40,550 --> 00:14:41,258
but is stretched.
324
00:14:41,258 --> 00:14:43,280
Before, we saw the
amount of stretch.
325
00:14:43,280 --> 00:14:46,470
The previous example, we saw
the amount of stretch was 1.
326
00:14:46,470 --> 00:14:47,659
It wasn't stretched at all.
327
00:14:47,659 --> 00:14:49,700
You just get back the same
vector you had before.
328
00:14:49,700 --> 00:14:52,370
But in principle, it could
come back with any length.
329
00:14:56,260 --> 00:14:59,680
For a real N-by-N
matrix, there will
330
00:14:59,680 --> 00:15:03,640
be eigenvectors and
eigenvalues, which
331
00:15:03,640 --> 00:15:07,565
are the amount of stretch,
which are complex numbers.
332
00:15:11,360 --> 00:15:14,120
And finding
eigenvector-eigenvalue pairs
333
00:15:14,120 --> 00:15:17,900
involves solving N equations.
334
00:15:17,900 --> 00:15:19,760
We'd like to know what
these eigenvectors
335
00:15:19,760 --> 00:15:21,920
and eigenvalues are.
336
00:15:21,920 --> 00:15:23,840
They're non-linear
because they depend
337
00:15:23,840 --> 00:15:28,220
on both the value and the
vector, the product of the two,
338
00:15:28,220 --> 00:15:30,134
for N plus 1 unknowns.
339
00:15:30,134 --> 00:15:32,300
We don't know how to solve
non-linear equations yet.
340
00:15:32,300 --> 00:15:33,410
So we're kind of--
341
00:15:33,410 --> 00:15:35,610
might seem like we're
in a rough spot.
342
00:15:35,610 --> 00:15:38,720
But I'll show you
that we're not.
343
00:15:38,720 --> 00:15:41,130
But because there's N equations
for N plus 1 unknowns,
344
00:15:41,130 --> 00:15:45,100
that means eigenvectors
are not unique.
345
00:15:45,100 --> 00:15:47,730
If W is an eigenvector,
than any other vector
346
00:15:47,730 --> 00:15:49,590
that points in
that same direction
347
00:15:49,590 --> 00:15:51,300
is also an eigenvector, right?
348
00:15:51,300 --> 00:15:55,840
It also gets stretched
by this factor lambda.
349
00:15:55,840 --> 00:15:59,760
So we can never say what
an eigenvector is uniquely.
350
00:15:59,760 --> 00:16:02,420
We can only prescribe
its direction.
351
00:16:02,420 --> 00:16:04,240
Whatever its magnitude
is, we don't care.
352
00:16:04,240 --> 00:16:05,910
We just care about
its direction.
353
00:16:05,910 --> 00:16:09,160
The amount of stretch,
however, is unique.
354
00:16:09,160 --> 00:16:11,080
It's associated
with that direction.
355
00:16:11,080 --> 00:16:12,589
So you have an
amount of stretch.
356
00:16:12,589 --> 00:16:13,630
And you have a direction.
357
00:16:13,630 --> 00:16:17,460
And that describes the
eigenvector-eigenvalue pair.
358
00:16:20,230 --> 00:16:22,000
Is this clear?
359
00:16:22,000 --> 00:16:24,250
You've heard of eigenvalues
and eigenvectors before?
360
00:16:24,250 --> 00:16:24,750
Good.
361
00:16:27,290 --> 00:16:30,950
So how do you find eigenvalues?
362
00:16:30,950 --> 00:16:34,250
They seem like special
sorts of solutions
363
00:16:34,250 --> 00:16:35,882
associated with a matrix.
364
00:16:35,882 --> 00:16:38,340
And if we understood them, then
we can do a transformation.
365
00:16:38,340 --> 00:16:39,714
So I'll explain
that in a minute.
366
00:16:39,714 --> 00:16:41,600
But how do you actually
find these things,
367
00:16:41,600 --> 00:16:43,450
these eigenvalues?
368
00:16:43,450 --> 00:16:47,570
Well, I've got to solve an
equation A times w equals
369
00:16:47,570 --> 00:16:52,580
lambda times w, which can be
transformed into A minus lambda
370
00:16:52,580 --> 00:16:55,414
identity times w equals 0.
371
00:16:55,414 --> 00:16:57,080
And so the solution
set to this equation
372
00:16:57,080 --> 00:17:00,390
is either w is equal to 0.
373
00:17:00,390 --> 00:17:02,660
That's one possible
solution to this problem
374
00:17:02,660 --> 00:17:09,140
or the eigenvector w belongs to
the null space of this matrix.
375
00:17:09,140 --> 00:17:12,170
It's one of those special
vectors that when it multiplies
376
00:17:12,170 --> 00:17:14,869
this matrix gives back 0, right?
377
00:17:14,869 --> 00:17:19,250
It gets projected out on
transformation by this matrix.
378
00:17:19,250 --> 00:17:22,829
Well, this solution doesn't
seem very useful to us, right?
379
00:17:22,829 --> 00:17:24,349
It's trivial.
380
00:17:24,349 --> 00:17:26,510
So let's go with this
idea that w belongs
381
00:17:26,510 --> 00:17:31,640
to the null space
of A minus lambda I.
382
00:17:31,640 --> 00:17:34,820
That means A minus lambda I must
be a singular matrix, whatever
383
00:17:34,820 --> 00:17:36,650
it is, right?
384
00:17:36,650 --> 00:17:39,270
And if it's singular, then the
determinant of a minus lambda
385
00:17:39,270 --> 00:17:40,460
I must be equal to 0.
386
00:17:43,450 --> 00:17:46,990
So if this is true,
and it should be true
387
00:17:46,990 --> 00:17:49,000
if we don't want a
trivial solution, then
388
00:17:49,000 --> 00:17:51,520
the determinant of A minus
lambda I is equal to 0.
389
00:17:51,520 --> 00:17:54,190
So if we can compute
that determinant
390
00:17:54,190 --> 00:17:59,135
and solve for lambda, then
we'll know the eigenvalue.
391
00:17:59,135 --> 00:18:01,750
Well, it turns out that
the determinant of a matrix
392
00:18:01,750 --> 00:18:09,340
like A minus lambda I is a
polynomial in terms of lambda.
393
00:18:09,340 --> 00:18:11,190
It's a polynomial
of degree N called
394
00:18:11,190 --> 00:18:13,840
the characteristic polynomial.
395
00:18:13,840 --> 00:18:17,050
And the N roots of this
characteristic polynomial
396
00:18:17,050 --> 00:18:21,460
are called the
eigenvalues of the matrix.
397
00:18:21,460 --> 00:18:24,850
So there are N possible
lambdas for which A minus
398
00:18:24,850 --> 00:18:26,680
lambda I become singular.
399
00:18:26,680 --> 00:18:28,680
It has a null space.
400
00:18:28,680 --> 00:18:32,140
And associated with those
values are eigenvectors, vectors
401
00:18:32,140 --> 00:18:35,610
that live in that null space.
402
00:18:35,610 --> 00:18:39,140
So this polynomial-- we could
compute it for any matrix.
403
00:18:39,140 --> 00:18:41,750
We could compute this
thing in principle, right?
404
00:18:41,750 --> 00:18:47,790
And we might even be able
to factor it into this form.
405
00:18:47,790 --> 00:18:50,100
And then lambda 1,
lambda 2, lambda N
406
00:18:50,100 --> 00:18:54,210
in this factorized form are
all the possible eigenvalues
407
00:18:54,210 --> 00:18:57,010
associated with our
matrix A, right?
408
00:18:57,010 --> 00:18:59,400
There are all the possible
amounts of stretch
409
00:18:59,400 --> 00:19:02,730
that can be imparted to
particular eigenvectors.
410
00:19:02,730 --> 00:19:04,470
We don't know those
vectors yet, right?
411
00:19:04,470 --> 00:19:06,384
We'll find them in a second.
412
00:19:06,384 --> 00:19:07,800
But we know the
amounts of stretch
413
00:19:07,800 --> 00:19:09,991
that can be imparted
by this matrix.
414
00:19:09,991 --> 00:19:10,490
OK?
415
00:19:13,160 --> 00:19:16,385
Any questions so far?
416
00:19:16,385 --> 00:19:18,920
No.
417
00:19:18,920 --> 00:19:20,420
Let's do an example.
418
00:19:20,420 --> 00:19:23,218
Here's a matrix, minus 2, 1, 3.
419
00:19:23,218 --> 00:19:24,980
And it's 0's everywhere else.
420
00:19:24,980 --> 00:19:28,830
And we'd like to find the
eigenvalues of this matrix.
421
00:19:28,830 --> 00:19:33,650
So we need to know A minus
lambda I and its determinant.
422
00:19:33,650 --> 00:19:36,080
So here's A minus lambda
I. We just subtract lambda
423
00:19:36,080 --> 00:19:37,850
from each of the diagonals.
424
00:19:37,850 --> 00:19:39,731
And the determinant--
well, here, it's
425
00:19:39,731 --> 00:19:41,480
just the product of
the diagonal elements.
426
00:19:41,480 --> 00:19:43,840
So that's the determinant
of a diagonal matrix
427
00:19:43,840 --> 00:19:45,840
like this, the product
of the diagonal elements.
428
00:19:45,840 --> 00:19:49,880
So it's minus 2 minus lambda
times 1 minus lambda times 3
429
00:19:49,880 --> 00:19:51,140
minus lambda.
430
00:19:51,140 --> 00:19:53,300
And the determent of this
has to be equal to 0.
431
00:19:53,300 --> 00:19:56,600
So the amounts of
stretch, the eigenvalues
432
00:19:56,600 --> 00:20:01,830
imparted by this matrix,
are minus 2, 1, and 3.
433
00:20:01,830 --> 00:20:04,770
And we found the eigenvalues.
434
00:20:04,770 --> 00:20:06,910
Here's another matrix.
435
00:20:06,910 --> 00:20:10,690
Can you work out the
eigenvalues of this matrix?
436
00:20:10,690 --> 00:20:11,660
Let's take 90 seconds.
437
00:20:11,660 --> 00:20:12,500
You can work with
your neighbors.
438
00:20:12,500 --> 00:20:14,874
See if you can figure out the
eigenvalues of that matrix.
439
00:20:37,880 --> 00:20:39,420
Nobody's collaborating today.
440
00:20:39,420 --> 00:20:41,936
I'm going to do it myself.
441
00:20:41,936 --> 00:20:42,950
AUDIENCE: [INAUDIBLE]
442
00:20:42,950 --> 00:20:43,908
JAMES W. SWAN: It's OK.
443
00:21:48,820 --> 00:21:49,320
OK.
444
00:21:49,320 --> 00:21:51,570
What are you finding?
445
00:21:51,570 --> 00:21:54,114
Anyone want to guess
what are the eigenvalues?
446
00:21:54,114 --> 00:21:56,757
AUDIENCE: [INAUDIBLE]
447
00:21:56,757 --> 00:21:57,590
JAMES W. SWAN: Good.
448
00:21:57,590 --> 00:21:58,310
OK.
449
00:21:58,310 --> 00:22:00,601
So we need to compute the
determinant of A minus lambda
450
00:22:00,601 --> 00:22:04,340
I. That'll be minus 2
minus lambda times minus 2
451
00:22:04,340 --> 00:22:07,310
minus lambda minus 1.
452
00:22:07,310 --> 00:22:11,010
You can solve this to find that
lambda equals minus 3 or minus
453
00:22:11,010 --> 00:22:13,325
1.
454
00:22:13,325 --> 00:22:15,052
These little checks are useful.
455
00:22:15,052 --> 00:22:16,510
If you couldn't do
this, that's OK.
456
00:22:16,510 --> 00:22:18,370
But you should try to
practice this on your own
457
00:22:18,370 --> 00:22:19,245
to make sure you can.
458
00:22:22,554 --> 00:22:23,720
Here are some more examples.
459
00:22:23,720 --> 00:22:25,480
So the elements of
a diagonal matrix
460
00:22:25,480 --> 00:22:28,840
are always the eigenvalues
because the determinant
461
00:22:28,840 --> 00:22:30,520
of a diagonal matrix
is the product
462
00:22:30,520 --> 00:22:33,010
of the diagonal elements.
463
00:22:33,010 --> 00:22:37,660
So these diagonal values here
are the roots of the secular
464
00:22:37,660 --> 00:22:38,890
characteristic polynomial.
465
00:22:38,890 --> 00:22:41,080
They are the eigenvalues.
466
00:22:41,080 --> 00:22:44,430
It turns out the diagonal
elements of a triangular matrix
467
00:22:44,430 --> 00:22:48,090
are eigenvalues, too.
468
00:22:48,090 --> 00:22:49,670
This should seem
familiar to you.
469
00:22:49,670 --> 00:22:53,170
We talked about easy-to-solve
systems of equations, right?
470
00:22:53,170 --> 00:22:55,987
Diagonal systems of equations
are easy to solve, right?
471
00:22:55,987 --> 00:22:58,070
Triangular systems of
equations are easy to solve.
472
00:22:58,070 --> 00:23:02,090
It's also easy to find
their eigenvalues.
473
00:23:02,090 --> 00:23:04,630
So the diagonal elements
here are the eigenvalues
474
00:23:04,630 --> 00:23:08,410
of the triangular matrix.
475
00:23:08,410 --> 00:23:10,090
And eigenvalues have
certain properties
476
00:23:10,090 --> 00:23:12,990
that can be inferred from the
properties of polynomials,
477
00:23:12,990 --> 00:23:13,490
right?
478
00:23:13,490 --> 00:23:15,310
Since they are the
roots to a polynomial,
479
00:23:15,310 --> 00:23:17,470
if we know certain
things that should
480
00:23:17,470 --> 00:23:19,240
be true of those
polynomial of roots,
481
00:23:19,240 --> 00:23:21,440
that has to be true of the
eigenvalues themselves.
482
00:23:21,440 --> 00:23:25,559
So if we have a matrix
which is real-valued,
483
00:23:25,559 --> 00:23:27,100
then we know that
we're going to have
484
00:23:27,100 --> 00:23:33,330
this polynomial of degree N
which is also real-valued, OK?
485
00:23:33,330 --> 00:23:38,350
It can have no more
than N roots, right?
486
00:23:38,350 --> 00:23:44,550
And so A can have no more
than N distinct eigenvalues.
487
00:23:44,550 --> 00:23:46,850
The eigenvalues, like the
factors of the polynomial,
488
00:23:46,850 --> 00:23:48,990
don't have to be
distinct, though?
489
00:23:48,990 --> 00:23:52,160
You could have multiplicity in
the roots of the polynomial.
490
00:23:52,160 --> 00:23:58,550
So it's possible that lambda
1 here is an eigenvalue twice.
491
00:23:58,550 --> 00:24:02,250
That's referred to as
algebraic multiplicity.
492
00:24:02,250 --> 00:24:04,510
We'll come back to
that idea in a second.
493
00:24:04,510 --> 00:24:06,390
Because the polynomial
is real-valued,
494
00:24:06,390 --> 00:24:08,370
it means that the
eigenvalues could
495
00:24:08,370 --> 00:24:10,890
be real or complex,
just like the roots
496
00:24:10,890 --> 00:24:12,810
of a real-valued polynomial.
497
00:24:12,810 --> 00:24:17,220
But complex eigenvalues always
appear as conjugate pairs.
498
00:24:17,220 --> 00:24:19,680
If there is a
complex eigenvalue,
499
00:24:19,680 --> 00:24:22,860
then necessarily its
complex conjugate
500
00:24:22,860 --> 00:24:26,129
is also an eigenvalue.
501
00:24:26,129 --> 00:24:27,670
And here's a couple
other properties.
502
00:24:27,670 --> 00:24:30,180
So the determinant
of a matrix is
503
00:24:30,180 --> 00:24:32,929
the product of the eigenvalues.
504
00:24:32,929 --> 00:24:34,970
We talked once about the
trace of a matrix, which
505
00:24:34,970 --> 00:24:37,070
is the sum of its
diagonal elements.
506
00:24:37,070 --> 00:24:40,730
The trace of a matrix is also
the sum of the eigenvalues.
507
00:24:43,490 --> 00:24:45,400
These can sometimes
come in handy--
508
00:24:45,400 --> 00:24:47,196
not often, but sometimes.
509
00:24:53,160 --> 00:24:56,470
Here's an example I
talked about before--
510
00:24:56,470 --> 00:24:57,890
so a series of
chemical reactions.
511
00:24:57,890 --> 00:24:59,970
So we have a batch,
a batch reactor.
512
00:24:59,970 --> 00:25:01,260
We load some material in.
513
00:25:01,260 --> 00:25:04,160
And we want to know how the
concentrations of A, B, C,
514
00:25:04,160 --> 00:25:08,700
and D vary as a
function of time.
515
00:25:08,700 --> 00:25:11,730
And so A transforms into B.
B and C are in equilibrium.
516
00:25:11,730 --> 00:25:13,500
C and D are in equilibrium.
517
00:25:13,500 --> 00:25:16,245
And our conservation equation
for material is here.
518
00:25:19,800 --> 00:25:22,350
This is a rate matrix.
519
00:25:22,350 --> 00:25:25,020
We'd like to understand what
the characteristic polynomial
520
00:25:25,020 --> 00:25:27,600
of that is.
521
00:25:27,600 --> 00:25:29,115
The eigenvalues
of that matrix are
522
00:25:29,115 --> 00:25:31,240
going to tell us something
about how different rate
523
00:25:31,240 --> 00:25:34,770
processes evolve in time.
524
00:25:34,770 --> 00:25:38,700
You can imagine
just using units.
525
00:25:38,700 --> 00:25:40,930
On this side, we have
concentration over time.
526
00:25:40,930 --> 00:25:42,430
On this side, we
have concentration.
527
00:25:42,430 --> 00:25:45,540
And the rate matrix has units
of rate, or 1 over time.
528
00:25:45,540 --> 00:25:48,390
So those eigenvalues
also have units of rate.
529
00:25:48,390 --> 00:25:52,110
And they tell us the rate at
which different transformations
530
00:25:52,110 --> 00:25:55,589
between these materials occur.
531
00:25:55,589 --> 00:25:57,880
And so if we want to find
the characteristic polynomial
532
00:25:57,880 --> 00:26:00,760
of this matrix and we need to
compute the determinant of this
533
00:26:00,760 --> 00:26:04,000
matrix minus lambda I-- so
subtract lambda from each
534
00:26:04,000 --> 00:26:05,340
of the diagonals--
535
00:26:05,340 --> 00:26:07,570
even though this is a
four-by-four matrix,
536
00:26:07,570 --> 00:26:09,220
its determinant
is easy to compute
537
00:26:09,220 --> 00:26:11,170
because it's full of zeros.
538
00:26:11,170 --> 00:26:13,690
I'm not going to
compute it for you here.
539
00:26:13,690 --> 00:26:16,090
It'll turn out that the
characteristic polynomial looks
540
00:26:16,090 --> 00:26:16,600
like this.
541
00:26:16,600 --> 00:26:18,850
You should actually try
to do this determinant
542
00:26:18,850 --> 00:26:21,490
and show that the polynomial
works out to be this.
543
00:26:21,490 --> 00:26:23,890
But knowing that this is the
characteristic polynomial,
544
00:26:23,890 --> 00:26:26,080
what are the eigenvalues
of the rate matrix?
545
00:26:29,830 --> 00:26:31,500
If that's the
characteristic polynomial,
546
00:26:31,500 --> 00:26:33,000
what are the
eigenvalues, or tell me
547
00:26:33,000 --> 00:26:35,430
some of the eigenvalues
of the rate matrix?
548
00:26:35,430 --> 00:26:35,930
AUDIENCE: 0.
549
00:26:35,930 --> 00:26:36,638
JAMES W. SWAN: 0.
550
00:26:36,638 --> 00:26:37,500
0's an eigenvalue.
551
00:26:37,500 --> 00:26:40,470
Lambda equals 0 is a solution.
552
00:26:40,470 --> 00:26:43,020
Minus k1 is another solution.
553
00:26:43,020 --> 00:26:48,236
What is this eigenvalue
0 correspond to?
554
00:26:48,236 --> 00:26:49,194
What's that?
555
00:26:49,194 --> 00:26:52,547
AUDIENCE: [INAUDIBLE]
556
00:26:55,410 --> 00:26:56,160
JAMES W. SWAN: OK.
557
00:26:58,800 --> 00:27:06,890
Physically, it's a rate process
with 0 rate, steady state.
558
00:27:06,890 --> 00:27:10,220
So the 0 eigenvalue's going to
correspond to the steady state.
559
00:27:10,220 --> 00:27:12,560
The eigenvector associated
with that eigenvalue
560
00:27:12,560 --> 00:27:16,300
should correspond to the
steady state solution.
561
00:27:16,300 --> 00:27:19,430
How about this
eigenvalue minus k1?
562
00:27:19,430 --> 00:27:21,500
This is a rate
process with rate k1.
563
00:27:21,500 --> 00:27:23,510
What physical process
does that represent?
564
00:27:27,020 --> 00:27:30,770
It's something evolving
in time now, right?
565
00:27:30,770 --> 00:27:33,900
So that's the
transformation of A into B.
566
00:27:33,900 --> 00:27:38,090
And the eigenvector should
reflect that transformation.
567
00:27:38,090 --> 00:27:41,044
We'll see what those
eigenvectors are in a minute.
568
00:27:41,044 --> 00:27:42,710
But these eigenvalues
can be interpreted
569
00:27:42,710 --> 00:27:44,090
in terms of physical processes.
570
00:27:44,090 --> 00:27:48,230
This quadratic solution
here has some eigenvalue.
571
00:27:48,230 --> 00:27:49,400
I don't know what it is.
572
00:27:49,400 --> 00:27:51,560
You use the quadratic
formula and you can find it.
573
00:27:51,560 --> 00:27:54,380
But it involves k2, k3, k4.
574
00:27:54,380 --> 00:27:55,710
And this is a typo.
575
00:27:55,710 --> 00:27:57,810
It should be k5.
576
00:27:57,810 --> 00:28:00,590
And so that says something about
the interconversion between B,
577
00:28:00,590 --> 00:28:04,400
C, and D, and the rate
processes that occur
578
00:28:04,400 --> 00:28:11,542
as we convert from B to C to D.
579
00:28:11,542 --> 00:28:12,250
Is that too fast?
580
00:28:12,250 --> 00:28:15,280
Do you want to write some more
on this slide before I go on,
581
00:28:15,280 --> 00:28:16,980
or are you OK?
582
00:28:16,980 --> 00:28:20,190
Are there any
questions about this?
583
00:28:20,190 --> 00:28:20,690
No.
584
00:28:23,740 --> 00:28:26,500
Given an eigenvalue, a
particular eigenvalue, what's
585
00:28:26,500 --> 00:28:29,740
the corresponding eigenvector?
586
00:28:29,740 --> 00:28:32,350
We know the eigenvector
isn't uniquely specified.
587
00:28:32,350 --> 00:28:35,500
It belongs to the null
space of this matrix
588
00:28:35,500 --> 00:28:41,710
A minus lambda I times identity.
589
00:28:41,710 --> 00:28:45,010
Even though it's not
unique, we might still
590
00:28:45,010 --> 00:28:47,740
try to find it using
Gaussian elimination, right?
591
00:28:47,740 --> 00:28:49,130
So we may try to take--
592
00:28:49,130 --> 00:28:52,090
we may try to solve the
equation A minus lambda
593
00:28:52,090 --> 00:28:56,020
I times identity
multiplied by w equals
594
00:28:56,020 --> 00:29:00,079
0 using Gaussian elimination.
595
00:29:00,079 --> 00:29:01,870
But because it's not
unique, at some point,
596
00:29:01,870 --> 00:29:05,550
we'll run out of rows
to eliminate, right?
597
00:29:05,550 --> 00:29:07,530
There's a null space
to this matrix, right?
598
00:29:07,530 --> 00:29:10,140
We won't be able to
eliminate everything.
599
00:29:10,140 --> 00:29:14,160
We'd say it's rank
deficient, right?
600
00:29:14,160 --> 00:29:16,950
So we'll be able to
eliminate up to some R,
601
00:29:16,950 --> 00:29:18,310
the rank of this matrix.
602
00:29:18,310 --> 00:29:19,740
And then all the
components below
603
00:29:19,740 --> 00:29:22,690
are essentially free or
arbitrarily specified.
604
00:29:22,690 --> 00:29:24,770
There are no
equations to say what
605
00:29:24,770 --> 00:29:27,030
those components of
the eigenvector are.
606
00:29:31,810 --> 00:29:35,500
The number of all 0 rows--
607
00:29:35,500 --> 00:29:38,331
it's called the geometric
multiplicity of the eigenvalue.
608
00:29:38,331 --> 00:29:38,830
Sorry.
609
00:29:38,830 --> 00:29:40,429
Geometric is missing here.
610
00:29:45,220 --> 00:29:47,750
It's the number of components
of the eigenvector that
611
00:29:47,750 --> 00:29:49,360
can be freely specified.
612
00:29:52,460 --> 00:29:55,820
The geometric
multiplicity might be 1.
613
00:29:55,820 --> 00:29:59,567
That's like saying that
the eigenvectors are all
614
00:29:59,567 --> 00:30:01,400
pointing in the same
direction, but can have
615
00:30:01,400 --> 00:30:03,680
arbitrary magnitude, right?
616
00:30:03,680 --> 00:30:07,400
It might have geometric
multiplicity 2, which
617
00:30:07,400 --> 00:30:10,130
means the eigenvectors
associated with this eigenvalue
618
00:30:10,130 --> 00:30:11,810
live in some plane.
619
00:30:11,810 --> 00:30:16,180
And any vector from that plane
is a corresponding eigenvector.
620
00:30:16,180 --> 00:30:18,555
It might have a higher geometric
multiplicity associated
621
00:30:18,555 --> 00:30:19,302
with it.
622
00:30:22,480 --> 00:30:23,935
So let's try something here.
623
00:30:23,935 --> 00:30:28,660
Let's try to find the
eigenvectors of this matrix.
624
00:30:28,660 --> 00:30:30,332
I told you what the
eigenvalues were.
625
00:30:30,332 --> 00:30:31,790
They were the
diagonal values here.
626
00:30:31,790 --> 00:30:35,560
So they're minus 2, 1, and 3.
627
00:30:35,560 --> 00:30:38,080
Let's look for the
eigenvector corresponding
628
00:30:38,080 --> 00:30:40,300
to this eigenvalue.
629
00:30:40,300 --> 00:30:44,450
So I want to solve this equation
A minus this particular lambda,
630
00:30:44,450 --> 00:30:49,100
which is minus 2, times
identity equals 0.
631
00:30:49,100 --> 00:30:52,070
So I got to do Gaussian
elimination on this matrix.
632
00:30:52,070 --> 00:30:54,080
It's already eliminated
for me, right?
633
00:30:54,080 --> 00:30:58,130
I have one row which
is all 0's, which
634
00:30:58,130 --> 00:31:03,080
says the first component
of my eigenvector
635
00:31:03,080 --> 00:31:05,270
can be freely specified.
636
00:31:05,270 --> 00:31:09,280
The other two
components have to be 0.
637
00:31:09,280 --> 00:31:12,160
3 times the second component
of my eigenvector is 0.
638
00:31:12,160 --> 00:31:13,940
5 times the third
component is 0.
639
00:31:13,940 --> 00:31:16,160
So the other two
components have to be 0.
640
00:31:16,160 --> 00:31:18,110
But the first component
is freely specified.
641
00:31:18,110 --> 00:31:22,340
So the eigenvector associated
with this eigenvalue
642
00:31:22,340 --> 00:31:25,520
is 1, 0, 0.
643
00:31:25,520 --> 00:31:30,650
If I take a vector which
points in the x-direction in R3
644
00:31:30,650 --> 00:31:32,080
and I multiply it
by this matrix,
645
00:31:32,080 --> 00:31:34,610
it gets stretched by minus 2.
646
00:31:34,610 --> 00:31:36,230
So I point in the
other direction.
647
00:31:36,230 --> 00:31:40,210
And I stretch out
by a factor of 2.
648
00:31:40,210 --> 00:31:43,380
You can guess then what
the other eigenvectors are.
649
00:31:43,380 --> 00:31:45,810
What's the eigenvector
associated with this eigenvalue
650
00:31:45,810 --> 00:31:47,830
here?
651
00:31:47,830 --> 00:31:50,340
0, 1, 0, or anything
proportional to that.
652
00:31:50,340 --> 00:31:51,820
What's the
eigenvector associated
653
00:31:51,820 --> 00:31:53,830
with this eigenvalue?
654
00:31:53,830 --> 00:31:56,230
0, 0, 1, or anything
proportional to it.
655
00:31:56,230 --> 00:32:00,910
All these eigenvectors have a
geometric multiplicity of 1,
656
00:32:00,910 --> 00:32:01,690
right?
657
00:32:01,690 --> 00:32:04,960
I can just specify some
scalar variant on them.
658
00:32:04,960 --> 00:32:07,000
And they'll transform
into themselves.
659
00:32:12,180 --> 00:32:14,464
Here's a problem you can try.
660
00:32:14,464 --> 00:32:16,380
Here's our series of
chemical reactions again.
661
00:32:16,380 --> 00:32:18,390
And we want to know the
eigenvector of the rate
662
00:32:18,390 --> 00:32:20,630
matrix having eigenvalue 0.
663
00:32:20,630 --> 00:32:22,380
This should correspond
to the steady state
664
00:32:22,380 --> 00:32:26,227
solution of our ordinary
differential equation here.
665
00:32:26,227 --> 00:32:28,185
So you've got to do
elimination on this matrix.
666
00:32:30,764 --> 00:32:31,430
Can you do that?
667
00:32:31,430 --> 00:32:32,530
Can you find this eigenvector?
668
00:32:32,530 --> 00:32:33,780
Try it out with your neighbor.
669
00:32:33,780 --> 00:32:35,440
See if you can do it.
670
00:32:35,440 --> 00:32:37,180
And then we'll compare results.
671
00:32:37,180 --> 00:32:39,468
This will just be a quick
test of understanding.
672
00:34:47,454 --> 00:34:50,889
Are you guys able to do this?
673
00:34:50,889 --> 00:34:52,270
Sort of, maybe?
674
00:34:56,489 --> 00:34:59,630
Here's the answer, or an
answer, for the eigenvector.
675
00:34:59,630 --> 00:35:01,470
It's not unique, right?
676
00:35:01,470 --> 00:35:04,500
It's got some constant
out in front of it.
677
00:35:04,500 --> 00:35:06,000
So you do Gaussian
elimination here.
678
00:35:06,000 --> 00:35:10,320
So subtract or add the
first row to the second row.
679
00:35:10,320 --> 00:35:12,780
You'll eliminate this 0, right?
680
00:35:12,780 --> 00:35:15,040
And then add the second
row to the third row.
681
00:35:15,040 --> 00:35:17,970
You'll eliminate this k2.
682
00:35:17,970 --> 00:35:22,870
You have to do a little bit more
work to do elimination of k4
683
00:35:22,870 --> 00:35:23,370
here.
684
00:35:23,370 --> 00:35:24,599
But that's not a big deal.
685
00:35:24,599 --> 00:35:26,640
Again, you'll add the
third row to the fourth row
686
00:35:26,640 --> 00:35:28,230
and eliminate that.
687
00:35:28,230 --> 00:35:30,870
And you'll also wind
up eliminating this k5.
688
00:35:30,870 --> 00:35:33,960
So the last row here
will be all 0's.
689
00:35:33,960 --> 00:35:37,140
And that means the last
component of our eigenvector's
690
00:35:37,140 --> 00:35:37,950
freely specifiable.
691
00:35:37,950 --> 00:35:39,970
It can be anything we want.
692
00:35:39,970 --> 00:35:41,770
So I said it is 1.
693
00:35:41,770 --> 00:35:43,860
And then I did back
substitution to determine all
694
00:35:43,860 --> 00:35:46,530
the other components, right?
695
00:35:46,530 --> 00:35:47,990
That's the way to do this.
696
00:35:47,990 --> 00:35:50,780
And here's what the eigenvector
looks like when you're done.
697
00:35:50,780 --> 00:35:53,160
The steady state
solution has no A in it.
698
00:35:53,160 --> 00:35:56,700
Of course, A is just eliminated
by a forward reaction.
699
00:35:56,700 --> 00:35:59,430
So if we let this run out to
infinity, there should be no A.
700
00:35:59,430 --> 00:36:01,660
And that's what happens.
701
00:36:01,660 --> 00:36:05,160
But there's equilibria
between B, C, and D.
702
00:36:05,160 --> 00:36:08,130
And the steady state solution
reflects that equilibria.
703
00:36:08,130 --> 00:36:10,294
We have to pick what this
constant out in front is.
704
00:36:10,294 --> 00:36:12,210
And we discussed this
before, actually, right?
705
00:36:12,210 --> 00:36:15,030
You would pick that based on
how much material was initially
706
00:36:15,030 --> 00:36:15,950
in the reactor.
707
00:36:15,950 --> 00:36:17,750
We've got to have an
overall mass balance.
708
00:36:17,750 --> 00:36:20,940
And that's missing from this
system of equations, right?
709
00:36:20,940 --> 00:36:24,400
Mass conservation is what gave
the null space for this rate
710
00:36:24,400 --> 00:36:26,890
matrix in the first place.
711
00:36:26,890 --> 00:36:28,740
Make sense?
712
00:36:28,740 --> 00:36:30,124
Try this example out.
713
00:36:30,124 --> 00:36:32,040
See if you can work
through the details of it.
714
00:36:32,040 --> 00:36:34,456
I think it's useful to be able
to do these sorts of things
715
00:36:34,456 --> 00:36:35,249
quickly.
716
00:36:35,249 --> 00:36:36,540
Here are some simpler problems.
717
00:36:39,090 --> 00:36:40,920
So here's a matrix.
718
00:36:40,920 --> 00:36:42,420
It's not a very good matrix.
719
00:36:42,420 --> 00:36:43,840
Matrices can't be good or bad.
720
00:36:43,840 --> 00:36:45,860
It's not particularly
interesting.
721
00:36:45,860 --> 00:36:47,900
But it's all 0's.
722
00:36:47,900 --> 00:36:51,170
So what are its eigenvalues?
723
00:36:51,170 --> 00:36:53,750
It's just 0, right?
724
00:36:53,750 --> 00:36:56,090
The diagonal elements
are the eigenvalues.
725
00:36:56,090 --> 00:36:58,010
And they're 0.
726
00:36:58,010 --> 00:37:02,320
That eigenvalue has
algebraic multiplicity 2.
727
00:37:04,840 --> 00:37:08,140
It's a double root of the
secular characteristic
728
00:37:08,140 --> 00:37:08,890
polynomial.
729
00:37:11,690 --> 00:37:14,510
Can you give me
the eigenvectors?
730
00:37:25,260 --> 00:37:27,820
Can you give me
eigenvectors of this matrix?
731
00:37:27,820 --> 00:37:30,640
Can you give me linearly
independent-- yeah?
732
00:37:30,640 --> 00:37:32,381
AUDIENCE: [INAUDIBLE]
733
00:37:32,381 --> 00:37:33,130
JAMES W. SWAN: OK.
734
00:37:33,130 --> 00:37:34,960
AUDIENCE: [INAUDIBLE]
735
00:37:34,960 --> 00:37:35,710
JAMES W. SWAN: OK.
736
00:37:35,710 --> 00:37:36,209
Good.
737
00:37:36,209 --> 00:37:40,470
So this is a very ambiguous sort
of problem or question, right?
738
00:37:40,470 --> 00:37:44,050
Any vector I multiply by A here
is going to be stretched by 0
739
00:37:44,050 --> 00:37:48,790
because A by its very
nature is all 0's.
740
00:37:48,790 --> 00:37:51,910
All those vectors
live in a plane.
741
00:37:51,910 --> 00:37:53,920
So any vector from
that plane is going
742
00:37:53,920 --> 00:37:57,320
to be transformed in this way.
743
00:37:57,320 --> 00:38:00,920
The eigenvector
corresponding to eigenvalue 0
744
00:38:00,920 --> 00:38:04,760
has geometric multiplicity
2 because I can freely
745
00:38:04,760 --> 00:38:06,590
specify two of its components.
746
00:38:06,590 --> 00:38:07,250
Oh my goodness.
747
00:38:07,250 --> 00:38:08,000
I went so fast.
748
00:38:08,000 --> 00:38:09,590
We'll just do it this way.
749
00:38:09,590 --> 00:38:13,700
Algebraic multiplicity 2,
geometric multiplicity 2--
750
00:38:13,700 --> 00:38:15,850
I can pick two vectors.
751
00:38:15,850 --> 00:38:20,020
They can be any two I
want in principle, right?
752
00:38:20,020 --> 00:38:23,600
It has geometric multiplicity 2.
753
00:38:23,600 --> 00:38:24,739
Here's another matrix.
754
00:38:24,739 --> 00:38:26,780
It's a little more
interesting than the last one.
755
00:38:26,780 --> 00:38:28,115
I stuck a 1 in there instead.
756
00:38:30,790 --> 00:38:37,240
Again, the eigenvalues are 0.
757
00:38:37,240 --> 00:38:38,140
It's a double root.
758
00:38:38,140 --> 00:38:41,140
So it has algebraic
multiplicity 2.
759
00:38:44,020 --> 00:38:45,990
But you can convince
yourself that there's
760
00:38:45,990 --> 00:38:50,760
only one direction
that transforms
761
00:38:50,760 --> 00:38:54,030
that squeeze down to 0, right?
762
00:38:54,030 --> 00:38:57,840
There's only one
vector direction
763
00:38:57,840 --> 00:39:00,910
that lives in the null
space of A minus lambda I--
764
00:39:00,910 --> 00:39:04,560
lives in the null
space of A. And that's
765
00:39:04,560 --> 00:39:07,890
vectors parallel to 1, 0.
766
00:39:07,890 --> 00:39:13,050
So the eigenvector associated
with that eigenvalue 0
767
00:39:13,050 --> 00:39:16,770
has geometric
multiplicity 1 instead
768
00:39:16,770 --> 00:39:19,200
of geometric multiplicity 2.
769
00:39:30,209 --> 00:39:31,750
Now, here's an
example for you to do.
770
00:39:36,040 --> 00:39:39,460
Can you find the eigenvalues
and some linearly independent
771
00:39:39,460 --> 00:39:42,100
eigenvectors of this
matrix, which looks
772
00:39:42,100 --> 00:39:43,630
like the one we just looked at.
773
00:39:43,630 --> 00:39:47,570
But now it's three-by-three
instead of two-by-two.
774
00:39:47,570 --> 00:39:50,180
And if you find those
eigenvalues and eigenvectors,
775
00:39:50,180 --> 00:39:53,330
what are the algebraic and
geometric multiplicity?
776
00:40:12,410 --> 00:40:14,114
Well, you guys must
had a rough week.
777
00:40:14,114 --> 00:40:15,530
You're usually
much more talkative
778
00:40:15,530 --> 00:40:17,048
and energetic than this.
779
00:40:17,048 --> 00:40:18,944
[LAUGHTER]
780
00:40:25,110 --> 00:40:27,228
Well, what are the
eigenvalues here?
781
00:40:27,228 --> 00:40:28,047
AUDIENCE: 0.
782
00:40:28,047 --> 00:40:28,880
JAMES W. SWAN: Yeah.
783
00:40:28,880 --> 00:40:31,670
They all turn out to be 0.
784
00:40:31,670 --> 00:40:35,810
So that's an algebraic
multiplicity of 3.
785
00:40:35,810 --> 00:40:39,260
It'll turn out there are two
vectors, two vector directions,
786
00:40:39,260 --> 00:40:43,160
that I can specify that will
both be squeezed down to 0.
787
00:40:43,160 --> 00:40:47,630
In fact, any vector
from the x-y plane
788
00:40:47,630 --> 00:40:49,100
will also be squeezed down to 0.
789
00:40:49,100 --> 00:40:51,950
So this has algebraic
multiplicity 3 and geometric
790
00:40:51,950 --> 00:40:53,726
multiplicity 2.
791
00:40:57,909 --> 00:41:00,200
I'm going to explain why this
is important in a second.
792
00:41:00,200 --> 00:41:02,180
But understanding
that this can happen
793
00:41:02,180 --> 00:41:05,250
is going to be useful for you.
794
00:41:05,250 --> 00:41:08,225
So if an eigenvalue
is distinct, then it
795
00:41:08,225 --> 00:41:10,510
has algebraic multiplicity 1.
796
00:41:10,510 --> 00:41:13,070
It's the only eigenvalue
with that value.
797
00:41:13,070 --> 00:41:17,420
It's the only time that
amount of stretch is imparted.
798
00:41:17,420 --> 00:41:20,261
And there will be only one
corresponding eigenvector.
799
00:41:20,261 --> 00:41:22,385
There will be a direction
and an amount of stretch.
800
00:41:25,330 --> 00:41:28,550
If an eigenvalue has a
algebraic multiplicity M,
801
00:41:28,550 --> 00:41:35,040
well, you just saw that
the geometric multiplicity,
802
00:41:35,040 --> 00:41:38,280
which is the dimension of
the null space of A minus
803
00:41:38,280 --> 00:41:39,300
lambda I--
804
00:41:39,300 --> 00:41:42,690
it's the dimension
of the space spanned
805
00:41:42,690 --> 00:41:45,920
by no vectors of
A minus lambda I--
806
00:41:45,920 --> 00:41:49,080
it's going to be bigger
than 1 or equal to 1.
807
00:41:49,080 --> 00:41:51,990
And it's going to be
smaller or equal to M.
808
00:41:51,990 --> 00:41:56,650
And we saw different variants on
values that sit in this range.
809
00:41:56,650 --> 00:41:59,820
So there could be as many
as M linearly independent
810
00:41:59,820 --> 00:42:02,042
eigenvectors.
811
00:42:02,042 --> 00:42:03,000
And there may be fewer.
812
00:42:06,039 --> 00:42:07,830
So geometric multiplicity--
it's the number
813
00:42:07,830 --> 00:42:09,979
of linearly independent
eigenvectors associated
814
00:42:09,979 --> 00:42:10,770
with an eigenvalue.
815
00:42:10,770 --> 00:42:13,155
It's the dimension of the
null space of this matrix.
816
00:42:16,940 --> 00:42:20,480
Problems for which the geometric
and algebraic multiplicity
817
00:42:20,480 --> 00:42:25,070
are the same for all the
eigenvalues and eigenvectors,
818
00:42:25,070 --> 00:42:29,570
all those pairs, are nice
because the matrix then
819
00:42:29,570 --> 00:42:34,250
is said to have a complete
set of eigenvectors.
820
00:42:34,250 --> 00:42:37,190
There's enough
eigenvectors in the problem
821
00:42:37,190 --> 00:42:43,000
that they describe the
span of our vector space
822
00:42:43,000 --> 00:42:47,300
RN that our matrix is doing
transformations between.
823
00:42:47,300 --> 00:42:49,250
If we have geometric
multiplicity that's
824
00:42:49,250 --> 00:42:53,420
smaller than the
algebraic multiplicity,
825
00:42:53,420 --> 00:42:55,520
then some of these
stretched-- we
826
00:42:55,520 --> 00:42:58,460
can't stretch in all
possible directions in RN.
827
00:42:58,460 --> 00:43:02,609
There's going to be a direction
that might be left out.
828
00:43:02,609 --> 00:43:04,650
We want to be able to do
a type of transformation
829
00:43:04,650 --> 00:43:08,325
called an eigendecomposition.
830
00:43:08,325 --> 00:43:09,950
I'm going to show
you that in a second.
831
00:43:09,950 --> 00:43:12,290
It's useful for solving
systems of equations
832
00:43:12,290 --> 00:43:15,500
or for transforming systems
of ordinary differential
833
00:43:15,500 --> 00:43:19,662
equations, linear ordinary
differential equations.
834
00:43:19,662 --> 00:43:21,620
But we're only going to
be able to do that when
835
00:43:21,620 --> 00:43:24,759
we have this complete
set of eigenvectors.
836
00:43:24,759 --> 00:43:26,300
When we don't have
that complete set,
837
00:43:26,300 --> 00:43:29,750
we're going to have to do
other sorts of transformations.
838
00:43:29,750 --> 00:43:32,120
You have a problem in your
homework now, I think,
839
00:43:32,120 --> 00:43:35,796
that has this sort of a
hang-up associated with it.
840
00:43:35,796 --> 00:43:37,670
It's the second problem
in your homework set.
841
00:43:37,670 --> 00:43:39,003
That's something to think about.
842
00:43:43,290 --> 00:43:46,570
For a matrix with the
complete set of eigenvectors,
843
00:43:46,570 --> 00:43:48,800
we can write the following.
844
00:43:48,800 --> 00:43:54,100
A times a matrix W is equal
to W times the matrix lambda.
845
00:43:54,100 --> 00:43:56,030
Let me tell you what
W and lambda are.
846
00:43:56,030 --> 00:44:00,670
So W's a matrix whose
columns are made up of this--
847
00:44:00,670 --> 00:44:04,230
all of these eigenvectors.
848
00:44:04,230 --> 00:44:08,200
And lambda's a matrix
whose diagonal values are
849
00:44:08,200 --> 00:44:11,380
each of the corresponding
eigenvalues associated
850
00:44:11,380 --> 00:44:13,270
with those eigenvectors.
851
00:44:13,270 --> 00:44:19,000
This is nothing more
than a restatement
852
00:44:19,000 --> 00:44:22,940
of the original
eigenvalue problem.
853
00:44:22,940 --> 00:44:31,000
AW is lambda W. But
now each eigenvalue
854
00:44:31,000 --> 00:44:33,650
has a corresponding
particular eigenvector.
855
00:44:33,650 --> 00:44:37,750
And we've stacked
those equations up
856
00:44:37,750 --> 00:44:40,879
to make this statement about
matrix-matrix multiplication.
857
00:44:40,879 --> 00:44:42,670
So we've taken each of
these W's over here.
858
00:44:42,670 --> 00:44:45,169
And we've just made them the
columns of a particular matrix.
859
00:44:45,169 --> 00:44:47,110
But it's nothing more
than a restatement
860
00:44:47,110 --> 00:44:48,970
of the fundamental
eigenvalue problem
861
00:44:48,970 --> 00:44:50,440
we posed at the beginning here.
862
00:44:53,650 --> 00:44:57,130
But what's nice is if I
have this complete set
863
00:44:57,130 --> 00:45:02,620
of eigenvectors, then W has an
inverse that I can write down.
864
00:45:02,620 --> 00:45:05,740
So another way to state this
same equation is that lambda--
865
00:45:05,740 --> 00:45:11,620
the eigenvalues can be found
from this matrix product, W
866
00:45:11,620 --> 00:45:14,996
inverse times A times W.
867
00:45:14,996 --> 00:45:16,370
And under these
circumstances, we
868
00:45:16,370 --> 00:45:18,310
say the matrix can
be diagonalized.
869
00:45:18,310 --> 00:45:23,890
There's a transformation
from A to a diagonal form.
870
00:45:23,890 --> 00:45:25,030
That's good for us, right?
871
00:45:25,030 --> 00:45:28,000
We know diagonal systems of
equations are easy to solve,
872
00:45:28,000 --> 00:45:28,500
right?
873
00:45:28,500 --> 00:45:31,950
So if I knew what the
eigenvectors were,
874
00:45:31,950 --> 00:45:34,380
then I can transform my
equation to this diagonal form.
875
00:45:34,380 --> 00:45:37,400
I could solve systems of
equations really easily.
876
00:45:37,400 --> 00:45:39,570
Of course, we just
saw that knowing
877
00:45:39,570 --> 00:45:41,910
what those eigenvectors
are requires solving
878
00:45:41,910 --> 00:45:43,380
systems of equations, anyway.
879
00:45:43,380 --> 00:45:45,300
So the problem of
finding the eigenvectors
880
00:45:45,300 --> 00:45:49,680
is as hard as the problem of
solving a system of equations.
881
00:45:49,680 --> 00:45:52,270
But in principle, I can do
this sort of transformation.
882
00:45:52,270 --> 00:45:55,830
Equivalently, the matrix A can
be written as W times lambda
883
00:45:55,830 --> 00:45:58,320
times W inverse.
884
00:45:58,320 --> 00:46:00,270
These are all equivalent
ways of writing
885
00:46:00,270 --> 00:46:03,835
this fundamental relationship
up here when the inverse of W
886
00:46:03,835 --> 00:46:04,335
exists.
887
00:46:06,937 --> 00:46:09,520
So this means that if I know the
eigenvalues and eigenvectors,
888
00:46:09,520 --> 00:46:12,490
I can easily reconstruct
my equation, right?
889
00:46:12,490 --> 00:46:14,290
If I know the
eigenvectors in A, then I
890
00:46:14,290 --> 00:46:17,110
can easily diagonalize my
system of equations, right?
891
00:46:17,110 --> 00:46:20,410
So this is a useful sort
of transformation to do.
892
00:46:20,410 --> 00:46:23,032
We haven't talked about how
it's done in the computer.
893
00:46:23,032 --> 00:46:24,990
We've talked about how
you would do it by hand.
894
00:46:24,990 --> 00:46:26,615
These are ways you
could do it by hand.
895
00:46:26,615 --> 00:46:28,570
The computer won't do
Gaussian elimination
896
00:46:28,570 --> 00:46:32,020
for each of those eigenvectors
independently, right?
897
00:46:32,020 --> 00:46:35,360
Each elimination procedure
is order N cubed, right?
898
00:46:35,360 --> 00:46:37,110
And you got to do that
for N eigenvectors.
899
00:46:37,110 --> 00:46:39,550
So that's N to the
fourth operations.
900
00:46:39,550 --> 00:46:40,757
That's pretty slow.
901
00:46:40,757 --> 00:46:42,340
There's an alternative
way of doing it
902
00:46:42,340 --> 00:46:46,270
that's beyond the scope
of this class called--
903
00:46:46,270 --> 00:46:48,810
it's called the
Lanczos algorithm.
904
00:46:48,810 --> 00:46:52,870
And it's what's referred
to as a Krylov subspace
905
00:46:52,870 --> 00:46:54,460
method, that sort
of iterative method
906
00:46:54,460 --> 00:46:57,910
where you take products of your
matrix with certain vectors
907
00:46:57,910 --> 00:47:00,400
and from those products,
infer what the eigenvectors
908
00:47:00,400 --> 00:47:01,574
and eigenvalues are.
909
00:47:01,574 --> 00:47:03,490
So that's the way a
computer's going to do it.
910
00:47:03,490 --> 00:47:05,890
That's going to be an order
N cubed sort of calculation
911
00:47:05,890 --> 00:47:08,380
to find all the eigenvalues
and eigenvectors [INAUDIBLE]
912
00:47:08,380 --> 00:47:09,925
solving a system of equations.
913
00:47:09,925 --> 00:47:13,030
But sometimes you
want these things.
914
00:47:13,030 --> 00:47:15,970
Here's an example of how
this eigendecomposition can
915
00:47:15,970 --> 00:47:18,580
be useful to you if you did it.
916
00:47:18,580 --> 00:47:22,750
So we know the matrix A can
be represented as W lambda W
917
00:47:22,750 --> 00:47:25,480
inverse times x equals b.
918
00:47:25,480 --> 00:47:28,110
This is our transformed
system of equations here.
919
00:47:28,110 --> 00:47:30,520
We've just substituted for A.
920
00:47:30,520 --> 00:47:33,520
If I multiply both sides of
this equation by W inverse,
921
00:47:33,520 --> 00:47:37,720
then I've got lambda times
the quantity W inverse x
922
00:47:37,720 --> 00:47:39,505
is equal to W inverse b.
923
00:47:39,505 --> 00:47:42,640
And if I call this
quantity in parentheses y,
924
00:47:42,640 --> 00:47:45,500
then I have an easy-to-solve
system of equations for y.
925
00:47:48,730 --> 00:47:50,530
y is equal to lambda
inverse times c.
926
00:47:50,530 --> 00:47:53,260
But lambda inverse
is just 1 over each
927
00:47:53,260 --> 00:47:55,140
of the diagonal
components of lambda.
928
00:47:55,140 --> 00:47:58,270
Lambda's a diagonal matrix.
929
00:47:58,270 --> 00:47:59,950
Then all I need
to do-- ooh, typo.
930
00:47:59,950 --> 00:48:01,450
There's an equal
sign missing here.
931
00:48:01,450 --> 00:48:02,660
Sorry for that.
932
00:48:02,660 --> 00:48:05,800
Now all I need to do is
substitute for what I called y
933
00:48:05,800 --> 00:48:07,090
and what I called c.
934
00:48:07,090 --> 00:48:09,880
So y was W inverse times x.
935
00:48:09,880 --> 00:48:13,860
That's equal to lambda inverse
times W inverse times b.
936
00:48:13,860 --> 00:48:16,690
And so I multiply both sides of
this equation by W. And I get x
937
00:48:16,690 --> 00:48:19,240
is W lambda inverse W inverse b.
938
00:48:19,240 --> 00:48:21,450
So if I knew the eigenvalues
and eigenvectors,
939
00:48:21,450 --> 00:48:23,920
I can really easily solve
the system of equations.
940
00:48:23,920 --> 00:48:27,160
If I did this decomposition,
I could solve many systems
941
00:48:27,160 --> 00:48:28,830
of equations, right?
942
00:48:28,830 --> 00:48:30,370
They're simple to
solve with just
943
00:48:30,370 --> 00:48:33,190
matrix-matrix multiplication.
944
00:48:33,190 --> 00:48:34,785
Now, how is W inverse computed?
945
00:48:37,350 --> 00:48:42,530
Well, W inverse transpose
are actually the eigenvectors
946
00:48:42,530 --> 00:48:43,880
of A transpose.
947
00:48:46,970 --> 00:48:49,000
You may have to compute
this matrix explicitly.
948
00:48:49,000 --> 00:48:50,541
But there are times
when we deal with
949
00:48:50,541 --> 00:48:53,530
so-called symmetric
matrices, ones for which they
950
00:48:53,530 --> 00:48:57,250
are equal to their transpose.
951
00:48:57,250 --> 00:48:59,020
And if that's the
case, and if you
952
00:48:59,020 --> 00:49:02,080
take all of your eigenvectors
and you normalize them
953
00:49:02,080 --> 00:49:03,990
so they're of length 1--
954
00:49:03,990 --> 00:49:06,340
the Euclidean norm is 1--
955
00:49:06,340 --> 00:49:10,680
then it'll turn out that
W inverse is precisely
956
00:49:10,680 --> 00:49:12,720
equal to W transpose, right?
957
00:49:12,720 --> 00:49:16,170
And so the eigenvalue
matrix will be unitary.
958
00:49:16,170 --> 00:49:19,400
It'll have this property where
its transposes is its inverse,
959
00:49:19,400 --> 00:49:20,260
right?
960
00:49:20,260 --> 00:49:22,090
So this becomes
trivial to do then,
961
00:49:22,090 --> 00:49:23,490
this process of W inverse.
962
00:49:23,490 --> 00:49:26,350
It's not always true that
this is the case, right?
963
00:49:26,350 --> 00:49:29,470
It is true when we
deal with problems
964
00:49:29,470 --> 00:49:32,950
that have symmetric matrices
associated with them.
965
00:49:32,950 --> 00:49:36,910
That pops up in a lot of cases.
966
00:49:36,910 --> 00:49:37,800
You can prove--
967
00:49:37,800 --> 00:49:39,630
I might ask you to
show this some time--
968
00:49:39,630 --> 00:49:41,940
that the eigenvectors
of a symmetric matrix
969
00:49:41,940 --> 00:49:47,050
are orthogonal, that they
satisfy this property that--
970
00:49:47,050 --> 00:49:50,370
I take the dot product between
two different eigenvectors
971
00:49:50,370 --> 00:49:54,982
and it'll be equal to 0 unless
those are the same eigenvector.
972
00:49:54,982 --> 00:49:57,190
That's a property associated
with symmetric matrices.
973
00:50:02,204 --> 00:50:03,620
They're also useful
when analyzing
974
00:50:03,620 --> 00:50:05,910
systems of ordinary
differential equations.
975
00:50:05,910 --> 00:50:10,160
So here, I've got a differential
equation, a vector x dot.
976
00:50:10,160 --> 00:50:15,960
So the time derivative of
x is equal to A times x.
977
00:50:15,960 --> 00:50:19,720
And if I substitute my
eigendecomposition--
978
00:50:19,720 --> 00:50:22,650
so W lambda W inverse--
979
00:50:22,650 --> 00:50:26,430
and I define a new
unknown y instead of x,
980
00:50:26,430 --> 00:50:28,990
then I can diagonalize
that system of equations.
981
00:50:28,990 --> 00:50:32,850
So you see y dot is
equal to lambda times y
982
00:50:32,850 --> 00:50:35,130
where each component
of y is decoupled
983
00:50:35,130 --> 00:50:36,220
from all of the others.
984
00:50:36,220 --> 00:50:40,590
Each of them satisfies their own
ordinary differential equation
985
00:50:40,590 --> 00:50:43,050
that's not coupled to
any of the others, right?
986
00:50:43,050 --> 00:50:45,610
And it has a simple
first-order rate constant,
987
00:50:45,610 --> 00:50:48,180
which is the
eigenvalue associated
988
00:50:48,180 --> 00:50:51,940
with that particular
eigendirection.
989
00:50:51,940 --> 00:50:53,870
So this system of
ODEs is decoupled.
990
00:50:53,870 --> 00:50:54,930
And it's easy to solve.
991
00:50:54,930 --> 00:50:56,340
You know the solution, right?
992
00:50:56,340 --> 00:50:57,390
It's an exponential.
993
00:50:59,957 --> 00:51:01,540
And that can be quite
handy when we're
994
00:51:01,540 --> 00:51:03,850
looking at different sorts
of chemical rate processes
995
00:51:03,850 --> 00:51:06,820
that correspond to linear
differential equations.
996
00:51:06,820 --> 00:51:09,100
We'll talk about nonlinear,
systems of nonlinear,
997
00:51:09,100 --> 00:51:13,125
differential equations
later in this term.
998
00:51:13,125 --> 00:51:15,250
And you'll find out that
this same sort of analysis
999
00:51:15,250 --> 00:51:17,200
can be quite useful there.
1000
00:51:17,200 --> 00:51:18,930
So we'll linearize
those equations.
1001
00:51:18,930 --> 00:51:22,282
And we'll ask is their linear--
in their linearized form, what
1002
00:51:22,282 --> 00:51:23,740
are these different
rate constants?
1003
00:51:23,740 --> 00:51:24,760
How big are they?
1004
00:51:24,760 --> 00:51:26,260
They might determine
what we need
1005
00:51:26,260 --> 00:51:30,935
to do in order to integrate
those equations numerically
1006
00:51:30,935 --> 00:51:32,810
because there are many
times when there's not
1007
00:51:32,810 --> 00:51:35,010
a complete set of eigenvectors.
1008
00:51:35,010 --> 00:51:36,380
That happens.
1009
00:51:36,380 --> 00:51:40,300
And then the matrix can't
be diagonalized in this way.
1010
00:51:40,300 --> 00:51:42,830
There are some
components that can't
1011
00:51:42,830 --> 00:51:45,736
be decoupled from each other.
1012
00:51:45,736 --> 00:51:47,610
That's what this
diagonalization does, right?
1013
00:51:47,610 --> 00:51:50,124
It splits up these different
stretching directions
1014
00:51:50,124 --> 00:51:50,790
from each other.
1015
00:51:50,790 --> 00:51:52,560
But there's some directions
that can't be decoupled
1016
00:51:52,560 --> 00:51:53,880
from each other anymore.
1017
00:51:53,880 --> 00:51:56,230
And then there are other
transformations one can do.
1018
00:51:56,230 --> 00:51:58,800
So there's an
almost diagonal form
1019
00:51:58,800 --> 00:52:03,610
that you can transform into
called the Jordan normal form.
1020
00:52:03,610 --> 00:52:06,640
There are other transformations
that one can do, like called,
1021
00:52:06,640 --> 00:52:08,440
for example, Schur
decomposition, which
1022
00:52:08,440 --> 00:52:10,960
is a transformation
into an upper triangular
1023
00:52:10,960 --> 00:52:12,160
form for this matrix.
1024
00:52:12,160 --> 00:52:16,129
We'll talk next time about the
singular value decomposition,
1025
00:52:16,129 --> 00:52:17,920
which is another sort
of transformation one
1026
00:52:17,920 --> 00:52:22,030
can do when we don't have these
complete sets of eigenvectors.
1027
00:52:29,700 --> 00:52:31,980
But this concludes our
discussion of eigenvalues
1028
00:52:31,980 --> 00:52:32,720
and eigenvectors.
1029
00:52:32,720 --> 00:52:35,819
You'll get a chance to practice
these things on your next two
1030
00:52:35,819 --> 00:52:37,110
homework assignments, actually.
1031
00:52:37,110 --> 00:52:40,230
So it'll come up in a couple
of different circumstances.
1032
00:52:40,230 --> 00:52:43,100
I would really
encourage you to try
1033
00:52:43,100 --> 00:52:46,080
to solve some of these example
problems that were in here.
1034
00:52:46,080 --> 00:52:47,414
Solving by hand can be useful.
1035
00:52:47,414 --> 00:52:49,080
Make sure you can
work through the steps
1036
00:52:49,080 --> 00:52:53,520
and understand where these
different concepts come
1037
00:52:53,520 --> 00:52:54,960
into play in terms
of determining
1038
00:52:54,960 --> 00:52:57,221
what the eigenvalues
and eigenvectors are.
1039
00:52:57,221 --> 00:52:57,720
All right.
1040
00:52:57,720 --> 00:52:58,780
Have a great weekend.
1041
00:52:58,780 --> 00:53:00,630
See you on Monday.