Conservation certificates and potentials

Try

Four pipes connect vertices 1 through 4; vertex 5 is isolated. Declare the arrows 1→2, 2→3, 1→3 and 3→4, in that order. A positive pipe coordinate follows its arrow; a negative coordinate means flow against it. We are studying signed conservation equations, with no capacity or nonnegativity constraints. This convention is important: an arrow records a coordinate choice, not a one-way valve.

The required net inflow minus outflow is b=(−2,0,1,1,0). Vertex 1 supplies two units, vertices 3 and 4 each receive one, and the others have zero net balance. Write the five conservation equations before inspecting the table. With B equal to minus one at an edge’s tail and plus one at its head, those equations are Bf=b.

The equations force f₄=1, f₂=f₁ and f₃=2−f₁; the remaining equation is then satisfied. Thus the table describes every solution, not just several successful examples. Compare t=0 and t=1. Both conserve flow, but they use the two routes from 1 to 3 differently.

Predict

Predict whether zero total balance guarantees feasibility. Change the request to b=(−1,0,0,0,1). Its entries sum to zero, but the isolated vertex cannot receive anything. Its equation would be 0=1. The obstacle is not numerical accuracy or a poor choice of flow: it is an exact contradiction.

Express that contradiction as a certificate y=(0,0,0,0,1). Since Bᵀy=0 but yᵀb=1, any claimed solution would imply 1=yᵀb=yᵀBf=(Bᵀy)ᵀf=0. This is a left-null certificate. More generally, the indicator of each connected component checks that component’s total balance. Here the connected components are 4 and 5; connectivity ignores the arrows because flows are signed.

For the original feasible request, predict which t uses the least squared flow. The objective is t²+t²+(2−t)²+1=3(t−2/3)²+11/3. Its unique minimum is at t=2/3, giving f₀=(2/3,2/3,4/3,1). “Minimum norm” refers to this specified Euclidean objective, not automatically to monetary cost, travel time or a physical resistance model.

Experiment

Use the explorer to inspect the incidence equations and compare feasible and infeasible balance requests. Before reading a result, write down which component sums must vanish. For a feasible result, check every row of Bf=b and then check whether changing the circulation preserves those rows. Treat the explorer’s available controls as a bounded investigation; the written changed cases below can be computed on paper.

Which balances can this network carry?

Negative vertex demand means net supply; positive demand means net receipt. An edge arrow fixes a reference direction. A negative edge flow travels against that arrow; no capacity or nonnegative-flow constraint is imposed.

Demand caseMove two units from 1: one to 3, one to 4Move two units from 1 to 3Move one unit from 1 to isolated vertex 5 NetworkInclude edge 3 → 4Remove edge 3 → 4 Cycle parameter t02/312 Reset

Edges in order: 1 → 2; 2 → 3; 1 → 3; 3 → 4. Vertex 5 has no edges. Incidence columns have −1 at the tail and +1 at the head.

Requested balance b = (-2, 0, 1, 1, 0). Candidate signed flows f = (0, 0, 2, 1).

Actual balance Bf = (-2, 0, 1, 1, 0). Residual Bf − b = (0, 0, 0, 0, 0).

• Component vertices 1, 2, 3, 4: requested balance sum 0.
• Component vertices 5: requested balance sum 0.

The demands are feasible. These candidate flows solve Bf=b.

Rank 3; edge nullspace dimension 1; left nullspace dimension 2. These counts follow from the proved component formula, not a numerical rank threshold.

Candidate squared norm Σfⱼ² = 5. The minimum-norm flow is (0.6667, 0.6667, 1.3333, 1), with squared norm 3.6667. It is orthogonal to the cycle (−1,−1,1,0); the lesson proves why this certifies the minimum.

Noninteger values are rounded to four decimal places; t=2/3 is the exact mathematical selection. These bounded controls are temporary and award no completion.

Inspect the incidence matrix

Vertex 1: [-1, 0, -1, 0]

Vertex 2: [1, -1, 0, 0]

Vertex 3: [0, 1, 1, -1]

Vertex 4: [0, 0, 0, 1]

Vertex 5: [0, 0, 0, 0]

Predict which component balance fails when you remove edge 3 → 4. Then change the demand to send everything to vertex 3. Explain why changing the cycle parameter changes the flow but cannot change any vertex balance.

For the static worked example above, verify the minimum independently. A kernel vector is z=(−1,−1,1,0): moving along it changes the two-edge route and the direct route in opposite ways. Check Bz=0 and f₀ᵀz=−2/3−2/3+4/3=0. Every feasible flow is f₀+sz for some real s, and its squared norm is 11/3+3s². This exact identity certifies a minimum over all real s; a plot at a finite list of values would not do that.

Now assign vertex potentials p=(0,2/3,4/3,7/3,0). Compute each head potential minus tail potential. The four differences are exactly f₀. Change all first four potentials by the same constant, and change the isolated potential independently. Predict why none of the four edge differences changes. This is gauge freedom: multiple potential descriptions give the same edge flow.

