Unimodality and peak location of the  characteristic polynomials of two distance matrices of trees

Rakesh Jana

Iswar Mahato
Sivaramakrishnan Sivasubramanian
Department of Mathematics, Indian Institute of Technology Bombay, Mumbai 400076, India

Unimodality of the normalized coefficients of the  characteristic polynomial of distance matrices of trees are known and bounds on the location of its peak (the largest coefficient) are also known. Recently, an extension of these results to distance matrices of block graphs was given. In this work, we extend these results to two additional distance-type matrices associated with trees: the Min-4PC matrix and the 2-Steiner distance matrix. We show that the sequences of coefficients of the characteristic polynomials of these matrices are both unimodal and log-concave. Moreover, we find the peak location for the coefficients of the characteristic polynomials of the Min-4PC matrix of any tree on $n$ vertices. Further, we show that the Min-4PC matrix of any tree on $n$ vertices is isometrically embeddable in $\RR^{n-1}$ equipped with the $\ell_1$ norm.

Unimodal, Log-concave, Characteristic polynomial, Four-point condition, Steiner distance.
[2020] 05C5005C0505C1215A18.

§ INTRODUCTION

Let $A = a_0,a_1,\cdots,a_m$ be a sequence of real numbers. The sequence $A$ is called
unimodal if there exists an index $k$ with $1 \leq k \leq m-1$
such that $a_{j-1}\leq a_j$
when $j\leq k$ and $a_j\geq a_{j+1}$ when $j\geq k$.  The  sequence $A$

is called log-concave if
$a_i^2\geq a_{i-1}a_{i+1}$ when $1 \leq i \leq m-1$. Log-concavity and unimodality are significant properties with application across various areas; for example, algebra (see [6] by Brändén and [14] by Stanley), probability theory  (see [13] by Prekopa), combinatorics and geometry [14]. These applications emphasize the importance of understanding and identifying log-concave sequences in different mathematical contexts. For the distance matrix of a tree, Graham and Lovász in <cit.> conjectured unimodality of the normalized coefficients of the characteristic polynomial of the distance matrix of trees and also conjectured the location of the peak(s). The unimodality part was proved by Aalipour et. al. in
[1] and the peak location was disproved by Collins in [8].

Two points are noteworthy.  Firstly,
for a square matrix $M$, the definition of its characteristic
polynomial used in all earlier papers is $\chi_M(x) = \det(M - xI)$
and this does not always make
$\chi_M(x)$ monic.  We thus change the definition slightly
and define

\begin{equation}
\label{eqn:charpoly_monic}
\charpoly_M(x) = \det(xI - M).
\end{equation}

Doing this small change helps us get rid of the need to multiply
its coefficients by a power of $(-1)$ with the exponent depending on $n$.

Hence, for the rest of this paper, for square matrices $M$, we define
$\charpoly_M(x)$ using (<ref>) and make the
needed small changes to results before  quoting them
from the literature.

Secondly, normalizing the coefficients of the  characteristic
polynomial is not important for unimodality as we get similar
results by scaling the coefficients $c_k$ of the characteristic polynomial
by $\alpha^k$, where $\alpha$ is a positive real number.  This point is also mentioned by both
Abiad et. al
in <cit.>
and by Aalipour et. al in
However, to determine the peak location of a unimodal sequence (or for
bounds on the peak location), it is important to know whether we
take the coefficients of the characteristic polynomial or its
normalized version.
In this paper, for results on the peak location, we consider the sequence
of coefficients of $\charpoly_M(x)$ without any normalization.
Abiad et. al in
[2] also
give their results for the coefficients of the un-normalized characteristic polynomial.

Let $T$ be a tree with $n$ vertices and let $D$ be its distance
matrix.  Let $\charpoly_D(x) = \det (xI - D) = \sum_{k=0}^n c_k x^k$
be $D$'s characteristic polynomial.  By definition, as
$\charpoly_D(x)$ is a monic polynomial, $c_n = 1$.
We further have $c_{n-1} = 0$ as $c_{n-1} = \Tr(D)$ which is
zero (as all diagonal entries of distance matrices are zero). In [1], Aalipour et. al proved the following result.

With the notation above, let $\displaystyle d_k = \frac{-1}{2^{n-k-2}}
c_k$ be the normalized coefficients of $\charpoly_D(x)$.  Then, the
sequence $d_k$ as $k$ varies from $0$ to $n-2$ is unimodal and log concave.

The proof of Theorem <ref> uses real
rootedness of $\charpoly_D(x)$ to show log
concavity. For unimodality, they need the following result
of Edelberg, Garey and Graham (see <cit.>)
which states that when $0 \leq k \leq n-2$,
$c_k$ is negative (and hence $d_k$ is positive).

With $T$ and $D$ as above, let $\displaystyle \charpoly_D(x) = \sum_{k=0}^n c_k x^k.$
Then, for $0 \leq k \leq n-2$, we have $c_k < 0$.

An extension of these results to distance matrices
of block graphs was obtained by
Abiad et al.
in [2].
The authors showed unimodality results for
coefficients in the characteristic polynomial of distance
matrices  of block graphs along similar lines and gave bounds on
the peak location for some block graphs.

In this paper, we extend such results to two other matrices.  Both
matrices are defined for trees $T$.  The first, $\Min_T$ is very similar to the
distance matrix $D_T$ of trees $T$ while the second is 2-Steiner
distance matrix $\DD_2(T)$ of trees $T$.   This second matrix does
not have diagonal elements that are zero but our proof goes through nonetheless.
Both of these are $\binom{n}{2} \times \binom{n}{2}$ matrices but are
not full rank matrices (see [3, 4]), so our results are for the restriction of these
matrices to a basis for their respective row spaces.

Let $T$ be a tree on $n$ vertices and let $\VV$ be the set of 2-element
subsets of the vertices of $T$.  Clearly $|\VV| = \binom{n}{2}$.  Define the following
$\binom{n}{2} \times \binom{n}{2}$ matrices whose rows and columns are indexed by
elements of $\VV$.
Let $d_{i,j}$ be the distance between $i$ and $j$ in $T$.  For four
vertices $i,j,k$ and $l$ from the vertex set of $T$, define the

$$S_{i,j,k,l} = \{ d_{i,l} + d_{j,k}, d_{i,k} + d_{j,l},
d_{i,j} + d_{k,l}\}.$$

Tree distances are special and Buneman
in [7] showed that for all choices $i,j,k,l$ of four
vertices, among the three terms in $S_{i,j,k,l}$, the second maximum value
equals the maximum value.  This inspired the definition of
the following $\binom{n}{2} \times \binom{n}{2}$ matrices.

Define the $\Min_T$ matrix as follows.  For $\{i,j\}, \{k,l\} \in \VV$,
the entry of $\Min_T$ corresponding to the row $\{i,j\}$ and the column $\{k,l\}$
is the minimum entry of $S_{i,j,k,l}$.  One can also define
the $\Max_T$ matrix by changing the word “minimum" in the
previous sentence to “maximum".    For a tree $T$, Azimi and Sivasubramanian
in [3] defined $\DD_2(T)$,
the 2-Steiner distance matrix of a tree $T$ as follows. For $\{i,j\}, \{k,l\} \in \VV$, the entry of
$\DD_2(T)$ corresponding to the row $\{i,j\}$ and column $\{k,l\}$
is the minimum number of edges among all connected subtrees of $T$ whose vertex set contains
the four vertices $i,j,k$ and $l$.
Azimi and Sivasubramanian showed that $\DD_2(T)$ is the average of the $\Max_T$ and $\Min_T$ matrix, that is, $\DD_2(T) = \frac{1}{2} \Big(\Max_T + \Min_T \Big)$.

Bapat and Sivasubramanian in
[4] studied the $\Min_T$ matrix and showed
results on its rank and  its invariant factors.
Consider a tree $T = (V,E)$ on $n$ vertices.  Let $j,k \in V$ with
$j\not= k$ be two vertices and let $f = \{j,k\}
\not\in E$ be a non edge of $T$ with $d_{j,k} = d > 1$
(that is, the distance in $T$ between $j$ and $k$ is $d$).
Bapat and Sivasubramanian in [4] proved that
$\rk(\Min_T) = n$ and
the set $B = E \cup \{f\}$ forms basis of $\Min_T$'s row space.
Our first result is the following about $\Min_T[B,B]$, the
submatrix of $\Min_T$ restricted to both the rows and columns in $B$.

With the notation above, let $N = \Min_T[B,B]$ and  $\charpoly_N(x) =  \sum_{k=0}^n a_kx^k$. Then, the sequence $|a_k|$  as $k$ varies from $0$ to $n-2$ is unimodal and log-concave. If $|a_t| = \max_{0 \leq k \leq n-2} |a_k|$  is the largest coefficient in absolute value, then  $\lfloor \frac{n-2}{3} \rfloor \leq t \leq \lceil \frac{n+1}{3}\rceil$.

When $T$ is a tree of order
$n$ with $p$ leaves and $B \in \BB$ is a basis of $\DD_2(T)$'s row space, the authors in
<cit.> proved that
$\DD_2(T)[B,B]$ has $2n-p-2$ negative eigenvalues and one positive eigenvalue. In this paper, we show that when $B$ is a basis of $\Min_T$'s row space, we get an analogous statement
for the matrix $\Min_T[B,B]$.   This is proved in two ways
with our first proof being Theorem <ref> proved in Section <ref>. Our second proof is more general and is of independent interest
as it gives some corollaries about hypermetricity and negative-type
metric spaces which we do not get from our first proof.
In Section <ref>, we
give an isometric embedding of $T$'s $\binom{n}{2} \times
\binom{n}{2}$  $\Min_T$ matrix into $\RR^{n-1}$ equipped with
the $\ell_1$ norm.  We prove the following result.

Let $T$ be a tree having $n$ vertices.

Then, $\Min_T$ is isometrically $\ell_1$-embeddable in

Our proof is surprisingly easy and appears in Section <ref>. For all trees $T$, it follows from the theory of isometrically $\ell_1$-embeddable finite metric spaces (see Deza and Laurent
<cit.>) that the $\Min_T$ matrix has exactly one positive eigenvalue. By standard interlacing arguments, restricting $\Min_T$ to elements
from a basis $B$, if $\Min_T[B,B]$ is a full rank matrix having
rank $r$,  one infers that $\Min_T[B,B]$ has $r-1$ negative eigenvalues
and 1 positive eigenvalue.

A distance matrix $D = (d_{i,j})_{1 \leq i,j \leq n}$ is said to be
a hypermetric if

\begin{equation}
\label{eqn:ineq-for-metr}
\sum_{1 \leq i < j \leq n} x_ix_jd_{i,j} \leq 0
\end{equation}

for all $x \in \ZZ^n$ with $\sum_{i=1}^n x_i = 1$ ($x_i$ here is the $i$-th
component of $x$).  If inequality
(<ref>) holds for  all $x \in \ZZ^n$
with $\sum_{i=1}^n x_i = 0$,
then $D$ is said to be a negative type metric.  It is known (see
<cit.>) that if a distance
matrix $D$ is isometrically embeddable in an $\ell_1$ space,
then it is both hypermetric and of negative type.
For any tree $T$, though the matrix $\Min_T$ satisfies the
triangle inequality, proving this takes some work.  Remark
<ref> shows that this can be
obtained as a simple consequence of our isometric embedding.

Azimi and Sivasubramanian in [3]
considered the matrix $\DD_2(T)$.
Note that the diagonal entry of $\DD_2(T)$ corresponding to
the row and column indexed by $\{i,j\} \in \VV$ equals $d_{i,j}$,
which is the tree distance between $i$ and $j$.
Hence, $\DD_2(T)$
does not have zero entries in its diagonal (indeed all its
main diagonal entries are positive).  For a tree $T$ of order $n$ with $p$ leaves
Azimi and Sivasubramanian
showed that $\rk(\DD_2(T)) = 2n-p-1$, gave a class $\BB$ of bases for
its row space and obtained the determinant of
$\DD_2(T)[B,B]$,  the restriction of $\DD_2(T)$ to the entries in rows and columns from $B \in \BB$. In this article, we obtain the following result about $\DD_2(T)[B,B]$.

Let $T$ be a tree on $n$ vertices and let $T$ have $p$ leaves.   With the
notation above, for any $B \in \BB$, consider $P = \DD_2(T)[B,B]$
and let $\charpoly_P(x) = \sum_{k=0}^{2n-p-1} a_kx^k$.
Then, the sequence $|a_k|$ as $k$ varies from $0$ to $2n-p-2$
is unimodal and log-concave.

Though we start with singular matrices, by restricting attention
to entries from a basis, we consider two full rank $r \times r$
matrices $M$.  Further, all our matrices will have
exactly one positive eigenvalue and $(r-1)$ negative eigenvalues.
Check that the result quoted below is on matrices with all
diagonal entries being 0.
We give a mild generalization of
on the $\charpoly_M(x)$ where $M$
has exactly one positive eigenvalue and has non negative
entries along its main diagonal.   This is given as Theorem
<ref> in Section <ref>.

We need this version for the matrix $\DD_2(T)[\BB,\BB]$,
as it has non-zero elements on its diagonals.

A uniform proof giving bounds on the peak location of the coefficients
of $\charpoly_{\DD_2(T)[B,B]}(x)$ for all trees $T$ seems hard.  So, we consider three
special cases, the star tree, the bi-star tree $S_{1,n-3}$ and the path tree
and obtain bounds on $|a_t| = \max_{0 \leq k \leq 2n-p-3} |a_k|$,
the largest coefficient in absolute value in their
respective characteristic polynomials.  For the star and
the bi-star our bounds are tight and are given as
Theorem  <ref> and Theorem
<ref> in Subsections
<ref> and <ref>, respectively.
For the path tree, we give an upper bound on the
peak location as Theorem <ref>
in Subsection <ref>, and we
conjecture the value of the peak location.

§ UNIMODALITY AND LOG-CONCAVITY

For unimodality, we will need the idea of real rootedness of polynomials
with real coefficients.  The following result
<cit.> is known.

Let $p(x)=\sum_{k=0}^n a_kx^k$ be a real-rooted polynomial with real

* Then its coefficient sequence $a_0,a_1,\hdots,a_n$ is

* If a sequence $a_0,a_1,\hdots,a_n$ is both positive and
log-concave, then it is unimodal.

For any real and symmetric matrix $M$, by the Spectral Theorem,
$\charpoly_M(x)$ is real rooted and so the first part of
Lemma <ref> is  trivially satisfied.
When all eigenvalues of $M$ are negative, it is easy to see that all
coefficients of $\charpoly_M(x)$ are positive.

