Steiner distance matrix of caterpillar graphs

Ali Azimi, R. B. Bapat and Shivani Goel

###### Abstract

For a connected graph $G:=(V,E)$, the Steiner distance $d_{G}(X)$ among a set
of vertices $X$ is the minimum size among all the connected subgraphs of $G$
whose vertex set contains $X$. The $k-$Steiner distance matrix $D_{k}(G)$ of
$G$ is a matrix whose rows and columns are indexed by $k-$subsets of $V$. For
$k$-subsets $X_{1}$ and $X_{2}$, the $(X_{1},X_{2})-$entry of $D_{k}(G)$ is
$d_{G}(X_{1}\cup X_{2})$. In this paper, we show that the rank of $2-$Steiner
distance matrix of a caterpillar graph on $N$ vertices and with $p$ pendant
veritices is $2N-p-1$.

Keywords. Steiner tree, caterpillar graph, determinant, schur complement,
distance matrix, rank of a matrix, Laplacian matrices.

AMS CLASSIFICATION. 05C50

MSC PRIMARY. 05C05, 05C12, 05C50

##  1 Introduction

Let $G:=(V,E)$ be a connected graph with vertex set $V$ and edge set $E$.
Suppose $u,v\in V$. The distance $d(u,v)$ between $u$ and $v$ is the length of
the shortest path connecting $u$ and $v$. The distance $d(u,v)$ can be
interpreted as the minimum size of a connected subgraph of $G$ containing both
$u$ and $v$. This insight towards the distance between two vertices gives the
motivation to extend the concept of distance between more than two vertices,
known as Steiner distance.

Let $X\subseteq V$, containing at least two vertices. The Steiner distance
$d_{G}(X)$ among the vertices of $X$ is the minimum size among all the
connected subgraphs of $G$ whose vertex set contains $X$. We refer to [1] for
more details on Steiner distance in graphs. Let $k\geq 2$ be an integer. We
define the $k-$Steiner distance matrix of $G$, denoted by $D_{k}(G)$ as
follows: The rows and columns of $D_{k}(G)$ are indexed by $k-$subsets of $V$.
Let $X_{1}$ and $X_{2}$ be two $k$-subsets of $V$. The $(X_{1},X_{2})-$entry
of $D_{k}(G)$ is $d_{G}(X_{1}\cup X_{2})$. We illustrate the $k-$Steiner
distance matrix by the following example.

######  Example 1.

Consider the following tree $T$ on $5$ vertices.

$0$$1$$2$$3$$4$ Figure 1: A tree $T$ on $5$ vertices

Suppose the rows and columns of $D_{2}(T)$ are indexed in the following order:

$\\{0,1\\},\\{0,2\\},\\{0,3\\},\\{0,4\\},\\{1,4\\},\\{2,4\\},\\{3,4\\},\\{1,2\\},\\{1,3\\},\\{2,3\\}$

Then, the $2-$Steiner distance matrix of $T$ is

$D_{2}(T)=\left[\begin{array}[]{cccccccccccc}1&2&3&4&4&4&4&2&3&3\\\
2&2&3&4&4&4&4&2&3&3\\\ 3&3&3&4&4&4&4&3&3&3\\\ 4&4&4&4&4&4&4&4&4&4\\\
4&4&4&4&3&3&3&3&3&3\\\ 4&4&4&4&3&2&2&3&3&2\\\ 4&4&4&4&3&2&1&3&3&2\\\
2&2&3&4&3&3&3&1&2&2\\\ 3&3&3&4&3&3&3&2&2&2\\\
3&3&3&4&3&2&2&2&2&1\end{array}\right].$

Throughout the paper, all vectors are considered as column vectors. For a
matrix $A$ and a set of indices $X$, we will use $A[X,X]$ to denote the
submatrix of $A$ determined by the rows and columns indexed by $X$. The
cardinality of a set $X$ is represented by $|X|$. We will use $J$ to denote
the matrix of all ones of appropriate order. For a matrix $A$, $A[i]$ will
denote the $i^{\rm th}$ row of $A$. The notations $I$ and $\mathbf{1}$ will
represent the identity matrix and all ones vector of the appropriate order,
respectively. The degree of a vertex $\alpha$ in a graph is denoted by ${\rm
deg}(\alpha)$.

###  1.1 Objective of the paper

Let $G$ be a connected graph with vertex set $V:=\\{0,1,\dotsc,n\\}$. The
Laplacian matrix of the graph $G$ is the matrix $L:=(l_{ij})$, where

$l_{ij}:=\begin{cases}~{}~{}\delta_{i}&~{}{\rm if}~{}i=j\\\ -1&~{}{\rm
if}~{}i~{}{\rm and}~{}j~{}{\rm are~{}adjacent}\\\ ~{}~{}0&~{}{\rm
otherwise}.\end{cases}$

Here, $\delta_{i}$ is the degree of the vertex $i$. Let $T$ be a tree with
vertex set $\\{1,2,\dotsc,n\\}$ and distance matrix $D$. Suppose $L$ is the
Laplacian of $T$. In [2], Graham and Lovász, showed that

$D^{-1}=-\frac{1}{2}L+\frac{1}{2(n-1)}\tau\tau^{\prime},$

where $\tau:=(2-\delta_{1},\dotsc,2-\delta_{n})^{\prime}$ and $\delta_{i}$ is
equal to the degree of the vertex $i$. In the spirit of Graham and Lovász
formula, there are inverse formula for distance matrices of several other
connected graphs, see [3], [4], [5], [6] and [7]. We now list the objectives
of the paper.

  1. 1.

Let $P_{n}$ be a path graph on $n+1$ vertices $\\{0,1,\dotsc,n\\}$ and let

$X:=\\{\\{0,\alpha\\}|~{}\alpha\neq
0\\}\cup\\{\\{\alpha,n\\}|~{}{\rm\deg}(\alpha)\neq 1\\}.$

It is easy to note that $|X|=2n-1$. Motivated by Graham and Lovász formula, we
first show that

$D_{2}(P_{n})[X,X]^{-1}=-L+\frac{1}{n}uu^{\prime},$

where
$u:=(0,\dotsc,0,\underbrace{1}_{n},0,\dotsc,0)^{\prime}\in\mathbb{R}^{2n-1}$
and $L$ is the Laplacian of a path graph on $2n-1$ vertices.

  2. 2.

A caterpillar graph is a tree in which all the vertices are within a distance
$1$ from a central path (see figure 2).

$0$$1$$2$$6$$7$$3$$4$$5$ Figure 2: A caterpillar graph

Suppose $\mathcal{C}$ is a caterpillar graph with its central path of maximum
length as $P_{n}$. We next show that, if

$X:=\\{\\{0,\alpha\\}|~{}\alpha\neq
0\\}\cup\\{\\{\alpha,n\\}|~{}deg(\alpha)\neq 1\\},$

then the matrix $D_{2}(\mathcal{C})[X,X]$ is invertible. In our main result of
this paper, we find the rank of $D_{2}(\mathcal{C})$.

##  2 Path graphs

Let $P_{n}$ denotes a path graph on $n+1$ vertices (see Figure 3).

$0$$1$$2$$n$ Figure 3: $P_{n}$

Let $D_{2}(P_{n})$ be the Steiner distance matrix of $P_{n}$ and let
$X:=\\{\\{0,\alpha\\}|~{}\alpha\neq
0\\}\cup\\{\\{\alpha,n\\}|~{}deg(\alpha)\neq 1\\}$. In this section, we will
deduce an inverse formula for $D_{2}(P_{n})[X,X]$. The result proved in this
section will be helpful in proving the main result of the paper. Suppose the
sets in $X$ are indexed in the following order:

$\\{0,1\\},\cdots,\\{0,n\\},\\{1,n\\},\cdots,\\{n-1,n\\}.$

We begin with a few observations on the matrix $D_{2}(P_{n})[X,X]$.

  1. 1.

Let $X_{1}=\\{0,\alpha_{1}\\}$, $X_{2}=\\{0,\alpha_{2}\\}$,
$X_{3}=\\{\alpha_{3},n\\}$ and $X_{4}=\\{\alpha_{4},n\\}$, where
$0<\alpha_{1},\alpha_{2}\leq n$ and $0<\alpha_{3},\alpha_{4}<n$ are pairwise
distinct vertices of $P_{n}$. It is easy to see that

$d_{P_{n}}(X_{1}\cup X_{2})=\mathop{\rm max}\\{\alpha_{1},\alpha_{2}\\},$
$d_{P_{n}}(X_{3}\cup X_{4})=n-\mathop{\rm min}\\{\alpha_{3},\alpha_{4}\\},$

and

$d_{P_{n}}(X_{1}\cup X_{i})=n,~{}{\rm for}~{}i=3,4.$

Using the above observation, the submatrix $D_{2}(P_{n})[X,X]$ of
$D_{2}(P_{n})$ can be written in the following block form

$D_{2}(P_{n})[X,X]=\left[\begin{array}[]{cc}S_{1}&nJ_{n,n-1}\\\
nJ_{n-1,n}&S_{2}\end{array}\right],$

where

$S_{1}:=\left[\begin{array}[]{ccccccccccccccccccccccc}1&2&3&4&\cdots&n\\\
2&2&3&4&\cdots&n\\\ 3&3&3&4&\cdots&n\\\ \cdots&\\\
n&n&n&n&\cdots&n\end{array}\right]~{}\mbox{and}~{}S_{2}:=\left[\begin{array}[]{ccccccccccccccccccccccc}n-1&n-1&n-1&\cdots&n-1\\\
n-1&n-2&n-2&\cdots&n-2\\\ n-1&n-2&n-3&\cdots&n-3\\\ \cdots&\\\
n-1&n-2&n-3&\cdots&1\end{array}\right].$

  2. 2.

Using the above block form, we deduce expressions for rows of
$D_{2}(P_{n})[X,X]$ as follows. If $1\leq i\leq n$, then

$D_{2}(P_{n})[X,X][i]=(\underbrace{i,\dotsc,i}_{i},i+1,i+2,\dotsc,n,\dotsc,n),$
(1)

and for $n+1\leq k\leq 2n-1$

$D_{2}(P_{n})[X,X][k]=(\underbrace{n,\dotsc,n}_{n},n-1,n-2,\dotsc,\underbrace{2n-k,\dotsc,2n-k}_{2n-k}).$
(2)

In the next two results, we deduce an inverse formula for $D_{2}(P_{n})[X,X]$.

######  Lemma 1.

Let $D:=D_{2}(P_{n})[X,X]$. If $L$ is the Laplacian of a path graph on $2n-1$
vertices, then

$LD+I=u\mathbf{1}^{\prime},$

where $u:=(0,\dotsc,0,\underbrace{1}_{n},0,\dotsc,0)\in\mathbb{R}^{2n-1}.$

###### Proof.

The Laplacian matrix of a path graph is a tridiagonal matrix with its main
diagonal determined by the vector $(1,2,\dotsc,2,1)$. The first diagonal above
and below the main diagonal have all the entries equal to $-1$. Using this, we
first note that

