# Dynamics of scalar-times the backward shift on analytic tridiagonal spaces

Bibhash Kumar Das  Indian Institute of Technology Bhubaneswar, Jatni Rd,
Khordha - 752050, India<EMAIL_ADDRESS>and  Aneesh Mundayadan  Indian
Institute of Technology Bhubaneswar, Jatni Rd, Khordha - 752050, India
<EMAIL_ADDRESS>
###### Abstract.

We study the backward shift operator $B$ acting on the Hilbert space
$\mathcal{H}_{a,b}$ of analytic functions on the unit disc, having an
orthonormal basis consisting of polynomials of the form
$f_{n}(z)=(a_{n}+b_{n}z)z^{n},~{}~{}n\geq 0$. We obtain necessary and
sufficient conditions for $B$ to be bounded, and prove that, under some mild
assumptions on $\\{a_{n}\\}$ and $\\{b_{n}\\}$, the operator $B$ is unitarily
equivalent to a compact perturbation of a weighted backward shift on
$\ell^{2}$. Further, we characterize the hypercyclicity, mixing, and chaos of
$\lambda B$ for a non-zero scalar $\lambda$, and establish the existence of
hypercyclic subspaces for $\lambda B$ by computing its essential spectrum. We
also provide vector valued versions of our results for $B$ when it acts on a
reproducing kernel space corresponding to matrix valued kernels.

###### Key words and phrases:

shift operator, hypercyclic, chaos, mixing operator, reproducing kernel
Hilbert space, matrix valued kernels

###### 2010 Mathematics Subject Classification:

Primary 47A16, 46E22, 32K05, 47B32; Secondary 47B37, 37A99.

###### Contents

  1. 1 Introduction
  2. 2 Boundedness of the shift operator on a tridiagonal space $\mathcal{H}_{a,b}$
  3. 3 The shift on $\mathcal{H}_{a,b}$ as a compact perturbation of a weighted shift on $\ell^{2}$
  4. 4 Hypercyclicity, mixing, and chaos
  5. 5 The shift operator on tridiagonal spaces given by matrix valued kernels
  6. 6 Concluding remarks

##  1\. Introduction

The aim of this paper is twofold, namely to realize the backward shift
operator (sometimes known as a Taylor shift)

$B\big{(}\sum_{n=0}^{\infty}\lambda_{n}z^{n}\big{)}=\sum_{n=0}^{\infty}\lambda_{n+1}z^{n},$

defined on a Hilbert space $\mathcal{H}_{a,b}$ of analytic functions on the
unit disc in the complex plane, having an orthonormal basis of the form

$\big{\\{}(a_{n}+b_{n}z)z^{n}:n\geq 0\big{\\}},$

as a compact perturbation of a weighted backward shift on the sequence space
$\ell^{2}$, and to study its linear dynamical properties. We prove that,
although the dynamics of the operator $B$ has similarities with that of a
weighted unilateral shift on $\ell^{2}$, the structure of the operator can be
quite different; see the results in the sections $3$ and $4$. Weighted shifts
have been extensively studied from the point of view of operator theory and
function theory for several decades, and we refer to Shields [32]. In linear
dynamics, they received a major attention through Godefroy and Shapiro [20],
Kitai [24] and Salas [31]. For a thorough account on the fundamentals of
linear dynamics, see the monographs by Bayart and Matheron [6] and Grosse-
Erdmann and Peris [23].

An operator $T$ on a separable Banach space $X$ is said to be hypercyclic if
there exists $x\in X$, known as a hypercyclic vector for $T$, such that the
orbit$\\{x,Tx,T^{2}x,\cdots\\}$ is dense in $X$. If a hypercyclic operator $T$
on $X$ has a dense set of periodic vectors, then $T$ is called chaotic. Recall
that a vector $y\in X$ is periodic for $T$ if its orbit under $T$ is periodic,
that is, $T^{p}y=y$ for some $p$. An operator $T$ on $X$ is said to be
topologically transitive if, for two non-empty open sets $U_{1}$ and $U_{2}$
of $X$, there exists a natural number $k$ such that $T^{k}(U_{1})\cap
U_{2}\neq\phi$. The transitivity notion is equivalent to that of
hypercyclicity, assuming the separability of the underlying Banach space $X$.
A strong form of transitivity is the topological mixing: an operator $T$ is
topologically mixing on $X$ if, for any two non-empty open sets $U_{1}$ and
$U_{2}$ of $X$, there exists $N$, a natural number, such that
$T^{n}(U_{1})\cap U_{2}\neq\phi$ for all $n\geq N$. Mixing and chaos are
stronger than the hypercyclicity; however, they are not comparable in general.
Several familiar operators including weighted shifts on sequence spaces, and
composition operators and differential operators on analytic function spaces
exhibit the hypercyclic, mixing and chaotic properties. The study is
intimately related to classical areas such as complex function theory,
dynamical systems, and operator theory, cf. [6] and [23].

There has been an enormous research on the dynamics of weighted or unweighted
backward shifts. On $F$-sequence spaces having the unit vectors $\\{e_{n}\\}$
as basis, it is well known that the hypercyclic properties of shifts depend on
the asymptotic behaviour of $\|e_{n}\|$, where $\|.\|$ refers to the $F$-norm
of the underlying space. Hypercyclicity and chaos of weighted shifts on
$F$-sequence spaces were characterized Grosse-Erdmann [22]. Prior to that,
Salas [31] had characterized the hypercyclicity of the classical unilateral
and bilateral shifts. Also, see Costakis and Sambarino [14] for mixing shifts,
and Bonet, Kalmes and Peris [11] for dynamics of shifts on non-metrizable
sequence spaces. In the context of the backward shift acting on $F$-spaces of
analytic functions on the unit disc, the dynamics depends naturally on
$\|z^{n}\|$. For example, it is well known that the backward shift on the
Bergman space of the unit disc is a mixing and non-chaotic operator, cf.
Gethner and Shapiro [19] and Grosse-Erdmann [22], respectively. We also refer
to Bonet [10], Beise and Müller [8], Beise, Meyrath and Müller [9], Bourdon
and Shapiro [13], and Müller and Maike [28] for the dynamics related to the
backward shift on analytic function spaces, (Bergman spaces, mostly).

We will make use of the following standard criteria in linear dynamics for
establishing the hypercyclic and chaotic properties of the backward shift.
Different versions of these criteria are available in the literature, cf. [6]
and [23].

######  Theorem 1.1.

(Gethner-Shapiro Criterion [19]) Let $T$ be a bounded operator on a separable
Banach space $X$, and let $X_{0}$ be a dense subset of $X$. If
$\\{n_{k}\\}\subseteq\mathbb{N}$ is a strictly increasing sequence and
$S:X_{0}\mapsto X_{0}$ is a map such that, for each $x\in X_{0}$,

$\lim_{k\rightarrow\infty}T^{n_{k}}x=0=\lim_{k\rightarrow\infty}S^{n_{k}}x,$

and

$TSx=x,$

then $T$ is hypercyclic. Moreover, if $n_{k}=k$ for all $k\geq 1$, then $T$ is
mixing on $X$.

A similar criterion, known as the chaoticity criterion, has been used to
obtain chaotic operators in Banach spaces, cf. [12]. This criterion is very
strong, and it has other implications in linear dynamics; see [6] and [23].

######  Theorem 1.2.

(Chaoticity Criterion [12]) Let $X$ be a separable Banach space, $X_{0}$ be a
dense set in $X$, and let $T$ be a bounded operator on $X$. If there exists a
map $D:X_{0}\rightarrow X_{0}$ such that

$\displaystyle\sum_{n\geq 0}T^{n}x\quad\mbox{and}\quad\sum_{n\geq 0}S^{n}x,$

are unconditionally convergent, and

$TSx=x$

for each $x\in X_{0}$, then the operator $T$ is chaotic and mixing on $X$.

The paper is organized as follows. In Section $2$, we introduce the
reproducing kernel space $\mathcal{H}_{a,b}$, and obtain necessary and
sufficient conditions for $B$ to be bounded on $\mathcal{H}_{a,b}$. In Section
$3$, under some mild conditions we show the shift $B$ on $\mathcal{H}_{a,b}$
is unitarily equivalent to a compact perturbation of a weighted shift on
$\ell^{2}$. Using this result, we compute the essential spectrum of $B$ on
$\mathcal{H}_{a,b}$, which establishes the existence of hypercyclic subspaces
for scalar multiples $\lambda B$. In Section $4$, we characterize the
hypercyclicity, mixing, and chaos of the scalar multiple $\lambda B$ in
$\mathcal{H}_{a,b}$. Section $5$ contains similar dynamical properties of the
shift on a vector valued tridiagonal space.

##  2\. Boundedness of the shift operator on a tridiagonal space
$\mathcal{H}_{a,b}$

We briefly recall the basics and essential properties of analytic (scalar and
matrix valued) reproducing kernel Hilbert spaces. Theory of these spaces is
available in Aronszajn [4] and Paulsen and Raghupati [30] in a more general
set up of operator valued kernels. The main purpose of this section is to
provide a sufficient condition for the backward shift to be a bounded operator
on an analytic tridiagonal space, see Theorem $2.3$.

Let $M_{d}(\mathbb{C})$ denote the space of $d\times d$ complex matrices. A
function $K:\mathbb{D}\times\mathbb{D}\rightarrow M_{d}(\mathbb{C})$ is called
an analytic kernel if $z\mapsto K(z,w)$ is analytic for each fixed
$w\in\mathbb{D}$ and

$\sum_{i,j=1}^{n}\langle K(w_{i},w_{j})u_{j},u_{i}\rangle_{\mathbb{C}^{d}}\geq
0,$

for all choices of $w_{1},\ldots,w_{n}\in\mathbb{D}$ and
$u_{1},\ldots,u_{n}\in\mathbb{C}^{d}$ and $n\in\mathbb{N}$. For an analytic
kernel $K(z,w)$ over $\mathbb{D}$, there exists a unique Hilbert space
$\mathcal{H}(K)$ of $\mathbb{C}^{d}$-valued analytic functions on $\mathbb{D}$
such that

$\text{span}~{}\\{K(\cdot,w)u:w\in\mathbb{D},u\in\mathbb{C}^{d}\\}$

is dense in $\mathcal{H}(K)$ and

$\langle f,K(\cdot,w)u\rangle_{\mathcal{H}(K)}=\langle
f(w),u\rangle_{\mathbb{C}^{d}},$ (2.1)

for all $f\in\mathcal{H}(K)$, $w\in\mathbb{D}$ and $u\in\mathbb{C}^{d}$. Here,
the symbol $K(\cdot,w)u$ denotes the function $z\mapsto K(z,w)u$ on
$\mathbb{D}$. Moreover, for $u_{1},\ldots,u_{n}\in\mathbb{C}^{d}$ and
$w_{1},\ldots,w_{n}\in\mathbb{D}$,

$\left\|\sum_{j=1}^{n}K(.,w_{j})u_{j}\right\|_{\mathcal{H}(K)}=\sum_{i,j=1}^{n}\langle
K(w_{i},w_{j})u_{j},u_{i}\rangle_{\mathbb{C}^{d}}$

which follows from (2.1). The Hilbert space $\mathcal{H}(K)$ is called the
analytic reproducing kernel Hilbert space associated to the kernel $K(z,w)$.
From (2.1) it follows that the evaluation operator
$E_{w}:\mathcal{H}(K)\rightarrow\mathbb{C}^{d}$ is bounded for all
$w\in\mathbb{D}$, where

$E_{w}(f)=f(w),\hskip 28.45274ptf\in\mathcal{H}(K).$

Conversely, if $\mathcal{H}$ is Hilbert space of $\mathbb{C}^{d}$-valued
analytic functions on $\mathbb{D}$, and the evaluation operators $E_{w}$ are
bounded for all $w\in\mathbb{D}$, then $\mathcal{H}$ is an analytic
reproducing kernel Hilbert space corresponding to the
$M_{d}(\mathbb{C})$-valued analytic kernel $K(z,w)=E_{z}\circ E_{w}^{*}$ for
$z,w\in\mathbb{D}$, where $E_{w}^{*}$ is the Hilbert space adjoint of $E_{w}$,
cf. [30]. From (2.1), it also follows that $K(z,w)$ is co-analytic in $w$.
(Analytic kernels play vital roles in operator theory; for instance, see Curto
and Salinas [15].) For a scalar valued analytic kernel $k(z,w)$, we recall
that the corresponding reproducing kernel space $\mathcal{H}(k)$ is uniquely
determined by the following properties [30]: the span
$\\{k(.,w):w\in\mathbb{D}\\}$ is dense in $\mathcal{H}(k)$ and

$f(w)=\big{\langle}f,k(.,w)\big{\rangle}_{\mathcal{H}(k)}$

for all $f\in\mathcal{H}(k)$ and $w\in\mathbb{D}$, where $k(.,w)$ denotes the
function $z\mapsto k(z,w)$ for a fixed $w\in\mathbb{D}$. The kernel function
has a formula, namely $k(z,w)=\sum_{n\geq 0}e_{n}(z)\overline{e_{n}(w)}$ for
any orthonormal basis $\\{e_{n}\\}_{n\geq 0}$ of the space for which $k(z,w)$
is the kernel.

It is known that, if $k(z,w)$ is an analytic scalar kernel, then the
derivatives

$\frac{\partial^{n}k(.,0)}{\partial\overline{w}^{n}}$

can give information on the dynamics of the adjoint of the multiplication by
the independent variable on $\mathcal{H}(k)$, see [29]. We will use the
following fact to derive the necessary parts in the characterization of
hypercyclicity, mixing and chaos of scalar multiples of $B$ on tridiagonal
spaces, and refer to [29].

######  Proposition 2.1.

If $\mathcal{H}(k)$ is an analytic reproducing kernel space over $\mathbb{D}$,
then

