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

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.

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.

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?

• The question assumes that the root node ($v_3$ in this case) is the first one. Also it seems to say that the source of an edge is the column, and the destination of the edge is the row. So let's rename $v_3$ as $v_0$. The edges are $\{(v_1,v_2),(v_0,v_1)\}$. Then the matrix is lower triangular: $\left[\begin{smallmatrix}0 & 0 & 0\\1 & 0 & 0\\0 & 1 & 0\end{smallmatrix}\right]$. Jan 5, 2015 at 16:28
• Yes, you are right. If you rename the nodes so that $v_3$ is really the root, it works out fine. I will have to think about this. Jan 5, 2015 at 16:28
• Well, it's highly dependent on labeling. If you just switch $v_2$ and $v_1$ in your example, so we have edges $\{(v_2,v_1),(v_0,v_2)\}$, then the matrix is $\left[\begin{smallmatrix}0 & 0 & 0\\0 & 0 & 1\\1 & 0 & 0\end{smallmatrix}\right]$, which is not triangular. Jan 5, 2015 at 16:31
• Well, should the matrix not be: $\begin{pmatrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 1 & 0\end{pmatrix}$. Jan 5, 2015 at 16:34
• thanks for you all. I suppose that the numbers of the rows is just the order of the nodes along the information direction. so if edges are ${(v_0,v_2),(v_2,v1)}$, then the rows should represent $v_0,v_2,v_1$. Jan 5, 2015 at 16:36