142 2.4 GRAPH MODELS AND KIRCHHOFF’S LAWS

Page 1

142

Chapter 2 A Framework for Applied Mathematics

2.4 GRAPH MODELS AND KIRCHHOFF’S LAWS

This section will develop the most important model in applied mathematics.

We begin with a graph, consisting of n nodes connected (or not) by m edges.

Those connections are recorded in an m by n “incidence matrix” A. In row j of A,

the nonzeros −1 and 1 indicate which two nodes are connected by the jth edge.

A line of springs is a special case. Then A is a first difference matrix, and A

is a second difference matrix (it has −1, 2, −1 on the inside rows). I can name right

away the key matrices for any graph, starting with the “Laplacian” A

Graph Laplacian

A = D − W = (diagonal) − (off-diagonal)

(1)

W is the adjacency matrix and D is the degree matrix. The number w

tells

whether nodes i and j are connected by an edge. The number d

tells how many

edges meet node j. For four springs, A

A is the free-free second difference matrix B

A =

⎡

⎢

⎣

1 −1

−1

2 −1

−1

2 −1

−1

⎤

⎥

⎦

W =

⎡

⎢

⎣

0 1

1 0 1

1 0

⎤

⎥

⎦

D =

⎡

⎢

⎣

⎤

⎥

⎦

Laplacian

Adjacency

Degrees

For other graphs the edges are no longer in a line, and A

A is no longer tridiagonal.

You will expect A

CA to appear, when C is a diagonal matrix of m weights:

Weighted

Laplacian

CA = D − W = (node weight matrix)−(edge weight matrix) (2)

If three edges in a line have weights a, b, c in C, those numbers enter W and D:

CA =

⎡

⎢

⎣

−a

−a a + b −b

−b

b + c −c

−c

⎤

⎥

⎦

W =

⎡

⎢

⎣

0 a

a 0 b

b 0 c

c 0

⎤

⎥

⎦

D =

⎡

⎢

⎣

a + b

b + c

⎤

⎥

⎦

Weighted Laplacian

Edge weights

Node weights

Notice especially the sums along every row of these matrices:

Row sums of W are in D

Row sums of A

A and A

CA are zero

Those zero row sums put (1, 1, 1, 1) into the nullspace of A and A

A and A

CA.

These are great matrices to work with. This section creates the matrices; Section ∗ 2.9

on Graph Cuts and Gene Clustering uses the eigenvalues.

Page 2

2.4 Graph Models and Kirchhoff’s Laws

143

The graph in Figure 2.16 shows m = 6 edges connecting n = 4 nodes. This is a

complete graph (all possible edges). It is also a directed graph (each edge has a

direction arrow). Those arrows will determine the signs in the incidence matrix A,

but they don’t affect A

A or A

CA. For this graph model, our framework can have

three equations or two or one:

e = b − Au

w = Ce

f = A

[

−1

][

]

[

]

CAu = A

Cb − f

(3)

These equations will soon extend to finite differences and finite elements for differen-

tial equations. I think of (3) as the “fundamental problem of scientific computing.”

The Incidence Matrix

The incidence matrix A has m = 6 rows and n = 4 columns. Each row corresponds

to an edge in the graph, and each column corresponds to a node. We do have to

number the edges and nodes, and also choose directions for the arrows, in order to

construct A. But the numbering and edge directions are arbitrary. Flows can travel

both ways, and a different choice of arrows will not change the reality of the model.

The entries −1 and 1 in each row of A give a record of the corresponding edge:

Row 1

The first edge leaves node 1 and goes to node 2.

The first row has −1 in column 1 and +1 in column 2.

Row 5 is typical. Edge 5 leaves node 2 (by −1 in column 2), and it enters node 4

(+1 in column 4). We chose arrows from lower-numbered nodes to higher-numbered

nodes, for simplicity. Then the −1 comes before the +1 in each row. In all cases, you

can write down A immediately by looking at the graph. The graph and the matrix

have the same information.

node

A =

⎡

⎢

⎣

−1

0 −1

−1

0 −1

⎤

⎥

⎦

edges 1 to 6

Incidence matrix

Figure 2.16: Complete graph with m = 6 edges and n = 4 nodes. A is 6 by 4.

Page 3

144

Chapter 2 A Framework for Applied Mathematics

Our second example is a subgraph of the first. It has the same four nodes but

only three edges 1, 3, and 6. Its incidence matrix is 3 by 4. Removing three edges

from the graph just removes three rows from the incidence matrix.

This graph is a tree. It has no closed loops. The tree has only m = n − 1 edges,

the minimum to connect all n nodes. The rows of A are linearly independent! A

