Our last topic in this chapter is the pseudo inverse of a matrix.
So we're gonna start with a connection between a Gram matrix,
uh, and the matrix itself.
So it's this.
If you have a matrix A,
it has linearly independent columns if and only if its Gram matrix is invertible, okay?
So, um, what does it mean to say it has linearly independent columns?
It basically says that if Ax equals 0,
that implies that x equals 0, right?
Because this simply says that there's a linear combination of the coefficients- oh,
sorry, there is a linear combination of the columns of A
with coefficients given by xi, um,
is 0 and linear dependency says the only way
to do that is when all the coefficients are 0 and that's what this is,
so this is what we're- this is what- this is what it means, uh,
for the columns of A to be linearly independent.
Okay, now, to show this,
what we're gonna show is that Ax is 0, uh,
if and only if A transpose x- A transpose Ax is 0.
Now, these are different sizes, right?
If A is m by n, that is an m,
uh- that's- that's- that has size m. This has size n,
uh, in this case,
because that's an n times n, uh, system, uh,
matrix and then that's, uh- this is,
uh- and- and then the 0 on the right-hand side is also size n. Okay.
So let's do this,
um, so first of all,
suppose Ax equals 0, and if you like,
that means that there's a linear combination of the columns of A,
which is 0, um,
then we're gonna- we're gonna show that basically,
the same- if I multiply by a transpose Ax,
I get 0, so let's see.
So A transpose Ax,
I'm gonna re-associate that as a transpose times Ax,
ah, but Ax is 0,
so this is A transpose 0 and that's 0.
Okay. And so what this tells you is if the- if that says that if Ax equals 0,
then A transpose Ax equals 0, okay?
Now, conversely, suppose A transpose Ax equals 0,
um, then what we're gonna write is,
I'm gonna take this thing, uh,
which is an n vector,
and I'm gonna multiply on the left by x- x transpose,
and I'm gonna get 0 is- well,
x transpose times 0 is 0,
so, uh, I get 0.
Um, but I'm gonna re-associate this quadruple product in the following way.
I'm gonna rewrite that as- first,
I'm gonna write it as x transpose A transpose Ax,
and then I'm gonna re- uh,
I'm gonna re-associate it this way,
and then x transpose A transpose I will recognize as Ax quantity transpose, okay?
Ah, but wait a minute,
this is the transpose of a vector in a product with itself- or sorry,
that- times itself, right?
And that's the norm squared.
So this says that 0 is the norm squared of Ax.
Well, the only way you can have a norm or norm squared be
0 is if the- the argument itself is 0.
So that says Ax equals 0.
And so what this does is it tells us- uh,
it establishes that a has
linearly independent columns if and only if A transpose A is- is invertible.
Okay. So- so that's the connection between, uh,
a matrix and- and the- and the Gram- and its associated Gram matrix.
Okay. And now we can say- we can tell you what the pseudo-inverse of a tall matrix is.
Um, I should say that this is pretty standard, uh,
mathematical notation like everybody knows what a
pseudo- what a pseudo-inverse is. There's some other names for it.
It's also called, I think the Moore Penrose inverse.
Uh, that's especially if you- if you come from the UK,
uh, they were British mathematicians.
Um, and it's probably got some other names as well.
Um, oh, and its notation is this,
it's a superscript with a dagger.
And- and so in fact,
in- in informal speech,
you might say a dagger. So that's what it is.
Okay. And here's what it is and, you know,
these things get very complicated to parse,
but you've really got to be on your toes to make sure everything's cool.
It's A transpose A quantity inverse, A transpose, okay?
So, um, let's quick- let's do a quick syntax check.
Let's make A is m by n,
and let's just- let's just check that the dimensions make sense.
Okay. So A transpose is an n by m matrix.
Now, let's see.
Let's look at A transpose a.
That's the Gram matrix,
by the way, so A transpose A,
A is m by n. A transpose is n by m,
and so the result,
A transpose A is n by n. That's the Gram matrix,
it's n by n. And so this is- now,
the inverse of an n by n matrix is an n by n matrix,
so this is n by n, and sure enough,
we're cool because we're multiplying two matrices and the,
uh- the- the dimension in the middle is equal, okay?
So it's that. So the whole thing,
A dagger is an n by m matrix.
So A dagger kinda looks like the transpose, uh, right?
Because it's- it- it has the- it has the transpose of dimensions,
um, okay, and it's equal to this.
Now, so far, I- that means nothing to you and in fact,
it's not even gonna make- mean a whole lot to you now.
Um, actually in the next section of the course,
it's gonna make a- it- it's actually gonna mean a lot to you.
We'll get to that. Okay. Now, first thing to note about A dagger or A pseudo-inverse,
um, is that it is a left inverse of A,
uh, so let's just check.
Um, A- that means if I multiply it on the left,
um, if I multiply A on the left by A dagger, so if I do that,
I just plug this stuff in and I
re-associate this as A transpose A inverse times A transpose A,
but a matrix- any matrix times its inverse on the left is the identity.
So look at that.
So we now have a left inverse.
By the way, we have now shown something that, uh,
I mentioned a few lectures ago,
but did not, uh, actually, uh,
derive, uh, and that is that if a matrix has independent columns,
then it has a pseudo-inverse and now we can be very explicit.
It's like here's- by the way,
it can have- it will have multiple pseudo inverses if it's tall,
but the point is it has at least a pseudo-inverse and in fact,
there's a simple formula for it.
It's A transpose A inverse A transpose.
Um, so- so that's- that's now established.
That was something left open from a couple lectures ago.
Um, now, there's some,
um, uh- by the way,
it- it's very easy to get into trouble with these kinds of equations, right?
Like- like- like that.
Um, it's just too easy to just look at it, not be present
or not be thinking about what it means and all of a sudden,
you're in big, big trouble.
Um, and to- to do that,
I'm- I'm gonna work out- we're gonna see what the pseudo-inverse is when A is square.
So if A is square,
then A dagger is equal to A transpose A in parentheses,
uh, quantity inverse times A transpose.
Now, because A is squared,
I'm gonna- I can actually say that A transpose A is
the product of two square matrices inverse.
That's the inverse- that's the product of the inverses in reverse order.
So this is A inverse times A transpose inverse,
that's slang for A transpose inverse,
is A minus T or something, uh,
like that, and then multiplied by A transpose.
Um now, this is the identity and it goes away,
so you get A inverse.
So we can think of the pseudo-inverse, uh,
as a- as a generalization of an inverse, uh,
to the case when a matrix A is top, let's say.
Oh, and I should say has indip- linearly independent columns,
then that- that's what the pseudo inverse is and indeed it's a left inverse of that.
So, okay, so that- that is- that- later we're gonna find
out that it's actually much more special than just merely A left inverse.
It's got some very special properties,
but for now we'll just, uh, leave it this way.
That's what the pseudo-inverse is.
Um, I should also say that you know,
all languages for manipulating, uh,
matrices, all packages and languages will indeed
have some function that carries out the pseudo inverse.
Okay. Now, we also have the pseudo inverse of a wide matrix.
So, A is wide then um,
AA transpose- that is by the way the Gram matrix of A transpose um, that's invertible,
and the pseudo-inverse is then defined this way;
it's a transpose times AA transpose quantity inverse.
Now, again, you have to be so, uh,
careful with these things because you can write down stuff like
this and it's either meaningless or wrong.
That's extremely, so you got to be very careful.
So this requires A to be wide with linearly independent rows otherwise,
this makes absolutely no sense.
It's just like parts of it are just wrong.
Like things are not invertible, all that kinda stuff.
Okay. Now, not surprisingly, a dagger,
the- the pseudo-inverse of
a wide matrix with a linearly independent rows is a right inverse.
The same way A dagger was a left inverse when A
is tall with linearly independent columns and you just check that.
You just multiply a dagger on the right,
you know, so I multiply A, uh,
times this expression and sure enough I get AA transpose times AA transpose inverse.
Um, and that's the identity. So that's it.
Okay. And once again,
it too produces to A inverse,
uh, when A is square.
Okay. So by the way,
this calculation here, expanding AA transpose and writing it as A, uh,
AA transpose is A minus transpose times A inverse,
um, that would be a terrible crime if A were strictly wide.
Um, if A is square and invertible or has,
you know, linearly independent columns,
this is cool, but uh, if it were,
if A were wi- strictly wide,
this would be a terrible crime.
The crime- there'd be many crimes committed here.
One is that you can't have a non-square matrix,
you can't have an inverse of it.
Sorry, it's a- you'd be in big trouble right there.
Now it turns out that the pseudo inverse we can get it.
It's very closely related to the,
uh, to the QR factorization.
Let's see how that works.
Um, so let's suppose A has
linearly independent columns and we form a QR comp- decomposition now,
because it has linearly independent columns, Gram-Schmidt,
if we use that to calculate QR is going
to succeed and that means we're going to end up with a matrix Q,
the same size as A.
And it's gonna- its columns are going to be orthonormal and R is upper triangular.
It's upper triangular and it's,
um, with positive entries on the diagonal.
Okay, now, let's work out what is a transpose A. Well, A is QR.
So I just go QR, paren transpose, QR,
and now I use the fact that the product- the transpose of
the product is the transpose- is the product of the transpose in the reverse order.
So I get over here.
Uh, here I get R transpose Q transpose QR.
Ah, the Q transpose Q is i. It's the identity.
Because in fact, that- that is precisely
equivalent to saying the columns of Q are orthonormal.
So that's an identity in the middle,
it goes away and I end up with R transpose R. Okay.
Interesting. Now, let's take a dagger.
A dagger is A transpose A quantity inverse A transpose.
But we just worked out A transpose A is R transpose
R. And so this is R transpose R inverse QR.
Now, A is- can be tall,
so I certainly cannot expand things and write A inverse,
but R is square and invertible.
So this thing I can for sure use the rule that says that
R transpose times R quantity inverse
is the inverse of R times the inverse of R transpose.
And so I get this.
Oh, and then this is QR quantity transpose.
That's the same as the tran- the product of the transposes is in reverse order.
And so this is- this is R transpose Q transpose. So I get there.
And what happens is in the next formula,
I have an R transpose inverse.
And an R transpose that line up next to each other,
they annil- annihilate each other.
The product is the identity and that just goes away and I get R inverse Q transpose.
Okay. Uh, so uh,
so that's- this is a very cool formula.
It's just R inverse times Q transpose.
That- that's the formula for the pseudoinverse of A of A tall, uh, matrix, right?
Linearly independent columns or tall or square, does- doesn't matter.
Um, okay, now that means I can actually
calculate the pseudo-inverse because I could just do this.
To do that, I'm going to- I'm going to calculate A dagger times e_i.
That's gonna give me the ith column of a dagger.
And to do that, I'll simply write it as R inverse times Q transpose e_i.
Okay, So now I see what we do.
We do a QR factorization.
You do a QR factorization on A. Um,
then you take the columns of Q transpose. That's these things.
And for each of those,
you do a back substitution.
And this will give you, uh, the A dagger, right?
And- and it will give you, uh,
it will give you this because you'll compute it column by column.
So that's- that's out there, okay.
So that, um, that is the QR factorization.
Um, I- I should say this- this
finishes a section of the- an entire section of the course.
Um, we've seen vectors, matrices,
uh, the concept of inverses and solving linear equations.
And we even know how to do it.
Uh, when I should say
various matrices have linearly independent columns or are invertible if it's square.
Um, so that's where we are so far.
So you know some- you know,
some things and you can do some useful things.
Um, I should say that the course is about to get much more
useful in the next section when we talk not about solving equations,
uh, but about solving equations approximately.
Um, and that's going to be coming up as the next section of the course.