B1 中級 美國腔 21 分類 收藏
Okay, this is linear algebra, lecture four.
And, the first thing I have to do is something
that was on the list for last time, but here

it is now.
What's the inverse of a product?
If I multiply two matrices together and I
know their inverses, how do I get the inverse

of A times B?
So I know what inverses mean for a single
matrix A and for a matrix B.

What matrix do I multiply by to get the identity
if I have A B?

Okay, that'll be simple but so basic.
Then I'm going to use that to -- I will have
a product of matrices and the product that

we'll meet will be these elimination matrices
and the net result of today's lectures is

the big formula for elimination, so the net
result of today's lecture is this great way

to look at Gaussian elimination.
We know that we get from A to U by elimination.
We know the steps -- but now we get the right
way to look at it, A equals L U.

So that's the high point for today.
Can I take the easy part, the first step first?
So, suppose A is invertible -- and of course
it's going to be a big question, when is the

matrix invertible?
But let's say A is invertible and B is invertible,
then what matrix gives me the inverse of A B?

So that's the direct question.
What's the inverse of A B?
Do I multiply those separate inverses?
Yes. I multiply the two matrices A inverse
and B inverse, but what order do I multiply?

In reverse order.
And you see why.
So the right thing to put here is B inverse
A inverse.

That's the inverse I'm after.
We can just check that A B times that matrix
gives the identity.

So why -- once again, it's this fact that
I can move parentheses around.

I can just erase them all and do the multiplications
any way I want to.

So what's the right multiplication to do first?
B times B inverse.
This product here I is the identity.
Then A times the identity is the identity
and then finally A times A inverse gives the

So forgive the dumb example in the book.
Why do you, do the inverse things in reverse

It's just like -- you take off your shoes,
you take off your socks, then the good way

to invert that process is socks back on first,
then shoes.

Sorry, okay.
I'm sorry that's on the tape.
And, of course, on the other side we should
really just check -- on the other side I have

B inverse,
A inverse. That does multiply A B, and this
time it's these guys that give the identity,

squeeze down, they give the identity, we're
in shape.

Okay. So there's the inverse.
Good. While we're at it, let me do a transpose,
because the next lecture has got a lot to

-- involves transposes.
So how do I -- if I transpose a matrix, I'm
talking about square, invertible matrices

right now.
If I transpose one, what's its inverse?
Well, the nice formula is -- let's see.
Let me start from A, A inverse equal the identity.
And let me transpose both sides.
That will bring a transpose into the picture.
So if I transpose the identity matrix, what
do I have?

The identity, right?
If I exchange rows and columns, the identity
is a symmetric matrix.

It doesn't know the difference.
If I transpose these guys, that product, then
again it turns out that I have to reverse

the order.
I can transpose them separately, but when
I multiply, those transposes come in the opposite

So it's A inverse transpose times A transpose
giving the identity.

So that's -- this equation is -- just comes
directly from that

one. But this equation tells me what I wanted
to know, namely what is the inverse of this

guy A transpose?
What's the inverse of that -- if I transpose
a matrix, what'ss the inverse of the result?

And this equation tells me that here it is.
This is the inverse of A transpose.
Inverse of A transpose.
Of A transpose.
So I'll put a big circle around that, because
that's the answer, that's the best answer

we could hope for.
That if you want to know the inverse of A
transpose and you know the inverse of A, then

you just transpose that.
So in a -- to put it another way, transposing
and inversing you can do in either order for

a single matrix.
Okay. So these are like basic facts that we
can now use, all right -- so now I put it

to use.
I put it to use by thinking -- we're really
completing, the subject of elimination.

Actually, -- the thing about elimination is
it's the right way to understand what the

matrix has got.
This A equal L U is the most basic factorization
of a matrix.

I always worry that you will think this course
is all elimination.

It's just row operations.
And please don't.
We'll be beyond that, but it's the right algebra
to do first.

Okay. So, now I'm coming near the end of it,
but I want to get it in a decent form.

So my decent form is matrix form.
I have a matrix A, let's suppose it's a good
matrix, I can do elimination, no row exchanges

-- So no row exchanges for now.
Pivots all fine, nothing zero in the pivot

