Characterizing a certain set of matrices arising from binary trees

Question

Suppose I have a binary tree, like

v1           v4
  \         /
   --------
  /         \
v2            v3

I can write a matrix for this tree whose $(i,j)$th entry gives the distance between vertex $i$ and $j$. In this case we would have:

$$A =\left( \begin{array}{cccc} 0&2& 3 &3 \\ 2& 0 &3&3\\ 3& 3 & 0 &2\\ 3&3&2&0 \end{array} \right)$$

These matrices have some nice properties, for instance:

• If you compute $\sum 2^{1-i}$ where the $i$ range over all the nonzero entries in a row, you get $1$
• They are symmetric, with zeroes on the diagonal
• Given such a matrix you can recover the original tree.

My questions are as follows:

These seem like fairly natural structures to consider. Do they have a name? Can you point me to any reference about them?

I most of all would like to be able to characterize all matrices which arise in this way, but really any information would be a help.

Edit: I'm not sure if this is going to be helpful, but I'll attempt to explain what I'm doing in an attempt to shed light on what I mean when I say "characterize". I'm working on a larger problem, involving two binary trees $S$ and $T$ (of the same size) together with an function $\sigma: leaves(S) \to leaves(T)$.

There is some quantity $f(S;T;\sigma)$ which depends on $\sigma$, and can be easily estimated by knowing these matrices. The goal is to prove that $f(S;S;id)$ bounds $f(S;T;\sigma)$ for any tree $T$, map $\sigma$.

It may be that this is just a dream and the simplest characterization is just "try to reconstruct the tree and see if you fail" but it would be really helpful to have something like "$A$ works if and only if it satisfies all equations of the form $g_n$" (note that this is just an example, and I'd really be happy with anything "clean")

Sorry if this is all quite nebulous.

Answer 1

I don't think I've seen a name of this type of matrix, other than "tree distance matrix" (which would be a special case of graph distance matrices).

Characterization depends on what kind of criteria you might be looking for. For example, a trivial way of characterizing them is by their one-to-one relation with unrooted binary trees, but this is trivial. However, this means generating all such matrices is equivalent to generating all unrooted binary trees.

A converse characterization could be a simple set of rules to check if a matrix $D=[d_{ij}]$ is a tree distance matrix. One way to do this is as follows.

1. Verify that it is symmetric, has zero on the diagonal, but with all other values integers $\ge2$.

2. Pick a cell, $(i,j)$ with $i\not=j$, with distance value 2: i.e. $d_{ij}=2$. Then, it is required that for all $r$ different from $i$ and $j$, $d_{ir}=d_{jr}$. Now, make a new matrix $D'$ where rows/columns $i$ and $j$ have been replaced with a row/column $k$ and $d'_{kr}=d_{ir}$, $d'_{kk}=0$: i.e. merge rows/columns $i$ and $j$, reducing all off-diagonal values by 1. Again, we should have $d'_{kr}\ge2$ for $r\not=k$.

3. Repeat step 2 on the reduced matrix ($D'$) until either it has been reduced to the $1\times1$ matrix $[0]$, in which case the original matrix was a tree distance matrix, or till there are no more cells $d_{ij}=2$ for which rule 2 may be applied, in which case it was not a tree distance matrix.

If this is good enough to fit what you'd consider a characterization of tree distance matrices, I suppose would depend on what the characterization is to be used for.

---

As you have noted, for any row/column $i$, the sum $\sum_{j\not=i}2^{-d_{ij}}=1/2$. Unfortunately, this is not a sufficient restriction. Two counter-examples are $$ \begin{pmatrix} -&3&3&3&3\\ 3&-&3&3&3\\ 3&3&-&3&3\\ 3&3&3&-&3\\ 3&3&3&3&-\\ \end{pmatrix} \quad\text{and}\quad \begin{pmatrix} -&2&4&4&5&6&6&4\\ 2&-&4&4&5&6&4&6\\ 4&4&-&2&5&4&6&6\\ 4&4&2&-&5&5&5&5\\ 5&5&5&5&-&2&4&4\\ 6&6&4&5&2&-&4&4\\ 6&4&6&5&4&4&-&2\\ 4&6&6&5&4&4&2&-\\ \end{pmatrix} $$ I suppose there might be other simple counter-examples as well.

There's another criterion that a tree distance matrix has to satisfy. For any four distinct leaves, $i,j,k,l$, of the four sums $$ (ij|kl)=d_{ij}+d_{kl},\, (ik|jl)=d_{ik}+d_{jl},\, (il|jk)=d_{il}+d_{jk}, $$ two of them must be identical while the third one is smaller than the two others: e.g. $$ (ij|kl)<(ik|jl)=(il|jk). $$ However, I don't think this is enough: it should be enough to give you a tree structure with weighted edges, but you'd need some extra criterion to ensure the edges all have weight 1.