$(LD)[1]=D[1]-D[2],$ $(LD)[i]=2D[i]-D[i-1]-D[i+1],~{}\mbox{for}~{}2\leq i\leq
2n-2$

and

$(LD)[2n-1]=D[2n-1]-D[2n-2].$

We now compute exact expressions for the rows of $LD$ by using (1) and (2),
repeatedly. This is done by considering several cases as listed below:

  1. (i)

It is easy to see that

$(LD)[1]=D[1]-D[2]=(-1,0,\dotsc,0).$

  2. (ii)

For $2\leq i\leq n-1$

$\displaystyle(LD)[i]$ $\displaystyle=2D[i]-D[i-1]-D[i+1]$
$\displaystyle=2(\underbrace{i,\dotsc,i}_{i},i+1,i+2,\dotsc,n,\dotsc,n)$
$\displaystyle~{}~{}~{}-(\underbrace{i-1,\dotsc,i-1}_{i-1},i,i+1,i+2,\dotsc,n,\dotsc,n)$
$\displaystyle~{}~{}~{}-(\underbrace{i+1,\dotsc,i+1}_{i+1},i+2,\dotsc,n,\dotsc,n)$
$\displaystyle=({0,\dotsc,0},\underbrace{-1}_{i},0,\dotsc,0).$

  3. (iii)

Next, we note that

$\displaystyle(LD)[n]$ $\displaystyle=2D[n]-D[n-1]-D[n+1]$
$\displaystyle=2n\mathbf{1}^{\prime}-(\underbrace{n-1,\dotsc,n-1}_{n-1},n,\dotsc,n)-(\underbrace{n,\dotsc,n}_{n},n-1,\dotsc,n-1)$
$\displaystyle=({1,\dotsc,1},\underbrace{0}_{n},1,\dotsc,1),$

and

$\displaystyle(LD)[n+1]$ $\displaystyle=2D[n+1]-D[n]-D[n+2]$
$\displaystyle=2(\underbrace{n,\dotsc,n}_{n},n-1,\dotsc,n-1)-n\mathbf{1}^{\prime}$
$\displaystyle~{}~{}~{}-(\underbrace{n,\dotsc,n}_{n},n-1,{n-2,\dotsc,n-2})$
$\displaystyle=({0,\dotsc,0},\underbrace{-1}_{n+1},0,\dotsc,0).$

  4. (iv)

Let $n+2\leq k\leq 2n-2$. Then

$\displaystyle(LD)[k]$ $\displaystyle=2D[k]-D[k-1]-D[k+1]$
$\displaystyle=2(\underbrace{n,\dotsc,n}_{n},n-1,n-2,\dotsc,\underbrace{2n-k,\dotsc,2n-k}_{2n-k})$
$\displaystyle~{}~{}~{}~{}-(\underbrace{n,\dotsc,n}_{n},n-1,n-2,\dotsc,\underbrace{2n-k+1,\dotsc,2n-k+1}_{2n-k+1})$
$\displaystyle~{}~{}~{}~{}-(\underbrace{n,\dotsc,n}_{n},n-1,n-2,\dotsc,\underbrace{2n-k-1,\dotsc,2n-k-1}_{2n-k-1})$
$\displaystyle=(0,\dotsc,0,\underbrace{-1}_{k},0,0,\dotsc,0).$

  5. (v)

Finally

$\displaystyle(LD)[2n-1]$ $\displaystyle=D[2n-1]-D[2n-2]$
$\displaystyle=(\underbrace{n,\dotsc,n}_{n},n-1,n-2,\dotsc,1)-(\underbrace{n,\dotsc,n}_{n},n-1,n-2,\dotsc,3,2,2)$
$\displaystyle=(0,\dotsc,0,-1).$

From (i), (ii), (iii), (iv) and (v), we note that except the $n^{\rm th}$ row,
all other rows of $LD$ are equal to the corresonding rows of the matrix $-I$.
Hence $LD+I$ has all other rows except the $n^{\rm th}$ row as zero. Also, the
$n^{\rm th}$ row of $LD+I$ is the all one vector. Thus

$LD+I=u\mathbf{1}^{\prime},$

where $u=(0,\dotsc,0,\underbrace{1}_{n},0,\dotsc,0)^{\prime}.$ This completes
the proof. ∎

######  Theorem 1.

Let $D=D_{2}(P_{n})[X,X]$ and $L$ be the Laplacian of a path graph on $2n-1$
vertices. Then

$D^{-1}=-L+\frac{1}{n}uu^{\prime},$

where $u=(0,\dotsc,0,\underbrace{1}_{n},0,\dotsc,0)\in\mathbb{R}^{2n-1}.$

###### Proof.

Since the $n^{\rm th}$ row of $D$ is $n\mathbf{1}^{\prime}$, it is easy to see
that $u^{\prime}D=n\mathbf{1}^{\prime}$. Now

$\displaystyle(-L+\frac{1}{n}uu^{\prime})D$
$\displaystyle=I-u\mathbf{1}^{\prime}+\frac{1}{n}uu^{\prime}D=I.$

Thus, $D$ is invertible and

$D^{-1}=-L+\frac{1}{n}uu^{\prime}.$

The proof is complete. ∎

##  3 Caterpillar graphs

In this section, we first introduce caterpillar graphs and observe the
structure of its $2-$Steiner distance matrix. Next, we compute the rank of its
$2-$Steiner distance matrix by finding an invertible submatrix of maximum
size. Let $\mathcal{C}$ be a caterpillar graph and let $P_{n}$ be a central
path of maximum length in $\mathcal{C}$ (see Figure 4).

$0$$1$$2$$n$ Figure 4: $\mathcal{C}$

Without loss of generality, we label the vertices of $\mathcal{C}$ in the
following way:

  1. 1.

The vertices of $P_{n}$ are labeled from $0$ to $n$.

  2. 2.

The vertices adjacent to $1$ other than that of $P_{n}$ are labeled from
$n+1,\dotsc,n+i_{1}$.

  3. 3.

The vertices adjacent to $2$ other than that of $P_{n}$ are labeled from
$n+i_{1}+1,\dotsc,n+i_{1}+i_{2}$.

  4. 4.

Continuing like this, the vertices adjacent to $n-1$ other than that of
$P_{n}$ are labeled from
$n+\sum_{j=1}^{n-2}i_{j}+1,\dotsc,n+\sum_{j=1}^{n-1}i_{j}$.

In the rest of the paper, we follow the above labelling for caterpillar
graphs. We now illustrate the $2-$Steiner distance matrix of a caterpillar
graph with an example.

######  Example 2.

Consider the caterpillar graph given in Figure 2. Suppose $D_{2}(\mathcal{C})$
denotes its $2-$Steiner distance matrix and let

$X=\\{\\{0,1\\},\\{0,2\\},\\{0,3\\},\\{0,4\\},\\{1,4\\},\\{2,4\\},\\{3,4\\},\\{0,5\\},\\{0,6\\},\\{0,7\\}\\}.$

Then

$D_{2}(\mathcal{C})[X,X]=\left[\begin{array}[]{cccccccccccc}1&2&3&4&4&4&4&2&3&3\\\
2&2&3&4&4&4&4&3&3&3\\\ 3&3&3&4&4&4&4&4&4&4\\\ 4&4&4&4&4&4&4&5&5&5\\\
4&4&4&4&3&3&3&5&5&5\\\ 4&4&4&4&3&2&2&5&5&5\\\ 4&4&4&4&3&2&1&5&5&5\\\
2&3&4&5&5&5&5&2&4&4\\\ 3&3&4&5&5&5&5&4&3&4\\\
3&3&4&5&5&5&5&4&4&3\end{array}\right].$

We observe that the submatrix of $D_{2}(\mathcal{C})[X,X]$ corresponding to
the first $7$ rows and columns is equal to the submatrix corresponding to the
same rows and columns of the matrix $D_{2}(T)$ given in Example 1 .

###  3.1 Block form for $D_{2}(\mathcal{C})[X,X]$

We recall that $X=\\{\\{0,j\\}|~{}j\neq 0\\}\cup\\{\\{j,n\\}|~{}deg(j)\neq
1\\}.$ If we write elements of $X$ in the following order

$X=\\{\\{0,1\\},\cdots,\\{0,n\\},\\{1,n\\},\cdots,\\{n-1,n\\},\\{0,n+1\\},\\{0,n+2\\},\dotsc,\\{0,n+\sum_{j=1}^{n-1}i_{j}\\}\\},$

then

  1. (a)

If $D$ is the matrix given in Theorem 1, then $D$ is a principal submatrix of
$D_{2}(\mathcal{C})[X,X]$. In fact, $D$ is the principal submatrix of
$D_{2}(\mathcal{C})[X,X]$ corresponding to the first $2n-1$ rows and columns.

  2. (b)

Let $X_{1}=\\{0,\alpha_{1}\\}$ and $X_{2}=\\{0,\alpha_{2}\\}$ be set of
vertices of $\mathcal{C}$, where $1\leq\alpha_{1}\leq n$ and $\alpha_{2}>n$ is
adjacent to the vertex $\alpha$ of $P_{n}$. We note that

$d_{\mathcal{C}}(X_{1}\cup X_{2})={\rm max}\\{\alpha_{1},\alpha\\}+1.$

Suppose $X_{3}=\\{\alpha_{3},n\\}$, where $1\leq\alpha_{3}\leq n-1$. Then it
is easy to see that

$d_{\mathcal{C}}(X_{3}\cup X_{2})=n+1.$

Now, let $X_{4}=\\{0,\alpha_{4}\\}$, where $\alpha_{4}>n$ is adjacent to the
vertex $\alpha^{\prime}$ of $P_{n}$. Then

$d_{\mathcal{C}}(X_{2}\cup X_{4})=\begin{cases}\alpha+1&{\rm
if}~{}\alpha_{2}=\alpha_{4}\\\ \alpha+2&{\rm
if}~{}\alpha_{2}\neq\alpha_{4}~{}{\rm but}~{}\alpha=\alpha^{\prime}\\\ {\rm
max}\\{\alpha,\alpha^{\prime}\\}+2&{\rm otherwise.}\end{cases}$

  3. (c)

Using observations (a) and (b), the submatrix $D_{2}(\mathcal{C})[X,X]$ of
$D_{2}(\mathcal{C})$ can be written in the block form

$D_{2}(\mathcal{C})[X,X]=\left[\begin{array}[]{cc}D&M\\\
M^{\prime}&N\end{array}\right],$ (3)

where the matrix $M$ of order $(2n-1)\times\sum_{j=1}^{n-1}i_{j}$ and the
matrix $N$ of order $\sum_{j=1}^{n-1}i_{j}\times\sum_{j=1}^{n-1}i_{j}$ are
defined as follows: For $1\leq m\leq n-1$

