1
00:00:01,161 --> 00:00:03,920
NARRATOR: The following content
is provided under a Creative
2
00:00:03,920 --> 00:00:05,310
Commons license.
3
00:00:05,310 --> 00:00:07,520
Your support will help
MIT OpenCourseWare
4
00:00:07,520 --> 00:00:11,610
continue to offer high-quality
educational resources for free.
5
00:00:11,610 --> 00:00:14,180
To make a donation or to
view additional materials
6
00:00:14,180 --> 00:00:18,140
from hundreds of MIT courses,
visit MIT OpenCourseWare
7
00:00:18,140 --> 00:00:19,026
at ocw.mit.edu.
8
00:00:23,528 --> 00:00:24,900
GILBERT STRANG: OK.
9
00:00:24,900 --> 00:00:31,740
So, I'd like to pick up again
on this neat family of matrices,
10
00:00:31,740 --> 00:00:32,960
circulant matrices.
11
00:00:32,960 --> 00:00:37,020
But first, let me say
here and then put it
12
00:00:37,020 --> 00:00:40,140
on the web, my thought
about the projects.
13
00:00:40,140 --> 00:00:45,690
So, I think the last deadline
I can give is the final class.
14
00:00:45,690 --> 00:00:49,830
So, I think that's not
next week but Wednesday
15
00:00:49,830 --> 00:00:53,550
of the following week, I think,
is our last class meeting.
16
00:00:53,550 --> 00:00:57,730
So, be great to get
them then or earlier.
17
00:00:57,730 --> 00:01:00,570
And if anybody or
everybody would
18
00:01:00,570 --> 00:01:07,420
like to tell the class a
little bit about their project,
19
00:01:07,420 --> 00:01:12,480
you know it's a
friendly audience
20
00:01:12,480 --> 00:01:17,310
and I'd be happy to make
space and time for that.
21
00:01:17,310 --> 00:01:22,320
So, send me an email and
give me the project earlier
22
00:01:22,320 --> 00:01:25,620
if you would like to just
say a few words in class.
23
00:01:25,620 --> 00:01:29,370
Or even if you are willing
to say a few words in class,
24
00:01:29,370 --> 00:01:30,320
I'll say.
25
00:01:30,320 --> 00:01:30,820
Yeah.
26
00:01:30,820 --> 00:01:34,650
Because I realize-- yeah, OK.
27
00:01:34,650 --> 00:01:36,970
So, other questions about--
28
00:01:36,970 --> 00:01:40,660
so, we're finished with
all psets and so on.
29
00:01:40,660 --> 00:01:43,040
So, it's really just
a project, and yeah.
30
00:01:43,040 --> 00:01:44,498
STUDENT: How is
the project graded?
31
00:01:44,498 --> 00:01:45,785
Like, on what basis?
32
00:01:45,785 --> 00:01:47,160
GILBERT STRANG:
How is it graded?
33
00:01:47,160 --> 00:01:48,840
Good question.
34
00:01:48,840 --> 00:01:51,600
But it's going to
be me, I guess.
35
00:01:51,600 --> 00:01:58,270
So I'll read all the projects
and come up with a grade
36
00:01:58,270 --> 00:02:01,320
somehow, you know.
37
00:02:01,320 --> 00:02:05,970
I hope you guys have
understood that my feeling is
38
00:02:05,970 --> 00:02:07,950
that the grades
in this course are
39
00:02:07,950 --> 00:02:11,890
going to be on the high
side because they should be.
40
00:02:11,890 --> 00:02:12,390
Yeah.
41
00:02:12,390 --> 00:02:14,760
I think it's that
kind of a course
42
00:02:14,760 --> 00:02:19,860
and I've asked you to
do a fair amount, and--
43
00:02:19,860 --> 00:02:22,875
anyway, that's my
starting basis.
44
00:02:25,590 --> 00:02:28,560
And there's a lot of topics
like circulant matrices
45
00:02:28,560 --> 00:02:31,920
that I'm not going to be able
to give you a pset about.
46
00:02:31,920 --> 00:02:36,720
But of course, these
are closely connected
47
00:02:36,720 --> 00:02:41,070
to the discrete
Fourier transform.
48
00:02:41,070 --> 00:02:49,350
So, let me just write the
name of the great man Fourier.
49
00:02:49,350 --> 00:02:51,806
So, the discrete Fourier
transform is, as you know,
50
00:02:51,806 --> 00:02:58,740
a very, very important
algorithm in engineering
51
00:02:58,740 --> 00:02:59,970
and in mathematics.
52
00:02:59,970 --> 00:03:01,080
Everywhere.
53
00:03:01,080 --> 00:03:08,955
Fourier is just
a key idea and so
54
00:03:08,955 --> 00:03:10,830
I think it's just good
to know about, though.
55
00:03:10,830 --> 00:03:13,860
So, circulant
matrices are connected
56
00:03:13,860 --> 00:03:20,160
with finite size matrices.
57
00:03:20,160 --> 00:03:22,230
Matrices of size n.
58
00:03:22,230 --> 00:03:28,460
So our circulant
matrices will be N by N.
59
00:03:28,460 --> 00:03:30,320
And you remember
this special form.
60
00:03:37,340 --> 00:03:40,490
So, this is a key point
about these matrices,
61
00:03:40,490 --> 00:03:48,050
C. That they're defined by
not n squared entries, only n.
62
00:03:48,050 --> 00:03:51,970
If you tell me just the
first row of the matrix,
63
00:03:51,970 --> 00:03:57,160
and that's all you would
tell Matlab, say, c0, c1, c2
64
00:03:57,160 --> 00:04:01,208
to c N minus 1.
65
00:04:01,208 --> 00:04:03,200
Then for a circulant,
that's all I
66
00:04:03,200 --> 00:04:07,120
need to know because these
diagonals are constant.
67
00:04:07,120 --> 00:04:09,590
This diagonal is constant-- c1--
68
00:04:09,590 --> 00:04:12,020
and then gets completed here.
69
00:04:12,020 --> 00:04:19,459
c2 diagonal come to c2 and then
gets completed cyclically here.
70
00:04:19,459 --> 00:04:24,050
So, n numbers and not n squared.
71
00:04:24,050 --> 00:04:29,780
The reason I mention
that, or a reason is,
72
00:04:29,780 --> 00:04:33,460
that's a big selling point
when you go to applications,
73
00:04:33,460 --> 00:04:39,010
say machine
learning, for images.
74
00:04:39,010 --> 00:04:45,130
So, you remember the big
picture of machine learning,
75
00:04:45,130 --> 00:04:48,070
deep learning, was
that you had samples.
76
00:04:51,670 --> 00:04:57,220
A lot of samples, let's
say N samples, maybe.
77
00:04:57,220 --> 00:05:03,710
And then each sample in this
image part will be an image.
78
00:05:03,710 --> 00:05:09,590
So, the thing is that an image
is described by its pixels
79
00:05:09,590 --> 00:05:13,550
and if I have 1,000
by 1,000 pixel--
80
00:05:13,550 --> 00:05:18,460
so, that's a million pixels.
81
00:05:18,460 --> 00:05:20,300
The feature vector,
the vector that's
82
00:05:20,300 --> 00:05:24,290
associated with 1
sample, is enormous.
83
00:05:24,290 --> 00:05:26,500
Is enormous.
84
00:05:26,500 --> 00:05:32,180
So I have N samples but maybe--
85
00:05:32,180 --> 00:05:35,150
well, if they were
in color that million
86
00:05:35,150 --> 00:05:36,740
suddenly becomes 3 million.
87
00:05:36,740 --> 00:05:40,680
So say 3 million features.
88
00:05:46,020 --> 00:05:50,030
So, our vectors
are a vector of--
89
00:05:50,030 --> 00:05:55,650
the whole computation of deep
learning works with our vectors
90
00:05:55,650 --> 00:05:58,740
with 3 million components.
91
00:05:58,740 --> 00:06:01,350
And that means that in the
ordinary way, if we didn't
92
00:06:01,350 --> 00:06:04,710
do anything special we
would be multiplying those
93
00:06:04,710 --> 00:06:10,380
by matrices of size like
3 million times 3 million.
94
00:06:10,380 --> 00:06:12,910
We would be computing
that many weights.
95
00:06:12,910 --> 00:06:14,530
That's like, impossible.
96
00:06:17,410 --> 00:06:21,430
And we would be computing
that for each layer
97
00:06:21,430 --> 00:06:24,670
in the deep network
so it would go up--
98
00:06:29,900 --> 00:06:32,230
so 3 million by 3
million is just--
99
00:06:32,230 --> 00:06:34,090
we can't compute.
100
00:06:34,090 --> 00:06:39,040
We can't use gradient descent
to optimize that many weights.
101
00:06:39,040 --> 00:06:45,190
So, the point is that the
matrices in deep learning
102
00:06:45,190 --> 00:06:47,140
are special.
103
00:06:47,140 --> 00:06:48,580
And they don't depend--
104
00:06:48,580 --> 00:06:51,730
they're like circulant matrices.
105
00:06:51,730 --> 00:06:54,160
They might not loop around.
106
00:06:54,160 --> 00:06:58,060
So, circulant matrices
have this cyclic feature
107
00:06:58,060 --> 00:07:02,560
that makes the theory
extremely nice.
108
00:07:02,560 --> 00:07:10,165
But of course, in general we
have matrices, let's say t0--
109
00:07:12,670 --> 00:07:18,310
constant diagonals and
maybe a bunch of diagonals.
110
00:07:18,310 --> 00:07:22,330
And here not necessarily
symmetric, or they
111
00:07:22,330 --> 00:07:23,710
might be symmetric.
112
00:07:23,710 --> 00:07:25,450
But they're not cyclic.
113
00:07:25,450 --> 00:07:29,530
So, what are these
matrices called?
114
00:07:29,530 --> 00:07:32,290
Well, they have a bunch of names
because they're so important.
115
00:07:32,290 --> 00:07:37,450
They're linear shift invariant.
116
00:07:37,450 --> 00:07:40,630
Or linear time
invariant, whatever is
117
00:07:40,630 --> 00:07:44,620
the right word in your context.
118
00:07:44,620 --> 00:07:48,430
So, they're convolutions.
119
00:07:48,430 --> 00:07:50,365
You could call it a
convolution matrix.
120
00:07:54,810 --> 00:07:57,880
When you multiply by
one of these matrices,
121
00:07:57,880 --> 00:08:05,210
I guess I'm going to call it t,
you're doing our convolution.
122
00:08:05,210 --> 00:08:09,090
And I'll better write down
the formula for convolution.
123
00:08:09,090 --> 00:08:11,190
You're not doing a
cyclic convolution
124
00:08:11,190 --> 00:08:14,670
unless the matrix cycles round.
125
00:08:14,670 --> 00:08:18,120
When you multiply by
C, this would give you
126
00:08:18,120 --> 00:08:20,820
cyclic convolution.
127
00:08:23,920 --> 00:08:27,300
Say if I multiply
C by some vector v,
128
00:08:27,300 --> 00:08:31,290
the result is the
cyclic convolution
129
00:08:31,290 --> 00:08:35,909
of the c vector
with the v vector.
130
00:08:35,909 --> 00:08:39,270
So, big C is a matrix
but it's completely
131
00:08:39,270 --> 00:08:42,659
defined by its first
row or first column.
132
00:08:42,659 --> 00:08:47,130
So I just have a vector
operation in there
133
00:08:47,130 --> 00:08:48,810
and it's a cyclic one.
134
00:08:48,810 --> 00:08:53,160
And over here, t
times a vector v
135
00:08:53,160 --> 00:08:59,960
will be the convolution of a t
vector with v, but not cyclic.
136
00:09:05,280 --> 00:09:07,830
And probably these are the
ones that would actually
137
00:09:07,830 --> 00:09:10,980
come into machine learning.
138
00:09:10,980 --> 00:09:16,620
So, linear shift invariant,
linear time invariant.
139
00:09:16,620 --> 00:09:17,970
I would call it--
140
00:09:17,970 --> 00:09:22,470
so, math people would
call it a Toeplitz matrix.
141
00:09:25,650 --> 00:09:29,840
That's why I used the letter t.
142
00:09:29,840 --> 00:09:37,180
In engineering it would be
a filter or a convolution
143
00:09:37,180 --> 00:09:40,240
or a constant diagonal matrix.
144
00:09:44,860 --> 00:09:47,420
These come up in
all sorts of places
145
00:09:47,420 --> 00:09:51,230
and they come up
in machine learning
146
00:09:51,230 --> 00:09:55,080
and with image processing.
147
00:09:55,080 --> 00:09:57,320
But basically,
because what you're
148
00:09:57,320 --> 00:10:00,380
doing at one point in
an image is pretty much
149
00:10:00,380 --> 00:10:02,450
what you're going to
do at the other points,
150
00:10:02,450 --> 00:10:05,240
you're not going to
figure out special weights
151
00:10:05,240 --> 00:10:08,053
for each little
pixel in the image.
152
00:10:08,053 --> 00:10:09,470
You're going to
take-- if you have
153
00:10:09,470 --> 00:10:15,350
an image, say you have an
image with zillions of pixels.
154
00:10:15,350 --> 00:10:19,340
Well, you might
want to cut down.
155
00:10:19,340 --> 00:10:21,830
I mean, it would be
very sensible to do
156
00:10:21,830 --> 00:10:30,160
some max pooling, some pooling
operation to make it smaller.
157
00:10:37,220 --> 00:10:42,260
So, that's really like, OK, we
don't want this large a system.
158
00:10:42,260 --> 00:10:43,940
Let's just reduce it.
159
00:10:43,940 --> 00:10:46,820
So, max pooling.
160
00:10:46,820 --> 00:10:49,100
That operation would be--
161
00:10:49,100 --> 00:10:55,640
say, take them 3 at a
time, some 9 pixels.
162
00:10:55,640 --> 00:10:59,130
And replace that 9
pixels by 1 pixel.
163
00:10:59,130 --> 00:11:02,000
So the max of those 9 numbers.
164
00:11:02,000 --> 00:11:05,720
That would be a very simple
operation that just reduces
165
00:11:05,720 --> 00:11:08,330
the dimension, make it smaller.
166
00:11:08,330 --> 00:11:09,680
Reduce the dimension.
167
00:11:16,770 --> 00:11:22,020
OK, so that's a cheap way
to make an image 4 times
168
00:11:22,020 --> 00:11:25,170
or 9 times or 64 times smaller.
169
00:11:25,170 --> 00:11:29,120
But the convolution part now--
170
00:11:29,120 --> 00:11:31,500
so, that's not
involving convolution.
171
00:11:31,500 --> 00:11:35,100
That's a different
operation here.
172
00:11:35,100 --> 00:11:40,300
Not even linear if I
take the max in each box.
173
00:11:40,300 --> 00:11:45,060
That's not a linear operation
but it's a fast one.
174
00:11:45,060 --> 00:11:51,140
OK, so where do circulants
or convolution or Toeplitz
175
00:11:51,140 --> 00:11:54,500
matrices or filters
come into it?
176
00:11:54,500 --> 00:11:56,510
So, I'll forget about
the max pooling.
177
00:11:56,510 --> 00:11:58,910
Suppose that's
happened and I still
178
00:11:58,910 --> 00:12:07,880
have a very big system
with n squared pixels,
179
00:12:07,880 --> 00:12:12,920
n squared features
for each sample.
180
00:12:12,920 --> 00:12:17,700
So, I want to operate on
that by matrices, as usual.
181
00:12:17,700 --> 00:12:24,200
I want to choose the weights to
bring out the important points.
182
00:12:24,200 --> 00:12:26,720
So, the whole idea is--
183
00:12:26,720 --> 00:12:32,150
on a image like that
I'll use a convolution.
184
00:12:35,420 --> 00:12:40,010
The same operation is
happening at each point.
185
00:12:40,010 --> 00:12:41,510
So, forget the max part.
186
00:12:41,510 --> 00:12:45,430
Let me erase, if I can
find an eraser here.
187
00:12:45,430 --> 00:12:49,200
OK, so I'm not going to--
188
00:12:49,200 --> 00:12:49,970
we've done this.
189
00:12:49,970 --> 00:12:51,890
So, that's done.
190
00:12:51,890 --> 00:12:56,090
Now, I want to
multiply it by weights.
191
00:12:56,090 --> 00:12:59,710
So, that's already done.
192
00:12:59,710 --> 00:13:02,410
OK.
193
00:13:02,410 --> 00:13:03,940
So, what am I looking to do?
194
00:13:07,000 --> 00:13:11,650
What kind of a job
would a filter do?
195
00:13:11,650 --> 00:13:17,290
A low-pass filter would
kill, or nearly kill,
196
00:13:17,290 --> 00:13:21,160
the high frequencies, the noise.
197
00:13:21,160 --> 00:13:28,060
So, if I wanted to get
a simpler image there,
198
00:13:28,060 --> 00:13:32,010
I would use a low-pass
filter, which might just--
199
00:13:32,010 --> 00:13:39,550
it might be this filter here.
200
00:13:39,550 --> 00:13:42,250
Let me just put in some
numbers that would--
201
00:13:45,760 --> 00:13:46,780
say 1/2 and 1/2.
202
00:13:50,470 --> 00:13:55,360
So, I'm averaging each
pixel with its neighbor
203
00:13:55,360 --> 00:13:59,770
just to take out some
of the high frequencies.
204
00:13:59,770 --> 00:14:02,350
The low frequencies
are constant.
205
00:14:02,350 --> 00:14:06,460
An all-black image would
come out not changed
206
00:14:06,460 --> 00:14:14,560
but a very highly speckled
image would get largely removed
207
00:14:14,560 --> 00:14:15,700
by that averaging.
208
00:14:15,700 --> 00:14:19,330
So, it's the same
idea that comes up
209
00:14:19,330 --> 00:14:24,400
in all of signal
processing, filtering.
210
00:14:24,400 --> 00:14:34,060
So, just to complete
this thought of,
211
00:14:34,060 --> 00:14:41,250
why do neural nets-- so,
I'm answering this question.
212
00:14:41,250 --> 00:14:43,710
How do they come in
machine learning?
213
00:14:43,710 --> 00:14:48,810
So, they come when
the samples are images
214
00:14:48,810 --> 00:14:55,920
and then it's natural to use
a constant diagonal matrix,
215
00:14:55,920 --> 00:15:00,930
a shift invariant matrix
and not an arbitrary matrix.
216
00:15:00,930 --> 00:15:08,300
So, we only have to compute
n weights and not n squared.
217
00:15:08,300 --> 00:15:10,470
Yeah, so that's the point.
218
00:15:10,470 --> 00:15:13,710
So, that's one
reason for talking
219
00:15:13,710 --> 00:15:22,620
about convolution and circulant
matrices in this course.
220
00:15:22,620 --> 00:15:26,940
I guess I feel another
reason is that everything
221
00:15:26,940 --> 00:15:33,690
to do with the DFT, with
Fourier and Fourier transforms
222
00:15:33,690 --> 00:15:39,600
and Fourier matrices, that's
just stuff you gotta know.
223
00:15:39,600 --> 00:15:46,590
Every time you're dealing
with vectors where shifting
224
00:15:46,590 --> 00:15:49,230
the vectors comes
into it, that's--
225
00:15:49,230 --> 00:15:51,510
Fourier is going to come in.
226
00:15:51,510 --> 00:15:54,120
So, it's just we
should see Fourier.
227
00:15:54,120 --> 00:15:54,900
OK.
228
00:15:54,900 --> 00:16:04,260
So now I'll go back to
this specially nice case
229
00:16:04,260 --> 00:16:11,010
where the matrix loops around.
230
00:16:11,010 --> 00:16:14,100
Where I have this
cyclic convolution.
231
00:16:14,100 --> 00:16:22,950
So, this would be cyclic because
of the looping around stuff.
232
00:16:26,340 --> 00:16:29,910
So, what was the
point of last time?
233
00:16:29,910 --> 00:16:32,145
I started with this
permutation matrix.
234
00:16:35,430 --> 00:16:43,340
And the permutation matrix
has c0 equals 0, c1 equal 1,
235
00:16:43,340 --> 00:16:46,820
and the rest of the c's are 0.
236
00:16:46,820 --> 00:16:51,350
So, it's just the effect
of multiplying by this--
237
00:16:53,920 --> 00:16:56,210
get a box around it here--
238
00:16:56,210 --> 00:16:59,390
the effect of multiplying
by this permutation matrix
239
00:16:59,390 --> 00:17:03,380
is to shift everything and
then bring the last one up
240
00:17:03,380 --> 00:17:05,250
to the top.
241
00:17:05,250 --> 00:17:07,010
So, it's a cyclic shift.
242
00:17:11,910 --> 00:17:16,250
And I guess at the
very end of last time
243
00:17:16,250 --> 00:17:18,950
I was asking about
its eigenvalues
244
00:17:18,950 --> 00:17:21,599
and its eigenvectors, so can
we come to that question?
245
00:17:21,599 --> 00:17:25,640
So, that's the starting
question for everything here.
246
00:17:25,640 --> 00:17:30,500
I guess we've understood
that to get deeper
247
00:17:30,500 --> 00:17:35,180
into a matrix, its
eigenvalues, eigenvectors,
248
00:17:35,180 --> 00:17:40,880
or singular value, singular
vectors, are the way to go.
249
00:17:40,880 --> 00:17:44,645
Actually, what would be the
singular values of that matrix?
250
00:17:50,080 --> 00:17:53,070
Let's just think
about singular values
251
00:17:53,070 --> 00:17:57,650
and then we'll see why
it's eigenvalues we want.
252
00:17:57,650 --> 00:18:02,100
What are the singular values
of a permutation matrix?
253
00:18:02,100 --> 00:18:04,960
They're all 1.
254
00:18:04,960 --> 00:18:06,190
All 1.
255
00:18:06,190 --> 00:18:10,200
That matrix is a
orthogonal matrix,
256
00:18:10,200 --> 00:18:18,270
so the SVD of the matrix
just has the permutation
257
00:18:18,270 --> 00:18:21,660
and then the identity
is there for the sigma.
258
00:18:21,660 --> 00:18:25,860
So, sigma is I for
this for this matrix.
259
00:18:31,320 --> 00:18:33,300
So, the singular values don't--
260
00:18:36,140 --> 00:18:39,270
that's because P transpose
P is the identity matrix.
261
00:18:41,980 --> 00:18:44,280
Any time I have--
262
00:18:44,280 --> 00:18:48,000
that's an orthogonal matrix,
and anytime P transpose P
263
00:18:48,000 --> 00:18:50,850
is the identity,
the singular values
264
00:18:50,850 --> 00:18:53,020
will be the eigenvalues
of the identity.
265
00:18:53,020 --> 00:18:56,010
And they're all just 1's.
266
00:18:56,010 --> 00:18:59,400
The eigenvalues of P, that's
what we want to find, so let's
267
00:18:59,400 --> 00:19:00,380
do that.
268
00:19:00,380 --> 00:19:06,030
OK, eigenvalues
of P. So, one way
269
00:19:06,030 --> 00:19:15,200
is to take P minus lambda I.
That's just the way we teach
270
00:19:15,200 --> 00:19:18,860
in 18.06 and never use again.
271
00:19:18,860 --> 00:19:23,450
So, it puts minus
lambda on the diagonal,
272
00:19:23,450 --> 00:19:26,480
and of course P is
sitting up here.
273
00:19:26,480 --> 00:19:31,100
And then the rest is 0.
274
00:19:31,100 --> 00:19:35,930
OK, so now following
the 18.06 rule,
275
00:19:35,930 --> 00:19:39,350
I should take that
determinant, right?
276
00:19:39,350 --> 00:19:42,870
And set it to 0.
277
00:19:42,870 --> 00:19:45,770
This is one of the very few
occasions we can actually
278
00:19:45,770 --> 00:19:49,220
do it, so allow me to do it.
279
00:19:49,220 --> 00:19:51,440
So, what is the
determinant of this?
280
00:19:51,440 --> 00:19:58,800
Well, there's that
lambda to the fourth,
281
00:19:58,800 --> 00:20:04,485
and I guess I think it's
lambda to the fourth minus 1.
282
00:20:04,485 --> 00:20:08,670
I think that's the
right determinant.
283
00:20:08,670 --> 00:20:15,590
That certainly has property--
so, I would set that to 0,
284
00:20:15,590 --> 00:20:21,360
then I would find that
the eigenvalues for that
285
00:20:21,360 --> 00:20:27,780
will be 1 and minus
1, and I and minus I.
286
00:20:27,780 --> 00:20:37,610
And they're the
fourth roots of 1.
287
00:20:37,610 --> 00:20:39,230
Lambda to the fourth equal 1.
288
00:20:42,410 --> 00:20:44,390
That's our eigenvalue equation.
289
00:20:44,390 --> 00:20:48,840
Lambda to the fourth equal 1
or lambda to the n-th equal 1.
290
00:20:48,840 --> 00:20:54,560
So, what would be the
eigenvalues for the P 8 by 8?
291
00:21:00,420 --> 00:21:03,320
This is the complex
plane, of course.
292
00:21:03,320 --> 00:21:08,120
Real and imaginary.
293
00:21:08,120 --> 00:21:12,520
So, that's got 8 eigenvalues.
294
00:21:12,520 --> 00:21:17,420
P to the eighth power
would be the identity.
295
00:21:17,420 --> 00:21:19,910
And that means that
lambda to the eighth power
296
00:21:19,910 --> 00:21:23,000
is 1 for the eigenvalues.
297
00:21:23,000 --> 00:21:25,970
And what are the 8 solutions?
298
00:21:25,970 --> 00:21:29,480
Every polynomial
equation of degree 8
299
00:21:29,480 --> 00:21:32,160
has got to have 8 solutions.
300
00:21:32,160 --> 00:21:37,510
That's Gauss's fundamental
theorem of algebra.
301
00:21:37,510 --> 00:21:40,158
8 solutions, so what are they?
302
00:21:40,158 --> 00:21:45,510
What are the 8 numbers
whose eighth power gives 1?
303
00:21:48,630 --> 00:21:51,430
You all probably know them.
304
00:21:51,430 --> 00:21:54,460
So, they're 1, of course
the eighth power of 1,
305
00:21:54,460 --> 00:21:58,420
the eighth power of minus 1,
the eighth power of minus I,
306
00:21:58,420 --> 00:22:00,340
and the other guys
are just here.
307
00:22:03,820 --> 00:22:07,780
The roots of 1 are equally
spaced around the circle.
308
00:22:07,780 --> 00:22:09,060
So, Fourier has come in.
309
00:22:09,060 --> 00:22:13,710
You know, Fourier wakes up
when he sees that picture.
310
00:22:13,710 --> 00:22:19,030
Fourier is going to be here and
it'll be in the eigenvectors.
311
00:22:19,030 --> 00:22:23,030
So, you're OK with
the eigenvalues?
312
00:22:23,030 --> 00:22:25,080
The eigenvalues of P will be--
313
00:22:27,660 --> 00:22:31,470
we better give a
name to this number.
314
00:22:31,470 --> 00:22:32,090
Let's see.
315
00:22:32,090 --> 00:22:36,240
I'm going to call that
number w and it will be
316
00:22:36,240 --> 00:22:41,070
e to the 2 pi i over 8, right?
317
00:22:41,070 --> 00:22:49,590
Because the whole angle is
2 pi divided in 8 pieces.
318
00:22:49,590 --> 00:22:52,650
So that's 2 pi i over 8.
319
00:22:52,650 --> 00:22:57,840
2 pi i over N for a matrix of--
320
00:22:57,840 --> 00:23:00,850
for the n by n permutation.
321
00:23:00,850 --> 00:23:03,720
Yeah, so that's number w.
322
00:23:03,720 --> 00:23:07,920
And of course, this
guy is w squared.
323
00:23:07,920 --> 00:23:15,840
This one is w cubed, w fourth,
w fifth, sixth, seventh,
324
00:23:15,840 --> 00:23:19,480
and w to the eighth
is the same as 1.
325
00:23:19,480 --> 00:23:19,980
Right.
326
00:23:27,685 --> 00:23:30,160
The reason I put
those numbers up there
327
00:23:30,160 --> 00:23:32,740
is that they come into
the eigenvectors as well
328
00:23:32,740 --> 00:23:34,120
as the eigenvalues.
329
00:23:34,120 --> 00:23:37,570
They are the eigenvalues,
these 8 numbers.
330
00:23:37,570 --> 00:23:45,220
1, 2, 3, 4, 5, 6, 7, 8 are the
8 eigenvalues of the matrix.
331
00:23:45,220 --> 00:23:48,160
Here's the 4 by 4 case.
332
00:23:48,160 --> 00:23:51,340
The matrix is an
orthogonal matrix.
333
00:23:51,340 --> 00:23:54,880
Oh, what does that tell
us about the eigenvectors?
334
00:23:54,880 --> 00:23:57,760
The eigenvectors of
an orthogonal matrix
335
00:23:57,760 --> 00:24:05,180
are orthogonal just
like symmetric matrices.
336
00:24:05,180 --> 00:24:12,820
So, do you know that
little list of matrices
337
00:24:12,820 --> 00:24:20,650
with orthogonal eigenvectors?
338
00:24:25,570 --> 00:24:27,900
I'm going to call them q.
339
00:24:27,900 --> 00:24:36,520
So qi dotted qj, the
inner product, is 1 or 0.
340
00:24:36,520 --> 00:24:42,280
1 if i equal j, 0 if i is not j.
341
00:24:42,280 --> 00:24:43,660
Orthogonal eigenvectors.
342
00:24:43,660 --> 00:24:46,480
Now, what matrices have
orthogonal eigenvectors?
343
00:24:46,480 --> 00:24:49,120
We're going back
to linear algebra
344
00:24:49,120 --> 00:24:53,110
because this is a
fundamental fact to know,
345
00:24:53,110 --> 00:24:57,370
this family of
wonderful matrices.
346
00:24:57,370 --> 00:25:00,340
Matrices with
orthogonal eigenvectors.
347
00:25:00,340 --> 00:25:03,296
Or tell me one bunch of
matrices that you know
348
00:25:03,296 --> 00:25:05,470
has orthogonal eigenvectors.
349
00:25:05,470 --> 00:25:06,420
STUDENT: Symmetric.
350
00:25:06,420 --> 00:25:07,642
GILBERT STRANG: Symmetric.
351
00:25:12,370 --> 00:25:15,150
And what is special
about the eigenvalues?
352
00:25:15,150 --> 00:25:17,730
They're real.
353
00:25:17,730 --> 00:25:21,330
But there are
other matrices that
354
00:25:21,330 --> 00:25:25,720
have orthogonal
eigenvectors and we really
355
00:25:25,720 --> 00:25:28,670
should know the whole
story about those guys.
356
00:25:28,670 --> 00:25:31,090
They're too important
not to know.
357
00:25:31,090 --> 00:25:34,550
So, what's another
bunch of matrices?
358
00:25:34,550 --> 00:25:39,010
So, these symmetric matrices
have orthogonal eigenvectors
359
00:25:39,010 --> 00:25:41,230
and--
360
00:25:41,230 --> 00:25:44,590
real symmetrics and the
eigenvalues will be real.
361
00:25:44,590 --> 00:25:47,980
Well, what other
kind of matrices
362
00:25:47,980 --> 00:25:51,220
have orthogonal eigenvectors?
363
00:25:51,220 --> 00:25:56,200
But they might be complex
and the eigenvalues
364
00:25:56,200 --> 00:25:58,240
might be complex.
365
00:25:58,240 --> 00:26:03,640
And you can't know Fourier
without saying, OK, I can
366
00:26:03,640 --> 00:26:07,600
deal with this complex number.
367
00:26:07,600 --> 00:26:10,750
OK, so what's another
family of matrices that
368
00:26:10,750 --> 00:26:13,960
has orthogonal eigenvectors?
369
00:26:13,960 --> 00:26:14,460
Yes.
370
00:26:14,460 --> 00:26:15,585
STUDENT: Diagonal matrices.
371
00:26:15,585 --> 00:26:19,270
GILBERT STRANG: Diagonal
for sure, right?
372
00:26:19,270 --> 00:26:29,860
And then we know that we
have the eigenvectors go
373
00:26:29,860 --> 00:26:32,710
into the identity matrix, right.
374
00:26:32,710 --> 00:26:35,740
Yeah, so we know everything
about diagonal ones.
375
00:26:35,740 --> 00:26:38,070
You could say those are
included in symmetric.
376
00:26:38,070 --> 00:26:40,480
Now, let's get some new ones.
377
00:26:40,480 --> 00:26:41,500
What else?
378
00:26:41,500 --> 00:26:42,940
STUDENT: [INAUDIBLE]
379
00:26:42,940 --> 00:26:45,580
GILBERT STRANG:
Orthogonal matrices count.
380
00:26:45,580 --> 00:26:51,760
Orthogonal matrices, like
permutations or like rotations
381
00:26:51,760 --> 00:26:54,180
or like reflections.
382
00:26:54,180 --> 00:26:55,160
Orthogonal matrices.
383
00:26:58,990 --> 00:27:02,970
And what's special
about their eigenvalues?
384
00:27:02,970 --> 00:27:06,684
The eigenvalues of
an orthogonal matrix?
385
00:27:06,684 --> 00:27:07,752
STUDENT: [INAUDIBLE]
386
00:27:07,752 --> 00:27:09,585
GILBERT STRANG: The
magnitude is 1, exactly.
387
00:27:12,110 --> 00:27:16,110
It has to be 1 because an
orthogonal matrix doesn't
388
00:27:16,110 --> 00:27:18,420
change the length of the vector.
389
00:27:18,420 --> 00:27:26,090
Q times x has the same
length as x for all vectors.
390
00:27:26,090 --> 00:27:29,130
And in particular,
for eigenvectors.
391
00:27:29,130 --> 00:27:36,410
So, if this was an eigenvector,
Q x would equal lambda x.
392
00:27:36,410 --> 00:27:39,510
And now if that equals that,
then lambda has to be 1.
393
00:27:39,510 --> 00:27:42,010
The magnitude of
lambda has to be 1.
394
00:27:42,010 --> 00:27:44,540
Of course.
395
00:27:44,540 --> 00:27:46,700
Complex numbers
are expected here
396
00:27:46,700 --> 00:27:49,610
and that's exactly
what we're seeing here.
397
00:27:49,610 --> 00:27:53,480
All the eigenvalues
of permutations
398
00:27:53,480 --> 00:27:56,460
are very special
orthogonal matrices.
399
00:27:56,460 --> 00:27:59,720
I won't add permutations
separately to the list
400
00:27:59,720 --> 00:28:00,590
but they count.
401
00:28:07,900 --> 00:28:10,660
The fact that this
is on the list
402
00:28:10,660 --> 00:28:13,150
tells us that the eigenvectors
that we're going to find
403
00:28:13,150 --> 00:28:14,200
are orthogonal.
404
00:28:14,200 --> 00:28:16,450
We don't have to
do a separate check
405
00:28:16,450 --> 00:28:19,930
to see that they are
once we compute them.
406
00:28:19,930 --> 00:28:21,520
They have to be.
407
00:28:21,520 --> 00:28:24,400
They're the eigenvectors
of an orthogonal matrix.
408
00:28:24,400 --> 00:28:29,320
Now, I could ask you--
let's keep going with this
409
00:28:29,320 --> 00:28:32,890
and get the whole list here.
410
00:28:32,890 --> 00:28:38,320
Along with symmetric there
is another bunch of guys.
411
00:28:38,320 --> 00:28:39,670
Antisymmetric.
412
00:28:39,670 --> 00:28:42,070
Big deal, but those
are important.
413
00:28:42,070 --> 00:28:48,220
So, symmetric means A transpose
equals A. Diagonal you know.
414
00:28:48,220 --> 00:28:54,110
A transpose equals A inverse
for orthogonal matrices.
415
00:28:54,110 --> 00:28:57,730
Now, I'm going to put in
antisymmetric matrices
416
00:28:57,730 --> 00:29:05,810
where A transpose
is minus A. What
417
00:29:05,810 --> 00:29:08,840
do you think you know
about the eigenvalues
418
00:29:08,840 --> 00:29:11,180
for antisymmetric matrices?
419
00:29:14,220 --> 00:29:17,190
Shall we take a example?
420
00:29:17,190 --> 00:29:18,600
Anti symmetric matrix.
421
00:29:21,940 --> 00:29:26,440
Say 0, 0, 1, and minus 1.
422
00:29:26,440 --> 00:29:28,540
What are the
eigenvalues of that?
423
00:29:28,540 --> 00:29:36,180
Well, if I subtract
lambda from the diagonal
424
00:29:36,180 --> 00:29:43,460
and take the determinant, I get
lambda squared plus 1 equals 0.
425
00:29:43,460 --> 00:29:46,330
So lambda is i or minus i.
426
00:29:50,740 --> 00:29:51,995
That's a rotation matrix.
427
00:29:55,380 --> 00:29:58,070
It's a rotation
through 90 degrees.
428
00:29:58,070 --> 00:30:00,320
So there could not
be a real eigenvalue.
429
00:30:00,320 --> 00:30:04,160
Have you thought about that?
430
00:30:04,160 --> 00:30:05,710
Or a real eigenvector.
431
00:30:05,710 --> 00:30:09,170
If I rotate every vector,
how could a vector
432
00:30:09,170 --> 00:30:11,810
come out a multiple of itself?
433
00:30:11,810 --> 00:30:19,120
How could I have A transpose
times the vector equal lambda
434
00:30:19,120 --> 00:30:20,600
times a vector?
435
00:30:20,600 --> 00:30:24,170
I've rotated it and yet
it's in the same direction.
436
00:30:24,170 --> 00:30:32,030
Well, somehow that's
possible in imaginary space
437
00:30:32,030 --> 00:30:34,820
and not possible in real space.
438
00:30:34,820 --> 00:30:41,940
OK, so here the
lambdas are imaginary.
439
00:30:41,940 --> 00:30:47,060
And now finally,
tell me if you know
440
00:30:47,060 --> 00:30:52,370
the name of the whole
family of matrices that
441
00:30:52,370 --> 00:30:55,010
includes all of those and more.
442
00:30:55,010 --> 00:30:59,810
Of matrices with
orthogonal eigenvectors.
443
00:30:59,810 --> 00:31:02,990
So, what are the
special properties then?
444
00:31:02,990 --> 00:31:04,620
These would be matrices.
445
00:31:04,620 --> 00:31:09,470
Shall I call them M for matrix?
446
00:31:09,470 --> 00:31:12,740
So, it has orthogonal
eigenvectors.
447
00:31:12,740 --> 00:31:17,210
So it's Q times the
diagonal times Q transpose.
448
00:31:21,910 --> 00:31:24,010
I've really written
down somehow--
449
00:31:24,010 --> 00:31:25,840
I haven't written a
name down for them
450
00:31:25,840 --> 00:31:30,160
but that's the way to get them.
451
00:31:30,160 --> 00:31:35,870
I'm allowing any
orthogonal eigenvectors.
452
00:31:35,870 --> 00:31:37,330
So, this is diagonalized.
453
00:31:37,330 --> 00:31:41,510
I've diagonalized the matrix.
454
00:31:41,510 --> 00:31:43,660
And here are any eigenvalues.
455
00:31:43,660 --> 00:31:49,000
So, the final guy on this
list allows any eigenvalues,
456
00:31:49,000 --> 00:31:51,220
any complex numbers.
457
00:31:51,220 --> 00:31:56,680
But the eigenvectors, I
want to be orthogonal.
458
00:31:56,680 --> 00:32:00,730
So that's why I have the Q.
459
00:32:00,730 --> 00:32:03,620
So, how would you
recognize such a matrix
460
00:32:03,620 --> 00:32:07,980
and what is the name for them?
461
00:32:07,980 --> 00:32:11,550
We're going beyond
18.06, because probably I
462
00:32:11,550 --> 00:32:20,200
don't mention the name for these
matrices in 18.06, but I could.
463
00:32:20,200 --> 00:32:23,440
Anybody know it?
464
00:32:23,440 --> 00:32:29,860
A matrix of that form
is a normal matrix.
465
00:32:29,860 --> 00:32:31,060
Normal.
466
00:32:31,060 --> 00:32:34,790
So, that's the total
list, is a normal matrix.
467
00:32:41,870 --> 00:32:43,920
So, normal matrices
look like that.
468
00:32:47,760 --> 00:32:51,910
I have to apologize for whoever
thought up that name, normal.
469
00:32:51,910 --> 00:32:55,155
I mean that's like, OK.
470
00:32:55,155 --> 00:32:57,030
A little more thought,
you could have come up
471
00:32:57,030 --> 00:33:01,950
with something more meaningful
than just, say, normal.
472
00:33:01,950 --> 00:33:05,490
[INAUDIBLE] that's the
absolute opposite of normal.
473
00:33:05,490 --> 00:33:08,670
Almost all matrices
are not normal.
474
00:33:08,670 --> 00:33:10,890
So anyway, but that's
what they're called.
475
00:33:10,890 --> 00:33:12,360
Normal matrices.
476
00:33:12,360 --> 00:33:17,070
And finally, how do you
recognize a normal matrix?
477
00:33:17,070 --> 00:33:20,010
Everybody knows how to
recognize a symmetric matrix
478
00:33:20,010 --> 00:33:22,410
or a diagonal
matrix, and we even
479
00:33:22,410 --> 00:33:26,610
know how to recognize an
orthogonal matrix or skew
480
00:33:26,610 --> 00:33:27,900
or antisymmetric.
481
00:33:27,900 --> 00:33:31,200
But what's the quick
test for a normal matrix?
482
00:33:33,800 --> 00:33:40,240
Well, I'll just tell you that
a normal matrix has M transpose
483
00:33:40,240 --> 00:33:42,490
M equal M M transpose.
484
00:33:45,970 --> 00:33:48,250
I'm talking here
about real matrices
485
00:33:48,250 --> 00:33:50,860
and I really should
move to complex.
486
00:33:50,860 --> 00:33:54,445
But let me just think
of them as real.
487
00:33:57,310 --> 00:34:01,000
Well, the trouble is that
the matrices might be real
488
00:34:01,000 --> 00:34:04,910
but the eigenvectors
are not going to be real
489
00:34:04,910 --> 00:34:07,130
and the eigenvalues are
not going to be real.
490
00:34:07,130 --> 00:34:08,489
So, really I--
491
00:34:08,489 --> 00:34:10,719
I'm sorry to say really again--
492
00:34:10,719 --> 00:34:17,090
I should get out of
the limitation to real.
493
00:34:17,090 --> 00:34:18,100
Yeah.
494
00:34:18,100 --> 00:34:22,570
And how do I get out of
the limitation to real?
495
00:34:22,570 --> 00:34:26,980
What do I change here if M
is a complex matrix instead
496
00:34:26,980 --> 00:34:28,520
of a real matrix?
497
00:34:28,520 --> 00:34:30,790
Then whenever you
transpose it you
498
00:34:30,790 --> 00:34:33,880
should take its
complex conjugate.
499
00:34:33,880 --> 00:34:35,920
So now that that's
the real thing.
500
00:34:35,920 --> 00:34:39,750
That's the normal thing,
that's the right thing.
501
00:34:39,750 --> 00:34:41,920
Yeah, right thing.
502
00:34:41,920 --> 00:34:42,750
Better.
503
00:34:42,750 --> 00:34:46,010
OK, so that's a normal matrix.
504
00:34:46,010 --> 00:34:48,790
And you can check
that if you took
505
00:34:48,790 --> 00:34:55,239
that M and you figured out
M transpose and did that,
506
00:34:55,239 --> 00:34:56,980
it would work.
507
00:34:56,980 --> 00:34:59,350
Because in the
end the Q's cancel
508
00:34:59,350 --> 00:35:05,890
and you just have 2
diagonal matrices there
509
00:35:05,890 --> 00:35:11,200
and that's sort of automatic,
that diagonal matrices commute.
510
00:35:11,200 --> 00:35:16,360
So, a normal matrix is one that
commutes with its transpose.
511
00:35:16,360 --> 00:35:19,390
Commutes with its
transpose or its conjugate
512
00:35:19,390 --> 00:35:21,850
transpose in the complex case.
513
00:35:21,850 --> 00:35:25,990
OK, why did I say all that?
514
00:35:25,990 --> 00:35:30,450
Simply because--
oh, I guess that--
515
00:35:30,450 --> 00:35:39,280
so the permutation
P is orthogonal
516
00:35:39,280 --> 00:35:42,070
so its eigenvectors, which
we're going to write down
517
00:35:42,070 --> 00:35:45,100
in a minute, are orthogonal.
518
00:35:45,100 --> 00:35:51,865
But actually, this matrix
C will be a normal matrix.
519
00:35:58,670 --> 00:36:01,100
I didn't see that
coming as I started
520
00:36:01,100 --> 00:36:03,170
talking about these guys.
521
00:36:03,170 --> 00:36:06,380
Yeah, so that's a normal matrix.
522
00:36:06,380 --> 00:36:08,780
Because circulant
matrices commute.
523
00:36:08,780 --> 00:36:11,410
Any 2 circulant
matrices commute.
524
00:36:11,410 --> 00:36:13,900
C1 C2 equals C2 C1.
525
00:36:18,160 --> 00:36:21,220
And now if C2 is
the transpose of--
526
00:36:21,220 --> 00:36:24,190
so, here's a matrix.
527
00:36:24,190 --> 00:36:25,870
Yeah, so these
are matrices here.
528
00:36:29,710 --> 00:36:30,860
Circulants all commute.
529
00:36:30,860 --> 00:36:33,730
It's a little
family of matrices.
530
00:36:33,730 --> 00:36:36,660
When you multiply them
together you get more of them.
531
00:36:36,660 --> 00:36:39,100
You're just staying in
that little circulant
532
00:36:39,100 --> 00:36:43,060
world with n parameters.
533
00:36:43,060 --> 00:36:46,570
And once you know the first row,
you know all the other rows.
534
00:36:50,080 --> 00:36:54,790
So in fact, they all have
the same eigenvectors.
535
00:36:54,790 --> 00:37:00,890
So, now let me be sure we get
the eigenvectors straight.
536
00:37:00,890 --> 00:37:01,390
OK.
537
00:37:08,820 --> 00:37:28,320
OK, eigenvectors of P will
also be eigenvectors of C
538
00:37:28,320 --> 00:37:42,100
because it's a combination
of powers of P.
539
00:37:42,100 --> 00:37:44,770
So once I find the
eigenvectors of P,
540
00:37:44,770 --> 00:37:48,430
I've found the eigenvectors
of any circulant matrix.
541
00:37:48,430 --> 00:37:50,980
And these eigenvectors
are very special,
542
00:37:50,980 --> 00:37:53,110
and that's the
connection to Fourier.
543
00:37:53,110 --> 00:37:56,860
That's why-- we expect
a connection to Fourier
544
00:37:56,860 --> 00:37:59,560
because we have
something periodic.
545
00:37:59,560 --> 00:38:02,650
And that's what Fourier
is entirely about.
546
00:38:02,650 --> 00:38:05,530
OK, so what are
these eigenvectors?
547
00:38:05,530 --> 00:38:11,800
Let's take P to be 4 by 4.
548
00:38:20,110 --> 00:38:23,810
OK, so the eigenvectors are--
549
00:38:23,810 --> 00:38:27,040
so we remember, the
eigenvalues are lambda equal 1,
550
00:38:27,040 --> 00:38:30,910
lambda equal minus
1, lambda equal I,
551
00:38:30,910 --> 00:38:35,730
and lambda equal minus I. We've
got 4 eigenvectors to find
552
00:38:35,730 --> 00:38:38,980
and when we find those,
you'll have the picture.
553
00:38:38,980 --> 00:38:43,876
OK, what's the eigenvector
for lambda equal 1?
554
00:38:43,876 --> 00:38:44,820
STUDENT: 1, 1, 1, 1.
555
00:38:44,820 --> 00:38:47,220
GILBERT STRANG: 1, 1, 1, 1.
556
00:38:47,220 --> 00:38:50,340
So, let me make
it into a vector.
557
00:38:50,340 --> 00:38:54,690
And the eigenvector for
lambda equal minus 1 is?
558
00:38:54,690 --> 00:38:58,870
So, I want this shift
to change every sign.
559
00:38:58,870 --> 00:39:06,240
So I better alternate those
signs so that if I shift it,
560
00:39:06,240 --> 00:39:08,460
the 1 goes to the minus 1.
561
00:39:08,460 --> 00:39:10,020
Minus 1 goes to the 1.
562
00:39:10,020 --> 00:39:12,880
So the eigenvalue is minus 1.
563
00:39:12,880 --> 00:39:16,090
Now, what about the
eigenvalues of i?
564
00:39:16,090 --> 00:39:20,190
Sorry, the eigenvector that
goes with eigenvalue i?
565
00:39:23,790 --> 00:39:30,640
If I start it with 1 and
I do the permutation,
566
00:39:30,640 --> 00:39:35,330
I think I just want i, i
squared, i cubed there.
567
00:39:35,330 --> 00:39:37,970
And I think with this
guy, with minus i,
568
00:39:37,970 --> 00:39:42,100
I think I want the
vector 1, minus i,
569
00:39:42,100 --> 00:39:44,980
minus i squared, minus i cubed.
570
00:39:52,810 --> 00:39:57,100
So without stopping
to check, let's
571
00:39:57,100 --> 00:40:00,880
just see the nice point here.
572
00:40:00,880 --> 00:40:03,160
All the components
of eigenvectors
573
00:40:03,160 --> 00:40:08,410
are in this picture.
574
00:40:08,410 --> 00:40:10,630
Here we've got 8 eigenvectors.
575
00:40:10,630 --> 00:40:12,910
8 eigenvalues, 8 eigenvectors.
576
00:40:12,910 --> 00:40:15,250
The eigenvectors
have 8 components
577
00:40:15,250 --> 00:40:20,210
and every component is
one of these 8 numbers.
578
00:40:20,210 --> 00:40:23,300
The whole thing is constructed
from the same 8 numbers.
579
00:40:23,300 --> 00:40:26,840
The eigenvalues and
the eigenvectors.
580
00:40:26,840 --> 00:40:29,990
And really the
key point is, what
581
00:40:29,990 --> 00:40:33,200
is the matrix of eigenvectors?
582
00:40:33,200 --> 00:40:35,210
So, let's just write that down.
583
00:40:39,220 --> 00:40:56,320
So, the eigenvector matrix
for all circulants of size
584
00:40:56,320 --> 00:41:06,520
N. They all have the same
eigenvectors, including
585
00:41:06,520 --> 00:41:18,710
P. All circulants C of size
N including P of size N.
586
00:41:18,710 --> 00:41:20,690
So, what's the
eigenvector matrix?
587
00:41:20,690 --> 00:41:24,320
What are the eigenvectors?
588
00:41:24,320 --> 00:41:31,490
Well, the first
vector is all 1's.
589
00:41:31,490 --> 00:41:33,840
Just as there.
590
00:41:33,840 --> 00:41:36,950
So, that's an
eigenvector of P, right?
591
00:41:36,950 --> 00:41:44,330
Because if I multiply by P,
I do a shift, a cyclic shift,
592
00:41:44,330 --> 00:41:46,870
and I've got all 1's.
593
00:41:46,870 --> 00:41:51,860
The next eigenvector
is powers of w.
594
00:41:59,760 --> 00:42:01,970
And let me remind
you, everything
595
00:42:01,970 --> 00:42:03,845
is going to be powers of w.
596
00:42:03,845 --> 00:42:10,260
e to the 2 pi i over N.
It's that complex number
597
00:42:10,260 --> 00:42:13,880
that's 1/n of the way around.
598
00:42:13,880 --> 00:42:16,950
So, what happens if
I multiply that by P?
599
00:42:16,950 --> 00:42:24,920
It shift it and it
multiplies by w or 1/w,
600
00:42:24,920 --> 00:42:27,200
which is another eigenvector.
601
00:42:27,200 --> 00:42:32,960
OK, and then the next one in
this list will be going with w
602
00:42:32,960 --> 00:42:33,590
squared.
603
00:42:33,590 --> 00:42:39,570
So it will be w fourth, w to
the sixth, w to the eighth.
604
00:42:39,570 --> 00:42:43,480
Wait a minute, did I get
these lined up all right?
605
00:42:43,480 --> 00:42:45,410
w goes with w squared.
606
00:42:45,410 --> 00:42:45,910
Whoops.
607
00:42:51,610 --> 00:42:52,520
w squared.
608
00:42:52,520 --> 00:42:57,550
Now it's w to the fourth, w
the sixth, w to the eighth,
609
00:42:57,550 --> 00:43:01,965
w to the 10th, w to the
12th, and w to the 14th.
610
00:43:05,470 --> 00:43:06,310
And they keep going.
611
00:43:09,940 --> 00:43:13,780
So that's the eigenvector
with eigenvalue 1.
612
00:43:13,780 --> 00:43:18,460
This will have the eigenvalue--
it's either w or the conjugate,
613
00:43:18,460 --> 00:43:21,280
might be the conjugate, w bar.
614
00:43:21,280 --> 00:43:24,610
And you see this matrix.
615
00:43:24,610 --> 00:43:27,300
So, what would be
the last eigenvector?
616
00:43:27,300 --> 00:43:29,740
It would be w--
617
00:43:29,740 --> 00:43:33,100
so this is 8 by 8.
618
00:43:33,100 --> 00:43:36,530
I'm going to call that the
Fourier matrix of size 8.
619
00:43:39,370 --> 00:43:41,350
And it's the eigenvector matrix.
620
00:43:41,350 --> 00:43:50,710
So Fourier matrix equals
eigenvector matrix.
621
00:43:58,490 --> 00:44:02,680
So, what I'm saying is
that the linear algebra
622
00:44:02,680 --> 00:44:06,970
for these circulants
is fantastic.
623
00:44:06,970 --> 00:44:09,880
They all have the same
eigenvector matrix.
624
00:44:09,880 --> 00:44:12,790
It happens to be the most
important complex matrix
625
00:44:12,790 --> 00:44:19,090
in the world and its
properties are golden.
626
00:44:19,090 --> 00:44:23,420
And it allows the fast
Fourier transform,
627
00:44:23,420 --> 00:44:26,980
which we could write in
matrix language next time.
628
00:44:26,980 --> 00:44:30,010
And all the entries
are powers of w.
629
00:44:30,010 --> 00:44:36,130
All the entries are
on the unit circle
630
00:44:36,130 --> 00:44:38,830
at one of those 8 points.
631
00:44:38,830 --> 00:44:43,780
And the last guy would be w to
the seventh, w to the 14th, w
632
00:44:43,780 --> 00:44:52,345
to the 21st, 28th,
35th, 42nd, and 49th.
633
00:44:56,970 --> 00:45:00,960
So, w to the 49th
would be the last.
634
00:45:00,960 --> 00:45:02,460
7 squared.
635
00:45:02,460 --> 00:45:06,350
It starts out with
w to the 0 times 0.
636
00:45:11,880 --> 00:45:15,510
You see that picture.
637
00:45:15,510 --> 00:45:16,890
w to the 49th.
638
00:45:16,890 --> 00:45:19,530
What is actually w to the 49th?
639
00:45:19,530 --> 00:45:26,600
If w is the eighth root of 1,
so we have w to the eighth,
640
00:45:26,600 --> 00:45:31,170
it's 1 because I'm doing 8 by 8.
641
00:45:31,170 --> 00:45:33,450
What is w to the 49th power?
642
00:45:36,306 --> 00:45:37,260
STUDENT: [INAUDIBLE]
643
00:45:37,260 --> 00:45:38,020
GILBERT STRANG: w?
644
00:45:38,020 --> 00:45:39,450
It's the same as w.
645
00:45:39,450 --> 00:45:47,260
OK, because w to the
48th is 1, right?
646
00:45:47,260 --> 00:45:51,380
I take the sixth power of this
and I get that w to the 48th
647
00:45:51,380 --> 00:45:52,170
is 1.
648
00:45:52,170 --> 00:45:54,862
So w to the 49th
is the same as w.
649
00:45:59,520 --> 00:46:04,700
Every column, every entry, in
the matrix is a power of w.
650
00:46:04,700 --> 00:46:08,310
And in fact, that power
is just the column number
651
00:46:08,310 --> 00:46:10,010
times the row number.
652
00:46:10,010 --> 00:46:12,800
Yeah, so those are
the good matrices.
653
00:46:19,860 --> 00:46:22,660
So, that is an
orthogonal matrix.
654
00:46:22,660 --> 00:46:25,800
Well, almost.
655
00:46:25,800 --> 00:46:28,770
It has orthogonal
columns but it doesn't
656
00:46:28,770 --> 00:46:30,570
have orthonormal columns.
657
00:46:33,090 --> 00:46:37,404
What's the length of
that column vector?
658
00:46:37,404 --> 00:46:38,400
STUDENT: [INAUDIBLE]
659
00:46:38,400 --> 00:46:41,060
GILBERT STRANG: The
square root of 8, right.
660
00:46:41,060 --> 00:46:44,270
I add up 1 squared 8 times
and I take the square root,
661
00:46:44,270 --> 00:46:46,950
I get to the square root of 8.
662
00:46:46,950 --> 00:46:49,880
So, this is really--
663
00:46:49,880 --> 00:46:54,860
it's the square root of 8
times an orthogonal matrix.
664
00:46:58,670 --> 00:46:59,170
Of course.
665
00:46:59,170 --> 00:47:02,780
The square root of
8 is just a number
666
00:47:02,780 --> 00:47:09,180
to divide out to make the
columns orthonormal instead
667
00:47:09,180 --> 00:47:11,060
of just orthogonal.
668
00:47:11,060 --> 00:47:15,080
But how do I know that
those are orthogonal?
669
00:47:15,080 --> 00:47:18,890
Well, I know they have to be
but I'd like to see it clearly.
670
00:47:18,890 --> 00:47:24,050
Why is that vector
orthogonal to that vector?
671
00:47:24,050 --> 00:47:25,850
First of all, they have to be.
672
00:47:25,850 --> 00:47:31,220
Because the matrix
is a normal matrix.
673
00:47:31,220 --> 00:47:34,700
Normal matrices
have orthogonal--
674
00:47:34,700 --> 00:47:38,370
oh yeah, how do I know
it's a normal matrix?
675
00:47:38,370 --> 00:47:39,725
So, I guess I can do the test.
676
00:47:44,840 --> 00:47:49,290
If I have the permutation
P, I know that P transpose P
677
00:47:49,290 --> 00:47:50,790
equals P P transpose.
678
00:47:50,790 --> 00:47:54,440
The permutations commute.
679
00:47:54,440 --> 00:47:57,080
So, it's a normal matrix.
680
00:47:57,080 --> 00:48:01,640
But I'd like to see
directly why is the dot
681
00:48:01,640 --> 00:48:05,060
product of the first
or the 0-th eigenvector
682
00:48:05,060 --> 00:48:08,810
and the eigenvector equals 0?
683
00:48:08,810 --> 00:48:10,400
Let me take that dot product.
684
00:48:10,400 --> 00:48:12,430
1 times 1 is 1.
685
00:48:12,430 --> 00:48:14,798
1 times w is w.
686
00:48:14,798 --> 00:48:17,960
1 times w squared is w squared.
687
00:48:17,960 --> 00:48:23,200
Up to w to the seventh, I
guess I'm going to finish at,
688
00:48:23,200 --> 00:48:24,050
equals 0.
689
00:48:29,610 --> 00:48:32,460
Well, what's that saying?
690
00:48:32,460 --> 00:48:44,340
Those numbers are these points
in my picture, those 8 points.
691
00:48:44,340 --> 00:48:50,940
So, those are the 8 numbers
that go into that column of--
692
00:48:50,940 --> 00:48:52,590
that eigenvector.
693
00:48:52,590 --> 00:48:55,140
Why do they add to 0?
694
00:48:55,140 --> 00:49:01,600
How do you see that the sum
of those 8 numbers is 0?
695
00:49:01,600 --> 00:49:03,040
STUDENT: There's symmetry.
696
00:49:03,040 --> 00:49:05,060
GILBERT STRANG: Yeah,
the symmetry would do it.
697
00:49:05,060 --> 00:49:12,110
When I add that guy to that guy,
w to the 0, or w to the eighth,
698
00:49:12,110 --> 00:49:14,870
or w to the 0.
699
00:49:14,870 --> 00:49:17,750
Yeah, when I add 1
and minus 1, I get 0.
700
00:49:17,750 --> 00:49:19,560
When I add these guys I get 0.
701
00:49:19,560 --> 00:49:21,280
When I add these--
702
00:49:21,280 --> 00:49:23,420
by pairs.
703
00:49:23,420 --> 00:49:27,140
But what about a 3 by 3?
704
00:49:34,820 --> 00:49:35,815
So, 3 by 3.
705
00:49:38,420 --> 00:49:43,220
This would be e to
the 2 pi i over 3.
706
00:49:43,220 --> 00:49:47,820
And then this would
be w to the 4 pi--
707
00:49:47,820 --> 00:49:52,250
this would be w squared,
e to the 4 pi i over 3.
708
00:49:52,250 --> 00:49:56,345
And I believe that those
3 vectors add to 0.
709
00:49:59,200 --> 00:50:01,350
And therefore they are
orthogonal to the 1,
710
00:50:01,350 --> 00:50:05,460
1, 1 eigenvector because
the dot product will just
711
00:50:05,460 --> 00:50:07,480
want to add those 3 numbers.
712
00:50:07,480 --> 00:50:09,090
So why is that true?
713
00:50:09,090 --> 00:50:16,830
1 plus e the 2 pi i over 3 plus
e to the 4 pi over 3 equals 0.
714
00:50:22,260 --> 00:50:27,420
Last minute of class today, we
can figure out how to do that.
715
00:50:27,420 --> 00:50:29,590
Well, I could get
a formula for--
716
00:50:29,590 --> 00:50:33,240
that sum is 1 and I
could get a closed form
717
00:50:33,240 --> 00:50:35,260
and check that I
get the answer 0.
718
00:50:35,260 --> 00:50:44,780
The quick way to see it is
maybe suppose I multiply by e
719
00:50:44,780 --> 00:50:48,530
to the 2 pi i over 3.
720
00:50:48,530 --> 00:50:52,730
So, I multiply every term, so
that's e to the 2 pi i over 3.
721
00:50:52,730 --> 00:50:56,450
e to the 4 pi i over 3.
722
00:50:56,450 --> 00:51:00,530
And e to the 6 pi i over 3.
723
00:51:00,530 --> 00:51:03,060
OK, what do I learn from this?
724
00:51:03,060 --> 00:51:04,760
STUDENT: [INAUDIBLE]
725
00:51:04,760 --> 00:51:07,570
GILBERT STRANG: It's the same
because e to the 6 pi i over 3
726
00:51:07,570 --> 00:51:08,340
is?
727
00:51:08,340 --> 00:51:09,110
STUDENT: 1.
728
00:51:09,110 --> 00:51:11,480
GILBERT STRANG: Is 1.
729
00:51:11,480 --> 00:51:14,210
That's 2 pi i, so that's 1.
730
00:51:14,210 --> 00:51:17,440
So I got the same sum,
1 plus this plus this.
731
00:51:17,440 --> 00:51:19,370
This plus this plus 1.
732
00:51:19,370 --> 00:51:24,710
So I got the same sum when
I multiplied by that number.
733
00:51:24,710 --> 00:51:27,110
And that sum has to be 0.
734
00:51:27,110 --> 00:51:29,570
I can't get the same sum--
735
00:51:29,570 --> 00:51:32,790
I can't multiply by this
and get the same answer
736
00:51:32,790 --> 00:51:35,450
unless I'm multiplying 0.
737
00:51:35,450 --> 00:51:43,520
So that shows me that
when n is odd I also have
738
00:51:43,520 --> 00:51:45,740
those n numbers adding to 0.
739
00:51:45,740 --> 00:51:48,740
OK, those are the basic--
740
00:51:48,740 --> 00:51:54,410
the beautiful picture
of the eigenvalues,
741
00:51:54,410 --> 00:51:57,620
the eigenvectors
being orthogonal.
742
00:51:57,620 --> 00:52:04,460
And then the actual details here
of what those eigenvectors are.
743
00:52:04,460 --> 00:52:05,750
OK, good.
744
00:52:05,750 --> 00:52:10,460
Hope you have a good weekend,
and we've just got a week
745
00:52:10,460 --> 00:52:14,060
and a half left of class.
746
00:52:14,060 --> 00:52:17,310
I may probably have one more
thing to do about Fourier
747
00:52:17,310 --> 00:52:19,760
and then we'll come
back to other topics.
748
00:52:19,760 --> 00:52:25,640
But ask any questions,
topics that you'd like to see
749
00:52:25,640 --> 00:52:27,590
included here.
750
00:52:27,590 --> 00:52:33,280
We're closing out 18.065 while
you guys do the projects.
751
00:52:33,280 --> 00:52:35,800
OK, thank you.