I get to the very end, which is U.
So I get from A to U.
And I want to know what's the connection?
How is A related to U?
And this is going to tell me that there's
a matrix L that connects them.

Can I do it for a two by two first?
Okay. Two by two, elimination.
Okay, so I'll do it under here.
Okay. So let my matrix A be -- We'll keep
it simple, say two and an eight, so we know

that the first pivot is a two, and the multiplier's
going to be a four and then let me put a one

here and what number do I not want to put

Four. I don't want a four there, because in
that case, the second pivot would not -- we

wouldn't have a second pivot.
The matrix would be singular, general screw-up.

So let me put some other number here like

Okay. Now I want to operate on that with my
elementary matrix.

So what's the elementary matrix?
Strictly speaking, it's E21, because it's
the guy that's going to produce a zero in

that position.
And it's going to produce U in one shot, because
it's just a two by two matrix.

So two one and I'm going to take four of those
away from those, produce that zero and leave

a three there.
And that's U.
And what's the matrix that did it?
Quick review, then.
What's the elimination elementary matrix E21
-- it's one zero, thanks.

And -- negative four one,
right. Good.
Okay. So that -- you see the difference between
this and what I'm shooting for.

I'm shooting for A on one side and the other
matrices on the other side of the equation.

So I can do that right away.
Now here's going to be my A equals L U.
And you won't have any trouble telling me
what -- so A is still two one eight seven.

L is what you're going to tell me and U is
still two one zero three.

Okay. So what's L in this case?
Well, first -- so how is L related to this
E guy?

It's the inverse, because I want to multiply
through by the inverse of this, which will

put the identity here, and the inverse will
show up there and I'll call it L.

So what is the inverse of this?
Remember those elimination matrices are easy
to invert.

The inverse matrix for this one is 1 0 4 1,
it has the plus sign because it adds back

what this removes.
Okay. Do you want -- if we did the numbers
right, we must -- this should be correct.

Okay. And of course it is.
That says the first row's right, four times
the first row plus the second row is eight

seven. Good. Okay.
That's simple, two by two.
But it already shows the form that we're headed

It shows -- so what's the L stand for?
Why the letter L?
If U stood for upper triangular, then of course
L stands for lower triangular.

And actually, it has ones on the diagonal,
where this thing has the pivots on the diagonal.

Oh, sometimes we may want to separate out
the pivots, so can I just mention that sometimes

we could also write this as -- we could have
this one zero four one -- I'll just show you

how I would divide out this matrix of pivots
-- two three.

There's a diagonal matrix.
And I just -- whatever is left is here.
Now what's left?
If I divide this first row by two to pull
out the two, then I have a one and a one half.

And if I divide the second row by three to
pull out the three, then I have a one.

So if this is L
U, this is maybe called L D or pivot U.

And now it's a little more balanced, because
we have ones on the diagonal here and here.

And the diagonal matrix in the middle.
So both of those...
Matlab would produce either one.
I'll basically stay with L U.
Okay. Now I have to think about bigger than
two by two.

But right now, this was just like easy exercise.
And, to tell the truth, this one was a minus
sign and this one was a plus sign.

I mean, that's the only difference.
But, with three by three, there's a more significant

Let me show you how that works.
Let me move up to a three by three, let's
say some matrix A, okay?

Let's imagine it's three by three.
I won't write numbers down for now.
So what's the first elimination step that
I do, the first matrix I multiply it by, what

letter will I use for
that? It'll be E two one, because it's -- the
first step will be to get a zero in that two

one position. right?
And then the next step will be to get a zero
in the three one position.

And the final step will be to get a zero in
the three two

That's what elimination is, and it produced
U. position.

And again, no row exchanges.
I'm taking the nice case, now, the typical
case, too -- when I don't have to do any row

exchange, all I do is these elimination steps.
Now, suppose I want that stuff over on the
right-hand side, as I really do.

That's, like, my point here.
I can multiply these together to get a matrix
E, but I want it over on the right.

I want its inverse over there.
So what's the right expression now?
If I write A and U, what goes there?
So I've got the inverse of this, I've got
three matrices in

a row now.
And it's their inverses that are going to
show up, because each one is easy to invert.

