This is lecture five in linear algebra.

And, it will complete this chapter of the book.

So the last section of this chapter

is two point seven that talks about permutations, which

finished the previous lecture, and transposes,

which also came in the previous lecture.

There's a little more to do with those guys, permutations

and transposes.

But then the heart of the lecture will be the beginning

of what you could say is the beginning of linear algebra,

the beginning of real linear algebra which is seeing

a bigger picture with vector spaces -- not just vectors,

but spaces of vectors and sub-spaces of those spaces.

So we're a little ahead of the syllabus, which

is good, because we're coming to the place

where, there's a lot to

do.

Okay.

So, to begin with permutations.

Can I just --

so these permutations, those are matrices P and they execute

row exchanges.

And we may need them.

We may have a perfectly good matrix,

a perfect matrix A that's invertible that we can solve A

x=b, but to do it --

I've got to allow myself that extra freedom

that if a zero shows up in the pivot position I move it away.

I get a non-zero.

I get a proper pivot there by exchanging from a row below.

And you've seen that already, and I just

want to collect the ideas together.

And principle, I could even have to do

that two times, or more times.

So I have to allow --

to complete the --

the theory, the possibility that I take my matrix A,

I start elimination, I find out that I need row exchanges

and I do it and continue and I finish.

Okay.

Then all I want to do is say -- and I won't make a big project

out of this --

what happens to A equal L U?

So A equal L U --

this was a matrix L with ones on the diagonal and zeroes

above and multipliers below, and this U

we know, with zeroes down here.

That's only possible.

That description of elimination assumes

that we don't have a P, that we don't have any row exchanges.

And now I just want to say, okay, how

do I account for row exchanges?

Because that doesn't.

The P in this factorization is the identity matrix.

The rows were in a good order, we left them there.

Maybe I'll just add a little moment of reality,

too, about how Matlab actually does elimination.

Matlab not only checks whether that pivot is not zero,

as every human would do.

It checks for is that pivot big enough,

because it doesn't like very, very small pivots.

Pivots close to zero are numerically bad.

So actually if we ask Matlab to solve a system,

it will do some elimination some row exchanges, which

we don't think are necessary.

Algebra doesn't say they're necessary, but accuracy --

numerical accuracy says they are.

Well, we're doing algebra, so here we

will say, well, what do row exchanges do,

but we won't do them unless we have to.

But we may have to.

And then, the result is --

it's hiding here.

It's the main fact.

This is the description of elimination with row exchanges.

So A equal L U becomes P A equal L U.

So this P is the matrix that does the row exchanges,

and actually it does them --

it gets the rows into the right order,

into the good order where pivots will not --

where zeroes won't appear in the pivot position,

where L and U will come out right as up here.

So, that's the point.

Actually, I don't want to labor that point,

that a permutation matrix --

and you remember what those were.

I'll remind you from last time of what the main points about

permutation matrices were --

and then just leave this factorization

as the general case.

This is -- any invertible A we get this.

For almost every one, we don't need a P.

But there's that handful that do need row exchanges,

and if we do need them, there they are.

Okay, finally, just to remember what P was.

So permutations, P is the identity matrix

with reordered rows.

I include in reordering the possibility that you just

leave them the same.

So the identity matrix is -- okay.

That's, like, your basic permutation matrix --

your do-nothing permutation matrix is the identity.

And then there are the ones that exchange two rows and then

the ones that exchange three rows and then then ones that

exchange four --

well, it gets a little --

it gets more interesting algebraically

if you've got four rows, you might exchange them

all in one big cycle.

One to two, two to three, three to four, four to one.

Or you might have -- exchange one and two and three and four.

Lots of possibilities there.

In fact, how many possibilities?

The answer was (n)factorial.

This is n(n-1)(n-2)...

(3)(2)(1).

That's the number of -- this counts the reorderings,

the possible reorderings.

So it counts all the n by n permutations.

And all those matrices have these --

have this nice property that they're all invertible,

because we can bring those rows back into the normal order.

And the matrix that does that is just P --

is just the same as the transpose.

You might take a permutation matrix,

