# Network Simplex Method: How to relabel the vertices and arcs such that the truncated matrix is upper triangular and non-singular.

Suppose $G = (V, A)$ is the acyclic weakly connected digraph with$V$consisting of vertices $v_{i}$ $(i = 1, 2, ..., 8)$ in which the seven arcs are $(v 1 , v 2 ), (v 3 , v 2 ), (v 4 , v 3 ),(v 7 , v 2 ),( v 3 , v 6 ), (v 5 , v 6 )$ and $(v 8 , v 7 )$. Relabel the vertices and arcs such that when the last row of the incidence matrix is deleted, the truncated matrix is upper triangular and non-singular.

Aunt Google does not tell me what is relabel and why we need relabel. Could any one use this example to explain why we need relabel and how to relabel?

-

To relabel (at least in this case) means to permute the labels. The vertices are currently labeled $1$ through $8$; the arcs strictly speaking haven't been labeled but could be regarded to be implicitly labeled $1$ through $7$ in the order in which they're listed. If you write down the incidence matrix with the rows and columns ordered according to these labels (i.e. with the entry for vertex $v_1$ in the first row and so on and the entry for arc $(v_1,v_2)$ in the first column and so on) and delete the last row, the resulting matrix is not upper triangular (since it has an entry $1$ in the second row and first column, for example). The exercise is asking you to find a different ordering of the vertices and arcs such that if you write down the incidence matrix with the rows and columns ordered accordingly, deleting the last row leads to a matrix that's upper-triangular and non-singular.