The second lecture in linear algebra, and I've put below my

main topics for today. I put right there a system of

equations that's going to be our example to work with.

But what are we going to do with it?

We're going to solve it. And the method of solution will

not be determinants. Determinants are something that

will come later. The method we'll use is called

elimination. And it's the way every software

package solves equations. And elimination,

well, if it succeeds, it gets the answer.

And normally it does succeed. If the matrix A that's coming

into that system is a good matrix, and I think this one is,

then elimination will work. We'll get the answer in an

efficient way. But why don't we,

as long as we're sort of seeing how elimination works -- it's

always good to ask how could it fail?

So at the same time, we'll see how elimination

decides whether the matrix is a good one or has problems.

Then to complete the answer, there's an obvious step of back

substitution. In fact, the idea of

elimination is -- you would have thought of it,

right? I mean Gauss thought of it

before we did, but only because he was born

earlier. It's a natural idea...

and died earlier, too.

Okay, and you've seen the idea. But now, the part that I want

to show you is elimination expressed in matrix language,

because the whole course -- all the key ideas get expressed

as matrix operations, not as words.

And one of the operations, of course, that we'll meet is

how do we multiply matrices and why?

Okay, so there's a system of equations.

Three equations and three unknowns.

And there's the matrix, the three by three matrix -- so

this is the system Ax = b. This is our system to solve,

Ax equal -- and the right-hand side is that vector 2,

12, 2. Okay.

Now, when I describe elimination -- it gets to be a

pain to keep writing the equal signs and the pluses and so on.

It's that matrix that totally matters.

Everything is in that matrix. But behind it is those

equations. So what does elimination do?

What's the first step of elimination?

We accept the first equation, it's okay.

I'm going to multiply that equation by the right number,

the right multiplier and I'm going to subtract it from the

second equation. With what purpose?

So that will decide what the multiplier should be.

Our purpose is to knock out the x part of equation two.

So our purpose is to eliminate x.

So what do I multiply -- and again, I'll do it with this

matrix, because I can do it short.

What's the multiplier here? What do I multiply -- equation

one and subtract. Notice I'm saying that word

subtract. I'd like to stick to that

convention. I'll do a subtraction.

First of all this is the key number that I'm starting with.

And that's called the pivot. I'll put a box around it and

write its name down. That's the first pivot.

The first pivot. Okay.

So I'm going to use -- that's sort of like the key number in

that equation. And now what's the multiplier?

So I'm going to -- my first row won't change,

that's the pivot row. But I'm going to use it -- and

now, finally, let me ask you what the

multiplier is. Yes?

3. 3 times that first equation

will knock out that 3. Okay.

So what will it leave? So the multiplier is 3.

3 times that will make that 0. That was our purpose.

3 2s away from the 8 will leave a 2 and three 1s away from 1

will leave a minus 2. And this guy didn't change.

Okay. Now the next step -- this is

forward elimination and that step's completed.

Oh, well, you could say wait a minute, what about the right

hand side? Shall I carry -- the right-hand

side gets carried along. Actually MatLab finishes up

with the left side before -- and then just goes back to do the

right side. Maybe I'll be MatLab for a

moment and do that. Okay.

I'm leaving a room for a column of b, the right-hand side.

But I'll fill it in later. Okay.

Now the next step of elimination is what?

Well, strictly speaking... this position that I cleaned up

was like the 2, 1 position, row 2,

column 1. So I got a 0 in the 2,

1 position. I'll use 2,1 as the index of

that step. The next step should be to

finish the column and get a 0 in that position.

So the next step is really the 3,1 step, row three,

column one. But of course,

I already have 0. Okay.

So the multiplier is 0. I take 0 of this equation away

from this one and I'm all set. So I won't repeat that,

but there was a step there which, MatLab would have to look

-- it would look at this number and, do that step,

unless you told it in advance that it was 0.

Okay. Now what?

Now we can see the second pivot, which is what?

The second pivot -- see, we've eliminated -- x is now

gone from this equation, right?

We're down to two equations in y and z.

And so now I just do it again. Like, everything's very recursive

at this -- this is like -- such a basic algorithm and

you've seen it, but carry me through one last

step. So this is still the first

pivot. Now the second pivot is this

guy, who has appeared there. And what's the multiplier,

the appropriate multiplier now? And what's my purpose?

Is it to wipe out the 3, 2 position, right?

This was the 2, 1 step.

And now I'm going to take the 3, 2 step.

So this all stays the same, 1 2 1, 0 2 -1 and the pivots

are there. Now I'm using this pivot,

so what's the multiplier? 2.

2 times this equation, this row, gets subtracted from

this row and makes that a 0. So it's 0, 0 and is it a 5?

Yeah, I guess it's a 5, is that right?

Because I have a one there and I'm subtracting twice of twice

this, so I think it's a 5 there. There's the third pivot.

So let me put a box around all three pivots.

Is there a -- oh, did I just invent a negative

one? I'm sorry that the tape can't,

correct that as easily as I can.