multiply by its transpose and you will see how --

that the ones hit the ones and give the ones in the identity

matrix.

So this is a --

we'll be highly interested in matrices

that have nice properties.

And one property that -- maybe I could rewrite that as P

transpose P is the identity.

That tells me in other words that this

is the inverse of that.

Okay.

We'll be interested in matrices that have P transpose

P equal the identity.

There are more of them than just permutations,

but my point right now is that permutations are like a little

group in the middle --

in the center of these special matrices.

Okay.

So now we know how many there are.

Twenty four in the case of -- there are twenty four four

by four permutations, there are five factorial which is

a hundred and twenty, five times twenty four would bump us up

to a hundred and twenty -- so listing all the five by five

permutations would be not so much fun.

Okay.

So that's permutations.

Now also in section two seven is some discussion of transposes.

And can I just complete that discussion.

First of all, I haven't even transposed a matrix

on the board here, have I?

So I'd better do it.

So suppose I take a matrix like (1 2 4; 3 3 1).

It's a rectangular matrix, three by two.

And I want to transpose it.

So what's --

I'll use a T, also Matlab would use a prime.

And the result will be --

I'll right it here, because this was three rows and two columns,

this was a three by two matrix.

The transpose will be two rows and three columns,

two by three.

So it's short and wider.

And, of course, that row -- that column becomes a row --

that column becomes the other row.

And at the same time, that row became a column.

This row became a column.

Oh, what's the general formula for the transpose?

So the transpose --

you see it in numbers.

What I'm going to write is the same thing in symbols.

The numbers are the clearest, of course.

But in symbols, if I take A transpose

and I ask what number is in row I and column J of A transpose?

Well, it came out of A.

It came out A by this flip across the main diagonal.

And, actually, it was the number in A

which was in row J, column I.

So the row and column --

the row and column numbers just get reversed.

The row number becomes the column number,

the column number becomes the row number.

No problem.

Okay.

Now, a special --

the best matrices, we could say.

In a lot of applications, symmetric matrices show up.

So can I just call attention to symmetric matrices?

What does that mean?

What does that word symmetric mean?

It means that this transposing doesn't change the matrix.

A transpose equals A.

And an example.

So, let's take a matrix that's symmetric,

so whatever is sitting on the diagonal --

but now what's above the diagonal, like a one,

had better be there, a seven had better be here,

a nine had better be there.

There's a symmetric matrix.

I happened to use all positive numbers as its entries.

That's not the point.

The point is that if I transpose that matrix,

I get it back again.

So symmetric matrices have this property A transpose equals A.

I guess at this point --

I'm just asking you to notice this family of matrices that

are unchanged by transposing.

And they're easy to identify, of course.

You know, it's not maybe so easy before we had a case where

the transpose gave the inverse.

That's highly important, but not so simple to see.

This is the case where the transpose gives the same matrix

back again.

That's totally simple to see.

Okay.

Could actually -- maybe I could even say when would we get such

a matrix?

For example, this -- that matrix is absolutely far from

symmetric, right?

The transpose isn't even the same shape --

because it's rectangular, it turns the --

lies down on its side.

But let me tell you a way to get a symmetric matrix out of

this.

Multiply those together.

If I multiply this rectangular, shall I

call it R for rectangular?

So let that be R for rectangular matrix

and let that be R transpose, which it is.

Then I think that if I multiply those together,

I get a symmetric matrix.

Can I just do it with the numbers

and then ask you why, how did I know it would be symmetric?

So my point is that R transpose R is always symmetric.

Okay?

And I'm going to do it for that particular R transpose R which

was --

let's see, the column was one two four three three one.

I called that one R transpose, didn't I,

and I called this guy one two four three three one.

I called that R.

Shall we just do that multiplication?

Okay, so up here I'm getting a ten.

Next to it I'm getting two, a nine, I'm getting an eleven.

Next to that I'm getting four and three, a seven.

Now what do I get there?

This eleven came from one three times two three, right?

Row one, column two.

What goes here?

Row two, column one.

But no difference.

One three two three or two three one three, same thing.

It's going to be an eleven.

That's the symmetry.