From Oriented Edges to a Matrix
A network flow has two ingredients: a quantity assigned to each edge and a conservation equation at each vertex. The incidence matrix organizes those equations so that one matrix-vector product gives the net flow at every vertex. Its columns record which two vertices an edge joins, with signs that depend on the edge’s chosen orientation.
Consider a finite network with vertices \(v_1,\dots,v_n\) and edges \(e_1,\dots,e_m\). Assume there are no edges from a vertex to itself; parallel edges are allowed. Choose an orientation for each edge, meaning that one endpoint is designated the tail and the other the head. This choice is a reference direction, not a claim that flow must actually travel that way.
With this sign convention, row \(i\) of \(\mathbf{B}\mathbf{x}\) gives the total flow leaving \(v_i\) along the chosen orientations, minus the total flow entering \(v_i\). An edge directed out of \(v_i\) contributes \(+x_j\); an edge directed into \(v_i\) contributes \(-x_j\). If \(\mathbf{b}\in\mathbb{R}^n\) is the prescribed net outward flow at each vertex, the conservation equations are
For example, a vertex with no external supply or demand must have net outward flow \(b_i=0\), so total internal inflow equals total internal outflow there. A positive \(b_i\) represents net flow supplied at that vertex, and a negative \(b_i\) represents net flow absorbed there. The equation describes signed real flows. If the application also requires every flow to follow its chosen orientation, that adds the inequalities \(x_j\ge 0\); those inequalities are not part of the matrix equation itself.
Building and Solving a Flow System
Worked Example: A Three-Edge Network
Use vertices \(A,B,C\) and orient the edges as \(e_1:A\to B\), \(e_2:B\to C\), and \(e_3:A\to C\). Build the incidence matrix, then solve for flows with prescribed net outward flow \(\mathbf{b}=(3,-1,-2)^{\top}\).
Use rows in the order \(A,B,C\) and columns in the order \(e_1,e_2,e_3\). Edge \(e_1\) contributes \((1,-1,0)^{\top}\), edge \(e_2\) contributes \((0,1,-1)^{\top}\), and edge \(e_3\) contributes \((1,0,-1)^{\top}\). Therefore
The equations, one per vertex, are \(x_1+x_3=3\), \(-x_1+x_2=-1\), and \(-x_2-x_3=-2\). Let \(x_3=t\). The first equation gives \(x_1=3-t\). Substituting this into the second gives \(x_2=x_1-1=2-t\). The third then reads \(-(2-t)-t=-2\), which holds for every \(t\). Thus the solutions are \(\mathbf{x}=(3-t,2-t,t)^{\top}\), with \(t\in\mathbb{R}\).
Taking \(t=1\) gives \(\mathbf{x}=(2,1,1)^{\top}\). Check by multiplication:
The one-parameter family reflects the fact that these three edges form a cycle: changing the flows around the cycle can leave every vertex’s net outward flow unchanged. The matrix equation, rather than a guess about individual routes, makes that freedom visible.
A general property of incidence matrices explains an important constraint on any solution. Every column contains one \(+1\) and one \(-1\), so the entries in each column sum to zero. Consequently, the net outward flow values across all vertices must sum to zero. For disconnected networks, the same reasoning applies separately within each connected component.
Proof. First suppose that \(\mathbf{B}\mathbf{x}=\mathbf{b}\) has a solution. Sum the equations corresponding to vertices in one component \(C\). Each edge incident to a vertex of \(C\) has both endpoints in \(C\), since otherwise those endpoints would belong to the same connected component. Its column contributes \(+x_j\) at its tail and \(-x_j\) at its head, so its total contribution to the sum is \(0\). Summing over all edges therefore gives \(\sum_{v_i\in C}b_i=0\). This also covers an isolated vertex: its row has no nonzero entries, so its equation requires \(b_i=0\).
Conversely, suppose the entries of \(\mathbf{b}\) sum to zero on every component. Work within one component and choose a vertex \(r\) as its root. For each other vertex \(v_i\), choose a path from \(v_i\) to \(r\), which exists because the component is connected. Assign a signed flow of \(b_i\) along that path, directed from \(v_i\) toward \(r\): use \(+b_i\) on an edge when its chosen orientation agrees with the path and \(-b_i\) when it disagrees. Set the flow on edges not used by any of these paths to zero, and add the assigned contributions if a path uses an edge more than once across this construction. Along the path from \(v_i\), the resulting net outward flow is \(b_i\) at \(v_i\), \(-b_i\) at \(r\), and \(0\) at each intermediate vertex, because the path flow entering an intermediate vertex equals the path flow leaving it. Adding the path flows for all vertices other than \(r\) gives net outward flow \(b_i\) at each non-root vertex and \(-\sum_{v_i\ne r}b_i=b_r\) at the root. The last equality follows from the assumed zero sum on the component. Thus the constructed flows solve the equations on this component. Doing this for every component gives a solution on the whole network. \(\square\)
Orientation Changes the Coordinates, Not the Network
Because an orientation is only a reference choice, reversing an edge should not change the physical flow represented by a solution. The signed coordinate for that edge must change sign at the same time.
Proof. Reversing an edge interchanges its tail and head, so its incidence column changes sign; columns for unreversed edges stay the same. Multiplication on the right by \(\mathbf{S}\) performs exactly these column sign changes, giving \(\mathbf{B}'=\mathbf{B}\mathbf{S}\). In the new orientation, the signed coordinate of each reversed edge must also change sign, while every other coordinate remains unchanged; this is \(\mathbf{x}'=\mathbf{S}\mathbf{x}\). Since every diagonal entry of \(\mathbf{S}\) is \(+1\) or \(-1\), \(\mathbf{S}^2=\mathbf{I}_m\). Therefore \(\mathbf{B}'\mathbf{x}'=\mathbf{B}\mathbf{S}\mathbf{S}\mathbf{x}=\mathbf{B}\mathbf{x}\), as required. \(\square\)
Worked Example: Reversing an Edge
Take three vertices \(1,2,3\), with edges \(1\to2\) and \(2\to3\). Find signed flows with net outward flow \(\mathbf{b}=(-4,0,4)^{\top}\), then reverse the first edge and check the new coordinates.
The incidence columns are \((1,-1,0)^{\top}\) and \((0,1,-1)^{\top}\), so
The equations are \(x_1=-4\), \(-x_1+x_2=0\), and \(-x_2=4\). The first gives \(x_1=-4\); the second gives \(x_2=x_1=-4\); the third becomes \(-(-4)=4\), so it is satisfied. Thus \(\mathbf{x}=(-4,-4)^{\top}\). Both negative coordinates mean the actual flow travels opposite the chosen direction on both edges. The multiplication check is
Now reverse the first edge, so the orientations are \(2\to1\) and \(2\to3\). The first column changes sign, and the signed flow on that edge changes from \(-4\) to \(4\):
Multiplying gives \(\mathbf{B}'\mathbf{x}'=(-4,4-4,4)^{\top}=(-4,0,4)^{\top}=\mathbf{b}\). The physical flow and the net outward flow at every vertex are unchanged.
A Tree Network and a Common Sign Error
Worked Example: Determining Flows on a Tree
Use vertices \(1,2,3,4\) and edges \(1\to2\), \(1\to3\), and \(3\to4\). Find the flows that produce \(\mathbf{b}=(5,-2,1,-4)^{\top}\).
The edge columns are \((1,-1,0,0)^{\top}\), \((1,0,-1,0)^{\top}\), and \((0,0,1,-1)^{\top}\), giving
The equations are \(x_1+x_2=5\), \(-x_1=-2\), \(-x_2+x_3=1\), and \(-x_3=-4\). The second equation gives \(x_1=2\); the fourth gives \(x_3=4\); the third then gives \(x_2=3\). The first checks because \(2+3=5\). Hence \(\mathbf{x}=(2,3,4)^{\top}\), and the full check is
The component total is \(5-2+1-4=0\), as required by the feasibility theorem. In this example the equations determine the flow on every edge; in a network with cycles, there may instead be multiple solutions.
Common mistake: giving both endpoints the same sign. For an edge \(A\to B\), a tempting but incorrect incidence column is \((1,1)^{\top}\). It would claim that sending flow \(3\) along this edge contributes \((3,3)^{\top}\), as if it were net outward flow at both endpoints. The correct column is \((1,-1)^{\top}\), so the contribution is \((3,-3)^{\top}\): flow leaves \(A\) and enters \(B\). The correct column also sums to zero, matching the fact that an internal edge cannot create or remove total flow.
When building a system, keep three choices consistent: the row order for vertices, the column order for edges, and the orientation assigned to each edge. Each column should have one \(+1\) at its tail and one \(-1\) at its head. Then \(\mathbf{B}\mathbf{x}\) has the stated net-outflow interpretation, and a solution can be checked by multiplying the matrix by the proposed flow vector. For an unrestricted signed-flow problem, the component-sum condition tells whether a solution exists; the equations determine the possible flows.
Check Your Understanding
Use the convention that each incidence column has \(+1\) at the tail and \(-1\) at the head.
- For edges \(1\to2\) and \(1\to3\), write the incidence matrix with rows \(1,2,3\) and columns in the order given.
- For the network with edges \(1\to2\), \(2\to3\), and \(1\to3\), solve \(\mathbf{B}\mathbf{x}=(2,-1,-1)^{\top}\) and verify your answer by multiplication.
- Why can no internal flow system on a connected network have prescribed net outward flows whose entries sum to a nonzero number?
- If one edge is reversed, what changes in its incidence column and in the coordinate that represents the same physical flow?
- A network has two connected components. What condition must the prescribed net outward flow satisfy on each component for a signed real solution to exist?