$M[m]:=(m+1,\dotsc,m+1,\underbrace{m+2,\dotsc,m+2}_{i_{m+1}},\dotsc,\underbrace{n,\dotsc,n}_{i_{n-1}}),$
(4)

and for $n\leq m\leq 2n-1$

$M[m]:=(n+1)\mathbf{1}^{\prime}.$ (5)

Before defining $N$, we note that any column of $N$ consist of the distance
between the set $\\{0,\alpha\\}$, $\alpha>n$ and the sets

$\\{0,n+1\\},\\{0,n+2\\},\dotsc,\\{0,n+\sum_{j=1}^{n-1}i_{j}\\}.$

Now, let $1\leq m\leq\sum_{j=1}^{n-1}i_{j}$. For convenience, we assume
$i_{0}=0$. Then there exists $k$, $1\leq k\leq n-1$ such that
$\sum_{j=0}^{k-1}i_{j}<m\leq\sum_{j=1}^{k}i_{j}$. Thus, the matrix $N$ is
defined as follows:

$\displaystyle m^{\rm th}~{}\mbox{column of}~{}N$
$\displaystyle:=(k+2,\dotsc,k+2,\underbrace{k+1}_{m^{\rm
th}},k+2,\dotsc,k+2,\underbrace{k+3,\dotsc,k+3}_{i_{k+1}},$ (6)
$\displaystyle~{}~{}~{}~{}\dotsc,\underbrace{n+1,\dotsc,n+1}_{i_{n-1}})^{\prime}.$

###  3.2 Invertibility of $D_{2}(\mathcal{C})[X,X]$

In this subsection, we show that $D_{2}(\mathcal{C})[X,X]$ is invertible. This
implies ${\mathop{\rm rank}}(D_{2}(\mathcal{C}))\geq|X|$. By Theorem 1, we
know that $D$ is invertible and

$D^{-1}=-L+\frac{1}{n}uu^{\prime},$

where $L$ is the Laplacian matrix of a path graph on $2n-1$ vertices and
$u=(0,\dotsc,0,\underbrace{1}_{n},0,\dotsc,0)\in\mathbb{R}^{2n-1}$. Suppose
$P$ denotes the schur complement of $D$ in $D_{2}(\mathcal{C})[X,X]$. We know
that

$\displaystyle P$ $\displaystyle=N-M^{\prime}D^{-1}M$
$\displaystyle=N-M^{\prime}(-L+\frac{1}{n}uu^{\prime})M$
$\displaystyle=N+M^{\prime}LM-\frac{1}{n}M^{\prime}uu^{\prime}M.$

Since $n^{\rm th}$ row of $M$ is $(n+1)\mathbf{1}^{\prime}$, we conclude that

$u^{\prime}M=(n+1)\mathbf{1}^{\prime}.$

Thus

$\displaystyle
P=N+M^{\prime}LM-\frac{(n+1)^{2}}{n}\mathbf{1}\mathbf{1}^{\prime}.$ (7)

We claim that $D_{2}(\mathcal{C})[X,X]$ is invertible. Since $D$ is
invertible, it is enough to show that $P$ is invertible. In the subsequent
lemmas, we compute an exact expression for $P$.

######  Lemma 2.

Suppose $M$ is the matrix given in the block form (3) of
$D_{2}(\mathcal{C})[X,X]$ and $L$ is the Laplacian matrix of a path graph on
$2n-1$ vertices. Then

$(LM)[m]=\begin{cases}(0,\dotsc,0,\underbrace{-1,\dotsc,-1}_{i_{m}},0,\dotsc,0)&~{}\mbox{if}~{}1\leq
m\leq n-1\\\ (1,\dotsc,1)&~{}\mbox{if}~{}m=n\\\
(0,\dotsc,0)&\mbox{otherwise.}\end{cases}$

###### Proof.

We recall that $L$ is a tridiagonal matrix with its main diagonal determined
by the vector $(1,2,\dotsc,2,1)$ and its first diagonal above and below the
main diagonal have all the entries equal to $-1$. Using this observation, it
is easy to deduce that

$(LM)[1]=M[1]-M[2],$ $(LM)[m]=2M[m]-M[m-1]-M[m+1],~{}\mbox{for}~{}2\leq m\leq
2n-2$

and

$(LM)[2n-1]=M[2n-1]-[2n-2].$

Now, we compute $LM$ by repeatedly using (4) and (5) in the following cases.

  1. (i)

It is easy to see that

$(LM)[1]=M[1]-M[2]=(\underbrace{-1,\dotsc,-1}_{i_{1}},0,\dotsc,0).$

  2. (ii)

Suppose $2\leq m\leq n-2$. Then

$\displaystyle(LM)[m]$ $\displaystyle=2M[m]-M[m-1]-M[m+1]$
$\displaystyle=2(m+1,\dotsc,m+1,\underbrace{m+2,\dotsc,m+2}_{i_{m+1}},\dotsc,\underbrace{n,\dotsc,n}_{i_{n-1}})$
$\displaystyle~{}~{}~{}~{}-({m,\dotsc,,m},\underbrace{m+1,\dotsc,m+1}_{i_{m}},\dotsc,\underbrace{n,\dotsc,n}_{i_{n-1}})$
$\displaystyle~{}~{}~{}~{}-({m+2,\dotsc,m+2},\underbrace{m+3,\dotsc,m+3}_{i_{m+2}},\dotsc,\underbrace{n,\dotsc,n}_{i_{n-1}})$
$\displaystyle=(0,\dotsc,0,\underbrace{-1,\dotsc,-1}_{i_{m}},0,\dotsc,0).$

  3. (iii)

Next,

$\displaystyle(LM)[n-1]$ $\displaystyle=2M[n-1]-M[n-2]-M[n]$
$\displaystyle=2n\mathbf{1}^{\prime}-({n-1,\dotsc,n-1},\underbrace{n,\dotsc,n}_{i_{n-1}})-(n+1)\mathbf{1}^{\prime}$
$\displaystyle=(0,\dotsc,0,\underbrace{-1,\dotsc,-1}_{i_{n-1}}),$

and

$\displaystyle(LM)[n]$ $\displaystyle=2M[n]-M[n-1]-M[n+1]$
$\displaystyle=2(n+1)\mathbf{1}^{\prime}-n\mathbf{1}^{\prime}-(n+1)\mathbf{1}^{\prime}$
$\displaystyle=\mathbf{1}^{\prime}.$

  4. (iv)

Suppose $n+1\leq m\leq 2n-2$. Since $M[m]=(n+1)\mathbf{1}^{\prime}$, we have

$(LM)[m]=2M[m]-M[m-1]-M[m+1]=(0,\dotsc,0).$

  5. (v)

Finally,

$(LM)[2n-1]=M[2n-1]-[2n-2]=(0,\dotsc,0).$

From (i), (ii), (iii), (iv) and (v), we deduce

$(LM)[m]=\begin{cases}(0,\dotsc,0,\underbrace{-1,\dotsc,-1}_{i_{m}},0,\dotsc,0)&~{}\mbox{if}~{}1\leq
m\leq n-1\\\ (1,\dotsc,1)&~{}\mbox{if}~{}m=n\\\
(0,\dotsc,0)&\mbox{otherwise}\end{cases}$

The proof is complete. ∎

######  Lemma 3.

Suppose $M$ is the matrix given in the block form (3) of
$D_{2}(\mathcal{C})[X,X]$ and $L$ is the Laplacian matrix of a path graph on
$2n-1$ vertices. If $1\leq m\leq\sum_{j=1}^{n-1}i_{j}$ such that
$\sum_{j=0}^{k-1}i_{j}<m\leq\sum_{j=1}^{k}i_{j}$, for some $1\leq k\leq n-1$,
then

$m^{\rm th}~{}\mbox{column
of}~{}M^{\prime}LM=(n-k,\dotsc,n-k,\underbrace{n-k-1,\dotsc,n-k-1}_{i_{k+1}},\dotsc,\underbrace{1,\dotsc,1}_{i_{n-1}})^{\prime}.$

###### Proof.

Let $1\leq m\leq\sum_{j=1}^{n-1}i_{j}$. Then there exists $k$, $1\leq k\leq
n-1$ such that $\sum_{j=0}^{k-1}i_{j}<m\leq\sum_{j=1}^{k}i_{j}$. Using Lemma
2, (4) and (5), we have

$\displaystyle m^{\rm th}~{}\mbox{column of}~{}M^{\prime}LM$
$\displaystyle=-k^{\rm th}~{}\mbox{ column of }~{}M^{\prime}+n^{\rm
th}~{}\mbox{ column of }~{}M^{\prime}$
$\displaystyle=-M[k]^{\prime}+M[n]^{\prime}$
$\displaystyle=-({k+1,\dotsc,k+1},\underbrace{k+2,\dotsc,k+2}_{i_{k+1}},\dotsc,\underbrace{n,\dotsc,n}_{i_{n-1}})^{\prime}+(n+1)\mathbf{1}$
$\displaystyle=(n-k,\dotsc,n-k,\underbrace{n-k-1,\dotsc,n-k-1}_{i_{k+1}},\dotsc,\underbrace{1,\dotsc,1}_{i_{n-1}})^{\prime}.$

This completes the proof. ∎

######  Lemma 4.

Suppose $M$ and $N$ are the matrices given in the block form (3) of
$D_{2}(\mathcal{C})[X,X]$ and $L$ is the Laplacian matrix of a path graph on
$2n-1$ vertices. Then

$N+M^{\prime}LM=(n+2)J-I.$

###### Proof.

Let $1\leq m\leq\sum_{j=1}^{n-1}i_{j}$. Then there exists $k$, $1\leq k\leq
n-1$ such that $\sum_{j=0}^{k-1}i_{j}<m\leq\sum_{j=1}^{k}i_{j}$. Using Lemma 3
and (6), we have

$\displaystyle m^{\rm th}~{}\mbox{column of}~{}(N+M^{\prime}LM)$
$\displaystyle=(k+2,\dotsc,k+2,\underbrace{k+1}_{m^{\rm
th}},k+2,\dotsc,k+2,\underbrace{k+3,\dotsc,k+3}_{i_{k+1}},$
$\displaystyle~{}~{}~{}\dotsc,\underbrace{n+1,\dotsc,n+1}_{i_{n-1}})^{\prime}$
$\displaystyle~{}~{}~{}+(n-k,\dotsc,n-k,\underbrace{n-k-1,\dotsc,n-k-1}_{i_{k+1}},\dotsc,\underbrace{1,\dotsc,1}_{i_{n-1}})^{\prime}$
$\displaystyle=(n+2,\dotsc,n+2,\underbrace{n+1}_{m^{\rm
th}},n+2,\dotsc,n+2)^{\prime}$ $\displaystyle=(n+2)\mathbf{1}-e_{m}.$

Here, $e_{m}\in\mathbb{R}^{\sum_{j=1}^{n-1}i_{j}}$ with $1$ at its $m^{\rm
th}$ position and $0$ elsewhere. Thus