When $M = (m_{i,j})_{1 \leq i,j \leq n}$ is an $n \times n$ real, symmetric
matrix with $m_{i,i} = 0$ for $1 \leq i \leq n$, and if $M$ has
exactly one positive eigenvalue then, the
proof of Theorem <ref> can be extended
to show that almost all the coefficients of $\charpoly_M(x)$
are negative.  This is the main point of

Below, we mildly generalize this to include real, symmetric
matrices which have a non negative trace.  Recall
the inertia of a real symmetric matrix $M$ is the triple
$\Inertia(M) = \big(n_{+}(M),n_{-}(M),n_{0}(M)\big)$.  Here, $n_{+}(M),$
$n_{-}(M)$ and $n_{0}(M)$ denote the number of positive, negative and zero
eigenvalues of $M$ respectively.

Consider a  real, symmetric matrix $M$ of order $n$ with $\Tr(M)\geq 0$ and $\charpoly_M(x)=\sum_{k=0}^n a_kx^k$.

Let $\Inertia(M)=(1,r-1,n-r)$, with $2\leq r\leq n$. If
$\Tr(M)=0$, then $a_k<0$ when $n-r\leq k\leq n-2$ and
if $\Tr(M)> 0$, then $a_k<0$ when $n-r\leq k\leq n-1$.

Let the non zero eigenvalues of $M$ be $\lambda_1, -\lambda_2, -\lambda_3,
\ldots, -\lambda_r$
and let the eigenvalue $0$ occur with multiplicity $n-r$.  Here, we
assume that $\lambda_i > 0$ when $1 \leq i \leq r$ and that the
$\lambda_i$'s need not be distinct.  Define $g_0 = 1$ and
when $k \geq 1$, define
$g_k$ to be the sum of all $k$-fold products of $\lambda_2, \ldots,
\lambda_n$.  Clearly, $g_k > 0$ when $1 \leq k \leq r$.  Further

\begin{eqnarray}
\charpoly_M(x) & = & x^{n-r}(x-\lambda_1)\prod_{i=2}^r(x+\lambda_i)  =  x^{n-r}(x - \lambda_1)\Bigg( \sum_{k=0}^{r-1} g_k x^{r-1-k}\Bigg) \nonumber \\
& = & \Bigg( x^n + \sum_{k=1}^{r-1} \big( g_k - \lambda_1g_{k-1} \big) x^{n-k} -\lambda_1 g_{n-1} x^{n-r} \Bigg) \label{eqn:imp}
\end{eqnarray}

Since $\lambda_1=g_1+t$, $g_k - \lambda_1g_{k-1}=g_k - (g_1+t)g_{k-1}
=(g_k-g_1g_{k-1})-tg_{k-1}<0 $ as we have $t\geq 0$ and
$ -\lambda_1 g_{n-1}= -(g_1+t) g_{n-1}<0$.
Moreover, $c_{n-1}=-\Tr(M)=-t$.  Hence,
when $n-r\leq k\leq n-1$ and  $t>0$, we have $a_k<0$.
Likewise, when $n-r\leq k\leq n-2$ and $t=0$, we have
$a_k<0$, completing the proof.

The following corollary of Theorem <ref> can be drawn.

Let $M$ be a real and symmetric matrix of order $n$ with $\charpoly_M(x)=\sum_{k=0}^n a_kx^k$ and $\Inertia(M)=(1,n-1,0)$.

* If $\Tr(M)=0$, then the sequence $|a_0|, |a_1|, \hdots,
of the  absolute values of its coefficients from $\charpoly_M(x)$
is log-concave and unimodal.

* If $\Tr(M)>0$, then the sequence $|a_0|, |a_1|, \hdots,
|a_{n-2}|, |a_{n-1}|$ of the  absolute values of its coefficients
from $\charpoly_M(x)$ is log-concave and unimodal.

Since $M$ is a real, symmetric matrix,
$\charpoly_M(x)$ is real-rooted and hence by Lemma <ref>, it
follows that the sequence $a_0,a_1,\hdots,a_{n-2},a_{n-1}, a_n$ is log-concave.

1. By Theorem <ref>, we get $a_k<0$ when $0\leq k\leq n-2$. Since
all terms $a_0,a_1,\hdots,a_{n-2}$ are negative, the sequence comprising their absolute
values $(|a_k|)_{k=0}^{n-2}$ is log-concave and positive.  By Lemma
<ref>,  $|a_0|, |a_1|, \hdots, |a_{n-2}|$ is unimodal.

2. By Theorem <ref>, we have $a_k<0$ for $0\leq k\leq n-1$.  As
all the terms $a_0,a_1,\hdots,a_{n-1}$ are negative, the sequence
comprising their absolute values $(|a_k|)_{k=0}^{n-1}$ is log-concave and positive.
By Lemma <ref>, $|a_0|, |a_1|, \hdots,
|a_{n-1}|$ is unimodal.

§ THE $\MIN_T$ MATRIX OF A TREE $T$

Let $T= \big(V,E\big)$ be a tree with $V=\{1,2,\hdots,n\}$.
Further, let $E=\{e_1,e_2,\hdots,e_{n-1}\}$. If $i,j \in V$ with $f=\{i,j\}
\not\in E$ be a non-edge of $T$ with $d_{i,j} = d > 1$,
then Bapat and Sivasubramanian in [4] showed
that $B = E \cup \{f\}$ is a basis of $\Min_T$'s row space.
Consider the $n \times n$ matrix $N = \Min_T[B,B]$ obtained by
restricting the matrix $\Min_T$ to its rows and columns in $B$.
We start this section with the following result.

Let $N = \Min_T[B,B]$ be the matrix as described above. Then, $N$ has
$(n-1)$ negative eigenvalues and  one positive eigenvalue.

In our proof, we use the Schur complement formula for inertia.  The matrix $N$
restricted to the
rows and columns indexed by $E$ is $K = 2(J-I)$ (see <cit.>)
whose inverse is also presented in <cit.>. Clearly,
$K$ has $(n-2)$ negative eigenvalues and one positive eigenvalue.
Further, let $x_f$ be an $(n-1)$-dimensional
column vector with its columns indexed by $e \in E$ with its
$e$-th component $x_f(e) = \Min_T(f,e)$.  Then, the Schur complement of $K$ in
$N$ equals $0 - x_f^tK^{-1}x_f$.  By
<cit.>, this equals $p = -\frac{n-1}{2(n-2)}$.  Since
$\Inertia(N) = \Inertia(K) + \Inertia(p)$, we get that $N$ has only
one positive eigenvalue and $n-1$ negative eigenvalues.

To give our proof of Theorem <ref>, we
compute $\charpoly_N(x)$

using equitable partitions.  We first recall the definition
of an equitable partition of a matrix $M$.

Let $M$ be an $n \times n$ real, symmetric matrix and index the rows
and columns of $M$ by elements of the set $X$. Let
$\Pi=\{X_1,X_2,\hdots,X_p\}$ be a partition of the set $X$ and let $M$
be partitioned according to $\Pi$ as

\[M=\left( {\begin{array}{cccc}
M_{11} & M_{12} &\hdots & M_{1p}\\
M_{21} & M_{22} &\hdots & M_{2p}\\
\vdots &\vdots & \ddots & \vdots\\
M_{p1} & M_{p2}& \hdots &M_{pp}\\
\end{array} } \right).\]

Here, $M_{ij}$ denotes the block submatrix of $M$ induced
by the rows in $X_i$ and the columns in $X_j$.
If the row sum of each block $M_{ij}$ is a constant,
then the partition $\Pi$ is called an equitable partition.
Let $q_{ij}$ denote
the average row sum of $M_{ij}$.   The matrix $Q=(q_{ij})$
is called the quotient matrix of $M$ with respect to $\Pi$.

Next, we state a well-known result (see <cit.>)
connecting the spectrum of a quotient matrix arising from an equitable partition
to the spectrum of the original matrix.

Let $Q$ be a quotient matrix of any real, symmetric, square matrix $M$ arising from
an equitable partition. Then, all eigenvalues of $Q$ are eigenvalues of $M$.

We next find the spectra of $\Min_T[B,B]$ for any tree $T$ of order $n$.

For any tree $T$ on $n$ vertices, the eigenvalues of $\Min_T[B,B]$ are $-2$ with
multiplicity $n-3$, and the three roots of the cubic polynomial

Let $f = \{i,j\}$ with $d_{i,j} = d$.  By relabelling, we can assume
that the edges $e_1, e_2, \ldots, e_d$ are on the $ij$-path in $T$.
Let $E_1=\{e_1,e_2,\hdots,e_d\}$ and $E_2=\{e_{d+1},\hdots,e_{n-1}\}$.
Let $J$ denote a matrix all of whose entries are 1 (of appropriate
dimension) and $I$ denoting the identity matrix (of appropriate
dimension), and $\bone$ denote a column vector all of whose components
are 1 (of appropriate dimension).  With these, $N=\Min_T[B,B]$ can be written as

\[ N=
\begin{blockarray}{cccc}
& E_1 & E_2  & f\\
\begin{block}{c(ccc)}
E_1 & 2(J-I)  & 2J & (d-1) \bone \\
E_2 & 2J & 2(J-I) & (d+1) \bone \\
f & (d-1)\bone^t & (d+1)\bone^t &  0\\
\end{block}
\end{blockarray} ~.\]

Let $e(i,j)$ denote the $n$-dimensional column vector that has its $i$-th component
$1$, its $j$-th component $-1$ and all other components as $0$.
If $S=\{e(j,j+1):1\leq j\leq d-1\}\cup \{e(j,j+1):d+1\leq j\leq n-2\}$, then for
any $\textbf{x}\in S$, we have $N\textbf{x}=-2\textbf{x}$.
Note that $|S|=n-3$, and that all vectors in $S$ are linearly independent.
Therefore, $-2$ is an eigenvalue of $N$ with multiplicity at least $n-3$.

Recall that $E_1=\{e_1,e_2,\hdots,e_d\}$ and $E_2=\{e_{d+1},\hdots,e_{n-1}\}$.
Then it is
easy to check that $\Pi_1=E_1 \cup E_2\cup \{f\}$ is an equitable partition of $N$
with quotient matrix

\[Q_{\Pi_1}=
\left ( {\begin{array}{ccc}
2(d-1) & 2(n-d-1) & d-1\\
2d & 2(n-d-2) & d+1 \\
d(d-1) & (d+1)(n-d-1) & 0 \\
\end{array} } \right).\]

By a direct calculation, the characteristic polynomial of $Q_{\Pi_1}$ is

By Lemma <ref>, all eigenvalues of $Q_{\Pi_1}$ are
eigenvalues of $N$ as well. Since $g(-2)\neq 0$, the eigenvalues of $N$ are $-2$
with multiplicity $n-3$, and the roots of $g(x)=0$.  This completes the proof.

We proceed to give our proof of Theorem <ref>.

Proof of Theorem <ref>:
For a tree $T$ of order $n$, by Theorem <ref>,
we have $\Inertia(\Min_T[B,B])=(1,n-1,0)$. Hence, by
Corollary <ref>, the sequence $|a_0|, |a_1|,
\cdots,|a_{n-2}|$ is unimodal and log-concave.

Now, we have to find the peak location of this unimodal sequence. By
Theorem <ref>, it follows that the characteristic polynomial
of $\Min_T[B,B]$ is
$i\displaystyle f(x)=(x+2)^{n-3}(x^3+b_1x^2+c_1x+d_1),$
where $b_1=-(2n-6)$, $c_1=-(nd^2-5d^2+2nd-2d+5n-9)$ and $d_1=-2(d-1)^2(n-1)$.

Let $a_k$ be the coefficient of $x^k$ in $f(x)$.  One can check that

\begin{align*}
a_0&=d_1\binom{n-3}{0}2^{n-3}=-2(d-1)^2(n-1)2^{n-3}, \\ a_1&=\bigg[2c_1\binom{n-3}{0}+d_1\binom{n-3}{1}\bigg]2^{n-4}\\
&=-\big[8(n-3)+2(nd^2-5d^2+2nd-2d+5n-9)(n-3)\big]2^{n-5} \\
a_{n-1}&=2\binom{n-3}{n-4}+b_1\binom{n-3}{n-3}=2(n-3)-2(n-3)=0,~~ a_n=1,
\end{align*}

and for $3\leq k\leq n-3$

\begin{align*}
a_k &=\bigg[8\binom{n-3}{k-3}+4b_1\binom{n-3}{k-2}+2c_1\binom{n-3}{k-1}+d_1\binom{n-3}{k}\bigg]2^{n-k-3} \\
%&= \binom{n-3}{k-3}2^{n-k-3}\bigg(8+\frac{4b_1(n-k)}{k-2}+ \frac{2c_1(n-k)(n-k-1)}{(k-2)(k-1)}+\frac{d_1(n-k)(n-k-1)(n-k-2)}{(k-2)(k-1)k}\bigg)\\
&= \binom{n-3}{k-3}2^{n-k-3} f_1(n,k), ~~ \text{where}\\
f_1(n,k)&=8+\frac{4b_1(n-k)}{k-2}+ \frac{2c_1(n-k)(n-k-1)}{(k-2)(k-1)}+\frac{d_1(n-k)(n-k-1)(n-k-2)}{(k-2)(k-1)k}\\
&=8-\frac{8(n-3)(n-k)}{k-2}- \frac{2(nd^2-5d^2+2nd-2d+5n-9)(n-k-1)(n-k)}{(k-1)(k-2)}\\
\end{align*}

Thus, $|a_k|=\binom{n-3}{k-3}2^{n-k-3} |f_1(n,k)|$. When $n \geq 8$,
it is easy to check that $|a_0|\leq |a_1|\leq |a_2|$ and $a_{n-3}\geq a_{n-2}$.
Further, when $3\leq k\leq n-3$, we have

\begin{align*}
|a_k|- |a_{k-1}|
&= \binom{n-3}{k-3}2^{n-k-3} |f_1(n,k)|-\binom{n-3}{k-4}2^{n-k-2} |f_1(n,k-1)|\\
%&= \binom{n-3}{k-4}2^{n-k-3} \bigg[\bigg(\frac{n-k+1}{k-3}\bigg)|f_1(n,k)|-2|f_1(n,k-1)|\bigg]\\
&= \binom{n-3}{k-4}2^{n-k-3} \bigg[\frac{8(n-2)(n^2-4kn+4n+3k^2-4k-1)}{(k-3)(k-2)}\\
&~~~~~~~~+\frac{2(nd^2-5d^2+2nd-2d+5n-9)(n-k)(n-k+1)}{(k-2)(k-3)}\cdot \bigg(\frac{n-3k+1}{k-1}\bigg)\\
&~~~~~~~~+\frac{2(d-1)^2(n-1)(n-k-1)(n-k)(n-k+1)}{(k-1)(k-2)(k-3)}\cdot \bigg(\frac{n-3k-2}{k}\bigg)\bigg].
\end{align*}

