

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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?

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
Your explain is very clear and easy to understand. I don't know how to relabel.I have tried permute the labels by hands but it seems time-consuming and does not work.Could you please illustrate or do you have some related study materials? Thanks : ) – John Hass Oct 29 '12 at 9:28

Your Answer