$\frac{\partial^{n}k(.,0)}{\partial\overline{w}^{n}}\in\mathcal{H}(k)\hskip
14.22636pt\text{and}\hskip
14.22636ptf^{(n)}(0)=\big{\langle}f,\frac{\partial^{n}k(.,0)}{\partial\overline{w}^{n}}\big{\rangle}_{\mathcal{H}(k)},$

for all $n\geq 0$ and $f\in\mathcal{H}(k)$. Moreover,

$\left\|\frac{\partial^{n}k(.,0)}{\partial\overline{w}^{n}}\right\|_{\mathcal{H}(k)}=\left(\frac{\partial^{2n}k}{\partial
z^{n}\partial\overline{w}^{n}}(0,0)\right)^{1/2}.$

A standard example for an analytic reproducing kernel space is the diagonal
space $\mathcal{H}^{2}(\beta)$: for a given
$\beta=\\{\beta_{n}\\}_{n=0}^{\infty}$ of strictly positive reals, this space
consists of analytic functions $f(z)=\sum_{n\geq 0}\lambda_{n}z^{n}$ on
$\mathbb{D}$ such that $\|f\|^{2}:=\sum_{n\geq
0}|\lambda_{n}|^{2}/{\beta_{n}}<\infty$. As $\sqrt{\beta_{n}}z^{n}$, $n\geq
0$, forms an orthonormal basis for $\mathcal{H}^{2}(\beta)$, its kernel is
given by $\sum_{n\geq 0}\beta_{n}z^{n}\overline{w}^{n}$, cf. [30].

We now introduce analytic tridiagonal kernel spaces. For two sequences of non-
zero complex numbers $a=\\{a_{n}\\}_{n=0}^{\infty}$ and
$b=\\{b_{n}\\}_{n=0}^{\infty}$, let $\mathcal{H}_{a,b}$ be the Hilbert space
of functions on $\mathbb{D}$, for which $\\{f_{n}\\}_{n=0}^{\infty}$ forms an
orthonormal basis, where

$f_{n}(z)=(a_{n}+b_{n}z)z^{n},~{}~{}n\geq 0.$

Since, $k(z,w)=\sum_{n\geq 0}f_{n}(z)\overline{f_{n}(w)},$ we get the tri-
diagonal kernel as,

$k(z,w)=|a_{0}|^{2}+\sum_{n\geq
1}(|a_{n}|^{2}+|b_{n-1}|^{2})z^{n}\overline{w}^{n}+\sum_{n\geq
0}a_{n}\overline{b_{n}}z^{n}\overline{w}^{n+1}+\sum_{n\geq
0}\overline{a_{n}}b_{n}z^{n+1}\overline{w}^{n},$ (2.2)

for all $z,w\in\mathbb{D}$. We call $\mathcal{H}_{a,b}$ a tridiagonal
reproducing kernel Hilbert space, or simply a tridiagonal space. We will
always assume the following:

For a fixed $w\in\mathbb{D}$, the series in (2.2) has a radius of convergence
$1$.

In that case, $k(z,w)$ is analytic in $z\in\mathbb{D}$, and consequently each
$f(z)$ in $\mathcal{H}_{a,b}$ is analytic on $\mathbb{D}$ by the continuity of
evaluation functionals. For more on the terminology of tridiagonal kernels, we
refer to Adams and McGuire [1].

To derive the boundedness and hypercyclicity properties of the backward shift
operator on tridiagonal spaces, we first express a monomial $z^{n}$ in the
orthonormal basis $\\{f_{n}\\}$; see (2.3) below. Such an expression will help
us to find estimates of $\|z^{n}\|_{\mathcal{H}_{a,b}}$ in terms of
$\\{a_{n}\\}$ and $\\{b_{n}\\}$, (Proposition 4.1). Since we repeatedly use
the orthonormal expansion of $z^{n}$, we prefer to show their derivations,
although the same is available in [1]. Indeed, fix $n\geq 0,$ and write
$z^{n}=\sum_{j=0}^{\infty}\alpha_{j}f_{j}$ for some
$\alpha_{j}\in\mathbb{C},n\geq 0.$ Then

$z^{n}=\alpha_{0}a_{0}+\sum_{j=1}^{\infty}(\alpha_{j-1}b_{j-1}+\alpha_{j}a_{j})z^{j}.$

Thus, comparing coefficients, we have
$\alpha_{0}=\alpha_{1}=\cdot\cdot\cdot=\alpha_{n-1}=0,$ and
$\alpha_{n}=\frac{1}{a_{n}},$ as the $\alpha_{i}$ non zero scalars. Since

$\alpha_{n+k-1}b_{n+k-1}+\alpha_{n+k}a_{n+k}=0,$

it follows that

$\alpha_{n+k}=-\frac{\alpha_{n+k-1}b_{n+k-1}}{a_{n+k}},$

and thus

$\alpha_{n+k}=\frac{(-1)^{k}}{a_{n}}\frac{b_{n}b_{n+1}\cdot\cdot\cdot
b_{n+k-1}}{a_{n+1}a_{n+2}\cdot\cdot\cdot a_{n+k}},\,\,\,\,(k\geq 1).$

This implies

$z^{n}=\frac{1}{a_{n}}\sum_{j=0}^{\infty}(-1)^{j}(\frac{\prod_{k=0}^{j-1}b_{n+k}}{\prod_{k=0}^{j-1}a_{n+k+1}})f_{n+j},\,\,\,\,(n\geq
0),$ (2.3)

where the term corresponding to $j=0$ is $1$. The above expansion will be used
repeatedly.

The backward shift operator on $\mathcal{H}_{a,b}$ is defined by

$(Bf)(z)=\sum_{n=0}^{\infty}\lambda_{n+1}z^{n},$ (2.4)

for $f(z)=\sum_{n=0}^{\infty}\lambda_{n}z^{n}$ in $\mathcal{H}_{a,b}$. Note
that $B$ is the “coefficient backward shift”. To obtain necessary and
sufficient conditions for $B$ to be bounded on $\mathcal{H}_{a,b}$, we proceed
by computing the matrix representation of the operator $B$ acting on
$\mathcal{H}_{a,b}$ with respect to the orthonormal basis $\\{f_{n}\\}_{n\geq
0}$ and then, study the matrix operator on $\ell^{2}$. See [1] for a similar
study on tridiagonal shifts.

Recall the orthonormal basis $f_{n}(z)=(a_{n}+b_{n}z)z^{n},n\geq 0$, in
$\mathcal{H}_{a,b}$. Note that $B(f_{n})(z)=a_{n}z^{n-1}+b_{n}z^{n},~{}n\geq
1$. Also, $f_{0}(z)=a_{0}+b_{0}z$ and

$B(f_{0})(z)=b_{0}=\frac{b_{0}}{a_{0}}f_{0}-\frac{b_{0}^{2}}{a_{0}a_{1}}f_{1}+\frac{b_{0}^{2}b_{1}}{a_{0}a_{1}a_{2}}f_{2}-\frac{b_{0}^{2}b_{1}b_{2}}{a_{0}a_{1}a_{2}a_{3}}f_{3}+\cdots.$

For $n\geq 1$, we have

$B(f_{n})(z)=a_{n}z^{n-1}+b_{n}z^{n}=\frac{a_{n}}{a_{n-1}}f_{{n-1}}+(\frac{b_{n}}{a_{n}}-\frac{a_{n}}{a_{n-1}}\frac{b_{n-1}}{a_{n}})a_{n}z^{n},$

by putting the value of $z^{n-1}$. Setting

$c_{n}:=\frac{b_{n}}{a_{n}}-\frac{b_{n-1}}{a_{n-1}},$

we immediately get

$B(f_{n})(z)=\frac{a_{n}}{a_{n-1}}f_{{n-1}}+c_{n}a_{n}z^{n},~{}~{}~{}n\geq 1.$

Now, the matrix representation of $B$ can be obtained from the following
expressions:

$B(f_{1})(z)=\frac{a_{1}}{a_{0}}f_{{0}}+c_{1}f_{{1}}-\frac{c_{1}b_{1}}{a_{2}}f_{{2}}+\frac{c_{1}b_{1}b_{2}}{a_{2}a_{3}}f_{{3}}-\cdots,$
$B(f_{2})(z)=\frac{a_{2}}{a_{1}}f_{{1}}+c_{2}f_{{2}}-\frac{c_{2}b_{2}}{a_{3}}f_{{3}}+\frac{c_{2}b_{2}b_{3}}{a_{3}a_{4}}f_{{4}}-\cdots,$

and so on. Hence, the matrix of $B$ with respect to the orthonormal basis
$\\{f_{n}\\}_{n\geq 0}$ is

$[B]:=\begin{bmatrix}\frac{b_{0}}{a_{0}}&\frac{a_{1}}{a_{0}}&0&0&0&\cdots\\\
-\frac{b_{0}^{2}}{a_{0}a_{1}}&c_{1}&\frac{a_{2}}{a_{1}}&0&0&\ddots\\\
\frac{b_{0}^{2}b_{1}}{a_{0}a_{1}a_{2}}&-\frac{c_{1}b_{1}}{a_{2}}&c_{2}&\frac{a_{3}}{a_{2}}&0&\ddots\\\
-\frac{b_{0}^{2}b_{1}b_{2}}{a_{0}a_{1}a_{2}a_{3}}&\frac{c_{1}b_{1}b_{2}}{a_{2}a_{3}}&-\frac{c_{2}b_{2}}{a_{3}}&c_{3}&0&\ddots\\\
\frac{b_{0}^{2}b_{1}b_{2}b_{3}}{a_{0}a_{1}a_{2}a_{3}a_{4}}&-\frac{c_{1}b_{1}b_{2}b_{3}}{a_{2}a_{3}a_{4}}&\frac{c_{2}b_{2}b_{3}}{a_{3}a_{4}}&-\frac{c_{3}b_{3}}{a_{4}}&\ddots&\ddots\\\
\vdots&\vdots&\vdots&\ddots&\ddots&\ddots\end{bmatrix}.\quad$ (2.5)

Compare the above matrix with that of a left inverse of the multiplication
operator $\big{(}Sf\big{)}(z)=zf(z)$ defined on a tridiagonal space, cf. Das
and Sarkar [17], Proposition $3.1$.

We now determine necessary and sufficient conditions under which the above
(formal) matrix defines a bounded operator on $\ell^{2}$. Equivalently, this
gives boundedness results for $B$ acting on $\mathcal{H}_{a,b}$.

Recall that

$c_{n}:=\frac{b_{n}}{a_{n}}-\frac{b_{n-1}}{a_{n-1}},~{}n\geq 1.$

######  Proposition 2.2.

If $B$ is bounded on an analytic tridiagonal space $\mathcal{H}_{a,b}$, then

$\big{\\{}\frac{a_{n+1}}{a_{n}}\big{\\}}_{n\geq 1}\hskip
21.33955pt\text{and}\hskip 21.33955pt\left\\{c_{n}\right\\}_{n\geq 1}$

are bounded sequences.

###### Proof.

Let $B$ be bounded on $\mathcal{H}_{a,b}$. Then the matrix $[B]$ induces a
bounded operator on $\ell^{2}$. Let $v_{n}$ be the $n$-th column of $[B]$.
Operating $[B]$ on the subset $\\{e_{n}\\}_{n\geq 1}$ of the standard
orthonormal basis in $\ell^{2}$, since $[B](e_{n})=v_{n}$, we get that

$\sup_{n}\|v_{n}\|<\infty.$

On the other hand,

$\|v_{n}\|_{\ell^{2}}^{2}\geq\big{|}\frac{a_{n}}{a_{n-1}}\big{|}^{2}+|c_{n}|^{2},\hskip
14.22636ptn\geq 1.$

This implies the necessary conditions, as in the proposition.

∎

The following theorem gives a (general) sufficient condition for $B$ to be
bounded.

######  Theorem 2.3.

Let $\mathcal{H}_{a,b}$ be the reproducing kernel Hilbert space having an
orthonormal basis of the form $\\{(a_{n}+b_{n}z)z^{n}:~{}n\geq 0\\}$. If

$\sup_{n\geq
1}~{}\Big{\\{}\lvert\frac{a_{n+1}}{a_{n}}\rvert,~{}|c_{n}|\Big{\\}}<\infty,~{}\text{and}~{}\sum_{n=1}^{\infty}\max\left\\{\left|\frac{b_{0}^{2}b_{1}\cdots
b_{n-1}}{a_{0}a_{1}\cdots a_{n}}\right|,~{}\sup_{j\geq
1}~{}\left|\frac{c_{j}b_{j}b_{j+1}\cdots b_{j+n-1}}{a_{j+1}a_{j+2}\cdots
a_{j+n}}\right|\right\\}<\infty,$

then $B$ is bounded on $\mathcal{H}_{a,b}$.

###### Proof.

We split the matrix of $B$ as a formal series of infinite matrices as follows:

$[B]=\begin{bmatrix}\frac{b_{0}}{a_{0}}&\frac{a_{1}}{a_{0}}&0&0&0&\cdots\\\
-\frac{b_{0}^{2}}{a_{0}a_{1}}&c_{1}&\frac{a_{2}}{a_{1}}&0&0&\ddots\\\
\frac{b_{0}^{2}b_{1}}{a_{0}a_{1}a_{2}}&-\frac{c_{1}b_{1}}{a_{2}}&c_{2}&\frac{a_{3}}{a_{2}}&0&\ddots\\\
-\frac{b_{0}^{2}b_{1}b_{2}}{a_{0}a_{1}a_{2}a_{3}}&\frac{c_{1}b_{1}b_{2}}{a_{2}a_{3}}&-\frac{c_{2}b_{2}}{a_{3}}&c_{3}&0&\ddots\\\
\frac{b_{0}^{2}b_{1}b_{2}b_{3}}{a_{0}a_{1}a_{2}a_{3}a_{4}}&-\frac{c_{1}b_{1}b_{2}b_{3}}{a_{2}a_{3}a_{4}}&\frac{c_{2}b_{2}b_{3}}{a_{3}a_{4}}&-\frac{c_{3}b_{3}}{a_{4}}&\ddots&\ddots\\\
\vdots&\vdots&\vdots&\ddots&\ddots&\ddots\end{bmatrix}\quad$