Hence, when $3\leq k\leq n-3$, one can verify that
$|a_k|\geq |a_{k-1}|$ if and only if $k\leq \frac{n-2}{3}$ and
$|a_k|\leq |a_{k-1}|$ if and only if $k\geq \frac{n+4}{3}$.
Thus, when $n \geq 8$, we have  $|a_0|\leq |a_1|\leq |a_2| \leq \hdots
\leq |a_{\lfloor \frac{n-2}{3} \rfloor}|$ and
$|a_{\lceil \frac{n+4}{3}-1\rceil}| \geq |a_{\lceil \frac{n+4}{3}\rceil}|
\geq \hdots \geq |a_{n-3}|\geq |a_{n-2}|$. Hence, if $|a_t|=\max_{0\leq k\leq n-2}
|a_k|$, then $ \lfloor \frac{n-2}{3} \rfloor \leq t \leq \lceil \frac{n+1}{3}\rceil$.
This completes the proof.

§ ISOMETRICALLY EMBEDDING $\MIN_T$ IN $\ELL_1$ SPACE

For any tree $T$ having $n$ vertices, we show that the $\Min_T$ matrix is
isometrically embeddable in $\RR^{n-1}$ equipped with the $\ell_1$ norm.
This gives an alternate proof that the  matrix $\Min_T$ has
$r-1$ negative eigenvalues and one positive eigenvalue, where $r$ is the
rank of $\Min_T$.

Identify the $(n-1)$ dimensions of $\RR^{n-1}$ with the edges of $T$.  For $\{i,j\} \in
\VV$, the embedding  $\phi_{ \{i,j\} }$  maps $\{i,j\}$ to the
incidence vector of the unique path $P_{i,j}$ between $i$ and $j$ in $T$.
We illustrate by an example.  Let $T$ be the tree given in Figure
<ref> with edge set $E = \{e_1,e_2,e_3, e_4\}$.
For brevity, for $\{i,j\} \in \VV$, we omit the comma in the subscript
and denote $\phi_{i,j}$ in Figure <ref> as $\phi_{ij}$.
Let $f = \{1,4\} \in \VV$.  The set of edges on the path $P_{1,4}$
between the vertices $1$ and $4$ is clearly $P_{1,4} = \{e_1,e_2 \}$
and thus, the column vector $\phi_{14} = (1,1,0,0)^t$.   This column
vector $\phi_{1,4}$ is illustrated with a different colour
in Figure <ref>.

$\begin{array}{l|r|r|r|r|r| r|r|r|r|r|}
& \phi_{12} & \phi_{13} & \phi_{14} & \phi_{15} & \phi_{23} & \phi_{24} & \phi_{25} &
\phi_{34} & \phi_{35} & \phi_{45} \\ \hline
e_1 & 1 & 1 & \fby{1} & 1 &    0 & 0 & 0 &  0 & 0 &  0 \\
e_2 & 0 & 0 & \fby{1} & 1 &    0 & 1 & 1 &  1 & 1 &  0 \\
e_3 & 0 & 1 & \fby{0} & 0 &    1 & 0 & 0 &  1 & 1 &  0 \\
e_4 & 0 & 0 & \fby{0} & 1 &    0 & 0 & 1 &  0 & 1 &  1 \\
\end{array}$

A tree and its embedding.  Column $\phi_{14}$ is illustrated on the left.

After seeing the example in Fig <ref>, we are
now ready for the proof of Theorem <ref>.

(Of Theorem <ref>):
We identify the $n-1$ dimensions of $\RR^{n-1}$ with
the edges of $T$.
Consider the embedding $\phi: \VV \rightarrow \RR^{n-1}$
described above.  Thus $\phi_{i,j}$ is the incidence vector
of the path $P_{i,j}$.

For all $i,j, s,t \in V(T)$, we show that
$\Min_T(\{i,j\}, \{s,t\}) =
\lVert \phi_{i,j} - \phi_{s,t} \rVert_1$.

We consider two cases depending on whether the path
$P_{i,j}$ intersects the path $P_{s,t}$.

Case 1, (when $P_{i,j} \cap P_{s,t} = \emptyset$):   In this case,
note that
$\lVert \phi_{i,j} - \phi_{s,t} \rVert_1 = d_{i,j} + d_{s,t}$.
If $\alpha$ is a vertex lying on $P_{i,j}$ and $\beta$ is a vertex on
the path $P_{s,t}$  are chosen such that $d_{\alpha,\beta}$ is the smallest
among choices of vertices $\alpha$ on the path $P_{i,j}$ and $\beta$ on
the path $P_{s,t}$, then as $d_{\alpha,\beta} \geq 0$, we have
$d_{i,j} + d_{s,t} \leq d_{i,t} + d_{j,s}$ and $d_{i,j} + d_{s,t}
\leq d_{i,s} + d_{j,t}$.  Thus,
$\Min_T(\{i,j\}, \{s,t\}) = d_{i,j} + d_{s,t}=
\lVert \phi_{i,j} - \phi_{s,t} \rVert_1$.

Case 2, (when $P_{i,j} \cap P_{s,t} \not= \emptyset$):   Let
$S = P_{i,j} \cap P_{s,t}$.  As $T$ is a tree, it is easy to see
that $S$ is a set of edges
on a path from $\alpha$ to $\beta$, where  $\alpha, \beta \in V(T)$.
That is $d_{\alpha,\beta} = |S|$.  In this case, it is easy to see that
$\lVert \phi_{i,j} - \phi_{s,t} \rVert_1 = d_{i,j} + d_{s,t} -
d_{\alpha,\beta}$.   It is now clear that the minimum element
of the set $S_{i,j,s,t}$ is
$d_{i,j} + d_{s,t} - d_{\alpha,\beta}$ completing the proof.

We make two remarks from the proof of Theorem

In the proof of Theorem  <ref>, note that the
images $\phi_{i,j}$ are vectors in $\{0,1\}^{n-1}$.  Thus, for
any tree $T$ having $n$ vertices, its $\Min_T$ matrix is isometrically
embeddable in the $(n-1)$ dimensional hypercube equipped with
the Hamming metric.  This is easily seen to be stronger than
being isometrically embeddable in $\ell_1$ space.

Theorem <ref>
shows that the $\Min_T$  matrix satisfies triangle inequality.

The following corollary is easily follows from Theorem <ref>.

For any tree $T$, the matrix $\Min_T$ is hypermetric, is of negative
type and has exactly one positive eigenvalue.

§ THE 2-STEINER DISTANCE MATRIX $\DD_2(T)$ OF A TREE $T$

Recall that for a tree $T$ having $n$ vertices and $p$ pendant vertices,
Azimi and Sivasubramanian in <cit.>
showed that its 2-Steiner distance matrix $\DD_2(T)$ has rank
$r = 2n-p-1$.  They also gave the following basis.

For a tree $T$ of order $n$ with $p$ leaves, let $B_1,B_2,\hdots,B_{n-p}$ be the blocks
of its line graph $\LG(T)$ such that $|B_i|=b_i$ for $ i=1,\ldots,n-p$. If $e_i\in V(\LG(T))$,
$i=1,\ldots,n-1$ and $f_j$, $j=1,\ldots,n-p$, is the symmetric difference
of endpoints of edge  $f_j^\prime \in B_j$ in $\LG(T)$, then
$B=\{e_1,e_2,\hdots,e_{n-1},f_1,\hdots,f_{n-p}\}$ forms a
basis for the row space of $\DD_2(T)$.

Below, we provide the proof of the first part of Theorem <ref>, followed by Corollary <ref>, which shows that the sequence $|a_0|, |a_1|, \hdots, |a_{r-1}|$ is unimodal and log-concave.

(Of Theorem <ref> :)
Let $T$ be a tree of order $n$ with $p$ pendant vertices and $r = 2n-p-1$.
Azimi and Sivasubramanian in <cit.>
showed that the matrix $\DD_2(T)[B,B]$ has $r-1$ negative eigenvalues and
one positive eigenvalue. Hence, by Corollary <ref>,
it follows that the sequence $|a_0|, |a_1|, \hdots,|a_{r-1}|$ is unimodal and log-concave,
completing the first part.

For the second part of Theorem <ref>, we
give our bounds on the peak location of the coefficients of
$\charpoly_{\DD_2(T)[B,B]}(x)$.  As we consider
three families of trees, the star $S_n$, the bi-star $S_{1,n-3}$
and the path $P_n$ on $n$ vertices, we trifurcate our proof into
three subsections.

§.§ Peak location for star trees

For a star $S_n$ on $n$ vertices, $B=E\cup \{f\}$ is a basis of $\DD_2(S_n)$, where $E$ is the edge set of $S_n$ and $f=\{i,j\}\notin E$ for any two vertices $i,j$ of $S_n$. In the following theorem, we find the spectra of $\DD_2(S_n)[B,B]$.

For a star $S_n$ on $n$ vertices,
the eigenvalues of
$\DD_2(S_n)[B,B]$ are $-1$ with multiplicity $n-3$
and the roots of the cubic polynomial $g(x)=x^3-2(n-1)x^2-7(n-2)x-(n-1).$

Let $S_n$ have vertex set $V=\{1,2,\hdots,n\}$.  Let $E(T)=\{e_i =
\{1,i+1\}: 1 \leq i < n\}$ be its edge set. Without loss of generality, assume that
$f=\{2,3\}\notin E(T)$ and $B=\{e_1,e_2,\hdots,e_{n-1},f\}$.

\[
\DD_2(S_n)[B,B] =
\begin{blockarray}{cccccc}
& e_1 & e_2 & \hdots & e_{n-1} & f\\
\begin{block}{c(ccccc)}
e_1 & 1 & 2  &  \hdots & 2 & 2 \\
e_2 & 2 & 1  &  \hdots & 2 & 2 \\
%		 			e_3 & 2 & 2  & \hdots & 2 & 3 \\
\vdots & \vdots & \vdots  &\vdots &\ddots &\vdots & \vdots \\
e_{n-1} & 2 & 2  & \hdots & 1 & 3 \\
f & 2 & 2  & \hdots & 3 & 2\\
\end{block}
\end{blockarray} .\]

Let $e(i,j)$ be the $n$-dimensional column vector with its $i$-th component
$1$, its $j$-th component $-1$ and all other components being $0$. If
$X=\{e(1,2)\}\cup \{e(j,j+1):3\leq j\leq n-2\}$, then for
any $\textbf{x}\in X$,
we clearly have $\big(\DD_2(S_n)[B,B]\big)\textbf{x}=-\textbf{x}$.
Note that $|X|=n-3$,
and all vectors in $S$ are linearly independent. Therefore, $-1$ is an
eigenvalue of $\DD_2(S_n)[B,B]$ with multiplicity at least $n-3$.

Let $E_1=\{e_1,e_2\}$, $E_2=\{e_3,\hdots,e_{n-1}\}$ and
$\Pi_2: E_1 \cup E_2 \cup \{f\}$.  It is easy to see that
$\Pi_2$ an equitable
partition of $\DD_2(S_n)[B,B]$ and gives rise to the quotient matrix

\[Q_{\Pi_2}=
\left ( {\begin{array}{ccc}
3 & 2(n-3) & 2\\
4 & 2(n-4)+1 & 3 \\
4 & 3(n-3) & 2 \\
\end{array} } \right).
\mbox{ A simple computation gives }
\]

\begin{equation}
\label{eqn:charpoly_equi_partn}
\charpoly_{Q_{\Pi_2}}(x)  =  g(x)=x^3-2(n-1)x^2-7(n-2)x-(n-1).
\end{equation}

By Lemma <ref>, all eigenvalues of $Q_{\Pi_2}$ are eigenvalues
of $\DD_2(S_n)[B, B]$. Since $g(-1)\neq 0$, the eigenvalues of
$\DD_2(S_n)[B, B]$ are $-1$ with multiplicity $n-3$, and the roots of $g(x)=0$,
completing the proof.

In our next result, we determine the peak location of the coefficients
of $\charpoly_{\DD_2(S_n)[B,B]}(x)$ up to an interval of constant
size that is independent of $n$.

Let $B$ be the basis of $\DD_2(S_n)$ used
in Theorem <ref>. If $a_0,a_1,\hdots,a_n$ are the
coefficients of the characteristic polynomial of $\DD_2(S_n)[B,B]$ and
$|a_t|=\max |a_k|$, then $\lfloor \frac{n-2}{2} \rfloor \leq t
\leq \lceil \frac{n}{2}\rceil$.

By Theorem <ref> and
(<ref>),  we have

If $a_k$ is the coefficient of $x^k$ in $f(x)$, then it is easy to see that

\begin{align*}
a_0 &=-(n-1),~~ a_1 =-(n^2+3n-11),~~a_2=-\frac{1}{2}(n^3+6n^2-47n+68),\\
a_k &= -\bigg[-\binom{n-3}{k-3}+2(n-1)\binom{n-3}{k-2}+14(n-2)\binom{n-3}{k-1}+(n-1)\binom{n-3}{k}\bigg]\\
&~~~~~\text{when}~ 3\leq k\leq n-3,\\
a_{n-2}&=-(3n^2+5n-28),~~ a_{n-1}=-(n+1), ~~\text{and} ~~ a_n=1.
\end{align*}

It is easy to check that $|a_0|\leq |a_1|\leq |a_2|$ and $|a_{n-2}|\geq
|a_{n-1}|\geq |a_{n}|$ when $n\geq 6$.  When $4\leq k\leq n-3$, one can check that

\begin{align*}
&|a_k|- |a_{k-1}|\\
&= \binom{n-3}{k-4} \bigg[\frac{(2n^3+4n^2-6kn^2+4k^2n-3kn-2k^2+4)}{(k-2)(k-3)}+\bigg(\frac{7(n-2)(n-k)(n-k+1)}{(k-1)(k-2)}\bigg)\cdot\\
&~~~~~~~~~~~~~~~~~~~~~~\bigg(\frac{n-2k+2}{k-3}\bigg)+\bigg(\frac{(n-1)(n-k-1)(n-k)(n-k+1)}{(k-1)(k-2)(k-3)}\bigg)\cdot \bigg(\frac{n-2k-2}{k}\bigg)\bigg].
\end{align*}

