Incidence Matrices of Graphs

• Download this transcript - PDF (English - US)

GILBERT STRANG: OK. I want to continue the last video, which was about incidence matrices, and graphs, and networks, and flows in the network. So that was 5.6. This is 5.6b.

And I'll remember the same graph. You remember a graph is some nodes, four nodes here, and some edges, and in this case five edges. So I have a 5 by 4 matrix, and that's what it was.

And I'll remember how it was created. Every row corresponds to an edge. So the first edge there goes from node 1 to node 2, so I put a minus 1 and a 1 in columns one and two. That tells me what that first edge is doing and it gives me one row of the incidence matrix. Five edges give me five rows. There is the matrix.

And here I'll multiply by v, thinking of a vector v as voltages at the four nodes, and I get that answer. The 1 and minus 1 produce this kind of answer. OK.

Now I'm ready for questions about the matrix A, the 5 by 4 matrix. These matrices, these incidence matrices, are beautiful examples of rectangular matrices where we can ask all the key questions about a matrix and get a nice answer. And the key questions that I have in mind are what are their solutions to Av equals 0? Are there--

That says, are there are combinations of the columns that give the zero column? So it's asking, are the columns dependent? If the columns were dependent, then I'll find some solutions, and here I will. If the columns are independent, the only solution I will find will be v equals 0.

But those columns are dependent. Now, how can we see that? Well, in this case, we can find a solution to Av equals 0, because I can see how do I get all those differences to be 0? Well, not hard. v could be the vector of all 1's. Then the differences would all be 1 minus 1, would all be 0. I would be solving Av equals 0.

And of course, I can multiply by any constant. The voltage is-- So all I'm saying is if all the voltages are equal, there won't be any flow. If all the voltages are equal and I don't have any batteries or other sources in the network, there will be no flow. And those are all the solutions. But the only way I could make all those 0 would be for all the v's to be the same.

So all the v's have to be the same. v is C, C, C, C.

And I learn something important. Av equals 0 has some solutions. And I'll just jump ahead one electrical moment. That's not good if we want an invertible matrix. In the end we would have A transpose A and it won't be invertible unless we do something.

And what do we do? We want to get rid of that last column. We can have three columns. Those will be independent, but that fourth column is a combination of the others. And what we do, in reality, is we ground a node, which means we set one of the v's, maybe v4, if we set that to 0, it's like we're fixing the temperature, we're fixing the voltage, we often have to do this on a sliding scale.

If we only know differences in temperature, we have to say, where is 0? And if we make that point 0, then we have only three unknown voltages and a 5 by 3 matrix and all well. OK. So that's the discussion of Av equals 0.

Now, what about A transpose w equals 0? So now I'm asking about the transpose of that matrix. Now, this is a 4 by 5 matrix. Again, a beautiful example, 4 by 5 matrix. w, of course. It's a 4 by 5 matrix multiplying w, which is 5 by 1. So 4 by 5 times 5 by 1. And I want to get all zeros, four zeros this time. Right.

So first of all, if I have a 4 by 5 matrix, so when I transpose this is you could say short and wide, I think there are automatically solutions. There will be solutions in a 4 by 5 matrix. With five unknowns and only four equations, I'm going to have some solutions to that system. So there will be some solutions. Well, the question is how many different w's could I find, how many different solutions, and what do they mean.

And that's the beauty of this example, that it's not just a bunch of 20 numbers in the matrix. The matrix has a meaning. The incidence matrix takes differences A to Av is differences in v, but what's the meaning of A transpose? That's the key question here. Why is this equation very important? OK.

So I have to tell you the meaning of A transpose. And maybe I have to copy down what A transpose is. So let me go to the next board and copy down A transpose. So I'm looking now at A transpose w. So now it will be 4 by 5. So that first row becomes a column. The second row becomes another column in the transpose. The third row, another column, the fourth row, is that column. And the fifth row is that one.

And that will multiply w1, 2, 3, 4, and 5 to give 0, 0, 0, 0. And that's called the current law, Kirchhoff's current law.

And what is that law? What does it mean? It means that in the network at a typical node, so at node 1, you remember, there was an edge out. Edge 1 went out. Three edges went out actually. This was to node 2. This was to node 3, and that was to node 4. At node 1, three edges are going out. And what does the current law tell me? It tells me that the total flow out is 0. The net flow, any flow in, which would be negative w's, and any flows out, which would be positive w's-- w, that came from the first edge. This was maybe the second edge. And I think that happened to be the fourth edge-- flows out of w.

And that's what I see here. A 1, a 2, and a 4 are multiplying w1, w2, and w4 are the-- The first equation there is minus. w1 plus w2 plus w4 equals 0. So that came from the first row of A transpose w equals 0. Right?

I just took those numbers from the first row. I wrote down that first equation. And you see it says exactly the sum of those three flows has to be 0.

So if there's some positive flows going out, there must be some negative w's coming in to balance. OK. And that was at node 1, and similarly at nodes 2, and 3, and 4, currents balance. It's the balance equation.

