Incidence matrix: Visual walkthrough — Coding deep dive

We build everything from zero. If a word or symbol shows up, it gets a picture first.

Step 1 — Start with dots and lines (nothing else)

WHAT. A graph is a collection of dots and lines that join two dots. The dots are called vertices (one of them is a vertex). The lines are called edges. That is the whole object — there are no numbers yet.

WHY. A computer cannot store a picture. It stores numbers in a grid. So our real goal is: turn this drawing into a rectangle of numbers without losing any information about who-connects-to-whom. Before we can encode a thing we must name its parts, so we name them here.

PICTURE. Three vertices labelled $1, 2, 3$ and three edges labelled $e_{1}, e_{2}, e_{3}$ . Look at the amber labels on the edges — each edge is a thing with a name, exactly like each vertex is.

Step 2 — Ask ONE question per (dot, line) pair

WHAT. We invent a grid. Down the left side we write the vertices (rows). Across the top we write the edges (columns). For every box in this grid we ask one yes/no question:

“Does this vertex touch this edge?” (Is this dot one of the two ends of this line?)

WHY. Notice the question relates a vertex to an edge — two different kinds of thing. That is the key design choice. The adjacency matrix relates vertex-to-vertex; here we relate vertex-to-edge. Because we ask the question once per (vertex, edge) pair, the grid must have one row per vertex and one column per edge.

PICTURE. The empty register: rows are vertices, columns are edges, every cell is a waiting question mark. The cyan arrow shows the single question we drop into each box.

Step 3 — Fill one column by looking at one edge

WHAT. Take a single column, say the column of edge $e_{1}$ . Edge $e_{1}$ joins vertices $1$ and $2$ . So in that column we write a $1$ in row $1$ and a $1$ in row $2$ , and $0$ everywhere else.

WHY. A line has exactly two ends. The two ends are the only vertices that "touch" this edge. Every other vertex answers "no" $\to 0$ . This is why a column can never have three $1$ 's: an edge simply cannot have three ends.

PICTURE. Edge $e_{1}$ glowing amber, with two cyan arrows shooting up into the cells $(1, e_{1})$ and $(2, e_{1})$ , each dropping a $1$ .

Step 4 — Repeat for every column: the full undirected matrix

WHAT. Do Step 3 for $e_{2} = (2, 3)$ and $e_{3} = (1, 3)$ too. Each edge fills its own column with exactly two $1$ 's.

WHY. The grid is finished the moment every edge (column) has answered. No memorisation happened — we just scanned each line and marked its two ends.

PICTURE. The completed triangle matrix, with each column colour-linked back to its edge in the graph so you can trace where every $1$ came from.

The matrix we just grew:

$B = 123 e_{1} 110 e_{2} 011 e_{3} 101$

Column $e_{1}$ has $1$ 's in rows $1, 2$ → edge joins vertices $1, 2$ . ✔
Column $e_{2}$ has $1$ 's in rows $2, 3$ → edge joins vertices $2, 3$ . ✔
Column $e_{3}$ has $1$ 's in rows $1, 3$ → edge joins vertices $1, 3$ . ✔

Step 5 — Read the rows: degree appears for free

WHAT. Add up the numbers along a single row. Row $1$ is $1 + 0 + 1 = 2$ . That total equals the degree of vertex $1$ — the number of edges sticking out of it.

WHY. A row has a $1$ in the column of every edge that touches that vertex. So counting the $1$ 's in a row is literally counting the edges at that vertex. Counting edges at a vertex is the definition of degree (Degree of a vertex).

PICTURE. Row $1$ highlighted; two amber arrows point at its two $1$ 's and merge into the label $de g (1) = 2$ .

Step 6 — Count the marks two ways: the Handshake Lemma

WHAT. Count all the $1$ 's in the whole matrix in two different ways.

By columns: every column has exactly $2$ marks, and there are $m$ columns → $2 m$ marks.
By rows: each row sums to $de g (v_{i})$ , so the grand total is $\sum_{i} de g (v_{i})$ .