Hence, when $4\leq k\leq n-3$, it is easy to verify that
$|a_k|\geq |a_{k-1}|$ if and only if $k\leq \frac{n-2}{2}$ and
$|a_k|\leq |a_{k-1}|$ if and only if $k\geq \frac{n+2}{2}$. Thus,
we have  $|a_0|\leq |a_1|\leq |a_2| \leq \hdots \leq
|a_{\lfloor \frac{n-2}{2} \rfloor}|$ and
$|a_{\lceil \frac{n+2}{2}-1\rceil}| \geq |a_{\lceil \frac{n+2}{2}\rceil}|
\geq \hdots \geq |a_{n-3}|\geq |a_{n-2}|$.
Hence, if $|a_t|=\max_{0\leq k\leq n-2} |a_k|$, then $\lfloor \frac{n-2}{2}
\rfloor \leq t \leq \lceil \frac{n}{2}\rceil$, completing our proof.

§.§ Peak location for the bi-star $S_{1,n-3}$

Let $S_{1,n-3}$ be a tree on $n$ vertices obtained from $P_2$ that has
the edge $\{v_1,v_2\}$ by
attaching a pendant vertex $v_0$ to $v_1$ and $(n-3)$ pendant vertices
$v_3,v_4,\hdots,v_{n-1}$ to $v_2$. Let $e_1=\{v_0,v_1\},
e_2=\{v_1,v_2\}$ and $e_i=\{v_2,v_i\}$ for $3\leq i \leq n-1$.
Since $S_{1,n-3}$ has $n-2$ pendant vertices, two
types of basis $B_1$ and $B_2$  are output by  the algorithm given by
Azimi and Sivasubramanian (see Remark <ref>).
These are

\begin{align*}
B_1&=\{e_1,e_2,\hdots,e_{n-1},f_1,f_2\}~ \text{where}~ f_1=\{v_0,v_2\},f_2=\{v_1,v_3\}~\text{and}\\
B_2&=\{e_1,e_2,\hdots,e_{n-1},f_1,f_2\}~ \text{where}~ f_1=\{v_0,v_2\},f_2=\{v_3,v_4\}.
\end{align*}

We find the eigenvalues of both $\DD_2(S_{1,n-3})[B_1,B_1]$ and

Let $B_1$ and $B_2$ be the
bases of $S_{1,n-3}$ as mentioned above. Then,

* the eigenvalues of $\DD_2(S_{1,n-3})[B_1,B_1]$ are $-1$ with multiplicity
$n-5$ and the roots of the polynomial

* the eigenvalues of $\DD_2(S_{1,n-3})[B_2,B_2]$ are $-1$ with multiplicity
$n-5$ and the roots of the polynomial

With the given labelling, we have

\begin{align*}
\DD_2(S_{1,n-3})[B_1,B_1]&=\begin{blockarray}{cccccccc}
%& e_1 & e_2 & e_3 & e_4 & \hdots & e_{n-1} & f_1 & f_2\\
& e_1 & e_2 & e_3 &  \hdots & e_{n-1} & f_1 & f_2\\
\begin{block}{c(ccccccc)}
e_1 & 1 & 2 & 3 &  \hdots & 3 & 2 & 3 \\
e_2 & 2 & 1 & 2 &  \hdots & 2 & 2 & 2 \\
e_3 & 3 & 2 & 1 &  \hdots & 2 & 3 & 2 \\
%e_4 & 3 & 2 & 2 &  \hdots & 2 & 3 & 3 \\
\vdots & \vdots & \vdots &\vdots &\ddots &\vdots &\vdots & \vdots \\
e_{n-1} & 3 & 3 & 2  &  \hdots & 1 & 3 & 3 \\
f_1 & 2 & 2 & 3 &  \hdots & 3 & 2 & 3 \\
f_2 & 3 & 2 & 2 &  \hdots & 3 & 3 & 2 \\
\end{block}
\end{blockarray}\quad \text{and}\\
\DD_2(S_{1,n-3})[B_2,B_2]&=\begin{blockarray}{ccccccccc}
%& e_1 & e_2 & e_3 & e_4 & e_5 & \hdots & e_{n-1} & f_1 & f_2\\
& e_1 & e_2 & e_3 & e_4 &  \hdots & e_{n-1} & f_1 & f_2\\
\begin{block}{c(cccccccc)}
e_1 & 1 & 2 & 3 & 3 &  \hdots & 3 & 2 & 4 \\
e_2 & 2 & 1 & 2 & 2 &  \hdots & 2 & 2 & 3 \\
e_3 & 3 & 2 & 1 & 2 &  \hdots & 2 & 3 & 2 \\
e_4 & 3 & 2 & 2 & 1 &  \hdots & 2 & 3 & 2 \\
%e_5 & 3 & 2 & 2 & 2 &  \hdots & 2 & 3 & 3 \\
\vdots & \vdots & \vdots &\vdots &\vdots &\ddots &\vdots &\vdots & \vdots \\
e_{n-1} & 3 & 2 & 2  & 2 &  \hdots & 1 & 3 & 3 \\
f_1 & 2 & 2 & 3 & 3 &  \hdots & 3 & 2 & 4 \\
f_2 & 4 & 3 & 2 & 2 &  \hdots & 3 & 4 & 2 \\
\end{block}
\end{blockarray}~.
\end{align*}

As before, let $e(i,j)$ be the $n$-dimensional column vector with its
$i$-th component $1$, its $j$-th component $-1$ and all other
components being $0$.  If $X= \{e(j,j+1):4\leq j\leq n-2\}$ and
$Y=\{e(3,4)\}\cup \{e(j,j+1):5\leq j\leq n-2\}$, then for any $\textbf{x}\in X$
and $\textbf{y}\in Y$, we have $\big(\DD_2(S_{1,n-3})[B_1,B_1]\big)\textbf{x}
=-\textbf{x}$ and $\big(\DD_2(S_{1,n-3})[B_2,B_2]\big)\textbf{y}=-\textbf{y}$.
Note that $|X|=|Y|=n-3$, and that all vectors in both $X$ and $Y$
are linearly independent.

Therefore, $-1$ is an eigenvalue of both $\DD_2(S_{1,n-3})[B_1,B_1]$ and
$\DD_2(S_{1,n-3})[B_2,B_2]$ with multiplicity at least $n-3$.

If $E_1=\{e_4,\hdots,e_{n-1}\}$, then it is easy to see that
$\Pi_3:\{e_1\}\cup \{e_2\}\cup \{e_3\}\cup E_1 \cup \{f_1\}\cup \{f_2\}$ is an
equitable partition of $\DD_2(S_{1,n-3})[B_1,B_1]$ with the quotient matrix given below.

A simple computation gives the characteristic polynomial of $Q_{\Pi_3}$ to be
By Lemma <ref>, the eigenvalues of $Q_{\Pi_3}$ are eigenvalues
of $\DD_2(S_{1,n-3})[B_1,B_1]$. Since $h_1(-1)\neq 0$, the eigenvalues of
$\DD_2(S_{1,n-3})[B_1,B_1]$ are $-1$ with multiplicity $n-5$, and the roots of $h_1(x)=0$.

If $E_2=\{e_3,e_4\}$ and $E_3=\{e_5,\hdots,e_{n-1}\}$, then it is easy to see that
$\Pi_4:\{e_1\}\cup \{e_2\}\cup E_2 \cup E_3 \cup \{f_1\}\cup \{f_2\}$ is an
equitable partition of $\DD_2(S_{1,n-3})[B_2,B_2]$ with the quotient matrix
given below.

\[
\left ( {\begin{array}{cccccc}
1 & 2 & 3 & 3(n-4) & 2 & 3\\
2 & 1 & 2 & 2(n-4) & 2 & 2\\
3 & 2 & 1 & 2(n-4) & 3 & 2\\
3 & 2 & 2 & 2(n-4)-1 & 3 & 3\\
2 & 2 & 3 & 3(n-4) & 2 & 3\\
3 & 2 & 2 & 3(n-4) & 3 & 2\\
\end{array} } \right)
\mbox{ and }
\left ( {\begin{array}{cccccc}
1 & 2 & 6 & 3(n-5) & 2 & 4\\
2 & 1 & 4 & 2(n-5) & 2 & 3\\
3 & 2 & 3 & 2(n-5) & 3 & 2\\
3 & 2 & 4 & 2(n-5)-1 & 3 & 3\\
2 & 2 & 6 & 3(n-5) & 2 & 4\\
4 & 3 & 4 & 3(n-5) & 4 & 2\\
\end{array} } \right)\]

The characteristic polynomial of $Q_{\Pi_4}$ clearly equals
(15n-34)x-(n-1).$  By Lemma <ref>, all eigenvalues of
$Q_{\Pi_4}$ are eigenvalues of $\DD_2(S_{1,n-3})[B_2,B_2]$. Since
$h_2(-1)\neq 0$, the eigenvalues of $\DD_2(S_{1,n-3})[B_2,B_2]$ are
$-1$ with multiplicity $n-5$, and the roots of $h_2(x)=0$.

For both $\DD_2(S_{1,n-3})[B_1,B_1]$ and
$\DD_2(S_{1,n-3})[B_2,B_2]$, we determine the peak location of
coefficients of their characteristic polynomial in the next result.

Let $S_{1,n-3}$ be the tree on $n$ vertices as mentioned above.

* Let $a_0,a_1,\hdots,a_n, a_{n+1}$ be the coefficients of
$\charpoly_{\DD_2(S_{1,n-3})[B_1,B_1]}(x)$  and $|a_t|=\max |a_k|$.
Then $\lfloor \frac{n-4}{2} \rfloor \leq t \leq \lceil \frac{n+4}{2}\rceil$.

* Let $b_0,b_1,\hdots,b_n,b_{n+1}$ be the coefficients of
$\charpoly_{\DD_2(S_{1,n-3})[B_2,B_2]}(x)$  and
$|b_t|=\max |b_k|$. Then $\lfloor \frac{n-4}{2} \rfloor \leq t
\leq \lceil \frac{n+4}{2}\rceil$.

Since our proofs for both parts are very similar, we give details for
the first part and only sketch details of the second part.

Proof of item 1. By Theorem <ref>,
it follows that the characteristic polynomial of
$\DD_2(S_{1,n-3})[B_1,B_1]$ is

If $a_k$ is the coefficient of $x^k$ in $h(x)$, then, we have

\begin{align*}
a_0 &=-(n-1),~~~a_1 =-(n^2+7n-23),~~~a_2=-\frac{1}{2}(n^3+14n^2-55n+30),\\
a_3 &=-\frac{1}{6}(n^4+20n^3-118n^2+91n+234),\\
a_k&=-\sum_{k=6}^{n-5} \bigg[(n-1)\binom{n-5}{k}+(13n-28)\binom{n-5}{k-1}+(45n-110)\binom{n-5}{k-2}+(54n-126)\cdot\\
&~~~\binom{n-5}{k-3}+(21n-36)\binom{n-5}{k-4}+2(n-1)\binom{n-5}{k-5}-\binom{n-5}{k-6}\bigg]~ \text{for}~ 6\leq k\leq n-5,\\
a_{n-2}&=-\frac{1}{6}(5n^3+72n^2-383n+354),~a_{n-1}=-\frac{1}{2}(3n^2+29n-41),~ a_n=-(n+3),~ a_{n+1}=1.
\end{align*}

It is easy to check when $n \geq 6$ that $|a_0|\leq |a_1|\leq |a_2|$ and
that $|a_{n-2}|\geq |a_{n-1}|\geq |a_{n}|$.  When $7\leq k\leq n-5$, it is
again easy to see that we have

\begin{align*}
\end{align*}

Hence, when $7\leq k\leq n-5$, one can check that
$|a_k|\geq |a_{k-1}|$ if and only if $k\leq \frac{n-4}{2}$ and
$|a_k|\leq |a_{k-1}|$ if and only if $k\geq \frac{n+6}{2}$. Thus, we have
$|a_0|\leq |a_1|\leq |a_2| \leq \hdots \leq |a_{\lfloor \frac{n-4}{2}
\rfloor}|$
and $|a_{\lceil \frac{n+6}{2}-1\rceil}| \geq |a_{\lceil \frac{n+6}{2}\rceil}|
\geq \hdots \geq |a_{n-2}|\geq |a_{n-1}|\geq |a_{n}|$. Hence, if
$|a_t|=\max_{0\leq k\leq n-2} |a_k|$, then $\lfloor \frac{n-4}{2} \rfloor
\leq t \leq \lceil \frac{n+4}{2}\rceil$. This completes the proof of
the first part.

Proof of item 2. By Theorem <ref>,
it follows that the characteristic polynomial of $\DD_2(S_{1,n-3})[B_2,B_2]$ is
(15n-34)x-(n-1)\big]$. As the rest of the proof is similar to the first case,
we omit its details.

§.§ Bounds on the peak location of the Path

For a matrix $M$ and index sets $\alpha$ and $\beta$, the submatrix of $M$ restricted to the rows
in  $\alpha$  and the columns in  $\beta$ is denoted by
When $\alpha=\beta$, we use the notation $M[\alpha]$ to denote the principal
submatrix $M[\alpha,\alpha]$ of $M$.
We also use the notation $M(\alpha|\beta)$ to denote the submatrix of $M$
obtained by deleting the rows corresponding to $\alpha$  and the
columns corresponding to $\beta$. We recall some results
from [3].

Suppose $T$ is a  a tree of order $n$ with $p$ leaves.
Let $B$ be a basis of $\DD_2(T)$ as defined in Remark
<ref> with
$B =\{e_1,e_2,\ldots,e_{n-1},f_1,\ldots,f_{n-p}\}$
and let $\v$ be the column vector defined as
$v_e_i = 1- ∑_e_i∈f_j' (|B_j|-1)$ and
$v_f_i = |B_i|-1,  where $f_i'\in B_i$.$
Then $^t=̌1$ and $_2[B,B]=̌(n-1)$.
\end{lemma}

\begin{remark}
\label{remark:v-for-path}
When $T=P_n$, a path on $n$ vertices, the vector $\v$
defined in Lemma \ref{lem:steiner-v} is given by
v_{f_j} =1$ for $1\leq j\leq n-p$, and for $1\leq i\leq n-1$, $v_{e_i}=\begin{cases}
0 & \text{if $e_i$ is a pendant edge},\\
-1 & \text{otherwise;}
\end{cases}
\end{remark}