Question is, what about the whole bunch?
How easy is it to invert the whole bunch?
So, that's what we know how to do.
We know how to invert, we should take the
separate inverses, but they go in the opposite

So what goes here?
E three two inverse, right, because I'll multiply
from the left by E three two inverse, then

I'll pop it up next to U.
And then will come E three one inverse.
And then this'll be the only guy left standing
and that's gone when I do an E two one inverse.

So there is L.
That's L U.
L is product of inverses.
Now you still can ask why is this guy preferring

And let me explain why.
Let me explain why is this product nicer than
this one?

This product turns out to be better than this

Let me take a typical case here.
Let me take a typical case.
So let me -- I have to do three by three for
you to see the improvement.

Two by two, it was just one E, no problem.
But let me go up to this case.
Suppose my matrices E21 -- suppose E21 has
a minus two in there.

Suppose that -- and now suppose -- oh, I'll
even suppose E31 is the identity.

I'm going to make the point with just a couple
of these.

Now this guy will have -- do something -- now
let's suppose minus five one.

Okay. There's typical.
That's a typical case in which we didn't need
an E31. Maybe we already had a zero in that

three one position.
Let me see -- is that going to be enough to,
show my point?

Let me do that multiplication.
So if I do that multiplication it's like good
practice to

multiply these matrices.
Tell me what's above the diagonal when I do
this multiplication?

All zeroes. When I do this multiplication,
I'm going to get ones on the diagonal and

zeroes above.
Because -- what does that say?
That says that I'm subtracting rows from lower

So nothing is moving upwards as it did last
time in Gauss-Jordan. Okay.

Now -- so really, what I have to do is check
this minus two one zero, now this is -- what's

that number?
This is the number that I'm really have in

That number is ten.
And this one is -- what goes here?
Row three against column two, it looks like
the minus five.

What – it's that ten.
How did that ten get in there?
I don't like that ten.
I mean -- of course, I don't want to erase
it, because it's right.

But I don't want it there.
It's because -- the ten got in there because
I subtracted two of row one from row two,

and then I subtracted five of that new row
two from row three.

So doing it in that order, how did row one
effect row three?

Well, it did, because two of it got removed
from row two and then five of those got removed

from row three.
So altogether ten of row one got thrown into
row three.

Now my point is in the reverse direction -- so
now I can do it -- below it I'll do the inverses.

And, of course, opposite order.
Reverse order.
Reverse order.
Okay. So now this is going to -- this is the
E that goes on the left side.

Left of A.
Now I'm going to do the inverses in the opposite
order, so what's the -- So the opposite order

means I put this inverse first.
And what is its inverse?
What's the inverse of E21? Same thing with
a plus sign, right?

For the individual matrices, instead of taking
away two I add back two of row one to row

two, so no problem.
And now, in reverse order, I want to invert

Just right?
I'm doing just this, this.
So now the inverse is again the same thing,
but add in the five.

And now I'll do that multiplication and I'll
get a happy result.

I hope.
Did I do it right so far?
Yes, okay.
Let me do the multiplication.
I believe this comes out.
So row one of the answer is one zero zero.
Oh, I know that all this is going to be left,
right? Then I have two one zero.
So I get two one zero there, right?
And what's the third row?
What's the third row in this product?
Just read it out to me, the third row?
0 5 1
Because one way to say is –
this is saying take one of the

last row and there it is.
And this is my matrix L.
And it's the one that goes on the left of

It goes into -- what do I mean here?
Maybe rather than saying left of A, left of
U, let me right down again what I mean.

E A is U, whereas A is L U.
Let me make the point now in words.
The order that the matrices come for L is
the right order.

The two and the five don't sort of interfere
to produce this ten one. In the

right order, the multipliers just sit in the
matrix L.

That's the point -- that if I want to know
L, I have no work to do.

I just keep a record of what those multipliers
were, and that gives me L.

So I'll draw the -- let me say it.
So this is the A=L U.
So if no row exchanges, the multipliers that
those numbers that we multiplied rows by and

subtracted, when we did an elimination step
-- the multipliers go directly into L.

So L is -- this is the way, to look at elimination.
You go through the elimination steps, and
actually if you do it right, you can throw