$=\begin{bmatrix}0&\frac{a_{1}}{a_{0}}&0&0&\cdots\\\
0&0&\frac{a_{2}}{a_{1}}&0&\ddots\\\ 0&0&0&\frac{a_{3}}{a_{2}}&\ddots\\\
0&0&0&0&\ddots\\\
\vdots&\vdots&\vdots&\ddots&\ddots\end{bmatrix}+\begin{bmatrix}\frac{b_{0}}{a_{0}}&0&0&0&\cdots\\\
0&c_{1}&0&0&\ddots\\\ 0&0&c_{2}&0&\ddots\\\ 0&0&0&c_{3}&\ddots\\\
\vdots&\vdots&\vdots&\ddots&\ddots\end{bmatrix}+\begin{bmatrix}0&0&0&\cdots\\\
-\frac{b_{0}^{2}}{a_{0}a_{1}}&0&0&\ddots\\\
0&-\frac{c_{1}b_{1}}{a_{2}}&0&\ddots\\\
0&0&-\frac{c_{2}b_{2}}{a_{3}}&\ddots\\\
\vdots&\vdots&\ddots&\ddots\end{bmatrix}+\ldots,$

which is a formal series of matrices,
$[B_{w}]+[D]+\sum_{n=1}^{\infty}[F_{n}]$. Here, $[B_{w}]$ is the matrix of the
standard weighted backward shift $B_{w}(e_{i})\mapsto w_{i}e_{i-1}$ on
$\ell^{2}$, $i\geq 1$, having weights

$w_{i}=\frac{a_{i}}{a_{i-1}},\hskip 28.45274pt(i\geq 1),$

and $[D]$ is the matrix of the diagonal operator

$\text{diag}~{}(\frac{b_{0}}{a_{0}},c_{1},c_{2},\cdots)$

on $\ell^{2}$. The matrix $[F_{n}]$ is obtained by deleting all the entries of
$[B]$, except those at the $n$-th subdiagonal, where $n\geq 1$. Observe that
$[F_{n}]$ is the matrix of suitable powers of a weighted forward shift $F_{n}$
for $n\geq 1$.
It follows, respectively by the first two assumptions in the theorem, that the
weighted shift $B_{w}$ and the diagonal operator $D$ are bounded on
$\ell^{2}$. Since

$\|F_{n}\|=\max\left\\{\left|\frac{b_{0}^{2}b_{1}\cdots
b_{n-1}}{a_{0}a_{1}\cdots a_{n}}\right|,~{}\sup_{j\geq
1}~{}\left|\frac{c_{j}b_{j}b_{j+1}\cdots b_{j+n-1}}{a_{j+1}a_{j+2}\cdots
a_{j+n}}\right|\right\\},$

the third condition in the theorem gives that $F_{n}$ is bounded, and

$\sum_{n\geq 1}\|F_{n}\|<\infty$

with respect to the operator norm. Hence, the shift $B$ is bounded on
$\mathcal{H}_{a,b}$. This completes the proof of the theorem. ∎

######  Remark 2.4.

We note that $B$ is a left-inverse of the multiplication operator
$(Sf)(z)=zf(z)$ on $\mathcal{H}_{a,b}$, assuming that both $B$ and $S$ are
bounded. A closely related left inverse $B_{1}$ of $S$ was studied in [17],
wherein the authors obtained conditions for the boundedness of $B_{1}$. The
matrices of $B$ and $B_{1}$ are almost the same, except the difference in the
first columns. Their assumptions, given below, for boundedness are strong
compared to those in the above theorem. Indeed, the conditions

$\sup_{n\geq 1}~{}\lvert\frac{a_{n+1}}{a_{n}}\rvert<\infty\hskip
11.38092pt\text{and}\hskip
11.38092pt\lim\sup_{n}\left\lvert\frac{b_{n}}{a_{n+1}}\right\rvert<1$ (2.6)

imply those in Theorem 2.3. To see this, writing

$c_{n}=\frac{b_{n}}{a_{n+1}}\frac{a_{n+1}}{a_{n}}-\frac{a_{n}}{a_{n-1}}\frac{b_{n-1}}{a_{n}},\hskip
28.45274pt(n\geq 1),$

we can see that $\\{c_{n}\\}$ is bounded. Moreover, since
$\lim\sup_{n}\left\lvert\frac{b_{n}}{a_{n+1}}\right\rvert<1$, there exist
$r<1$ and $N\in\mathbb{N}$ such that
$\left\lvert\frac{b_{n}}{a_{n+1}}\right\rvert<r$, for $n\geq N$. From this,
the remaining conditions in Theorem 2.3 follows.

##  3\. The shift on $\mathcal{H}_{a,b}$ as a compact perturbation of a
weighted shift on $\ell^{2}$

Under some mild assumptions on $\\{a_{n}\\}$ and $\\{b_{n}\\}$, we prove that
the shift $B$ acting on $\mathcal{H}_{a,b}$ is unitarily equivalent to the sum
$B_{w}+K$ on $\ell^{2}$ for a suitable weighted backward shift on $\ell^{2}$
and a compact operator $K$. Using this perturbation result, we compute the
essential spectrum of the shift $B$ acting on $\mathcal{H}_{{a},{b}}$. These
results are of independent interest as well.

The essential spectrum $\sigma_{e}(T)$, of an operator $T$ on a complex
Hilbert space $\mathcal{H}$ is the set of all $\lambda\in\mathbb{C}$ such that
$T-\lambda I$ is not Fredholm, that is,

$\sigma_{e}(T)=\\{\lambda\in\mathbb{C}:~{}\text{dim~{}Ker}(T-\lambda
I)=\infty~{}\text{or dim Ker}(T^{*}-\overline{\lambda}I)=\infty\\},$

where $T^{*}$ is the adjoint of $T$, cf. Bayart and Matheron [6] and Douglas
[18]. The essential spectrum plays a key role in the investigation of
hypercyclic subspaces; see the section $4$.

In the proof of the following theorem, we use a well known fact:
$\sigma_{e}(T)$ is invariant under a compact perturbation, that is,

$\sigma_{e}(T+K)=\sigma_{e}(T)$

for every compact operator $K$.

######  Theorem 3.1.

Let $\mathcal{H}_{{a},{b}}$ be a tridiagonal reproducing kernel space over the
unit disc $\mathbb{D}$. Assume that

$\sup_{n}|\frac{a_{n+1}}{a_{n}}|<\infty,~{}\limsup_{n}|\frac{b_{n}}{a_{n+1}}|<1,~{}and~{}\lim_{n}\left|\frac{b_{n}}{a_{n}}-\frac{b_{n-1}}{a_{n-1}}\right|=0.$

Then the following hold.

  1. (i)

The operator $B$ on $\mathcal{H}_{{a},{b}}$ is unitarily equivalent to
$B_{w}+K$ for some compact operator $K$ and the weighted backward shift
$B_{w}$ on the sequence space $\ell^{2}$, where the weight sequence
$w=(w_{n})$ is given by

$w_{n}=\frac{a_{n}}{a_{n-1}},\hskip 5.69046ptn\geq 1.$

  2. (ii)

The essential spectrum $\sigma_{e}(B)$ is the annulus

$\sup_{n\geq 1}\left(\inf_{k\geq
1}\left|\frac{a_{k+n}}{a_{k}}\right|\right)^{1/n}~{}\leq|z|\leq\inf_{n\geq
1}\left(\sup_{k\geq 1}\left|\frac{a_{k+n}}{a_{k}}\right|\right)^{1/n}.$

###### Proof.

The proof relies on the matrix representation of $B$ with respect to the
orthonormal basis $f_{n}(z)=(a_{n}+b_{n}z)z^{n}$ of $\mathcal{H}_{a,b}$.
Consider the unitary operator $U:\mathcal{H}_{a,b}\rightarrow\ell^{2}$ given
by

$U(\sum_{n=0}^{\infty}\lambda_{n}f_{n})=\sum_{n=0}^{\infty}\lambda_{n}e_{n},$

that is, $U(f_{n})=e_{n}$ for all $n$, where $\\{e_{n}\\}_{n\geq 0}$ is the
standard basis in $\ell^{2}$. Now, from the proof of Theorem 2.3 we recall
that $B$ on $\mathcal{H}_{a,b}$ is unitarily equivalent via $U$ to the sum (in
the operator norm)

$B_{w}+D+\sum_{m=1}^{\infty}F_{m}.$

Here, $B_{w}$ in the weighted backward shift on $\ell^{2}$ with weights

$w_{n}=\frac{a_{n}}{a_{n-1}},\hskip 28.45274ptn\geq 1.$ (3.1)

Further, by the assumptions, the operators $D$ and $F_{m}$ are compact on
$\ell^{2}$ as the entries in the matrix of $D$ and $F_{m}$ converges to $0$
for all $m\geq 1$. Hence

$K:=D+\sum_{m=1}^{\infty}F_{m}$

is a compact operator on $\ell^{2}$, and consequently, $B$ acting on
$\mathcal{H}_{a,b}$ is unitarily equivalent to $B_{w}+K$. This proves (i).

The invariance of the essential spectrum under compact perturbations along
with (i) yields that

$\sigma_{e}(B)=\sigma_{e}(B_{w}+K)=\sigma_{e}(B_{w}).$

Thus, it is enough to compute $\sigma_{e}(B_{w})$. We now recall the essential
spectrum of a weighted backward shift on $\ell^{2}$ and refer to [6] and [32]:
In general, for an injective weighted shift $B_{w}$ corresponding to
$w=\\{w_{n}\\}_{n=1}^{\infty}$, the essential spectrum is the annulus

$\sup_{n\geq 1}\left(\inf_{k\geq
1}\prod_{i=1}^{n}|w_{k+i}|\right)^{1/n}~{}\leq|z|\leq\inf_{n\geq
1}\left(\sup_{k\geq 1}\prod_{i=1}^{n}|w_{k+i}|\right)^{1/n}.$

In our setting, $B_{w}$ is the weighted shift with weights as in (3.1). Since

$\prod_{i=1}^{n}w_{k+i}=\frac{a_{k+n}}{a_{k}}$

for all $k,n\geq 1$, the result in (ii) follows. The proof is complete. ∎

##  4\. Hypercyclicity, mixing, and chaos

In this section, we characterize the hypercyclicity, mixing and chaos of the
backward shift $\lambda B$ on $\mathcal{H}_{a,b}$. These results resemble to
those of weighted backward shifts on $\ell^{2}$. The following estimates on
the norms of monomials will be used in the characterizations of the
hypercyclicity properties of $\lambda B$.

######  Proposition 4.1.

Assume that the conditions in Theorem 2.3 hold, with $c_{n}\neq 0$ for all
$n\geq 0$. Then there exists constant $M_{1}>0$ such that

$\|z^{n}\|_{\mathcal{H}_{a,b}}\leq\frac{M_{1}}{|c_{n}a_{n}|},\hskip
9.95863ptn\geq 0.$ (4.1)

In addition, if $\limsup_{n}|\frac{b_{n}}{a_{n+1}}|<1$, then there is a
constant $M_{2}>0$ such that

$\|z^{n}\|_{\mathcal{H}_{a,b}}\leq\frac{M_{2}}{|a_{n}|},\hskip 9.95863ptn\geq
0.$ (4.2)

###### Proof.

By the orthonormal expansion in $\mathcal{H}_{a,b}$ and the continuity of
evaluation functionals, we can find some
$\\{\lambda_{j}\\}_{j=0}^{\infty}\in\ell^{2}$ such that

$z^{n}=\sum_{j\geq 0}\lambda_{j}(a_{j}z^{j}+b_{j}z^{j+1}),$

for all $z\in\mathbb{D}$. Equating the coefficients of like-powers, we have
that $\lambda_{j}=0$ for $j=0,\ldots,n-1$, and

$\lambda_{n}=\frac{1}{a_{n}},~{}~{}\lambda_{n+1}=-\frac{b_{n}}{a_{n+1}}\lambda_{n}=-\frac{1}{a_{n}}\frac{b_{n}}{a_{n+1}},~{}~{}\lambda_{n+2}=\frac{1}{a_{n}}\frac{b_{n}}{a_{n+1}}\frac{b_{n+1}}{a_{n+2}},$
(4.3)

and so on. Since $\lVert z^{n}\rVert^{2}_{\mathcal{H}_{a,b}}=\sum_{j\geq
0}|\lambda_{j}|^{2},$ we have

$\lVert
z^{n}\rVert^{2}_{\mathcal{H}_{a,b}}=\frac{1}{|a_{n}|^{2}}+\left|\frac{1}{a_{n}}\frac{b_{n}}{a_{n+1}}\right|^{2}+\left|\frac{1}{a_{n}}\frac{b_{n}}{a_{n+1}}\frac{b_{n+1}}{a_{n+2}}\right|^{2}+\ldots.$
(4.4)

By multiplying the numerators and denominators of each of the above terms by
$c_{n}$, we get the first part in the proposition.
On the other hand, the strong assumption

$\limsup_{n}|\frac{b_{n}}{a_{n+1}}|<1$

implies that there exist $r<1$ and $N\in\mathbb{N}$ such that
$|b_{n}/a_{n+1}|<r$ for all $n\geq N$. Thus, by the equation (4.4) we have

$\lVert
z^{n}\rVert^{2}_{\mathcal{H}_{a,b}}\leq\frac{1}{|a_{n}|^{2}}\left(\sum_{k\geq
0}r^{2k}\right),$