\begin{remark}
\label{remark: basis Pn}
Let $P_n$ be the path on $n$ vertices with edges $e_i=\{i,i+1\}$
for $i=1,\ldots, n-1$. Let  $B=(e_1,f_1,e_2,f_2,\ldots,
e_{n-2},f_{n-2},e_{n-1})$ be the ordered basis for the
row space of $\DD_2(P_n)$ where  $f_j=\{j,j+2\}$,
for $j=1,\ldots, n-2$.  We follow this particular ordering
of $B$ to order the rows and columns of $\DD_2(P_n)[B,B]$.
\end{remark}

We denote by $\DPn$ the matrix
$\DD_2(P_n)[B, B]$, that is, $\DPn:=\DD_2(P_n)[B, B]$.

\begin{remark}\label{remark:laplacian-like}
By the definition of the Laplacian-type matrix outlined
in \cite[Page 77]{aliazimi-siva-steiner-2-dist}, we define the
matrix $L$ whose rows and columns are indexed by the elements of
$B$ with entries as follows:
the entries $L(e_i,e_j)$ and $L(f_i,f_j)$ are zero if $i\neq j$.
Further, define
L(x,x) =\begin{cases}
2 & \text{if  $x\in B\setminus\{e_1,e_{n-1}\}$},\\
1 & \text{if $x\in \{e_1,e_{n-1}\}$},
\end{cases}, \quad \text{and} \quad L(e_i,f_k) = \begin{cases}
-1 & \text{if $i\in\{k-1,k\}$},\\
0 & \text{otherwise}.
\end{cases}$$
Note that $L$ is a symmetric tridiagonal matrix
1  & -1 & 0  & 0  & \cdots  & 0    \\
-1 & 2  & -1 & 0  & \cdots  & 0    \\
0  & -1 & 2  & -1 & \cdots  & 0    \\
\vdots  & \vdots   &\ddots  & \ddots  &\ddots   & \vdots    \\
0  & 0  & \cdots & -1  & 2  & -1 \\
0  & 0  &    \cdots  & 0   & -1 & 1
\end{array}\right).
\end{remark}

The following result is a special case of
\cite[Theorem 1 and  2]{aliazimi-siva-steiner-2-dist} and provides
the inverse of  $\DPn$.

\begin{theorem}\label{th:det-inv-st-path}
Let $P_n$ is the path on $n$ vertices  and
let $B=(e_1,f_1,e_2,f_2,\ldots,e_{n-2},f_{n-2},e_{n-1})$
be the ordered basis  of $\DD_2(P_n)$ as defined in Remark
\ref{remark: basis Pn}.  Then  $\det\DPn = (n-1)$ and
$ \DPn^{-1} = -L +\frac{1}{n-1} \v \v^t.$
\end{theorem}

We need the following result (see  Horn and Johnson \cite[Page 18]
{horn-johnson-matrix-analysis}), about the blocks in the inverse of a
partitioned nonsingular matrix $M$.
\begin{lemma}\label{lem:partition-inverse}
Let $M$ be a nonsingular matrix and $\alpha$ be a subset of the
index set of $M$'s rows and columns.  Let $\alpha^c$ denote
the complement set of $\alpha$ and suppose $M^{-1}[\alpha]$
and $M[\alpha^c]$ are invertible. Then,
$$\left(M^{-1}[\alpha]\right)^{-1}= M[\alpha]-M\left[\alpha, \alpha^c\right]M\left[\alpha^c\right]^{-1} M\left[\alpha^c, \alpha\right].$$
\end{lemma}

In our next result, we find the principal minors of $\DPn$ of size $r-1$.

\begin{theorem}\label{th:principal-monors}
Let $P_n$ be a path on $n\geq 3$ vertices and $\DD_2(P_n)$ be
its $2$-Steiner distance matrix. If $B$ is a basis of $\DD_2(P_n)$'s row space and $\alpha \in B$, then
\det \DPn(\alpha | \alpha) =
\begin{cases}
-(n-1) & \text{ if $\alpha$ is a pendant edge in $P_n$},\\
-(2n-3) & \text{otherwise}.
\end{cases}
\end{theorem}

\begin{proof}
Our proof is by induction on $n$. Let $B=\{e_1,f_1,e_2\}$ be a
basis of $\DD_2(P_3)$. Note that $\DP3=\left(\begin{array}{rrr}
1 & 2 & 2 \\
2 & 2 & 2 \\
2 & 2 & 1
\end{array}\right)$. Clearly $\DP3(f_1 | f_1)=-3$ and
$\DP3(e_i | e_i)=-2$ when $i=1,2$. Hence, the result holds
when $n=3$. Further, note that
$\DP4 = \left(\begin{array}{rrrrr}
1 & 2 & 2 & 3 & 3 \\
2 & 2 & 2 & 3 & 3 \\
2 & 2 & 1 & 2 & 2 \\
3 & 3 & 2 & 2 & 2 \\
3 & 3 & 2 & 2 & 1
\end{array}\right).$
One can verify that $\det \DP4(e_1|e_1) =\det \DP4(e_3|e_3)=-3$
and that $\det\DP4(\alpha|\alpha)=-5$ for $\alpha\in \{f_1,e_2,f_2\}$.
Hence, our result is also true when $n=4$.

Assume that the statement is true for all path on $k$ vertices, where $k\leq n-1$.
By $P_n$ we mean the  path on $n>4$ vertices with  $e_i=\{i,i+1\}$
for $i=1,\ldots, n-1$ and let $f_j=\{j,j+2\}$ for $j=1,\ldots, n-2$.
Let $B_n=(e_1,f_1,e_2,f_2,\ldots,e_{n-2},f_{n-2},e_{n-1})$ be an
ordered basis of $\DD_2(P_n)$'s row space and
$\DPn= \DD_2(P_n)[B_n,B_n]$.
Further note that $\dST(e_1,b_i) =\dST(f_1,b_i)$ for each
$b_i\in B_n\setminus \{e_1\}$ and  $\dST(f_1,b_i) =\dST(e_2,b_i)$
for each $b_i\in B_n\setminus \{e_1,f_1\}$.
For $x\in B_n$, we write $r_x$ (respectively $c_x$) to denote
the row (respectively column)  corresponding to $x$. By
performing the elementary row operations
$r_{f_1}=r_{f_1}-r_{e_2}$ and $c_{f_1}=c_{f_1}-c_{e_2}$
on the matrix $\DPn(e_1|e_1)$ we get
\left( \begin{array}{r|c}
-1 & \1^t\\ \hline
\1 & \DP{n-1}
\end{array}\right),
where $\DP{n-1}=\DD_2(P_{n-1})[B_{n-1},B_{n-1}]$.  By
Lemma \ref{lem:steiner-v}, there exist $v$ such that
$\1^tv=1$ and $\DP{n-1}v=(n-2)\1$.   By Schur complements and the
determinantal formula \cite[sec. 0.8.5]{horn-johnson-matrix-analysis}
and Theorem \ref{th:det-inv-st-path}, we get
\begin{align*}
\det \DPn(e_1|e_1) = \det(\DP{n-1}) \left(-1- \1^t \DP{n-1}^{-1}\1\right) = (n-2) \left(-1-  \frac{\1^t v}{n-2}\right) =-(n-1).
\end{align*}

Analogously, we have $ \det \DPn(e_{n-1}|e_{n-1}) =-(n-1)$.
Let $\alpha\in \{f_1,e_{2},\ldots, e_{n-2}, f_{n-2}\}$. Since $n>4$,
without loss of generality, we may assume that $\{e_1,f_1,e_2\}
\subset \alpha^c$. By performing the row operations
$r_{f_1}=r_{f_1}-r_{e_2}$ and $c_{f_1}=c_{f_1}-c_{e_2}$ on
the matrix $\DPn(\alpha|\alpha)$ we get
\begin{align*}
\DPn(\alpha|\alpha) \sim   \left(\begin{array}{rr|c}
-2 & 1 & \1^t  \\
1 & -1  & \0^t \\  \hline
\1 & \0 & \DP{n-1}(\alpha|\alpha)
\end{array}\right).
\end{align*}

Again, by applying Schur complements and the determinantal formula,
we get
\begin{equation}
\det \DPn(\alpha|\alpha)  =\det  \DP{n-1}(\alpha|\alpha)  \det \left[
\left(\begin{array}{cc}
-2 & 1 \\
1 & -1
\end{array}\right)
- X^t  \DP{n-1}(\alpha|\alpha)^{-1} X
\right], \label{eq:schur-complement-minor}
\end{equation}
where $X= \begin{pmatrix}	\1 & \0 \end{pmatrix} $.  By Lemma \ref{lem:partition-inverse}, we get
\begin{equation}\label{eq:inverse-D-partition}
\DP{n-1}[\alpha^c]^{-1} =  \DP{n-1}^{-1}[\alpha^c] - \DP{n-1}^{-1}[\alpha^c,\alpha] \left(\DP{n-1}^{-1}[\alpha]\right)^{-1}\DP{n-1}^{-1}[\alpha,\alpha^c].
\end{equation}
Let $L$ be the Laplacian-like matrix for the tree $P_{n-1}$, as described in Remark \ref{remark:laplacian-like}. Suppose $v[\alpha] =t$. Clearly $t\in\{-1,1\}$. By Theorem \ref{th:det-inv-st-path}, we get
\begin{equation}\label{eq:m11}
\DP{n-1}^{-1}[\alpha] = -L[\alpha] + \frac{1}{n-2} v[\alpha](v[\alpha])^t = -2+\frac{1}{n-2} =-  \frac{2n-5}{n-2}.
\end{equation}
Note that $\1^tv[\alpha^c]\1 +v[\alpha] =1$. Since $L\1=\0$, it follows that $\1^tL[\alpha^c]\1  = 2$. Hence, by Theorem \ref{th:det-inv-st-path}, we get
\begin{equation} \label{eq:m12}
X^t  \DP{n-1}^{-1}[\alpha^c] X =  - \begin{pmatrix}
\1^t L[\alpha^c]\1 & 0 \\
0 & 0
\end{pmatrix} +
\frac{1}{n-2}
\begin{pmatrix}
\1^t v[\alpha^c] (v[\alpha^c])^t\1 & 0 \\
0 & 0
\end{pmatrix}  = \begin{pmatrix}
-2 + \dfrac{(1-t)^2}{n-2} & 0\\0&0
\end{pmatrix}.
\end{equation}
Further, note that
\begin{equation} \label{eq:m13}
X^t  \DP{n-1}^{-1}[\alpha^c,\alpha]  = X^t
\left[ -L[\alpha^c,\alpha] + \frac{1}{n-2} v[\alpha^c](v[\alpha])^t\right]
= \begin{pmatrix}
2 + \dfrac{t(1-t)}{n-2} \\0
\end{pmatrix}.
\end{equation}
\begin{equation} \label{eq:m14}
\DP{n-1}^{-1}[\alpha,\alpha^c] X =
\left[ -L[\alpha] + \frac{1}{n-2} v[\alpha](v[\alpha])^t\right]X
= \begin{pmatrix}
2 + \dfrac{t(1-t)}{n-2}  & 0
\end{pmatrix}.
\end{equation}
By \eqref{eq:inverse-D-partition}, \eqref{eq:m11}, \eqref{eq:m12}, \eqref{eq:m13}, and \eqref{eq:m14}, we get
\begin{equation*}
X^t  \DP{n-1}(\alpha|\alpha)^{-1} X = \begin{pmatrix}
-2 + \dfrac{(1-t)^2}{n-2} & 0\\0&0
\end{pmatrix} +\frac{n-2}{2n-5} \begin{pmatrix}
\left[2 + \dfrac{t(1-t)}{n-2} \right]^2 & 0\\0&0
\end{pmatrix} .
\end{equation*}
On simplification we get
\begin{equation} \label{eq:m15}
X^t  \DP{n-1}(\alpha|\alpha)^{-1} X =  \begin{pmatrix}
\frac{2}{2n-5}+f(t)& 0\\0&0
\end{pmatrix},
\end{equation}
where   $f(t) = \frac{(1-t)^2}{n-2}+\frac{4t(1-t)}{2n-5}+\frac{t^2(1-t)^2}{(n-2)(2n-5)}
$. It is easy to note that $f(\pm 1)=0$. Hence, it follows from \eqref{eq:m15} that
\begin{equation} \label{eq:m16}
X^t  \DP{n-1}(\alpha|\alpha)^{-1} X  = \begin{pmatrix}
\frac{2}{2n-5}& 0\\0&0
\end{pmatrix}.
\end{equation}
By \eqref{eq:schur-complement-minor} and \eqref{eq:m16} we get
\det \DPn(\alpha|\alpha)  =  \frac{2n-3}{2n-5}\ \det \DP{n-1}(\alpha|\alpha)  .
Thus, the result follows by induction and our proof
is complete.
\end{proof}

We next present our upper bound on the peak location for coefficients
in the characteristic polynomial of
$\DPn=\DD_2(P_n)[B,B]$, where the basis $B$ is defined as in Remark \ref{remark: basis Pn}.   .

\begin{theorem}
\label{th: peak-steiner-path}
Let $P_n$ be a path on $n> 2$ vertices and $\charpoly_{\DPn}(x) =
\sum_{i=0}^{2n-3}a_ix^i$.  If $|a_\ell| = \max\{|a_0|,|a_1|, \ldots, |a_{2n-4}|\}$, then $\ell \leq \left\lfloor\dfrac{7n}{5}\right\rfloor$.
\end{theorem}

\begin{proof}
To prove the result we will use Lemma 3.2(1) of[2]. Since $\det (\DPn) = (n-1)$, we have $|a_0| = n-1$. Furthermore, by Theorem \ref{th:principal-monors}, the sum of all principal minors of $\det \DD_2(P_n)[B,B]$ of size $2n-4$ is given by
-(2n-5)(2n-3) -2(n-1) = -(4n^2-14n+13).
It follows that $|a_1|= 4n^2-14n+13$.  Now note that
\dfrac{(2n-3)-j}{(2n-3)(j+1)} \dfrac{4n^2-14n+13}{n-1} <1  \iff  j > \dfrac{(2n-3)(4n^2-15n+14)}{3(2n-3)(n-2)+2(n-1)} =f(n)
Suppose $g(n) = \frac{7n}{5}$. Note that $g'(n) - f'(n) > 0$ for $n > 2$. Hence, by \cite[Lemma 3.2(1)]{Abiad-Brimkov-Hayat-Khramova-Koolen-dist-char-poly}, it follows that $\ell \leq  \left\lfloor\dfrac{7n}{5}\right\rfloor$.
\end{proof}