complete graph has the maximum number of edges m =

n(n − 1), to connect every

pair of nodes. Other subgraphs are also trees; the three edges 1, 2, 4 come out from

one node. (The six edges contain a total of 16 trees.) The rank of A

tree

is r = 3.

node

tree

⎡

⎣

−1

0 −1

⎤

⎦

edge

Incidence matrix

Figure 2.17: A tree has no loops. With 4 nodes it has 3 edges.

The matrix A has two purposes. It gives a record of all connections in the graph

(it is a topology matrix). At the same time, we can multiply A times a vector u. The

matrix can act. When A multiplies u, you see it as a difference matrix:

Differences

across edges

Au =

⎡

⎢

⎣

−1

0 −1

−1

0 −1

⎤

⎥

⎦

⎡

⎢

⎣

⎤

⎥

⎦

⎡

⎢

⎣

− u

⎤

⎥

⎦

(4)

The numbers u

, u

could represent the heights of the nodes, or the pres-

sures at the nodes, or the voltages at the nodes. Most often they are simply called

potentials. Then the vector Au contains the “potential difference” across each edge:

u =

⎧

⎪

⎨

⎪

⎩

heights

pressures

voltages

potentials

Au =

⎧

⎪

⎨

⎪

⎩

height differences

pressure differences

voltage differences

potential differences

This model of nodes and edges is everywhere. The main point is that the n-

component node vector u leads to an m-component edge vector Au.

Page 4

2.4 Graph Models and Kirchhoff’s Laws

145

The Nullspace of A

The nullspace of A contains the vectors that solve Au = 0. When the

columns of A are independent, the only solution is u = 0 and the nullspace contains

only that one “zero vector.” Otherwise the nullspace might be a line of u’s, or a

plane, depending on how many combinations of the columns of A lead to Au = 0.

For incidence matrices, the nullspace is a line. Constant vectors solve Au = 0:

u =

⎡

⎢

⎣

⎤

⎥

⎦

and any u =

⎡

⎢

⎣

⎤

⎥

⎦

will satisfy Au = 0 .

(5)

In every row of Au, −C is canceled by +C and we get Au = 0. More intuitively,

we see Au as a vector of differences. When the components of u are all equal to C,

every difference is zero in Au. Thus u = (C, C, C, C) is a vector in the nullspace of A.

This applies to the complete graph and the tree example and all connected graphs.

A has the same nullspace as A, containing the constant vectors.

The word “connected” means that each pair of nodes is connected by a path of

edges. The graph does not break up into two or more separate pieces. If it did break

up, the vector u could be all ones in the first piece and all zeros in the other pieces.

This would still have differences Au = 0 across all existing edges; it would be in the

nullspace. The dimension of the nullspace N(A) is the number of separate pieces,

and we always assume that this number is one: a connected graph.

The rank of A is r = n − 1. Any n − 1 columns of the incidence matrix

are linearly independent. But the n columns are linearly dependent: their sum is the

zero column. We will have to remove one column (ground one node) to produce

independent columns in A. Then A

A is invertible (and positive definite). We can

only solve for the n − 1 potentials after one node is grounded: say u

= 0.

Looking ahead

For m currents and n−1 voltages, we will need m+n−1 equations.

We have Ohm’s Law on m edges (involving A) and Kirchhoff’s Law at n − 1 nodes

(involving A

). The right sides are voltage sources (batteries b

,...,b

) and current

sources f. Here is the framework and the all-important block matrix (KKT matrix):

Ground u

= 0 node potentials u

current sources f

w = f

Batteries b

voltage drops e

edge currents w

e = b − Au

w = Ce (Ohm’s Law)

[

−1

][

]

[

]

Page 5

146

Chapter 2 A Framework for Applied Mathematics

Kirchhoff’s Current Law A

w = 0

w = 0 enforces zero net flow into every node: Flow in equals flow out. These

are the balance equations for the currents w

,...,w

along the edges. There are n

equations in A

w = 0, one for each node. We are looking for currents that “balance

themselves” without any current sources from outside. The nullspace of A

is more

interesting than the line of constant vectors in the nullspace of A.

w = 0 is Kirchhoff’s Current Law (KCL). It is crucial for our framework

that transposing A produces the correct statement A

w = 0 of Kirchhoff’s Law.

⎡

⎢

⎣

−1 −1

0 −1

⎤

⎥

⎦

−w

− w

= 0

− w

= 0

+ w

− w

= 0

+ w

= 0

at node 1

(6)

The plus and minus signs in the equations are consistent with the arrows. At node 1,

