Moore-Penrose inverse of distance Laplacians of trees are Z matrices
R. Balaji and Vinayak Gupta

(In memory of Professor Michael Neumann)

11footnotetext: Corresponding author: Vinayak Gupta, Email address:
<EMAIL_ADDRESS>
###### Abstract

We show that all off-diagonal entries in the Moore-Penrose inverse of the
distance Laplacian matrix of a tree are non-positive.

Keywords: Trees, distance matrices, Laplacian matrices, Distance Laplacian
matrices, Moore-Penrose inverse.
AMS CLASSIFICATION. 05C50

##  1 Introduction

Let $T$ be a tree on $n$ vertices $\\{1,\dotsc,n\\}$. Suppose to each edge
$(p,q)$ of $T$, a positive number $w_{pq}$ is assigned. We say that $w_{pq}$
is the weight of $(p,q)$. The distance between any two vertices $i$ and $j$,
denoted by $d_{ij}$, is the sum of all the weights in the path connecting $i$
and $j$. The distance matrix of $T$ is then the $n\times n$ matrix with
$(i,j)^{\rm th}$ entry equal to $d_{ij}$ if $i\neq j$ and $d_{ii}=0$ for all
$i=1,\dotsc,n$.

Define

$\eta_{i}=\sum\limits_{j=1}^{n}d_{ij}~{}~{}\mbox{and}~{}~{}\Delta:=\mathop{\rm
Diag}(\eta_{1},\dotsc,\eta_{n}).$

The distance Laplacian of $T$ is then the matrix $L_{D}:=\Delta-D$. Distance
Laplacian matrices are introduced and studied in [4]. Recall that the
classical Laplacian matrix of $T$ is $L:=\nabla-A$, where $A$ is the adjacency
matrix of $T$ and $\nabla$ is the diagonal matrix with $\nabla_{ii}$ equal to
degree of vertex $i$. We note some properties common to $L_{D}$ and $L$.

  1. (i)

$L_{D}$ and $L$ are positive semidefinite.

  2. (ii)

Row sums of $L_{D}$ and $L$ are equal to zero.

  3. (iii)

$\mathop{\rm rank}(L)=\mathop{\rm rank}(L_{D})=n-1$.

  4. (iv)

All off-diagonal entries of $L$ and $L_{D}$ are non-positive.

In this paper, we deduce a property of distance Laplacian matrices of trees
which the classical Laplacian matrices do not have. An $n\times n$ real matrix
$A=[a_{ij}]$ is called a Z matrix if all the off diagonal entries of $A$ are
non-positive. The objective of this paper is to show that $L_{D}^{{\dagger}}$
is always a Z matrix. In the following example, we see that $L$ is the
classical Laplacian of a path on four vertices, but $L^{\dagger}$ is not a Z
matrix.

$L=\left[\begin{array}[]{ccccc}1&-1&0&0\\\ -1&2&-1&0\\\ 0&-1&2&-1\\\
0&0&-1&1\end{array}\right]~{}~{}~{}~{}~{}\mbox{and}~{}~{}~{}~{}~{}L^{\dagger}=\left[\begin{array}[]{ccccc}\frac{7}{8}&\frac{1}{8}&\frac{-3}{8}&\frac{-5}{8}\\\
\frac{1}{8}&\frac{3}{8}&\frac{-1}{8}&\frac{-3}{8}\\\
\frac{-3}{8}&\frac{-1}{8}&\frac{3}{8}&\frac{1}{8}\\\
\frac{-5}{8}&\frac{-3}{8}&\frac{1}{8}&\frac{7}{8}\end{array}\right].$

Distance matrices are well studied and have many interesting properties and
applications: see [1]. Numerical experiments reveal several new results on
distance matrices. For example, a perturbation result says that if $D$ is the
distance matrix of a tree and $L$ is the Laplacian of some connected graph
(with same number of vertices), then all entries in $(D^{-1}-L)^{-1}$ are non-
negative: See Theorem 4.6 in [2]. A far reaching generalisation of this result
for matrix weighted trees is shown in Theorem 2.1 in [3]. Again this result
was motivated by numerical experiments. Our result here is also motivated by
numerical computations.

If $A$ is a Z matrix, then we say it is an M matrix if all the eigenvalues of
$A$ have a non-negative real part. A question in [6] asks when the group
inverse of a singular irreducible matrix M matrix is again an M matrix.
Another question in resistive electrical networks [8] asks when is the Moore-
Penrose inverse of a Laplacian of a connected graph is an M matrix. Kirkland
and Neumann [7] characterized all weighted trees whose Laplacian have this
property. The result in this paper says that distance Laplacians of trees are
irreducible M matrices and their Moore-Penrose inverses are also M matrices.
(We note that group inverse and Moore-Penrose inverse coincide for Laplacians
and distance Laplacians.)

Our proof techniques in this paper works only for trees. To extend the result
in a more general setting, for example, resistance Laplacian matrices of
connected graphs, additional new techniques are certainly required.

##  2 Preliminaries

###  2.1 Notation

  1. (i)

If $A=[a_{ij}]$ is an $n\times n$ matrix with $(i,j)^{\rm th}$ entry equal to
$a_{ij}$, then the matrix $A(i|j)$ will denote the submatrix of $A$ obtained
by deleting the $i^{\rm th}$ row and the $j^{\rm th}$ column of $A$.

  2. (ii)

Let $\Omega_{1}:=\\{s_{1},\dotsc,s_{k}\\}$ and
$\Omega_{2}:=\\{t_{1},\dotsc,t_{m}\\}$ be subsets of $\\{1,\dotsc,n\\}$. Then
$A[\Omega_{1},\Omega_{2}]$ will be the $k\times m$ matrix with $(i,j)^{\rm
th}$ entry equal to $a_{s_{i}t_{j}}$. So, $A=[a_{s_{i}t_{j}}]$.

  3. (iii)

The vector of all ones in $\mathbb{R}^{n}$ will be denoted by $\mathbf{1}$. If
$m<n$, then $\mathbf{1}_{m}$ will denote the vector of all ones in
$\mathbb{R}^{m}$. The notation $J$ will stand for the symmetric matrix with
all entries equal to $1$.

  4. (iv)

The Moore-Penrose inverse of a matrix $B$ is denoted by $B^{\dagger}$ and its
transpose by $B^{\prime}$.

  5. (v)

To denote the subgraph induced by a set of vertices $W$, we use the notation
$[W]$. If $a$ and $b$ are any two vertices, then ${\mathbf{P}}_{ab}$ will be
the path connecting $a$ and $b$. The set of all vertices of a subgraph $H$ is
denoted by $V(H)$.

###  2.2 Basic results and techniques

We shall use the following results. Let $T$ be a tree on $n$ vertices labelled
$\\{1,\dotsc,n\\}$ where $n\geq 3$. Let $D=[d_{ij}]$ be the distance matrix of
$T$.

  1. (P1)

(Theorem 3.4, [5]) If $L$ is the Laplacian matrix of a weighted tree and
$L^{\dagger}=[\alpha_{ij}]$, then

$d_{ij}=\alpha_{ii}+\alpha_{jj}-2\alpha_{ij}.$

Because $\mathop{\rm rank}(L)=n-1$ and $L$ is positive semidefinite, it
follows that for any $0\neq x=(x_{1},\dotsc,x_{n})^{\prime}\in\mathbb{R}^{n}$
such that $\sum\limits_{i=1}^{n}x_{i}=0$,