$N+M^{\prime}LM=(n+2)J-I,$

and the proof is complete. ∎

In the next theorem, we will prove the main result of this subsection.

######  Theorem 2.

The matrix $D_{2}(\mathcal{C})[X,X]$ is invertible.

###### Proof.

Using Lemma 4 in (7), we have

$\displaystyle P$ $\displaystyle=(n+2)J-I-\frac{1}{n}(n+1)^{2}J$
$\displaystyle=-\frac{1}{n}J-I.$

Thus $P$ is invertible. Since

${\rm det}(D_{2}(\mathcal{C})[X,X])={\rm det}(D){\rm det}(P),$

we conclude that $D_{2}(\mathcal{C})[X,X]$ is invertible. The proof is
complete. ∎

###  3.3 Rank of $D_{2}(\mathcal{C})$

For a distinct pair of vertices $\\{k,j\\}$,
$D_{2}(\mathcal{C})^{\prime}[\\{k,j\\}]$ is the column of $D_{2}(\mathcal{C})$
which is indexed by $\\{k,j\\}$. We recall that

$X=\\{\\{0,1\\},\cdots,\\{0,n\\},\\{1,n\\},\cdots,\\{n-1,n\\},\\{0,n+1\\},\\{0,n+2\\},\dotsc,\\{0,n+\sum_{j=1}^{n-1}i_{j}\\}\\}.$

We claim that each column of $D_{2}(\mathcal{C})$ corresponding to sets in
$X^{c}$ is a linear combination of columns of $D_{2}(\mathcal{C})$
corresponding to the sets in $X$. This along with Theorem 2 proves that rank
of $D_{2}(\mathcal{C})$ is $|X|$. Before, we begin the proof, we observe the
following. Suppose $\\{k,j\\}\in X^{c}$. Then, exactly one of the following
holds.

  1. (i)

$0<k,j<n$,

  2. (ii)

$0<k\leq n$ and $j>n$, or

  3. (iii)

$k,j>n$.

In the subsequent lemmas, we discuss the above cases separately and prove that
$D_{2}(\mathcal{C})^{\prime}[\\{k,j\\}]$ is a linear combination of columns of
$D_{2}(\mathcal{C})$ corresponding to the sets in $X$.

######  Lemma 5.

Let $\\{k,j\\}\in X^{c}$. If $0<k,j<n$, then

$D_{2}(\mathcal{C})^{\prime}[\\{k,j\\}]=D_{2}(\mathcal{C})^{\prime}[\\{0,j\\}]-D_{2}(\mathcal{C})^{\prime}[\\{0,n\\}]+D_{2}(\mathcal{C})^{\prime}[(k,n)].$

###### Proof.

Without loss of generality, we assume $k<j$. Let $\\{p,q\\}$ be a set of
distinct vertices of $\mathcal{C}$. We discuss the cases $\\{p,q\\}\in X$ and
$\\{p,q\\}\in X^{c}$, separately. In the following tables, the entries in each
column describes the entry in the $\\{p,q\\}^{\rm th}$ row of
$D_{2}(\mathcal{C})^{\prime}[\\{\alpha,\alpha^{\prime}\\}]$, for different
$\alpha$ and $\alpha^{\prime}$.

  1. 1.

For $\\{p,q\\}\in X$, we have the following.

$\\{p,q\\}$ $D_{2}(\mathcal{C})^{\prime}[\\{0,j\\}]$
$D_{2}(\mathcal{C})^{\prime}[\\{0,n\\}]$ $D_{2}(\mathcal{C})^{\prime}[(k,n)]$
$D_{2}(\mathcal{C})^{\prime}[\\{k,j\\}]$ $\\{0,l\\}$, $0<l\leq n$
$max\\{l,j\\}$ $n$ $n$ $max\\{l,j\\}$ (Fig 5) $\\{l,n\\}$, $0<l<n$ $n$ $n$
$n-min\\{l,k\\}$ $n-min\\{l,k\\}$ (Fig 5) $\\{0,l\\}$, $l>n$ $max\\{i,j\\}+1$
$n+1$ $n+1$ $max\\{i,j\\}+1$ (Fig 6)

$0$$l$$k$$j$$n$ Figure 5:  $0$$i$$l$$k$$j$$n$ Figure 6:

  2. 2.

Suppose $\\{p,q\\}\in X^{c}$. Without loss of generality, we assume $p<q$.
Now, the following holds.

$\\{p,q\\}$ $D_{2}(\mathcal{C})^{\prime}[\\{0,j\\}]$
$D_{2}(\mathcal{C})^{\prime}[\\{0,n\\}]$ $D_{2}(\mathcal{C})^{\prime}[(k,n)]$
$D_{2}(\mathcal{C})^{\prime}[\\{k,j\\}]$ $0<p,q<n$ $max\\{q,j\\}$ $n$
$n-min\\{p,k\\}$ $max\\{q,j\\}$ (Fig 7) $-min\\{p,k\\}$ $0<p\leq n$, $q>n$
$max\\{p,i,j\\}+1$ $n+1$ $n-min\\{p,i,k\\}+1$ $max\\{p,i,j\\}$ (Fig 8)
$-min\\{p,i,k\\}+1$ $p,q>n$ $max\\{i,j\\}+2$ $n+2$ $n-min\\{i^{\prime},k\\}+2$
$max\\{i,j\\}$ (Fig 9) $-min\\{i^{\prime},k\\}+2$

$0$$p$$q$$k$$j$$n$ Figure 7:  $0$$p$$i$$q$$k$$j$$n$ Figure 8:
$0$$i^{\prime}$$p$$i$$q$$k$$j$$n$ Figure 9:

From Case 1 and 2, we conclude that

$D_{2}(\mathcal{C})^{\prime}[\\{k,j\\}]=D_{2}(\mathcal{C})^{\prime}[\\{0,j\\}]-D_{2}(\mathcal{C})^{\prime}[\\{0,n\\}]+D_{2}(\mathcal{C})^{\prime}[(k,n)].$

The proof is complete. ∎

######  Lemma 6.

Let $\\{k,j\\}\in X^{c}$. Suppose $0<k\leq n$, $j>n$ and $j$ is adjacent to
vertex $i$ of $P_{n}$. If $k<i$, then

$D_{2}(\mathcal{C})^{\prime}[\\{k,j\\}]=D_{2}(\mathcal{C})^{\prime}[\\{0,j\\}]-D_{2}(\mathcal{C})^{\prime}[\\{0,n\\}]+D_{2}(\mathcal{C})^{\prime}[(k,n)].$

###### Proof.

Without loss of generality we assume $k<j$. We consider the following two
cases.

  1. 1.

Suppose $\\{p,q\\}\in X$. Then

$\\{p,q\\}$ $D_{2}(\mathcal{C})^{\prime}[\\{0,j\\}]$
$D_{2}(\mathcal{C})^{\prime}[\\{0,n\\}]$ $D_{2}(\mathcal{C})^{\prime}[(k,n)]$
$D_{2}(\mathcal{C})^{\prime}[\\{k,j\\}]$ $\\{0,l\\}$, $0<l\leq n$
$max\\{l,i\\}+1$ $n$ $n$ $max\\{l,i\\}+1$ (Fig 10) $\\{l,n\\}$, $0<l<n$ $n+1$
$n$ $n-min\\{l,k\\}$ $n-min\\{l,k\\}+1$ (Fig 10) $\\{0,l\\}$, $l>n$
$max\\{l^{\prime},i\\}+|\\{l,j\\}|$ $n+1$ $n+1$
$max\\{l^{\prime},i\\}+|\\{l,j\\}|$ (Fig 11)

$0$$l$$k$$i$$j$$n$ Figure 10:  $0$$l^{\prime}$$l$$k$$i$$j$$n$ Figure 11:

  2. 2.

Suppose $\\{p,q\\}\in X^{c}$. Without loss of generality we assume $p<q$. Now,

$\\{p,q\\}$ $D_{2}(\mathcal{C})^{\prime}[\\{0,j\\}]$
$D_{2}(\mathcal{C})^{\prime}[\\{0,n\\}]$ $D_{2}(\mathcal{C})^{\prime}[(k,n)]$
$D_{2}(\mathcal{C})^{\prime}[\\{k,j\\}]$ $0<p,q<n$ $max\\{q,i\\}$ $n$
$n-min\\{p,k\\}$ $max\\{q,i\\}$ (Fig 12) +1 $-min\\{p,k\\}+1$ $0<p\leq n$,
$q>n$ $max\\{p,q^{\prime},i\\}$ $n+1$ $n-min\\{p,q^{\prime},k\\}$
$max\\{p,q^{\prime},i\\}$ (Fig 13) +$|\\{q,j\\}|$ $+1$
$-min\\{p,q^{\prime},k\\}+|\\{q,j\\}|$ $p,q>n$ $max\\{q^{\prime},i\\}$ $n+2$
$n-min\\{p^{\prime},k\\}$ $max\\{q^{\prime},i\\}$ (Fig 14) $+|\\{p,q,j\\}|$
$+2$ $-min\\{p^{\prime},k\\}+|\\{p,q,j\\}|$

$0$$p$$q$$k$$i$$j$$n$ Figure 12:  $0$$p$$q^{\prime}$$q$$k$$i$$j$$n$ Figure 13:
$0$$p^{\prime}$$p$$q^{\prime}$$q$$k$$i$$j$$n$ Figure 14:

From Case 1 and 2, we conclude that

$D_{2}(\mathcal{C})^{\prime}[\\{k,j\\}]=D_{2}(\mathcal{C})^{\prime}[\\{0,j\\}]-D_{2}(\mathcal{C})^{\prime}[\\{0,n\\}]+D_{2}(\mathcal{C})^{\prime}[(k,n)].$

This completes the proof. ∎

######  Lemma 7.

Let $\\{k,j\\}\in X^{c}$. Suppose $0<k\leq n$, $j>n$ and $j$ is adjacent to
vertex $i$ of $P_{n}$. If $k\geq i$, then

$\displaystyle D_{2}(\mathcal{C})^{\prime}[\\{k,j\\}]$
$\displaystyle=D_{2}(\mathcal{C})^{\prime}[\\{0,j\\}]-D_{2}(\mathcal{C})^{\prime}[\\{0,n\\}]+D_{2}(\mathcal{C})^{\prime}[\\{i,n\\}]$
$\displaystyle~{}~{}~{}+D_{2}(\mathcal{C})^{\prime}[\\{0,k\\}]-D_{2}(\mathcal{C})^{\prime}[\\{0,i\\}].$

###### Proof.

Without loss of generality, we assume $k<j$. We consider the following two
cases.

  1. 1.

Suppose $\\{p,q\\}\in X$. We compute the following.