away A as you create L U.
If you think about it, those steps of elimination,
as when you've finished with row two of A,

you've created a new row two of U, which you
have to save, and you've created the multipliers

that you used -- which you have to save,
and then you can forget A.

So because it's all there in L and U.
So that's -- this moment is maybe the new
insight in elimination that comes from matrix

-- doing it in matrix form.
So it was -- the product of Es is -- we can't
see what that product of Es is.

The matrix E is not a particularly attractive

What's great is when we put them on the other
side -- their inverses in the opposite order,

there the L comes out just right. Okay.
Now -- oh gosh, so today's a sort of,
like, practical day.
Can we think together how expensive is elimination?
How many operations do we do?
So this is now a kind of new topic which I
didn't list as -- on the program, but here

it came. Here it comes.
How many operations on an n by n matrix A.
I mean, it's a very practical question.
Can we solve systems of order a thousand,
in a second or a minute or a week?

Can we solve systems of order a million in
a second or an hour or a week?

I mean, what's the -- if it's n by n, we often
want to take n bigger.

I mean, we've put in more information.
We make the whole thing is more accurate for
the bigger matrix.

But it's more expensive, too, and the question
is how much more expensive?

If I have matrices of order a hundred.
Let's say a hundred by a hundred.
Let me take n to be a hundred.
Say n equal a hundred.
How many steps are we doing?
How many operations are we actually doing
that we -- And let's suppose there aren't

any zeroes, because of course if a matrix
has got a lot of zeroes in good places, we

don't have to do those operations, and,
it'll be much faster.
But -- so just think for a moment about the
first step.

So here's our matrix A, hundred by a hundred.
And the first step will be -- that column,
is got zeroes down

here. So it's down to 99 by 99, right?
That's really like the first stage of elimination,
to get from this hundred
by hundred non-zero matrix to this stage where
the first pivot is sitting up here and the

first row's okay the first column is okay.
So, eventually -- how many steps did that

You see, I'm trying to get an idea.
Is the answer proportional to n?
Is the total number of steps in elimination,
the total number, is it proportional to n

-- in which case if I double n from a hundred
to two hundred -- does it take me twice as

Does it square, so it would take me four times
as long?

Does it cube so it would take me eight times
as long?

Or is it n factorial, so it would take me
a hundred times as long?

I think, you know, from a practical point
of view, we have to have some idea of the

cost, here.
So these are the questions that I'm -- let
me ask those questions again.

Is it proportional -- does it go like n, like
n squared, like n cubed -- or some higher

power of n?
Like n factorial where every step up multiplies
by a hundred and then by a hundred and one

and then by a hundred and two -- which is

Okay, so that's the only way I know to answer
that is to think through what we actually

had to do.
So what was the cost here?
Well, let's see.
What do I mean by an operation?
I guess I mean, well an addition or -- yeah.
No big deal.
I guess I mean an addition or a subtraction
or a multiplication or a division.

And actually, what operation I doing all the

When I multiply row one by multiplier L and
I subtract from row six.

What's happening there individually?
What's going on?
If I multiply -- I do a multiplication by
L and then a subtraction.

So I guess operation -- Can I count that for
the moment as, like, one operation?

Or you may want to count them separately.
The typical operation is multiply plus a subtract.
So if I count those together, my answer's
going to come out

half as many as if -- I mean,
if I count them separately, I'd have a certain

number of multiplies, certain number of subtracts.
That's really want to do.
Okay. How many have I got here?
So, I think -- let's see.
It's about -- well, how many, roughly?
How many operations to get from here to here?
Well, maybe one way to look at it is all these
numbers had to get changed.

The first row didn't get changed, but all
the other rows got changed at this step.

So this step -- well, I guess maybe -- shall
I say it cost about a hundred squared.

I mean, if I had changed the first row, then
it would have been exactly hundred squared,

because -- because that's how many numbers
are here.

A hundred squared numbers is the total count
of the entry, and all but this insignificant

first row got changed.
So I would say about a hundred squared.
Now, what about the next step?
So now the first row is fine.
The second row is fine.
And I'm changing these zeroes are all fine,
so what's up with the second step?

And then you're with me.
Roughly, what's the cost?
If this first step cost a hundred squared,
about, operations then this one, which is