for every $n\geq N$. The required result in the second part of the proposition
follows. ∎

The next theorems contain the main results of this section.

######  Theorem 4.2.

Let $\mathcal{H}_{a,b}$ be the analytic tridiagonal space corresponding to
$a=\\{a_{n}\\}_{n=0}^{\infty}$ and $b=\\{b_{n}\\}_{n=0}^{\infty}$ satisfying
the conditions of Theorem 2.3 and that $c_{n}\neq 0$ for all $n$. Then the
following hold for a scalar $\lambda$:

  1. (i)

$\lambda B$ is hypercyclic on $\mathcal{H}_{a,b}$ if

$\sup_{n}~{}|\lambda^{n}c_{n}a_{n}|=\infty.$

  2. (ii)

If $\lambda B$ is hypercyclic, then

$\sup_{n}|\lambda|^{n}(|a_{n}|+|b_{n-1}|)=\infty.$

  3. (iii)

Assuming the stronger condition $\limsup_{n}|b_{n}/a_{n+1}|<1$, the operator
$\lambda B$ is hypercyclic if and only if

$\sup_{n}|\lambda^{n}a_{n}|=\infty.$

###### Proof.

To get (i), we apply the Gethner-Shapiro criterion. Let $X_{0}$ be the space
of all polynomials. Then, $X_{0}$ is dense in $\mathcal{H}_{a,b}$ as it
contains the orthonormal basis $\\{(a_{n}+b_{n}z)z^{n}:n\geq 0\\}$. Consider
the forward $S:X_{0}\rightarrow X_{0}$ given by

$S(z^{n})=z^{n+1},\hskip 17.07182ptn\geq 0.$

Trivially,

$BSf=f\hskip 11.38092pt\text{and}\hskip 11.38092pt(\lambda B)^{n}f\rightarrow
0,\hskip 22.76228pt\text{as}~{}n\rightarrow\infty,$

for all $f\in X_{0}$. It suffices to show that, there exists a strictly
increasing sequence $\\{m_{k}\\}$ of natural numbers such that

$\frac{1}{\lambda^{m_{k}}}S^{m_{k}}(z^{n})\rightarrow 0,$

as $k\rightarrow\infty$, for every monomial $z^{n}$. Combining (iii) of our
theorem, with the first estimate in Proposition 4.1, we get an increasing
sequence $\\{d_{k}\\}$ such that

$\frac{1}{\lambda^{d_{k}}}S^{d_{k}}(z^{n})\rightarrow 0,$

as $k\rightarrow\infty$. Now, Lemma 4.2 of [23] completes the proof of (i).

To obtain (ii), let

$f(z)=\sum_{n=0}^{\infty}\lambda_{n}f_{n}(z),~{}~{}z\in\mathbb{D},$

be a hypercyclic vector for $\lambda B$, where
$f_{n}(z)=a_{n}z^{n}+b_{n}z^{n+1}$, $n\geq 0$, forms an orthonormal basis of
$\mathcal{H}_{a,b}$. Rearranging the above sum as a power series, we get

$B^{n}f(z)=\lambda_{n-1}b_{n-1}+\lambda_{n}a_{n}+(\lambda_{n}b_{n}+\lambda_{n+1}a_{n+1})z+\cdot\cdot\cdot.$

As $\\{(\lambda B)^{n}f:n\geq 0\\}$ is dense in $\mathcal{H}_{a,b},$ it
follows that

$\displaystyle\sup_{n}~{}\lvert\lambda^{n}(\lambda_{n-1}b_{n-1}+\lambda_{n}a_{n})\rvert$
$\displaystyle=$ $\displaystyle\infty.$

On the other hand,

$\lambda_{n-1}b_{n-1}+\lambda_{n}a_{n}=\frac{f^{(n)}(0)}{n!},\hskip
14.22636ptn\geq 1,$

which gives that

$\sup_{n}|\lambda|^{n}|\frac{f^{(n)}(0)}{n!}|=\infty.$

Recalling from Proposition 2.1 that $|f^{(n)}(0)|$ can be dominated by
derivatives of the kernel function $k(z,w)$ of $\mathcal{H}_{a,b}$, we obtain
that

$\sup_{n}\frac{|\lambda|^{n}}{n!}\left(\frac{\partial^{2n}k}{\partial
z^{n}\partial\overline{w}^{n}}(0,0)\right)^{\frac{1}{2}}=\infty.$

Now, the kernel for $\mathcal{H}_{a,b}$ is

$k(z,w)=|a_{0}|^{2}+\sum_{n\geq
1}(|a_{n}|^{2}+|b_{n-1}|^{2})z^{n}\bar{w}^{n}+\sum_{n\geq
0}a_{n}\bar{b_{n}}z^{n}\bar{w}^{n+1}+\sum_{n\geq
0}\bar{a_{n}}b_{n}z^{n+1}\bar{w}^{n},$

for all $z,w\in\mathbb{D}$, from which it follows that

$\sup_{n}|\lambda|^{n}(|a_{n}|+|b_{n-1}|)=\infty.$

This completes the proof of (ii).

To see the part (iii), we proceed as in (i) and (ii) for the sufficiency and
necessity, respectively, and along the way, use the second part in Proposition
4.1 and the condition $\limsup_{n}|b_{n}/a_{n+1}|<1$. ∎

Our next result is on the mixing property of $\lambda B$ in
$\mathcal{H}_{a,b}$.

######  Theorem 4.3.

Consider the space $\mathcal{H}_{a,b}$ corresponding to $a=\\{a_{n}\\}$ and
$b=\\{b_{n}\\}$ satisfying the assumptions as in the previous theorem. Then
the following hold for the shift $B$ on $\mathcal{H}_{a,b}$ and a scalar
$\lambda$.

  1. (i)

$\lambda B$ is topologically mixing on $\mathcal{H}_{a,b}$ if

$\lim_{n\rightarrow\infty}~{}|\lambda^{n}c_{n}a_{n}|=\infty$

  2. (ii)

If $\lambda B$ is mixing, then

$\lim_{n\rightarrow\infty}|\lambda|^{n}(|a_{n}|+|b_{n-1}|)=\infty.$

  3. (iii)

Assuming the stronger condition $\limsup_{n}|b_{n}/a_{n+1}|<1$, the operator
$\lambda B$ is mixing if and only if

$\lim_{n\rightarrow\infty}|\lambda^{n}a_{n}|=\infty.$

###### Proof.

For the sufficiency parts in (i) and (iii), proceed exactly as in the proof of
the previous theorem by applying the Gethner-Shapiro criterion with $n_{k}=k$
for $k\geq 1$. ∎

In the part (iii) of the above theorems, we obtained characterizations of
hypercyclicity and mixing of $\lambda B$, under the strong assumption that
$\limsup_{n}|b_{n}/a_{n+1}|<1$. Along the same lines, we obtain a
characterization for $\lambda B$ to be chaotic using the chaoticity criterion.

######  Theorem 4.4.

Let $\mathcal{H}_{a,b}$ be a reproducing kernel Hilbert space of analytic
functions on $\mathbb{D}$ having an orthonormal basis
$\\{f_{n}(z)=(a_{n}+b_{n}z)z^{n},n\geq 0\\},$ where $a_{n},b_{n}$ are non-zero
complex numbers, satisfying $\sup_{n}\big{|}a_{n+1}/a_{n}\big{|}<\infty$ and
$\limsup_{n}\big{|}b_{n}/a_{n+1}\big{|}<1$. Then the following are equivalent
for the backward shift $B$ and a scalar $\lambda$.

  1. (i)

$\lambda B$ is chaotic on $\mathcal{H}_{a,b}$.

  2. (ii)

$\lambda B$ has a non-trivial periodic vector.

  3. (iii)

$\sum_{n=0}^{\infty}\lvert\lambda^{n}a_{n}\rvert^{-2}<\infty.$

###### Proof.

Suppose that the condition in (iii) holds. We apply the chaoticity criterion
to show that $\lambda B$ is chaotic on $\mathcal{H}_{a,b}.$

Let $X_{0}$ be the space of all polynomials. Define $S:X_{0}\rightarrow X_{0}$
given by $S(z^{n})=\frac{1}{\lambda}z^{n+1}$, $n\geq 0$. Clearly $(\lambda
B)S=I$ on $X_{0}$. Moreover, the series $\sum_{n=0}^{\infty}(\lambda
B)^{n}(f)$ converges unconditionally for each $f\in X_{0}.$ It remains to show
that the series $\sum_{n=0}^{\infty}S^{n}(f)$ converges unconditionally, for
each $f\in X_{0}.$ We prove that

$\sum_{n=0}^{\infty}\frac{1}{\lambda^{n}}z^{n}$

is unconditionally convergent in $\mathcal{H}_{a,b}$. Recalling the
orthonormal expansion from (2.3), for a fixed $n\geq 0,$ we have

$z^{n}=\frac{1}{a_{n}}\sum_{j=0}^{\infty}\lambda_{n,j}f_{n+j},$ (4.5)

where

$\lambda_{n,0}=1,\hskip 17.07182pt\text{and}\hskip
17.07182pt\lambda_{n,j}=(-1)^{j}\frac{b_{n}b_{n+1}\cdot\cdot\cdot
b_{n+j-1}}{a_{n+1}a_{n+2}\cdot\cdot\cdot a_{n+j}},\,\,\,\,(j\geq 1).$

Also,

$\displaystyle\sum_{n=0}^{\infty}\frac{1}{\lambda^{n}}z^{n}=$
$\displaystyle\sum_{n=0}^{\infty}\frac{1}{\lambda^{n}}\left(\frac{1}{a_{n}}\sum_{j=0}^{\infty}\lambda_{n,j}f_{n+j}\right)$
$\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}\left(\frac{\lambda_{0,n}}{a_{0}}+\frac{\lambda_{1,n-1}}{\lambda
a_{1}}+\cdots+\frac{\lambda_{n,0}}{\lambda^{n}a_{n}}\right)f_{n}.$

As $\limsup_{n}|b_{n}/a_{n+1}|<1$, one gets $N\in\mathbb{N}$ and $r<1$ such
that $|b_{n}/a_{n+1}|<r$ for all $n\geq N$. Hence,

$\left|\frac{\lambda_{0,n}}{a_{0}}+\frac{\lambda_{1,n-1}}{\lambda
a_{1}}+\cdots+\frac{\lambda_{n,0}}{\lambda^{n}a_{n}}\right|\leq\frac{r^{n}}{|a_{0}|}+\frac{r^{n-1}}{|\lambda
a_{1}|}+\cdots+\frac{1}{|\lambda|^{n}|a_{n}|},$

for all $n\geq N$. The right hand side of the above inequality is the $n$-th
term of an $\ell^{1}$-convolution of the $\ell^{2}$ element
$\\{\frac{1}{\lambda^{n}a_{n}}\\}$, and hence it is absolutely square
summable. Consequently, the series $\sum_{n}\lambda^{-n}z^{n}$ is convergent.
The unconditional convergence occurs because $\\{f_{n}\\}$ is orthonormal.
Hence, $\lambda B$ satisfies the chaoticity criterion, and (i) follows.

To see that (ii) implies (iii), let

$f(z)=\sum_{n=0}^{\infty}\lambda_{n}f_{n}(z),$

be a non-zero periodic vector for $B$ on $\mathcal{H}_{a,b}$, where
$f_{n}(z)=a_{n}z^{n}+b_{n}z^{n+1}$, $n\geq 0$, forms an orthonormal basis for
$\mathcal{H}_{a,b}$. Now,

$\displaystyle f(z)$ $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}\lambda_{n}f_{n}(z)$ $\displaystyle=$
$\displaystyle\lambda_{0}a_{0}+\sum_{n=1}^{\infty}(\lambda_{n-1}b_{n-1}+\lambda_{n}a_{n})z^{n}$
$\displaystyle:=$ $\displaystyle\sum_{n=0}^{\infty}A_{n}z^{n},$

where $A_{0}=\lambda_{0}a_{0}$ and
$A_{n}=\lambda_{n-1}b_{n-1}+\lambda_{n}a_{n},\,n\geq 1.$ Let $p\in\mathbb{N}$
such that $B^{p}f(z)=f(z)$ for all $z\in\mathbb{D}$. Then $B^{kp}f(z)=f(z)$
for all $k\geq 1$. It follows that

$\lambda^{kp}(A_{kp}+A_{kp+1}z+\ldots+A_{kp+n}z^{n}+\ldots)=A_{0}+A_{1}z+\ldots+A_{n}z^{n}+\ldots,$

for all $z\in\mathbb{D}$. We can compare the respective coefficients and get
the required result. Indeed, equating the coefficients of $z^{j}$ for $0\leq
j\leq p-1$, we obtain

$A_{j}=\lambda^{kp}A_{kp+j}~{}~{}\forall~{}k\geq 1.$

The case $j=0$ gives

$\lambda_{0}a_{0}=\lambda^{kp}\lambda_{kp-1}b_{kp-1}+\lambda^{kp}\lambda_{kp}a_{kp},$

for all $k\geq 1$. We get

$\lvert\lambda_{0}a_{0}\rvert^{2}\sum_{k=1}^{\infty}\left\lvert\frac{1}{\lambda^{kp}a_{kp}}\right\rvert^{2}\leq
C\left(r^{2}\sum_{k=1}^{\infty}\left\lvert\lambda_{kp-1}\right\rvert^{2}+\sum_{k=1}^{\infty}\left\lvert\lambda_{kp}\right\rvert^{2}\right)$

for some $C>0$, where
$r:=\sup_{n}\left\lvert\frac{b_{n}}{{}_{a_{n+1}}}\right\rvert<1.$ Since
$\\{\lambda_{n}\\}\in\ell^{2}$,

$\sum_{k=1}^{\infty}\left\lvert\frac{1}{\lambda^{kp}a_{kp}}\right\rvert^{2}<\infty.$

