
Title:
Matrix Multiplication  Intro to Algorithms

Description:

Just as a quick aside, if you're familiar with matrix multiplication,

there is a very nice connection between this little algorithm

that we're just working on and matrix multiplication.

To appreciate that, the first thing you need to understand is that

if we can represent a graph on a set of nodes as a matrix

and it's a matrix that consists of all 0s and 1s and if it's a sparse graph, say mostly zeros.

But if there's a link between node I and node J,

then the corresponding position in the matrix has a number in it, number 1.

That 1 there means that there is a link from I to J.

The graphs that we've been talking about links are bidirectional.

So if there's a 1 in this IJ position, then there is also a 1 in the JI position,

which in this picture seems like it'd be really nearby, which means that this matrix is symmetric,

and I'm not going to get into matrix terminology but again if you're familiar with it,

you'll recognize what a symmetric matrix is.

The matrix equals a its own transpose if you flip things the other way.

So basically it's natural, it means for just interchanging the nodes

since the connections are bidirectional, we'll have the same matrix again.

So let's call this matrix (M) and let's think about what it means to multiply (M) times itself.

In matrix multiplication, the way we fill in the IJ entry of the product,

we take the I row of the first matrix and J column of the second matrix

and I always need two hands whenever I think about matrix multiplication

and you across this one and down this one at the same time.

And what we do in this case since it's all zeros and ones and it's a square matrix,

but what we're going through and figure out.

Anywhere where there is a 0 and 1, and a 0 and the other, it's going to be 0.

Only if there is a 1 in both, is it going to be a product that's not 0.

So this multiplication of this row times this column is exactly a count of the number of 1's

that the two vectors have in exactly the same positions.

What does it mean for them to have a 1 in the same position? Let's check.

Let's imagine that there is a 1 in position K here and at the same time in position K here.

This position here means that our graph had a link from I to K.

There, that's what this means that there's a 1 there.

And similarly, if there's a 1 in this position, it means that very same graph that we're talking about

this graph that (M) is representing also has a link from K to J

and what we're doing is counting up all the Ks that have the property

that they would take as you can get from I to one of those and then to J from one of those.

It's going to add all those up. That's exactly what matrix multiplication does.

This value here is going to be filled in with precisely the number of 2step path from I to J

which is exactly what we needed in that other example hat we're basically counting up

the comic books that are uncommon between some character I and some character J.

In the case of the bipartite graph of the Marvel comic book characters,

any 2step path that starts at a character goes through a comic book and then a character.

So this is counting up exactly the number of comic books that I and J are both in.

There we go, the square of the matrix which represents

the connections of the graph actually gives us the same answer.

The running time of this algorithm, of course, is n³,

because we're looping through for each of the entries of this matrix that we're going to fill in

and there's n² to them, we're doing this row by column multiplication which also takes time in.

So it's in cubed. The algorithm that we've just been talking about.

Something more like number edges times the number of nodes.

The number of edges here comes from the fact that we loop over

each of the character book combinations that we have stored explicitly.

And then for each of those, we examined which characters are there connected to it.

It could be as bad as N*M. If (M) is dense matrix, then this is (N)²,

so this algorithm ended up being in cubed again, but if it's a sparse matrix,

so the number of edges is linear like in a planar graph, for example,

then this is (N)² which is actually a lot better.