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

Let $G = (V,E)$ be a connected graph and $T$ one of its spanning trees. Let $w \in[0,1]^{|V|-1}$ be a weight for the spanning tree, i.e. we assign to each of the spanning tree's edges a number in $[0,1]$. For $(i,j) \in V \times V$ let $x_{ij}^T(w)$ be the minimum of the weights on the unique path from $i$ to $j$ in $T$. For $i=j$ we assign $x_{ij}^T(w) = 1$.

Theorem: The $|V| \times |V|$ real symmetric matrix $x_{ij}^T(w)$ is positive semidefinite. If we assume $w \in [0,1[^{|V|-1}$ it is even positive definite.

This positivity property is necessary for the absolute convergence of the reshuffled sum using the Loop Vertex Expansion. It is the central property of the forest formula, however I am wondering: Is there a simple proof not related to the forest formula at all?

//edit: The proof I already know is in Rivasseau's and Wang's "How To Resum Feynman Graphs".

share|cite|improve this question
I'm a little confused I think. What if $G=K_2=T$ and we assign $w(e)=1$. Then don't we get the non-positive semidefinite matrix $\begin{bmatrix} 0 & 1\\1& 0\end{bmatrix}$? – Casteels Dec 5 '13 at 13:17
I guess the real question I have is what value do we assign to the diagonal entries? – Casteels Dec 5 '13 at 13:21
@Casteels: I'm sorry I completely forgot. The diagonal entries are 1. – Huy Dec 5 '13 at 15:09
@user1551. What tree are you using and with what edge weights? From the first row, it seems you have the tree $2-1-3$ with $w(2,1)=0.8$ and $w(1,3)=0$, but then the (2,3) entry of the matrix would be 0. – Casteels Dec 7 '13 at 8:03
@Casteels: Was there a comment that is deleted now? – Huy Dec 7 '13 at 10:55
up vote 4 down vote accepted

Fun problem. Let the weights of the edges be $w_1 \leq w_2 \leq \cdots \leq w_{n-1}$. For convenience, define $w_0=0$ and $w_1=1$. Let $e_1$, $e_2$, ..., $e_{n-1}$ be the edges, in the same order as the weights. Let $D$ be the matrix in the problem.

For $1 \leq k \leq n$, let $D_k$ be the matrix where $(D_k)_{ij}=1$ if $D_{ij} \geq w_k$ and $(D_k)_{ij}=0$ otherwise. Then $$D = \sum_{k=1}^n (w_k-w_{k-1}) D_k.$$ So it is enough to show that each $D_k$ is positive semidefinite. Moreover, it is enough to check this in the case that $w_k > w_{k-1}$, as otherwise the coefficient of $D_k$ is $0$.

So, assume $w_{k-1} < w_k$. We have $(D_k)_{ij}=1$ if and only if the path from $i$ to $j$ does NOT pass through edges $e_1$, $e_2$, ..., $e_{k-1}$. In other words, let $F_k$ be the forest obtained by deleting $e_1$, $e_2$, ..., $e_{k-1}$ from $T$; then $D_k$ is the block diagonal matrix whose blocks correspond to the connected components of $F_k$ and where each block is a square matrix entirely made up of $1$'s. This matrix is definitely positive semi-definite.

Moreover, if $w_{n-1} <1$, then $D_n$ is the identity matrix, so the sum is positive definite.

After writing this up, I checked the proof in Rivasseau and Wang (Theorem 2.2) and this is basically the same thing, so I don't know if you will like it any better.

share|cite|improve this answer
I'm sorry I didn't refer to the paper earlier. I asked for an alternative proof because the proof provided was not very intuitive to me, i.e. I would have never been able to come up with it. Since you came up independently with basically the same proof: Is there any logical reason for introducing that matrix and decomposing the matrix $D$ as in your answer? Is it just experience or is there a deeper reason? I have never seen this kind of decomposition yet which is why it was rather odd for me. – Huy Dec 9 '13 at 16:50
I first (well, after some dead ends) thought about what happened when one $w(e)$ equalled $1$ and saw that two rows and two columns became identical. Adding more edges equal to $1$ made more rows and columns coincide. Going to the extreme of all weights $0$ or $1$ made a very pretty block matrix. Doing just $3$ weights: $0$, $w$ and $1$ made something that was still very blocky, and a little thought made me realize it was a linear combination of my two previous block matrices, which occurred in the limits of $w \to 0$ and $w \to 1$. – David Speyer Dec 9 '13 at 17:24

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.