$\\{p,q\\}$ $D_{2}(\mathcal{C})^{\prime}[\\{0,j\\}]$
$D_{2}(\mathcal{C})^{\prime}[\\{0,n\\}]$
$D_{2}(\mathcal{C})^{\prime}[\\{i,n\\}]$
$D_{2}(\mathcal{C})^{\prime}[\\{0,k\\}]$ $\\{0,l\\}$, $0<l\leq n$
$max\\{l,i\\}+1$ $n$ $n$ $max\\{l,k\\}$ (Fig 15) $\\{l,n\\}$, $0<l<n$ $n+1$
$n$ $n-min\\{l,i\\}$ $n$ (Fig 15) $\\{0,l\\}$, $l>n$
$max\\{l^{\prime},i\\}+|\\{l,j\\}|$ $n+1$ $n+1$ $max\\{l^{\prime},k\\}+1$ (Fig
16)

$0$$l$$k$$i$$j$$n$ Figure 15:  $0$$l^{\prime}$$l$$k$$i$$j$$n$ Figure 16:

$\\{p,q\\}$ | $D_{2}(\mathcal{C})^{\prime}[\\{0,i\\}]$ | $D_{2}(\mathcal{C})^{\prime}[\\{k,j\\}]$
---|---|---
$\\{0,l\\}$, $0<l\leq n$ | $max\\{l,i\\}$ | $max\\{l,k\\}+1$
(Fig 15) |  |
$\\{l,n\\}$, $0<l<n$ | $n$ | $n-min\\{l,i\\}+1$
(Fig 15) |  |
$\\{0,l\\}$, $l>n$ | $max\\{l^{\prime},i\\}+1$ | $max\\{l^{\prime},k\\}+|\\{l,j\\}|$
(Fig 16) |  |

  2. 2.

Suppose $\\{p,q\\}\in X^{c}$. Without loss of generality, we assume $p<q$. So,
we have

$0$$p$$q$$k$$i$$j$$n$ Figure 17:

$\\{p,q\\}$ $D_{2}(\mathcal{C})^{\prime}[\\{0,j\\}]$
$D_{2}(\mathcal{C})^{\prime}[\\{0,n\\}]$
$D_{2}(\mathcal{C})^{\prime}[\\{i,n\\}]$
$D_{2}(\mathcal{C})^{\prime}[\\{0,k\\}]$ $0<p,q<n$ $max\\{q,i\\}$ $n$
$n-min\\{p,i\\}$ $max\\{q,k\\}$ (Fig 17) +1 $0<p\leq n$, $q>n$
$max\\{p,q^{\prime},i\\}$ $n+1$ $n-min\\{p,q^{\prime},i\\}$
$max\\{p,q^{\prime},k\\}+1$ (Fig 18) +$|\\{q,j\\}|$ $+1$ $p,q>n$
$max\\{q^{\prime},i\\}$ $n+2$ $n-min\\{p^{\prime},i\\}$
$max\\{q^{\prime},k\\}+2$ (Fig 19) $+|\\{p,q,j\\}|$ $+2$

$0$$p$$q^{\prime}$$q$$k$$i$$j$$n$ Figure 18:
$0$$p^{\prime}$$p$$q^{\prime}$$q$$k$$i$$j$$n$ Figure 19:

$\\{p,q\\}$ | $D_{2}(\mathcal{C})^{\prime}[\\{0,i\\}]$ | $D_{2}(\mathcal{C})^{\prime}[\\{k,j\\}]$
---|---|---
$0<p,q<n$ | $max\\{q,i\\}$ | $max\\{q,k\\}-min\\{p,i\\}+1$
(Fig 17) |  |
$0<p\leq n$, $q>n$ | $max\\{p,q^{\prime},i\\}+1$ | $max\\{p,q^{\prime},k\\}-min\\{p,q^{\prime},i\\}+|\\{q,j\\}|$
(Fig 18) |  |
$p,q>n$ | $max\\{q^{\prime},i\\}+2$ | $max\\{q^{\prime},k\\}-min\\{p^{\prime},i\\}+|\\{p,q,j\\}|$
(Fig 19) |  |

From Case 1 and 2, we conclude that

$\displaystyle D_{2}(\mathcal{C})^{\prime}[\\{k,j\\}]$
$\displaystyle=D_{2}(\mathcal{C})^{\prime}[\\{0,j\\}]-D_{2}(\mathcal{C})^{\prime}[\\{0,n\\}]+D_{2}(\mathcal{C})^{\prime}[\\{i,n\\}]$
$\displaystyle~{}~{}~{}+D_{2}(\mathcal{C})^{\prime}[\\{0,k\\}]-D_{2}(\mathcal{C})^{\prime}[\\{0,i\\}].$

The proof is complete. ∎

######  Lemma 8.

Let $\\{k,j\\}\in X^{c}$. Suppose $k,j>n$. If $j$ is adjacent to vertex $i$ of
$P_{n}$ and $k$ is adjacent to vertex $k^{\prime}$ of $P_{n}$, then

$\displaystyle D_{2}(\mathcal{C})^{\prime}[\\{k,j\\}]$
$\displaystyle=D_{2}(\mathcal{C})^{\prime}[\\{0,j\\}]-D_{2}(\mathcal{C})^{\prime}[\\{0,n\\}]+D_{2}(\mathcal{C})^{\prime}[\\{k^{\prime},n\\}]$
$\displaystyle~{}~{}~{}+D_{2}(\mathcal{C})^{\prime}[\\{0,k\\}]-D_{2}(\mathcal{C})^{\prime}[(0,k^{\prime})].$

###### Proof.

Without loss of generality, we assume $k<j$. We consider the following two
cases.

  1. 1.

If $\\{p,q\\}\in X$, then

$\\{p,q\\}$ $D_{2}(\mathcal{C})^{\prime}[\\{0,j\\}]$
$D_{2}(\mathcal{C})^{\prime}[\\{0,n\\}]$
$D_{2}(\mathcal{C})^{\prime}[\\{k^{\prime},n\\}]$
$D_{2}(\mathcal{C})^{\prime}[\\{0,k\\}]$ $\\{0,l\\}$, $0<l\leq n$
$max\\{l,i\\}+1$ $n$ $n$ $max\\{l,k^{\prime}\\}+1$ (Fig 20) $\\{l,n\\}$,
$0<l<n$ $n+1$ $n$ $n-min\\{l,k^{\prime}\\}$ $n+1$ (Fig 20) $\\{0,l\\}$, $l>n$
$max\\{l^{\prime},i\\}+|\\{l,j\\}|$ $n+1$ $n+1$
$max\\{l^{\prime},k^{\prime}\\}+|\\{l,k\\}|$ (Fig 21)

$0$$l$$k^{\prime}$$k$$i$$j$$n$ Figure 20:
$0$$l^{\prime}$$l$$k^{\prime}$$k$$i$$j$$n$ Figure 21:

$\\{p,q\\}$ | $D_{2}(\mathcal{C})^{\prime}[(0,k^{\prime})]$ | $D_{2}(\mathcal{C})^{\prime}[\\{k,j\\}]$
---|---|---
$\\{0,l\\}$, $0<l\leq n$ | $max\\{l,k^{\prime}\\}$ | $max\\{l,i\\}+2$
(Fig 20) |  |
$\\{l,n\\}$, $0<l<n$ | $n$ | $n-min\\{l,k^{\prime}\\}+2$
(Fig 20) |  |
$\\{0,l\\}$, $l>n$ | $max\\{l^{\prime},k^{\prime}\\}+1$ | $max\\{l^{\prime},i\\}+|\\{l,j,k\\}|$
(Fig 21) |  |

Here, we observe the fact that $|\\{l,j\\}|+|\\{l,k\\}|-1=|\\{l,j,k\\}|$.

  2. 2.

Suppose $\\{p,q\\}\in X^{c}$. Without loss of generality, we assume $p<q$.
Now, we have

$0$$p$$q$$k^{\prime}$$k$$i$$j$$n$ Figure 22:
$0$$p$$q^{\prime}$$q$$k^{\prime}$$k$$i$$j$$n$ Figure 23:

$\\{p,q\\}$ $D_{2}(\mathcal{C})^{\prime}[\\{0,j\\}]$
$D_{2}(\mathcal{C})^{\prime}[\\{0,n\\}]$
$D_{2}(\mathcal{C})^{\prime}[\\{k^{\prime},n\\}]$
$D_{2}(\mathcal{C})^{\prime}[\\{0,k\\}]$ $0<p,q<n$ $max\\{q,i\\}$ $n$
$n-min\\{p,k^{\prime}\\}$ $max\\{q,k^{\prime}\\}+1$ (Fig 22) +1 $0<p\leq n$,
$q>n$ $max\\{p,q^{\prime},i\\}$ $n+1$ $n-min\\{p,q^{\prime},k^{\prime}\\}$
$max\\{p,q^{\prime},k^{\prime}\\}$ (Fig 23) +$|\\{q,j\\}|$ $+1$ $+|\\{q,k\\}|$
$p,q>n$ $max\\{q^{\prime},i\\}$ $n+2$ $n-min\\{p^{\prime},k^{\prime}\\}$
$max\\{q^{\prime},k^{\prime}\\}$ (Fig 24) $+|\\{p,q,j\\}|$ $+2$
$+|\\{p,q,k\\}|$

$0$$p^{\prime}$$p$$q^{\prime}$$q$$k^{\prime}$$k$$i$$j$$n$ Figure 24:

$\\{p,q\\}$ | $D_{2}(\mathcal{C})^{\prime}[(0,k^{\prime})]$ | $D_{2}(\mathcal{C})^{\prime}[\\{k,j\\}]$
---|---|---
$0<p,q<n$ | $max\\{q,k^{\prime}\\}$ | $max\\{q,i\\}-min\\{p,k^{\prime}\\}+2$
(Fig 22) |  |
$0<p\leq n$, $q>n$ | $max\\{p,q^{\prime},k^{\prime}\\}+1$ | $max\\{p,q^{\prime},i\\}-min\\{p,q^{\prime},k^{\prime}\\}+|\\{q,j,k\\}|$
(Fig 23) |  |
$p,q>n$ | $max\\{q^{\prime},k^{\prime}\\}+2$ | $max\\{q^{\prime},i\\}-min\\{p^{\prime},k^{\prime}\\}+|\\{p,q,j,k\\}|$
(Fig 24) |  |

Here, we note that $|\\{q,j\\}|+|\\{q,k\\}|-1=|\\{q,j,k\\}|$ and
$|\\{p,q,j\\}|+|\\{p,q,k\\}|-2=|\\{p,q,j,k\\}|$.

From Case 1 and 2, we conclude that

$\displaystyle D_{2}(\mathcal{C})^{\prime}[\\{k,j\\}]$
$\displaystyle=D_{2}(\mathcal{C})^{\prime}[\\{0,j\\}]-D_{2}(\mathcal{C})^{\prime}[\\{0,n\\}]+D_{2}(\mathcal{C})^{\prime}[\\{k^{\prime},n\\}]$
$\displaystyle~{}~{}~{}+D_{2}(\mathcal{C})^{\prime}[\\{0,k\\}]-D_{2}(\mathcal{C})^{\prime}[(0,k^{\prime})].$