For $j=1,\ldots,p-1$, we similarly have
$\lambda_{j-1}b_{j-1}+\lambda_{j}a_{j}=\lambda^{kp}(\lambda_{kp+j-1}b_{kp+j-1}+\lambda_{kp+j}a_{kp+j})$.
Once again, using $r<1$, we obtain

$\sum_{k=1}^{\infty}\left\lvert\frac{1}{\lambda^{kp}a_{kp+j}}\right\rvert^{2}<\infty.$

Consequently, the series in (iii) is convergent.

∎

######  Remark 4.5.

The dynamics of the shift $B$ in $\mathcal{H}_{a,b}$ can be observed from the
previous theorems by taking $\lambda=1$.

We conclude this section with a remark on the existence of hypercyclic
subspaces for $\lambda B$ in $\mathcal{H}_{a,b}$. Recall that if the set
$HC(T)$ of all hypercyclic vectors of an operator $T$ on a Banach space $X$
contains a closed infinite dimensional subspace (excluding the zero vector),
then we say that $T$ has a hypercyclic subspace. It is well known that the
essential spectrum of an operator $T$ on a complex Banach space completely
characterizes the existence of hypercyclic subspaces, thanks to an important
result of González, León-Saavedra and Montes-Rodríguez [21]: if $T$ is a
bounded operator satisfying the hypercyclicity criterion in a complex Banach
space, then $T$ has a hypercyclic subspace if and only if

$\sigma_{e}(T)\cap\overline{\mathbb{D}}\neq\phi.$ (4.6)

For details on the study of hypercyclic subspaces and related topics for
various classes of operators including the weighted backward shifts, we refer
to [6], [25], [26], and [27].

In view of (4.6) and Theorem 3.1 we can now establish the existence of
hypercyclic subspaces in $\mathcal{H}_{a,b}$.

######  Corollary 4.6.

Let $\mathcal{H}_{a,b}$ be an analytic tridiagonal space over the unit disc
such that $\sup_{n}|a_{n+1}/a_{n}|<\infty$ and $\limsup_{n}|b_{n}/a_{n+1}|<1$.
Then the multiple $\lambda B$ has hypercyclic subspaces in $\mathcal{H}_{a,b}$
if and only if

$\sup_{n}|\lambda^{n}a_{n}|=\infty\hskip 19.91684pt\text{and}\hskip
19.91684pt\sup_{n\geq 1}\left(\inf_{k\geq
1}\left|\frac{a_{k+n}}{a_{k}}\right|\right)^{1/n}\leq\frac{1}{|\lambda|}.$

##  5\. The shift operator on tridiagonal spaces given by matrix valued
kernels

We now consider tridiagonal reproducing kernel Hilbert spaces which are
induced by matrix valued analytic kernels, and study the dynamics of the shift
$B$ acting on these spaces. The results obtained in this section can be
regarded, in particular, as the vector valued versions of our previous results
in the scalar tridiagonal kernel spaces.

For sequences $\mathcal{A}:=\\{A_{n}\\}_{n=0}^{\infty}$ and
$\mathcal{B}:=\\{B_{n}\\}_{n=0}^{\infty}$ of complex matrices of order $d$, we
consider the function

$K:\mathbb{D}\times\mathbb{D}\rightarrow M_{d}(\mathbb{C}),$

defined by

$K(z,w)=\sum_{n=0}^{\infty}(A_{n}+B_{n}z)(A_{n}^{*}+B_{n}^{*}\overline{w})z^{n}\overline{w}^{n},$
(5.1)

where the symbol $A^{*}$ denote the transpose conjugate of $A$. We assume
that, for each fixed $w\in\mathbb{D}$, the above series (considered as a power
series in $z$) has a radius of convergence $1$. Note that $K(z,w)$ reduces to
a scalar tridiagonal form when $d=1$.
It follows that $K(z,w)$ is an $M_{d}(\mathbb{C})$-valued kernel over
$\mathbb{D}$. To verify this, from the definition of kernels it can be seen
that

$(A_{n}+B_{n}z)(A_{n}^{*}+B_{n}^{*}\overline{w})z^{n}\overline{w}^{n},\hskip
17.07182pt(n\geq 0),$

is a kernel function and so is their sum. We refer to Paulsen and Raghupati
[30] wherein it is proved that a sum of kernels is also a kernel. Denote the
reproducing kernel space corresponding to $K(z,w)$ by
$\mathcal{H}_{\mathcal{A},\mathcal{B}}$.

The following gives a sufficient condition for the backward shift on
$\mathcal{H}_{\mathcal{A},\mathcal{B}}$ to be a bounded operator.

######  Theorem 5.1.

Let $K(z,w)$ be an $M_{d}(\mathbb{C})$-valued kernel over $\mathbb{D}$, of the
form $\eqref{tm-kernel}$, and let $\\{A_{n},B_{n}:n\geq 0\\}$ be
simultaneously and unitarily diagonalizable invertible matrices. Let
$a_{n}^{(1)},\ldots,a_{n}^{(d)}$ and $b_{n}^{(1)},\ldots,b_{n}^{(d)}$ be the
eigenvalues of $A_{n}$ and $B_{n}$, respectively. If, for each $1\leq q\leq
d$,

$\sup_{n}\big{|}a^{(q)}_{n+1}/a^{(q)}_{n}\big{|}<\infty\hskip
21.33955pt\text{and}\hskip
21.33955pt\limsup_{n}\big{|}b^{(q)}_{n}/a^{(q)}_{n+1}\big{|}<1,$ (5.2)

then the backward shift $B$ is bounded on
$\mathcal{H}_{\mathcal{A},\mathcal{B}}$. In fact, the shift on
$\mathcal{H}_{\mathcal{A},\mathcal{B}}$ is unitarily similar to the direct sum
of the backward shifts on $\oplus_{q=1}^{d}\mathcal{H}_{q}$, where
$\mathcal{H}_{q}$ is the (scalar) tridiagonal space having an orthonormal
basis of the form

$a_{n}^{(q)}z^{n}+b_{n}^{(q)}z^{n+1},~{}~{}n\geq 0.$

###### Proof.

By the assumptions on $\\{A_{n}\\}$ and $\\{B_{n}\\}$, there exists a unitary
matrix $Q$ such that

$A_{n}=Q^{*}D_{n,1}Q\hskip 17.07182pt\text{and}\hskip
17.07182ptB_{n}=Q^{*}D_{n,2}Q,\hskip 14.22636ptn\geq 0.$

Here, $D_{n,1}$ and $D_{n,2}$ are respectively, the diagonal matrices
consisting of the eigenvalues of $A_{n}$ and $B_{n}$. Thus, we have

$K(z,w)=Q^{*}\Big{(}\sum_{n=0}^{\infty}(D_{n,1}+D_{n,2}z)(D_{n,1}^{*}+D_{n,2}^{*}\overline{w})z^{n}\overline{w}^{n}\Big{)}Q,$

for all $z,w\in\mathbb{D}$. Since $Q$ preserves the inner product in
$\mathbb{C}^{d}$, the above factorization along with the reproducing property
implies that the shift $B$ on $\mathcal{H}_{\mathcal{A},\mathcal{B}}$ is
unitarily similar to the backward shift on the reproducing kernel space
$\mathcal{H}$ corresponding to the kernel

$K_{1}(z,w):=\sum_{n=0}^{\infty}(D_{n,1}+D_{n,2}z)(D_{n,1}^{*}+D_{n,2}^{*}\overline{w})z^{n}\overline{w}^{n}.$

To see this, we claim that the spaces $\mathcal{H}_{\mathcal{A},\mathcal{B}}$
and $\mathcal{H}$ are equal as sets with equal norms: for if
$w_{1},\ldots,w_{n}\in\mathbb{D}$ and $u_{1},\ldots,u_{n}\in\mathbb{C}^{d}$,
we have

$\begin{split}\|\sum_{i=0}^{n}K(.,w_{i})u_{i})\|_{\mathcal{\mathcal{\mathcal{H}_{\mathcal{A},\mathcal{B}}}}}^{2}&=\sum_{i,j=1}^{n}\langle
K(w_{i},w_{j})u_{j},u_{i}\rangle_{\mathbb{C}^{d}}\\\ &=\sum_{i,j=0}^{n}\langle
K_{1}(w_{i},w_{j})u_{j},u_{i}\rangle_{\mathbb{C}^{d}}\\\
&=\|\sum_{i=1}^{n}K_{1}(.,w_{i})u_{i})\|_{\mathcal{H}}^{2}.\end{split}$

Since the sets

$\\{K(.,w)u:~{}w\in\mathbb{D},u\in\mathbb{C}^{d}\\}~{}~{}\text{and}~{}~{}\\{K_{1}(.,w)u:~{}w\in\mathbb{D},u\in\mathbb{C}^{d}\\}$

span dense subspaces of $\mathcal{H}_{\mathcal{A},\mathcal{B}}$ and
$\mathcal{H}$ respectively, the above claim is proved.

It remains to show that the backward shift on $\mathcal{H}$ is unitarily
equivalent to the direct sum of shifts on the tridiagonal spaces mentioned in
the theorem. The kernel function $K_{1}(z,w)$ can be written as a $d\times d$
diagonal matrix:

$K_{1}(z,w)=\text{diag}~{}\big{[}a_{n}^{(1)}z^{n}+b_{n}^{(1)}z^{n+1},a_{n}^{(2)}z^{n}+b_{n}^{(2)}z^{n+1},\dots,a_{n}^{(d)}z^{n}+b_{n}^{(d)}z^{n+1}\big{]}.$

So, if $\mathcal{H}_{q}$, $q=1,2,\ldots,d,$ denotes the reproducing kernel
space having an orthonormal basis of the form

$a_{n}^{(q)}z^{n}+b_{n}^{(q)}z^{n+1},~{}~{}n\geq 0,$

we see that $\mathcal{H}$ can be identified with
$\oplus_{q=1}^{d}\mathcal{H}_{q}$ under the unitary map defined by

$U:\mathcal{H}_{d}\mapsto\oplus_{q=1}^{d}\mathcal{H}_{q},$ $\hskip
56.9055ptU\big{(}g_{1},\ldots,g_{d}\big{)}=g_{1}\oplus\ldots\oplus g_{d},$

where $(g_{1},\ldots,g_{d})$ is an arbitrary function in $\mathcal{H}$. The
same unitary operator intertwines the backward shift on $\mathcal{H}$ and the
direct sum of the backward shifts on $\oplus_{q=1}^{d}\mathcal{H}_{q}$. On the
other hand, it follows the assumption (5.2) that the backward shift on
$\mathcal{H}_{q}$ is bounded for all $q=1,\ldots,d$. This shows that shift $B$
is bounded on $\mathcal{H}$. The proof is complete. ∎

In view of Theorem 5.1, we immediately obtain tridiagonal vector valued
versions of the results obtained in the section $4$. The hypercyclicity,
mixing, and chaos of $B$ on $\mathcal{H}_{\mathcal{A},\mathcal{B}}$ is
respectively, equivalent to those of $B_{1}\oplus\cdots\oplus B_{d}$. Here
$B_{q}$ refers to the backward shift on the tridiagonal space having an
orthonormal basis $a_{n}^{(q)}z^{n}+b_{n}^{(q)}z^{n+1},~{}~{}n\geq 0$. Also,
along the same lines of the proofs in Theorems $4.2$, $4.3$ and $4.4$, we can
deduce the dynamical properties of $B_{1}\oplus\cdots\oplus B_{d}$. We have
the following:

######  Theorem 5.2.

Let $\\{A_{n}\\}$ and $\\{B_{n}\\}$ be matrices satisfying the conditions in
(5.2). Then the following hold for the shift $B$ acting on
$\mathcal{H}_{\mathcal{A},\mathcal{B}}$.

  1. (i)

$B$ is hypercyclic if and only if $\displaystyle\sup_{n}\Big{(}\min_{1\leq
q\leq d}|a_{n}^{(q)}|\Big{)}=\infty$.

  2. (ii)

$B$ is mixing if and only if
$\displaystyle\lim_{n\rightarrow\infty}|a_{n}^{(q)}|=\infty$ for all
$q=1,\ldots,d$.

  3. (iii)

$B$ is chaotic if and only if
$\displaystyle\sum_{n=0}^{\infty}|a_{n}^{(q)}|^{-2}<\infty$ for all
$q=1,\ldots,d$.

It is important to note that, unlike the scalar case, the existence of a
single non-trivial periodic vector does not imply that $B$ is chaotic on
$\mathcal{H}_{\mathcal{A},\mathcal{B}}$. This can be seen by choosing
$\\{A_{n}\\}$ and $\\{B_{n}\\}$ to be diagonal matrices appropriately in
Theorem 5.1 and recalling that if the direct sum of operators is chaotic, so
is each of those operators.

##  6\. Concluding remarks

The chaoticity criterion (cf. the section $1$) yields strong dynamical
properties of operators. In particular, if an operator $T$ satisfies the
chaoticity criterion, then it is frequently hypercyclic, see [12]. (The notion
of frequent hypercyclicity was introduced by Bayart and Grivaux [5]). Hence,
any of the statements in Theorem $4.4$ implies that $\lambda B$ is frequently
hypercyclic on $\mathcal{H}_{a,b}$. It would be interesting to know if the
condition $\sum_{n}|\lambda^{n}a_{n}|^{-2}<\infty$ is also necessary for
$\lambda B$ to be frequently hypercyclic. For weighted shifts on $\ell^{p}$,
it is well known that the chaos and frequent hypercyclicity are equivalent,
cf. [7].