Kirchhoff's law, it's the balance equation. It's conservation. A fundamental equation in modeling applied mathematics is if a body is sitting there in equilibrium, then the forces on it are in balance. If I have steady flow around the network, the currents are in balance. Always there's a balance equation, so that things are not collecting up at a node. It's stable. OK.

So that's the meaning of Kirchhoff's current law. That's the meaning of A transpose w equals 0.

And what about solutions? Solutions w. Now, so now we're getting down into the details. Can we actually find the w's? Well, there will be some. There will be some.

As I said, we've got five unknowns here and only four equations. So we're certainly going to find a solution. And let me suggest one good way to look for it.

Suppose the flow-- Let me put in the other two edges-- suppose the flow goes around a loop. Loops are the key here. The key to the solution is a loop. So that's a flow that sends a flow of 1 along that edge, a flow of 1 going that way along that edge, which I think was w5, and a flow of 1 going that way.

Pay attention. It's going to send 1 Amp around the loop. I go with the arrow, with the flow, this way and this way, but this one is against the arrow. So I'm thinking that a solution is w1 equals 1.

You see I'm writing down a solution without doing any elimination or other linear algebra. I'm just understanding the picture. w1 is 1. w5 is 1. w5 is 1. And what is w4? Negative 1, because it's going against the arrow.

And the other two w's are 0, w2 and w3. This was w3 here. Those are not involved in this loop.

So there is a solution with w2 and w3 equal to 0. And I think that how could it fail on Kirchhoff's current law? Nothing is piling up at a node. We're just sending it around a loop. And of course, I put in that's a 1. w2 is a 0. w4 is a minus 1. I have a 1 and a minus 1. I get 0, just right. And all the equations would be solved.

In other words, conclusion, the solutions w come from loops in the network. Every loop in the network gives me a w.

Here's another loop. I could send flow down there. Now that would be a w4 plus 1. This way. This way. Do you see that second loop? Let me draw my little loopy symbol. Flow going around that loop. That loop happens to have four edges on it. So I'd have four w's. 1 minus 1, 1, and minus 1, and no flow on edge 1, and I would have another solution. And it would be a different solution.

So I'm going from-- Can I insert here two loops? In that graph I see two loops, two small loops. And each of those small loops gives me a flow, a w, that solves the current law, because it's just continuously running around and around.

Now, there's another question to ask you, and that is what about the big loop, w1, w3-- I think that is-- and minus w2? What if I send flow around the big loop? No problem. That gives me another set of w's . Those satisfy Kirchhoff's current law. They satisfy these equations. They satisfy A transpose w equals 0.

But I don't want that big loop. I don't want to include that in my list of w's, because I was only looking for two w's. I was only looking for two w's.

And linear algebra told me that was the number to look for. And here you're suggesting-- I'll blame you-- a third around the big loop. So what's up? Well, do you see it? The flow around that big loop does solve A transpose w equals 0, but it's not new. It's the sum of a flow around that loop plus a flow around that. Do you see?

If I add together the flow vector, the loop vector for w for that loop and for that loop, they will cancel on the edges that are in both loops, and I'll just be left with the flow there, the flow there, and the flow there, and that's the big loop.

In other words, that big loop doesn't give me a new vec-- It doesn't give me-- It gives me a vector w that's a combination of what I already have. And in linear algebra, that's always the question. You want the number of independent w's, and this big loop is a dependent w, because it's a combination of the other two. OK.

So that's the picture for one particular example. I'll just end with linear algebra facts, linear algebra facts. OK.

So how many-- So if I have an m by n matrix, and suppose Av equals 0 has how many independent solutions shall I say? k independent solutions. And in my example, the incidence matrix, the answer was, for A equal incidence matrix, k was 1.

So if I know the number of solutions to that equation, then how many solutions do I expect to-- This has-- So how many solutions do I expect there?

The difference between m and n comes in it, and then plus k. So independent solutions.

That's a basic fact of linear algebra that I never wrote down before. I never wrote it in this notation. I'll make that a question on a future linear algebra exam.

What I'm saying is that if I know how many solutions Av has, how many combinations, these are combinations of the columns of A that give 0, then I know how many combinations of the rows of A.

Let's just check that this counting theorem was correct. This was k equals 1, right? The only solution to Av equals 0 was the constants, 1, 1, 1, 1. Then m was 5. n was 4. k was 1. 5 minus 4 plus 1 is 2. And that's the number of loop solutions to Kirchhoff's current law. OK.

We have voltages. We have currents. And there's a lot of beautiful linear algebra involved with these matrices.

I'll also include a video about RLC circuits, which are totally an application of this. And there I'll begin with just one loop, one RLC loop. But the reality of modern electronics is thousands of nodes, thousands of edges, maybe tens of thousands of edges, and many, many loops.

Good. Thank you.

Free Downloads

Video

• iTunes U (MP4 - 44MB)
• Internet Archive (MP4 - 44MB)

Subtitle

• English - US (SRT)