The proof is complete. ∎

Now, we state and prove the main result of this paper.

######  Theorem 3.

Let $\mathcal{C}$ be a caterpillar graph on $N$ vertices and let
$D_{2}(\mathcal{C})$ be its $2-$ Steiner distance matrix. Then

${\rm rank}(D_{2}(\mathcal{C}))=2N-p-1,$

where $p$ denotes the number of pendant vertices of $\mathcal{C}$.

###### Proof.

Suppose $\mathcal{C}$ is labelled as described in Figure 4. Using Lemma 5-8,
we conclude that

${\rm rank}(D_{2}(\mathcal{C}))=2n-1+\sum_{j=1}^{n-1}i_{j},$

Since

$\displaystyle 2N-p-1$
$\displaystyle=2(n+1+\sum_{j=1}^{n-1}i_{j})-(\sum_{j=1}^{n-1}i_{j}+2)-1$
$\displaystyle=2n-1+\sum_{j=1}^{n-1}i_{j},$

the proof is complete. ∎

We conclude this paper with the following open problem. Open Problem: If $T$
is a general tree on $n$ vertices, find $\mathop{\rm rank}(D_{2}(T))$.

## Acknowledgement

The second author acknowledges the support of the Indian National Science
Academy under the INSA Senior Scientist scheme.

## References

  * [1] Y. Mao, Steiner distance in graphs–a survey (2017).  arXiv:1708.05779.
  * [2] R. Graham, L. Lovász, Distance matrix polynomials of trees, Advances in Mathematics 29 (1) (1978) 60–88.  doi:10.1016/0001-8708(78)90005-1.
  * [3] R. Bapat, S. Kirkland, M. Neumann, On distance matrices and laplacians, Linear Algebra and its Applications 401 (2005) 193–209.  doi:10.1016/j.laa.2004.05.011.
  * [4] R. Bapat, S. Sivasubramanian, Inverse of the distance matrix of a block graph, Linear and Multilinear Algebra 59 (12) (2011) 1393–1397.  doi:10.1080/03081087.2011.557374.
  * [5] R. Balaji, R. Bapat, S. Goel, An inverse formula for the distance matrix of a wheel graph with an even number of vertices, Linear Algebra and its Applications 610 (2021) 274 – 292.  doi:https://doi.org/10.1016/j.laa.2020.10.003.
  * [6] R. Balaji, R. B. Bapat, S. Goel, On distance matrices of wheel graphs with an odd number of vertices, Linear and Multilinear Algebra (2020) 1–32doi:10.1080/03081087.2020.1840499.
  * [7] S. Goel, On distance matrices of helm graphs obtained from wheel graphs with an even number of vertices, Linear Algebra and its Applications 621 (2021) 86–104.  doi:https://doi.org/10.1016/j.laa.2021.03.008.

Ali Azimi
Department of Mathematics, University of Neyshabur, Neyshabur, Iran
E-mail address<EMAIL_ADDRESS>

R.B. Bapat
Theoretical Statisticsand Mathematics Unit, Indian Statistical Institute,
Delhi, India
E-mail address<EMAIL_ADDRESS>

Shivani Goel
Department of Mathematics, IISc Bangalore, Bangalore, India.
E-mail address<EMAIL_ADDRESS>


# MoRSE: Deep Learning-based Arm Gesture Recognition for Search and Rescue
Operations

Panagiotis Kasnesis  Electrical and Electronics Engineering
University of West Attica
Egaleo, Greece
<EMAIL_ADDRESS>Christos Chatzigeorgiou  Electrical and Electronics
Engineering
University of West Attica
Egaleo, Greece
<EMAIL_ADDRESS>Dimitrios G. Kogias  Electrical and Electronics Engineering
University of West Attica
Egaleo, Greece
<EMAIL_ADDRESS>Charalampos Z. Patrikakis  Electrical and Electronics
Engineering
University of West Attica
Egaleo, Greece
<EMAIL_ADDRESS>Harris V. Georgiou  Hellenic Rescue Team of Attica (HRTA)
Athens, Greece
<EMAIL_ADDRESS>Aspasia Tzeletopoulou  Hellenic Rescue Team of Attica
(HRTA)
Athens, Greece
<EMAIL_ADDRESS>
###### Abstract

Efficient and quick remote communication in search and rescue operations can
be life-saving for the first responders. However, while operating on the field
means of communication based on text, image and audio are not suitable for
several disaster scenarios. In this paper, we present a smartwatch-based
application, which utilizes a Deep Learning (DL) model, to recognize a set of
predefined arm gestures, maps them into Morse code via vibrations enabling
remote communication amongst first responders. The model performance was
evaluated by training it using 4,200 gestures performed by 7 subjects (cross-
validation) wearing a smartwatch on their dominant arm. Our DL model relies on
convolutional pooling and surpasses the performance of existing DL approaches
and common machine learning classifiers, obtaining gesture recognition
accuracy above 95%. We conclude by discussing the results and providing future
directions.

###### Index Terms:

deep learning, wearable computing, gesture recognition, search and rescue

##  I Introduction

Wrist-worn devices (e.g., smartwatches and wristbands) are widely used
electronics for recording data, such as motion signals produced by embedded
motion sensors (e.g., accelerometers, gyroscopes, etc.). The wearable market
was valued at 35.36 billion EUROS in 2020 and is expected to expand at a
compound annual growth rate (CAGR) of 13.8% from 2021 to 2028 [1]. This is
mainly due to their properties of being unobtrusive means of communication and
capable of monitoring their users’ vital signs [2, 3] (e.g., heart rate),
emotions [4], daily activities [5], etc.

Over the last few years, common Machine Learning (ML) and Deep Learning (DL)
techniques have been applied broadly and successfully to recognize the
gestures and activities performed by users wearing electronic devices, thus,
they are exploited for effective gesture-based human-machine interaction [6].
In particular, ML/DL applications have been used to several domains, such as
smart homes [7] to recognize gestures and send the corresponding commands to
the home automation platform [8, 9], smart factories assisting workers in
performing preventive and corrective machine maintenance [10], gesture-based
UAV control [11], automotive [12], even empowering physical security [13].

Regarding physical security, arm signals are internationally used in several
field operations, ranging from military services, firefighters, coast guards,
lifeguards, police, medical First Responders (FRs), etc. They are, also, used
in various working sectors for specialized operations such as cranes, loading
and unloading of trucks to manage speed, direction and safety procedures.
During the basic training courses, FRs learn different ways to communicate on
the field. These include audio signals, arm/hand gestures, RF communications,
visual signals and in some domains even flag signalling. In case of emergency
or degraded communications (e.g. underground) or in extremely noisy
environments (e.g. using heavy machinery during victim extrication), FRs on
Search and Rescue (SaR) operations (e.g., emergency medical services or
emergency medical technicians) should employ a common approach for gesture
communication [14]. However, in these cases at least one member of the SaR
team should keep the FR performing the gesture in view.

In the current paper we propose MoRSE (arM Movement Recognition for firSt
rEsponders), which is an application that is deployed in the smartwatches of
the FRs in SaR operations to capture and identify arm gestures exploiting a
deep Convolutional Neural Network (CNN). In particular, 5 Gestures of Interest
(GoI) have been selected, that, if a FR performs one of them a non-visual/non-
audible message, is sent to the corresponding FR member of his/her team,
through vibrations on his/her smartwatch device. To this end, we built MoRSE
dataset to train the DL model and deploy it, afterwards, to smartwatches, to
classify in real-time incoming motion signals to predefined gestures.

In the next section related works regarding wearable-based gesture recognition
for improving public safety are presented. Section 3 describes the developed
application, providing explanation on selecting the 5 GoI and introduces the
architecture of the selected algorithm. The collected MoRSE dataset is
described in section 4 and demonstrates the obtained results. Finally, section
5 concludes the paper discussing future steps.

##  II Related works

In the current section, we report mobile/wearable approaches that have been
proposed in the literature for empowering public safety and are based on
machine learning (ML) techniques. Moreover, these works exploit Inertial
Measurement Unit (IMU) sensors to classify the arm/hand gestures and the
activities explicitly (i.e., the users perform them intentionally for
notification purposes), or implicitly where the system identifies the
situation they are in.

Car accident detection based on motion sensor data is an ML task that has been
explored in several works [15][16][17]. In [15] the authors exploit the
smartphone sensors to provide situational awareness to emergency responders;
they rely on GPS and accelerometer sensors to resist false positives and
discuss how smartphone-based accident detection reduces traffic congestion and
increases the preparedness of emergency responders. On the other hand, Goel et
al. [17] try to detect the driver’s distraction into order to prevent
accidents and increase road safety. In their experiment, they achieved
promising results using a driving simulator and 16 adult subjects that were
asked to wear on their wrist a smart device equipped with an accelerometer and
a gyroscope. Similar work was done by Tavacoli et al. [18], however, the
authors exploited more sensor modalities (e.g., Photoplethysmogram) and
executed their experiments in the wild. In addition to this, distraction has
been evaluated, also, from the pedestrian perspective [19], where a novel
complex activity recognition framework called DFAM was designed exploiting
motion data from the users’ mobile and wearable devices and evaluated against
several baseline classifiers (i.e., k-NN, random forests, decision trees,
naïve Bayes, support vector machines).

Gunshot recognition has been explored in [20][21]. In [20] logistic regression
is used to identify patterns on wrist movements to detect gunshots based on
wearable sensors data; it obtained 99.4% in terms of classification accuracy
when tested against a hold-out sample of observations. A more complex gunshot
detection task is presented in [21], where the machine learning (ML) algorithm
should identify various categories of firearms (i.e., handgun, rifle, shotgun)
and recognize whether a firearm is autoloaded or manual. The best results were
obtained using a decision trees classifier.

Fall detection based on mobile or wearable devices is also a well-investigated
computer task [22][23]. Fall detection is considered to be crucial in the case
of the elderly people, since falls may lead to their hospitalization and
sometimes are fatal, thus, fast assistance is important. In [22] the authors
used a smartphone equipped with an accelerometer, magnetometer and gyroscope
sensors and obtained up to 93% for specificity and 100% for sensitivity. The
work introduced in [23] focuses on reducing false alarms (i.e., false
positives) using the accelerometer data of a smartwatch.

Finally, incident reporting through the use of gestures is reported in [13].
The authors proposed and evaluated an incident reporting application that can
be deployed on smartwatches and uses a late sensor fusion deep CNN model to
recognise gestures. This technique allows citizens to report hazardous events
using discreet arm signals to alert the law enforcement agents. The proposed
approach was evaluated using a dataset the authors build and managed to
produce accuracy above 98% and F1-score over 97%.

##  III MoRSE application

In the current section we introduce MoRSE application, describing in detail
the selected GoI, the examined DL and ML algorithms used for recognizing them
and, finally, the communication pipeline and mapping to Morse code (Figure 1).