Both count the same marks, so they must be equal: $\sum_{i} de g (v_{i}) = 2 m .$

WHY. This is the Handshake Lemma, and the incidence matrix proves it just by counting the same dots two ways. No cleverness — the grid does the work.

PICTURE. The matrix with a cyan bracket under it labelled "count by columns $= 2 m$ " and an amber bracket beside it labelled "count by rows $= \sum de g$ ", both pointing at the same field of $1$ 's.

Step 7 — Add direction: signs are born

WHAT. Now give every edge an arrow (a direction). The end the arrow leaves is the tail; the end it enters is the head. We change the rule: put $- 1$ in the tail's row and $+ 1$ in the head's row.

WHY. With plain $1$ 's we cannot tell $1 \to 2$ from $2 \to 1$ — direction is lost. The minus sign records "the arrow left here"; the plus sign records "the arrow arrived here." Now the number's sign carries the direction.

PICTURE. Edge $e_{1}$ drawn as an arrow from $1$ to $2$ ; a red $- 1$ drops into cell $(1, e_{1})$ (tail) and a cyan $+ 1$ into cell $(2, e_{1})$ (head).

Directed triangle ( $e_{1} : 1 \to 2, e_{2} : 2 \to 3, e_{3} : 1 \to 3$ ):

$B = 123 e_{1} - 1 + 1 0 e_{2} 0 - 1 + 1 e_{3} - 1 0 + 1$

Every column now sums to $0$ : each edge has one $- 1$ (tail) and one $+ 1$ (head) that cancel. That vanishing sum is exactly what makes the Graph Laplacian $L = B B^{T}$ work. In symbols $1^{T} B = 0$ , where $1$ is the column of all-ones.

Step 8 — The degenerate case: a self-loop

WHAT. A self-loop is an edge that starts and ends at the same vertex (an edge $1 \to 1$ ). In the undirected matrix its column holds a single $2$ in that vertex's row.

WHY. A loop touches vertex $1$ with both of its ends. Each end contributes $1$ to the touch-count, so together they contribute $2$ . This keeps the "row sum = degree" rule honest: a loop adds $2$ to a vertex's degree, so it must add $2$ in the matrix. (For directed graphs the tail $- 1$ and head $+ 1$ land in the same cell and cancel to $0$ , which is why loops are treated separately — they carry no orientation information.)

PICTURE. A single vertex with a lasso-shaped loop; both ends of the lasso point back into cell $(1, e_{1})$ , stacking to a $2$ .

The one-picture summary

Everything above, compressed: a graph on the left, the register in the middle, and the two readings (columns give edges & $2 m$ ; rows give degree) fanning out on the right — undirected on top, directed (with signs) on the bottom.

Recall Feynman retelling — the whole walk in plain words

I drew some dots and some lines. I made a grid: names down the side, lines across the top. For each box I asked one dumb question — "is this dot an end of this line?" — and wrote $1$ for yes, $0$ for no. Because a line always has exactly two ends, every column got exactly two $1$ 's. When I added up a row I was secretly counting the lines at that dot — that's its degree. Counting all the $1$ 's by columns gave $2 m$ ; counting them by rows gave the sum of degrees; same marks, so $\sum de g = 2 m$ — the Handshake Lemma, for free. Then I put arrows on the lines and swapped one $1$ for $- 1$ (where the arrow leaves) so direction wasn't lost; now every column cancels to $0$ , which is the seed of the Laplacian. The only oddball is a line from a dot to itself — it touches that dot twice, so it writes a $2$ . That grid of numbers is the incidence matrix, and I never memorised a formula — I just watched it grow.

Connections

Incidence matrix — the parent note (rules & worked examples).
3.5.03 Incidence matrix (Hinglish) — same ideas in Hinglish.
Adjacency matrix — the $n \times n$ vertex-to-vertex alternative.
Graph Laplacian — $L = B B^{T}$ , built from Step 7's signed matrix.
Degree of a vertex — the row sum of Step 5.
Handshake Lemma — the two-way count of Step 6.
Sparse graph representations — how huge matrices are stored compactly.