Understand

For any incidence matrix, the edge entries of Bᵀy are head-minus-tail differences. Therefore Bᵀy=0 exactly when y is constant on every connected component. Equality propagates along paths; an isolated vertex permits its own arbitrary constant. Conversely, any componentwise-constant vector has zero edge differences.

The inner-product identity yᵀBf=(Bᵀy)ᵀf proves (im B)⊥=ker Bᵀ. In a finite-dimensional real inner-product space, taking the orthogonal complement again gives im B=(ker Bᵀ)⊥. This standard finite-dimensional decomposition is the theorem dependency here. Consequently Bf=b is solvable if and only if every component sum of b is zero. This proves sufficiency as well as the easier conservation necessity, without assuming the graph is connected.

For feasible b, any two solutions differ by a vector in ker B. A feasible f₀ is minimum norm exactly when it is orthogonal to that kernel. Sufficiency follows from ||f₀+z||²=||f₀||²+||z||². For necessity, if f₀ᵀz≠0, a sufficiently small real step s of the opposite sign makes ||f₀+sz||²=||f₀||²+2s f₀ᵀz+s²||z||² smaller. Both signs of s are allowed because no inequalities restrict the flow. The orthogonal minimum is unique.

Potentials construct this special solution. Solve BBᵀp=b and set f₀=Bᵀp. Then Bf₀=b, while f₀ᵀz=pᵀBz=0 for every circulation. To prove this equation is solvable for every feasible b, observe that pᵀBBᵀp=||Bᵀp||² gives ker(BBᵀ)=ker Bᵀ. Symmetry then gives im(BBᵀ)=(ker Bᵀ)⊥=im B. The matrix BBᵀ is singular whenever there is a component; singularity does not mean every right-hand side is impossible.

Differences of potential solutions are componentwise constants, so their edge flows coincide. For the worked example the entire potential family is (c,c+2/3,c+4/3,c+7/3,d). There are two independent offsets. Setting only p₁=0 does not determine p₅; one reference per component fixes the whole gauge.

Apply

Reverse the direct edge to 3→1 but keep the same physical balance. Predict the signed minimum before recomputing. Only the third coordinate changes sign, giving (2/3,2/3,−4/3,1). More generally, if D is diagonal with entries ±1 recording reversals, then the new matrix is BD and the new flow is Df. Since D²=I and ||Df||=||f||, conservation and minimum norm are unchanged. The potential equation is unchanged too: BDDᵀBᵀ=BBᵀ.

Now make a genuinely different model by requiring every coordinate on those reversed arrows to be nonnegative. Conservation gives (t,t,t−2,1), so t≥2. The former signed minimum is forbidden. The new minimum is at t=2, with flow (2,2,0,1) and squared norm 9. Check this by minimizing the same quadratic over the restricted ray, not over all real numbers.

Check the distinction with an infeasibility challenge

For the reversed graph, request b=(1,0,0,−1,0). Both component sums vanish, so a signed solution exists. But the only edge meeting vertex 4 enters it, and its equation requires f₄=−1. Nonnegative flows cannot satisfy that request. Component balance is an exact certificate for the unrestricted linear system; it is not a substitute for analyzing additional inequalities. The explorer’s signed-flow calculation does not certify a constrained transportation problem.

Prescribed potentials change which equations we solve

The preceding minimum-norm convention used f=Bᵀp as an algebraic potential construction. A passive resistor has a different physical sign: with B still minus at the tail and plus at the head, current flowing from higher potential to lower is j=−WBᵀv. Here W is diagonal with positive conductances; zero conductance means the edge is removed. Then L=BWBᵀ and −Bj=Lv is net outgoing current. External injection q into a vertex balances that outgoing current. A negative injection is withdrawal.

Divide vertices into prescribed boundary vertices D, with values g, and free interior vertices I, with specified injections q. Only the interior equations are imposed:

$$L_{II}u=q-L_{ID}g,\qquad v=(u,g),\qquad j=-WB^Tv.$$

The ordering v=(u,g) is for this block formula; the diagram retains vertex order 1–4. Boundary injections are the computed values (Lv) on D. They generally are not zero: a boundary reservoir must supply or remove current to maintain its potential. Imposing Lv=0 at every vertex would incorrectly forbid a nonconstant potential on a connected network.

Does every free component reach a prescribed potential?

Prescribe v1=1 and v4=0. Interior vertices 2 and 3 have zero external injection. Positive conductance carries current from higher to lower potential. Values use consistent dimensionless teaching units.

Cross-edge conductance c0124 NetworkBoth interior vertices connected to boundariesRemove all four boundary connections Reset boundary network

Interior potentials: v2=0.400000, v3=0.600000. Grounded determinant=15.

