could a spanning tree graph be expressed by a lower triangular matrix?

Question

Suppose a directed spanning tree graph $G$, there are $n$ nodes, and the root is node $1$. We express this graph by a matrix $M_{n\times n}$. If there is an directed edge from node $i$ to node $j$, the corresponding element in $M$ is $1$ ($e_{ji}=1$), otherwise it is $0$. All the diagonal elements are $0$.

I say: For any spanning tree graph $G$, the corresponding matrix $M_{n\times n}$ is always a lower triangular matrix.

Am I right? I didn't find the related documents to explain this.

Thanks for any help.

Answer 1

If the question is: "For an arbitrary labeling of the nodes, so long as the root is the first, is the resulting matrix triangular?" The answer is no.

For instance, a simple counterexample is a graph with edges $\{(v_1, v_3), (v_3, v_2)\}$. Then the adjacency matrix (as defined in the question) is $\left[\begin{smallmatrix} 0 & 0 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0\end{smallmatrix}\right]$.

In comments, you suggest the additional requirement that nodes are labeled so that destinations of an edge always come later than the source of the edge. In this case, the answer is yes, since every non-zero element of the matrix corresponds to an edge, and so the column index (the source node's label) is smaller than the row index (the destination node's label). Moreover, such a labeling can be found for any directed (rooted) tree. You can stratify the tree into "layers", with the root in layer 0, all its neighbors in layer 1, all their children in layer 2, etc., and then number them (proceeding across each layer in succession.) Another approach is to complete the partial order given by the tree to a linear order.

Answer 2

I tried to find a counter example and I came up with this one:

Edit: As was pointed out in the comments, my original example lacked the root condition.

Let $ V = \{ v_0, v_1, v_2 \} $ be the nodes and $ E = \{ (v_0,v_2), (v_2, v_1) \} $.

I think the resulting matrix should be:

$$ \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix} $$

The question here is: Is there a way to relabel the nodes so that the matrix is in lower triangular shape?