The main result in the section $3$ shows that the operator $B$, under mild
conditions, is a compact perturbation of a weighted shift. This does not
reveal the structure of $B$ completely, although its essential spectrum can be
understood. For example, the spectrum of $B$ on $\mathcal{H}_{a,b}$ is
unknown. Similar work for the multiplication operator $f(z)\mapsto zf(z)$ are
available in [1], [2] and [16]. In particular, the authors in [2] show that
the aforementioned multiplication operator on a very specific tridiagonal
space is a rank-one perturbation of the unilateral unweighted shift. This
motives us to raise a similar question for $B$ on $\mathcal{H}_{a,b}$.

We hope to investigate these issues in an upcoming work.

Acknowledgments. The first author acknowledges a research fellowship of CSIR,
File No.: 09/1059(0037)/2020-EMR-I, and the second named author acknowledges
SERB, DST, File. No.: SRG/2021/002418, for a start-up grant.

## References

  * [1] G.T. Adams and P.J. McGuire, Analytic tridiagonal reproducing kernels, J. Lond. Math. Soc. (2) 64 (2001) 722–738.
  * [2] G.T. Adams and P.J. McGuire, A class of tridiagonal reproducing kernels, Oper. Matrices 2 (2008) 233–247.
  * [3] G.T. Adams, P.J. McGuire and V. Paulsen, Analytic reproducing kernels and multiplication operators, Ill. J. Math. 36 (1992) 404–419.
  * [4] N. Aronszajn, Theory of reproducing kernels, Trans. Amer. Math. Soc. 68 (1950) 337–404.
  * [5] F. Bayart and S. Grivaux, Frequently hypercyclic operators, Trans. Amer. Math. Soc. 358 (2006) 5083-5117.
  * [6] F. Bayart and E. Matheron, Dynamics of Linear Operators, Camb. Univ. Press. 179 (2009).
  * [7] F. Bayart and I.Z. Ruzsa, Difference sets and frequently hypercyclic weighted shifts, Ergod. Theor. Dyn. Syst. 35 (3) 2015 691-709.
  * [8] H.-P. Beise and J. Müller, Generic boundary behaviour of Taylor series in Hardy and Bergman spaces, Math. Z. 284 (2016) 1185–1197.
  * [9] H.-P. Beise, T. Meyrath and J. Müller, Mixing Taylor shifts and universal Taylor series, Bull. Lond. Math. Soc. 47 (2015) 136–142.
  * [10] J. Bonet: Dynamics of the differentiation operator on weighted space of entire functions, Math. Z. 261 (2009) 649–657.
  * [11] J. Bonet, T. Kalmes, and A. Peris: Dynamics of shift operators on non-metrizable sequence spaces Rev. Mat. Iberoam. 37 (2021) no.6, 2373-2397.
  * [12] A. Bonilla and K.-G. Grosse-Erdmann, Frequently hypercyclic operators and vectors, Ergod. Theor. Dyn. Syst. 27 (2007) 383–404.
  * [13] P.S. Bourdon and J.H.Shapiro, Hypercyclic operators that commute with the Bergman backward shift, Trans. Amer. Math. Soc. 352 (2000), no. 11, 5293 - 5316.
  * [14] G. Costakis and M. Sambarino, Topologically mixing hypercyclic operators, Proc. Amer. Math. Soc. 132 (2004) 385–389.
  * [15] R. Curto and N. Salinas, Generalized Bergman kernels and the Cowen-Douglas theory, Amer. J. Math. 106 (1984) 447–488.
  * [16] S. Das and J. Sarkar, Tridiagonal shifts as compact $+$ isometry Arch. der. Math. 119 (2022) 507-518.
  * [17] S. Das and J. Sarkar, Tridiagonal kernels and left-invertible operators with applications to Aluthge transforms, Rev. Mat. Iberoam. 39(2023) 397–437.
  * [18] R.G. Douglas, Banach Algebra Techniques in Operator Theory, New York: Academic, 1972.
  * [19] R.M. Gethner, J.H. Shapiro, Universal vectors for operators on spaces of holomorphic functions, Proc. Amer. Math. Soc. 100 (1987) 281–288.
  * [20] G. Godefroy and J.H. Shapiro, Operators with dense, invariant, cyclic vector manifolds, J. Funct. Anal. 98 (1991) 229–269.
  * [21] M. González, F. León-Saavedra and A. Montes-Rodríguez, Semi-Fredholm theory: hypercyclic and supercyclic subspaces, Proc. Lond. Math. Soc. (3) 81 (2000) 169-189.
  * [22] K.-G. Grosse-Erdmann, _Hypercyclic and chaotic weighted shifts_ , Stud. Math. 139 (2000) 47–68.
  * [23] K.-G. Grosse-Erdmann and A. Peris, _Linear Chaos_ , Springer Universitext, 2011\.
  * [24] C. Kitai, Invariant closed sets for linear operators, Ph.D thesis, University of Toronto, Toronto, 1982.
  * [25] F. León-Saavedra and A. Montes-Rodríguez: Linear structure of hypercyclic vectors, J. Funct. Anal. 148, 524–545 (1997).
  * [26] Q. Menet, Hypercyclic subspaces and weighted shifts Adv. Math. 255 (2014) 305-337.
  * [27] A. Montes-Rodríguez: Banach spaces of analytic functions Michigan Math. J. 43 (1996) no. 3, 419-436.
  * [28] J. Müller and T. Maike: Dynamics of the Taylor shift on Bergman spaces, J. Oper. Theor. 87 (2022) 25–40.
  * [29] A. Mundayadan and J. Sarkar, Linear dynamics in reproducing kernel Hilbert spaces, Bull. Sci. Math. 159 (2020) 102826, 29 pp.
  * [30] V. Paulsen and M. Raghupathi, _An introduction to the theory of reproducing kernel Hilbert spaces_ , Camb. Univ. Press 152, 2016.
  * [31] Hector N. Salas, Hypercyclic weighted shifts, Trans. Amer. Math. Soc. 347 (1995), no. 3, 993-1004.
  * [32] A.L. Shields, Weighted shift operators and analytic function theory, in: Topics of Operator Theory, in: Math. Surveys Monogr., vol.13, American Math. Soc., Providence, RI, 1974, pp.49–128.


# Node-Bound Communities for Partition of Unity Interpolation on Graphs

Roberto Cavoretto<EMAIL_ADDRESS>Alessandra De Rossi
<EMAIL_ADDRESS>Sandro Lancellotti<EMAIL_ADDRESS>Federico Romaniello<EMAIL_ADDRESS>Department of Mathematics
“Giuseppe Peano”, University of Torino, via Carlo Alberto 10, 10123 Torino,
Italy  Member of the INdAM Research group GNCS

###### Abstract

Graph signal processing benefits significantly from the direct and highly
adaptable supplementary techniques offered by partition of unity methods
(PUMs) on graphs. In our approach, we demonstrate the generation of a
partition of unity solely based on the underlying graph structure, employing
an algorithm that relies exclusively on centrality measures and modularity,
without requiring the input of the number of subdomains. Subsequently, we
integrate PUMs with a local graph basis function (GBF) approximation method to
develop cost-effective global interpolation schemes. We also discuss numerical
experiments conducted on both synthetic and real datasets to assess the
performance of this presented technique.

###### keywords:

Partition of unity methods , Kernel-based approximation , graph basis
functions , graph signal processing , graph theory.

††journal: Applied Mathematics and Computation

##  1 Introduction

Graph signal processing is a very popular tool when it comes to study the
field of graph signals and, for this reason, several mathematical techniques
such as filtering, compression, noise removal, sampling or decomposition are
deeply investigated in the literature, see [16, 21]. Moreover, graphs
naturally appear in several problems, as in social networks or traffic maps
[6]. However, they generally have a complex structure that requires efficient
and fast processing tools for their analysis. Among the notable
characteristics of graphs that depict real systems, the arrangement of
vertices into communities stands out. These communities exhibit a high density
of edges connecting vertices within them, while the connections between
vertices from distinct communities are relatively sparse. Detecting
communities is of great importance in sociology, biology and computer science,
disciplines where systems are often represented as graphs, nonetheless this
problem is very hard and not yet satisfactorily solved, see [12].

Partition of unity methods (PUMs) enables the execution of tasks like signal
reconstruction from samples, node classification, or localized signal
filtering on smaller segments of the graph [6]. Subsequently, they facilitate
the reconstruction of the global signal from these localized components. In
the scattered data approximation, the blend of radial basis functions (RBFs)
with PUMs results in markedly sparser system matrices in collocation or
interpolation tasks, leading to a substantial reduction in computing time, see
e.g. [3, 4, 10]. In what follows, we will focus on approximation methods based
on generalized translates of a graph basis function (GBF), see [8] and [9] for
more details.

In this article, we provide a more adaptive technique for the selection of the
partitions on the graph than the one presented in [6]. In particular, by
interpreting the communities of a graph as the candidate partitions for the
PUM, we propose a process that automatically finds an optimal number of
communities or subdomains based on their modularity and on the underlying
graph structure. We remark that the desired number of subdomains are not
needed as an input for the GBF-PUM algorithm and, as far as the authors’
knowledge, such an approach has never been used before. Our study has been
supported by several numerical experiments carried out to validate our new
algorithm on both test and real-world datasets.

The structure of the paper is outlined in the following manner. In Section 2
we give a brief outline of graph theory and positive definite GBFs for signal
approximation on graphs. A description of our algorithm, how it can be
integrated to the GBF-PUM schema proposed in [6] is provided in Section 3,
together with a computational complexity analysis. In Section 4 numerical
examples showing the behaviour of the presented technique both in synthetic
and real datasets are presented. Finally, Section 5 concludes the paper also
including future work.

##  2 Preliminaries

###  2.1 Graph theory

A _graph_ is an incidence structure $G=(V,E)$, where $V(G)$ is a set whose
elements are called _vertices_ or _nodes_ , and $E(G)$ is a set of pairs of
vertices, whose elements are called _edges_ or _links_.

In what follows, we use the letter $G$ to denote a graph and the symbol
$|V(G)|$ to denote the cardinality of its vertex set $V(G)$. Moreover, all
graphs considered here are connected and simple, that is, without loops, i.e.
edges of the form $(v,v)$, and multiple edges, i.e. more than one edge for a
given pair of vertices. We refer the reader to [2] and [15] for further
definitions and notation not explicitly stated in this section.

######  Definition 1.

A graph $H=(V(H),E(H))$ is called a _subgraph_ of $G=(V(G),E(G))$ if and only
if $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$. A collection of disjoint
subgraphs of $G$ which covers $V(G)$ is a _partition_ of $G$ and the subgraphs
are called _communities_.

Given $u\in V(G)$, the set $N(u)=\left\\{v\in V(G)|(u,v)\in E(G)\right\\}$ is
the _neighbourhood_ of $u$. The number of edges $|N(u)|$ incident to a vertex
$u$ is said to be the _degree_ of $u$, and will be denoted as $deg_{G}(u)$.
Given a graph $G$ with $V(G)=\\{u_{1},\dots,u_{n}\\}$, it is possible to
describe its entire structure with matrices, as shown below.

######  Definition 2.

The _adjacency matrix_ of the graph $G$ is a square $n\times n$ matrix $A$
such that its entry $A_{ij}=1$ if and only if there is an edge between
vertices $u_{i}$ and $u_{j}$, and zero otherwise.

######  Definition 3.

The _Laplacian matrix_ of the graph $G$ is a square $n\times n$ matrix $L$
defined as $L=D-A$, where $D$ is the $n\times n$ diagonal matrix with
$D_{ii}=deg_{G}(u_{i})$ and $A$ is the adjacency matrix of $G$.

Centrality is a very important notion when it comes to identifying the most
important nodes in a graph. It may come in different flavours and each one of
them highlights its importance from a different perspective. The following
definition will be useful.

######  Definition 4.

_Katz centrality_ computes the relative influence of a vertex within a graph
by measuring the number of the immediate neighbours and also all other
vertices in the network that connect to the vertex under consideration through
these immediate neighbours. Connections made with distant neighbours are,
however, penalized by an attenuation factor $\alpha$, usually set as $0.5$.
The Katz centrality for vertex $v_{i}$ is:

$C_{Katz}(u_{i})=\sum_{k=1}^{\infty}\sum_{j=1}^{n}\alpha^{k}(A^{k})_{ij}.$

Furthermore, we will need the following concepts, to better understand the
algorithms presented in Section 3.

######  Definition 5.

Given a graph $G$, a partition of $V(G)$ into two subgraphs $c_{1},c_{2}$ is
said to be a _cut_ $c=(c_{1},c_{2})$. The set of edges having one endpoint in
$c_{1}$ and the other one in $c_{2}$ is said the _cut-set_ of $c$. When $s$
and $v$ are specified vertices of $V(G)$, then an $(s,v)$-cut is a cut
$c=(c_{1},c_{2})$ such that $s\in c_{1}$ and $t\in c_{2}$.

######  Definition 6.

Given an undirected and unweighted graph, the _capacity_ of a cut $c$ is the
number of edges belonging to the cut-set of $c$. If the graph has weights on
the edge-set, the capacity is the sum of the weights of the edges belonging to
the cut-set. Accordingly, in an undirected graph, the cut whose weight is
smaller (or equal) than the weight of any other cut is called _minimum cut_.

######  Definition 7.

Let $u,v\in V(G)$, the _Jaccard similarity index_ $J(u,v)=\frac{|N(u)\cap
N(v)|}{|N(u)\cup N(v)|}$ measures the similarity between two vertices. It can
easily be extended to communities $U,V$ of $G$ as follows:

$J(U,V)=\operatorname*{avg}\limits_{u\in U,v\in V}\left\\{J(u,v)\right\\}.$

Note that, by design, $0\leq J(U,V)\leq 1$.

######  Definition 8.

The _modularity_ $Q$ of a graph is a measure of the strength of the division
of a graph into communities $c_{1},\dots,c_{n}$. Graphs with high modularity
have dense connections between the vertices within communities but sparse
connections between vertices in different communities. It is defined as