all arrows go outward (the flows w

can go either way!). Kirchhoff’s Law says

that those flows add to zero (no net flow). But the four equations are not independent.

If we add the equations, everything cancels to give 0 = 0. The rows of A

add to the zero row—because the columns of A add to the zero column.

When we remove column 4 of A (by grounding node 4) this removes row 4 of A

That fourth equation w

+ w

= 0 comes from the other three equations.

So A

w = 0 has n − 1 = 3 independent equations in m = 6 unknowns w

,...,w

We expect 6 − 3 = 3 independent solutions. This is m − (n − 1).

What are the solutions to A

w = 0? Which flows on the six edges balance at

every node? It is certainly possible to solve by elimination, but fortunately there is a

direct way to visualize a flow that “balances itself.”

Suppose one unit of flow goes around a closed loop. Let the flow be zero

on all other edges not in the loop. Kirchhoff’s Law is satisfied by this loop flow w:

Loop

flow

⎧

⎨

⎩

+1 when edge i is in the loop, in the arrow direction

−1 when edge i is in the loop; flow against the arrow

0 when edge i is not in the loop

(7)

Loop

flows

w =

⎡

⎢

⎣

−1

⎤

⎥

⎦

⎡

⎢

⎣

−1

⎤

⎥

⎦

⎡

⎢

⎣

−1

⎤

⎥

⎦

.......

...

....

.......

Figure 2.18: Three independent loop flows solve Kirchhoff’s Current Law A

w = 0.

Page 6

2.4 Graph Models and Kirchhoff’s Laws

147

The loop of nodes 1 − 2 − 4 − 1 in Figure 2.18 consists of edge 1 then edge 5 then

backward on edge 4. Thus w

= 1, w

= −1 solves Kirchhoff’s Current Law.

Two independent solutions come from the other two small loops in the graph.

The graph has other loops! One possibility is the big loop around the outside,

from nodes 1 − 2 − 3 − 1. This gives the solution w

big

= (1, −1, 1, 0, 0, 0). That is

the sum of the three w’s from the small loops. The three small loops give a basis for

the nullspace of A

. The Fundamental Theorem of Linear Algebra confirms that the

dimension of the nullspace (number of basis vectors) is 6 − 3 = 3:

Number of independent solutions = (Number of unknowns) − (Rank) .

There are six unknowns w

,...,w

(six columns in A

). There are three independent

equations, counted by the rank. Apparently A

w = 0 gives four equations, but they

add to 0 = 0. Three equations for six unknowns leaves a three-dimensional nullspace.

The tree has no loops at all. The only flow in a tree that satisfies KCL is a zero

flow. A

has three columns, and they are independent (rank = 3). So this nullspace

has dimension 3 − 3 = 0. It contains only the single point (w

) = (0, 0, 0).

If a connected graph has n nodes, then A and A

have rank n − 1. Therefore

w = 0 has m − (n − 1) independent solutions coming from loops:

Dimension of nullspace = Number of independent loops = m − n + 1.

When the graph lies in a plane (like our examples) the small loops are easy to count.

This count gives a linear algebra proof of Euler’s Formula for every plane graph:

(Number of nodes) − (Number of edges) + (Number of loops) = 1 (8)

A triangle has (3 nodes)−(3 edges)+(1 loop). Our six-edge graph has 4 − 6 + 3 = 1.

On a seven-node tree, Euler’s Formula would give 7 − 6 + 0 = 1. All graphs lead to

the same answer (n) − (m) + (m − n + 1) = 1.

Kirchhoff’s Voltage Law

The twin laws of circuit theory are KCL and KVL,

current law and voltage law. The voltage law says that the sum of voltage drops e

around every closed loop is zero. We now put this into matrix language: e = Au.

When w gives flow around a loop (w

= ±1), the product e

w is the sum of voltage

drops on that loop. So the voltage law is e

w = 0. The Fundamental Theorem of

Linear Algebra says that if e is perpendicular to the nullspace of A

, then e is in the

column space of A. Thus e must be a combination e = Au of the columns of A.

Here is the point. If A

w = 0 is in the framework, then e = Au must be there too.

The voltage law says that the “potentials” u

,...,u

must exist. The twin laws

assure that A and A

will both appear. We discovered A

when we wrote out

the balance equation, but Kirchhoff knew that it would be there waiting for us.

Page 7

148

Chapter 2 A Framework for Applied Mathematics

The Graph Laplacian Matrix A

The incidence matrix A is rectangular (m by n). You expect the network equations

to produce A

A and eventually A

CA. These matrices are square (n by n) and

symmetric and very important. A

A is also a pleasure to calculate.

