Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Digital systems, linear algebra, introduction to formal proof / 4

Apply the elementary row operations from bottom to top: $R_4\leftarrow R_4-R_3$, $R_3\leftarrow R_3-R_2$, and $R_2\leftarrow R_2-R_1$. This order ensures that each subtraction uses the original preceding row. The result is the upper triangular matrixPut ${\delta }_1=a$, ${\delta }_2=b-a$, ${\delta }_3=c-b$, ${\delta }_4=d-c$. Row $i$ is either zero if ${\delta }_i=0$, or has its first nonzero entry in column $i$. Thus, for arbitrary real parameters, a row echelon form is obtained by retaining the nonzero rows of $T$ in their existing order and moving every zero row to the bottom. This deals explicitly with vanishing parameters; an upper triangular matrix with an intermediate zero row is not yet a row echelon form.

The subtractions preserve the determinant, so the original matrix hasA square matrix is invertible exactly when its determinant is nonzero. Consequently,These conditions concern consecutive parameters: no ordering, positivity, or pairwise distinctness of all four is required. More generally the rank of a matrix here is the number of nonzero ${\delta }_i$, because the retained nonzero rows have distinct leading columns.

Summing the flow conservation equations over all four junctions cancels every internal flow. The total entering flow is $300+500+250+50+100=1200$, and the known exiting flow is $700+200=900$. ThusThe original arrows point $A\to B$, $C\to A$, $B\to D$, and $C\to D$ for $f_2,f_3,f_4,f_5$, respectively. In particular, $f_1$ exits north from $A$.^[ref]

The individual flow conservation equations areChoose $t=f_5$. Substitution gives all solutions of these linear equations:The inequalities enforce nonnegative flows on all one-way streets. The last junction equation follows from the first three and total flow conservation, so it introduces no further restriction.

The maximum is $\boxed{f_5=150}$. It makes $f_2=f_3=0$. At $A$, all 300 vehicles arriving from the west turn north and leave along $f_1$; none arrives from $C$ or continues east to $B$.