1
00:00:11,021 --> 00:00:17,090
OK, this is linear algebra, lecture 11
2
00:00:17,474 --> 00:00:20,146
And at the end of lecture 10
3
00:00:20,884 --> 00:00:24,232
I was talking about some vector spaces
4
00:00:25,466 --> 00:00:26,884
But there…
5
00:00:26,919 --> 00:00:31,945
The same thing in those vector spaces
were not what we usually called vectors
6
00:00:33,323 --> 00:00:37,868
Nevertheless, you could add them
and you could multiply by numbers
7
00:00:37,903 --> 00:00:39,975
So, we can't call them vectors.
8
00:00:40,344 --> 00:00:43,885
I think the example I was working with
they were matrices
9
00:00:44,228 --> 00:00:50,801
So we have a matrix space
the space of all 3 by 3 matrices
10
00:00:50,836 --> 00:00:53,226
And I would like to just
pick up on that
11
00:00:54,388 --> 00:01:00,980
Because we've been so specific
about N dimensional space here
12
00:01:01,015 --> 00:01:02,857
And you really want to see
13
00:01:02,892 --> 00:01:07,132
that the same idea has
worked as long as you can
14
00:01:07,167 --> 00:01:09,654
Add and multiply by scalars
15
00:01:09,689 --> 00:01:14,667
So these new vector spaces…
16
00:01:15,445 --> 00:01:25,797
The example I talked was
the space M of all 3 by 3 matrices
17
00:01:26,991 --> 00:01:28,087
OK
18
00:01:29,867 --> 00:01:32,640
I can add them
I can multiply by scalars
19
00:01:32,675 --> 00:01:36,461
I can multiply 2 of them together
but I don't do that
20
00:01:37,072 --> 00:01:39,447
That's not a part of the vector
space vector
21
00:01:39,482 --> 00:01:41,833
The vector space part is just
22
00:01:41,868 --> 00:01:45,816
adding the matrices and
multiplying by numbers
23
00:01:46,472 --> 00:01:52,911
And that's fine, we stay within
this space of 3 by 3 matrices
24
00:01:52,946 --> 00:01:58,926
And I have some subspaces that
we are interested like symmetric
25
00:01:59,818 --> 00:02:03,432
the subspace of symmetric matrices
26
00:02:03,467 --> 00:02:05,406
symmetric 3 by 3
27
00:02:06,390 --> 00:02:12,260
Or the subspace of upper triangular
3 by 3
28
00:02:14,025 --> 00:02:15,359
Now I...
29
00:02:16,961 --> 00:02:19,434
I used the word 'subspace'
30
00:02:19,855 --> 00:02:21,562
because it follows the rule
31
00:02:22,757 --> 00:02:25,884
If I multiply 2 symmetric matrices
I am still symmetric
32
00:02:25,884 --> 00:02:31,165
If I multiply 2 symmetric matrices
is the product automatically symmetric?
33
00:02:31,764 --> 00:02:35,042
No! But I'm not multiplying matrices
34
00:02:35,077 --> 00:02:39,140
I'm just adding. So I'm fine
this is the subspace
35
00:02:39,175 --> 00:02:44,929
Similarly, if I add 2 upper triangular
matrices, I'm still upper triangular
36
00:02:46,181 --> 00:02:49,318
And that's the subspace
37
00:02:49,353 --> 00:02:53,358
Now, I just want to take these examples
and ask
38
00:02:53,393 --> 00:02:56,351
Well, what's the basis
for that subspace?
39
00:02:56,386 --> 00:02:58,602
What's the dimension of that subspace?
40
00:02:58,637 --> 00:03:01,154
And what's the dimension
of the whole space?
41
00:03:01,895 --> 00:03:02,813
So
42
00:03:03,951 --> 00:03:08,753
There is a natural basis
for all 3 by 3 matrices
43
00:03:09,372 --> 00:03:11,039
And why don't we just write it down?
44
00:03:12,428 --> 00:03:14,571
So, so M -
45
00:03:14,606 --> 00:03:16,410
the basis
46
00:03:19,032 --> 00:03:20,874
for M
47
00:03:22,542 --> 00:03:25,399
again, all 3 by 3's
48
00:03:28,768 --> 00:03:29,918
Ok
49
00:03:31,533 --> 00:03:35,698
And then, I'll just count
how many members are in that basis
50
00:03:35,733 --> 00:03:37,178
and I'll know the dimension
51
00:03:37,213 --> 00:03:40,929
And, OK, it's gonna
take me a little time
52
00:03:41,674 --> 00:03:44,362
In fact, what is the dimension?
53
00:03:44,397 --> 00:03:48,835
Any idea of what
I'm coming up with next?
54
00:03:48,870 --> 00:03:55,129
How many numbers does it take
to specify that 3 by 3 matrix?
55
00:03:56,026 --> 00:03:56,830
9
56
00:03:56,963 --> 00:04:00,551
9 is the dimension I'm going to find
57
00:04:00,586 --> 00:04:03,571
And the most obvious basis would be
58
00:04:03,606 --> 00:04:07,391
The matrix, that's that matrix
59
00:04:09,184 --> 00:04:13,348
and then, this matrix
when the 1 there
60
00:04:14,862 --> 00:04:18,712
and, that's 2 of them
61
00:04:18,747 --> 00:04:20,626
shall I put in the third one
62
00:04:22,271 --> 00:04:25,730
and then onwards
63
00:04:26,293 --> 00:04:30,600
And the last one maybe
would end with a 1
64
00:04:31,153 --> 00:04:32,081
OK
65
00:04:35,657 --> 00:04:37,651
that's like the standard basis
66
00:04:37,686 --> 00:04:40,691
In fact, our basis is practically
67
00:04:41,346 --> 00:04:44,181
the same as 9-dimensional space
68
00:04:44,933 --> 00:04:51,092
It's just 9 numbers are written
in a square, instead of in a column
69
00:04:51,394 --> 00:04:56,749
But somehow it's different
and it could be sort of…
70
00:04:59,514 --> 00:05:02,442
Sort of natural for itself
71
00:05:02,477 --> 00:05:03,648
Because…
72
00:05:03,683 --> 00:05:06,661
now what about the symmetric 3 by 3's?
73
00:05:07,364 --> 00:05:08,902
So, that's a subspace
74
00:05:10,292 --> 00:05:13,939
just let you think what's
the dimension of that subspace
75
00:05:13,974 --> 00:05:16,586
and what's the basis for that subspace
76
00:05:18,134 --> 00:05:19,016
OK
77
00:05:19,548 --> 00:05:22,234
And I guess this question occurs to me
78
00:05:22,269 --> 00:05:27,348
If I looked at the subspace
of symmetric 3 by 3's
79
00:05:28,065 --> 00:05:29,183
Well
80
00:05:31,049 --> 00:05:36,063
how many of these original basis
numbers belong to the subspace?
81
00:05:37,257 --> 00:05:39,524
I think only 3 of them do
82
00:05:39,559 --> 00:05:41,163
This one is symmetric
83
00:05:41,959 --> 00:05:44,941
this last one is symmetric
84
00:05:44,976 --> 00:05:50,149
And the one in the middle
with a 1 in that position
85
00:05:50,184 --> 00:05:54,683
in the (2, 2) position
would be symmetric, but that...
86
00:05:54,718 --> 00:05:58,849
So, I've got 3 of these original 9
are symmetric, but…
87
00:06:01,817 --> 00:06:04,155
So this is an example where…
88
00:06:05,450 --> 00:06:07,226
but that, that's not all, right?
89
00:06:07,261 --> 00:06:10,103
What's the dimension?
Let's put the dimensions down
90
00:06:10,138 --> 00:06:13,809
The dimension of M
was 9
91
00:06:15,304 --> 00:06:21,314
What's the dimension?
Shall we call it S, is what?
92
00:06:21,349 --> 00:06:23,051
What's the dimension of this?
93
00:06:23,086 --> 00:06:26,187
I'm sort of taking simple examples
where we can...
94
00:06:26,222 --> 00:06:31,113
we can spot the answer
to these questions
95
00:06:31,655 --> 00:06:34,201
So, how many…
If I have a symmetric…
96
00:06:34,236 --> 00:06:38,170
Think of all symmetric matrices
as a subspace
97
00:06:38,828 --> 00:06:43,488
How many parameters do I choose
in 3 by 3 symmetric matrices?
98
00:06:44,636 --> 00:06:45,818
6, right
99
00:06:46,770 --> 00:06:51,044
If I tour the diagonal
that's 3
100
00:06:51,079 --> 00:06:57,104
And the 3 entries above the diagonal
then I know what the 3 entries below
101
00:06:57,139 --> 00:06:58,772
So, the dimension is 6
102
00:07:00,241 --> 00:07:02,654
I guess
What's the dimension of this here?
103
00:07:02,689 --> 00:07:06,490
Let's call this space U
for upper triangular
104
00:07:06,903 --> 00:07:12,517
So what's the dimension of that
space of upper triangular 3 by 3's?
105
00:07:13,086 --> 00:07:14,542
Again, 6
106
00:07:15,191 --> 00:07:17,076
Again, 6
107
00:07:19,348 --> 00:07:21,308
And…
108
00:07:23,628 --> 00:07:25,613
But we haven't got
we haven't seen the…
109
00:07:25,648 --> 00:07:31,106
Well, absolutely, maybe we had have
a basis here, for the upper triangular's
110
00:07:31,598 --> 00:07:33,702
I guess 6 of these guys
111
00:07:33,737 --> 00:07:38,573
1, 2, 3, 4
and a couple more
112
00:07:39,060 --> 00:07:43,227
would be upper triangulars
So there is an accidental case
113
00:07:43,262 --> 00:07:48,640
where the big basis contains
in it a basis for the subspace
114
00:07:49,128 --> 00:07:51,556
But for the symmetric guy
it didn't have
115
00:07:52,223 --> 00:07:55,974
The symmetric guy, the basis
so you see what
116
00:07:56,009 --> 00:07:58,784
A basis is the basics of a big space
117
00:07:58,819 --> 00:08:04,219
We generally need to think it all over
again to get a basis for the subspace
118
00:08:04,875 --> 00:08:08,146
And then how do I get other subspaces?
119
00:08:08,181 --> 00:08:14,726
Well, we spoke before about
the subspace
120
00:08:14,761 --> 00:08:20,461
the symmetric matrices
and the upper triangular
121
00:08:20,496 --> 00:08:27,961
This is symmetric and upper triangular
122
00:08:30,762 --> 00:08:32,014
OK
123
00:08:32,796 --> 00:08:34,457
What's the...
124
00:08:36,423 --> 00:08:39,644
What's the dimension of that space?
125
00:08:40,308 --> 00:08:41,862
or what's in that space?
126
00:08:41,897 --> 00:08:45,729
So, what's...if a matrix is symmetric
and also upper triangular
127
00:08:45,764 --> 00:08:49,414
that makes it diagonal
128
00:08:49,449 --> 00:08:53,872
So this is the same as
the diagonal matrices
129
00:08:54,832 --> 00:08:56,890
diagonal 3 by 3's
130
00:08:57,972 --> 00:09:05,779
And the dimension of this of S
intersect U, right?
131
00:09:05,814 --> 00:09:07,663
Are you OK with that symbol?
132
00:09:08,607 --> 00:09:12,391
That's the vectors
that are in both S and U
133
00:09:13,070 --> 00:09:14,641
And that's D
134
00:09:14,821 --> 00:09:17,786
So, as the S intersect U is
the diagonals
135
00:09:17,821 --> 00:09:23,175
and the dimension of
the diagonal matrices is 3
136
00:09:23,715 --> 00:09:26,657
And we've got a basis, no problem
137
00:09:27,488 --> 00:09:30,384
OK, as I write that, I think
OK…
138
00:09:30,419 --> 00:09:35,555
what about...
putting together…
139
00:09:35,590 --> 00:09:38,834
So this is like…
this intersection
140
00:09:38,869 --> 00:09:44,414
is taking all the vectors
that are in both
141
00:09:44,449 --> 00:09:48,128
That are symmetric and also
upper triangular
142
00:09:48,163 --> 00:09:53,014
Now we looked at the union
143
00:09:53,049 --> 00:10:00,586
Suppose I take the matrices that are
symmetric, or upper triangular
144
00:10:01,173 --> 00:10:04,269
Why was that no good?
145
00:10:04,304 --> 00:10:07,754
So why is no..
146
00:10:07,789 --> 00:10:11,690
Why am I not interested in the union
147
00:10:11,725 --> 00:10:15,736
putting together those 2 subspaces?
148
00:10:15,771 --> 00:10:20,364
So these are the matrices
that are in S or in U
149
00:10:20,557 --> 00:10:22,456
or possibly both
150
00:10:22,491 --> 00:10:24,588
so the diagonals included
151
00:10:24,623 --> 00:10:26,447
But what's that about this?
152
00:10:28,275 --> 00:10:32,688
It's not a subspace
it's like having taking…
153
00:10:32,723 --> 00:10:35,287
You know a couple of lines in a plane
154
00:10:35,799 --> 00:10:37,769
and stopping there
155
00:10:39,403 --> 00:10:41,471
A line, this is…
156
00:10:41,506 --> 00:10:45,556
so there is a 3 dimensional subspace
of a 9 dimensional space there
157
00:10:45,591 --> 00:10:46,951
Oh, sorry, 6
158
00:10:46,986 --> 00:10:50,958
There is a 6 dimensional subspace
of a 9 dimensional space
159
00:10:50,993 --> 00:10:52,182
There's another one
160
00:10:52,217 --> 00:10:55,721
But they headed in different directions
161
00:10:55,756 --> 00:10:59,770
So we can't just put them together
we have to fill in
162
00:10:59,805 --> 00:11:01,593
So, that's what we do
163
00:11:01,628 --> 00:11:05,389
To get this bigger space
that I'll write with a plus sign
164
00:11:06,937 --> 00:11:12,221
This is combinations of things
in the S and things in the U
165
00:11:12,761 --> 00:11:13,629
OK
166
00:11:13,664 --> 00:11:18,215
So, that's the final space
I'm gonna introduce
167
00:11:18,250 --> 00:11:20,626
A couple of subspaces
168
00:11:20,661 --> 00:11:25,240
I can take their intersection
and now I'm interested in…
169
00:11:25,275 --> 00:11:27,914
Not their union, but their sum
170
00:11:27,949 --> 00:11:29,300
So this would be the…
171
00:11:29,335 --> 00:11:33,790
This is the intersection
and this will be their sum
172
00:11:34,971 --> 00:11:38,893
So, what do I need
for a subspace here?
173
00:11:41,196 --> 00:11:44,892
I take anything in S
plus anything in U
174
00:11:46,700 --> 00:11:48,625
I don't just say things that are in S
175
00:11:48,660 --> 00:11:52,068
and pop in also
separately things that are in U
176
00:11:52,103 --> 00:11:58,912
This is the sum of any element of S
177
00:12:00,235 --> 00:12:10,639
That is, any symmetric matrix
plus any element of U
178
00:12:11,905 --> 00:12:12,808
OK
179
00:12:12,843 --> 00:12:17,423
Now, as long as we got an example here
tell me what we get?
180
00:12:18,785 --> 00:12:23,495
If I take every symmetric matrix
if all symmetic matrices
181
00:12:23,530 --> 00:12:26,099
And add them to all
upper triangular matrices
182
00:12:26,100 --> 00:12:29,774
then I've got a whole lot of matrices
and it is a subspace
183
00:12:31,040 --> 00:12:32,795
And what's…
184
00:12:32,795 --> 00:12:36,327
And it's a vector space, and what
vector space do I need to have?
185
00:12:37,510 --> 00:12:39,232
Any idea? What...
186
00:12:39,267 --> 00:12:44,574
What matrices can I get out of
a symmetric plus an upper triangular?
187
00:12:45,979 --> 00:12:47,371
I can get anything
188
00:12:47,751 --> 00:12:53,053
I get all matrices!
I get all 3 by 3's
189
00:12:57,015 --> 00:12:58,176
Which we are all thinking about that
190
00:12:58,211 --> 00:13:00,624
It's just like stretch
your mind a little
191
00:13:00,659 --> 00:13:06,173
Just a little to think of these subspaces
192
00:13:06,174 --> 00:13:09,473
and what their intersection is
193
00:13:09,508 --> 00:13:10,865
And what their sum is
194
00:13:10,900 --> 00:13:12,530
And now, can I give you a little…
195
00:13:12,565 --> 00:13:14,487
Oh, let's figure out the dimension
196
00:13:14,522 --> 00:13:23,114
So what's the dimension of
S + U in this example is?
197
00:13:25,046 --> 00:13:27,833
9, because we've got all 3 by 3's
198
00:13:29,052 --> 00:13:33,162
So the original space has….
199
00:13:33,197 --> 00:13:37,044
The original symmetric space
had dimension 6
200
00:13:37,079 --> 00:13:41,646
And the original upper triangular
space had dimension 6
201
00:13:41,681 --> 00:13:43,294
And actually
202
00:13:44,960 --> 00:13:47,441
I'm seeing here a nice formula
203
00:13:52,080 --> 00:13:54,550
That the dimension of S
204
00:13:55,316 --> 00:13:58,022
plus the dimension of U
205
00:13:58,733 --> 00:14:00,453
If I have 2 subspaces
206
00:14:00,488 --> 00:14:04,337
The dimension of one plus
the dimension of the other equals
207
00:14:06,618 --> 00:14:11,658
The dimension of their intersection
plus the dimension of their sum
208
00:14:11,693 --> 00:14:17,405
6 + 6 = 3 + 9
209
00:14:20,593 --> 00:14:22,245
This can be satisfied!
210
00:14:22,280 --> 00:14:25,122
That these natural operations…
211
00:14:25,157 --> 00:14:27,110
This is it, actually
212
00:14:27,145 --> 00:14:33,037
This is the set of natural
things to do with subspaces
213
00:14:33,072 --> 00:14:40,154
That the dimensions
come out in a good way
214
00:14:40,711 --> 00:14:41,693
OK
215
00:14:42,196 --> 00:14:47,525
Maybe I'll take just one more
example of vector space
216
00:14:48,204 --> 00:14:50,094
That doesn't have vectors in it
217
00:14:52,235 --> 00:14:55,993
It, say, comes from
differential equations
218
00:14:58,270 --> 00:15:03,535
So this is one more new vector space
that I will give just a few minutes to
219
00:15:03,570 --> 00:15:13,755
Suppose I have a differential equation
like d2y/dx^2 + y = 0
220
00:15:14,504 --> 00:15:15,525
OK
221
00:15:16,474 --> 00:15:19,038
I'm looking at the solutions
to that equation
222
00:15:20,901 --> 00:15:23,719
So what is the solution to
that equation?
223
00:15:24,715 --> 00:15:29,796
y = cos(x) is a solution
224
00:15:32,364 --> 00:15:35,339
y = sin(x) is a solution
225
00:15:36,361 --> 00:15:41,268
y equals…
well e^ix is a solution
226
00:15:41,303 --> 00:15:44,433
If you allow me to put that in
227
00:15:45,052 --> 00:15:48,154
Oh, but why should I put that in
It's already there
228
00:15:49,706 --> 00:15:52,750
You see, I'm really looking at
the nullspace here
229
00:15:52,785 --> 00:15:56,414
I'm looking at the nullspace
of a differential equation
230
00:15:57,077 --> 00:15:58,889
That's the solution space
231
00:15:59,706 --> 00:16:04,229
And describe the solution space
232
00:16:04,230 --> 00:16:07,599
all solutions to this differential equation
233
00:16:07,634 --> 00:16:11,800
So the equation is y'' + y = 0
234
00:16:12,426 --> 00:16:16,245
Cosine is a solution
Sine is a solution
235
00:16:16,280 --> 00:16:17,990
now tell me all the solutions
236
00:16:18,990 --> 00:16:19,778
there...
237
00:16:20,474 --> 00:16:23,680
So I don't need the e^ix
forget that
238
00:16:23,715 --> 00:16:28,904
What are all…
what are all the complete solution
239
00:16:35,272 --> 00:16:36,128
is what?
240
00:16:37,592 --> 00:16:39,357
A combination of these…
241
00:16:39,392 --> 00:16:42,723
The complete solution is y equals
242
00:16:42,758 --> 00:16:48,929
some multiple of the cosine
plus some multiple of the sine
243
00:16:52,942 --> 00:16:54,768
That's a vector space
244
00:16:55,820 --> 00:16:57,411
That's a vector space
245
00:16:57,446 --> 00:16:59,388
What's the dimension of that space?
246
00:16:59,423 --> 00:17:01,289
What's the basis for that space?
247
00:17:02,058 --> 00:17:04,687
OK, let me ask you a basis first
248
00:17:04,722 --> 00:17:10,431
If I take the set of the solutions of
that second order differential equation
249
00:17:11,330 --> 00:17:13,781
There it is, those are the solutions
250
00:17:14,702 --> 00:17:17,470
What's the basis for that space?
251
00:17:19,487 --> 00:17:21,956
Now remember what's
the question am I asking
252
00:17:21,991 --> 00:17:23,965
Because if you know
the question I'm asking
253
00:17:24,000 --> 00:17:25,628
You'll see the answer
254
00:17:26,436 --> 00:17:28,359
A basis means
255
00:17:28,394 --> 00:17:33,771
all the guys in the space are
combinations of these bases vectors
256
00:17:33,806 --> 00:17:38,611
Well, this is a basis
sin(x), cos(x)
257
00:17:38,646 --> 00:17:41,713
There is a basis
258
00:17:43,640 --> 00:17:44,926
Those two…
259
00:17:46,311 --> 00:17:49,071
There writes the special solutions
right?
260
00:17:49,106 --> 00:17:52,136
We have special solutions to Ax = b
261
00:17:52,171 --> 00:17:57,218
Now we've got special solutions
to differential equations
262
00:17:58,708 --> 00:18:03,643
Sorry, we have special solution to Ax=0
I misspoke
263
00:18:04,268 --> 00:18:06,914
The special solutions for the nullspace
264
00:18:06,949 --> 00:18:09,504
Just as here
we're talking about the nullspace
265
00:18:10,094 --> 00:18:12,539
Do you see that here is...
those two…
266
00:18:12,574 --> 00:18:17,469
And what's the dimension
of the solution space?
267
00:18:22,376 --> 00:18:23,448
is...
268
00:18:26,088 --> 00:18:29,192
How many vectors in this basis?
2?
269
00:18:30,040 --> 00:18:31,713
The sine and cosine?
270
00:18:32,375 --> 00:18:36,214
Are those the only basis for the space?
271
00:18:36,249 --> 00:18:37,519
By no means!
272
00:18:37,554 --> 00:18:41,724
either the e^(ix), and either e^(-ix)
would be another basis
273
00:18:42,181 --> 00:18:43,787
Lots of bases
274
00:18:43,822 --> 00:18:47,291
But do you see that really…
what...
275
00:18:48,037 --> 00:18:53,834
A course in differential... in linear
differential equations about is
276
00:18:55,053 --> 00:18:57,629
Finding a basis for the solution space
277
00:18:57,664 --> 00:19:03,232
The dimension of the solution
space will always be, will be 2
278
00:19:03,267 --> 00:19:06,391
Because we have a second order equation
279
00:19:06,426 --> 00:19:08,930
So that's like…
There's 18.03 (differential equation)
280
00:19:08,965 --> 00:19:14,593
and 5 minutes in
18.06 to care to 18.03
281
00:19:14,628 --> 00:19:15,508
OK
282
00:19:15,966 --> 00:19:18,619
So there's...
That's one more example
283
00:19:18,654 --> 00:19:22,348
and of course
the point of the example is
284
00:19:22,976 --> 00:19:28,007
These things don't look like vectors
285
00:19:28,602 --> 00:19:30,934
they look like functions
286
00:19:30,969 --> 00:19:34,678
But we can call them vectors
287
00:19:34,713 --> 00:19:36,496
Because we can add them
288
00:19:37,245 --> 00:19:39,722
and we can multiply by constants
289
00:19:39,757 --> 00:19:41,883
So we can take linear combinations
290
00:19:41,918 --> 00:19:44,050
That's all we have to be allowed to do
291
00:19:45,288 --> 00:19:48,806
So, that's really why these ideas
of linear algebra
292
00:19:48,841 --> 00:19:50,736
and basis and dimension and so on
293
00:19:50,771 --> 00:19:53,027
plays a wider world than…
294
00:19:54,371 --> 00:19:55,438
than...
295
00:19:55,915 --> 00:20:01,741
Than our constant
discussion of N by N matrices
296
00:20:01,776 --> 00:20:05,651
OK. That's what I wanted
to say about that problem
297
00:20:05,686 --> 00:20:13,069
Now, of course
the key number...
298
00:20:13,104 --> 00:20:15,486
associated with matrices…
299
00:20:15,521 --> 00:20:18,464
To go back to that number, is the rank
300
00:20:18,990 --> 00:20:21,997
And the rank…
301
00:20:22,032 --> 00:20:24,186
What do we know about the rank?
302
00:20:26,586 --> 00:20:28,993
Well, we know it's not bigger than m
303
00:20:29,028 --> 00:20:30,855
and it's not bigger than n
304
00:20:30,856 --> 00:20:34,773
So, but I'd like a little discussion
on the rank
305
00:20:34,773 --> 00:20:36,247
Maybe I'll put that here
306
00:20:36,382 --> 00:20:40,235
So I'm picking up this topic
of rank-1 matrices
307
00:20:43,825 --> 00:20:44,922
And
308
00:20:46,763 --> 00:20:52,405
the reason I'm interested in
rank-1 matrices is
309
00:20:52,405 --> 00:20:53,870
These things ought to be simple
310
00:20:54,737 --> 00:20:56,285
If the rank is only one
311
00:20:57,108 --> 00:20:58,412
the matrix can't
312
00:21:00,428 --> 00:21:01,868
get away from us
313
00:21:01,868 --> 00:21:06,639
So, for example, let me create
a rank 1 matrix
314
00:21:06,610 --> 00:21:11,409
Ok. Suppose it's 2 by 3
315
00:21:13,540 --> 00:21:17,767
and let me give you the first row
316
00:21:22,021 --> 00:21:24,646
What can the second row be?
317
00:21:25,360 --> 00:21:28,124
Tell me a possible second row here
318
00:21:29,138 --> 00:21:32,056
for this matrix to have rank 1
319
00:21:33,800 --> 00:21:35,816
A possible second row is…
320
00:21:36,374 --> 00:21:37,654
2, 8, 10
321
00:21:39,181 --> 00:21:41,500
The second row is...
322
00:21:43,635 --> 00:21:46,273
a multiple of the first row
323
00:21:47,222 --> 00:21:49,054
It's not independent
324
00:21:49,070 --> 00:21:51,775
So tell me a basis for the…
Oh yeah
325
00:21:51,775 --> 00:21:55,920
sorry to keep bringing up
the same questions
326
00:21:56,120 --> 00:21:58,264
After the clip I'll stop
327
00:21:58,202 --> 00:22:02,802
But for now, tell me a basis
for the rowspace
328
00:22:02,802 --> 00:22:06,746
The basis for the rowspace
of that matrix is…
329
00:22:08,329 --> 00:22:12,086
The first row, right?
the first row (1, 4, 5)
330
00:22:12,759 --> 00:22:17,103
A basis for the column
space of this matrix is…
331
00:22:17,103 --> 00:22:19,676
What's the dimension of
the column space?
332
00:22:21,334 --> 00:22:25,903
The dimension of the column
space is also 1, right?
333
00:22:25,938 --> 00:22:27,405
Because it is also the rank
334
00:22:27,405 --> 00:22:28,480
The dimension…
335
00:22:28,515 --> 00:22:34,138
You remember, the dimension of
the column space equals to rank
336
00:22:34,970 --> 00:22:41,261
equals to the dimension of the
columnspace of trans(A)
337
00:22:42,408 --> 00:22:44,460
which is the rowspace of A
338
00:22:44,872 --> 00:22:49,112
OK, and in this case it's one
R is one
339
00:22:50,488 --> 00:22:54,078
And sure enough, all columns are…
340
00:22:54,079 --> 00:22:57,282
All the other columns are
multiples of that column
341
00:22:57,494 --> 00:23:02,865
Now, there ought to be
a nice way to see that
342
00:23:03,892 --> 00:23:05,171
and here it is
343
00:23:06,035 --> 00:23:12,382
I can write that matrix
as pivot columns (1, 2)
344
00:23:13,401 --> 00:23:18,549
Times (1, 4, 5)
345
00:23:20,620 --> 00:23:22,508
A column times a row
346
00:23:22,543 --> 00:23:27,857
One column times one row
gives me a matrix, right?
347
00:23:27,857 --> 00:23:29,913
If I multiply a column by a row
348
00:23:30,920 --> 00:23:36,863
that's 2 by 1 matrix
times a 1 by 3 matrix
349
00:23:36,898 --> 00:23:40,596
And the result of the
multiplication is 2 by 3
350
00:23:41,097 --> 00:23:43,059
And it comes out right
351
00:23:43,059 --> 00:23:50,958
So, what I wanna...
my point is, the rank-1 matrices
352
00:23:51,689 --> 00:23:55,111
Every rank-1 matrice has the form
353
00:23:55,573 --> 00:24:00,502
Some column times some row
354
00:24:01,593 --> 00:24:03,881
So, u is the column vector
355
00:24:03,881 --> 00:24:05,718
v is a column vector
356
00:24:05,718 --> 00:24:09,869
but I make it into a row by
putting in trans(v)
357
00:24:09,869 --> 00:24:12,401
So, that's the...
that's the...
358
00:24:15,368 --> 00:24:18,378
That's the complete picture
of rank-1 matrices
359
00:24:18,830 --> 00:24:21,276
We'll be interested in rank-1 matrices
360
00:24:21,276 --> 00:24:25,853
Later we'll find all their determinants
that will be easy
361
00:24:25,853 --> 00:24:28,912
Their eigenvalues that will
be interesting
362
00:24:30,217 --> 00:24:34,621
Rank-1 matrices will be like
the building blocks for all matrices
363
00:24:35,228 --> 00:24:37,672
And actually maybe you can guess…
364
00:24:43,485 --> 00:24:46,081
If I put any matrix
365
00:24:47,712 --> 00:24:51,916
a 5 by 17 matrix has rank 4
366
00:24:54,432 --> 00:24:58,339
Then it seems pretty likely
and it's true
367
00:24:58,803 --> 00:25:02,795
that I could break that
5 by 17 matrix down
368
00:25:02,795 --> 00:25:06,178
As a combination of rank-1 matrices
369
00:25:06,178 --> 00:25:09,225
And probably how many
of those would I need
370
00:25:09,983 --> 00:25:13,792
If I have a 5 by 17 matrix of rank 4
371
00:25:15,319 --> 00:25:16,720
Only four
372
00:25:17,604 --> 00:25:20,348
4 rank-1 matrices…
373
00:25:20,348 --> 00:25:24,193
So the rank-1 matrices are
the building blocks
374
00:25:24,705 --> 00:25:27,396
And I can produce every...
375
00:25:27,938 --> 00:25:34,596
I can produce every 5 by 17 rank 4
matrix out of 4 rank-1 matrices
376
00:25:34,596 --> 00:25:38,669
OK. That brings me to
a question, of course
377
00:25:40,492 --> 00:25:44,245
Would a rank-4 matrices
form a subspace?
378
00:25:45,884 --> 00:25:49,477
Let me take all 5 by 17 matrices
379
00:25:49,916 --> 00:25:52,176
and think about rank-4…
380
00:25:52,176 --> 00:25:55,921
The substrate of rank-4 matrices
381
00:25:55,921 --> 00:25:57,519
Let me...
I'll write this down
382
00:26:00,780 --> 00:26:04,640
You see, I'm...
I'm reviewing for the quiz actually
383
00:26:04,675 --> 00:26:07,953
Coz I am asking the kind of questions
that's are short enough
384
00:26:07,953 --> 00:26:08,976
but they are bring out
385
00:26:08,976 --> 00:26:11,573
Do you know what these words mean…
386
00:26:11,608 --> 00:26:20,991
So I pick my matrix space M now
it's all 5 by 17 matrices
387
00:26:24,815 --> 00:26:28,430
And now the question I ask is…
388
00:26:28,465 --> 00:26:35,424
The subset of rank-4 matrices
389
00:26:38,133 --> 00:26:39,897
Is that a subspace?
390
00:26:41,673 --> 00:26:43,686
If I have a matrix of…
391
00:26:43,721 --> 00:26:48,998
if I multiply a matrix of
rank-4 by a rank-4 or less thing
392
00:26:50,370 --> 00:26:53,046
Because I have to
let the 0-vector in
393
00:26:53,990 --> 00:26:56,424
Because it's going to be a subspace
394
00:26:56,425 --> 00:27:00,413
But that doesn't discuss
the rank-0 matrix got in there
395
00:27:00,448 --> 00:27:02,209
doesn't mean I have a subspace
396
00:27:03,805 --> 00:27:04,956
So if I...
397
00:27:04,991 --> 00:27:10,583
the question really comes down to
if I add 2 rank-4 matrices
398
00:27:11,195 --> 00:27:13,336
Is the sum rank-4?
399
00:27:16,521 --> 00:27:17,934
What do you think?
400
00:27:20,336 --> 00:27:22,131
No, not usually
401
00:27:22,525 --> 00:27:23,581
not usually
402
00:27:23,581 --> 00:27:27,696
If I add 2 rank-4 matrices
the sum is probably...
403
00:27:27,696 --> 00:27:29,470
What could I say about the sum?
404
00:27:30,102 --> 00:27:31,739
Well, actually…
405
00:27:33,269 --> 00:27:35,837
Well, the rank could be 5
406
00:27:38,168 --> 00:27:40,097
It's a general question if I say...
407
00:27:40,132 --> 00:27:47,240
The rank of A plus B can't be more than
rank of A plus rank of B
408
00:27:48,533 --> 00:27:50,498
So this was saying
by adding two of those
409
00:27:50,533 --> 00:27:52,179
the rank couldn't be more than 8
410
00:27:52,214 --> 00:27:55,895
But I know actually the rank
couldn't be as large as 8 anyway
411
00:27:55,930 --> 00:27:57,835
Well how big could the rank be?
412
00:27:58,491 --> 00:28:01,404
For the rank of the matrix in M
413
00:28:01,851 --> 00:28:03,690
Could be as large as 5
414
00:28:04,869 --> 00:28:08,181
So, they're all for natural ideas
415
00:28:08,216 --> 00:28:12,566
So, rank-4 matrices
or rank-1 matrices
416
00:28:13,179 --> 00:28:15,598
So, let me take just the rank-1
417
00:28:17,817 --> 00:28:20,451
Let me take the subset
of rank-1 matrices
418
00:28:20,486 --> 00:28:22,410
Is that a vector space?
419
00:28:22,982 --> 00:28:26,975
If I add the rank-1 matrix
to a rank-1 matrix
420
00:28:27,674 --> 00:28:30,635
No, it's most like we can have rank-2
421
00:28:30,670 --> 00:28:32,786
So this is...
So I'll just make that point
422
00:28:32,821 --> 00:28:36,459
not a subspace
423
00:28:39,667 --> 00:28:40,577
Ok
424
00:28:42,470 --> 00:28:45,213
Ok. Those are topics that I wanted to…
425
00:28:46,927 --> 00:28:50,893
Just fill out the previous lectures
426
00:28:51,547 --> 00:28:57,846
I'll have one more subspaces question
a more likely example
427
00:28:58,309 --> 00:29:02,586
Suppose I'm…
Let me put this example on this board
428
00:29:04,687 --> 00:29:07,315
Suppose I'm in R4
429
00:29:10,999 --> 00:29:16,809
So my typical vector in R4
has 4 components
430
00:29:16,844 --> 00:29:19,827
v1, v2, v3, and v4
431
00:29:23,085 --> 00:29:31,303
Suppose I take the subspace of vectors
whose components add to 0
432
00:29:31,812 --> 00:29:37,441
So, I'd like S be all v
433
00:29:37,442 --> 00:29:42,210
all vector v in 4-dimensional space
434
00:29:42,685 --> 00:29:51,446
With v1 + v2 + v3 + v4 = 0
435
00:29:54,841 --> 00:29:58,976
So I just want you to consider that
bunch of vectors
436
00:29:59,011 --> 00:30:01,401
Is it a subspace, first of all?
437
00:30:02,495 --> 00:30:04,235
It is a subspace
438
00:30:04,609 --> 00:30:07,873
It is a subspace.
How do we see that?
439
00:30:10,449 --> 00:30:12,064
It is a subspace
440
00:30:12,435 --> 00:30:14,789
Normally I could check…
441
00:30:14,824 --> 00:30:19,885
If I add 1 vector with those
components add to 0
442
00:30:19,920 --> 00:30:21,815
I multiply a vector by 6
443
00:30:22,256 --> 00:30:26,491
The components still add to 0
Just 6 time 2, 6 time 2
444
00:30:28,119 --> 00:30:31,289
If I had a couple a v and a w
and I add them
445
00:30:31,324 --> 00:30:33,434
The components still add to 0
446
00:30:33,469 --> 00:30:35,034
OK, it's a subspace
447
00:30:35,495 --> 00:30:38,119
What's the dimension of that subspace
448
00:30:38,154 --> 00:30:40,111
and what's the basis for that subspace?
449
00:30:41,023 --> 00:30:43,754
So you see I can just describe a space
450
00:30:44,549 --> 00:30:48,111
and we can ask for the dimension...
451
00:30:48,146 --> 00:30:51,627
Ask for the basis first
and the dimension
452
00:30:51,662 --> 00:30:57,121
For the dimension is the one that's
easy to come in by a single word
453
00:30:57,156 --> 00:31:00,508
What's the dimension of
our subspace S here?
454
00:31:04,048 --> 00:31:08,258
And the basis...
Tell me some vectors in it
455
00:31:10,127 --> 00:31:14,671
Oh, I'm going to make these axes again
to guess the dimension
456
00:31:15,373 --> 00:31:17,406
Again, I think I heard it…
457
00:31:17,441 --> 00:31:20,175
3! The dimension is 3
458
00:31:20,875 --> 00:31:27,194
How does it connect to our Ax = 0?
459
00:31:27,229 --> 00:31:29,767
Is this the nullspace or something?
460
00:31:29,802 --> 00:31:32,850
Is that the nullspace of a matrix
461
00:31:32,885 --> 00:31:35,941
and then we can look at the matrix
and...
462
00:31:35,976 --> 00:31:38,509
we know everything about
those subspaces
463
00:31:38,903 --> 00:31:41,684
This is the nullspace...
464
00:31:46,835 --> 00:31:49,198
of what matrix?
465
00:31:55,684 --> 00:32:01,701
What's the matrix
where the nullspace is the Av = 0?
466
00:32:01,736 --> 00:32:06,295
So I want this equation to be Av = 0
467
00:32:08,347 --> 00:32:10,497
v is now the vector
468
00:32:11,157 --> 00:32:14,335
and what's the matrix
that we're seeing here?
469
00:32:16,204 --> 00:32:22,545
It's the matrix of 4 1's
470
00:32:24,244 --> 00:32:26,330
Do you see the fact?
471
00:32:26,365 --> 00:32:32,352
That if I look at Av = 0
for this matrix of A, I multiply by b
472
00:32:32,387 --> 00:32:37,927
And I get this requirement
that its components add to 0
473
00:32:37,962 --> 00:32:40,953
So I'm really…
When I speak about this
474
00:32:42,246 --> 00:32:45,665
I'm seeking about the nullspace
of that matrix
475
00:32:45,700 --> 00:32:50,082
OK. Let's just say
we've got a matrix now
476
00:32:50,117 --> 00:32:52,143
We want its nullspace
477
00:32:53,046 --> 00:32:56,297
Well, tell me its rank first
478
00:32:56,332 --> 00:32:59,169
The rank of the matrix is
479
00:33:02,324 --> 00:33:05,308
1, thanks!
So r is 1
480
00:33:06,164 --> 00:33:10,220
What's the general formula for
the dimension of the nullspace?
481
00:33:10,255 --> 00:33:16,311
The dimension of the
nullspace of a matrix is
482
00:33:16,346 --> 00:33:20,640
In general, an n by n matrix of rank-r
483
00:33:21,410 --> 00:33:26,777
How many independent guys
in the nullspace?
484
00:33:29,387 --> 00:33:31,616
n - r , right?
485
00:33:32,287 --> 00:33:34,518
n - r
486
00:33:35,032 --> 00:33:40,338
In this case, n is 4
4 columns
487
00:33:40,373 --> 00:33:44,398
The rank is 1
so the nullspace is 3-dimensional
488
00:33:44,433 --> 00:33:48,694
So, of course
you could see it in this case
489
00:33:48,729 --> 00:33:50,919
But you can also see it here
490
00:33:50,954 --> 00:33:59,230
in our systematic way of dealing with
four fundamental subspaces of a matrix
491
00:34:00,811 --> 00:34:05,358
So, actually what are
all 4 subspaces then?
492
00:34:05,393 --> 00:34:10,519
The rowspace is clear
The rowspace is in R4
493
00:34:10,554 --> 00:34:15,928
Can we take the 4 fundamental
subspaces of this matrix?
494
00:34:15,963 --> 00:34:18,563
It's just a ** example
495
00:34:20,441 --> 00:34:23,701
The rowspace is one dimensional
496
00:34:24,742 --> 00:34:28,065
It's all multiple of that row
497
00:34:28,944 --> 00:34:31,700
The nullspace is 3 dimensional
498
00:34:31,735 --> 00:34:34,945
Oh, you'd better give me a basic
for the nullspace
499
00:34:35,378 --> 00:34:38,697
So, what's the basis for the nullspace
the special solution?
500
00:34:39,618 --> 00:34:43,698
To find a special solution
I look for the free variables
501
00:34:43,733 --> 00:34:47,450
The free variables here are…
there it is
502
00:34:48,845 --> 00:34:52,589
The free variables are 2, 3, and 4
503
00:34:52,624 --> 00:35:01,971
So the basis for S will be…
504
00:35:02,006 --> 00:35:05,405
I'm expecting 3 vectors
505
00:35:09,021 --> 00:35:10,871
3 special solutions
506
00:35:10,906 --> 00:35:15,700
I give the value 1 to that free variable
507
00:35:16,243 --> 00:35:19,425
and what's the pivot variable?
508
00:35:20,069 --> 00:35:23,503
If it is going to be a vector in S
509
00:35:24,562 --> 00:35:25,562
-1!
510
00:35:25,597 --> 00:35:29,372
Now we'll have the entries add to 0
511
00:35:29,407 --> 00:35:34,056
The second special solution has
the 1 in the second free variable
512
00:35:34,091 --> 00:35:37,051
And again a -1 to make it right
513
00:35:37,086 --> 00:35:40,450
The third one turns to 1
in the third free variable
514
00:35:40,485 --> 00:35:43,223
And again a -1 makes it right
515
00:35:44,126 --> 00:35:47,383
That's my answer. That's the answer
I would be looking for
516
00:35:49,097 --> 00:35:52,611
The...A basis for the subspace is…
517
00:35:53,116 --> 00:35:57,880
You will just list 3 vectors and those
would be the natural free at least
518
00:35:57,915 --> 00:36:01,865
Not the only possible free...
but the...the...
519
00:36:01,900 --> 00:36:04,223
those of the special three
520
00:36:04,932 --> 00:36:08,340
OK, tell me about the columnspace
521
00:36:09,015 --> 00:36:12,730
What's the columnspace
of this matrix A?
522
00:36:17,012 --> 00:36:22,988
So the columnspace is
the subspace of R1!
523
00:36:23,597 --> 00:36:27,404
Because n is only 1
the columns have only 1 component
524
00:36:27,439 --> 00:36:31,035
So the column space of S
the column space of A
525
00:36:31,735 --> 00:36:34,775
is somewhere in the space of R1
526
00:36:34,810 --> 00:36:38,990
Because we only have…
These columns are short
527
00:36:39,899 --> 00:36:43,020
And what is the columnspace actually?
528
00:36:46,007 --> 00:36:51,826
I just talking with these
words of what I'm doing
529
00:36:52,480 --> 00:36:57,963
The columnspace for that matrix is R1
530
00:36:57,998 --> 00:37:05,983
The columnspace for that matrix
is all multiples of that column
531
00:37:06,018 --> 00:37:07,603
And there is...
532
00:37:08,216 --> 00:37:11,075
And all multiples give you all of R1
533
00:37:13,267 --> 00:37:14,748
And what's the…
534
00:37:14,783 --> 00:37:23,286
The remaining fourth space
the nullspace of trans(A), is what?
535
00:37:27,449 --> 00:37:28,992
So we transpose A
536
00:37:31,820 --> 00:37:39,787
we look for combinations of the columns
now that gives 0 for trans(A)
537
00:37:39,788 --> 00:37:41,475
And thereinto
538
00:37:41,939 --> 00:37:43,181
The only thing...
539
00:37:43,216 --> 00:37:50,867
the only combination of these rows
to give the 0 row is 0 combination
540
00:37:51,421 --> 00:37:54,986
OK. So let's just check dimensions
541
00:37:57,053 --> 00:38:00,949
The nullspace has dimension 3
542
00:38:00,984 --> 00:38:03,353
The rowspace has dimension 1
543
00:38:03,388 --> 00:38:05,046
3 + 1 = 4
544
00:38:07,098 --> 00:38:09,673
The column space has dimension 1
545
00:38:09,708 --> 00:38:15,364
And what's the dimension of this
like smaller possible space
546
00:38:15,399 --> 00:38:18,924
What's the dimension of the zero-space?
547
00:38:18,959 --> 00:38:20,570
It's a subspace
548
00:38:23,255 --> 00:38:26,292
0! What else could it be?
I mean, let's...
549
00:38:26,327 --> 00:38:30,176
we have to take a reasonable answer
and the only reasonable answer is 0
550
00:38:30,211 --> 00:38:31,926
So, 1 + 0 gives...
551
00:38:31,961 --> 00:38:36,152
This was n
the number of columns
552
00:38:36,187 --> 00:38:39,296
And this is m
the number of rows
553
00:38:40,554 --> 00:38:43,092
And let me just say again
554
00:38:43,127 --> 00:38:47,784
then the subspace that has only 1 point
555
00:38:48,509 --> 00:38:51,820
That point is 0 dimensional, of course
556
00:38:52,943 --> 00:38:57,043
And the basis is empty
because the dimension is 0
557
00:38:57,078 --> 00:38:59,109
there couldn't be anybody in the basis
558
00:38:59,483 --> 00:39:05,907
So the basis of that smaller subspace
is the empty set
559
00:39:06,273 --> 00:39:09,604
And the number of members in
the empty set is zero
560
00:39:09,604 --> 00:39:11,332
So that's the dimension
561
00:39:11,332 --> 00:39:12,216
OK
562
00:39:13,299 --> 00:39:14,103
Good
563
00:39:14,138 --> 00:39:19,405
Now I have just 5 minutes
to tell you about…
564
00:39:20,345 --> 00:39:22,521
Well actually about some…
565
00:39:24,015 --> 00:39:25,535
Some...
566
00:39:25,570 --> 00:39:29,148
This is now the last topic of
the small world graph
567
00:39:29,183 --> 00:39:37,032
And leads into a lecture
about graph in linear algebra
568
00:39:37,491 --> 00:39:41,558
But let me tell you
in these last minutes
569
00:39:41,593 --> 00:39:43,856
The graph that I'm interested in
570
00:39:47,208 --> 00:39:49,175
It's the graph where…
571
00:39:49,210 --> 00:39:50,472
What is a graph?
572
00:39:50,507 --> 00:39:52,319
I'll tell you that first
573
00:39:52,354 --> 00:39:54,271
Ok, what's the graph?
574
00:39:57,099 --> 00:40:00,129
OK. This isn't calculus
575
00:40:00,164 --> 00:40:03,488
I'm not thinking of
like some sine curve
576
00:40:04,218 --> 00:40:08,003
The word graph is used
in a completely different way
577
00:40:08,038 --> 00:40:15,768
It's a set of...
a bunch of nodes, and edges
578
00:40:17,843 --> 00:40:19,918
Edges connecting the nodes
579
00:40:20,413 --> 00:40:25,162
So I have nodes like 5 nodes
580
00:40:26,226 --> 00:40:31,221
And edges, I'm putting some edges
putting through them all
581
00:40:31,922 --> 00:40:34,754
Well, let me put in a couple more
582
00:40:37,763 --> 00:40:43,368
There's a graph with
5 nodes and 6 edges
583
00:40:44,991 --> 00:40:50,918
And some 5 by 7 matrix is going to
tell us everything about that graph
584
00:40:51,473 --> 00:40:53,194
That we need that matrix
585
00:40:53,229 --> 00:40:56,378
so next time I'll tell you about
the question I'm interested in
586
00:40:56,808 --> 00:40:58,099
Suppose...
587
00:40:59,360 --> 00:41:04,804
Suppose the graph
doesn't just have 5 nodes
588
00:41:04,839 --> 00:41:06,450
Suppose every...
589
00:41:07,300 --> 00:41:10,884
Suppose every person
in this room is a node
590
00:41:13,699 --> 00:41:20,120
And suppose there's an edge between
2 nodes if those people are friends
591
00:41:21,636 --> 00:41:23,665
So I'll just describe the graph
592
00:41:24,363 --> 00:41:29,184
It's a pretty big graph
hundreds of nodes
593
00:41:29,219 --> 00:41:32,184
And I don't know
how many edges are in it
594
00:41:35,754 --> 00:41:37,520
There's an edge if you're friends
595
00:41:37,555 --> 00:41:41,114
So that's the graph for this class
596
00:41:41,149 --> 00:41:45,634
A similar graph
you could take for whole country
597
00:41:46,222 --> 00:41:53,072
So 260 million nodes
and edges between friends
598
00:41:54,039 --> 00:41:56,832
And the question for that graph is
599
00:41:58,922 --> 00:42:03,329
How many steps does it take
to get from anybody to anybody
600
00:42:06,851 --> 00:42:14,401
What's two people are furthest apart
in this friendship graph, say for the US
601
00:42:14,436 --> 00:42:18,181
By furthest apart I mean
the distance from…
602
00:42:19,787 --> 00:42:22,671
Well, I'll tell you
my distance to Clinton
603
00:42:23,451 --> 00:42:24,634
It's two
604
00:42:24,669 --> 00:42:29,012
I happened to go to college with
somebody who knows Clinton
605
00:42:29,047 --> 00:42:32,877
I don't know him
So, my distance to Clinton is not 1
606
00:42:32,912 --> 00:42:34,425
Because I don't
607
00:42:35,045 --> 00:42:37,569
I believe or not
don't know him
608
00:42:37,604 --> 00:42:43,325
But I know somebody who does
he's a senator, so actually knows him
609
00:42:43,326 --> 00:42:45,189
Ok, I don't know what your...
610
00:42:45,224 --> 00:42:47,286
Well, what's your distance to Clinton?
611
00:42:50,051 --> 00:42:51,878
Well, it's not more than 3, right?
612
00:42:51,913 --> 00:42:53,363
Actually 2!
613
00:42:53,918 --> 00:42:59,845
You know me, I take credit for
reducing your distance and distance…
614
00:43:01,623 --> 00:43:04,037
What's the distance to Monica?
615
00:43:10,011 --> 00:43:13,998
Anybody belows 4 is in trouble here…
616
00:43:14,931 --> 00:43:17,321
Oh, maybe 3, but...
617
00:43:17,746 --> 00:43:20,840
Right
So...
618
00:43:23,433 --> 00:43:28,923
what's Hillary's distance from me…
I don't think...
619
00:43:30,207 --> 00:43:34,941
Maybe 1 or 2, I guess…
Is that right?
620
00:43:35,566 --> 00:43:40,229
Well we won't think more about that
621
00:43:40,264 --> 00:43:44,301
So, actually
the real question in this
622
00:43:45,619 --> 00:43:48,906
What're the largest distance?
623
00:43:48,941 --> 00:43:52,325
How far apart could
people be separated?
624
00:43:52,962 --> 00:43:58,603
And roughly, this number 6, the degree
of separation, this kind of...
625
00:43:58,638 --> 00:44:00,966
appeared a the movie title
as a book title
626
00:44:01,001 --> 00:44:04,087
and it's with this meaning
that...
627
00:44:04,122 --> 00:44:05,860
Roughly speaking
628
00:44:07,182 --> 00:44:11,999
6 might be a very…
not too many people
629
00:44:12,562 --> 00:44:15,564
If you just met somebody in an airplane
630
00:44:16,793 --> 00:44:18,499
You get to talking to them
631
00:44:18,999 --> 00:44:22,116
You begin to discuss mutual friends
632
00:44:22,151 --> 00:44:26,535
Sort of find out…
OK, what connections do you have
633
00:44:26,570 --> 00:44:32,236
And very often, you will find
you're connected in by 2 or 3 or 4 steps
634
00:44:32,890 --> 00:44:35,185
And you will remark it's a small world
635
00:44:35,220 --> 00:44:38,867
And that tells an expression
small world, very often
636
00:44:39,946 --> 00:44:42,720
But 6, I don't know...
if you took 6
637
00:44:42,755 --> 00:44:46,281
I don't know if you would
successfully discover those 6
638
00:44:46,316 --> 00:44:48,289
in an airplane conversation
639
00:44:48,248 --> 00:44:53,984
But here's my last question
and I'll leave it for the next lecture 12
640
00:44:53,984 --> 00:44:56,797
And do a lot in linear algebra
in lecture 12
641
00:44:56,832 --> 00:44:59,263
But the que...the...
642
00:45:00,403 --> 00:45:03,947
The interesting point is
that with a few shortcuts
643
00:45:05,678 --> 00:45:09,124
The distances come down dramatically
644
00:45:11,603 --> 00:45:16,057
I mean all your distance to Clinton
immediately dropped to 3
645
00:45:16,092 --> 00:45:18,128
by taking linear algebra
646
00:45:18,163 --> 00:45:21,713
That's like an extra bonus
for taking linear algebra
647
00:45:22,733 --> 00:45:26,011
And to understand mathematically
648
00:45:26,046 --> 00:45:29,036
What it is about these graphs
649
00:45:29,071 --> 00:45:32,469
We'd like to graph of
the World Wide Web
650
00:45:33,170 --> 00:45:34,681
There's a fantastic graph
651
00:45:34,716 --> 00:45:38,703
So many people would like to
understand a model, the web
652
00:45:39,178 --> 00:45:41,809
What are the edges of the links
653
00:45:42,389 --> 00:45:47,189
and the nodes are sites, websites
654
00:45:49,023 --> 00:45:51,647
I'll leave you what's that graph
and see…
655
00:45:51,682 --> 00:45:54,254
Have a good weekend
and see you on Monday!
Last Modified 3/30/08 4:37 AM
|