For the complete graph with four nodes, multiplying A

A gives 3’s and −1’s:

⎡

⎢

⎣

−1 −1

0 −1

⎤

⎥

⎦

⎡

⎢

⎣

−1

0 −1

−1

0 −1

⎤

⎥

⎦

⎡

⎢

⎣

3 −1 −1 −1

−1

3 −1 −1

−1 −1

3 −1

−1 −1 −1

⎤

⎥

⎦

(9)

The columns still add to produce the zero column. The all-ones vector u = (1, 1, 1, 1)

is in the nullspace of A

A. This must be true, because Au = 0 gives A

Au = 0. The

matrix A

A always has the same rank and nullspace as A. Here the rank is r = 3

and the nullspace is the line of constant vectors.

The numbers in A

A follow a neat pattern. Its diagonal is the degree matrix

D. Here the degrees are 3, 3, 3, 3. The off-diagonal part of A

A is −W. Here the

adjacency matrix W has all possible 1’s, because the graph has all possible edges.

On the diagonal

= degree = number of edges meeting at node j.

Row 4 of A

and column 4 of A are (0, 0, 0, 1, 1, 1). They multiply to give (A

= 3.

But column 4 overlaps column 3 = (0, 1, 1, 0, 0, −1) in a single −1:

Off the diagonal

{

−1 if nodes j and k share an edge

0 if no edge goes between those nodes.

For the complete graph, every off-diagonal entry in A

A is −1. All edges are present.

But the tree has missing edges, which produce zeros in the graph Laplacian A

tree

⎡

⎢

⎣

1 −1

−1

2 −1

0 −1

2 −1

0 −1

⎤

⎥

⎦

= D − W

The zeros show

3 edges removed

in Figure 2.17

(10)

The middle nodes in Figure 2.17 have two edges. The outer nodes only have one

edge, so those diagonal entries are 1. The off-diagonals show 0’s for missing edges.

Our −1, 2, −1 matrix B

appears because this tree is really a line of four nodes.

When node 4 is grounded, which fixes u

= 0, the last row and column disappear

from A

A. Then (A

reduced

becomes invertible (it is exactly the matrix T

Page 8

2.4 Graph Models and Kirchhoff’s Laws

149

In many applications another potential is fixed, say u

= V volts. Then row 1 and

column 1 also disappear, since u

is known. That number V will turn up on the

right side of the equations. Currents still balance. Since u

multiplied column 1,

moving it to the right side will produce −V times column 1:

Fixed voltage u

= V

3 identical resistors

− u

= V

−u

+ 2u

= 0

(11)

This tree is like a line of springs. The grounded node 4 is like a fixed end u

= 0.

The potential u

= V is like a nonzero fixed displacement. All springs are

equally stretched and all edges carry the same current, and (11) is easy to solve:

Potentials at nodes

) = (V,

V, 0)

(12)

Question

What is A

A for the tree with edges 1, 2, 4 all coming out of node 1?

tree

⎡

⎢

⎣

3 −1 −1 −1

−1

⎤

⎥

⎦

= D − W

3 edges to node 1

1 edge to nodes 2, 3, 4

Important: A

A is positive semidefinite but not positive definite. The determinant

is zero; A

A is not invertible. We have to remove a column of A (ground a node).

That removes a row and column of A

A, and then (A

reduced

is invertible.

Inputs b, f and Matrices A, C, A

A network has nodes and edges, and it also assigns numbers c

,...,c

to those

edges. Thus the network starts with a graph, and its incidence matrix A. The m

numbers go into a diagonal matrix C. These positive numbers are the conductances,

and they give the flow law for each edge. Hooke’s Law becomes Ohm’s Law:

Ohm’s Law w

= c

Edge current = (Conductance)×(Voltage drop)

Important! Voltage drops e

are measured across the resistors. Those drops make

the current flow. Some or all of the edges can include batteries (voltage sources). We

have separated out edge 2 in Figure 2.19 to see the sign convention in e = b − Au.

As in least squares, b is a given vector (b = 0 means no batteries). A enters with

a minus sign because the flow is from higher potential to lower potential. The minus

sign on A also appears in heat flow and fluid flow: from higher temperature to lower

temperature, from higher pressure to lower pressure.

Page 9

150

Chapter 2 A Framework for Applied Mathematics

12V

voltage

source b

4 amps

current

source f

...

= −4

= +4

−

12V

−

voltage drop

from u

to u

= 12 + u

− u

Figure 2.19: The network has conductances c

, batteries b

, and current sources f

Assembling the Matrix K = A

The weighted Laplacian matrix K = A

n×m

m×m

m×n

is still n by n. When C

was I and all c

= 1, the unweighted A

A came from counting edges into nodes.

Now we include the numbers c

that are assigned to those edges. Row 4 of A

and

column 4 of A are (0, 0, 0, 1, 1, 1) for the complete graph. When C is in the middle,

the multiplication produces c

. This will be K

, in the bottom corner of the

conductance matrix K = A

CA = D − W:

On the diagonal

= sum of weights c

on the edges meeting at node j

The off-diagonals of A

A are −1 or 0, edge or no edge. Then A

CA gives −c

or 0:

Off the diagonal

{

−c

if edge i connects nodes j and k

0 if no edge goes between those nodes

(13)

Not grounded

Not invertible

K = D − W

K =

⎡

⎢

⎣

+ c

−c

+ c

−c

+ c

−c

+ c

⎤

⎥

⎦

(14)

Grounding node 4 removes row 4 and column 4. Then K

reduced

becomes invertible.

May I mention how K can be “assembled” from small matrices? Each edge of the

network contributes a 2 by 2 matrix to be placed into K. If we look at the tree, its

edges 1, 3, 6 contribute three element matrices K

, K

tree

from

[

−c

]

+ +

[

−c

]

+ +

[

−c

]

(15)

The typical element matrix K

comes from the 3rd column of A

times c

times the

3rd row of A. Matrix multiplication can be done this way (columns times rows):

CA = assembly of K

∑

(column i of A

)(c

)(row i of A). (16)

Page 10

2.4 Graph Models and Kirchhoff’s Laws

151

The element matrices K

are actually full-size, 4 by 4. But only the 2 by 2 parts

shown in (15) are nonzero. The double plus signs in (15) mean that K

has to be

placed correctly into K. Here the pieces are assembled into K = A

CA for the tree:

Line of edges

Tridiagonal K

tree

⎡

⎢

⎣

−c

+ c

−c

+ c

−c

⎤

⎥

⎦

(17)

K is singular because u = (1, 1, 1, 1) is in its nullspace. When all c

= 1, this is the

−1, 2, −1 matrix B

= A

A. When node 4 is grounded, A

A becomes T

(invertible!).

Example 1 Suppose all the conductances in Figure 2.19 are c

= 1. Exceptionally we

can solve this system by hand. Look first at the 4-amp current source in f. That current

has to return from node 1 to node 2. Consider three paths from node 1 to node 2:

Edge 1 (node 1 directly to node 2) :

conductance =

Edges 2 and 3 in series (via node 3) : conductance = (1 + 1)

−1

= 0.5

Edges 4 and 5 in series (via node 4) : conductance = (1 + 1)

−1

= 0.5

These three paths are in parallel. Their total conductance is 1+

= 2. The four amps

of current will travel down those paths in the ratio 2 to 1 to 1. Following the arrows,

= 2 w

= 1 w

= −1 w

= 1 w

= −1 w

= 0 (by symmetry) .

Those six currents satisfy the balance equations A

w = f. The potential drop between

node 1 and node 2 is total current/total conductance = 4/2 = u

− u

Voltages

= 1 u

= −1 u

= 0 (by symmetry) and u

= 0 (grounded).

The systematic way to find those currents w and potentials u is from A

w = f

and w = Ce and e = b − Au. With e = C

−1

w, the voltage equation becomes

−1

w + Au = b. Column 4 of A is removed by u

= 0. For the six currents and three

voltages, we have Ohm’s Law on six edges and Kirchhoff’s Law at nodes 1, 2, 3:

+ u

− u

= 0

+ u

− u

= 12

+ u

− u

= 0

− u

= 0

− u

= 0

− u

= 0

−w

− w

= −4

− w

= +4

+ w

− w

= 0

⎡

⎢

⎣

1/c

−1

0 −1

−1

0 −1

1/c

0 −1

−1 −1

0 −1

⎤

⎥

⎦

⎡

⎢

⎣

⎤

⎥

⎦

(18)

Notice the −4 and +4 adding to zero as required. Our solutions above account for this

4-amp current source. Problem 11 will account for the 12-volt battery. By addition

we account for both, and solve the full system (18) with all conductances c

= 1.

Page 11

152

Chapter 2 A Framework for Applied Mathematics

The Saddle Point KKT Matrix

The “KKT” matrix in (18) is absolutely fundamental to applied mathe-

matics. It appears in network equilibrium problems (like this one). It also appears

in optimization problems (maximum or minimum with constraints). It has a square

symmetric block C

−1

in one corner and a square zero block. The other blocks A and

make it symmetric. Its size is m + n − 1 = 6 + 4 − 1