Skip to main content

Graphs, networks, incidence matrices

讲座摘要（lecture summary）​

When we use linear algebra to understand physical systems, we often find 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 11 shows one small graph.

bf03dbe2b5108d9fceefbe1f81a5aba20938f047484c7d92ea09f7cf93316c8a.jpg

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

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

4bc12dbd64feaec3418d287f9c6064c9b69b76ea903199f69486b0da6f7ba706.jpg

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:

A=[−11000−110−1010−100100−11].A=\left[{\begin{array}{r r r r}{-1}&{1}&{0}&{0}\\ {0}&{-1}&{1}&{0}\\ {-1}&{0}&{1}&{0}\\ {-1}&{0}&{0}&{1}\\ {0}&{0}&{-1}&{1}\end{array}}\right].

If an edge runs from node aa to node bb , the row corresponding to that edge has −1^{-1} in column aa and 1 in column bb ; all other entries in that row are 00. If we were 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 11, 22 and 33 and edges ①,② and ③ form a loop. The matrix describing just those nodes and edges looks like:

[−11000−110−1010].\left[{\begin{array}{r r r r}{-1}&{1}&{0}&{0}\\ {0}&{-1}&{1}&{0}\\ {-1}&{0}&{1}&{0}\end{array}}\right].

Note that the third row is the sum of the first two rows; loops in the graph correspond to linearly dependent rows of the matrix.

To find the nullspace of AA , we solve Ax=0A\mathbf{x}=\mathbf{0} :

Ax=[x2−x1x3−x2x3−x1x4−x1x4−x3]=[00000].A\mathbf{x}=\left[{\begin{array}{l}{x_{2}-x_{1}}\\ {x_{3}-x_{2}}\\ {x_{3}-x_{1}}\\ {x_{4}-x_{1}}\\ {x_{4}-x_{3}}\end{array}}\right]=\left[{\begin{array}{l}{0}\\ {0}\\ {0}\\ {0}\\ {0}\end{array}}\right].

If the components xix_{i} of the vector x\mathbf{x} describe the electrical potential at the nodes ii of the graph, then AxA\pmb{x} is a vector describing the difference in potential across each edge of the graph. We see Ax = 0A\mathbf{x}\,=\,\mathbf{0} when x1 = x2 = x3 = x4,x_{1}\,=\,x_{2}\,=\,x_{3}\,=\,x_{4}, so the nullspace has dimension 11. In terms of an electrical network, the potential difference is zero on each edge if each node has the same potential. We can’t tell what that potential is by observing the flow 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 44 columns and a 11 dimensional nullspace, so its rank is 33. The first, 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 AA consists of the solutions y to the equation: ATy=0A^{T}\mathbf{y}=\mathbf{0} . Since ATA^{T} has 55 columns and rank 33 we know that the dimension of N(AT)N(A^{T}) is m−r=2m-r=2 . Note that 22 is the number of loops in the graph and mm is the number of edges. The rank rr is n−1n-1 , one less than the number of nodes. This gives us #loops = #edges - (#nodes - 11), or:

number of nodes−number of edges+number of loops=1.\text{number of nodes} − \text{number of edges} + \text{number of loops} =1 .

This is Euler’s formula for connected graphs.

Kirchhoff’s law​

In our example of an electrical network, we started with the potentials xix_{i} of the nodes. The matrix AA then told us something about potential differences. An engineer could create a matrix CC using Ohm’s law and information about the conductance of the edges and use that matrix to determine the current yiy_{i} on each edge. Kirchhoff’s Current Law then says that ATy = 0.A^{T}\mathbf{y}\,=\,\mathbf{0}. , where y is the vector with components y1,y2,y3,y4,y5y_{1},y_{2},y_{3},y_{4},y_{5} . Vectors in the nullspace of ATA^{T} correspond to collections of currents that satisfy Kirchhoff’s law.

51c070609a84a36603af338b222031bfb37391625d227cc9d2c6bf1f8692db92.jpg

Figure 3: The currents in our graph.

x=x1,x2,x3,x4ATy=0potentials at nodesKirchhoff’s Current Lawe=Ax↓↑ATyx2−x1,etc.y=Cey1,y2,y3,y4,y5potential differences⟶currents on edgesOhm’s Law\begin{array}{ccc} \mathbf{x}=x_{1},x_{2},x_{3},x_{4} & & A^{T}\mathbf{y}=0 \\ \text{potentials at nodes} & & \text{Kirchhoff’s Current Law} \\ \\ \mathbf{e}=A\mathbf{x}\downarrow && \uparrow A^{T}\mathbf{y} \\ \\ x_2 - x_1,\text{etc.} & \mathbf{y}=C\mathbf{e}& y_{1},y_{2},y_{3},y_{4},y_{5}\\ \text{potential differences} & \longrightarrow &\text{currents on edges} \\ &\text{Ohm’s Law}& \end{array}