really working on this guy to produce this,
costs about what?

How many operations to fix?
About ninety-nine squared, or ninety-nine
times ninety-eight. But less, right?

Less, because our problem's getting smaller.
About ninety-nine squared.
And then I go down and down and the next one
will be ninety-eight squared, the next ninety-seven

squared and finally I'm down around one squared
or -- where it's just like the little numbers.

The big numbers are here.
So the number of operations is about n squared
plus that was n, right? n was a hundred?

n squared for the first step, then n minus
one squared, then n minus two squared, finally

down to three squared and two squared and
even one squared.

No way I should have written that -- squeezed
that in.

Let me try it so the count is n squared plus
n minus one squared plus -- all the way down

to one squared.
That's a pretty decent count.
Admittedly, we didn't catch every single tiny
operation, but we got the right leading term

And what do those add up to?
Okay, so now we're coming to the punch of
this, question, this operation count.

So the operations on the left side, on the
matrix A to finally get to U.

And anybody -- so which of these quantities
is the right ballpark for that count?

If I add a hundred squared to ninety nine
squared to ninety eight squared -- ninety

seven squared, all the way down to two squared
then one squared, what have I got, about?

It's just one of these -- let's identify it

Is it n?
Certainly not.
Is it n factorial?
If it was n factorial, we would -- with determinants,
it is n factorial.

I'll put in a bad mark against determinants,
because that -- okay, so what is it?

It's n -- well, this is the answer.
It's this order -- n cubed.
It's like I have n terms, right?
I've got n terms in this sum.
And the biggest one is n squared.
So the worst it could be would be n cubed,
but it's not as bad as -- it's n cubed times

-- it's about one third of n cubed.
That's the magic operation count.
Somehow that one third takes account of the
fact that the numbers are getting smaller.

If they weren't getting smaller, we would
have n terms times n squared, but it would

be exactly n cubed.
But our numbers are getting smaller -- actually,
row two and row one moves down to row three.

do you remember where does one third come
in this -- I'll even allow a mention of calculus.

So calculus can be mentioned, integration
can be mentioned now in the next minute and

not again for weeks.
It's not that I don't like 18.01, but18.06
is better.

Okay. So, -- so what's -- what's the calculus
formula that looks like?

It looks like -- if we were in calculus instead
of summing stuff, we would integrate.

So I would integrate x squared and I would
get one third x

cubed. So if that was like an integral from
one to n, of x squared b x, if the answer

would be one third n cubed -- and it's correct
for the sum also, because that's, like, the

whole point of calculus.
The whole point of calculus is -- oh, I don't
want to tell you the whole -- I mean, you

know the whole point of calculus.
Calculus is like sums except it's continuous.
Okay. And algebra is discreet.
So the answer is one third n cubed.
Now I'll just -- let me say one more thing
about operations.

What about the right-hand side?
This was what it cost on the left side.
This is on A.
Because this is A that we're working with.
But what's the cost on the extra column vector
b that we're hanging around here?

So b costs a lot less, obviously, because
it's just one column.

We carry it through elimination and then actually
we do back substitution.

Let me just tell you the answer there.
It's n squared.
So the cost for every right hand side is n

So let me -- I'll just fit that in here -- for
the cost of b turns out to be n squared.

So you see if we have, as we often have, a
a matrix A and several right-hand sides, then

we pay the price on A, the higher price on
A to get it split up into L and U to do elimination

on A, but then we can process every right-hand
side at low cost.

So the -- We really have discussed the most
fundamental algorithm for a system of equations.

So, I'm ready to allow row exchanges.
I'm ready to allow -- now what happens to
this whole -- today's lecture if there are

row exchanges?
When would there be row exchanges?
There are row -- we need to do row exchanges
if a zero shows up in the pivot position.

So moving then into the final section of this
chapter, which is about transposes -- well,

we've already seen some transposes, and -- the
title of this section is,

and Permutations."

Okay. So can I say, now, where does a permutation
come in?

Let me talk a little about permutations.
So that'll be up here, permutations.
So these are the matrices that I need to do
row exchanges.

And I may have to do two row exchanges.
Can you invent a matrix where I would have
to do two row exchanges and then would come

