02. Multiplying and Factoring Matrices
2.71M subscribers
SUBSCRIBED
MIT 18.065 Matrix Methods in Data Analysis, Signal Processing, and Machine Learning, Spring 2018 Instructor: Gilbert Strang View the complete course: https://ocw.mit.edu/18-065S18YouTube Playlist: https://www.youtube.com/playlist?list...Multiplying and factoring matrices are the topics of this lecture. Professor Strang reviews multiplying columns by rows: AB = sum of rank one matrices. He also introduces the five most important factorizations. License: Creative Commons BY-NC-SA More information at https://ocw.mit.edu/termsMore courses at https://ocw.mit.edu
00:00
00:01
The following content is provided under a Creative
00:03
Commons license.
00:05
Your support will help MIT OpenCourseWare
00:07
continue to offer high quality educational resources for free.
00:11
To make a donation, or to view additional materials
00:14
from hundreds of MIT courses, visit MIT OpenCourseWare
00:18
at ocw.mit.edu.
00:19
00:22
PROFESSOR: So, are we ready to go?
00:24
Any questions on 18065?
00:28
So it will be, as I said before, a mixture of linear algebra
00:34
and math questions, along with online using the material.
00:42
OK.
00:43
So I'm, in this first week or two,
00:47
reviewing the highlights of linear algebra.
00:51
And I've reached this point, to remember--
00:59
well, so we--
01:00
I just said two words about multiplying matrices
01:07
by using column times row as a way to do it.
01:12
And now, I want to illustrate that
01:16
by the five key factorizations of matrices.
01:23
OK.
01:24
So what are they?
01:25
And do you recognize them?
01:28
Everybody uses those letters.
01:29
In fact, some of those letters, like LU or QR,
01:33
would be the most used MATLAB commands in linear algebra.
01:38
So a A equal LU of, maybe--
01:42
say something I'll develop today--
01:44
but it's about elimination.
01:46
01:54
Solving linear systems.
01:57
So that's always the start of a linear algebra course.
02:00
But it will go fast here.
02:03
I just want to show you a different way
02:05
they get to L times U-- lower triangular
02:09
times upper triangular.
02:11
Probably you've seen that--
02:13
those triangular matrices.
02:16
So do you know what QR is?
02:18
What's QR about?
02:21
AUDIENCE: Least squares?
02:23
PROFESSOR: Least squares is the big application,
02:26
the factorization.
02:28
So what kind of a matrix gets that letter Q?
02:31
AUDIENCE: Orthogonal?
02:32
PROFESSOR: Orthogonal.
02:33
The columns are orthogonal.
02:35
Often orthonormal.
02:37
So orthogonal means they're perpendicular to each other.
02:40
And orthonormal means they're unit vectors.
02:44
So that is-- so Q often represents a matrix
02:52
with orthonormal columns.
02:55
So you-- we could say Gram-Schmidt,
02:58
if you want to remember a couple of old timers
03:06
whose algorithm produces Q and R.
03:13
How about this one?
03:14
This is really a central one in math--
03:18
pure math, applied math, everywhere-- applications.
03:21
So S stands for symmetric.
03:24
So this is a special factorization
03:26
for symmetric matrices.
03:29
And you can see that it's symmetric.
03:31
This lambda is the diagonal eigenvalue matrix--
03:35
always lambda for eigenvalues.
03:38
Q is like that Q--
03:41
different Q, of course.
03:43
That Q you can find just straight forward
03:46
from Gram-Schmidt.
03:48
This Q has the eigenvectors.
03:52
So you don't find eigenvectors without some extra work.
03:55
OK.
03:56
So that's eigenvectors.
03:58
Yeah.
03:58
So that would be worth expanding.
04:04
So here are the eigenvectors of the matrix S--
04:08
n of them, normalized.
04:11
Here are the eigenvalues lambda 1 to lambda n.
04:15
And here are the eigenvectors now transposed.
04:19
04:25
So remind me of the great fact about--
04:29
two facts, I guess-- one fact about the eigenvalues
04:32
and one fact about eigenvectors.
04:34
This is an important fact statement in linear algebra.
04:41
What do we know about the eigenvectors?
04:44
Oh well, I guess I've given it away.
04:46
The eigenvectors are orthogonal.
04:50
That's very important.
04:52
Makes some matrices-- well, they're beautiful matrices.
04:55
They're the kings of linear algebra.
04:59
Qs are the queens, in my opinion.
05:01
Orthogonal matrices are the queens,
05:03
and symmetric matrices are the kings.
05:06
So these are orthonormal eigenvectors.
05:12
And the key point--
05:14
an important point that's implicit
05:16
here-- is, there are n of them.
05:19
There is a complete set.
05:20
The matrix can be diagonalized.
05:23
And those-- well, what's special about the eigenvalues?
05:28
Other matrices could be Q lambda Q transpose.
05:32
But symmetric matrices are something additional
05:35
about lambda.
05:36
AUDIENCE: They're all real?
05:37
PROFESSOR: They're all real.
05:39
So eigenvalues are real.
05:41
And eigenvectors are orthonormal--
05:45
can be chosen orthonormal-- can be chosen,
05:48
I guess I have to say.
05:49
OK.
05:50
Good.
05:50
Good.
05:51
Good.
05:51
Oh, now maybe I'll use that as an example
05:54
of matrix multiplication.
05:57
So let me just do that here.
05:59
Simple matrix multiplication, but it makes the point.
06:03
So Q lambda Q transpose.
06:08
06:10
OK.
06:11
Well, what was my point about matrix multiplication?
06:15
Let me-- it really involved two matrices.
06:20
Here, I unfortunately have three.
06:21
So I'm going to have to squeeze lambda in with one of the Qs,
06:25
to see it nicely as two matrices.
06:28
Shall I just do that?
06:30
Yeah.
06:32
Now I've made it two matrices.
06:33
That was easy.
06:35
OK.
06:36
Now what's the rule?
06:38
In the first notes, this was A and this was B.
06:43
And when you multiply two matrices,
06:45
the rule is, this is columns of Q lambda times
06:54
rows of Q transpose.
06:59
I'm multiplying columns by rows.
07:02
And so it's a column vector times a row vector,
07:07
and that gives us a matrix.
07:09
So each-- and it's a special matrix.
07:13
So this is our column.
07:14
This is a row.
07:16
And when I multiply n by 1 times 1 by n, I get an n by n matrix.
07:22
And it's pretty special.
07:24
And what is the special fact about I'm
07:27
sort of recalling from last time.
07:29
What's special about a column times a row?
07:32
It's rank is special.
07:34
It's rank is 1.
07:36
It's column space-- well, the only column around is this one.
07:42
So all columns are multiples of this guy.
07:46
All rows are multiples of this guy,
07:50
as we could see from an example.
07:52
Shall I just do an example?
07:54
1, 2 times 3, 4, to take a random example.
08:00
So that would give us 3, 4, 6, 8.
08:05
And sure enough, the columns are multiples of 1, 2.
08:10
The rows are multiples of 3, 4.
08:13
And the rank is 1.
08:16
OK.
08:17
So those are the building blocks.
08:19
Now I want to build something.
08:21
So here we go.
08:22
08:25
So this is a sum of rank 1.
08:27
Sum of rank 1.
08:33
Sum of column times row.
08:36
So I take column 1 times row 1.
08:40
That's my first thing in the sum.
08:42
So column 1 of that.
08:43
So you see I had to sneak the lambda
08:46
to have just two factors.
08:50
So what's column 1 of Q lambda?
08:52
That's a good question.
08:54
So column 1 of Q is Q1--
08:59
the first eigenvector.
09:01
But now, I am multiplying by this diagonal matrix.
09:05
Do you see in your mind what's the first column of Q lambda?
09:09
09:12
Just think about that a second.
09:15
So here's-- we can steal any little corner for a matrix.
09:23
So here's q1, and the rest of the columns.
09:27
And then here is lambda 1.
09:31
And that's Q lambda.
09:32
So I'm putting those together.
09:34
And I'm asking, what's the first column of the answer?
09:38
Can you see how that works?
09:41
AUDIENCE: q1 lambda 1?
09:42
PROFESSOR: It's... sorry?.
09:43
AUDIENCE: q1 lambda 1?
09:44
PROFESSOR: q1 lambda 1.
09:45
Exactly.
09:46
That lambda 1 will multiply q1.
09:49
These other lambdas multiplied later columns.
09:52
So the first column is lambda 1 times q1.
09:54
Right.
09:55
So it's the first guy, lambda 1, q1.
10:00
And then the first row of this will be q1 transpose.
10:06
That's the first guy in our sum of n things.
10:11
And let me put the next one and the last one.
10:14
Lambda 2, q2, q2 transpose.
10:20
And lambda n, qn, qn transpose.
10:25
10:29
That's really a nice right way to write
10:33
to breakup the product, q lambda q transpose.
10:39
This is called the spectral theorem.
10:41
So that's the symmetric-- that's S. That's S there, is that.
10:47
So that's-- we've broken up S into rank 1 pieces.
10:53
That's like a constant theme.
10:57
And these rank 1 pieces are quite special because they're
11:01
symmetric.
11:02
Q1q1 transpose will be symmetric.
11:05
And oh, so can we--
11:09
so let's just-- I follow the rule for multiplying matrices.
11:14
But maybe I could just check that it's the right thing--
11:19
that it came out right.
11:22
So what do I mean by checking?
11:23
I guess I'll just check about S times q1.
11:28
So look at S--
11:33
this thing-- times the first eigenvector, and what do I get?
11:38
OK.
11:39
So you'll like this.
11:43
I've split up S into a sum of rank 1 pieces.
11:47
And that splitting is--
11:48
you see it all over.
11:52
It's really showing you what the pieces of the symmetric matrix
11:56
are.
11:57
And now I'm just going to check that that's
11:59
a correct formula for S, so I'll multiply it by q1.
12:04
And I'm hoping to get the right thing.
12:06
And what do I actually get?
12:08
If I multiply this whole business times q1,
12:14
I get lambda 1, q1, q1 transpose--
12:20
that's the first guy times my q1--
12:23
plus-- right?
12:26
I'm multiplying S by q1, and this first term gave me that.
12:31
And what does the next term give me?
12:33
Put me out of my misery here.
12:37
I'm looking for this thing to simplify like mad.
12:40
OK.
12:40
So what's the second term?
12:42
When I multiply this guy by q1, what do I get?
12:47
AUDIENCE: Zero.
12:48
PROFESSOR: Zero.
12:49
That's right.
12:50
That's what we want.
12:52
And when I multiply the last guy by q1,
12:56
I get zero, because the qs are orthogonal.
13:01
So this is all I get.
13:03
And then-- so, I don't need this plus anymore.
13:05
That's it.
13:07
And then what can I do to improve
13:10
that little somewhat repetitive formula for the answer?
13:18
What do I want to do finally?
13:19
I want to remember that the qs are normalized.
13:23
They're unit vectors.
13:25
So what does that tell me here?
13:26
AUDIENCE: Q1 transpose.
13:27
PROFESSOR: Q1 transpose times q1.
13:30
This is just 1.
13:34
It's-- that's what normalized means--
13:38
that the length squared is the length--
13:41
the length of the vector squared.
13:44
And it's 1.
13:45
So I can cancel that term.
13:48
And I'm getting the right answer.
13:50
That's all-- that's all this was about.
13:53
I was just checking and wanted to see how it would fall out.
13:59
And it falls right out that this formula
14:05
is the correct matrix S, because it's
14:08
got the right eigenvectors, qs.
14:11
And it's got the right eigenvalues lambdas.
14:13
So it's gotta be the right matrix S. Is that OK?
14:18
That's like a first example to see how this--
14:24
14:28
splitting into rank 1s--
14:31
gives you back what you expect easily enough.
14:35
It gives you the information you expect.
14:38
OK.
14:38
So that's the symmetric eigenvalue picture
14:43
for symmetric matrices.
14:45
And we'll see it again.
14:47
It's-- well, all five of these are big, are important.
14:54
I don't know if you know this one,
14:56
but it's going to be a foundational factorization
15:02
for this course and for all of data science.
15:05
Do you know its name?
15:07
So, what does it mean, first of all?
15:09
Just a comment on this, and then we'll
15:12
save it for a couple of weeks.
15:15
So this view is actually an orthogonal matrix.
15:19
And so is V. So it has two orthogonal matrices.
15:23
So that's why people call them U and V
15:27
rather than Q1 and Q2, which was too much to get subscript.
15:33
So orthogonal times diagonal times orthogonal.
15:37
And we'd say, orthogonal, diagonal, orthogonal.
15:45
And 18.06 would, as of now, reach this topic
15:51
because it's jumped up in importance.
15:54
And it's called?
15:55
AUDIENCE: Singular value decomposition.
15:57
PROFESSOR: Singular value decomposition.
16:00
Well, those are long words, so everybody calls it the SVD--
16:04
the singular value decomposition.
16:07
The point is it works for every matrix--
16:15
rectangular matrices.
16:16
There's no issue of, does it have
16:18
enough eigenvectors or not?
16:21
That's an issue here.
16:23
Well, it's an issue here.
16:25
Not every matrix has got enough eigenvectors to make that work.
16:29
Every matrix that one works because instead
16:35
of one set of vectors it's got two
16:39
matrices-- two different sets of singular vectors.
16:45
Oh, we'll see that.
16:47
That's important.
16:50
OK.
16:51
So that's really a quick overview
16:55
of fundamental factorizations.
16:59
And I'd like to say just another word about elimination,
17:03
A equal LU, and then we'll leave it alone.
17:09
So elimination.
17:11
Yeah.
17:12
Do you remember that first beginning of linear algebra,
17:20
when you're solving ax equal b?
17:22
You do these row operations.
17:24
Can I just-- what I want to say is, all those row operations
17:28
that you do are perfectly expressed by L times U.
17:35
And so that's a key point in 18.06,
17:40
but I have a different way to look at it.
17:42
So that's what I wanted to show you.
17:44
I have a--
17:45
I want to show you a sum of rank 1's, or row times column.
17:51
It fits in today.
17:53
So I'd just like to see, why does a matrix invertible--
18:02
this is a square matrix, now invertible.
18:05
And it factors-- if all goes well with elimination
18:11
and the pivots are non-zero--
18:13
it factors into lower triangular times upper triangular.
18:17
So that's a key step that is--
18:20
that MATLAB would do with a lu of A--
18:23
would produce those two factors.
18:24
18:28
Now I want to do them in a column times row
18:32
way, which I just realized late, was a neat way to do it.
18:39
So can I take a matrix and do elimination?
18:47
How big a matrix shall I take?
18:51
2 by 2 [INAUDIBLE].
18:55
3 by 3 Somebody's not convinced totally by 2 by 2
18:59
Let me do it 2 by 2 and then if you want-- if you really
19:01
want a 3 by 3 do it.
19:05
OK.
19:05
Here's 2 by 2 2, 4, 3, 7.
19:11
How's that?
19:13
OK.
19:14
19:17
So what is-- yeah.
19:18
So let's remember what elimination does.
19:23
It subtracts a multiple of that row from that one,
19:31
to get to 2, 3.
19:34
And the multiple is 2.
19:35
So it knocks out the 4.
19:37
Two 3's are 6.
19:39
So it leaves a 1.
19:40
And we're-- oh, yeah.
19:42
Thanks for allowing me to do 2 by 2.
19:44
I've already done it now.
19:46
I've reached U. So here's A. And here's U--
19:50
the upper triangular guy with the pivots on the diagonal.
19:54
19:56
And then the question is, express
20:01
that step in matrix language.
20:05
And the right answer is l times U. So the right answer
20:10
is that this A is--
20:14
so I'll just erase that letter U--
20:18
is l times U. So what is l?
20:23
L is the lower triangular guy.
20:26
And it has there the number that you used here.
20:31
And what was that?
20:32
I subtracted 2 of that row from this.
20:35
So I want a 2 there.
20:37
20:44
So that would be--
20:46
I would call that a multiplier.
20:48
I multiplied row 1 by 2.
20:50
Subtracted to get that 0.
20:53
And for a 2 by 2 example, I was finished.
20:57
OK.
20:57
Now I want to see this--
21:00
so there is l times U. It happened.
21:02
Right.
21:04
I would like to see how l times U comes out of this row--
21:10
column times row.
21:12
So let me start--
21:14
let me think again.
21:15
21:20
So really the point of elimination--
21:23
why did we do this in the first place?
21:26
Because here we had two coupled equations.
21:30
There were coupled together.
21:31
We couldn't solve them instantly.
21:33
That step of elimination reduced me to--
21:38
down here in this corner--
21:39
one equation, that I've eliminated the first unknown x
21:44
from the second equation.
21:47
So the second equation is 0x plus 1y equal right hand side.
21:52
And I solve it immediately.
21:54
OK.
21:55
So how did I get to that 1 by 1 problem,
22:01
with these guys removed?
22:03
Well-- yeah.
22:06
I'll just write-- can I write here the--
22:09
my parallel way to think of it?
22:13
2 by 2 is pretty small, I admit.
22:15
OK.
22:16
So I start with 2, 3, 4, 7.
22:19
22:22
I want to split it into--
22:24
I want to get the first row and column in one piece.
22:30
Something goes there.
22:32
And the other piece is something there.
22:38
OK.
22:40
That's what elimination has done.
22:42
It's taken the original matrix.
22:45
It's split-- these are both rank 1.
22:47
22:54
So let's just-- first of all, you
22:56
could tell me what goes in that blank space in the first rank 1
23:01
matrix.
23:01
So what-- can I say this in words?
23:05
The first stage of elimination pulls off from A--
23:11
so A is some big matrix.
23:14
It pulls off from A. It takes account of the first column
23:19
and row.
23:20
So it writes A as--
23:25
here we go-- as a first column, say column
23:33
1, row 1, plus the easy part.
23:40
The easy part will be a matrix with all zeros there--
23:45
all zeros there.
23:47
And here I have a 2.
23:49
Can I call it a 2?
23:51
This is my way now to think about what
23:56
elimination is really doing.
23:58
It's starting with an n by n matrix.
24:01
It's pulling off a rank 1 matrix,
24:04
which gets that column and that row correct.
24:09
And it gets whatever it has in here.
24:11
And then the rest of what's in there is A2.
24:16
Do you see that we've done that here?
24:19
The first step got the first row and column correct.
24:23
And if it's rank 1, what number goes there?
24:25
AUDIENCE: 6.
24:26
PROFESSOR: 6.
24:27
6 for there.
24:29
And then this is the rest.
24:31
This is what we have, one size smaller to work on.
24:35
And it looks like it was 7.
24:38
6 has been used.
24:39
So it's a 1.
24:40
24:43
That's really-- I want to think of this rank 1 matrix
24:52
as the first column of l times the first row of u.
24:58
And then this guy is the second column
25:01
of l times the second row of u.
25:05
25:11
OK.
25:13
I haven't presented as proof in a class before.
25:17
25:20
And for 2 by 2, it's looking like overkill to me.
25:23
I mean, why?
25:24
You don't have to do all that deep thinking
25:26
to get the pieces.
25:29
But my idea is that it gives the breakdown.
25:35
And this, of course, is, by our column times
25:39
row rule, that's LU.
25:43
So we're starting with A, and we're breaking it up into LU,
25:48
where lu--
25:49
the first piece of lu--
25:52
is the first column times row.
25:55
And then the next pieces are the rest of the matrix.
26:01
And those get broken down-- the next stage of elimination would
26:06
break--
26:07
if I had a 3 by 3, this stage peeled off
26:10
the first column and row--
26:12
then the next stage would peel off the second--
26:15
the new second column and row.
26:17
And the third stage would have the third column and row--
26:21
just the last pivot does this make any sense to you?
26:25
You could email me and say it's not that great.
26:30
But I think it's--
26:32
to see that the final result of elimination is l times u is--
26:39
there's a little magic in seeing what you're doing.
26:45
And I think this is a way to see what you're doing--
26:48
that you're peeling off a first part
26:52
to leave a second part like that.
26:55
Then the second part, you would peel off
26:58
the second column times the second row,
27:01
maybe divide by the pivot to make it correct.
27:05
And that would put something in the rest of the box.
27:09
And then A3 would be the rest of that box.
27:14
OK.
27:15
I'm stopping here.
27:17
I'm glad you let me do 2 by 2, since I see that 3 by 3
27:23
would have ruined the day.
27:24
Yeah.
27:25
OK.
27:26
A question, or let me pause for a minute.
27:30
So I've talked about these factorizations.
27:35
This one we won't see again.
27:38
This one we will see, big time.
27:41
And this one we will.
27:43
And this one we will.
27:44
Yeah.
27:46
2, 3 and 5 are the ones that we're really
27:49
going to see a lot of.
27:51
Questions or thoughts or--
27:54
OK.
27:55
I guess I want to tell you now to complete today's--
28:00
moving forward in this subject--
28:03
the fundamental theorem of linear algebra--
28:06
the fundamental theorem of linear algebra.
28:08
OK.
28:08
Ready for that?
28:10
Or you may have seen it already, because it's
28:13
like the highlight of this subject--
28:17
of the basic ideas in this subject.
28:21
Right.
28:22
And then maybe I can--
28:23
after I tell you that theorem--
28:25
28:28
people around the world send me homework problems to do.
28:32
Now, you would think any sensible professor would never
28:35
do those problems.
28:37
He would say, it's your problem.
28:39
But I get carried away and I solve them sometimes.
28:43
So one came from India last week,
28:47
and it involved the fundamental theorem of linear algebra.
28:50
Whoever teaching it there really was on the ball.
28:53
And well, I'll tell you that problem
28:56
after the fundamental theorem.
29:00
OK.
29:00
Fundamental theorem.
29:01
29:06
It's about four sub spaces.
29:09
So I invented the name four fundamental sub spaces.
29:13
So can I list the four sub places?
29:16
Fundamental sub spaces.
29:20
Well, we know one of them already.
29:23
The column space-- so, for a matrix.
29:29
We are given a matrix A--
29:32
that's m by n of rank r.
29:35
29:37
That's our normal starting point.
29:39
29:43
So what are those four sub spaces,
29:45
and how are they related?
29:46
And what's their dimension?
29:47
And what-- those are key facts.
29:51
OK.
29:52
We already know the column space--
29:54
29:59
column space of a matrix.
30:02
And actually, we already know the row space of a matrix.
30:07
And we have the notation for that,
30:09
column space of A transpose.
30:13
And what is the dimension--
30:16
so that was the key point in the first lecture.
30:18
Anybody who missed the first lecture,
30:20
should go back to the notes of 1.1
30:28
for the thinking that goes into the dimension equals what?
30:36
Which of those three numbers do I want to--
30:39
is the dimension of the column space?
30:42
R. And what can I say about r, right away,
30:46
compared to m and n?
30:47
AUDIENCE: [INAUDIBLE].
30:49
PROFESSOR: Yeah.
30:50
Less or equal.
30:52
r couldn't-- I couldn't have more independent columns than I
30:57
have columns.
30:58
So I've got n columns.
31:01
So r of them are independent.
31:04
So r is somewhere, less or equal-- hopefully equal to n.
31:09
What about the dimension of the row space?
31:11
How many independent rows has the matrix got?
31:15
AUDIENCE: R.
31:15
PROFESSOR: R. Thank you.
31:16
That's the great fact with a new proof last time
31:23
in section 1.1--
31:26
that those have the same dimension, same dimension.
31:30
Which is-- you think, oh, OK.
31:33
You look at a simple example.
31:35
It's true.
31:36
But if you're given a matrix that's 50 by 100,
31:42
really the fact that those 100 columns
31:46
have the same number of independent ones as those 50
31:50
row--
31:51
that's like great.
31:53
OK.
31:54
Now the other spaces are the null space
31:59
of the matrix, N of A.
32:03
And just to make everything naturally symmetric,
32:07
the null space of A transpose.
32:11
32:14
Those are the last two.
32:16
Those are the four fundamental sub spaces, which you've seen.
32:21
And they're even on the cover of the linear algebra textbook.
32:25
OK.
32:26
So what's the null space?
32:28
AUDIENCE: It's the set of [INAUDIBLE]..
32:30
PROFESSOR: It's the set of solutions to Ax
32:32
equals 0, right.
32:34
Null space is all solutions to Ax equal 0.
32:48
So the null space has vector--
32:50
these vectors in it-- the x's.
32:51
32:54
The null space isn't taken from the matrix.
32:57
The row space and the column space-- those numbers
33:01
are sitting in the matrix.
33:03
The null space, and the null space of A transpose,
33:07
are solutions to--
33:09
the word null is reflecting the fact that that's a 0.
33:14
And that's what makes it a space.
33:16
Now can you just--
33:18
let me just ask you to think again.
33:20
What's implied when I say--
33:23
when I use the word space--
33:25
a space of vectors?
33:27
AUDIENCE: Closed under addition--
33:29
PROFESSOR: I can add--
33:30
yeah.
33:31
So I can do the most important operations of linear algebra
33:37
in that space.
33:39
I can add two vectors.
33:41
Here, let me just add them.
33:42
So here I'll have a vector x, and let
33:45
me say another one, a vector y.
33:49
Then, I do addition.
33:53
I follow the rules.
33:54
I see that this can be written as Ax plus y is 0 plus 0.
34:00
So what have I learned?
34:03
I've learned that if x is in the null space,
34:07
and y is in the null space, then x plus y.
34:10
So the null space is, as you said, closed,
34:13
meaning I don't go outside it.
34:16
If x is in it, and y is in it, then the sum is in it.
34:19
And similarly, from Ax equals 0, I get to A times cx equals 0.
34:27
Just multiply by c-- by a number c.
34:31
So those two facts--
34:33
that means I can do linear algebra.
34:37
I can multiply by numbers.
34:39
And I can add.
34:40
In other words, I can take linear combinations.
34:44
That's what you do with vectors.
34:46
And the point is, if I do it--
34:48
if I take combinations of two null space guys,
34:52
I'm still in the null space.
34:55
OK.
34:56
So that's the point of the null space.
35:01
And-- well now-- so now part of the fundamental theorem
35:06
is to figure out how many independent vectors are
35:11
in the null space.
35:12
How many solutions-- independent solutions--
35:16
does that system of equations have?
35:19
So that would be the dimension.
35:21
And I have to ask you what it is.
35:25
Let me draw a picture, while you're
35:27
thinking about those spaces.
35:29
35:32
It's fantastic to have these beautiful clean boards.
35:35
OK.
35:36
So here's my picture of the row space.
35:39
35:43
Row-- that's the column space of A transpose.
35:48
And here's my picture of the null space, N of A.
35:58
And that's the solutions to Ax equals 0.
36:01
36:03
And why have I put these two together,
36:06
and these two together?
36:08
So-- and the other pair will be the column space, C of A.
36:17
and the null space of A transpose.
36:26
So there are the four spaces.
36:27
36:29
Their relationship is the fundamental theorem
36:33
of linear algebra.
36:35
So first of all, what--
36:40
so I have an m by n matrix.
36:42
36:45
So that tells me that my row--
36:48
a typical row has n components, right?
36:51
I look at an m by n matrix.
36:53
Let's do a 2 by 3 matrix.
36:55
37:00
So if I look at the row space, this is m.
37:04
And this is n.
37:06
So I see three--
37:08
the rows have length three.
37:12
And of course, they multiply the x's,
37:14
which also have the length three, x1, x2, x3.
37:19
That's why these are together, because they're
37:21
both in n dimensional space.
37:23
37:29
Then why are these together?
37:31
Because the columns are in two dimensional space,
37:36
for this example.
37:38
And the null space of A transpose
37:41
would be just two components, like y1 and y2, to give 0s.
37:49
So do you see that this is R--
37:51
these guys are in Rn?
37:54
So that's the first--
37:56
get things straight.
37:58
Two spaces in Rn, two spaces in Rm.
38:02
38:08
Now, what am I going to ask about these spaces?
38:12
I guess I've already started asking
38:14
and didn't wait for an answer.
38:16
Their dimension.
38:18
So this has dimension R. And what's the dimension--
38:24
how many-- this is really such a key fact.
38:31
If I have m equations, Ax equals 0.
38:37
And if R of those equations are independent,
38:41
how many solutions?
38:43
So the dimension of this space is
38:45
going to tell me how many solutions
38:48
to Ax in two m equations, but really
38:53
only are genuine independent equations in this system Ax
39:02
equals 0.
39:03
How many?
39:04
So can I ask the question again?
39:06
And I want the answer in terms of m, and n, and R. So I have--
39:12
I really have R equations.
39:15
If I look at Ax equals 0, it looks
39:17
like m separate equations.
39:19
But m minus R--
39:23
of those-- are just copies or combinations of others.
39:27
So there are independent equations.
39:30
So what's-- how many have I got?
39:32
AUDIENCE: [INAUDIBLE].
39:35
PROFESSOR: And And that's what I'm going to write in here.
39:37
39:40
So-- yeah.
39:41
So x has n components.
39:45
And there are real active equations
39:51
that they have to satisfy.
39:53
And that leaves n minus R. That's the key point.
39:58
That's the key point that there are n components of x--
40:04
n unknowns-- n unknowns.
40:07
And there are R constraints--
40:11
independent constraints.
40:13
So those n get--
40:16
if I want to satisfy those constraints that knocks out
40:19
dimension R, and leaves n minus R. So that's
40:23
the dimension here.
40:23
40:26
And the beauty of the count is that those two numbers add up
40:31
to n.
40:33
Everybody's accounted for.
40:35
Every vector has a piece in the row space
40:39
and a piece and the null space.
40:41
And that's-- those two pieces give you back the vector.
40:47
Do you see that?
40:48
That's just nice, that the numbers come out right.
40:51
And of course, they come out right here, too.
40:54
You could say, just transpose the matrix
40:57
and write it-- write the same thing again.
40:59
What's the dimension of the column space?
41:01
41:05
Equals?
41:06
The other column space in the matrix has dimension--
41:08
AUDIENCE: R.
41:09
PROFESSOR: R. Right.
41:11
And the row-- this guy is left out of some linear algebra
41:15
books, as if it doesn't belong.
41:18
But isn't it clear that without it, everything
41:23
is only three quarters done?
41:28
We have to have this guy.
41:29
And its dimension is
41:32
AUDIENCE: M minus R.
41:34
PROFESSOR: M minus R. Yeah.
41:37
That count is just, for A transpose, what
41:41
this count was for A. Yeah.
41:44
So we've got those dimensions, R and n minus R, R and m
41:50
minus R. Yeah.
41:51
41:54
You'll have known this, but we need
41:57
to see it once again in 2018, before we start using it.
42:05
Now is that the fundamental theorem?
42:06
Is that all to it there is?
42:10
No.
42:12
There is another piece to the fundamental theorem,
42:14
which is, sort of you could say, the geometry.
42:19
Here I have a sub space.
42:20
Here I have a subspace of this big n dimensional space.
42:26
So I visualize those sub spaces as some kind of a plane--
42:31
an R dimensional plane- and an n minus R dimensional plane.
42:36
And I want to see how are those two planes connected.
42:41
How are those two planes connected?
42:45
And let me get a piece of the--
42:49
blank piece of the board to remember the final step.
42:52
Right.
42:53
So we've got dimensions r and n minus r, and then over here r,
43:02
and m minus r.
43:05
OK.
43:05
And this is for the rows.
43:09
This is for the null space.
43:12
So this has the rows in it.
43:15
This has the null--
43:16
the solutions to Ax equals 0.
43:19
What is the beautiful geometry--
43:23
43:26
how do you visualize those two spaces?
43:30
How do you visualize?
43:30
Let me take an example.
43:32
Let A be 1, 2, 4, 2, 4, 8.
43:39
Sorry about that.
43:40
That's kind of a--
43:41
you see it hoked up example.
43:43
43:46
So this is 2 by 3.
43:49
So there n is 3.
43:52
What's in the null space of this matrix?
43:54
43:58
Can you see a vector that solves Ax equals 0?
44:04
And in fact, how many will there be?
44:06
What's-- yeah, what's r for this matrix?
44:09
Just tell me all the good stuff.
44:11
For that example, m is 2, n is 3, and r is--
44:20
AUDIENCE: 1.
44:21
PROFESSOR: 1.
44:22
Everybody sees 1 for the rank?
44:24
The rows are dependent.
44:28
There's only one independent row.
44:30
The columns are dependent.
44:31
There's only-- every column is a multiple of 1, 2.
44:35
It's a rank 1 matrix.
44:38
OK.
44:38
What about its-- so its row space has dimension--
44:45
AUDIENCE: 1.
44:46
PROFESSOR: 1.
44:47
And it's null space has dimension--
44:51
AUDIENCE: 2.
44:53
PROFESSOR: 2 So, cause n minus r will be 2.
44:57
So I'm looking for a couple of vectors that both give 0.
45:01
I believe there--
45:02
I think I've only got one independent row there.
45:07
So I should be able to find two different vectors
45:10
that solve Ax equals 0.
45:17
So what what's the solution to Ax equals 0?
45:20
AUDIENCE: 0 minus 2, 1.
45:22
PROFESSOR: 0 minus 2, 1.
45:27
Yeah, that works.
45:29
And what's an independent solution?
45:31
AUDIENCE: 4, 0, negative 1?
45:32
PROFESSOR: 4, 0-- don't throw me off--
45:36
4, 0 and--
45:38
AUDIENCE: Minus 1.
45:39
PROFESSOR: Minus 1.
45:39
Yeah.
45:40
That looks good.
45:42
That looks good.
45:44
And then the claim is that every solution would
45:46
be a combination of those two.
45:49
And this is how many there are.
45:51
And now, it's the geometry I'm completing.
45:56
So we have two minutes left in this lecture.
45:58
You just have to tell me how--
46:01
what's the relation between these guys in the row space,
46:06
and that guy in the null space?
46:08
What's the relation between the rows of A,
46:12
the solutions to Ax equals 0?
46:15
Between-- if you see it-- if you saw that vector and that
46:17
vector--
46:18
well, A times x is 0.
46:23
So what does that tell us?
46:24
What do we see for the relation between 1, 2, 4, and 0
46:29
minus 2, 1.
46:30
AUDIENCE: Orthogonal
46:31
PROFESSOR: They are orthogonal.
46:32
Terrific.
46:33
Yes.
46:34
Orthogonal I test by the dot product, 0 minus 4,
46:37
4, add to 0.
46:39
Yes.
46:40
So the-- and that's a completely general fact.
46:46
When I look at Ax equals 0, it's telling me
46:50
that x is orthogonal to the rows.
46:53
Do you see that?
46:54
Just to put it in again here.
46:57
If I look at Ax, A has a bunch of rows.
47:03
X has one column.
47:05
And I get 0.
47:06
That's the point of the null space.
47:08
47:11
And that equation is just saying that row 1 is orthogonal,
47:17
because that's the dot product of row 1 with x.
47:20
So here is row 1, row 2, row 3, and row 4 with x.
47:24
The rows with x--
47:26
and I get 0s.
47:27
So the point is then, these two spaces are at 90 degree angles.
47:36
That's really a neat picture of the four sub spaces.
47:41
And these two are for the same reason--
47:43
at 90 degree angles--
47:45
off in m dimensional space.
47:49
So this is the fundamental theorem of linear algebra--
47:54
to see that the dimensions come out right,
47:57
and the geometry comes out right.
48:00
Yeah.
48:00
And then, now, next time--
48:02
following the notes-- and I have a few more copies
48:06
of the one hand out.
48:11
We'll move on quickly next week to eigenvalues and positive
48:18
definite matrices.
48:20
Good this is really linear algebra moving on.
English - CC (English)
###