Read all four spaces of a network incidence matrix

Try

A network records transfers between five labeled locations. Its reference directions are e₁:1→2, e₂:2→3, e₃:1→3 and e₄:3→4. Location 5 is isolated. A positive edge coordinate means transfer along its arrow; a negative coordinate means transfer against it. We work over the real numbers and impose no capacity or nonnegativity constraints.

Send one unit along e₁ and one along e₂. Compare the net change at every location with sending one unit along e₃. Both remove one unit at 1 and add one at 3; the intermediate location 2 has no net change. Thus different edge instructions can have exactly the same vertex result. This is a concrete reason for a nonzero kernel, not a numerical accident.

Predict

The incidence matrix B has one row per vertex and one column per edge. Each column has −1 at its tail and +1 at its head. For an edge vector x, the vertex vector Bx records net inflow: incoming transfers minus outgoing transfers. Predict B(−1,−1,1,0) before multiplying. It reverses the two-edge route and adds the direct route, so all vertex changes cancel.

Also predict what a vector y in the kernel of Bᵀ means. Its edge coordinate is y at the head minus y at the tail. All these differences vanish precisely when y is constant along every component. The isolated vertex supplies its own independent constant; forgetting it loses a genuine condition.

Experiment

Copy the matrix and multiply by x=(2,2,0,1). You should obtain (−2,0,1,1,0). Add any multiple of (−1,−1,1,0) to x and repeat. Your output remains unchanged. Then reverse the e₃ arrow, negate column 3 and negate the third edge coordinate. Check that the vertex result is again unchanged.

B: vertex rows and edge columns

Vertex	e₁	e₂	e₃	e₄
1	−1	0	−1	0
2	1	−1	0	0
3	0	1	1	−1
4	0	0	0	1
5	0	0	0	0

Let b₁,…,b₄ denote the columns and r₁,…,r₅ the rows. The column identity b₃=b₁+b₂ immediately predicts a dependency. Columns b₁,b₂,b₄ are independent: in a combination equal to zero, row 4 first forces the b₄ coefficient to vanish, row 3 then forces the b₂ coefficient to vanish, and row 2 forces the b₁ coefficient to vanish. Hence rank B=3.

Here are all four spaces, with coordinates stated explicitly. Reconstruct each listed basis from the matrix rather than trusting its length alone.

Space	Ambient space	Basis	Dimension
Column space	R⁵, vertices	b₁,b₂,b₄	3
Kernel	R⁴, edges	(−1,−1,1,0)	1
Row space	R⁴, edges	(−1,0,−1,0), (1,−1,0,0), (0,0,0,1)	3
Left kernel, ker Bᵀ	R⁵, vertices	(1,1,1,1,0), (0,0,0,0,1)	2

For the kernel, solving the rows gives x₂=x₁, x₄=0 and x₃=−x₁, which is exactly the displayed one-dimensional span. The listed rows r₁,r₂,r₄ are independent by inspecting columns 3,2,4 in that order, and r₃=−r₁−r₂−r₄, r₅=0. For the left kernel, the edge equations force y₁=y₂=y₃=y₄ while y₅ is free. These calculations prove spanning as well as membership.

Understand

We now prove the general mechanism. Take a finite loopless undirected graph, with arbitrary reference orientations, n≥1 vertices, m edges and c connected components. Parallel edges may be distinguished. Connectedness here ignores the reference arrows. Choose a spanning tree in each component; an isolated vertex contributes an empty tree. Such trees can be constructed by repeatedly adding an edge reaching a new vertex until the component is exhausted. They contain every vertex, have no cycle and together form a spanning forest.

A tree on v vertices has v−1 edges: for v>1 take a longest simple path, whose endpoint has degree one, remove that leaf and use induction. Thus the forest has n−c edges. Its incidence columns are independent. In any zero linear combination a leaf row has just one remaining forest entry, either +1 or −1, so its coefficient is zero. Remove that edge and leaf and repeat in each component. Every coefficient is forced to vanish.

Every other edge column is a signed sum of forest columns. For an edge from u to v, follow the unique forest path from u to v, assigning +1 to an edge traversed along its orientation and −1 when traversed against it. Each interior vertex has one arrival and one departure, so its terms cancel. The remaining vector is −1 at u and +1 at v, exactly the desired edge column. Consequently the independent forest columns span every column and

rank B=n−c; dim ker B=m−n+c.

This proof also works when there are no edges: c=n and the empty list is a basis of the zero column space. A loop, if permitted under a different graph convention, would give a zero column; we excluded loops to keep the edge description uniform.

What exactly is the column space? Summing the entries of any column over a component gives zero. Therefore every Bx has sum zero on each component. Conversely, the space of vertex vectors with those zero sums has dimension n−c: on a component with v vertices choose the first v−1 coordinates freely and set the last to minus their sum. Our column space lies inside this space and has that same dimension, so the two are equal. This is both a necessary and sufficient real solvability criterion. A single global sum is insufficient when the graph is disconnected.

The left kernel consists exactly of vectors constant on each component: Bᵀy=0 asserts equal values at the two ends of every edge, which propagate along paths. The c component indicator vectors form a basis, including indicators of isolated vertices. They are independent because their nonempty supports are disjoint.

Finally, an edge vector Bᵀy is orthogonal to every circulation z in ker B, since ⟨Bᵀy,z⟩=⟨y,Bz⟩=0. Thus row B is contained in (ker B)⊥. Both dimensions equal rank B in Rᵐ, so equality holds. Likewise col B=(ker Bᵀ)⊥ in Rⁿ. The word “cycle” in this interpretation allows signed traversal against reference arrows: in the worked triangle the circulation (−1,−1,1,0) exists even though its reference arrows have no directed cycle. These orthogonality statements use the ordinary real dot product.

Apply

Delete the bridge e₄ but keep vertices 4 and 5. Predict the dimensions before calculating: there are now three components and three edges, so rank is 5−3=2 and nullity is 3−2=1. The remaining triangle still supplies (−1,−1,1). The column space now requires d₁+d₂+d₃=0 and d₄=d₅=0. Its basis is b₁,b₂ with the fifth and fourth coordinates retained. The row space in R³ has basis (−1,0,−1),(1,−1,0). The left kernel has basis (1,1,1,0,0),(0,0,0,1,0),(0,0,0,0,1). A formerly connected vertex has become an independent conservation condition.

For an unfamiliar change, retain all original edges and add e₅:4→1. Construct its column and prove it equals −b₁−b₂−b₄. Rank stays 3, while the edge kernel grows to dimension 2. Find the added circulation (1,1,0,1,1), verify all five vertex equations, and prove that it and (−1,−1,1,0,0) form a basis. Their fifth coordinates distinguish them, so independence is immediate; the dimension calculation then proves spanning. Explain why merely adding an edge need not increase rank.

Continue

Use the four spaces as distinct certificates: column membership tests possible vertex demands, the left kernel detects component imbalance, the edge kernel describes nonuniqueness, and the row space identifies edge differences produced by vertex potentials. Do not confuse the vertex and edge ambient dimensions, or treat a negative real flow as forbidden without explicitly adding inequalities.

Return to rank, kernels and pivot columns for the algebraic dimension tools, or adjoints and orthogonal complements for the general orthogonality argument. The next network investigation can use these certificates to solve demands and compare different feasible flows; the present lesson establishes the spaces on which that analysis depends.