Figure 1: MoRSE data processing and communication pipeline. Arm gesture is
performed by a FR (Responder A) it is recognized at his/her smartwatch, and
transmitted to his/her colleague’s (Responder B) smartwatches and translated
into Morse code using vibrations.

###  III-A Selected hand signals

For our solution, four widely used arm/hand signals taken from airport ground
control operations [24] were selected as emergency arm signals to be used in
such an automated procedure. They are widely known and easy to perform for
every FR on the field, almost under any condition. Additionally, a fifth hand
signal was developed to indicate an FR in distress/emergency.

These five signals cover the situations of:

Figure 2: Illustrations of the 5 selected Emergency Arm Signals [24].

  1. 1.

Recommended Evacuation (RE). A back and forth movement of the arm indicates
emergency evacuation (Figure 2b).

  2. 2.

Recommended Stop (RS). An “X” is made with the hands above the head indicates
stop activities or stop works in progress, including evacuation, if in
progress (Figure 2b).

  3. 3.

Fire (F) A movement in the shape of number 8 performed with the hand that the
smartwatch is on indicates fire alert (Figure 2c).

  4. 4.

Emergency Contained (EC). It means that activities can be resumed indicating
“all clear” and it is shown with arms extended outwards and down until wrist
crossed and backwards at 45-degree angle (Figure 2d).

  5. 5.

Distress (DS). The last signal is repeatedly rotating movements of the wrist
(leftwards and rightwards) and indicates a FR in distress. This movement is
chosen because it can be performed in emergency situations in very confined
spaces which is a common place for an FR to be, e.g. inside narrow tunnels,
vertical ascend/descend in elevator shafts, crawling under semi-collapsed
structures, etc. (Figure 2e).

The rationale behind the selection of these five hand signals is based on the
fact that they differ from each other significantly in timing and spatial
movement, thus it is difficult to be misinterpreted. Furthermore, they can be
performed in places where there is limited space, or the body position of the
FR permits only limited movement. During a massive disaster event, the number
of FRs operating on the field varies from a few tenths to hundreds, from
different operational fields (e.g., police, USAR, medics, civil protection)
and perhaps different countries. Hence, arm signals must be as clear as
possible and at the same time easy for FRs to learn and perform. It has been
shown that arm signals used internationally in airport ground control are
ideal candidates for such use. Regarding the fifth arm signal (distress), it
is expected that FR many times find themselves in need of immediate
assistance. Thus, such an arm signal that can be easily performed in very
confined spaces can be lifesaving. Finally, we should mentioned that an extra
movement called ”random” was recorded including a high variance of arm
movements not belonging to any of the aforementioned classes (see section IV).

###  III-B Selected algorithms

The proposed network, is a lightweight deep CNN in order to be deployed on the
smartwatch (i.e., contains around 55,000 parameters). Its architecture is very
similar to previously developed deep CNN [25], and consists of the following
layers:

  * •

layer 1: 12 convolutional filters with a size of (1,11), i.e., W1 has shape
(1, 11, 1, 12). This is followed by a ReLU activation function, a (1,4)
strided pooling operation and a dropout probability equal to 0.5.

  * •

layer 2: 24 convolutional filters with a size of (1,11), i.e., W2 has shape
(1, 11, 12, 24). Similar to the first layer, this is followed by a ReLU
activation function, a (1,2) strided pooling operation and a dropout
probability equal to 0.5.

  * •

layer 3: 32 convolutional filters with a size of (6,11), i.e., W3 has shape
(6, 11, 24, 32). The 2D convolution operation is followed by a ReLU activation
function, a 2D global pooling operation and a dropout probability equal to
0.5.

  * •

layer 4: 32 hidden units, i.e., W4 has shape (32,6), followed by a softmax
activation function.

Moreover, starting from the fact that a neural network can represent any
function provided it has sufficient capacity (i.e. sufficiently broad and deep
to represent the function), we examined, also, convolutional pooling (i.e., as
a pooling operation apart from max pooling) which is a biologically inspired
pooling layer modelled on strided convolutional operations [26]. It can be
imagined as the convolutional pooling gives increased weight to stronger
features and suppresses weaker features, similar to a latent space, thus, we
call it latent pooling operation; the designed deep CNN that utilizes them is
denoted from now on as CNN-lp.

The proposed deep CNN algorithms were evaluated by comparing their performance
to Convolutional LSTM [27] and conventional classifiers: Logistic Regression
(LR), k-Nearest Neighbours (k-NN), Decision Tree (DT), and Random Forest (RF).
We selected to extract only seven time-dependent features for each axis of the
accelerometer and gyroscope signals, resulting into 42 features in total,
since, they have been proven to be more robust and efficient than frequency-
dependent features in activity recognition [28]. Moreover, using too many
features in some cases decrease the accuracy [17] and result to overfitting.
The selected features over all the sensor modalities are: a) mean value, b)
minimum value, c) maximum value, d) median value, e) standard deviation, f)
skewness (i.e., degree of asymmetry of the signal distribution), and g)
kurtosis (i.e., degree of peakedness of the signal distribution).

Finally, the Convolutional LSTM architecture is very similar to that presented
in [27]. In particular, the network consists of 4 convolutional layers each
containing 32 kernels with filter size (1,5) and their output is processed by
an LSTM layer. This network contains around 29,000 parameters.

###  III-C Mobile application

The MoRSE application has been mainly developed for smartwatches, however, it
communicates also with the paired smartphone to act as a gateway to the
network in case the detected event (i.e., recognized gesture) should be sent
to a central control of operation platform.

In particular, the smartwatch features include:

  * •

Gesture recognition (uses the DL model for inference)

  * •

Location acquisition (exploits the GPS module)

  * •

Gesture scanning from nearby FRs (utilizes Bluetooth Low Energy protocol)

  * •

Translation of detected gesture to Morse code through vibrations

The gesture recognition features consumes the motion data signals produced by
the embedded 3axial accelerometer and gyroscope sensors. Every second the
collected signals are processed by the deployed DL model and the result
(captured gesture) is displayed on the smartwatch Messages screen.

In particular, the Messages screen is divided horizontally into two halves
(Figure 3). The upper half displays (with yellow letters) information about
any received message. Information includes the user ID, the gesture the user
performed and their location (if available). The lower half displays (with
green letters) the current user’s ID, the operation mode (transmitting,
recognizing) and the last recognized gesture along with the relative time and
the confidence of the recognition.

Figure 3: Messages screen in smartwatch.

Moreover, when a gesture is detected, it is broadcasted for 10 seconds to
nearby FRs using Bluetooth Low Energy (BLE), while the users can also scan
messages broadcasted from nearby FRs manually (exploiting BLE) by pressing the
corresponding button. Message transmission is performed if all of the
following are true:

  * •

A gesture is not Rnd (Random)

  * •

Another gesture is not currently being transmitted

  * •

The captured gesture is different than the previous.

The user will be notified with a notification in the smartwatch stating that
transmission has been initiated. If the device is going to be operated in a
closed space (e.g., building), location tracking has to be disabled in the
application’s settings. Location information is acquired from the GPS, and
gesture transmission happens after the device gets the location. However, in
closed spaces, location acquisition is almost always impossible since there is
no line of sight with the GPS satellites. Therefore, the device will never get
the location and will never transmit the gesture.

When a message is received from nearby FRs, the device vibrates several times
depending on the gesture pattern as shown in Table I. This is a a very
important functionality enabling a wide range of messages via Morse code,
which is a hands-free, non-verbal way of communication, provided that the FR
is trained on it. In particular, each ”.” symbol is translated into a 200ms
vibration, the ”-” symbol into 400ms vibration, while the space (i.e., no
symbol) is mapped into 400ms of no vibration.

TABLE I: Vibration patterns depending on the recognized gesture. Gesture | Morse code
---|---
Recommended Stop | .-. …
Emergency Contained | . -.-.
Recommended Evacuation | .-. .
Fire | ..-.
Distress | -.. …

##  IV Results

In this section we present the collected MoRSE dataset, the experimental
results and provide a discussion on them.

###  IV-A Dataset

For the purpose of this research, a dataset that includes the aforementioned
Gestures of Interest (GoI) performed by 5 subjects has been collected. In
particular, the participants were asked to wear a FOSSIL GEN 5 smartwatch, on
the wrist of the arm they performed the moves and annotated them using the
MoRSE data collection/annotation mobile application. Moreover, the subjects
were asked to perform, except from the 5 GoI, some everyday life movements by
acting naturally (e.g., do computer work, walking, scratching head etc.) while
they wore the device, constituting the sixth class (denoted as random) in our
classification scheme.

The MoRSE dataset consists of GoI performed by 7 subjects; contains around
4,200 data samples (approximately 600 for each class), which are 5-second
segments including data values from the 3-axial gyroscopes and accelerometers
of the smartwatch. It should be noted that the average sampling rate for both
motion sensors is approximately 50 Hz, thus, each segment contains 250 values
for each modality. In order to obtain subject dependent results, we used a
7-fold cross-validation technique and split our dataset into a training set
containing 5 subjects, a validation set and a test set containing 1 subject.
Finally, each sensor signal’s values were normalized by subtracting the mean
value and dividing by the standard deviation. Table II presents the
distribution of the collected gestures per subject.

TABLE II: Distribution of the performed gestures per subject. Subject No | Hand | Rnd | SA | RA | E | Fire | Distress
---|---|---|---|---|---|---|---
1 | Left | 100 | 100 | 100 | 100 | 100 | 101
2 | Right | 100 | 100 | 100 | 100 | 100 | 100
3 | Right | 100 | 71 | 101 | 99 | 99 | 100
4 | Right | 100 | 100 | 100 | 100 | 100 | 100
5 | Right | 100 | 100 | 101 | 101 | 106 | 115
6 | Left | 100 | 103 | 102 | 102 | 101 | 101
7 | Left | 100 | 100 | 100 | 100 | 100 | 100

###  IV-B Experimental results

The ML experiments were executed on a computer workstation equipped with an
NVIDIA GTX 1080Ti GPU, which has 11 gigabytes RAM, 3584 CUDA cores, and a
bandwidth of 484 GB/s. Python was used as programming language, and
specifically the Numpy for matrix multiplications, data pre-processing,
segmentation and the Tensorflow 2.0 framework for developing the neural
networks. In order to accelerate the tensor multiplications, CUDA Toolkit in
support with the cuDNN was used, which is the NVIDIA GPU-accelerated library
for deep neural networks. The software is installed on a 18.04 Ubuntu Linux
operating system.

The model was trained using the Adam optimizer [29] with the following hyper-
parameters: learning rate =0.001, beta1 = 0.9, beta2 = 0.999, epsilon=1e-08,
decay=0.0. Moreover, we set the minimum number of epochs to 2000; however, the
training procedure terminated automatically whether the best training accuracy
had improved or not, after a threshold of 200 epochs. The training epoch that
achieved the lowest error rate on the validation set was saved, and its
filters were used to obtain the accuracy of the model on the test set.

