Incidence matrix

WHAT is an incidence matrix?

Definition Incidence matrix

For a graph $G$ with $n$ vertices and $m$ edges, the incidence matrix is an == $n \times m$ == matrix $B$ where:

Rows = vertices ( $v_1 \dots v_n$ )
Columns = edges ( $e_1 \dots e_m$ )

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

Directed graph (oriented): $B_{ij} = \begin{cases} -1 & \text{if } e_j \text{ leaves } v_i \ (\text{tail}) \\ +1 & \text{if } e_j \text{ enters } v_i \ (\text{head}) \\ 0 & \text{otherwise} \end{cases}$

HOW to build it from scratch (derivation by construction)

We don't memorise a formula — we generate the matrix.

List every vertex → these label the rows.
List every edge as the pair of vertices it joins → these label the columns.
For each column (edge), put a mark in the rows of its two endpoints.

Worked Example 1 — Undirected

Graph: vertices $\{1,2,3\}$ , edges $e_1=(1,2),\ e_2=(2,3),\ e_3=(1,3)$ (a triangle).

	$e_1$	$e_2$	$e_3$
$1$	1	0	1
$2$	1	1	0
$3$	0	1	1

Why row 1 = 1 0 1? Vertex 1 is in edges $e_1$ and $e_3$ only. → Why this step? We scan each edge and ask "is vertex 1 an endpoint?"
Check degrees: each row sums to 2 → every vertex has degree 2. Correct for a triangle. ✔

Worked Example 2 — Directed

Edges: $e_1: 1\to 2$ , $e_2: 2\to 3$ , $e_3: 1\to 3$ .

	$e_1$	$e_2$	$e_3$
$1$	$-1$	0	$-1$
$2$	$+1$	$-1$	0
$3$	0	$+1$	$+1$

Why $B_{1,1}=-1$ ? Edge $e_1$ leaves vertex 1 (vertex 1 is the tail). → Why this step? Convention: tail negative, head positive.
Check: every column sums to 0. ✔

Worked Example 3 — Self-loop

Edge $e_1$ is a loop at vertex 1 (an edge $1\to1$ ).

	$e_1$
$1$	2

Why 2 (in undirected) instead of 1? A loop touches vertex 1 with both its endpoints, so it contributes 2 to the degree. → Why this step? Keeps the row-sum = degree rule consistent (loops add 2 to degree).

Common mistake Steel-manned common mistakes

Mistake 1: "Incidence matrix is square ( $n\times n$ )." Why it feels right: the adjacency matrix is square, so students assume all graph matrices are. The fix: incidence relates two different sets (vertices vs edges), so it's $n\times m$ . Only when $n=m$ does it look square by coincidence.

Mistake 2: "Column can have three 1's." Why it feels right: a vertex can have many edges, so it seems an edge could touch many vertices. The fix: an edge has exactly two endpoints, so each column has exactly two non-zeros (or one entry of "2" for a loop).

Mistake 3: "In directed graphs use 1/0 like undirected." Why it feels right: 1 = "connected" is intuitive. The fix: direction information is lost without signs. Use $-1$ (tail) / $+1$ (head) so that column sums vanish and $L=BB^T$ works.

Recall Feynman: explain to a 12-year-old

Imagine a list of friendships. Down the side you write everyone's name. Across the top you write each friendship like "Friendship #1". You put a tick in the box if that person is part of that friendship. Since a friendship always joins exactly two people, every column gets exactly two ticks. Count the ticks in your row and you know how many friends you have. That tick-grid is the incidence matrix — a way to write friendships in pure numbers so a computer can read them.

Flashcards

What are the dimensions of an incidence matrix for a graph with n vertices and m edges?

n \times m

(rows = vertices, columns = edges).

In an undirected incidence matrix, how many non-zero entries does each column have?

Exactly two (the two endpoints), or a single "2" for a self-loop.

What does the sum of row

i

equal (undirected)?

The degree of vertex

v_i

In a directed incidence matrix, what values mark the tail and head of an edge?

Tail =

-1

, Head =

+1

Why does every column of a directed incidence matrix sum to 0?

Each edge has one tail (

-1

) and one head (

+1

); they cancel.

How does a self-loop appear in an undirected incidence matrix?

As a single entry of

2

in that vertex's row (loop adds 2 to degree).

How does the incidence matrix prove the Handshake Lemma?

Total 1's counted by columns =

2m

; counted by rows =

\sum\deg(v_i)

; so

\sum\deg = 2m

What is the graph Laplacian in terms of incidence matrix B (directed)?

L = B B^T

Connections

Adjacency matrix — alternative $n\times n$ representation (vertex-to-vertex).
Graph Laplacian — built as $L=BB^T$ from the oriented incidence matrix.
Degree of a vertex — equals a row sum here.
Handshake Lemma — falls out of counting incidence marks.
Sparse graph representations — incidence lists/CSR for big graphs.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, graph ek picture hai — dots (vertices) aur unko jodne wali lines (edges). Computer ko ye picture samajhane ke liye usko numbers me convert karna padta hai. Incidence matrix bilkul ek attendance register jaisa hai: rows me vertices likho (students), columns me edges likho (classes). Agar koi vertex us edge ka endpoint hai, to wahan mark laga do. Isliye matrix ka size hota hai $n \times m$ — n vertices, m edges. Yaad rakho, ye adjacency matrix ki tarah square nahi hota, kyunki yahan hum vertices ko edges se relate kar rahe hain, vertices ko vertices se nahi.

Undirected graph me har column me bas do 1 hote hain — kyunki har edge ke sirf do endpoints hote hain. Agar tum kisi row ka sum karo, to wo us vertex ka degree ban jaata hai (kitni edges us pe lagi hain). Isi se Handshake Lemma aa jaata hai: total marks ko columns se gino to $2m$ , aur rows se gino to $\sum \deg$ — dono barabar, matlab $\sum\deg = 2m$ .

Directed graph me thoda twist hai: 0/1 ki jagah hum $-1$ (jahan se edge nikalti hai, tail) aur $+1$ (jahan edge aati hai, head) lagate hain. Isse har column ka sum 0 ho jaata hai, kyunki ek tail aur ek head cancel kar dete hain. Yahi cheez aage graph Laplacian $L = BB^T$ banane me kaam aati hai, jo machine learning aur network analysis me bahut use hota hai.

Common galti: log ise square ( $n\times n$ ) samajh lete hain ya column me 3 marks daal dete hain. Bas yaad rakho — "ek edge ke do hi endpoints hote hain", isliye column me hamesha do hi marks (ya self-loop ke liye ek "2"). Yeh chhota sa rule clear ho gaya to incidence matrix ka pura concept clear ho jaata hai.