Written out, ATy=0A^{T}\mathbf{y}=\mathbf{0} looks like:

[−10−1−101−10000110−100011][y1y2y3y4y5]=[0000].\left[{\begin{array}{r r r r r}{-1}&{0}&{-1}&{-1}&{0}\\ {1}&{-1}&{0}&{0}&{0}\\ {0}&{1}&{1}&{0}&{-1}\\ {0}&{0}&{0}&{1}&{1}\end{array}}\right]{\left[\begin{array}{l}{y_{1}}\\ {y_{2}}\\ {y_{3}}\\ {y_{4}}\\ {y_{5}}\end{array}\right]}=\left[{\begin{array}{l}{0}\\ {0}\\ {0}\\ {0}\end{array}}\right].

Multiplying the first row by the column vector y\mathbf{y} we get −y1−y3−y4 = 0-y_{1}-y_{3}-y_{4}\,=\,0 . This tells us that the total current flowing out of node 1 is zero – it’s a balance equation, or a conservation law. Multiplying the second row by y tells us y1−y_{1}- y2=0.y_{2}=0. ; the current coming into node 2 is balanced with the current going out. Multiplying the bottom rows, we get y2+y3−y5=0y_{2}+y_{3}-y_{5}=0 and y4+y5=0y_{4}+y_{5}=0 .

We could use the method of elimination on ATA^{T} to find its column space, but we already know the rank. To get a basis for N(AT)N(A^{T}) we just need to find two independent vectors in this space. Looking at the equations y1−y2 = 0y_{1}-y_{2}\,=\,0 we might guess y1=y2=1y_{1}=y_{2}=1 . Then we could use the conservation laws for node 33 to guess y3=−1y_{3}=-1 and y5=0y_{5}=0 . We satisfy the conservation conditions on node 44 with y4=0y_{4}=0 , giving us a basis vector [11−100].\left[\begin{array}{r}{1}\\ {1}\\ {-1}\\ {0}\\ {0}\end{array}\right]. This vector represents one unit of current flowing around the loop joining nodes 11, 22 and 33; a multiple of this vector represents a different amount of current around the same loop.

We find a second basis vector for N(AT)N(A^T) by looking at the loop formed by nodes 11, 33 and 44: [001−11]\left[\begin{array}{r}{0}\\ {0}\\ {1}\\ {-1}\\ {1}\end{array}\right]. The vector [110−11]\left[\begin{array}{r}{1}\\ {1}\\ {0}\\ {-1}\\ {1}\end{array}\right] that represents a current around the outer loop is also in the nullspace, but it is the sum of the first two vectors we found.

We’ve 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 ATy=0A^{T}\mathbf{y}=\mathbf{0} in Kirchhoff’s current law to ATy=fA^{T}\mathbf{y}=\mathbf{f} . Combining the equations e=Ax.\mathbf{e}=A\mathbf{x}. , y=Ce\mathbf{y}=C\mathbf{e} and ATy=fA^{T}\mathbf{y}=\mathbf{f} gives us:

ATCAx=f.A^{T}C A\mathbf{x}=\mathbf{f}.

Problems and Solutions（习题及答案）​

