Incidence Matrix — Definition, Formula & Examples

An incidence matrix is a rectangular matrix that shows which vertices are connected by which edges in a graph. Each row represents a vertex, each column represents an edge, and the entries indicate whether a vertex is an endpoint of that edge.

For an undirected graph $G = (V, E)$ with $|V| = n$ vertices and $|E| = m$ edges, the incidence matrix $B$ is the $n \times m$ matrix where $B_{ij} = 1$ if vertex $v_i$ is an endpoint of edge $e_j$ , and $B_{ij} = 0$ otherwise. For a directed graph, $B_{ij} = +1$ if edge $e_j$ leaves vertex $v_i$ , $B_{ij} = -1$ if edge $e_j$ enters vertex $v_i$ , and $B_{ij} = 0$ otherwise.

Key Formula

B_{ij} = \begin{cases} 1 & \text{if vertex } v_i \text{ is an endpoint of edge } e_j \\ 0 & \text{otherwise} \end{cases}

Where:

$B$ = The incidence matrix of size n × m
$v_i$ = The i-th vertex of the graph
$e_j$ = The j-th edge of the graph

How It Works

To build an incidence matrix, label each vertex as a row and each edge as a column. For an undirected graph, place a 1 in row

i

, column

j

whenever vertex

i

touches edge

j

; every non-loop column will contain exactly two 1s. For a directed graph, use

+1

for the tail (source) of an edge and

-1

for the head (target). The sum of each row gives the degree of that vertex in the undirected case. Incidence matrices are especially useful for computations in network flow, circuit analysis, and algebraic graph theory.

Worked Example

Problem: Construct the incidence matrix for an undirected graph with vertices {A, B, C} and edges e₁ = {A, B}, e₂ = {B, C}, e₃ = {A, C}.

Set up the matrix: Create a 3×3 matrix with rows for vertices A, B, C and columns for edges e₁, e₂, e₃.

Fill in entries for e₁ = {A, B}: Vertex A and vertex B are endpoints of e₁, so place 1 in rows A and B of column e₁. Vertex C gets 0.

Fill in entries for e₂ = {B, C} and e₃ = {A, C}: Apply the same rule for the remaining edges to complete the matrix.

B = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}

Answer: The incidence matrix is the 3×3 matrix shown above. Each column sums to 2 (each edge has two endpoints), and each row sum gives the degree of that vertex (all vertices have degree 2).

Why It Matters

Incidence matrices appear throughout electrical engineering (Kirchhoff's laws rely on the oriented incidence matrix), network optimization, and algebraic graph theory. The matrix product

B B^T

is closely related to the Laplacian matrix, which drives spectral clustering algorithms and connectivity analysis.

Common Mistakes

Mistake: Confusing the incidence matrix with the adjacency matrix.

Correction: The adjacency matrix is square (vertex × vertex) and records which vertices are adjacent. The incidence matrix is rectangular (vertex × edge) and records which vertices touch which edges. They encode the same graph but have different dimensions and different entries.