$\sum_{i,j}x_{i}x_{j}d_{ij}=-2\sum_{i,j}x_{i}x_{j}\alpha_{ij}<0.$

  2. (P2)

Triangle inequality: If $i,j,k\in\\{1,\dotsc,n\\}$, then

$d_{ik}\leq d_{ij}+d_{jk}.$

  3. (P3)

Let $\nu$ be a positive integer and the sets $L_{1},\dotsc,L_{N}$ partition
$\\{1,\dotsc,\nu\\}$. Let $A=[a_{uv}]$ be a $\nu\times\nu$ matrix such that
$A[L_{i},L_{j}]=O$ for all $i<j$. Then there exists a permutation matrix $P$
such that

$P^{\prime}AP=\left[\begin{array}[]{ccccc}A[L_{1},L_{1}]&O&\ldots&O\\\
A[L_{2},L_{1}]&A[L_{2},L_{2}]&\ldots&O\\\ \ldots&\ldots&\ddots&\vdots\\\
A[L_{N},L_{1}]&A[L_{N},L_{2}]&\ldots&A[L_{N},L_{N}]\\\ \end{array}\right].$

As a consequence,

    1. (a)

If $a_{xy}=0$ for all $x\in L_{i}$, $y\in L_{j}$ and $i<j$, then $A$ is
similar to a block lower triangular matrix with $i^{\rm th}$ diagonal block
equal to $A[L_{i},L_{i}]$.

    2. (b)

If $a_{xy}=0$ for all $x\in L_{i}$, $y\in L_{j}$ and $i>j$, then $A$ is
similar to a block upper triangular matrix with $i^{\rm th}$ diagonal block
equal to $A[L_{i},L_{i}]$.

    3. (c)

If $a_{xy}=0$ for all $x\in L_{i}$, $y\in L_{j}$ and $i\neq j$, then $A$ is
similar to a block diagonal matrix with $i^{\rm th}$ diagonal block equal to
$A[L_{i},L_{i}]$.

  4. (P4)

(Matrix determinant lemma) Let $A$ be a $m\times m$ matrix and $x,y$ be
$m\times 1$ vectors. Then

${\rm det}(A+xy^{\prime})={\rm det}(A)+y^{\prime}\mathop{\rm adj}(A)x.$

##  3 Main result

Consider a tree $T$ with vertices labelled $\\{1,\dotsc,n\\}$. If $n=2$, then
the result is easy to verify. We assume $n>2$. Let $D:=[d_{ij}]$ denote the
distance matrix of $T$ and $\eta_{i}$ be the $i^{\rm th}$ row sum of $D$.
Define $\Delta:=\mathop{\rm Diag}(\eta_{1},\dotsc,\eta_{n})$. Let

$S:=\Delta-D.$

Each row sum of $S$ is zero. So, all the cofactors of $S$ are equal. Let this
common cofactor be $\gamma$. Henceforth, we fix the notation $T,D,\Delta$ and
$S$. Our aim is to show that all the off-diagonal entries of
$S^{\dagger}=[s^{{\dagger}}_{ij}]$ are non-positive. We shall show that
$s^{\dagger}_{12}\leq 0$. A similar argument can be repeated to any other off-
diagonal entry of $S^{\dagger}$. In the first step, we show that
$s^{{\dagger}}_{12}\leq 0$ if and only if the determinant of a certain matrix
constructed from $D$ is non-negative.

###  3.1 Reformulation of the problem

We shall find a matrix $R$ such that that $s^{{\dagger}}_{12}\leq 0$ if and
only if ${\rm det}(R)\geq 0$. The following lemma will be useful.

######  Lemma 1.

Let $S_{*}:=S+J$. The following items hold.

  1. (i)

$S$ is positive semidefinite and $\mathop{\rm rank}(S)=n-1.$

  2. (ii)

$S_{*}^{-1}=S^{\dagger}+\frac{J}{n^{2}}$.

  3. (iii)

${\rm det}(S_{*})=n^{2}\gamma$.

  4. (iv)

Let $C=S(1|2)$. Then,

$s^{{\dagger}}_{12}=\frac{\mathbf{1}_{n-1}^{\prime}C^{-1}\mathbf{1}_{n-1}}{n^{2}}.$

###### Proof.

It follows from the definition of $S$ that, $S\mathbf{1}=\mathbf{0}$. Let
$0\neq x\in\mathbf{1}^{\perp}$. By (P1), $x^{\prime}Dx>0$. So,

$x^{\prime}Sx=x^{\prime}\Delta x-x^{\prime}Dx>0.$

If $x\in\mathop{\rm span}\\{\mathbf{1}\\}$, then $Sx=\mathbf{0}$. Hence $S$ is
positive semidefinite and $S$ has $n-1$ positive eigenvalues. So, $\mathop{\rm
rank}(S)=n-1$. This proves (i).

Since $S\mathbf{1}=\mathbf{0}$ and $\mathop{\rm rank}(S)=n-1$,

$SS^{\dagger}=I-\frac{J}{n}.$

From a direct verification,

$S_{*}^{-1}=S^{\dagger}+\frac{J}{n^{2}}.$

This proves (ii).

Writing $S_{*}=S+\mathbf{1}\mathbf{1}^{\prime}$, by (P4),

${\rm det}(S_{*})={\rm det}(S)+\mathbf{1}^{\prime}\mathop{\rm
adj}(S)\mathbf{1}.$

As $S\mathbf{1}=0$, ${\rm det}(S)=0$. Since all the cofactors of $S$ are equal
to $\gamma$,

$\mathop{\rm adj}(S)=\gamma J.$

Therefore, ${\rm det}(S_{*})=n^{2}\gamma$. Item (iii) is proved.

Each cofactor of $S$ is $\gamma$ and $C=S(1|2)$. So,

${\rm det}(C)={\rm det}(S(1|2))=-\gamma.$

In view of item (ii),

