This is the lecture on the singular value decomposition.

But everybody calls it the SVD.

So this is the final and best factorization of a matrix.

Let me tell you what's coming.

The factors will be, orthogonal matrix,

diagonal matrix, orthogonal matrix.

So it's things that we've seen before, these special good

matrices, orthogonal diagonal.

The new point is that we need two orthogonal matrices.

A can be any matrix whatsoever.

Any matrix whatsoever has this singular value decomposition,

so a diagonal one in the middle, but I need two different

-- probably different orthogonal matrices to be able to do this.

Okay.

And this factorization has jumped into importance and is

properly, I think, maybe the bringing together of

everything in this course.

One thing we'll bring together is the very good family of

matrices that we just studied, symmetric, positive,

definite.

Do you remember the stories with those guys?

Because they were symmetric, their eigenvectors were

orthogonal, so I could produce an orthogonal matrix -- this is

my usual one.

My usual one is the eigenvectors and eigenvalues

In the symmetric case, the eigenvectors are

orthogonal, so I've got the good -- my ordinary s has become an

especially good Q.

And positive definite, my ordinary lambda has become a

positive lambda.

So that's the singular value decomposition in case our matrix

is symmetric positive definite -- in that case,

I don't need two -- U and a V -- one orthogonal matrix will do

for both sides.

So this would be no good in general, because usually the

eigenvector matrix isn't orthogonal.

So that's not what I'm after.

I'm looking for orthogonal times diagonal times orthogonal.

And let me show you what that means and where it comes from.

Okay.

What does it mean?

You remember the picture of any linear transformation.

This was, like, the most important figure in

And what I looking for now?

A typical vector in the row space

-- typical vector, let me call it v1,

gets taken over to some vector in the column space,

say u1.

So u1 is Av1.

Okay.

Now, another vector gets taken over here somewhere.

What I looking for?

In this SVD, this singular value

decomposition, what I'm looking for is an

orthogonal basis here that gets knocked over into an orthogonal

basis over there.

See that's pretty special, to have an orthogonal basis in

the row space that goes over into an orthogonal basis --

so this is like a right angle and this is a right angle --

into an orthogonal basis in the column space.

So that's our goal, is to find -- do you see how

things are coming together?

First of all, can I find an orthogonal basis

for this row space?

Of course.

No big deal to find an orthogonal basis.

Graham Schmidt tells me how to do it.

Start with any old basis and grind through Graham Schmidt,

out comes an orthogonal basis.

But then, if I just take any old orthogonal basis,

then when I multiply by A, there's no reason why it should

be orthogonal over here.

So I'm looking for this special set up where A takes these basis

vectors into orthogonal vectors over there.

Now, you might have noticed that the null space I didn't

include.

Why don't I stick that in?

You remember our usual figure had a little null space and a

little null space.

And those are no problems.

Those null spaces are going to show up as zeroes on the

diagonal of sigma, so that doesn't present any

difficulty.

Our difficulty is to find these.

So do you see what this will mean?

This will mean that A times these v-s, v1,

v2, up to -- what's the dimension of this row space?

Vr.

Sorry, make that V a little smaller -- up to vr.

So that's -- Av1 is going to be the first column,

so here's what I'm achieving.

Oh, I'm not only going to make these orthogonal,

but why not make them orthonormal?

Make them unit vectors.

So maybe the unit vector is here, is the u1,

and this might be a multiple of it.

So really, what's happening is Av1 is some multiple of u1,

right?

These guys will be unit vectors and they'll go over into

multiples of unit vectors and the multiple I'm not going to

call lambda anymore.

I'm calling it sigma.

So that's the number -- the stretching number.

And similarly, Av2 is sigma two u2.

This is my goal.

And now I want to express that goal in matrix language.

That's the usual step.

Think of what you want and then express it as a matrix

multiplication.

So Av1 is sigma one u1 -- actually, here we go.

Let me pull out these -- u1, u2 to ur and then a matrix with

the sigmas.

Everything now is going to be in that little part of the

blackboard.

Do you see that this equation says what I'm trying to do with

my figure.

A times the first basis vector should be sigma one times the

other basis -- the other first basis vector.

These are the basis vectors in the row space,

these are the basis vectors in the column space and these are

the multiplying factors.

So Av2 is sigma two times u2, Avr is sigma r times ur.

And then we've got a whole lot of zeroes and maybe some zeroes

at the end, but that's the heart of it.

And now if I express that in -- as matrices, because you knew

that was coming -- that's what I have.

So, this is my goal, to find an orthogonal basis in