Signed currents on 1→2, 1→3, 2→3, 2→4, 3→4: 0.600000, 0.800000, -0.200000, 0.800000, 0.600000. Negative means opposite the named arrow.

External injections at vertices 1–4: 1.400000, 0.000000, -0.000000, -1.400000. Only the two interior entries must vanish. Boundary supply is not an equation error.

Dissipated power=1.400000; energy (half the power)=0.700000. With this unit potential difference the boundary input current equals total power.

Predict and explain before reading

Increasing the cross conductance tends to equalize the interior potentials. Removing every boundary connection destroys positive definiteness on the interior. Adding an external injection of one at vertex 2 and zero at vertex 3 in the floating case is impossible: summing the interior equations would give 0=1.

Eight bounded settings, temporary state and no automatic learning credit. Use the written tasks to prove the claims for general positive weighted graphs.

For the displayed graph at c=1, the interior equations are 4v2−v3=1 and −v2+4v3=2. Thus v2=2/5 and v3=3/5. The five ordered currents are 3/5,4/5,−1/5,4/5,3/5. They sum at each interior vertex to zero net injection, but the boundaries inject 7/5 and −7/5. A negative cross-edge current is physically allowed; an arrow only selects its coordinate sign.

Exactly when grounding gives uniqueness

For a finite graph, retain only edges of strictly positive conductance. Extend an interior vector z by zero on D, obtaining z̃. The energy identity is

$$z^T L_{II}z=\widetilde z^TL\widetilde z=\sum_{e=ab}w_e(\widetilde z_a-\widetilde z_b)^2.$$

It is nonnegative. It vanishes exactly when z̃ is constant on each connected component. If every component containing an interior vertex reaches D, its constant must be zero. Hence LII is positive definite and invertible, giving exactly one solution for every q and g. Conversely, the indicator of any interior component missing D is a nonzero null vector. This proves the precise condition; the entire graph need not be connected. Isolated interior vertices count as ungrounded components.

For an ungrounded component, summing its equations requires the sum of q there to be zero, since internal edge currents cancel. This is also sufficient: the symmetric block has kernel exactly the component constants, and its image is their orthogonal complement. On grounded components it is invertible. Thus an incompatible component sum gives no solution; compatible sums give a family with one additive constant per ungrounded component. Setting a reference potential is then an extra gauge choice, not a proof that the original problem had a unique potential.

Energy certificate and maximum principle

With boundary values held fixed, define E(v)=one half of the sum of conductance times squared edge drops. For nonzero interior injection, minimize F(u)=E(u,g)−qᵀu rather than E alone. At a solution u*, expansion and the interior equations cancel the linear term:

$$F(u_*+z)-F(u_*)=\frac12 z^TL_{II}z.$$

Positive definiteness proves unique global minimality. Without grounding, the same identity establishes minimality but allows the stated constant shifts when compatible. Also vᵀLv equals the total dissipated power, which is twice E. For q=0, only the boundary terms remain in vᵀLv; this checks the example’s power 7/5 and energy 7/10 independently of the interior solve.

When q=0, each nonisolated interior potential is the conductance-weighted average of its neighbors. An interior maximum strictly above all boundary values would force every adjacent vertex to have the same maximum, because all weights are positive. Propagate along a path to a boundary to obtain a contradiction. The minimum argument is identical. Thus every interior value lies between the minimum and maximum prescribed values in its component. Grounding and zero interior injection are necessary hypotheses for this argument; with a unit conductance from one interior vertex to boundary value zero and q=1, the interior value is one.

Changed graph: deleting an edge need not destroy uniqueness

A chain has conductances 2,3,6, in order from vertex 1 to vertex 4, with boundary values 3 and −1. Series resistance is 1/2+1/3+1/6=1, so current is 4. Interior values are 1 and −1/3. If the middle edge is removed, each interior vertex still touches its own boundary component: both components remain grounded, the unique interior values become 3 and −1, and all currents vanish. Deleting an edge is not the same as leaving a component ungrounded.

Source comparison: the MIT 18.06 Spring 2010 final, question 9 requests incidence, potential and fixed-boundary current calculations. This weighted example and general grounding proof are original practice; the archive is a dated comparator, not a claim of current exam equivalence. These statements concern finite passive linear networks, not nonlinear components, time-dependent circuits or a continuum boundary-value theorem.

Continue

Write three separate certificates in your solution: feasibility through component sums, conservation through the row equations, and minimum norm through orthogonality to every circulation. When a request fails, exhibit a left-null vector with nonzero pairing against b. When potentials are nonunique, identify their gauge rather than claiming the minimizing edge flow is also nonunique.

The practice changes balances, orientations and constraints and asks for general proofs. Keep the spaces distinct: vertex requests lie in im B, circulating edge adjustments lie in ker B, potential-generated flows lie in im Bᵀ, and component indicators lie in ker Bᵀ. Each space has a concrete role in deciding what a network can carry and which signed flow a chosen norm selects.