Note that Theorem \ref{th: peak-steiner-path} only provides an
upper bound for the peak location of the unimodal sequence
${|a_0|,\ldots, |a_{2n-4}|}$ associated to a path $P_n$. One can
use the approach mentioned in
\cite[Lemma 3.2(2)]{Abiad-Brimkov-Hayat-Khramova-Koolen-dist-char-poly}
to get a lower bound on the peak location.  However, to use
\cite[Lemma 3.2(2)]{Abiad-Brimkov-Hayat-Khramova-Koolen-dist-char-poly},
a suitable estimate of $a_{2n-4}$ and $a_{2n-5}$ is required.
In the case of $P_n$, even if $a_{2n-4}$ and $a_{2n-5}$ are
known exactly,
\cite[Lemma 3.2(2)]{Abiad-Brimkov-Hayat-Khramova-Koolen-dist-char-poly}
does not seem to provide a lower bound on the peak location, and
so we do not discuss this aspect in this paper.  Using
SageMath [15],  when  $5<n<15$, the actual peak location
for $P_n$ seems to be $n-1$.  We record this as a conjecture.

\begin{conjecture}
For a path $P_n$ on $n> 5$ vertices, if $\charpoly_{\DPn}(x) = \sum_{i=0}^{2n-3}a_ix^i$ and $|a_\ell| = \max\{|a_0|,|a_1|, \ldots, |a_{2n-4}|\}$, then $\ell  =n-1$.
\end{conjecture}

We further note that $|a_{2n-4}|$ is the trace of $\DPn$, and
hence $|a_{2n-4}|=2(n-2) +(n-1) =3n-5$.  One needs to find principal
minors of a suitable size to estimate $a_{2n-5}$. Again, by looking
at the data from SageMath, we make the following conjecture
that provides an estimate for $a_{2n-5}$.

\begin{conjecture}
For a path $P_n$ on $n> 5$ vertices, if $\charpoly_{\DPn}(x) = \sum_{i=0}^{2n-3}a_ix^i$, then
$a_{2n-5}  =- \frac{1}{6} (n - 1) (n - 2) (2n^2 + 6n - 15).$
\end{conjecture}

%section 2

% Bibliography
\bibliographystyle{abbrv}
\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{AAB{\etalchar{+}}18}