the orthonormal, even -- basis in the row space

and an orthonormal basis in the column space so that I've sort

of diagonalized the matrix.

The matrix A is, like, getting converted to this

diagonal matrix sigma.

And you notice that usually I have to allow myself two

different bases.

My little comment about symmetric positive definite was

the one case where it's A Q equal Q sigma,

where V and U are the same Q.

But mostly, you know, I'm going to take a matrix like

-- oh, let me take a matrix like four four minus three three.

Okay.

There's a two by two matrix.

It's invertible, so it has rank two.

So I'm going to look for two vectors, v1 and v2 in the row

space, and U -- so I'm going to look for v1, v2 in the row

space, which of course is R^2.

And I'm going to look for u1, u2 in the column space,

which of course is also R^2, and I'm going to look for

numbers sigma one and sigma two so that it all comes out right.

So these guys are orthonormal, these guys are orthonormal and

these are the scaling factors.

So I'll do that example as soon as I get the matrix picture

straight.

Okay.

Do you see that this expresses what I want?

Can I just say two words about null spaces?

If there's some null space, then we want to stick in a

basis for those, for that.

So here comes a basis for the null space, v(r+1) down to vm.

So if we only had an r dimensional row space and the

other n-r dimensions were in the null space --

okay, we'll take an orthogonal -- orthonormal basis there.

No problem.

And then we'll just get zeroes.

So, actually, w- those zeroes will come out

on the diagonal matrix.

So I'll complete that to an orthonormal basis for the whole

space, R^m.

I complete this to an orthonormal basis for the whole

space R^n and I complete that with zeroes.

Null spaces are no problem here.

So really the true problem is in a matrix like that,

which isn't symmetric, so I can't use its

eigenvectors, they're not orthogonal -- but

somehow I have to get these orthogonal --

in fact, orthonormal guys that make it work.

I have to find these orthonormal guys,

these orthonormal guys and I want Av1 to be sigma one u1 and

Av2 to be sigma two u2.

Okay.

That's my goal.

Here's the matrices that are going to get me there.

Now these are orthogonal matrices.

I can put that -- if I multiply on both sides by V inverse,

I have A equals U sigma V inverse, and of course you know

the other way I can write V inverse.

This is one of those square orthogonal matrices,

so it's the same as U sigma V transpose.

Okay.

Here's my problem.

I've got two orthogonal matrices here.

And I don't want to find them both at once.

So I want to cook up some expression that will make the Us

disappear.

I would like to make the Us disappear and leave me only with

the Vs.

And here's how to do it.

It's the same combination that keeps showing up whenever we

have a general rectangular matrix, then it's A transpose A,

that's the great matrix.

That's the great matrix.

That's the matrix that's symmetric, and in fact positive

definite or at least positive semi-definite.

This is the matrix with nice properties, so let's see what

will it be?

So if I took the transpose, then, I would have -- A

transpose A will be what?

What do I have?

If I transpose that I have V sigma transpose U transpose,

that's the A transpose.

Now the A -- and what have I got?

Looks like worse, because it's got six things now

together, but it's going to collapse into something good.

What does U transpose U collapse into?

I, the identity.

So that's the key point.

This is the identity and we don't have U anymore.

And sigma transpose times sigma, those are diagonal

matrixes, so their product is just going to have sigma

squareds on the diagonal.

So do you see what we've got here?

This is V times this easy matrix sigma one squared sigma

two squared times V transpose.

This is the A transpose A.

This is -- let me copy down -- A transpose A is that.

Us are out of the picture, now.

I'm only having to choose the Vs, and what are these Vs?

And what are these sigmas?

Do you know what the Vs are?

They're the eigenvectors that -- see, this is a perfect

eigenvector, eigenvalue, Q lambda Q transpose for the

matrix A transpose A.

A itself is nothing special.

But A transpose A will be special.

It'll be symmetric positive definite, so this will be its

eigenvectors and this'll be its eigenvalues.

And the eigenvalues'll be positive because this thing's

positive definite.

So this is my method.

This tells me what the Vs are.

And how I going to find the Us?

Well, one way would be to look at A A transpose.

Multiply A by A transpose in the opposite order.

That will stick the Vs in the middle, knock them out,

and leave me with the Us.

So here's the overall picture, then.

The Vs are the eigenvectors of A transpose A.

The Us are the eigenvectors of A A transpose,

which are different.

And the sigmas are the square roots of these and the positive

square roots, so we have positive sigmas.

Let me do it for that example.

This is really what you should know and be able to do for the