Problem 12.1: (8.2 #1. Introduction to Linear Algebra: Strang) Write down the four by four incidence matrix AA for the square graph, shown below. (Hint: the first row has −1-1 in column 11 and +1+1 in column 22.) What vectors (x1,x2,x3,x4)\left(x_{1},x_{2},x_{3},x_{4}\right) are in the nullspace of A?A? How do you know that (1,0,0,0)(1,0,0,0) is not in the row space of A?A?

87fb8caa7947e0a66ca83ea2d40aa6f7d1138a133d8122d928676afd6f02d336.jpg

Solution

Solution: The incidence matrix AA is written as:

A=[−11000−110001−1−1001].A=\left[{\begin{array}{r r r r}{-1}&{1}&{0}&{0}\\ {0}&{-1}&{1}&{0}\\ {0}&{0}&{1}&{-1}\\ {-1}&{0}&{0}&{1}\end{array}}\right].

To find the vectors in the nullspace, we solve Ax=0A\mathbf{x}=\mathbf{0} :

[−11000−110001−1−1001][x1x2x3x4]=[x2−x1x3−x2x3−x4x4−x1]=[0000],\left[\begin{array}{r r r r}{-1}&{1}&{0}&{0}\\ {0}&{-1}&{1}&{0}\\ {0}&{0}&{1}&{-1}\\ {-1}&{0}&{0}&{1}\end{array}\right]\left[\begin{array}{r}{x_{1}}\\ {x_{2}}\\ {x_{3}}\\ {x_{4}}\end{array}\right]=\left[\begin{array}{r}{x_{2}-x_{1}}\\ {x_{3}-x_{2}}\\ {x_{3}-x_{4}}\\ {x_{4}-x_{1}}\end{array}\right]=\left[\begin{array}{r}{0}\\ {0}\\ {0}\\ {0}\end{array}\right],

so x1=x2=x3=x4x_{1}=x_{2}=x_{3}=x_{4} . Therefore, the nullspace consists of vectors of the form (a,a,a,a)\left(a,a,a,a\right) .

Finally, (1,0,0,0)(1,0,0,0) is not in the row space of AA because it is not orthogonal to the nullspace.

Problem 12.2: (8.2 #7.) Continuing with the network from problem one, suppose the conductance matrix is

C=[1000020000200001].C=\left[\begin{array}{c c c c}{{1}}&{{0}}&{{0}}&{{0}}\\ {{0}}&{{2}}&{{0}}&{{0}}\\ {{0}}&{{0}}&{{2}}&{{0}}\\ {{0}}&{{0}}&{{0}}&{{1}}\end{array}\right].

Multiply matrices to find ATCAA^{T}C A . For f = (1,0,−1,0),\mathbf{f}\,=\,(1,0,-1,0), , find a solution to ATCA˙x=f.A^{T}C\dot{A}x=\mathbf{f}. Write the potentials x\mathbf{x} and currents y=−CAx\mathbf{y}=-C A\mathbf{x} on the square graph (see above) for this current source f going into node 1 and out from node 33.

Solution

Solution: From the previous question, we know that the incidence matrix is:

A=[−11000−110001−1−1001].A=\left[{\begin{array}{r r r r}{-1}&{1}&{0}&{0}\\ {0}&{-1}&{1}&{0}\\ {0}&{0}&{1}&{-1}\\ {-1}&{0}&{0}&{1}\end{array}}\right].

Multiply to obtain ATCAA^{T}C A :

[−100−11−100011000−11][1000020000200001][−11000−110001−1−1001]=[2−10−1−13−200−24−2−10−2−3] .\left[{\begin{array}{r r r r}{-1}&{0}&{0}&{-1}\\ {1}&{-1}&{0}&{0}\\ {0}&{1}&{1}&{0}\\ {0}&{0}&{-1}&{1}\end{array}}\right]\left[{\begin{array}{r r r r}{1}&{0}&{0}&{0}\\ {0}&{2}&{0}&{0}\\ {0}&{0}&{2}&{0}\\ {0}&{0}&{0}&{1}\end{array}}\right]\left[{\begin{array}{r r r r}{-1}&{1}&{0}&{0}\\ {0}&{-1}&{1}&{0}\\ {0}&{0}&{1}&{-1}\\ {-1}&{0}&{0}&{1}\end{array}}\right]=\left[{\begin{array}{r r r r}{2}&{-1}&{0}&{-1}\\ {-1}&{3}&{-2}&{0}\\ {0}&{-2}&{4}&{-2}\\ {-1}&{0}&{-2}&{-3}\end{array}}\right]\,.

Solving the equation ATCAx=fA^{T}C A\mathbf{x}=\mathbf{f} by performing row reduction on the augmented matrix

[−100−111−10000110−100−110]\left[{\begin{array}{r r r r | r}{-1}&{0}&{0}&{-1}& 1\\ {1}&{-1}&{0}&{0} & 0\\ {0}&{1}&{1}&{0} & -1\\ {0}&{0}&{-1}&{1}&0\end{array}}\right]

and choosing x3=0x_{3}=0 to represent a grounded node gives:

x=[x1x2x3x4] = [3/41/401/4] .\mathbf{x}={\left[\begin{array}{l}{x_{1}}\\ {x_{2}}\\ {x_{3}}\\ {x_{4}}\end{array}\right]}\,=\,{\left[\begin{array}{r}{\bf 3/4}\\ {\bf 1/4}\\ {\bf 0}\\ {\bf 1/4}\end{array}\right]}\,.

We know y=−CAx,\mathbf{y}=-C A\mathbf{x}, so

y=[1−10002−2000−22100−1][3/41/401/4]=[1/21/21/21/2].\mathbf{y}=\left[\begin{array}{r r r r}{1}&{-1}&{0}&{0}\\ {0}&{2}&{-2}&{0}\\ {0}&{0}&{-2}&{2}\\ {1}&{0}&{0}&{-1}\end{array}\right]\left[\begin{array}{r}{3/4}\\ {1/4}\\ {0}\\ {1/4}\end{array}\right]=\left[\begin{array}{r}{\bf 1/2}\\ {\bf 1/2}\\ {\bf 1/2}\\ {\bf 1/2}\end{array}\right].

We draw these values on the square graph: