Well now we have the idea of multiplying matrices.
Uh, we'll see now that a matrix is square,
you can multiply it by itself,
and that's gonna give you the square matrix.
And you can multiply it by itself again,
and you're gonna get the cube of a matrix.
So basically you're going to have the idea of matrix powers.
Let's take a look at that now.
So of course it only makes sense if A is square.
So- otherwise you can't multiply A by itself or something like that.
So, if A is square,
then A squared simply means AA.
And the same for higher powers.
So for example, A cubed is A times A times A,
and as we know,
it doesn't matter which order you multiply it in.
So that's- that's- that would be.
And we've got to denote it as A cubed.
Now notice here that we're doing some- uh,
some overloading of notation again.
Because if someone walks up to you on the street and says A cubed and A is a number,
then you know what it is. It's the cube of the number.
You multiply the number by itself three times, all right?
But here we're doing the same thing except A is a matrix.
Uh, so but again, it makes perfect sense,
so that these are the matrix powers.
Um, now again, uh,
to- uh, to- to,
it's going to be useful to uh,
introduce the notation to define A to the 0 as the identity.
Now, notice that that's like for a number raised to the 0 power you get 1.
And I is something like- uh,
I is something like the matrix analog of the number 1.
Well, in fact, of course,
when I is 1 by 1, it is the number 1.
Okay. And if you do that,
then you get this very nice thing that you know,
that's an identity that you know,
holds for numbers, all right?
That if I- if I multiply the K_th power of a number times the L_th power number,
I get the K_th plus L_th power of the number.
But the same is true for- for- for matrices as well.
A square matrix. If I take a square matrix, I take it to the K_th power,
I multiply it by the same matrix to the L_th power,
I'm going to get uh,
the same- the original matrix to the K plus L power.
Okay, now, later in this- in this book and course,
we- we're going to see negative powers.
Uh, for example, we're going to see,
you know A inverse uh,
which is going to be, well, the inverse of the matrix.
That's actually one of our next topics.
Uh- uh, In more advanced courses,
you will see weird things like this square root of a matrix.
Like, you know, A to the one-half, all right?
And you'll see all sorts of other crazy stuff like that.
We're not going to be talking about fractional powers in this course,
although they do- they do come up uh,
in- in some applications.
But we will be talking about inverses. That's later.
For now we're just talking about positive powers or the zero power,
which by convention, is the identity of a matrix.
Okay. Why don't we just do a quick example.
Let's just start with like, you know 1 uh,
minus 1, 2, 0, that's A.
And so A squared uh, in that case uh,
let's work out A squared.
Well, that's going to be 1 minus 1, 2,
0 times 1 minus 2,
0, You just simply multiply the two together.
And when I multiply that out,
the first one gives me 1 minus 2,
that's minus 1, 1 times minus 1,
0 is minus 1.
Uh. this times that is 2 times 1
plus that's going to be 2 and this is going to be minus 2.
Okay? So the square of this matrix is that matrix there.
Okay? So just- just- just so we can see what it- what it looks like.
Okay? So A lot of cool applications of it.
We're going to look at one that involves directed graphs.
So actually, you remember that several lectures ago we looked at
directed graphs and we looked at the nodes and edges.
There's another way to describe a directed graph which
does not explicitly enumerate the edges.
So here's a directed graph right here.
Actually they're- they're closely related.
If you look in the book, you'll see how uh,
the description when we enumerate and label the edges can be converted to this one.
So that was the uh, incidence matrix.
This is the adjacency matrix, okay?
[NOISE] And it's n by n. So here I have five nodes in my graph,
and we simply define the adjacency matrix of a graph this way, Aij is 1.
If there is an edge from vertex j to vertex i.
Notice it kind of goes backwards, all right?
Because Aij, you'd think it might be from i to j,
but in fact it's from j to i. And I should also admit
to you that there are people who use the opposite convention so that
the adjacency matrix is
Aij equals 1 means that there's an edge from 1 to, from i to j.
But for us it's j to i.
Okay? And of course the two are just related by transposing.
Okay, so here's an example- here's a matrix.
And now let's take a look at, let's audit a few things like oh,
well, we could do all sorts of cool things.
Here's an- this edge goes from 3 to 2.
So that means that A,
2, 3 should have a 1 in it.
And sure enough, it does.
Let's go the other way. Let's find this.
That says that A,
5, 4 is 1.
That means there should be an edge going from node four to node five.
Let's see if that's true.
It is, indeed, and that's the very edge it is.
And let's just audit one more just to make sure everything's cool here.
Let's audit this 0 here, that says that A,
4, 2 equals 0.
And that tells us there is not an edge going from node two to node four.
And that is indeed the case.
There is no edge going from here to here.
Okay? So that's the idea.
That's- that's the uh,- this is called the adjacency matrix of a graph.
It's also, by the way, an absolutely standard mathematical concept
and- and- kind of universal.
Okay, now let's look at the square of the adjacency matrix.
It's super interesting.
It is this um,
the ij entry of the square of an- well,
of any matrix is this.
It's the sum from k equals 1 to n, Aik, Akj.
But let's figure out what that means.
Well, it says.
We sum over all nodes and we take the product of Akj and Aik.
But- but these Akj and Aijs,
the Aik and Akjs, they're either 0 or 1.
Okay? So basically, usually this product is
0 because one of them is 0 or both of them are 0.
Okay? However, there is a way when you get 1.
You get a 1 if Akj is 1 and Aik is 1.
But that has a specific meaning.
If Akj is 1,
it says there's an edge from j to k and
Aik is 1 that only happened- that means there is an edge from k to i.
Okay? And so basically, you get a 1 whenever there is an-
there is an edge from j to k and also from k to i.
Now by the way, two edges that uh,
where one goes from one node to another and
then another one starts from that node and goes to the other one.
That's called a path of length 2.
Okay? So for example, in this graph,
you know, let me get you a path of length 2. Here's one.
You go uh, from here to here,
uh, and then you go from here to here.
So from- there's a path from node five to node 2 of length 2,
and you go along this edge and then that edge.
Now notice that the path has to go in the direction of the arrow.
This is a so-called directed graph.
Okay? So, what this says- what our analysis up here says is actually kind of amazing.
It says that when you square the adjacency matrix,
the numbers in that- the numbers in the entries tell you how many paths there are uh,
that go- of that length,
of length 2 that goes from j to i.
In fact, that's a beautiful interpretation of an adjacency matrix.
An adjacency matrix tells you how many paths there are of length 1.
That just means, a path of length 1 is just a path.
And they're either 0 or there's 1.
0 if there's not an edge, 1 if there is.
So this is consistent. But the square is already kind of interesting. Um.
And so for example,
I will spare you the details and
not to mention that I would almost certainly get it wrong,
but if you squared this matrix here
you would get- [LAUGHTER] assuming there's no typo here.
Yeah, but maybe there's not.
Um, you would get this matrix here.
Super interesting and it's got- it's got 0s, 1s, and 2s.
You know, that makes sense, uh,
because if we talk about the numbers of paths of length 2, um,
sometimes there's not a- there's not a path of length 2,
and that means there is a 0 here,
but we can audit a couple of these.
Um, I don't know. Let's go from node 4-3, um,
and that's gonna be the A 3, 4,
that is right here, and it says it's 2.
So apparently there are two paths of length 2 that go from node 4 to node 3.
So let's- let's- lets see if this is true.
Well, that was the drum roll,
and we're gonna go- we're gonna go paths of length 2 from 4-3.
Okay. So we're gonna go from 4-3,
and there's- here are the two paths of length 2.
One is you go from 4-3 and then you go on this- oh,
I should say, that's called a self-loop.
It's kinda cool. You can have a loop that goes from
yourself- from yourself actually to yourself.
That's called the self-loop.
Okay. So that's a path of length 2.
Here's another path of length 2 that goes from 4-3.
First, you go to 5,
that's your intermediary node, and then you go on to 3.
So it's cool, and there are no others,
uh, that's what this is telling you.
Okay? So that's- that's what this tells you,
and so more generally,
if I take the l_th power of as- of a matrix,
which is the adjacency matrix, um,
then it's fully interpretable as, uh,
the ij entry as the number of paths of length l from j to i. Um,
so that's what this is.
Um, uh-huh, there's- there is a small typo there.
Oops. Okay, um, good.
Um, our last topic is to show that we can use, uh,
this powerful matrix notation to super compactly,
ah, describe the QR factorization, not the algorithm,
but the result, uh, sorry, Gram-Schmidt,
and it basically turns out the Gram-Schmidt can be interpreted as a matrix factorization,
and the truth is that most people think of it that way.
They- um, everyone has heard of the Gram-Schmidt, you know, algorithm,
but mostly people think of it as a factor- as a matrix factorization,
which is called the QR factorization.
Let's see how that goes. Well, um,
so what I'll do is I'll take a matrix A,
it's gonna have- uh,
it's gonna have have, ah, k,
ah, columns, a_1 through a_k, and they're n-vectors.
I'm matching the notation from Gram-Schmidt, okay?
So A- A has dimension n by k. Now,
if the columns are linearly independent and I run Gram-Schmidt,
then I get, uh, some orthonormal vectors,
those are q_1 through q_k, okay?
Um, and I'll define a- an n by k matrix Q,
and it's going to have these columns, right?
Now, uh, we can very compactly say that
the columns of Q are orthonormal. That's this equation.
It says that the Gram matrix of the q's is the identity,
and the- on the diagonal it says that the q's have norm 1 on the off-diagonals,
it says that the q's are mutually orthogonal.
So this- you will- you will- henceforth,
when you see the equation matrix transpose times matrix equals i,
you will know basically what it's saying is the columns of that matrix are orthonormal.
Okay. [NOISE] Now from the Gram-Schmidt algorithm,
it says if a_i is equal to, uh,
this- that's a linear combination of q_1 up to q_i, okay?
Um, oh, by the way,
where the coefficient of q_i is actually positive because q_i tilde it's pos- I- sorry,
q_i tilde is non-zero and the norm of q_i tilde is positive.
Um, and so we're going to simply call those,
you know, R_1i up to R_ii, okay?
Um, now, notice that a_i is a linear combination.
You don't need more- you don't need q_i plus 2,
q_i plus 1, these things,
it's- it's not, they're not,
and so what that tells you is that R is upper triangular,
the matrix R, because we'll take it to be 0 for all the other entries.
Um, and then what happens is, ah- is this,
you can write this equation out in- as this factorization.
It says that, you know, A, here's A,
equals, ah, Q, here's q, times R, right?
And not only that, R is itself,
R is upper triangular,
so it's only got entries here,
and on the diagonal it's got positive entries,
um, so that's- that's the picture.
By the way, this drawing I'm doing here is actually a useful thing to do.
It kinda shows you the dimensions
and allows you to keep them in mind and things like that.
Okay. So summary on this is that the- when you
carry out Gram-Schmidt on a sequence of vectors, um,
[NOISE] and if- if you think of the- those vectors as being the columns of a matrix,
that's the same as factorizing that matrix into a product Q and R.
Q has columns that are orthonormal and R is
upper triangular with positive entries on the diagonal.
And- so actually people refer to, you know,
QR factorization Gram-Schmidt, um,
interchangeably, they're not quite the same.
Gram-Schmidt is- is if you like Gram-Schmidt is
an algorithm for computing the so-called QR factorization,
but this is how a lot of people would- would- would talk about it.
Also, I guess if you look in numerical packages for a linear algebra,
you probably wouldn't hear anything about, uh, Gram-Schmidt, um,
however, you would for every single such package,
will have a QR factorization,
which of course is nothing but Gram-Schmidt expressed in matrix notation.
Okay. So this is the QR- so-called QR factorization of A, um,
and it- right now,
you can see that there's no reason for you to have any interest at all in it.
Uh, right now, in fact, Gram-Schmidt,
I think is a bit mysterious.
Gram-Schmidt- the only use Gram-Schmidt has at this point in the book, it's only one,
is it's a way to- to computationally
determine if a set of vectors is linearly independent, okay?
Now, to which I am comp- I am fully admitting the following.
There is no reason you should care about that at this point because, like,
I don't know, what- what does it mean for vectors to be linearly independent,
does it mean the bridge doesn't fall down?
I don't know. We'll see later if then it's gonna have a lot of important things,
but for right now I'm just admitting it has no interest.
Very soon you will see that this is actually gonna
be- it's going to have a lot of practical implications.
I'm just admitting that we haven't seen them yet.