$\displaystyle s^{{\dagger}}_{12}$
$\displaystyle=(S_{*}^{-1})_{12}-\frac{1}{n^{2}}$ $\displaystyle=\frac{1}{{\rm
det}(S_{*})}(\mathop{\rm adj}S_{*})_{12}-\frac{1}{n^{2}}$
$\displaystyle=\frac{-1}{n^{2}\gamma}({\rm det}(S_{*}(1|2))-\frac{1}{n^{2}}$
$\displaystyle=-\frac{1}{n^{2}\gamma}({\rm
det}(S(1|2)+J(1|2))-\frac{1}{n^{2}}.$

By the matrix determinant lemma (P4),

$\displaystyle s^{{\dagger}}_{12}$ $\displaystyle=\frac{-1}{n^{2}\gamma}({\rm
det}(C)+{\rm
det}(C)\mathbf{1}_{n-1}^{\prime}C^{-1}\mathbf{1}_{n-1})-\frac{1}{n^{2}}$
$\displaystyle=\frac{-1}{n^{2}\gamma}(-\gamma-\gamma\mathbf{1}_{n-1}^{\prime}C^{-1}\mathbf{1}_{n-1})-\frac{1}{n^{2}}$
$\displaystyle=\frac{\mathbf{1}_{n-1}^{\prime}C^{-1}\mathbf{1}_{n-1}}{n^{2}}.$

Item (iv) is proved and the proof is complete. ∎

By numerical computations, we note that the sign of $s_{12}^{\dagger}$ depends
on the sign of the determinant of a certain matrix defined from $D$. We
introduce this matrix now.

######  Definition 1.

For any $i,j\in\\{3,\dotsc,n\\}$, define

$R_{ij}:=\begin{cases}-d_{21}+d_{i1}+d_{2j}-d_{ij}&i\neq j\\\
-d_{21}+d_{i1}+d_{2i}+\sum\limits_{k=1}^{n}d_{ik}&i=j.\end{cases}$

Set $R:=[R_{ij}]$.

The order of $R$ is $n-2$. By triangle inequality,

$-d_{21}+d_{i1}+d_{2i}\geq 0~{}~{}~{}~{}i=3,\dotsc,n.$

Hence,

$R_{ii}>0~{}~{}~{}i=3,\dotsc,n.$

######  Lemma 2.

$s^{{\dagger}}_{12}\leq 0$ if and only if ${\rm det}(R)\geq 0$.

###### Proof.

Let $C=S(1|2)$ and $Q$ be the $(n-1)\times(n-1)$ matrix
$\left[\begin{array}[]{rrrrrrrrrrrrr}1&\mathbf{1}_{n-2}\\\
\mathbf{0}&I_{n-2}\end{array}\right]$. Then,
$Q^{-1}=\left[\begin{array}[]{rrrrrrrrrrrrr}1&-\mathbf{1}_{n-2}\\\
\mathbf{0}&I_{n-2}\end{array}\right]$. By a direct computation,

$Q^{\prime-1}CQ^{-1}=\left[\begin{array}[]{rrrrrrr}s_{21}&-s_{21}+s_{23}&\dotsc&~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}-s_{21}+s_{2n}\\\
-s_{21}+s_{31}&s_{21}-s_{31}-s_{23}+s_{33}&\dotsc&s_{21}-s_{31}-s_{2n}+s_{3n}\\\
\ldots{}{}{}{}{}&\ldots{}{}{}&\ddots&\ldots{}{}{}{}{}\\\
-s_{21}+s_{n1}&s_{21}-s_{n1}-s_{23}+s_{n3}&\dotsc&s_{21}-s_{n1}-s_{2n}+s_{nn}\end{array}\right].$

The entries of $S$ are

$s_{ij}=\begin{cases}-d_{ij}&{i\neq j}\\\
\sum\limits_{k=1}^{n}d_{ik}&{i=j}.\end{cases}$

Hence,

$Q^{\prime-1}CQ^{-1}(1|1)=R.$ (1)

We note that

${\rm det}(C)=-\gamma<0~{}~{}\mbox{and}~{}~{}{\rm det}(Q)=1.$

So,

${\rm det}(Q^{\prime-1}CQ^{-1})=-\gamma<0.$

By a simple computation,

$(QC^{-1}Q^{\prime})_{11}=\mathbf{1}_{n-1}^{\prime}C^{-1}\mathbf{1}_{n-1}.$
(2)

Using (1),

$\displaystyle(QC^{-1}Q^{\prime})_{11}$ $\displaystyle=\frac{1}{{\rm
det}(Q^{\prime-1}CQ^{-1})}{\rm det}(Q^{\prime-1}CQ^{-1}(1|1))$ (3)
$\displaystyle=-\frac{1}{\gamma}{\rm det}(R).$

By (2) and (3),

$\mathbf{1}_{n-1}^{\prime}C^{-1}\mathbf{1}_{n-1}=-\frac{1}{\gamma}{\rm
det}(R).$

By item (iv) in Lemma 1, it now follows that $s^{{\dagger}}_{12}\leq 0$ if and
only if ${\rm det}(R)\geq 0$. ∎

###  3.2 A property of $R$

We now proceed to show that ${\rm det}(R)\geq 0$. The following lemma will be
useful in the sequel.

######  Lemma 3.

Let $\alpha\in V({\mathbf{P}}_{12})$. Suppose there exists a connected
component $\widetilde{X}$ of $T\smallsetminus(\alpha)$ not containing $1$ and
$2$. Let $u\in V(\widetilde{X})$ be the vertex adjacent to $\alpha$. Consider
a connected subgraph $X$ of $\widetilde{X}$ containing $u$. Put $E:=V(X)$.
Then, $R[E,E]$ is a positive semidefinite matrix.

###### Proof.

If $E=\\{u\\}$, then $R[E,E]=[R_{uu}]$. As $R_{uu}>0$, the lemma is true in
this case. Let $|E|\geq 2$.

Claim 1: $R[E,E]$ is symmetric.
Let $r,s\in E$. Recall that

$R_{rs}=-d_{21}+d_{r1}+d_{2s}-d_{rs}.$ (4)

By our assumption,

$d_{r1}=d_{r\alpha}+d_{\alpha 1}~{}~{}\mbox{and
}~{}d_{s2}=d_{s\alpha}+d_{\alpha 2}.$ (5)

By (4) and (5),

$R_{rs}=-d_{21}+d_{r\alpha}+d_{\alpha 1}+d_{s\alpha}+d_{\alpha 2}-d_{rs}.$ (6)

Again by our assumption,

$d_{r2}=d_{r\alpha}+d_{\alpha 2}~{}~{}\mbox{and
}~{}d_{s1}=d_{s\alpha}+d_{\alpha 1}.$ (7)

By (6) and (7),

$R_{rs}=-d_{21}+d_{s1}+d_{r2}-d_{rs}.$

The right hand side of the above equation is $R_{sr}$. The claim is proved.

We know that $u\in E$ and is adjacent to $\alpha$. Let $\Omega$ be the set of
all non-pendant vertices in $T$. Since $X$ is connected, and has at least two
vertices, $u$ is adjacent to a vertex in $E$. Hence, $u\in E\cap\Omega$. So,
$E\cap\Omega$ is a non-empty set.

Let $\delta\in E$ be such that

$d_{\delta\alpha}=\max\\{d_{x\alpha}:x\in E\cap\Omega\\}.$

Since $X$ is a tree, there exists a pendant vertex adjacent to $\delta$.
Without loss of generality, let $E=\\{x_{1},\dotsc,x_{t-1},x_{t}\\}$ where
$x_{1}=u$, $x_{t-1}=\delta$ and $x_{t}$ is pendant vertex adjacent to
$x_{t-1}$.
Claim 2:

$R_{ix_{t-1}}=R_{ix_{t}}~{}~{}\mbox{for
all}~{}i\in\\{x_{1},x_{2},\dotsc,x_{t-2}\\}.$ (8)

By the definition of $R$,

$\displaystyle R_{ix_{t-1}}-R_{ix_{t}}$
$\displaystyle=-d_{21}+d_{i1}+d_{2x_{t-1}}-d_{ix_{t-1}}-(-d_{21}+d_{i1}+d_{2x_{t}}-d_{ix_{t}})$
(9) $\displaystyle=(d_{2x_{t-1}}-d_{2x_{t}})-(d_{ix_{t-1}}-d_{ix_{t}}).$

Since $x_{t}$ is a pendant vertex and is adjacent to $x_{t-1}$, we have

$d_{2x_{t-1}}-d_{2x_{t}}=-d_{x_{t}x_{t-1}},$

and since $i\in\\{x_{1},\dotsc,x_{t-2}\\}$, we have

$d_{ix_{t-1}}-d_{ix_{t}}=-d_{x_{t}x_{t-1}}.$

By (9), we now get

$R_{ix_{t-1}}=R_{ix_{t}}.$

The claim is true.

Claim 3: $R_{x_{t-1}x_{t}}=2d_{{\delta\alpha}}=2d_{x_{t-1}\alpha}$.
By definition,

$\displaystyle R_{x_{t-1}x_{t}}$
$\displaystyle=-d_{21}+d_{x_{t-1}1}+d_{2x_{t}}-d_{x_{t-1}x_{t}}.$ (10)

Vertices $2$ and $x_{t}$ belong to different components of
$T\smallsetminus(\alpha)$. Also, $x_{t}$ and $x_{t-1}$ are adjacent and
$x_{t}$ is pendant in $X$. Hence,

$d_{2x_{t}}=d_{2\alpha}+d_{\alpha x_{t}}=d_{2\alpha}+d_{\alpha
x_{t-1}}+d_{x_{t-1}x_{t}}.$ (11)

By (10) and (11),

$R_{x_{t-1}x_{t}}=-d_{21}+d_{x_{t-1}1}+d_{2\alpha}+d_{\alpha x_{t-1}}.$

As $\alpha\in V({\mathbf{P}}_{12})$, $d_{21}=d_{2\alpha}+d_{\alpha 1}$. Hence

$R_{x_{t-1}x_{t}}=-d_{\alpha 1}+d_{x_{t-1}1}+d_{\alpha x_{t-1}}.$ (12)

As $1\not\in V(\tilde{X})$, $d_{x_{t-1}1}=d_{x_{t-1}\alpha}+d_{\alpha 1}$.
Hence by (12),

$R_{x_{t-1}x_{t}}=2d_{\alpha x_{t-1}}.$ (13)

This proves the claim.

Claim 4 : Diagonal entries of $R[E,E]$ are greater than or equal to
$2d_{\delta\alpha}$.
Let $r\in E$. By definition,

$R_{rr}=-d_{21}+d_{r1}+d_{2r}+\sum\limits_{k=1}^{n}d_{rk}.$ (14)

Since $r\in E$, $1\not\in E$ and $2\not\in E$,

$d_{r1}=d_{r\alpha}+d_{1\alpha}\mbox{ and }d_{r2}=d_{r\alpha}+d_{2\alpha}.$
(15)

By (14) and (15),

$\displaystyle
R_{rr}=-d_{21}+d_{r\alpha}+d_{1\alpha}+d_{r\alpha}+d_{2\alpha}+\sum_{k=1}^{n}d_{rk}.$
(16)

As $d_{21}=d_{2\alpha}+d_{\alpha 1}$, (16) simplifies to

$R_{rr}=2d_{r\alpha}+\sum_{k=1}^{n}d_{rk}.$ (17)

Case 1: Suppose $r\notin\\{\delta,x_{t}\\}$.
Then

$R_{rr}=2d_{r\alpha}+\sum\limits_{k=1}^{n}d_{rk}\geq
2d_{r\alpha}+d_{r\delta}+d_{rx_{t}}.$ (18)

By triangle inequality,

$d_{r\alpha}+d_{r\delta}\geq
d_{\delta\alpha}~{}~{}\mbox{and}~{}~{}d_{r\alpha}+d_{rx_{t}}\geq
d_{x_{t}\alpha}.$

In view of (18),

$R_{rr}\geq d_{x_{t}\alpha}+d_{\delta\alpha}.$

As $x_{t}$ is adjacent only to $\delta$,

$R_{rr}\geq
d_{x_{t}\alpha}+d_{\delta\alpha}=d_{{\delta}\alpha}+d_{{\delta}x_{t}}+d_{\delta\alpha}\geq
2d_{\delta\alpha}.$

Case 2: If $r=\delta$, then it is immediate from (17).
Case 3: Suppose $r=x_{t}$.

By (17),

$R_{x_{t}x_{t}}\geq 2d_{x_{t}\alpha}.$

Since $x_{t}$ is pendant and adjacent to $\delta$,

$d_{x_{t}\alpha}=d_{\delta\alpha}+d_{x_{t}\delta}=d_{\delta\alpha}+d_{{\delta}x_{t}}\geq
d_{\delta\alpha}.$

By the two previous inequalities,

$R_{x_{t}x_{t}}\geq 2d_{\delta\alpha}.$

The claim is proved.

Define a $t\times t$ matrix

$P:=\left[\begin{array}[]{ccccccccccccc}2d_{\delta\alpha}&R_{x_{1}x_{2}}&\ldots&R_{x_{1}x_{t}}\\\
R_{x_{2}x_{1}}&2d_{\delta\alpha}&\ldots&R_{x_{2}x_{t}}\\\
\ldots&\ldots&\ddots&\ldots\\\
R_{x_{t}x_{1}}&R_{x_{t}x_{2}}&\ldots&2d_{\delta\alpha}\end{array}\right].$

Because $R[E,E]$ is a symmetric matrix, $P$ is symmetric.

Claim 5: $P$ is positive semidefinite.
We will prove this by using induction on $|E|$. Suppose $|E|$ has only two
vertices. Write $E=\\{x_{1},x_{2}\\}$, where $u=x_{1}$. By a simple
verification,

$P=\left[\begin{array}[]{rrrrrrrrrrrrr}2d_{\alpha u}&2d_{\alpha u}\\\
2d_{\alpha u}&2d_{\alpha u}\end{array}\right].$

So, the claim is true in this case. Suppose the result is true if $|E|<t$.
Define a $t\times t$ matrix by

$Q_{1}:=\left[\begin{array}[]{rrrrrrrrrrrrr}I_{t-2}&\mathbf{0}&\mathbf{0}\\\
\mathbf{0}^{\prime}&1&-1\\\ \mathbf{0}^{\prime}&0&1\end{array}\right].$

We show that $Q_{1}^{\prime}PQ_{1}$ is positive semidefinite. Claim 2 and
Claim 3 imply that the last two columns of $P$ are equal. Hence, by direct
computation,

$Q_{1}^{\prime}PQ_{1}=\left[\begin{array}[]{rrrrrrrrrrrrr}P(x_{t}|x_{t})&\mathbf{0}\\\
\mathbf{0}^{\prime}&0\end{array}\right].$ (19)

Define

$X^{\prime}:=X\smallsetminus(x_{t}).$

Because $x_{t}$ is pendant, $X^{\prime}$ is a connected subgraph of $X$ and
$u\in V(X^{\prime})$. Set

$E^{\prime}:=V(X^{\prime})=\\{x_{1},\dotsc,x_{t-1}\\},~{}\mbox{where}~{}~{}x_{1}=u.$

Define

$d_{\mu 1}:=\max\\{d_{x\alpha}:x\in\Omega\cap E^{\prime}\\}.$

By induction hypothesis,

$P_{1}:=\left[\begin{array}[]{ccccc}2d_{\mu\alpha}&R_{x_{1}x_{2}}&\ldots&R_{x_{1}x_{t-1}}\\\
R_{x_{2}x_{1}}&2d_{\mu\alpha}&\ldots&R_{x_{2}x_{t-1}}\\\
\ldots&\ldots&\ddots&\ldots\\\
R_{x_{t-1}x_{1}}&R_{x_{t-1}x_{2}}&\ldots&2d_{\mu\alpha}\end{array}\right]$

is positive semidefinite. Put

$P_{2}:=\left[\begin{array}[]{ccccc}2d_{\delta\alpha}-2d_{\mu\alpha}&0&\ldots&0\\\
0&2d_{\delta\alpha}-2d_{\mu\alpha}&\ldots&0\\\ \ldots&\ldots&\ddots&\ldots\\\
0&0&\ldots&2d_{\delta\alpha}-2d_{\mu\alpha}\end{array}\right].$

Then,

$P(x_{t}|x_{t})=P_{1}+P_{2}.$

Since $d_{\delta\alpha}-d_{\mu\alpha}\geq 0$, $P(x_{t}|x_{t})$ is positive
semidefinite and so is $P$. This proves the claim.
Define

$\Lambda:=\mathop{\rm
Diag}(R_{x_{1}x_{1}}-2d_{\delta\alpha},\dotsc,R_{x_{t}x_{t}}-2d_{\delta\alpha}).$

Then,

$R[E,E]=P+\Lambda.$

By Claim 4, $\Lambda$ is positive semidefinite and by the previous claim, $P$
is positive semidefinite. So, $R[E,E]$ is positive semidefinite. The proof is
complete. ∎

###  3.3 Partitioning $\\{3,\dotsc,n\\}$

Let the degree of vertex $1$ be $m$. We denote the vertex sets of $m$
components of $T\smallsetminus(1)$ by

$V_{1}^{\prime},V_{2},\dotsc,V_{m}.$

Assume $2\in V_{1}^{\prime}$. Define

$V_{1}:=V_{1}^{\prime}\smallsetminus\\{2\\}.$

Illustration
Consider Figure $1$: $T_{16}\smallsetminus(1)$ has three components.

$1$$2$$3$$4$$5$$6$$7$$8$$9$${10}$${11}$${12}$${13}$${14}$${15}$${16}$ Figure
1: Tree $T_{16}$ on 16 vertices

Vertex set of these components are

$V_{1}^{\prime}=\\{3,13,11,12,4,14,2,5,6,15,16\\},~{}V_{2}=\\{10\\},~{}V_{3}=\\{7,9,8\\}.$

Now,

$V_{1}=V_{1}^{\prime}\smallsetminus\\{2\\}=\\{3,13,11,12,4,14,5,6,15,16\\}.$

###  3.4 A canonical form of $R$

We now show that $R$ is similar to a block lower triangular matrix.

######  Lemma 4.

$R$ is similar to a block lower triangular matrix with diagonal blocks equal
to $R[V_{1},V_{1}],R[V_{2},V_{2}],\dotsc,R[V_{m},V_{m}]$.

###### Proof.

We know that

$V_{1}\cup\cdots\cup V_{m}=\\{3,\dotsc,n\\}~{}~{}\mbox{and}~{}~{}V_{i}\cap
V_{j}=\emptyset.$

Since

$R=[R_{\alpha\beta}]~{}~{}~{}3\leq\alpha,\beta\leq n,$

by item (a) in (P3), it suffices to show that if $i<j$, $x\in V_{i}$ and $y\in
V_{j}$, then

$R_{xy}=0.$

By definition,

$R_{xy}=-d_{21}+d_{x1}+d_{2y}-d_{xy}.$ (20)

Since $x$ and $y$ belong to different components of $T\smallsetminus(1)$,

$d_{xy}=d_{x1}+d_{y1}.$ (21)

Using $(\ref{dxy1})$ in (20),

$\displaystyle R_{xy}$ $\displaystyle=-d_{21}+d_{x1}+d_{2y}-d_{x1}-d_{y1}$
(22) $\displaystyle=-d_{21}+d_{2y}-d_{y1}.$

We recall that $2\in V_{1}^{\prime}$ and $y\in V_{j}$. Since $i<j$, we see
that $1<j$. Hence, $2$ and $y$ belong to different components of
$T\smallsetminus(1).$ Thus, $d_{2y}=d_{21}+d_{y1}$. By (22), $R_{xy}=0$. The
proof is complete. ∎

The following is immediate.

######  Corollary 1.

${\rm det}(R)=\prod_{i=1}^{m}{\rm det}(R[V_{i},V_{i}]).$

######  Lemma 5.

${\rm det}(R[V_{j},V_{j}])\geq 0~{}~{}~{}~{}~{}~{}j=2,\dotsc,m.$

###### Proof.

Let $j\in\\{2,\dotsc,m\\}$. Put $\widetilde{X}=X=[V_{j}]$, $E=V_{j}$ and
$\alpha=1$ in Lemma 3. The result now follows. ∎

###  3.5 A canonical form of $R[V_{1},V_{1}]$

We partition $V_{1}$. Define

$V_{A}:=\\{y\in V_{1}:2\notin V({\mathbf{P}}_{1y})\\}.$ $V_{B}:=\\{y\in
V_{1}:2\in V({\mathbf{P}}_{1y})\\}.$

Then,

$V_{1}=V_{A}\cup V_{B}~{}~{}\mbox{and}~{}~{}V_{A}\cap V_{B}=\emptyset.$

For example, in Figure 1,

$V_{A}=\\{3,4,14,11,13,12\\}\mbox{ and }V_{B}=\\{5,6,15,16\\}.$

######  Lemma 6.

Let $x\in V_{B}$ and $y\in V_{A}$. Then $2\in V({\mathbf{P}}_{xy})$.

###### Proof.

Suppose

$2\notin V({\mathbf{P}}_{xy}).$ (23)

Since $y\in V_{A}$,

$2\notin V({\mathbf{P}}_{1y}).$ (24)

Equations (23) and (24) imply $2\notin V({\mathbf{P}}_{1x})$. This contradicts
$x\in V_{B}$. The proof is complete. ∎

######  Lemma 7.

$R[V_{1},V_{1}]$ similar to a block upper triangular matrix with diagonal
blocks equal to $R[V_{A},V_{A}]$ and $R[V_{B},V_{B}]$.

###### Proof.

Let $x\in V_{B}$ and $y\in V_{A}$. In view of item (b) in (P3), it suffices to
show that $R_{xy}=0$.

By the previous Lemma

$d_{2y}+d_{2x}=d_{xy}.$ (25)

By Definition 1,

$R_{xy}=-d_{21}+d_{x1}+d_{2y}-d_{xy}.$ (26)

As $x\in V_{B}$,

$d_{1x}-d_{21}=d_{2x}.$ (27)

By (26) and (27),

$R_{xy}=d_{2x}+d_{2y}-d_{xy}.$

Equation (25) now gives

$R_{xy}=0.$

The proof is complete. ∎

The following is now immediate.

######  Corollary 2.

${\rm det}(R[V_{1},V_{1}])={\rm det}(R[V_{A},V_{A}]){\rm
det}(R[V_{B},V_{B}]).$

###  3.6 Partitioning $V_{A}$

We partition $V_{A}$. Let ${\mathbf{P}}_{12}$ be the path with vertices
$\\{1,u_{1},\dotsc,u_{q},2\\}$ and edges

$(1,u_{1}),(u_{1},u_{2}),\dotsc,(u_{q},2).$

Define

$U_{i}:=\\{y\in V_{A}:d_{u_{i}y}\leq d_{u_{j}y}~{}~{}~{}\mbox{for
all}~{}~{}i\neq j\\}~{}~{}~{}i=1,\dotsc,q.$

(We can think of $U_{i}$ as the collection of vertices in $V_{A}$ which are
nearer to $u_{i}$ than $u_{j}$.) Clearly $u_{i}\in U_{i}$. To illustrate,
consider Figure 1. Here,

$u_{1}=3,~{}U_{1}=\\{3,11,12,13\\},~{}u_{2}=4,~{}U_{2}=\\{4,14\\}.$

######  Lemma 8.

The following items hold.

  1. (i)

If $y\in U_{i}$, then $u_{i}\in V({\mathbf{P}}_{y2})\cap
V({\mathbf{P}}_{y1})$.

  2. (ii)

If $y\in U_{i}$, then $u_{i}\in V({\mathbf{P}}_{yu_{j}})$ for $j\neq i$.

  3. (iii)

$U_{1},\dotsc,U_{q}$ partition $V_{A}$.

  4. (iv)

Let $y\in U_{i}$ and $z\in U_{j}$. If $i\neq j$, then

${\mathbf{P}}_{yz}={\mathbf{P}}_{yu_{i}}\cup{\mathbf{P}}_{u_{i}u_{j}}\cup{\mathbf{P}}_{u_{j}z}.$

  5. (v)

Each $[U_{i}]$ is a tree.

###### Proof.

We prove (i) now. Assume that $u_{i}\notin V({\mathbf{P}}_{1y})$. Because
$u_{1}$ is the only vertex in $V_{1}$ adjacent to $1$, $i\neq 1$. So,
$u_{i}\notin V({\mathbf{P}}_{u_{1}y})$. Then,
${\mathbf{P}}_{u_{1}y}\cup{\mathbf{P}}_{u_{1}u_{i}}$ contains
${\mathbf{P}}_{yu_{i}}$. Now, $u_{i-1}\in V({\mathbf{P}}_{yu_{i}})$. This
implies

$d_{u_{i-1}y}<d_{u_{i}y}.$

But this cannot happen as $y\in U_{i}$. So,

$u_{i}\in V({\mathbf{P}}_{1y}).$

Using a similar argument,

$u_{i}\in V({\mathbf{P}}_{2y}).$

This proves (i).

Let $j>i$. By (i) and from the definition of $u_{i}$ and $u_{j}$,

$u_{i}\in V({\mathbf{P}}_{2y})~{}~{}\mbox{and}~{}~{}u_{j}\in
V({\mathbf{P}}_{2u_{i}}).$

Thus,

${\mathbf{P}}_{2y}={\mathbf{P}}_{2u_{j}}\cup{\mathbf{P}}_{u_{j}u_{i}}\cup{\mathbf{P}}_{u_{i}y}.$

The above equation implies

$u_{i}\in V({\mathbf{P}}_{yu_{j}})~{}~{}\mbox{for all}~{}j>i.$

A similar argument leads to

$u_{i}\in V({\mathbf{P}}_{yu_{j}})~{}~{}\mbox{for all}~{}j<i.$

The proof of (ii) is complete.

Let $y\in U_{i}\cap U_{j}$, where $j\neq i$. By (ii), it now follows that

$u_{i}\in V({\mathbf{P}}_{u_{j}y})~{}~{}\mbox{and}~{}~{}u_{j}\in
V({\mathbf{P}}_{u_{i}y}).$

As these two cannot happen simultaneously, $y\notin U_{i}\cap U_{j}$. Thus,

$U_{i}\cap U_{j}=\emptyset.$

By definition of $U_{1},\dotsc,U_{q}$,

$U_{1}\cup\cdots\cup U_{q}\subseteq V_{A}.$

Let $x\in V_{A}$ and $k\in\\{1,\dotsc,q\\}$ be such that

$d_{xu_{k}}:=\min(d_{xu_{1}},\dots,d_{xu_{q}}).$

Then, $x\in U_{k}$. Hence

$V_{A}\subseteq U_{1}\cup\cdots\cup U_{q}.$

So,

$V_{A}=U_{1}\cup\cdots\cup U_{q}.$

The proof of (iii) is complete.

The proof of (iv) follows from (ii).

We now show that $[U_{i}]$ is a tree. Let $y\in U_{i}$. Since $y,u_{i}\in
V_{1}^{\prime}$ and $[V_{1}^{\prime}]$ is a tree, we have

$V({\mathbf{P}}_{yu_{i}})\subseteq V_{1}^{\prime}.$ (28)

To show that $[U_{i}]$ is a tree, it now suffices to show that
$V({\mathbf{P}}_{yu_{i}})\subseteq U_{i}$. Let $x\in
V({\mathbf{P}}_{yu_{i}})$. Assuming $x\notin U_{i}$, we shall get a
contradiction. By (28), we now have only three cases:

$\mbox{(a)}~{}x\in U_{j}~{}\mbox{for some}~{}j\neq
i~{}~{}\mbox{(b)}~{}x=2~{}~{}\mbox{(c)}~{}x\in V_{B}.$

Assume (a). In view of item (iv) above, we get $u_{i}\in
V({\mathbf{P}}_{xy})$. But then $x\notin V({\mathbf{P}}_{yu_{i}})$. This is a
contradiction. So, (a) is not true.

If (b) is true, then $2\in V({\mathbf{P}}_{yu_{i}})$. However (i) implies
$u_{i}\in V({\mathbf{P}}_{y2})$. This is a contradiction.

If we assume (c), then $x\in V({\mathbf{P}}_{yu_{i}})$. By Lemma 6, $2\in
V({\mathbf{P}}_{yx})$ and therefore $2\in V({\mathbf{P}}_{yu_{i}})$ implying
case (b) is true which is a contradiction.

Hence, $V({\mathbf{P}}_{yu_{i}})\subseteq U_{i}$. So, $[U_{i}]$ is a tree.
This completes the proof. ∎

###  3.7 A canonical form of $R[V_{A},V_{A}]$

We now show that $R[V_{A},V_{A}]$ is similar to a block upper triangular
matrix.

######  Lemma 9.

$R[V_{A},V_{A}]$ is similar to a block upper triangular matrix with $i^{\rm
th}$ diagonal block equal to $R[U_{i},U_{i}]$.

###### Proof.

Let $i>j$. Pick any two elements $r\in U_{i}$ and $s\in U_{j}$. By item (c) in
(P3), it suffices to show that

$R_{rs}=0.$

We recall that

$R_{rs}=-d_{21}+d_{r1}+d_{2s}-d_{rs}.$ (29)

By item (i) and (iv) of Lemma 8,

$d_{r1}=d_{ru_{i}}+d_{u_{i}1},~{}~{}d_{2s}=d_{2u_{j}}+d_{u_{j}s}~{}~{}\mbox{and}~{}~{}d_{rs}=d_{ru_{i}}+d_{u_{j}u_{i}}+d_{su_{j}}.$
(30)

Thus (29) and (30) give

$\displaystyle R_{rs}$
$\displaystyle=-d_{21}+d_{ru_{i}}+d_{u_{i}1}+d_{2u_{j}}+d_{u_{j}s}-(d_{ru_{i}}+d_{u_{j}u_{i}}+d_{su_{j}})$
$\displaystyle=-d_{21}+d_{u_{i}1}+d_{2u_{j}}-d_{u_{j}u_{i}}.$

Since $i>j$ and ${\mathbf{P}}_{12}$ has edges $(u_{k},u_{k+1})$,

$-d_{21}+d_{u_{i}1}=-d_{u_{i}2}~{}~{}\mbox{and}~{}~{}d_{2u_{j}}-d_{u_{j}u_{i}}=d_{2u_{i}}.$

Thus, $R_{rs}=0$. This completes the proof. ∎

The following is immediate now.

######  Corollary 3.

${\rm det}(R[V_{A},V_{A}])=\prod_{i=1}^{q}{\rm det}(R[{U_{i}},{U_{i}}]).$

###  3.8 Computation of ${\rm det}(R[U_{i},U_{i}])$

Fix $i\in\\{1,\dotsc,q\\}$. We further partition $U_{i}$ into disjoint sets.
Let $u_{i}$ have $p_{i}$ adjacent vertices in $[U_{i}]$. Then,
$[U_{i}]\smallsetminus(u_{i})$ have $p_{i}$ components:

$G_{i1},\dotsc,G_{ip_{i}}.$

Define $Q_{ik}:=V(G_{ik})$. For example in Figure 1, for $i=1$, we have

$u_{1}=3,~{}U_{1}=\\{12,11,3,13\\}.$

There are two components in $[U_{1}]\smallsetminus(3)$. The vertices of these
components are

$Q_{11}=\\{12,11\\}~{}\mbox{and}~{}Q_{12}=\\{13\\}.$

######  Lemma 10.

Th following items hold.

  1. (i)

${\rm det}(R[U_{i},U_{i}])=R_{u_{i}u_{i}}(\prod\limits_{k=1}^{p_{i}}{\rm
det}(R[Q_{ik},Q_{ik}]))$.

  2. (ii)

$G_{i1},\dotsc,G_{ip_{i}}$ are connected components of
$T\smallsetminus(u_{i})$.

  3. (iii)

${\rm det}(R[U_{i},U_{i}])\geq 0$.

###### Proof.

Let $a\in Q_{ir}$, $b\in Q_{is}$ and $r\neq s$. By definition,

$R_{ab}=-d_{21}+d_{a1}+d_{2b}-d_{ab}.$

Since $u_{i}\in V({\mathbf{P}}_{12})$,

$R_{ab}=-d_{2u_{i}}-d_{u_{i}1}+d_{a1}+d_{2b}-d_{ab}.$ (31)

As $a\in U_{i}$, it follows from item (i) of Lemma 8 that

$d_{au_{i}}=d_{a1}-d_{1u_{i}}.$ (32)

Using (32) in (31),

$R_{ab}=-d_{2u_{i}}+d_{u_{i}a}+d_{2b}-d_{ab}.$ (33)

As $b\in U_{i}$, it follows from item (i) of Lemma 8 that

$d_{bu_{i}}=d_{2b}-d_{2u_{i}}.$ (34)

Using (34) in (33),

$R_{ab}=d_{bu_{i}}+d_{u_{i}a}-d_{ab}.$ (35)

Finally, since $a$ and $b$ belong to different components of
$[U_{i}]\smallsetminus(u_{i})$,

$d_{bu_{i}}+d_{u_{i}a}=d_{ab}.$ (36)

Using (36) in (35)

$R_{ab}=0.$

We now show that $R_{u_{i}x}=0$ for any $x\in Q_{is}$. By definition,

$R_{u_{i}x}=-d_{21}+d_{u_{i}1}+d_{2x}-d_{u_{i}x}.$

Since $u_{i}$ lies on ${\mathbf{P}}_{12}$,

$R_{u_{i}x}=-d_{u_{i}2}+d_{2x}-d_{u_{i}x}.$ (37)

As $x\in Q_{is}\subset U_{i}$, by part (i) of Lemma 8,

$d_{xu_{i}}+d_{2u_{i}}=d_{2x}.$ (38)

By (37) and (38),

$R_{u_{i}x}=0.$

Similarly,

$R_{xu_{i}}=0.$

By item (c) in (P3), we now conclude that $R[U_{i},U_{i}]$ is similar to a
block diagonal matrix with diagonal blocks

$R_{u_{i}u_{i}},~{}~{}R[Q_{ik},Q_{ik}]~{}~{}~{}~{}~{}k=1,\dotsc,p_{i}.$

Hence

${\rm det}(R[U_{i},U_{i}])=R_{u_{i}u_{i}}(\prod_{k=1}^{p_{i}}{\rm
det}(R[Q_{ik},Q_{ik}])).$

This completes the proof of (i).

By definition $G_{i1},\dotsc,G_{ip_{i}}$ are connected components of
$[U_{i}]\smallsetminus(u_{i})$. So, each $G_{ik}$ is connected. Suppose
$G_{ik}$ is not a connected component of $T\smallsetminus(u_{i})$. Then, there
exists $v\in V(T)\smallsetminus\\{u_{i}\\}$ but not in $Q_{ik}$ such that $v$
is adjacent to a vertex $g\in Q_{ik}$.

Suppose $v\in Q_{ij}$ for some $j\neq k$. But $Q_{ik}$ and $Q_{ij}$ are
components of $[U_{i}]\smallsetminus(u_{i})$ and hence $u_{i}\in
V({\mathbf{P}}_{gv})$. This is not possible.

Suppose $v\in U_{j}$ where $j\neq i$. Then, item (iv) in Lemma 8 implies
$u_{i}\in V({\mathbf{P}}_{gv})$. This is not possible.

Suppose $v\in V_{B}$. Then, Lemma 6 gives $2\in V({\mathbf{P}}_{vg})$. Again,
this is not possible.

Let $v\in V_{2}\cup\cdots\cup V_{m}$. Since $g\in V_{1}$,
$1\in{\mathbf{P}}_{gv}$. This is a contradiction. Thus, $G_{ik}$ is a
connected component of $T\smallsetminus(u_{i})$. The proof of (ii) is
complete.

Fix $k\in\\{1,\dotsc,p_{i}\\}$. We use Lemma 3. Set $\tilde{X}=X=G_{ik}$,
$E=Q_{ik}$ and $\alpha=u_{i}$. By (ii), $X$ is a connected component of
$T\smallsetminus(u_{i})$. Hence ${\rm det}(R[Q_{ik},Q_{ik}])\geq 0$. In view
of item (i), ${\rm det}(R[U_{i},U_{i}])\geq 0$. The proof is complete. ∎

From Corollary 3 and Lemma 10, we get the following.

######  Lemma 11.

${\rm det}(R[V_{A},V_{A}])\geq 0.$

###  3.9  Computation of ${\rm det}(R[V_{B},V_{B}])$

Let $[V_{B}]$ have $s$ components and let the vertex sets of these components
be

$W_{1},\dotsc,W_{s}.$

For example in Figure 1, $[V_{B}]$ has two components

$W_{1}=\\{5,6\\},~{}W_{2}=\\{15,16\\}.$

######  Lemma 12.

Let $z_{i}\in W_{i}$ and $z_{j}\in W_{j}$ where $i\neq j$. Then $2\in
V({\mathbf{P}}_{z_{i}z_{j}})$.

###### Proof.

Since $z_{i}$ and $z_{j}$ belong to different components of $[V_{B}]$, there
must exist a vertex $x$ such that

$x\in V_{1}^{\prime},~{}~{}x\notin V_{B},~{}~{}\mbox{and}~{}~{}x\in
V({\mathbf{P}}_{z_{i}z_{j}}).$

If $x=2$, then we are done. Now, assume $x\neq 2$. Then, $x\in V_{A}$. Since
$z_{i}\in V_{B}$, Lemma 6 implies that $2\in V({\mathbf{P}}_{z_{i}x})$. This
implies $2\in V({\mathbf{P}}_{z_{i}z_{j}})$. The proof is complete. ∎

######  Lemma 13.

$[W_{1}],\dotsc,[W_{s}]$ are connected components of $T\smallsetminus(2)$.

###### Proof.

Each $[W_{j}]$ is connected. Suppose $[W_{j}]$ is not a component in
$T\smallsetminus(2)$. Then there exists a vertex $g\in W_{j}$ adjacent to
$v\in V(T\smallsetminus(2))\smallsetminus W_{j}$.

Let $v\in W_{k}$, where $k\neq j$. Then, by Lemma 12, $2\in
V({\mathbf{P}}_{vg})$. This is not possible.

Suppose $v\in V_{A}$. Then, by Lemma 6, $2\in V({\mathbf{P}}_{vg})$. This is a
contradiction.

Suppose $v\notin V_{1}^{\prime}$. Then, $v\in V_{2}\cup\cdots\cup V_{m}$;
hence $1\in V({\mathbf{P}}_{vg})$. This is a contradiction.

Thus, $[W_{j}]$ is a component in $T\smallsetminus(2)$. This completes the
proof. ∎

######  Lemma 14.

The following items hold.

  1. (i)

${\rm det}(R[V_{B},V_{B}])=\prod\limits_{\nu=1}^{s}{\rm
det}(R[{W_{\nu}},{W_{\nu}}])$.

  2. (ii)

${\rm det}(R[W_{i},W_{i}])\geq 0~{}~{}~{}~{}i=1,\dotsc,s$.

  3. (iii)

${\rm det}(R[V_{B},V_{B}])\geq 0$.

###### Proof.

The sets $W_{1},\dotsc,W_{s}$ partition $V_{B}$. Let $a\in W_{i}$ and $b\in
W_{j}$. We claim that if $i\neq j$, then $R_{ab}=0$. By definition

$R_{ab}=-d_{21}+d_{a1}+d_{2b}-d_{ab}.$ (39)

By Lemma 12, $2\in V({\mathbf{P}}_{ab})$. Hence

$d_{ab}=d_{a2}+d_{2b}.$ (40)

By (39) and (40),

$R_{ab}=-d_{21}+d_{a1}+d_{2b}-d_{a2}-d_{2b}=-d_{21}+d_{a1}-d_{a2}.$ (41)

Since $a\in V_{B}$, $2\in V({\mathbf{P}}_{a1})$,

$d_{a1}=d_{a2}+d_{21}.$ (42)

By (41) and (42),

$R_{ab}=0.$

By (P3), $R[V_{B},V_{B}]$ is similar to a block diagonal matrix with diagonal
blocks

$R[{W_{1}},{W_{1}}],\dotsc,R[{W_{s}},{W_{s}}].$

Therefore,

${\rm det}(R[V_{B},V_{B}])=\prod_{i=1}^{s}{\rm det}(R[{W_{i}},{W_{i}}]).$

This completes the proof of (i).

The proof of (ii) follows by substituting $\widetilde{X}=X=[W_{i}]$, $E=W_{i}$
and $\alpha=2$ in Lemma 3.

Item (iii) is immediate from (i) and (ii). ∎

Corollary 2, Lemma 11 and Lemma 14 give the following.

######  Lemma 15.

${\rm det}(R[V_{1},V_{1}])\geq 0.$

###  3.10 Proof of main result

######  Theorem 1.

The Moore-Penrose inverse of the distance Laplacian matrix of a tree is a Z
matrix.

###### Proof.

The proof follows from Lemmas 2, 5 and 15. ∎

##  4 An example

We can ask if the result true for any Euclidean distance matrix. Here is a
counter example. Let

$D=\left[\begin{array}[]{ccccccccccccc}0&1&4&9&16\\\ 1&0&1&4&9\\\ 4&1&0&1&4\\\
9&4&1&0&1\\\ 16&9&4&1&0\end{array}\right].$

Using standard techniques, it can be verified that $D$ is an Euclidean
distance matrix. Let

$\Delta:=\mathop{\rm
Diag}(\eta_{1},\eta_{2},\eta_{3},\eta_{4},\eta_{5})~{}~{}\mbox{and}~{}~{}~{}S:=\Delta-D.$

Then,

$S^{\dagger}=\left[\begin{array}[]{ccccccccccccc}\frac{2}{81}&\frac{-1}{81}&\frac{-1}{90}&\frac{-1}{405}&\frac{1}{810}\\\
\frac{-1}{81}&\frac{19}{405}&\frac{-1}{45}&\frac{-4}{405}&\frac{-1}{405}\\\
\frac{-1}{90}&\frac{-1}{45}&\frac{1}{15}&\frac{-1}{45}&\frac{-1}{90}\\\
\frac{-1}{405}&\frac{-4}{405}&\frac{-1}{45}&\frac{19}{405}&\frac{-1}{81}\\\
\frac{1}{810}&\frac{-1}{405}&\frac{-1}{90}&\frac{-1}{81}&\frac{2}{81}\end{array}\right].$

We see that $s_{15}^{{\dagger}}>0$.

Acknowledgement: We thank Prof. R. B. Bapat for introducing this problem. The
result in this paper was observed by Prof. Michael Neumann.

## References

  * [1] R.B. Bapat,  Graphs and Matrices,  Springer-Verlag, London,  2014\.
  * [2] R. Bapat, S.J. Kirkland, M. Neumann,  On distance matrices and Laplacians,  Linear algebra and its applications,  401,  2005,  193-209.
  * [3] R Balaji, R.B. Bapat, S. Goel,  Distance Matrices Perturbed by Laplacians,  Applications of Mathematics,  65,  2020,  599-607.
  * [4] M. Aouchiche, P. Hansen,  Two Laplacians for the distance matrix of a graph,  Linear Algebra and its Applications,  439,  2013,  21-33.
  * [5] R. Balaji, R.B. Bapat  Block distance matrices,  Electronic Journal of Linear Algebra,  17,  2007,  435-443.
  * [6] E. Deutsch, M. Neumann,  Derivatives of the Perron root at an essentially nonnegative matrix and the group inverse of an M-matrix,  Journal of Mathematical Analysis and Applications,  102(1),  1984,  1-29.
  * [7] S.J. Kirkland, M. Neumann,  The M-Matrix Group Generalized Inverse Problem for Weighted Trees,  SIAM Journal on Matrix Analysis and Applications,  19(1),  1998,  226-234.
  * [8] G.P.H. Styan, G. E. Subak-Sharpe,  Inequalities and equalities associated with the campbell-youla generalized inverse of the indefinite admittance matrix of resistive networks,  Linear Algebra and its Applications,  250,  1997,  349-370.

R. Balaji and Vinayak Gupta
Department of Mathematics
Indian Institute of Technology -Madras
Chennai 600036
India.