Okay. Thank you very much.

You get an A in the course now. Is that correct?

Is it correct now? Okay.

So the three pivots are there -- I know right away a lot about

this matrix. This elimination step from A --

this matrix I'm going to call U. U for upper triangular.

So the whole purpose of elimination was to get from A to

U. And, literally,

that's the most common calculation in scientific

computing. And people think of how could I

do that faster? Because it's a major,

major thing. But we're doing it the

straightforward way. We found three pivots,

and by the way, I didn't say this,

pivots can't be 0. I don't accept 0 as a pivot.

And I didn't get 0. So this matrix is great.

It gave me three pivots, I didn't have to do anything

special, I just followed the rules and, and the pivots are 1,

2 and 5. By the way, just because I

always anticipate stuff from a later day, if I wanted to know

the determinant of this matrix --

which I never do want to know, but I would just multiply the

pivots. The determinant is 10.

So even things like the determinant are here.

Okay. Now -- oh, let me talk about

failure for a moment, and then --

and then come back to success. How could this have failed?

How could -- by fail, I mean to come up with three

pivots. I mean, there are a couple of

points. I would have already been in

trouble if this very first number here was 0.

If it was a 0 there -- suppose that had been a 0,

there were no Xs in that equation -- first equation.

Does that mean I can't solve the problem?

Does that mean I quit? No.

What do I do? I switch rows.

I exchange rows. So in case of a 0,

I will not say 0 pivot. I will never be heard to utter

those words, 0 pivot. But if there's a 0 in the pivot

position, maybe I can say that, I would try to exchange for a

lower equation and get a proper pivot up there.

Okay. Now, for example,

this second pivot came out two. Could it have come out 0?

What -- actually, if I change that 8 a little

bit, I would have got a little trouble.

What should I change that 8 to so that I run into trouble?

A 6. If that had been a 6,

then this would have been 0 and I couldn't have used that as the

pivot. But I could have exchanged

again. In this case.

In this case, because when can I get out of

trouble? I can get out of trouble if

there's a non-0 below this troublesome 0.

And there is here. So I would be okay in this

case. If this was a 6,

I would survive by a row exchange.

Now -- of course, it might have happened that I

couldn't do the row, that -- that there was 0s below

it, but here there wasn't. Now, I could also have got in

trouble if this number 1 was a little different.

See, that 1 became a 5, I guess, by the end.

So can you see what number there would have got me trouble

that I really couldn't get out of?

Trouble that I couldn't get out of would mean if 0 is in the

pivot position and I've got no place to exchange.

So there must be some number which if I had had here it would

have meant failure. Negative 4, good.

If it was a negative 4 here -- if it happened to be a negative

4, I'll temporarily put it up here.

If this had been a negative 4 z, then I would have gone

through the same steps. This would have been a minus 4,

it still would have been a minus 4.

But at the last minute it would have become 0.

And there wouldn't have been a third pivot.

The matrix would have not been invertible.

Well, of course, the inverse of a matrix is

coming next week, but, you've heard these words

before. So, that's how we identify

failure. There's temporary failure when

we can do a row exchange -- and get out of it,

or there's complete failure when we get a 0 and -- and

there's nothing below that we can use.

Okay. Let's stay with -- back to

success now. In fact, I guess the next topic

is back substitution. So what's back substitution?

Well, now I'd better bring the right-hand side in.

So what would MatLab do and what should we do?

Let me bring in the right-hand side as an extra column.

So there comes B. So it's 2, 12,

2. I would call this the augmented

matrix. "Augment" means you've tacked

something on. I've tacked on this extra

column. Because, when I'm working with

equations, I do the same thing to both sides.

So, at this step, I subtracted 2 of the first

equation away from the second equation so that this augmented

-- I even brought some colored chalk, but I don't know if it

shows up. So this is like the augmented

-- no! Damn, circled the wrong thing.

Okay. Here is b.

Okay, that's the extra column. Okay.

So what happened to that extra column, the right-hand side of

the equations, when I did the first step?

So that was 3 of this away from this, so it took -- the 2 stayed

the same, but three 2s got taken away from 12,

leaving 6, and that 2 stayed the same.

So this is how it's looking halfway along.

And let me just carry to the end.

The 2 and the 6 stay the same, but -- what do I have here?

Oh, gosh. Help me out,

now. What -- so now I'm --

This is still like forward elimination.

I got to this point, which I think is right,

and now what did I do at this step?

I multiplied that pivot by 2 or that whole equation by 2 and

subtracted from that, so I think I take two 6s,

which is 12, away from the 2.

Do you think minus 10 is my final right-hand side -- the

right-hand side that goes with U, and let me call that once and

forever the vector c. So c is what happens to b,

and U is what happens to A. Okay.

There you've seen elimination clean.

Okay. Oh, what's back substitution?

So what are my final equations, then?

Can I copy these equations? x+2y+z=2 is still there and

2y-2z=6 is there, and 5z=-10.

Okay. Those are the equations that

these numbers are telling me about.