[1]
G.~Aalipour, A.~Abiad, Z.~Berikkyzy, L.~Hogben, F.~H.~J. Kenter, J.~C.-H. Lin,
and M~Tait.
\newblock Proof of a {C}onjecture of {G}raham and {L}ov{\'a}sz concerning
{U}nimodality of {C}oefficients of the {D}istance {C}haracteristic
{P}olynomial of a {T}ree.
\newblock {\em Electronic Journal of Linear Algebra}, 34:373--380, 2018.

[2]
A. Abiad, B. Brimkov, S. Hayat, A.~P. Khramova, and J.~H. Koolen.
\newblock Extending a conjecture of {G}raham and {L}ov{\'a}sz on the distance
characteristic polynomial.
\newblock {\em Linear Algebra and its Applications}, To
appear:https://doi.org/10.1016/j.laa.2023.03.027, 2023.

[3]
A. Azimi and S.~Sivasubramanian.
\newblock The $2$-Steiner distance matrix of a tree.
\newblock {\em Linear Algebra and its Applications}, 655:65--86, 2022.

[4]
R.~B. Bapat and S.~Sivasubramanian.
\newblock Smith {N}ormal {F}orm of a distance matrix inspired by the four-point
\newblock {\em Linear Algebra and its Applications}, 603:301--312, 2020.

[5]
A.~E. Brouwers and W.~H. Haemers.
\newblock {\em {Spectra of Graphs}}.
\newblock Universitext, Springer Verlag, 2012.

[6]
P. Br{\"a}nd{\'e}n.
\newblock Unimodality, {L}og-concavity, {R}eal-rootedness and {B}eyond.
\newblock In M~Bona, editor, {\em Handbook of Enumerative Combinatorics},
chapter~7. Chapman \& Hall \/ CRC Press, 2015.

[7]
P. Buneman.
\newblock A {N}ote on the {M}etric {P}roperties of {T}rees.
\newblock {\em Journal of Combinatorial Theory Series B}, 17:48--50, 1974.

[8]
K.~L. Collins.
\newblock On a conjecture of {G}raham and {L}ov{\'a}sz about distance matrices.
\newblock {\em Discrete Applied Mathematics}, 25:27--35, 1989.

[9]
M.~Deza and M.~Laurent.
\newblock {\em Geometry of Cuts and Metrics}.
\newblock Springer Verlag, volume 15 edition, 1997.

[10]
M.~Edelberg, M.~R. Garey, and R.~L Graham.
\newblock On the distance matrix of a tree.
\newblock {\em Discrete Mathematics}, 14:23--39, 1976.

[11]
R.~L. Graham and L.~Lovasz.
\newblock Distance matrix polynomials of trees.
\newblock {\em Advances in Mathematics}, 29(1):60--88, 1978.

[12]
R.~A. Horn and C.~R. Johnson.
\newblock {\em Matrix Analysis}.
\newblock Cambridge University Press, 2012.

[13] A. Prekopa.  Logarithmic concave measures and related topics. In: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Statistics, University of California Press, 513–525, 1971.

[14] R.P. Stanley. Log-concave and unimodal sequences in algebra, combinatorics, and geometry. Annals of the New York Academy of Sciences, 576, 500–535, 1989.

[15]
The~Sage Developers.
\newblock {\em SageMath, the {S}age {M}athematics {S}oftware {S}ystem
({V}ersion 9.4)}, 2021.
\newblock {\tt http://www.sagemath.org}.

\end{thebibliography}

%	\bibliography{bibdatabase}

\end{document}


# Correlate-and-Excite: Real-Time Stereo Matching viaGuided Cost Volume
Excitation

Antyanta Bangunharcana1, Jae Won Cho2, Seokju Lee2, In So Kweon2, Kyung-Soo
Kim1, Soohyun Kim1 1A. Bangunharcana, K-S. Kim, and S. Kim are with
Mechatronics, Systems and Control Laboratory, KAIST, Daejeon, 34141, Republic
of Korea {antabangun, kyungsoo<EMAIL_ADDRESS>W. Cho, S. Lee, I. S.
Kweon are with the Robotics and Computer Vision Laboratory, KAIST, Daejeon,
34141, Republic of Korea {chojw, seokju91<EMAIL_ADDRESS>
###### Abstract

Volumetric deep learning approach towards stereo matching aggregates a cost
volume computed from input left and right images using 3D convolutions. Recent
works showed that utilization of extracted image features and a spatially
varying cost volume aggregation complements 3D convolutions. However, existing
methods with spatially varying operations are complex, cost considerable
computation time, and cause memory consumption to increase. In this work, we
construct Guided Cost volume Excitation (GCE) and show that simple channel
excitation of cost volume guided by image can improve performance
considerably. Moreover, we propose a novel method of using top-$k$ selection
prior to soft-argmin disparity regression for computing the final disparity
estimate. Combining our novel contributions, we present an end-to-end network
that we call Correlate-and-Excite (CoEx). Extensive experiments of our model
on the SceneFlow, KITTI 2012, and KITTI 2015 datasets demonstrate the
effectiveness and efficiency of our model and show that our model outperforms
other speed-based algorithms while also being competitive to other state-of-
the-art algorithms. Codes will be made available at
https://github.com/antabangun/coex.

##  I INTRODUCTION

Stereo matching aims to estimate depth from a pair of images [1, 2] and is an
essential task in the field of robotics, autonomous driving, and computer
vision. This task has various challenging issues such as occlusions,
textureless areas, areas with repeating textures, thin or small objects, etc.
With the advancements of deep learning algorithms, the accuracy of stereo
matching algorithms has improved significantly; however, many accurate state-
of-the-art models do not have fast processing speed for real-time applications
[3, 4, 5, 6, 7]. Algorithms that focus on fast computations exist but often
sacrifice accuracy to gain this advantage which may be the main reason why
stereo cameras are not utilized more frequently in applications [8, 9] such as
autonomous driving where fast computation is essential. If the efficiency of
stereo matching algorithms can be improved from the current standard, stereo
camera based depth perception can be an alternative to the expensive LiDAR
sensors that are currently used in many self-driving algorithms [10].

Figure 1: D1-all% error on KITTI stereo 2015 leaderboard vs. frame rate. Our
proposed method CoEx, shown in the red star, achieve competitive performance
compared to other state-of-the-art models while also being real-time. Figure
2: An overall end-to-end stereo matching model with an hourglass architecture
of cost aggregation. GCE modules are inserted in between the 3D convolutions
to utilize image feature map. Operation between image and cost volume features
are broadcasted operation. Top-$k$ regression is used to compute the final
disparity estimate. This model can be extended to other volumetric CNN-based
architecture and the proposed modules can be incorporated in the same manner.

Recent series of learning-based stereo matching algorithms [11, 12, 5] use
left and right input images to construct a cost volume by computing the cross-
correlation or concatenation of the features between from the two images. The
correlation based approach reduces the input images’ feature vectors into
cosine similarity values, giving a model with lower memory usage and faster
runtime. However, this reduces the representation power of the neural network
and often results in poor performance compared to the concatenation based cost
volume.

In a volumetric approach, the computed cost volume is aggregated using 3D
convolutional layers [13]. However, deep stacks of 3D convolutions are
computationally expensive and memory inefficient [14]. Recent works have tried
to improve the efficiency of the cost aggregation step using spatially varying
aggregation [5, 3, 15]. While these works show improvements in accuracy, there
is a significant increase in computational cost and memory consumption as well
as additional complexity in the implementation of the proposed approaches.

We propose an efficient and straightforward way of improving cost aggregation
by utilizing extracted image features using attention based approaches that
have been shown to improve image classification networks [16, 17]. Given a
cost volume feature map, Guided Cost volume Excitation (GCE) excites the cost
volume channels with weights computed from the the reference image features.
The computed weights are shared across the disparity channel, so the operation
is lightweight and easy to implement. This module lets the 3D neural network
layers to extract geometric features from the cost volume and the image-guided
weights to excite the relevant features. We empirically show that this
operation improves performance significantly without any significant
additional computational cost. We show that this module allows correlation
based cost volume to utilize image information and performs at a similar
accuracy with the concatenation based model, allowing us to construct a fast
and accurate correlation based stereo matching model.

In volumetric based stereo matching models, soft-argmin is the standard
approach to compute the final disparity estimates, and few works have been
done to improve the soft-argmin regression. The soft-argmin function computes
the expected value from a disparity distribution at each pixel obtained from
the cost volume aggregation. However, in many cases, the disparity
distribution can have multiple peaks _e.g_., on the edge boundaries or even an
almost uniform distribution _e.g_., textureless region. Due to this reason,
taking the expected value when the distribution is not unimodal may not be the
best choice to estimate the disparity. Instead, we propose to use only the
top-$k$ values from the distribution to compute the disparity map. We show
that this simple yet novel idea gives more accurate depth estimates and can be
applied to any volumetric based model.

With our proposed ideas, we construct an end-to-end real-time stereo matching
network that we call CoEx (Correlate-and-Excite). We sum up our contributions
and list them as follows:

  1. 1.

We present Guided Cost volume Excitation (GCE) to utilize extracted feature
map from image as guidance for cost aggregation to improve performance.

  2. 2.

We propose a new method of disparity regression in place of soft-
argmax(argmin) to compute disparity from the top-$k$ matching cost values and
show that it reliably improves performance.

  3. 3.

Through these methods, we build a real-time stereo matching network CoEx, that
outperforms other speed-oriented methods and shows its competitiveness when
compared to state-of-the-art models.

##  II Related Works

Recent works have focused on using deep Convolutional Neural Networks (CNN) to
improve stereo matching performance. In [18, 19, 20], CNNs are used to obtain
feature representation for left and right images to be used for feature
matching, but cost aggregation is still done using traditional means. DispNet
[12] extended the idea to train an end-to-end deep model to predict depth from
stereo images by introducing a correlation layer to construct the cost volume.
Following this, many more end-to-end works have been proposed which can mostly
be divided into either direct regression or volumetric approach [21]. Direct
regression based methods use 2D convolutions on the cost volume to directly
compute the disparity map [22, 23, 24]. On the other hand, volumetric based
methods use 3D convolutions to aggregate the cost volume by taking into
account the geometric constraints [11, 13, 14, 21] and stacking 3D
convolutions in an hourglass architecture.

Recently, more works have focused on improving the efficiency of 3D
convolutions in the aggregation step. Two notable works GANet [5] and CSPN [3]
use spatially dependent filters to aggregate cost. These methods have achieved
a higher accuracy using spatially dependent 3D aggregation but at the cost of
a higher computation time. Inspired by the strengths and drawbacks of these
approaches, we base our model on spatially dependent 3D operation but focus on
speed and efficiency. On the other hand, StereoNet [25] focused on building a
real-time stereo matching model, and like many others, do so by sacrificing
its accuracy. Recently, the accuracy of works [26, 27] on real-time stereo
matching models are getting closer to the best performing models.

The volumetric based approaches mentioned above outputs a distribution of
matching cost values at each disparity level for every pixel. The final
disparity estimates are then computed by taking the expected value of the
distribution using a soft-argmin operation. As a result, the network is only
indirectly trained to produce a disparity distribution and can fail in
ambiguous regions. There have been few works improving the soft-argmin
disparity regression. Recent studies AcfNet [28] and CDN [29] train the
network to produce better unimodal distribution by introducing novel loss
functions. This work presents a new method that builds upon the soft-argmin
operation itself and improves the overall disparity regression.

##  III Method

A deep learning based end-to-end stereo matching network consists of matching
cost computation, cost aggregation, and disparity regression. We present a
novel GCE and top-$k$ soft-argmin disparity regression module that can be
integrated into volumetric based baseline stereo approaches, both without
adding significant computation overhead to the baseline stereo matching model.
A real-time end-to-end stereo model is built using the proposed modules, shown
in Fig. 2, that achieves competitive performance to the state-of-the-art. We
describe each of the components in detail in the following subsections.

###  III-A Matching cost computation

Given a left and right input stereo image pair $3\times H\times W$, feature
maps are extracted from both of them using a shared feature extraction module.
We use MobileNetV2 [30] as our backbone feature extractor for its lightweight
property and build a U-Net [31] style upsampling module with long skip
connections at each scale level. From this feature extraction module, features
at each scale are extracted for use later as a guiding signal for spatially
varying cost aggregations. To construct the cost volume, feature maps
extracted at the $1/4$ scale of the left and right image are used with
correlation layer [12] to output a $D/4\times H/4\times W/4$ cost volume,
where $D=192$ is the maximum disparity set for our network.

###  III-B Guided Cost volume Excitation (GCE)

3D convolutions are used in modern architectures to aggregate the constructed
cost volume to allow the neural network to capture geometric representation
from the data. Recent works [32, 5] have used spatially varying modules to
complement 3D convolutions and lead to better performance. Specifically,
weights are computed from the reference image feature map to aggregate the 3D
feature representation computed from the cost volume. The modules compute
weights at each location for each pixel of interest and its surrounding
neighbors to allow for neighborhood aggregation in a spatially dependent
manner.

We argue that the 3D convolutions in a volumetric cost aggregation already
capture neighborhood information. A spatially varying update of the cost
volume feature map without neighborhood aggregation is sufficient and is
significantly more efficient. To formulate it, for a cost volume with $c$
feature channels, we pass an image feature map at the same scale into a
guidance sub-network to output $c$ weights for each pixel. With this
formulation, the 3D convolutions capture geometric information from the cost
volume, and the guidance weights excite the relevant geometric features. At
scale $(s)$ of the cost volume:

$\begin{split}\alpha=\sigma(F^{2D}(I^{(s)}))\\\ C_{o}^{(s)}=\alpha\times
C_{i}^{(s)},\end{split}$ (1)

where $F^{2D}$ is implemented using 2D point-wise convolution, with $\sigma$
being the sigmoid function. The guidance weights are shared across the
disparity dimension, and the multiplication in (1) is a broadcasted
multiplication. This flow is shown on the bottom left of Fig. 2. Since this
module involves excitation of cost volume features using weights computed from
the reference image feature map as guidance, we call this module Guided Cost
volume Excitation (GCE). This module is extremely simple and straightforward,
with only a few operations added to the overall network; however, we show in
Sec. IV-D1 that adding GCE module can improve the accuracy of our model
significantly. In our CoEx model, the cost aggregation architecture follows
GC-Net [13], with an hourglass architecture of 3D convolutions but with a
reduced number of channels and network depth to reduce computational cost. The
proposed GCE module is then added at every scale of the cost volume ( Fig. 2).
The overall cost aggregation module with GCE is detailed in Table VI. The
module outputs a 4D cost volume at $1/4$ of the original image resolution.

###  III-C Top-$k$ disparity regression

The 4D cost volume produced in the previous steps gives us matching confidence
values for each disparity level for every pixel, which can be transformed into
a probability distribution by taking a Softmax across the disparity values. In
previous works, the soft-argmax operation is used to compute disparity by
taking the expected value over this distribution [13]:

$\hat{d}=\sum_{d=0}^{D}d\times Softmax(c_{d})$ (2)

where $d$ is a predetermined set of disparity indices.

A disparity distribution where there is only a single peak may give an
adequate estimate for disparity predictions. However, in some instances, there
can be multiple peaks or even a relatively uniform distribution. In these
cases, the expected value of the matching cost distribution can diverge
significantly from the actual ground truth value.

To alleviate this issue, instead of taking the expected value of the whole
distribution, we use only the top-$k$ values of the aggregated cost volume at
every pixel. We call this regression strategy top-$k$ soft-argmax(argmin)
disparity regression. Specifically, at every pixel, we use the top-$k$ weights
to compute the expected disparity value.

When $k$ equals the number of disparity of interest $D$, the top-$k$
regression is simply a soft-argmax operation [13]. When $D>k>1$, only the
top-$k$ values in each pixel are used to compute the estimated disparity. This
is done by masking the top-$k$ values and performing softmax on these values
to normalize them so that weights that sum up to 1 can be obtained. These
weights are then multiplied with their corresponding disparity indices, while
the remaining values are masked out. The sum of the values are the weighted
average of the top-$k$ disparity candidates. This operation can be seen as
similar to $k$-max pooling [33]. In the instance where $k$ equals $1$, the
top-$k$ regression becomes an argmax, since the weight of the maximum index
becomes a constant at $1$. When this is the case, the operation is not
trainable, and is why previous works resorted to using soft-argmax. Though
simple, we show through our experiments the effectiveness of the top-$k$ soft-
argmax regression.

Using the top-$k$ regression to compute the disparity map at the full
resolution requires a large amount of additional computation time, as shown in
Sec. IV-D. To mitigate this, we design our model to compute the disparity
regression at $1/4$ of the input image resolution. Finally, the output
disparity prediction is upsampled to the original input image resolution.
Following the footsteps of [34], the final disparity estimate at each pixel in
the upsampled resolution is obtained with a weighted average of a $3\times 3$
“superpixel” surrounding it. Another CNN branch predicts the weights for each
superpixel.

We train the network in a fully supervised end-to-end manner using
$\textit{smooth}_{L1}$ loss function. Our final loss function is as follows:

$\mathcal{L}(d_{GT},\hat{d})=\frac{1}{N}\sum_{i=1}^{N}\textit{smooth}_{L_{1}}(d_{GT,i}-\hat{d}_{i}),$
(3)

given,

$\textit{smooth}_{L_{1}}(x)=\left\\{\begin{tabular}[]{ll}$0.5x^{2}$,&{if}
$|x|<1$\\\ $|x|-0.5$,&{otherwise}\end{tabular},\right.\\\ $ (4)

where, $N$ is the number of labeled pixels, $d_{GT}$ and $\hat{d}$ is the
ground truth and predicted disparity respectively.

##  IV Experiments

Methods Scene- KITTI Flow 2012 2015 Runtime EPE 3px(%) D1(%) ($ms$) Accuracy
GC-Net [13] 2.51 2.30 2.87 900 CRL [22] 1.32 – 2.67 470 SegStereo [23] 1.45
2.03 2.25 600 PSMNet [11] 1.09 1.89 2.32 410 PDS-Net [14] 1.12 2.53 2.58 500
GANet-deep[5] 0.84 1.60 1.81 1,800 CSPN [3] 0.78 – 1.74 1,000 HD3S [4] 0.78
1.80 2.02 140 CSN [7] 0.65 – 2.00 600 CDN [29] 0.70 – 1.92 400 LEAStereo [21]
0.78 1.45 1.65 300 Speed DispNetCorr [12] 1.68 4.65 4.34 60 DeepPrunerFast
[26] 0.97 – 2.59 62 StereoNet [25] 1.101 6.02 4.83 15 AANet [27] 0.87 2.42
2.55 62 AANet+ [27] 0.72 2.04 2.03 60 CoEx (Ours) 0.69 1.93 2.13 27

TABLE I: Comparison with other state-of-the-arts models. Bold: Best,
Underscore: Second best.

In this section, we explain in detail the implementation details and training
of our Correlate-and-Excite (CoEx) network, show through extensive experiments
and ablations the effectiveness of our approach, and include detailed
discussions on our method.

###  IV-A Datasets and Evaluation metrics

To test the effectiveness of our approach CoEx, we conduct experiments and
evaluations on the following datasets: SceneFlow [12], KITTI Stereo 2012 [35],
and KITTI Stereo 2015 [36].

SceneFlow is a synthetic dataset consisting of 35,454 training images and
4,370 testing images. The disparity range starts from 1 to 468, with all
images having a size of $W=960$, $H=540$. We use the ‘finalpass’ version of
the dataset. Only pixels with disparity values lower than our maximum
disparity of 192 are used for training and evaluation. The end-point-error
(EPE), which is the average difference between the predicted and ground truth,
is used as a reporting metric.

KITTI 2012 and 2015 datasets are real-world datasets with sparse ground truth
obtained from a LiDAR sensor. We divide the training data into 90% training
and 10% validation set. KITTI 2012 uses ‘Out-All’, the percentage of erroneous
pixels in total for an error threshold of 3 pixels, for its metric. For KITTI
2015, we show the ‘D1-all’ metric reported on the leaderboard, which is the
percentage of all labeled pixels’ stereo disparity outliers.

###  IV-B Implementation details

We use the MobileNetV2 pre-trained on ImageNet [37] as listed in Sec. III-A
for our feature extractor backbone. The use of ImageNet pre-trained model
allows for faster convergence during training. We implement our model using
PyTorch and use the Adam optimizer ($\beta_{1}=0.9$, $\beta_{2}=0.999$) as our
optimizer with Stochastic Weight Averaging (SWA) [38]. We randomly crop images
to size $W=576$, $H=288$ for training.

On the SceneFlow dataset, we train our model for 10 epochs with a learning
rate $1\times 10^{-3}$ for the first 7 epochs and $1\times 10^{-4}$ for the
remaining 3 epochs with a batch size of $8$. For our experiments on the KITTI
dataset, we use a model pre-trained on the SceneFlow dataset and finetune the
model on the KITTI dataset for 800 epochs with an initial learning rate of
$1\times 10^{-3}$ decaying by a factor of $0.5$ at epochs $30$, $50$, and
$300$. The Nvidia RTX 2080Ti GPU is used for training and testing.

Figure 3: Qualitative results on KITTI 2015 test set. Error in orange
corresponds erroneous prediction. Figure 4: Disparity distributions of models
trained with different choice of $k$ in top-$k$ regression. Dashed red line is
the estimated disparity and the solid green line is ground truth disparity.

###  IV-C Performance of CoEx

We show the comparisons of our model to the existing state-of-the-art in Table
I. Note that KITTI results are all from the KITTI Stereo Matching Leaderboard,
and the SceneFlow EPE values, as well as the runtime, are the values reported
in each work. Among the speed based models, StereoNet is the fastest
performing model with a runtime of 15 $ms$. However, StereoNet’s accuracy on
SceneFlow and KITTI is considerably less than CoEx, with differences being
0.411 EPE for SceneFlow and 2.7% on KITTI 2015.

Methods Feature Cost Refine- Total Extraction Aggregation ment LEAStereo [21]
12 463 – 475 AANet [27] 22 32 32 88 AANet+ [27] 11 21 45 80 CoEx (Ours) 10 17
– 27

TABLE II: Time comparison in $ms$ with other state-of-the-arts models on the
same hardware. Bold: Best time.

As runtime comparisons in different hardware do not give a fair comparison, we
compare the runtime breakdown of LEAStereo [21] and AANet [27] with our model
tested on the same hardware (RTX 2080Ti) using the official open-source models
in Table II. The cost aggregation part includes cost volume construction and
disparity regression. Our model is $3.3\times$ faster than AANet while giving
0.18 EPE lower and 0.46% better KITTI 2012 3px out-all% and 0.42% better
D1-all% on KITTI 2015. AANet+ added more focus towards disparity refinement to
improve accuracy without sacrificing speed at the cost of a high number of
network parameters at $8.4M$ compared to our $2.7M$. Our model does not use
any post aggregation refinement and still gives similar accuracy while being
$3\times$ faster than AANet+.

###  IV-D Ablation study

Base Cost volume GCE Top-k reg SceneFlow Time model Corr Concat $k$ EPE (ms)
PSMNet ✓ 192 0.8291 292 ✓ 6 0.7437 405 ✓ One 192 0.8176 297 ✓ One 6 0.7321 405
✓ 192 1.053 223 ✓ 6 0.8798 332 ✓ One 192 0.8285 225 ✓ One 192$\rightarrow$6*
0.8088 333 ✓ One 6 0.7653 333 ✓ One 2 1.108 332 CoEx ✓ 48 0.8552 26 ✓ 6 0.8262
26 ✓ 3 0.7928 26 ✓ 2 0.7942 26 ✓ One 48 0.8242 26 ✓ Full 48 0.7426 26 ✓ Full
48$\rightarrow$2* 0.7782 27 ✓ Full 6 0.7185 27 ✓ Full 3 0.7115 27 ✓ Full 2
0.6854 27

TABLE III: Ablation study of GCE and top-$k$ soft-argmin regression integrated
into base models on SceneFlow ‘finalpass’ with the EPE metric (lower is
better). ‘One’ means only a single GCE layer is added into the model, while
‘Full’ adds GCE layer at every scale level Fig. 2.
*$k_{1}\rightarrow k_{2}$ : the model is trained using $k_{1}$ and tested using $k_{2}$ soft-argmin regression

Base GCE SceneFlow model Add Excite EPE 3px CoEx 0.7426 4.308 ✓ 0.7310 4.159 ✓
0.6854 4.021

TABLE IV: Comparison between the use of addition or excitation of cost volume
features from reference image features.

Base GCE Neighborhood SceneFlow Time model EPE 3px (ms) CoEx One 0.7684 4.409
26 One 0.7732 4.435 47

TABLE V: Comparison of GCE and spatially varying neighborhood aggregation

We perform ablation studies on the SceneFlow dataset to study the influence of
the proposed modules. We integrate GCE and top-$k$ soft-argmin regression into
baseline stereo matching models. For this ablation study, we used the baseline
PSMNet and CoEx model (Table III). Note that PSMNet uses a concatenation of
the feature representations between the left and right images to construct
cost volume. Concatenation allows the neural network to have a stronger
representation power than correlation based cost volume construction that
reduces the feature map to a single value of cosine similarity for each match.
Replacing the concatenation in PSMNet to correlation reduces the accuracy as
expected. However, adding only a single GCE layer into the correlation based
PSMNet, indicated by ‘One’ in Table III, brings the accuracy to a similar
value to the concatenation based PSMNet, indicating that GCE enable the
network to utilize image feature representations that is missed by
correlation. In addition, the use of correlation also reduces the computation
time significantly.

In PSMNet, the cost volume is upsampled to the original input image resolution
and the maximum disparity value is at $D=192$. We test top-$k$ soft-argmin
regression in PSMNet with $k$ between $2$ to $192$. We found that reducing $k$
from the original value of $k=192$ generally improves performance up to a
point. The accuracy degrades when k is set too low, perhaps due to a lack of
gradient flow in backpropagation. Moreover, performing sorting to obtain the
top-$k$ values in the full cost volume resolution proves to be too
computationally costly.

This motivated us to compute our disparity regression in the CoEx model at
$1/4$ the input image resolution and utilize the superpixel upsampling Sec.
III-C to obtain the disparity map at the original resolution. Note that in
CoEx, $k=192/4=48$ is the maximum value of $k$. We show in Table III, adding
top-$k$ soft-argmin regression to CoEx hardly increases the computation time
and gives better accuracy when lower $k$ values are used.

Table III also shows the performance gain when GCE is integrated at every
scale level (Fig. 2), indicated by ‘Full’. Our best model is obtained when
full GCE integration and top-$2$ soft-argmin regression are added into the
base CoEx model. Notice that the two proposed modules only add $1ms$ of
computation overhead from the base model but gives $0.17$ lower test EPE.

####  IV-D1 GCE

We investigated two approaches to use the reference image as a guide for cost
volume aggregation. The first is a simple addition between image features and
cost volume features with a broadcasted operation, which effectively acts like
a UNet style skip-connection. The second is based on excitation and is the
proposed GCE module. The test comparison between the two on the SceneFlow
dataset is shown in Table IV. Addition based skip-connection does give a
slight accuracy improvement to the baseline. However, we found cost volume
excitation a much more effective way of utilizing image features in cost
aggregation.

We compare the GCE module that performs spatially varying local aggregation
with a similar spatially varying operation that involves neighborhood
aggregation. To do this, we formulate a neighborhood as a graph and use graph
convolution to aggregate the nodes surrounding the center node of interest,
where the graph edges are spatially varying and computed from the reference
image feature map. The details of this graph-based aggregation are given in
the Appendix. Table V shows that a simple excitation of the cost volume
feature using a GCE module is performs better and more efficient than the
implemented neighborhood spatially independent aggregation.

####  IV-D2 Top-$2$ disparity regression

To further illustrate how top-$k$ regression improves compared to soft-argmin
regression, we plot the disparity distribution, produced from the output of
cost aggregation, of models trained with each $k$ value. Fig. 4 illustrates 3
cases where a lower $k$ value in top-$k$ regression outperforms the baseline
soft-argmin method. In the left most plot, the candidate disparities have a
unimodal distribution. The middle case shows when there are 2 possible peaks,
and the rightmost case shows the case when the distribution is relatively
flat. In all those cases, the model trained using top-$2$ distribution is able
to use only the peak matching values and is able to suppress values far away
from the correct matching peak, resulting in a more accurate estimate.

Then how well would models trained with full soft-argmin perform when we
replace this regression module with top-$k$ soft-argmin at test time? We
provide experimental results for this test in Table III and found no
improvement in the accuracy. The models need to learn to use the top-$k$ soft-
argmin regression during training.

##  V Conclusion

This paper introduces a new real-time stereo matching model that leverages
spatially dependent cost aggregation that we call CoEx. We show that spatially
varying aggregation can be performed in a lightweight and straightforward
fashion to improve performance. We also show how a direct use of top-$k$
values can improve the soft-argmin disparity regression. We believe that the
incredible speed of our method, where it is fast enough for real-time
applications, can be a springboard for future real-time stereo matching
research in real-world application settings.

## APPENDIX

###  V-A Detailed architecture

The detailed cost aggregation module is shown in Table VI. $s$ and $p$ are
stride and padding sizes for the convolution kernels respectively. $I^{(s)}$
is the feature map of the left image obtained in the feature extraction stage
at scale $(s)$.

No. Layer Setting Input $[1]$ correlation layer $I^{(4)}$ (Left and Right)
$[2$-$1]$ conv3d $3\times 3\times 3,8$ $[1]$ $[2]$ GCE $[2$-$1]$ and $I^{(4)}$
$[3$-$1]$ $\left[\begin{tabular}[]{@{}l@{}}conv3d $3\times 3\times 3,16$,
$s=2$\\\ conv3d $3\times 3\times 3,16$\end{tabular}\right]$ $[2]$ $[3]$ GCE
$[3$-$1]$ and $I^{(8)}$ $[4$-$1]$ $\left[\begin{tabular}[]{@{}l@{}}conv3d
$3\times 3\times 3,32$, $s=2$\\\ conv3d $3\times 3\times
3,32$\end{tabular}\right]$ $[3]$ $[4]$ GCE $[4$-$1]$ and $I^{(16)}$ $[5$-$1]$
$\left[\begin{tabular}[]{@{}l@{}}conv3d $3\times 3\times 3,48$, $s=2$\\\
conv3d $3\times 3\times 3,48$\end{tabular}\right]$ $[4]$ $[5]$ GCE $[5$-$1]$
and $I^{(32)}$ $[6$-$1]$ deconv3d $4\times 4\times 4,32$, $s=2,p=1$ $[5]$
$[6$-$2]$ conv3d $3\times 3\times 3,32$ $[6$-$1]$ $[6]$ GCE $[6$-$2]$ and
$I^{(16)}$ $[7$-$1]$ deconv3d $4\times 4\times 4,16$, $s=2,p=1$ $[6]$
$[7$-$2]$ conv3d $3\times 3\times 3,16$ $[7$-$1]$ $[7]$ GCE $[7$-$2]$ and
$I^{(8)}$ $[8]$ deconv3d $4\times 4\times 4,1$, $s=2,p=1$ $[7]$

TABLE VI: Cost aggregation module.

###  V-B Neighborhood aggregation

There are multiple previously proposed methods performing spatially varying
aggregation that utilizes the neighborhood information [15, 32, 5]. To compare
GCE with a module that computes spatially varying aggregation of the
neighbors, here we formulate a module that performs image-guided neighborhood
aggregation. Given a voxel of interest at pixel location $i$ and its neighbors
$j\in N(i)$ in a $1\times n\times n$ window, we compute the feature update of
cost volume at $i$ as follows:

$\begin{split}m_{i}^{(s,t+1)}=\sum_{j\in N(i)}e_{ji}\odot
C^{(s,t)}_{j},\quad\quad\quad\\\
C_{i}^{(s,t+1)}=\xi(W_{1}C_{i}^{(s,t)}+W_{2}m_{i}^{(t+1)}+b),\\\ \end{split}$
(5)

where $\odot$ represent element-wise product and $\xi$ is an activation
function. $e_{ji}$ is the edge weight (or affinity in [32] of $j$ to $i$, and
it is computed using $MLP$ on the image features at $i$ and $j$, and also the
encoding of the relative position $p_{i}-p_{j}$ of the neighbors:

$\begin{split}\hat{e}_{ji}=MLP([I_{i}^{(s)}||I_{j}^{(s)}||MLP(p_{i}-p_{j})])\\\
e_{ji}^{c}=\exp{\hat{e}_{ji}^{c}}/\sum_{j\in
N(i)}\exp{\hat{e}_{ji}^{c}},\end{split}$ (6)

where we use softmax (2nd line of the eqation) to normalize the edge weights
at each feature channel $c$. In this work, Deep Graph Library (DGL) [39] is
used to implement the neighborhood aggregation as a graph.

For image feature map with $c_{I}$ channels and cost volume of size $c\times
d\times h\times w$, GCE requires the following computation cost:

$\begin{split}(c_{I}\times c\times h\times w)+(c\times d\times h\times
w)\end{split}$ (7)

Where the left part of the equation is the cost to obtain spatially varying
weights, and the right part is the self-update. In contrast, if we write down
the cost of weight computation and update of neighborhood aggregation in a
$1\times n\times n$ neighborhood, in the simplest form of weight computation
where it computes weight by a point-wise convolution, it would require a
computation cost of at least:

$\begin{split}(c_{I}\times n\times n\times c\times h\times w)+(n\times n\times
c\times d\times h\times w).\end{split}$ (8)

Even in the simplest form, it would require $n\times n$ more times than GCE.

## References

  * [1] H. Hirschmuller, “Stereo processing by semiglobal matching and mutual information,” _IEEE Trans. on Patt. Anal. and Mach. Intel._ , 2007.
  * [2] D. Scharstein and R. Szeliski, “A taxonomy and evaluation of dense two-frame stereo correspondence algorithms,” _International journal of computer vision_ , 2002.
  * [3] X. Cheng, P. Wang, and R. Yang, “Depth estimation via affinity learned with convolutional spatial propagation network,” in _ECCV_ , 2018.
  * [4] Z. Yin, T. Darrell, and F. Yu, “Hierarchical discrete distribution decomposition for match density estimation,” in _CVPR_ , 2019.
  * [5] F. Zhang, V. Prisacariu, R. Yang, and P. H. Torr, “Ga-net: Guided aggregation net for end-to-end stereo matching,” in _CVPR_ , 2019.
  * [6] S. Lee, S. Im, S. Lin, and I. S. Kweon, “Learning residual flow as dynamic motion from stereo videos,” in _IROS_ , 2019.
  * [7] X. Gu, Z. Fan, S. Zhu, Z. Dai, F. Tan, and P. Tan, “Cascade cost volume for high-resolution multi-view stereo and stereo matching,” in _CVPR_ , 2020\.
  * [8] S. Lee, S. Im, S. Lin, and I. S. Kweon, “Learning monocular depth in dynamic scenes via instance-aware projection consistency,” in _AAAI_ , 2021.
  * [9] T. Zhou, M. Brown, N. Snavely, and D. G. Lowe, “Unsupervised learning of depth and ego-motion from video,” in _CVPR_ , 2017.
  * [10] S. Hwang, N. Kim, Y. Choi, S. Lee, and I. S. Kweon, “Fast multiple objects detection and tracking fusing color camera and 3d lidar for intelligent vehicles,” in _URAI_ , 2016.
  * [11] J.-R. Chang and Y.-S. Chen, “Pyramid stereo matching network,” in _CVPR_ , 2018.
  * [12] N. Mayer, E. Ilg, P. Hausser, P. Fischer, D. Cremers, A. Dosovitskiy, and T. Brox, “A large dataset to train convolutional networks for disparity, optical flow, and scene flow estimation,” in _CVPR_ , 2016.
  * [13] A. Kendall, H. Martirosyan, S. Dasgupta, P. Henry, R. Kennedy, A. Bachrach, and A. Bry, “End-to-end learning of geometry and context for deep stereo regression,” in _ICCV_ , 2017.
  * [14] S. Tulyakov, A. Ivanov, and F. Fleuret, “Practical deep stereo (pds): Toward applications-friendly deep stereo matching,” in _NeurIPS_ , 2018.
  * [15] C. Cai and P. Mordohai, “Do end-to-end stereo algorithms under-utilize information?” in _3DV_ , 2020.
  * [16] S. Woo, J. Park, J.-Y. Lee, and I. S. Kweon, “Cbam: Convolutional block attention module,” in _ECCV_ , 2018.
  * [17] J. Hu, L. Shen, and G. Sun, “Squeeze-and-excitation networks,” in _CVPR_ , 2018.
  * [18] W. Luo, A. G. Schwing, and R. Urtasun, “Efficient deep learning for stereo matching,” in _CVPR_ , 2016.
  * [19] J. Zbontar and Y. LeCun, “Stereo matching by training a convolutional neural network to compare image patches,” _Journal of Machine Learning Research_ , 2016.
  * [20] S. Lee, J. Kim, T.-H. Oh, Y. Jeong, D. Yoo, S. Lin, and I. S. Kweon, “Visuomotor understanding for representation learning of driving scenes,” in _BMVC_ , 2019.
  * [21] X. Cheng, Y. Zhong, M. Harandi, Y. Dai, X. Chang, H. Li, T. Drummond, and Z. Ge, “Hierarchical neural architecture search for deep stereo matching,” in _NeurIPS_ , 2020.
  * [22] J. Pang, W. Sun, J. S. Ren, C. Yang, and Q. Yan, “Cascade residual learning: A two-stage convolutional neural network for stereo matching,” in _ICCVw_ , 2017.
  * [23] G. Yang, H. Zhao, J. Shi, Z. Deng, and J. Jia, “Segstereo: Exploiting semantic information for disparity estimation,” in _ECCV_ , 2018.
  * [24] X. Song, X. Zhao, L. Fang, H. Hu, and Y. Yu, “Edgestereo: An effective multi-task learning network for stereo matching and edge detection,” _International Journal of Computer Vision_ , pp. 1–21, 2020.
  * [25] S. Khamis, S. Fanello, C. Rhemann, A. Kowdle, J. Valentin, and S. Izadi, “Stereonet: Guided hierarchical refinement for real-time edge-aware depth prediction,” in _ECCV_ , 2018.
  * [26] S. Duggal, S. Wang, W.-C. Ma, R. Hu, and R. Urtasun, “Deeppruner: Learning efficient stereo matching via differentiable patchmatch,” in _ICCV_ , 2019\.
  * [27] H. Xu and J. Zhang, “Aanet: Adaptive aggregation network for efficient stereo matching,” in _CVPR_ , 2020.
  * [28] Y. Zhang, Y. Chen, X. Bai, S. Yu, K. Yu, Z. Li, and K. Yang, “Adaptive unimodal cost volume filtering for deep stereo matching.” in _AAAI_ , 2020\.
  * [29] D. Garg, Y. Wang, B. Hariharan, M. Campbell, K. Q. Weinberger, and W.-L. Chao, “Wasserstein distances for stereo disparity estimation,” _NeurIPS_ , 2020\.
  * [30] M. Sandler, A. Howard, M. Zhu, A. Zhmoginov, and L.-C. Chen, “Mobilenetv2: Inverted residuals and linear bottlenecks,” in _CVPR_ , 2018.
  * [31] O. Ronneberger, P. Fischer, and T. Brox, “U-net: Convolutional networks for biomedical image segmentation,” in _MICCAI_ , 2015.
  * [32] X. Cheng, P. Wang, and R. Yang, “Learning depth with convolutional spatial propagation network,” _arXiv preprint arXiv:1810.02695_ , 2018.
  * [33] N. Kalchbrenner, E. Grefenstette, and P. Blunsom, “A convolutional neural network for modelling sentences,” _arXiv preprint arXiv:1404.2188_ , 2014\.
  * [34] F. Yang, Q. Sun, H. Jin, and Z. Zhou, “Superpixel segmentation with fully convolutional networks,” in _CVPR_ , 2020.
  * [35] A. Geiger, P. Lenz, and R. Urtasun, “Are we ready for autonomous driving? the kitti vision benchmark suite,” in _CVPR_ , 2012.
  * [36] M. Menze and A. Geiger, “Object scene flow for autonomous vehicles,” in _CVPR_ , 2015.
  * [37] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “ImageNet: A Large-Scale Hierarchical Image Database,” in _CVPR09_ , 2009.
  * [38] P. Izmailov, D. Podoprikhin, T. Garipov, D. Vetrov, and A. G. Wilson, “Averaging weights leads to wider optima and better generalization,” _arXiv preprint arXiv:1803.05407_ , 2018.
  * [39] M. Wang, D. Zheng, Z. Ye, Q. Gan, M. Li, X. Song, J. Zhou, C. Ma, L. Yu, Y. Gai, T. Xiao, T. He, G. Karypis, J. Li, and Z. Zhang, “Deep graph library: A graph-centric, highly-performant package for graph neural networks,” _arXiv preprint arXiv:1909.01315_ , 2019.