Incidence Matrices

Definition

An incidence matrix $A$ represents the topology of a graph. For a graph with $n$ nodes and $m$ edges, $A$ is an $m \times n$ matrix where each row represents an edge connecting two nodes: $-1$ at the source node and $+1$ at the destination node.

Why It Matters

This matrix is the “DNA” of a network, providing a rigorous mathematical way to describe connections that would otherwise be too complex to manage. By encoding topology into linear algebra, we can use powerful matrix operations to solve massive engineering problems in power grids, internet routing, and structural design—turning a “drawing” of a network into a system of solvable equations.

Core Concepts

• Rows = Edges, Columns = Nodes: Each edge (row) has exactly one $-1$ and one $+1$.
• Nullspace $N(A)$: Contains the “constant” vectors (e.g., all 1s). For a connected graph, the nullspace is 1D, representing a constant “potential” (like voltage) at every node.
• Rank: For a connected graph with $n$ nodes, the rank is $n-1$.
• Loops and Cycles: The rows corresponding to edges that form a cycle are linearly dependent.
• Fundamental Law: $A^T y = f$ represents Kirchhoff’s Current Law (KCL), where $y$ are flows on edges and $f$ are external sources at nodes.
  • How to read: “The transpose of matrix A times the vector y is equal to f.”
  • Meaning: At each node, net inflow from edges plus external source equals zero (conservation of flow) — the matrix form of KCL.

Connected Concepts

• Equilibrium
• Conservation Laws
• Matrix Algebra: Inverses