12. Graphs, Networks, Incidence Matrices

Overview

An oriented graph with 4 nodes and 5 edges yields a sparse incidence matrix whose rows encode edge directions and whose columns encode node potentials. The lecture connects its four fundamental subspaces to electrical networks: A computes potential differences, Ohm's law maps differences to currents, and A transpose y = 0 expresses Kirchhoff's Current Law; cycle-space dimension then gives the connected-graph identity nodes minus edges plus independent loops equals 1.

Key takeaways

For a connected graph with n nodes and m oriented edges, the incidence matrix has rank n - 1 because constant node potentials lie in its null space.
The null space of A transpose is the cycle space: its dimension m - n + 1 counts independent current loops, not all visually traceable cycles.
The incidence matrix converts node potentials into edge potential differences, while its transpose encodes node-by-node flow conservation.
A spanning tree on n connected nodes contains n - 1 independent edges and no cycles; adding each further edge creates one additional independent cycle.
For a network with conductance matrix C and external current vector F, the equilibrium equations combine into A transpose C A x = F.
Grounding one node removes the arbitrary constant in the potential reference; for a connected network, this allows the remaining node potentials to be determined.

Chapters

0:00 Graphs as Structured Sources of Applied Matrices

Real matrices arise from applications, such as chemical reaction quantities and networks, rather than being arbitrary classroom examples.
A graph consists of nodes and edges and can model websites, telephone connections, people, electrical circuits, water flow, or structures.
The lecture builds an electrical network example with 4 nodes and 5 edges.

5:00 Constructing the Oriented Incidence Matrix

Each of the 5 rows represents one edge, and each of the 4 columns represents one node.
Orienting an edge assigns a -1 at its starting node and a +1 at its destination; every row therefore has exactly two nonzero entries.
The resulting 5-by-4 incidence matrix is sparse, with 2m = 10 nonzero entries for m = 5 edges.
The triangle formed by edges 1, 2, and 3 creates a row dependency: the row for edge 1 plus the row for edge 2 equals the row for edge 3.

10:25 The Null Space of A Represents Constant Node Potentials

For node potentials x = (x1, x2, x3, x4), multiplying by A produces edge differences such as x2 - x1 and x3 - x2.
Solving Ax = 0 requires equal potentials at the ends of every edge, so a connected graph has null space spanned by (1, 1, 1, 1).
The 5-by-4 incidence matrix has rank 3 and a one-dimensional null space because adding the same constant to every node potential changes no edge difference.
Grounding one node fixes the arbitrary reference potential and leaves 3 independent potential variables.

20:00 A Transpose and the Electrical Network Equations

A transpose is a 4-by-5 matrix, and rank-nullity gives dim N(A transpose) = m - r = 5 - 3 = 2.
The vector y = (y1, y2, y3, y4, y5) represents currents on the 5 oriented edges.
Ohm's law maps edge potential differences to currents using conductances, collected in a matrix C.
The equation A transpose y = 0 is Kirchhoff's Current Law for a network without external current sources.

24:00 Kirchhoff's Current Law as Node-by-Node Flow Balance

At node 1, the equation -y1 - y3 - y4 = 0 balances the three currents directed outward from that node.
At node 2, y1 - y2 = 0 requires incoming current y1 to equal outgoing current y2.
At node 3, y2 + y3 - y5 = 0 balances two incoming currents against the outgoing current y5.
At node 4, y4 + y5 = 0 expresses zero net flow, so charge does not accumulate at any node.

30:00 Independent Cycle Currents Form the Null Space of A Transpose

A unit current around the triangle uses y1 = 1, y2 = 1, and y3 = -1, with y4 = y5 = 0.
A second independent circulation uses the loop through edges 3, 4, and 5, with signs chosen to follow or oppose each edge arrow.
These two loop-current vectors form a basis for N(A transpose), matching its dimension of 2.
The current around the outside loop is not a third basis vector because it is the sum of the two smaller loop currents.

35:45 Spanning Trees, Independent Edges, and the Cycle Count

The pivot columns of A transpose correspond to edges 1, 2, and 4, which connect all 4 nodes without forming a loop.
A connected, loop-free subgraph with 4 nodes and 3 edges is a tree; its edges provide an independent set.
For a connected graph, rank r = n - 1, so the number of independent cycles is dim N(A transpose) = m - n + 1.
Rearranging gives nodes minus edges plus independent loops equals 1, the graph identity presented as Euler's formula in the lecture.

39:20 Checking the Node-Edge-Loop Identity on Another Graph

A second example has 5 nodes, 7 edges, and 3 independent loops.
The count gives 5 - 7 + 3 = 1, illustrating the connected-graph identity.
The loop count refers to independent cycles, not every possible route that can be traced around the graph.

43:35 Combining the Network Equations into A Transpose C A

The network equations proceed from node potentials x to potential differences E = Ax, then to edge currents y = CE.
Kirchhoff's law with external current sources is A transpose y = F, yielding A transpose C A x = F.
The matrix A transpose C A is symmetric when C is symmetric; A transpose A is also always symmetric.
The resulting system models equilibrium current distribution and is a core form of a numerical linear algebra problem.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, MIT OpenCourseWare.