out fine?
Yeah let's just, for the heck of it -- so
I'll put it here.

Let me do three by threes.
Actually, why don't I just plain list all
the three by three permutation matrices.

There're a nice little group of them.
What are all the matrices that exchange no
rows at all?

Well, I'll include the identity.
So that's a permutation matrix that doesn't
do anything.

Now what's the permutation matrix that exchanges
-- what is P12? The permutation matrix that

exchanges rows one and two would be -- 0 1
0 -- 1 0 0, right.

I just exchanged those rows of the identity
and I've got it.

Okay. Actually, I'll -- yes.
Let me clutter this up.
Okay. Give me a complete list of all the row
exchange matrices.

So what are they?
They're all the ways I can take the identity
matrix and rearrange its rows.

How many will there be?
How many three by three permutation matrices?
Shall we keep going and get the answer?
So tell me some more.
STUDENT: Zero one –
STRANG: Zero – What one
are you going to do now?

STUDENT: I'm going to switch the –
STRANG: Switch rows one and -- One and
three, okay. One and three, leaving two alone.

Now what else? Switch -- what would
be the next easy one -- is switch two and

three, good. So I'll leave one zero zero alone
and I'll switch -- I'll move number three

up and number two down.
Okay. Those are the ones that just exchange
single -- a pair of

rows. This guy, this guy and this guy exchanges
a pair of rows, but now there are more possibilities.

What's left?
So tell -- there is another one here.
What's that?
It's going to move -- it's going
to change all rows, right?

Where shall we put them?
So -- give me a first row.
STUDENT: Zero one zero?
STRANG: Zero one zero.
Okay, now a second row -- say zero zero one
and the third guy

One zero zero.
So that is like a cycle.
That puts row two moves up to row one,
row three moves up to

row two and row one moves
down to row three.

And there's one more, which is -- let's see.
What's left?
I'm lost.
STUDENT: Is it zero zero one?
STRANG: Is it zero zero one? Okay.
STUDENT: One zero zero.
STRANG: One zero zero, okay.
Zero one zero, okay.
Six. Six of them.
Six P. And they're sort of nice, because what
happens if I write, multiply two of them together?

If I multiply two of these matrices together,
what can you tell me about the answer?

It's on the list.
If I do some row exchanges and then I do some
more row exchanges, then all together I've

done row exchanges.
So if I multiply -- but, I don't know.
And if I invert, then I'm just doing row exchanges
to get back again.

So the inverses are all there.
It's a little family of matrices that -- they've
got their own -- if I multiply, I'm still

inside this group.
If I invert I'm inside this group -- actually,
group is the right name for this subject.

It's a group of six matrices, and what about
the inverses?

What's the inverse of this guy, for example?
What's the inverse -- if I exchange rows one
and two, what's the inverse matrix?

Just tell me fast.
The inverse of that matrix is -- if I exchange
rows one and two, then what I should do to

get back to where I started is the same thing.
So this thing is its own inverse.
That's probably its own inverse.
This is probably not -- actually, I think
these are inverses of each other.

Oh, yeah, actually -- the inverse is the transpose.
There's a curious fact about permutations
matrices, that the inverses are the transposes.

And final moment -- how many are there if
I -- how many four by four permutations?

So let me take four by four -- how many Ps?
Well, okay.
Make a good guess.
Twenty four, right. Twenty four Ps.
Okay. So, we've got these permutation matrices,
and in the next lecture, we'll use them.

So the next lecture,
finishes Chapter 2

and moves to Chapter 3.
Thank you.


線性代數 Lec4 (Lec 4 Factorization into A = LU)

21 分類 收藏
Lin 發佈於 2018 年 8 月 31 日
  1. 1. 單字查詢


  2. 2. 單句重複播放


  3. 3. 使用快速鍵


  4. 4. 關閉語言字幕


  5. 5. 內嵌播放器


  6. 6. 展開播放器


  1. 英文聽力測驗


  1. 點擊展開筆記本讓你看的更舒服

  1. UrbanDictionary 俚語字典整合查詢。一般字典查詢不到你滿意的解譯,不妨使用「俚語字典」,或許會讓你有滿意的答案喔