$Q=\frac{1}{2m}\sum_{i,j}\left(A_{ij}-\frac{k_{i}k_{j}}{2m}\right)\delta(c_{i},c_{j}),$

where $m$ is the number of edges, $k_{i}$ is the degree of $u_{i}$ and
$\delta(c_{i},c_{j})$ is 1 if $u_{i}$ and $u_{j}$ are in the same community,
zero otherwise. The value for the modularity for unweighted and undirected
graphs lies in the range $[-1/2,1]$ and it is positive if the number of edges
within communities exceeds the number expected on the basis of choice.

###  2.2 Signal approximation on graphs with positive definite GBFs

GBFs, when only a limited number of samples are available, serve as
straightforward and efficient instruments for interpolating and approximating
graph signals. In particular, when positive definite GBFs are used, better
results can be achieved. The theory closely parallels a related one in
scattered data approximation using positive definite RBFs in Euclidean space,
see [19] and [23].

######  Definition 9.

Given a graph $G$, a function $x:V(G)\rightarrow\mathbb{R}$ is said a _graph
signal_. If $|V(G)|=n$, then the $n$-dimensional vector space of all graph
signals will be denoted by $\mathcal{L}(G)$.

By means of the Laplacian matrix $L$, it is possible to consider a Fourier
transform on the graph $G$ since $L=UM_{\lambda}U^{T}$, where
$M_{\lambda}=diag(\lambda_{1},\dots,\lambda_{n})$ identifies the diagonal
matrix whose entries are the (increasingly ordered) eigenvalues of $L$ and the
columns of the orthonormal matrix $U$ denote the normalised eigenvectors of
$L$ w.r.t. the corresponding eigenvalue. The set
$\hat{G}=\\{u_{1},\dots,u_{n}\\}$ consisting of the ordered eigenvectors forms
an orthonormal basis for the space $\mathcal{L}(G)$ and it is called the
_spectrum_ of $G$.

######  Definition 10.

Given a graph $G$, let $L=UM_{\lambda}U^{T}$ be its Laplacian and let
$x\in\mathcal{L}(G)$ be a signal on $G$. The Fourier transform on the graph
$G$ of the signal $x$ is the vector $\hat{x}=U^{T}x$, whose inverse Fourier
transform is defined by $x=U\hat{x}$.

We will now focus on kernels $K:V\times V\rightarrow\mathbb{R}$ defined on $G$
such that, for every $u,v\in V:K(u,v)=K(v,u)$. Kernels permit to consider a
linear operator $\textbf{K}:\mathcal{L}(G)\rightarrow\mathcal{L}(G)$ which
acts on $x\in\mathcal{L}(G)$ by

$\textbf{K}x(v_{i})=\sum_{j=1}^{n}K(v_{i},v_{j})x(v_{j}).$

Hence, K can be represented as the following symmetric matrix of size $n\times
n$:

$K=\begin{bmatrix}K(v_{1},v_{1})&K(v_{1},v_{2})&\dots&K(v_{1},v_{n})\\\
\vdots&\vdots&\ddots&\vdots\\\
K(v_{n},v_{1})&K(v_{n},v_{2})&\dots&K(v_{n},v_{n})\end{bmatrix}.$

We will name a symmetric kernel function $K$ _positive definite_ if the
associated matrix $K$ is strictly positive definite, that is $x^{T}Kx\geq 0$,
$\forall x\in\mathbb{R}^{n},x\neq 0$. We remark that every positive definite
kernel $K$ induces on the space $\mathcal{L}(G)$ an inner product $\langle
x,y\rangle_{K}=y^{T}Kx$ and a norm $\|x\|_{K}$ , for every
$x,y\in\mathcal{L}(G)$. This resulting inner product space will be referred to
as _native space_ $\mathcal{N}_{K}$. Moreover, it is a reproducing kernel
Hilbert space, see [1]. To obtain a GBF approximation $x_{\star}$ for a signal
$x$ based on $N$ samples $x(w_{i})$, where $i=1,\dots,N$, we seek the solution
$x_{\star}$ to the following regularized least squares (RLS) problem:

$x_{\star}=\text{argmin}_{y\in\mathcal{N}_{\textbf{K}}}\left\\{\frac{1}{N}\sum_{i=1}^{N}|x(w_{i})-y(w_{i})|^{2}+\gamma\|y\|^{2}_{\textbf{K}_{f}}\right\\}.$
(1)

The first term in of Equation (1) is referred to as the data fidelity term,
which guarantees the proximity of the values $x_{\star}(w_{i})$ to the
provided values $x(w_{i})$, on the sampling set $W$, whereas $\gamma>0$ is
denoted as the regularization parameter.

Numerical examples presented in Section 4 rely on polyharmonic splines on
graphs, which are an example of a positive definite GBF based on the kernel:

$K_{f_{(\epsilon I_{n}+L)^{-s}}}=(\epsilon
I_{n}+L)^{-s}=\sum_{k=1}^{n}\frac{1}{(\epsilon+\lambda_{k})^{s}}u_{k}u_{k}^{T},$

where $u_{1},\dots,u_{n}$ are the eigenvectors of the Laplacian $L$. If
$\lambda_{1}$ is the largest eigenvalue of $L$, this kernel is positive
definite for $\epsilon>-\lambda_{1}$ and $s>0$ (see [17] and [22]). Hence
values of $\epsilon=-\lambda_{1}+1$ and $s=1$ are set for the experiments.

##  3 Topology based subdomain detection

Signal interpolation on graphs with PUM requires overlapping subdomains with
the property that at least one vertex of the subdomain is an interpolation
node. In what follows we describe how it is possible to find such subdomains
for PUM on graphs, based on the structural topology of the underlying
structure.

###  3.1 Overlapping communities detection

Community detection is an edge-cutting topic in graph theory, indeed different
approaches may be used, see [15] for a detailed overview. Our method is a
divisive technique where the centrality of the interpolation nodes is the main
criterion for splitting, allowing overlapping among communities. The finding
communities process was decomposed into five different functions combined with
each other. It is worth noting here that, when the adjacency matrix $A$ of the
graph $G$ is part of the input of an algorithm, automatically all information
on nodes $V(G)$ and edges $E(G)$ is stored. In detail, the main function is
Algorithm 1, in which, given in input $A$, the adjacency matrix of the graph
$G$, and the set of the interpolation (or sample) nodes $W$, an attempt is
made to iteratively divide communities until the number of interpolation nodes
is reached or no attempt at division leads to an increase in modularity.
During the attempt of division, Algorithm 2 provides a new candidate sub-
partition, for each community, with its modularity obtained by splitting the
considered community. In the end, the sub-partition with the highest
modularity, if greater than the initial modularity, superseded the previous
partition. Then, small communities are merged with the big ones using
Algorithm 4 and, finally, with Algorithm 5, communities are expanded to create
the required overlapping for the GBF-PUM.

Algorithm 1 community_detection

Input:

  * $A$: adjacency matrix of the graph $G$, $W$: interpolation vertices, $r$: ratio of neighbours of a vertex inside the community over the total number, $dmax$: distance of max augmentation, $dmin$: distance of min augmentation.

$partition\rightarrow\\{V(G)\\}$

$Q^{\prime}\rightarrow-1$

$Q\rightarrow modularity(partition)$

while $|partition|<=|W|\quad\&\quad Q^{\prime}<Q$ do

$Q^{\prime}\rightarrow Q$

for $i\leq|partition|$ do

$partition_{i},Q_{i}\rightarrow find\\_partition(A,partition,partition(i),W)$

if $Q_{i}>Q$ then

$partition\rightarrow partition_{i}$

$Q\rightarrow Q_{i}$

end if

end for

end while

$partition\rightarrow join\\_communities(A,partition)$

$expanded\\_partition\rightarrow
expand\\_communities(A,partition,r,dmax,dmin)$

Output:

  * $partition$: partition of $V$, $expanded\\_partition$: expanded partition with overlap of $V$.

Algorithm 2 is used for generating the candidate sub-partition. It takes in
input the adjacency matrix $A$ of the graph $G$, a $partition$ of $V(G)$, the
community to divide and the set of samples $W$. It begins calling Algorithm 3
to retrieve the two sub-communities obtained by the splitting, then it
generates the sub-partition and evaluates its modularity, returning them as
output.

Algorithm 2 find_partition

Input:

  * $A$: adjacency matrix of the graph $G$, $partition$: partition of $V(G)$, $community$: a community of $G$, $W$: interpolation vertices.

$c_{1}$, $c_{2}$ $\rightarrow split\\_net(A,community,W)$

$partition^{\prime}\rightarrow(partition\setminus
community)\cup\\{c_{1},c_{2}\\}$

$Q^{\prime}\rightarrow$ modularity of $partition^{\prime}$

Output:

  * $partition^{\prime}$: the sub-partition, $Q^{\prime}$: modularity of $partition^{\prime}$.

The core step of the entire procedure is mastered by Algorithm 3, which, taken
as input a connected graph (which may be $G$ or one of its communities) and
the set of interpolation nodes $W$, evaluates the Katz centrality for each
sample vertex (see Definition 4). After that, it selects the two vertices $s$
and $v$ with the highest centrality values. Furthermore, the capacity (see
Definition 6) of all edges having as first end-point $s$ or $v$ and as the
other end-point neither a vertex different from $v$ or $s$ nor one of their
neighbours respectively is set to infinity; whereas, a capacity value of 1 is
set to all other edges. Eventually, it performs a minimum $(s,v)$-cut (see
Definition 5) obtaining the 2 sub-communities returned as output.

Algorithm 3 split_net

Input:

  * $A$: adjacency matrix of the graph $G$, $G$: connected graph $G$, $W$: interpolation vertices.

Evaluate the Katz centrality for each vertex in $W$

Select $s$ and $v$, the vertices with high centrality

for $\\{x,y\\}\in E(G)$ do

$capacity(\\{x,y\\})\rightarrow 1$

end for

for $u\in N(s)$ do

if $u\notin N(v)\cup\\{v\\}$ then

$capacity(\\{s,u\\})\rightarrow\infty$

end if

end for

for $u\in N(v)$ do

if $u\notin N(s)\cup\\{s\\}$ then

$capacity(\\{v,u\\})\rightarrow\infty$

end if

end for

$c_{1},c_{2}\rightarrow\text{Compute the value and the node partition of a
minimum $(s,v)-cut$}$

Output:

  * $c_{1}$: split community, $c_{2}$: split community, $partition^{\prime}$: new partition, $Q^{\prime}$: modularity of $partition^{\prime}$.

Algorithm 4 merges the small communities into the most similar large one.
Taking as input $A$ and the $partition$ it starts by dividing the communities
into small if contains less than the $2\%$ of vertices and large. For each
small community, it evaluates the Jaccard similarity (see Definition 7) among
the small community considered and all the large ones in the graph. Then, the
small one is merged with the most similar big community.

Algorithm 4 join_communities

Input:

  * $A$: adjacency matrix of the graph $G$, $partition$: partition of $V(G)$.

Divide $partition$ in $small\\_communities$ and $big\\_communities$ (a
community is small if contains less than the $2\%$ of vertices)

for $community$ in $small\\_communities$ do

find the highest Jacard index between the $community$ and the
$big\\_communities$

merge the communities with the highest Jacard index

update $partition$

end for

Output:

  * $partition$: partition of $V$ without small communities.

The last step in the search for communities is completed by Algorithm 5, which
takes in input $A$, $partition$, $r$, $dmax$ and $dmin$. Then, for all
vertices in a community it counts the ratio of the number of neighbours inside
the community among the total number of neighbours. If this ratio is less than
$r$, it expands the community with all vertices within distance $dmax$ from
the considered vertex, otherwise the community is expanded with all vertices
within distance $dmin$. The overlapping communities needed for the GBF-PUM
interpolation (Algorithm 6) are given as output.

Algorithm 5 expand_communities

Input:

  * $A$: adjacency matrix of the graph $G$, $partition$: partition of $V(G)$, $r$: ratio of neighbours of a vertex inside the community over the total number, $dmax$: distance of max augmentation, $dmin$: distance of min augmentation.

for $i\leq|partition|$ do

for $v$ in $partition(i)$ do

$N(v)\rightarrow$ neighbours of $v$

$N(v)_{in}\rightarrow$ neighbours of $v$ inside $community$

if $|N(v)_{in}|<r*|N(v)|$ then

add to $partition(i)$ all the vertices within distance of $dmax$ from $v$

else

add to $partition(i)$ all the vertices within distance of $dmin$ from $v$

end if

end for

end for

Output:

  * $partition$: partition of $V$ with expanded communities.

###  3.2 Computational complexity of Algorithm 1