Table III presents the accuracy results that were obtained by applying the
aforementioned algorithms to our dataset. The best accuracy was achieved by
the developed deep CNN-lp model (95.27%), which utilizes the latent pooling
layer and surpassed (by a lot) the developed architecture relying on max
pooling (i.e., deep CNN). It is, also, worth mentioning that the presented
results are the average values of the 5 runs that were executed for each fold.
In addition to this, Figure 4 shows the box plots of the obtained results,
with KNN having the biggest deviation in terms of accuracy among the 7
subjects and Deep CNN-lp the smallest one, making it more robust and reliable
in real-world applications.

TABLE III: Performance of each ML model on the MoRSE dataset. Method Name | Accuracy
---|---
LR | 88.59%
KNN | 88.03%
DT | 84.78%
RF | 91.34%
Convolutional LSTM | 90.83%
Deep CNN | 91.90%
Deep CNN-lp | 95.27%

Figure 4: The performance, in terms of accuracy, of the developed machine
learning algorithms.

Figure 5 presents the confusion matrix obtained using deep CNN-lp. It is
observable that around 5% of the performed GoIs were misclassified into Random
(R), probably due to the fact that many arm movements that were close to them
were added to the dataset to increase the model’s robustness to false
positives. Furthermore, 2.69% of the Recommend Evacuation (RE) gestures were
classified as distress signals and almost 2% of Fire (F) indications were
falsely identified as RE and Emergency Contained (EC). It should be noted that
the EC gesture produced the best F1-score (98.21%).

Figure 5: Plots displaying: The confusion matrix of the deep CNN-lp.

Figure 6 displays the property of latent pooling towards paying more attention
on the most import feature, and, more specifically an example of this effect
that takes place on the X-axis of a recommended evacuation signal. It is
observable that the values produced in the first 1.5 seconds where the subject
lifted his/her arm are set to zero (i.e., they are discarded), while emphasis
is given the last seconds that include the back and forth arm movement.

Figure 6: Visualization of the accelerometer X-axis outputs produced by the
1st kernel map of the 2nd convolutional layer (a) and the 2nd latent pooling
operation (b). The dislayed signal presents a recommended evacuation gesture.

One of the drawbacks of the proposed approach is its size against the other
evaluated methods. The latent pooling increases the number of parameters (
2,000 more parameters) and consequently its latency. More specific, inference
time is around 68 ms on FOSSIL GEN 5 smartwatch, while the max pooling
approach around 63 ms. Furthermore, having a closer look at the confusion
matrix and projecting its results on an one hour SaR operation it leads to
around 176 false positives. Thus, an error analysis based on ROC and AUC
curves should be done to alter the GoI detection thresholds.

##  V Conclusion

One of the major issues for FR is their safety, for both the victims and the
FRs who operate inside the disaster area. Arm gesture recognition technology
with the use of smartwatch can improve remote communications and coordination
of FR teams. To this end, we developed MoRSE smartwatch application that
exploits a DL model trained over a collected dataset of arm gestures used in
airport ground control operations. The proposed deep CNN architecture was
evaluated against several DL and ML algorithms, obtaining accuracy over 95%.

Future steps include MoRSE evaluation in real-world SaR operations.
Furthermore, model optimization techniques (e.g., quantization or knowledge
distillation [30]) could be applied to decrease the model’s inference time,
while modality-wise relational reasoning [31] will be examined for more
effective sensor fusion. Finally, a usability study provided by FRs should
also be helpful to improve the smartwatch application.

## Acknowledgment

This research was funded by the European Commission’s H2020 programme under
project FASTER, grant number 833507.

## References

  * [1] “Fitness tracker market size,” June 2022. [Online]. Available: https://www.fortunebusinessinsights.com/fitness-tracker-market-103358
  * [2] A. Reiss, I. Indlekofer, P. Schmidt, and K. V. Laerhoven, “Deep ppg: Large-scale heart rate estimation with convolutional neural networks,” _Sensors (Basel, Switzerland)_ , vol. 19, 2019.
  * [3] A. Burrello, D. J. Pagliari, M. Risso, S. Benatti, E. Macii, L. Benini, and M. Poncino, “Q-ppg: Energy-efficient ppg-based heart rate monitoring on wearable devices,” _IEEE Transactions on Biomedical Circuits and Systems_ , vol. 15, pp. 1196–1209, 2021.
  * [4] P. Schmidt, A. Reiss, R. Dürichen, C. Marberger, and K. V. Laerhoven, “Introducing wesad, a multimodal dataset for wearable stress and affect detection,” _Proceedings of the 20th ACM International Conference on Multimodal Interaction_ , 2018.
  * [5] A. Stisen, H. Blunck, S. Bhattacharya, T. S. Prentow, M. B. Kjærgaard, A. K. Dey, T. Sonne, and M. M. Jensen, “Smart devices are different: Assessing and mitigatingmobile sensing heterogeneities for activity recognition,” _Proceedings of the 13th ACM Conference on Embedded Networked Sensor Systems_ , 2015.
  * [6] P. Zhu, H. Zhou, S. Cao, P. Yang, and S. Xue, “Control with gestures: A hand gesture recognition system using off-the-shelf smartwatch,” _2018 4th International Conference on Big Data Computing and Communications (BIGCOM)_ , pp. 72–77, 2018.
  * [7] G. Laput, R. Xiao, and C. Harrison, “Viband: High-fidelity bio-acoustic sensing using commodity smartwatch accelerometers,” _Proceedings of the 29th Annual UIST_ , 2016.
  * [8] M. M. Luna, T. P. Carvalho, F. Soares, H. A. D. Nascimento, and R. M. da Costa, “Wrist player: A smartwatch gesture controller for smart tvs,” _2017 IEEE 41st Annual Computer Software and Applications Conference (COMPSAC)_ , vol. 02, pp. 336–341, 2017.
  * [9] T. H. Nascimento, F. Soares, H. A. D. Nascimento, M. A. Vieira, T. P. Carvalho, and W. F. de Miranda, “Netflix control method using smartwatches and continuous gesture recognition,” _2019 IEEE CCECE_ , pp. 1–4, 2019.
  * [10] V. Villani, L. Sabattini, N. Battilani, and C. Fantuzzi, “Smartwatch-enhanced interaction with an advanced troubleshooting system for industrial machines,” 2016.
  * [11] Y. Choi, I. Hwang, and S. Oh, “Wearable gesture control of agile micro quadrotors,” _2017 IEEE International Conference on MFI_ , pp. 266–271, 2017\.
  * [12] K. Małecki, A. Nowosielski, and M. Kowalicki, “Gesture-based user interface for vehicle on-board system: A questionnaire and research approach,” _Applied Sciences_ , vol. 10, p. 6620, 2020.
  * [13] P. Kasnesis, C. Chatzigeorgiou, L. Toumanidis, and C. Z. Patrikakis, “Gesture-based incident reporting through smart watches,” in _2019 IEEE International Conference on PerCom Workshops_. IEEE, 2019, pp. 249–254.
  * [14] “Usar coordination handbook,” May 2022. [Online]. Available: https://www.insarag.org/wp-content/uploads/2022/05/UC-Handbook-2022.pdf
  * [15] A. F. G. G. Ferreira, D. M. A. Fernandes, A. P. Catarino, and J. L. Monteiro, “Localization and positioning systems for emergency responders: A survey,” _IEEE Communications Surveys & Tutorials_, vol. 19, no. 4, pp. 2836–2870, 2017.
  * [16] R. K. Megalingam, R. N. Nair, and S. M. Prakhya, “Wireless vehicular accident detection and reporting system,” in _2010 International Conference on Mechanical and Electrical Technology_. IEEE, 2010, pp. 636–640.
  * [17] B. Goel, A. K. Dey, P. Bharti, K. B. Ahmed, and S. Chellappan, “Detecting distracted driving using a wrist-worn wearable,” in _2018 IEEE International Conference on PerCom Workshops_. IEEE, 2018, pp. 233–238.
  * [18] A. Tavakoli, S. Kumar, M. Boukhechba, and A. Heydarian, “Driver state and behavior detection through smart wearables,” _2021 IEEE IV Symposium_ , pp. 559–565, 2021.
  * [19] N. Vinayaga-Sureshkanth, A. Maiti, M. Jadliwala, K. Crager, J. He, and H. Rathore, “Towards a practical pedestrian distraction detection framework using wearables,” in _2018 IEEE International Conference on PerCom Workshops_. IEEE, 2018, pp. 239–245.
  * [20] C. E. Loeffler, “Detecting gunshots using wearable accelerometers,” _PloS one_ , vol. 9, no. 9, p. e106664, 2014.
  * [21] M. A. A. H. Khan, D. Welsh, and N. Roy, “Firearm detection using wrist worn tri-axis accelerometer signals,” in _2018 IEEE International Conference on PerCom Workshops_. IEEE, 2018, pp. 221–226.
  * [22] I. N. Figueiredo, C. Leal, L. Pinto, J. Bolito, and A. Lemos, “Exploring smartphone sensors for fall detection,” _mUX: the journal of mobile user experience_ , vol. 5, no. 1, pp. 1–17, 2016.
  * [23] I. Maglogiannis, C. Ioannou, G. Spyroglou, and P. Tsanakas, “Fall detection using commodity smart watch and smart phone,” in _IFIP International Conference on AIAI_. Springer, 2014, pp. 70–78.
  * [24] “Emergency handsignals,” May 2021. [Online]. Available: https://www.skybrary.aero/index.php/Emergency_Hand_Signals
  * [25] P. Kasnesis, C. Z. Patrikakis, and I. S. Venieris, “Perceptionnet: a deep convolutional neural network for late sensor fusion,” in _Proceedings of SAI Intelligent Systems Conference_. Springer, 2018, pp. 101–119.
  * [26] Y. Shen, X. He, J. Gao, L. Deng, and G. Mesnil, “A latent semantic model with convolutional-pooling structure for information retrieval,” _Proceedings of the 23rd ACM CIKM_ , 2014.
  * [27] F. J. Ordóñez and D. Roggen, “Deep convolutional and lstm recurrent neural networks for multimodal wearable activity recognition,” _Sensors_ , vol. 16, no. 1, p. 115, 2016.
  * [28] D. Figo, P. C. Diniz, D. R. Ferreira, and J. M. Cardoso, “Preprocessing techniques for context recognition from accelerometer data,” _Personal and Ubiquitous Computing_ , vol. 14, no. 7, pp. 645–662, 2010.
  * [29] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.
  * [30] H. Touvron, M. Cord, M. Douze, F. Massa, A. Sablayrolles, and H. J’egou, “Training data-efficient image transformers & distillation through attention,” in _ICML_ , 2021.
  * [31] P. Kasnesis, C. Chatzigeorgiou, C. Z. Patrikakis, and M. Rangoussi, “Modality-wise relational reasoning for one-shot sensor-based activity recognition,” _Pattern Recognit. Lett._ , vol. 146, pp. 90–99, 2021.