Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Say I have a directed network that is organized in a tree, with all connections going downstream (genealogically). By that I mean that there is one root node connected to $c_{00}$ child nodes, and each $jth$ child node at generation $i$ (of which there are $\sum_{j} c_{(i-1),j}$) is connected to $c_{ij}$ child nodes. If I line up these $c_{ij}$ as a matrix where $i$ is the column index and $j$ is the row index, I have something like this:

$$ \begin{bmatrix} 2 & 2 & 1 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix} $$

This would correspond to a network where the root node is connected to two child nodes, one of which is connected to two grandchild nodes, while the other has no children. The grandchildren are each connected to one child node, both of which are childless. (These values are the Hamming distance of each $ij$th column of the adjacency matrix from zero (the number of nonzero connections at each node).)

I think that the adjacency matrix of a network like this is nilpotent, as long as there are a finite number of generations. Is this conjecture true, or are there limiting conditions on the child counts, or am I totally wrong?

share|cite|improve this question
This is true. ${}$ – Qiaochu Yuan Mar 30 '13 at 2:15
It doesn't seem totally obvious, though. What if the edge weights are large compared to the number of edges? – Trevor Alexander Mar 30 '13 at 3:03
The adjacency matrix itself is not weighted and, as Qiaochu states, is nilpotent. The matrix you have provided as an example is not an adjacency matrix. – Chris Godsil Mar 30 '13 at 13:01
Yeah, the matrix I described above is definitely not. I was just trying to be absolutely clear about what sort of structure I was describing. Are you saying that all adjacency matrices of directed graphs are nilpotent? – Trevor Alexander Mar 30 '13 at 19:06
@Trevor Alexander: no, we're saying that adjacency matrices of directed graphs without cycles are nilpotent. – Chris Godsil Mar 31 '13 at 1:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.