To analyse the computational complexity of Algorithm 1 we have to evaluate the
complexity of the other algorithms called during the procedure. We remark here
that logarithms are taken base 2. In details, in Algorithm 3, _split_net_ ,
the minimum-cut procedure costs $O(|c_{i}||E(c_{i})|+|c_{i}|^{2}\log(|c_{i}|)$
for each community $c_{i}$. Hence its total computation time in one iteration
is

$\sum_{i=1}^{|C|}O(|c_{i}||E(c_{i})|+|c_{i}|^{2}\log(|c_{i}|)\leq
O(|V||E|+|V|^{2}\log(|V|).$

On the other hand, calculating the Katz centrality for the vertices in $G$
takes $O(|V|+|E|)$, when the power iteration algorithm is used. Hence,
Algorithm 3 has the same complexity as the minimum-cut.

The computation of the modularity for each community should also be considered
when estimating the total complexity. As the changes of $Q$ are tracked during
the execution, its complexity is bounded by $O(|V|+|E|)$. Moreover,
calculating the Jaccard index between the communities takes $O(|V|^{2})$ in
the worst-case scenario $|C|=|V|$. All the other executions of the procedures
take linear time. Hence, both the evaluation of modularity and Jaccard index
do not affect the total time complexity as they are faster than Algorithm 3.
We can conclude that in the worst possible case when the number of iterations
is exactly equal to $|V|$, the total time complexity is

$O(|V|^{2}|E|+|V|^{3}\log(|V|)\approx O(|V|^{3}\log(|V|),$

which is in polynomial time.

###  3.3 GBF-PUM approximation on graphs

Partition of unity is a widespread tool used in mesh-free approximation
problems as it sharply reduces the computational cost when related subproblems
are solved [11]. In [5] and [6] this technique has been adapted to graph
signal interpolation and it may be applied to social networks or traffic map
problems because of their underlying graph structure. Once the overlapping
communities of a graph are found, to construct a partition of unity we need a
set of functions $\varphi^{(j)}\in\mathcal{L}(G)$, $j=1,\dots,|C|$, such that:

  * 1.

$\rm{supp}(\varphi^{(j)})\subseteq V_{j}$;

  * 2.

$\varphi^{(j)}\geq 0$;

  * 3.

$\sum_{j=1}^{|C|}\varphi^{(j)}(v)=1$, $\forall v\in V$.

In particular, we choose the characteristic function
$\varphi^{(j)}(v)=\mathbbm{1}_{V_{j}}(v)=\begin{cases}1\text{ if $v\in
V_{j}$}\\\ 0\text{ if $v\not\in V_{j}$}\end{cases}$, to get the following
partition of unity:

$\varphi^{(j)}(v)=\frac{\mathbbm{1}_{V_{j}}(v)}{|j\in\\{1,\dots,|C|:v\in
V_{j}\\}|}.$

The main step of this process is the calculation of the local approximants
$x_{\star}^{(j)}$ on the subgraph $G_{j}$ corresponding to the $j$-th
community. This is done by using a GBF approximation scheme, as shown in
Subsection 2.2. When the local approximants are computed, the global GBF-PUM
approximation scheme on the entire graph $G$ is:

$x_{\star}(v)=\sum_{j=1}^{|C|}\varphi^{(j)}(v)x_{\star}^{(j)}(v).$

We remark that overlapping subdomains are needed for a good PUM. Further
details on the error of the global approximant can be found in [6]. The
following Algorithm 6 traces the steps to obtain the global interpolant.
Unlike the other pseudocodes presented above, Algorithm 6 is described
verbosely as all other procedures except community detection are well-known in
literature. The reader may find further details about them in [6, Section 4].

Algorithm 6 GBF-PUM Approximation on Graphs

Input:

  * $A$: adjacency matrix of the graph $G$, $W$: interpolation vertices, $r$: ratio of neighbours of a vertex inside the community over the total number, $dmax$: distance of max augmentation, $dmin$: distance of min augmentation.

Find the overlapping communities $C$ applying community detection (Algorithm
1)

Construct a partition of unity subordinate to the communities in $C$

For all subgraphs $c$ in $C$ calculate the local Laplacian $L^{c}$

For all subgraphs $c$ in $C$ construct the local GBF kernel

For all subgraphs $c$ in $C$ calculate the local GBF approximant

Create a global GBF-PUM approximation from the local ones

Output:

  * $x_{\star}$: GBF-PUM approximant of the signal.

##  4 Numerical examples

In what follows, we exhibit the subdivision ability of the algorithm by
considering Zachary’s Karate Club graph [24]. Then, numerical results obtained
by applying our framework on the Minnesota Road Graph [18], using a test
function as a signal on its vertices, and on the real dataset of the freight
transport dataset of Brussels [13] are presented. To perform tests, the values
of $r=0.75$, $dmax=6$, $dmin=4$ are set as input for Algorithm 1.

All tests were carried out on the infrastructure for high-performance
computing _MathHPC_ , virtual cloud server of the structure _HPC4AI_ (High-
Performance Computing for Artificial Intelligence:
https://www.dipmatematica.unito.it/do/progetti.pl/View?doc=Laboratori_di_ricerca.html).

###  4.1 Zachary’s Karate Club graph

Figure 1: The Zachary’s Karate Club graph two communities.

Figure 2: On the left it is shown how a bad selection of the sample nodes
leads to a non-subdivision of the network. On the right, when the two sample
nodes are chosen as the instructor and the administrator of the karate club
the algorithm finds the ground truth two communities. The sample nodes are
dotted in yellow.

Zachary’s Karate Club graph is a 34-vertex, 78-edge social network of a
University Karate Club, described in the paper [24]. During the study, a
conflict arose between the administrator and the instructor, hence splitting
the club into two parts. Half of the members formed a new club around the
instructor; members from the other part found a new instructor or gave up
karate. These ground-truth communities are depicted in Figure 1.

Let $W=\\{u_{1},u_{2}\\}$ be the set of sampling nodes for the community
algorithm, and suppose that $u_{1},u_{2}$ are neighbours. An execution of
Algorithm 1 does not perform any subdivision as there is no way to increase
the modularity by splitting the two sample nodes. On the other hand, if we
choose $u_{1}$ and $u_{2}$ as the node corresponding to the instructor and the
administrator, our algorithm performs exactly one subdivision splitting the
network into the well-known two communities, see Figure 2.

###  4.2 Minnesota Road Graph

The Minnesota Road Graph is a 2642-vertex, 3304-edge network representing,
respectively, intersections and roads of the State of Minnesota [20]. A test
function based on the Laplacian matrix introduced in [5] and [6] has been
adapted and used as a signal on the vertex set to apply the presented
algorithms.

Figure 3: On top, the partition of the vertices in 9 different disjoint
subdomains is shown. It is obtained using 800 interpolation nodes. On bottom,
a subdomain is highlighted to show how it is expanded when creating the
overlap (left to right).

The communities are shown in Figure 3, whereas numerical results are
summarised in Table 1. We would like to remark that the number of communities
found by the divisive Algorithm 1 only depends on the centrality values of the
sample vertices. The number of detected communities, Relative-Max-Absolute-
Error (RMAE), Relative-Root-Mean-Squared-Error (RRMSE), and computational time
to the variation of the number of interpolation vertices are shown in Table 1.

$W$ | Communities | RMAE | RRMSE | time (s)
---|---|---|---|---
400 | 11 | 3.509e-01 | 3.208681e-02 | 1.425e+02
800 | 9 | 9.276e-02 | 5.880306e-03 | 1.879e+02
1200 | 11 | 1.977e-02 | 1.444769e-03 | 1.587e+02
1600 | 10 | 1.517e-02 | 6.787503e-04 | 1.586e+02
2000 | 9 | 5.078e-03 | 2.122356e-04 | 1.690e+02
Table 1: A summarisation of the numerical results for increasing number of
sampling nodes in the Minnesota Road Graph. The number of communities, RMAE,
RRMSE, and computational time are also shown.

###  4.3 Brussel Freight Transport network

The Brussel Freight Transport Network is a 4540-vertex, 14946-edge graph
representing the road network of the city of Brussels [13]. For 3451 vertices,
a measurement of the flow every 15 minutes is available. As signal for the
numerical test, we will consider a single-time measure of the flow in the
sample vertices. The associated real data problem will be reconstructing the
missing value via GBF-PUM interpolation, whereas for testing purposes we
considered the largest connected component of the vertices on which we know
the flow. A sample of found communities is shown in Figure 4, while numerical
results are reported in Table 2.

Figure 4: On top the division in communities of the Brussel Freight Transport Network using 1200 sample nodes and the expansion of one of them is shown (left to right). On bottom the sample set of measures is highlighted in red, whereas the unknown values to predict are in green. $W$ | Communities | RMAE | RRMSE | time (s)
---|---|---|---|---
400 | 15 | 1.500e+01 | 6.881386e-02 | 2.767e+02
800 | 7 | 9.173e-01 | 6.087108e-02 | 2.752e+02
1200 | 15 | 8.015e-01 | 4.673573e-02 | 2.768e+02
1600 | 9 | 6.286e-01 | 3.925505e-02 | 2.253e+02
2000 | 17 | 5.845e-01 | 3.011343e-02 | 2.168e+02
2400 | 16 | 6.538e-01 | 2.435230e-02 | 2.166e+02
2800 | 12 | 3.589e-01 | 1.770847e-02 | 1.974e+02
3200 | 6 | 1.732e-01 | 7.304001e-03 | 1.629e+02
Table 2: A summarisation of the numerical results for increasing number of
sampling nodes in the Brussel Freight Transport Network. The number of
communities, RMAE, RRMSE and computational time are also shown.

##  5 Conclusions

From the numerical experiments (Table 1 and Table 2) we note that when the
number of sample nodes increases, also does the precision of the GBF-PUM
method. We remark that in the case of a real dataset, this behaviour is less
noticeable but still significant, due to the nature of the data. Moreover, the
proposed method does not require the number of subdomains for the PUM as an
input and it goes in the direction of finding a reasonable number of
subdomains for PUMs in an automatic way. This is a well-studied problem not
only when working with graphs or networks, but also in the context of
interpolation and approximation of sparse data, when solving PDEs [14] and
within a stochastic framework [7]. As future work, an automatic routine also
for community augmentation may be investigated.

### Acknowledgments

This work has been supported by the INdAM–GNCS 2022 Project “Computational
methods for kernel-based approximation and its applications”, code
CUP$\\_$E55F22000270001, and by the Spoke “FutureHPC & BigData” of the ICSC –
National Research Center in ”High-Performance Computing, Big Data and Quantum
Computing”, funded by European Union – NextGenerationEU. Moreover, the work
has been supported by the Fondazione CRT, project 2022 “Modelli matematici e
algoritmi predittivi di intelligenza artificiale per la
mobilit$\grave{\text{a}}$ sostenibile”.

## References

  * [1] N. Aronszajn, Theory of reproducing kernels, Trans. Amer. Math. Soc. 68 (1950), 337–404.
  * [2] J.A. Bondy, U.S.R. Murty, Graph Theory, Springer Series: Graduate Texts in Mathematics. Springer London, 2008.
  * [3] R. Cavoretto, Adaptive radial basis function partition of unity interpolation: A bivariate algorithm for unstructured data, J. Sci. Comput. 87 (2021), 41.
  * [4] R. Cavoretto, A. De Rossi, Error indicators and refinement strategies for solving Poisson problems through a RBF partition of unity collocation scheme, Appl. Math. Comput. 369 (2020), 124824.
  * [5] R. Cavoretto, A. De Rossi, W. Erb, GBFPUM - A MATLAB Package for Partition of Unity Based Signal Interpolation and Approximation on Graphs, Dolomites Res. Notes Approx. 15 (2022), 25–34.
  * [6] R. Cavoretto, A. De Rossi, W. Erb, Partition of Unity Methods for Signal Processing on Graphs, J. Fourier Anal. Appl. 27 (2021), 66.
  * [7] R. Cavoretto, A. De Rossi, E. Perracchione, Learning with partition of unity-based kriging estimators, Appl. Math. Comput. 448 (2023), 127938.
  * [8] W. Erb, Graph Signal Interpolation with Positive Definite Graph Basis Functions, Appl. Comput. Harmon. Anal. 60 (2022), 368–395.
  * [9] W. Erb, Semi-Supervised Learning on Graphs with Feature-Augmented Graph Basis Functions. arXiv:2003.07646 (2020).
  * [10] G.E. Fasshauer, Meshfree Approximation Methods with MATLAB, World Scientific, Singapore, 2007, 500 pp.
  * [11] G.E. Fasshauer, M.J. McCourt, Kernel-based Approximation Methods Using MATLAB, World Scientific, Singapore, 2015, 536 pp.
  * [12] S. Fortunato, Community detection in graphs, Phys. Report 486 (2010), 75–174.
  * [13] T. Guns, S. Hadavi, C. Macharis, S. Verlinde, W. Verbekem Monitoring Urban-Freight Transport Based on GPS Trajectories of Heavy-Goods Vehicles, IEEE Transactions on Intelligent Transportation Systems 20(10) (2019), 3747–3758.
  * [14] E. Larsson, V. Shcherbakov, A. Heryudono, A least squares radial basis function partition of unity method for solving PDEs, SIAM J. Sci. Comput. 39 (2017), A2538–A2563.
  * [15] M. Newman, Networks: An Introduction, OUP Oxford, 2010, 784 pp.
  * [16] A. Ortega, P. Frossard, J. Kovačević, J.M.F. Moura, P. Vandergheynst, Graph signal processing: overview, challenges, and applications, Proc. IEEE 106(5) (2018), 808–828.
  * [17] I.Z. Pesenson, Variational splines and Paley-Wiener spaces on combinatorial graphs, Constr. Approx. 29(1) (2009), 1–21.
  * [18] R.A. Rossi, N.K. Ahmed, The Network Data Repository with Interactive Graph Analytics and Visualization, in Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015, _http://networkrepository.com_.
  * [19] R. Schaback, H. Wendland, Approximation by Positive Definite Kernels, in Advanced Problems in Constructive Approximation, Birkhäuser Verlag, Basel, 2003, pp. 203–222
  * [20] D.I. Shuman, B. Ricaud, P. Vandergheynst, Vertex-frequency analysis on graphs, Appl. Comput. Harm. Anal. 40(2) (2016), 260–291.
  * [21] L. Stanković, L. Daković, E. Sejdić, Introduction to Graph Signal Processing, in Vertex-Frequency Analysis of Graph Signals, Springer, 2019, pp. 3–108.
  * [22] J.P. Ward, F.J. Narcowich, J.L. Ward, Interpolating splines on graphs for data science applications, Appl. Comput. Harm. Anal. 49(2) (2020), 540–557.
  * [23] H. Wendland, Scattered Data Approximation, Cambridge University Press, Cambridge, 2005, 336 pp.
  * [24] W.W. Zachary, An Information Flow Model for Conflict and Fission in Small Groups, Jour. of Anthropological Research 33(4) (1977), 452–473.