13 Graphs, Networks, Incidence Matrices

Graphs, networks, incidence matrices
When we use linear algebra to understand physical systems, we often nd

more structure in the matrices and vectors than appears in the examples we
make up in class. There are many applications of linear algebra; for example,
chemists might use row reduction to get a clearer picture of what elements
go into a complicated reaction. In this lecture we explore the linear algebra
associated with electrical networks.
Graphs and networks

A graph is a collection of nodes joined by edges; Figure 1 shows one small
graph.
Figure 1: A graph with n = 4 nodes and m = 5 edges.

We put an arrow on each edge to indicate the positive direction for currents
running through the graph.
1

2

3
Figure 2: The graph of Figure 1 with a direction on each edge.
Incidence matrices
The incidence matrix of this directed graph has one column for each node of the
graph and one row for each edge of the graph:
1
1
0 0
0 1
1 0
0
1 0
A = 1
.
1
0
0 1
0
0 1 1
If an edge runs from node a to node b, the row corresponding to that edge has
1 in column a and 1 in column b; all other entries in that row are 0. If we were
1
studying a larger graph we would get a larger matrix but it would be sparse;
most of the entries in that matrix would be 0. This is one of the ways matrices
arising from applications might have extra structure.
Note that nodes 1, 2 and 3 and edges , and form a loop. The matrix
describing just those nodes and edges looks like:
1
1 0 0
0 1 1 0 .
1
0 1 0
Note that the third row is the sum of the rst two rows; loops in the graph
correspond to linearly dependent rows of the matrix.
To nd the nullspace of A, we solve Ax = 0:
x2 x1
0
x3 x2 0
Ax =
x3 x1 =
0 .
x4 x1 0
x4 x3
0
If the components xi of the vector x describe the electrical potential at the nodes
i of the graph, then Ax is a vector describing the difference in potential across
each edge of the graph. We see Ax = 0 when x1 = x2 = x3 = x4 , so the
nullspace has dimension 1. In terms of an electrical network, the potential
difference is zero on each edge if each node has the same potential. We cant tell
what that potential is by observing the ow of electricity through the network,
but if one node of the network is grounded then its potential is zero. From that
we can determine the potential of all other nodes of the graph.
The matrix has 4 columns and a 1 dimensional nullspace, so its rank is 3.
The rst, second and fourth columns are its pivot columns; these edges connect
all the nodes of the graph without forming a loop a graph with no loops is
called a tree.
The left nullspace of A consists of the solutions y to the equation: A T y = 0.
Since A T has 5 columns and rank 3 we know that the dimension of N ( A T ) is
m r = 2. Note that 2 is the number of loops in the graph and m is the number
of edges. The rank r is n 1, one less than the number of nodes. This gives us
# loops = # edges (# nodes 1), or:
number of nodes number of edges + number of loops = 1.
This is Eulers formula for connected graphs.
Kirchhoffs law
In our example of an electrical network, we started with the potentials xi of
the nodes. The matrix A then told us something about potential differences.
An engineer could create a matrix C using Ohms law and information about
2
1
y1
2
y4
y3
y5
3
y2
Figure 3: The currents in our graph.

the conductance of the edges and use that matrix to determine the current yi
on each edge. Kirchhoffs Current Law then says that A T y = 0, where y is
the vector with components y1 , y2 , y3 , y4 , y5 . Vectors in the nullspace of A T
correspond to collections of currents that satisfy Kirchhoffs law.
x = x1 , x2 , x3 , x4
potentials at nodes
AT y = 0
Kirchhoffs Current Law
e = Ax
AT y
x2 x1 , etc.
potential differences
y = Ce
Ohms Law
y1 , y2 , y3 , y4 , y5
currents on edges
Written out, A T y = 0 looks like:
1
0 1 1
0 1
y2
1 1
0
0
0
y3 =

0
1
1
0 1
y4
0
0
0
1
1
y5
0
0
.
0
0
Multiplying the rst row by the column vector y we get y1 y3 y4 = 0.

This tells us that the total current owing out of node 1 is zero its a balance
equation, or a conservation law. Multiplying the second row by y tells us y1
y2 = 0; the current coming into node 2 is balanced with the current going out.
Multiplying the bottom rows, we get y2 + y3 y5 = 0 and y4 + y5 = 0.
We could use the method of elimination on A T to nd its column space, but
we already know the rank. To get a basis for N ( A T ) we just need to nd two
independent vectors in this space. Looking at the equations y1 y2 = 0 we
might guess y1 = y2 = 1. Then we could use the conservation laws for node 3
to guess y3 = 1 and y5 = 0. We satisfy
conditions on node 4
the conservation
with y4 = 0, giving us a basis vector 1 . This vector represents one unit

0
0
of current owing around the loop joining nodes 1, 2 and 3; a multiple of this
vector represents a different amount of current around the same loop.
T
We nd a second
basis
vector for N
( A )by looking at the loop formed by
0
nodes 1, 3 and 4: 1
1
. The vector 0
that represents a current around
the outer loop is also in the nullspace, but it is the sum of the rst two vectors
we found.
Weve almost completely covered the mathematics of simple circuits. More
complex circuits might have batteries in the edges, or current sources between
nodes. Adding current sources changes the A T y = 0 in Kirchhoffs current law
to A T y = f. Combining the equations e = Ax, y = Ce and A T y = f gives us:
A T CAx = f.
MIT OpenCourseWare
http://ocw.mit.edu
18.06SC Linear Algebra

Fall 2011
For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.

13 Graphs, Networks, Incidence Matrices

Uploaded by

Copyright:

Available Formats

13 Graphs, Networks, Incidence Matrices

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

13 Graphs, Networks, Incidence Matrices

Uploaded by

Copyright:

Available Formats

Graphs, networks, incidence matrices

When we use linear algebra to understand physical systems, we often nd

Graphs and networks

Figure 1: A graph with n = 4 nodes and m = 5 edges.

Figure 2: The graph of Figure 1 with a direction on each edge.

Figure 3: The currents in our graph.

Written out, A T y = 0 looks like:

Multiplying the rst row by the column vector y we get y1 y3 y4 = 0.

with y4 = 0, giving us a basis vector 1 . This vector represents one unit

that represents a current around

18.06SC Linear Algebra

You might also like