Incidence Matrices of Graphs
MIT OpenCourseWare · Video · 20 min
Start at 0:37. Watch 0:37–3:37 for the edge-row convention, or the complete 20-minute video for incidence and cycles. Transpose its matrix for our edge columns.
Open the sourceThe first exact bridge: graph → matrix
A cycle is a linear dependence written in another dialect.
Prerequisites: 09 · Rank and the information that disappears, 13 · Graphs: connection and redundancy
Understand
Objectives
- Translate one oriented edge into a signed incidence column.
- Check a cycle relation and the 4×3 rank with an isolated vertex.
- Explain why flipping an orientation preserves column independence.
Start with something you can see
In the graph lab, select edges 1–2, 2–3 and 1–3, leaving vertex 4 isolated. Before filling the matrix, predict whether reversing 1–3 changes the cycle. It changes a sign, not the edge dependence. In Strang’s video each edge occupies a row; our edge columns are the transpose of that convention. The one-edge rule starts at 0:37. [1]
Give the idea a precise name
For an undirected graph, assign each edge a temporary direction. Its signed oriented incidence column has −1 at the starting vertex, +1 at the ending vertex, and 0 elsewhere. Put one column per edge and one row per vertex to make B. Strang’s row-per-edge matrix A has B=Aᵀ: a row relation in his convention is a column relation in ours. This is not an unsigned 0/1 matrix.
rank(B)=|V|−c(G); ker(B)={edge flows whose vertex sums vanish}
Each column represents one ground-set edge; each row tracks the net signed contribution at one vertex. A zero linear combination of selected columns is a cycle flow. On a forest, a leaf row contains one selected nonzero entry, forcing that coefficient to zero; removing leaves eliminates every coefficient. Conversely, a cycle has a nonzero signed flow. Thus an edge subset is a forest exactly when its columns are independent.
Work one small world
Orient the lab’s triangle as a:1→2, b:2→3, c:3→1. Vertex 4 stays as a zero row. The table links each button to its exact column. The MIT transpose and cycle-flow discussion begins at 6:49. [2]
| Lab edge | Direction | row 1 | row 2 | row 3 | row 4 |
|---|---|---|---|---|---|
| a: 1–2 | 1→2 | −1 | +1 | 0 | 0 |
| b: 2–3 | 2→3 | 0 | −1 | +1 | 0 |
| c: 1–3 | 3→1 | +1 | 0 | −1 | 0 |
The 4×3 matrix has a+b+c=0 and rank 4−2=2. Every pair of columns is independent. Flip c to 1→3: its column changes sign, and the relation becomes a+b−c′=0. The independent edge subsets are unchanged.
Counterexample to using unsigned incidence: for the triangle, columns with 1 at both endpoints form [[1,0,1],[1,1,0],[0,1,1]], whose determinant is 2. It has rank three over ℝ, so it does not exhibit the cycle relation. The signs are essential.
THE BRIDGEThe incidence columns realize graphic independence as linear independence; matroid axioms will keep that pattern without the matrix.
WHERE THIS IDEA STOPSThe transpose convention matters: do not confuse a row relation in Strang’s matrix with a column relation here, or substitute unsigned incidence.
Experiment
Use the graph lab buttons 1–2, 2–3 and 1–3, with vertex 4 untouched. Compare the rank and circuit display with the table; orientation is bookkeeping done in the table, not a lab control.
What does a leaf row force in a supposed zero linear combination?
Check & explain
For the triangle plus isolated vertex, what is the rank of its signed incidence matrix?
After reversing the orientation of c, what happens to the column matroid?
- It is unchanged
- The cycle becomes independent
- Its ground set becomes vertices
Teach back
Rebuild the 4×3 matrix from the edge buttons, flip c, and give the new nonzero kernel relation. Explain why the unsigned version fails.
- Label rows as vertices and columns as edges.
- Write a valid signed relation after the flip.
- Use the leaf or cycle argument, not a picture alone.