Horospherical Cauchy Transform on Some Pseudo-Hyperbolic Spaces

Horospherical Cauchy Transform
on Some Pseudo-Hyperbolic Spaces††This paper is a contribution to the Special
Issue on Algebra, Topology, and Dynamics in Interaction in honor of Dmitry
Fuchs. The full collection is available at
https://www.emis.de/journals/SIGMA/Fuchs.html

Simon GINDIKIN

S. Gindikin

Department of Mathematics, Hill Center, Rutgers University,
110 Frelinghysen Road, Piscataway, NJ 08854, USA<EMAIL_ADDRESS>
Received October 28, 2019, in final form March 29, 2020; Published online
April 07, 2020

We consider the horospherical transform and its inversion in 3 examples of
hyperboloids. We want to illustrate via these examples the fact that the
horospherical inversion formulas can be directly extracted from the classical
Radon inversion formula. In a more broad context, this possibility reflects
the fact that the harmonic analysis on symmetric spaces (Riemannian as well as
pseudo-Riemannian ones) is equivalent (homologous), up to the Abelian Fourier
transform, to the similar problem in the flat model. On the technical level it
is important that we work not with the usual horospherical transform, but with
its Cauchy modification.

pseudo-hyperbolic spaces; hyperboloids; horospheres; horospherical transform;
horospherical Cauchy transform

32A45; 33C55; 43A75; 44A12

To Mitya Fuchs, my dear friend of more
than 60 years, on his 80th birthday.

##  1 Introduction

We realize pseudo-hyperbolic geometries on the $(n-1)$-dimensional
hyperboloids $X_{p,q}\subset{\mathbb{R}}^{n}$, $n=p+q,$ defined by the
equations

$\displaystyle\square(x)=\square_{p,q}(x)=(x_{1})^{2}+\cdots+(x_{p})^{2}-(x_{p+1})^{2}-\cdots-(x_{p+q})^{2}=1.$

We do not exclude the case $q=0$, where we have the sphere. $X_{p,q}$ carries
a transitive action of the group ${\rm SO}(p,q)$, and this action preserves
the pseudo-hyperbolic metric.

We will consider the following 3 examples. In the 1st example $p=1$, $q=n-1$,
we have the classical hyperbolic geometry, and this is an example of a
Riemannian non-compact symmetric space. The 2nd example is that of the sphere
$S^{n-1}=X_{n,0}$. This is an example of a compact Riemannian symmetric space.
Our final example is that of $X_{2,n-2}$, which models the pseudo-hyperbolic
geometry; it is a pseudo-Riemannian symmetric space that includes the group
${\rm SL}(2;{\mathbb{R}})$.

In all of these cases the inversion of the horospherical transform is the
result of the same construction: the application of a universal fundamental
closed differential form on the set of hyperbolic sections of hyperboloids. We
deform the cycle of horospheres into a special cycle of hyperplane sections
(we call it a geodesic cycle), on which the inverse transform is equivalent to
the one given by the classical Radon inversion formula.

Let us discuss the conceptual picture which we illustrate by the simplest
examples in this paper. There are 2 parallel languages in harmonic analysis on
symmetric spaces. One is the original spectral approach that uses the
decomposition into irreducible representations. This can be interpreted as the
spherical Fourier transform. The other one is the horospherical transform of
Gelfand – the analog of the affine Radon transform in which affine hyperplanes
are replaced by horospheres in the symmetric spaces. These 2 transforms are
connected by the (Abelian) Mellin transform. The translation from one language
to another can help with some problems. Here is the most important example:
the inverse spherical Fourier transform (Plancherel formula) can be deduced
from the inverse horospherical formula.

It may not be easy to use this simple connection between 2 languages in order
to obtain explicit statements and formulas as there are facts that are
specific to one of the languages. The focus of this paper is one such fact in
the example of hyperboloids: the inversion of the horospherical transform is
equivalent (homologous!) to a similar problem for the flat models, which is a
simple modification of the Radon inversion formula.

Specifically, we consider for functions with support on a hyperboloid their
integrals over hyperplane sections. The problem of the reconstruction of
functions through these integrals is overdetermined. Our principal
construction is that of a universal closed differential form on the space of
hyperplane sections. We call it the fundamental form for hyperboloids.
Different inversion formulas for the Radon transform on the hyperboloids can
be produced by the integration of this closed form over different cycles in
the space of sections.

A special role is played by the cycle which we call geodesic. It is the cycle
of hyperplane sections passing through the origin. Using the central
projection we can interpret the restriction to the geodesic cycle as a version
of the projective Radon transform [1], and the Radon inversion formula gives
the inversion of this transform. It plays the role of the flat model for our
problem. In the case of the sphere, it is the Minkowski–Funk transform.

The inversion formula on the geodesic cycle coincides with the restriction of
the fundamental closed form. The same will be true for homologous cycles. In
particular, we construct a contraction of the cycle of horospheres to the
geodesic cycle. In the case of a compact or a pseudo-Riemannian symmetric
space we need one more essential ingredient that we obtain by defining the
complex horospherical transform on real hyperboloids. As we illustrate by the
3rd example, we need the complex horospheres if there are discrete series of
representations. The construction of the horospherical transform is more
complicated and takes values in $\bar{\partial}$-cohomology. We will consider
it in another paper.

##  2 Preliminary constructions

Let us start with some definitions and facts for an arbitrary $X=X_{p,q}$. We
will assume here that all functions satisfy $f\in C_{0}^{\infty}(X)$.
Sometimes we interpret them as functions on ${\mathbb{R}}^{n}$ with support on
the hyperboloid $X$. We will need some notations for differential forms. Let
us denote by $[a_{1},\dots,a_{n}]$ the determinant of the matrix with columns
$a_{1},\dots,a_{n}$, some of the entries can be 1-forms. We expand such
determinants from left to right and use the exterior product for the
multiplication of 1-forms. Such a determinant with identical columns can
differ from zero: $[{\rm d}x,\dots,{\rm d}x]=n!{\rm
d}x_{1}\wedge\cdots\wedge{\rm d}x_{n}$. We will write $a^{\\{k\\}}$ if a
column $a$ is repeated $k$ times.

Recall that by definition the interior product of forms, $\varphi\rfloor\psi$,
is a form $\alpha$ such that $\varphi\wedge\alpha=\psi$. Its restriction to
the submanifold where $\varphi=0$ is uniquely defined. If $\varphi={\rm d}f$
where $f$ is a function, then ${\rm d}f\rfloor\psi$ is, up to a constant
factor, the residue of $\psi/f$ at $\\{f=0\\}$.

Let ${\mathbb{R}}^{n}_{\xi}$ and ${\mathbb{R}}^{n}_{x}$ be two copies of
${\mathbb{R}}^{n}$, and consider the pairing

${\mathbb{R}}^{n}_{\xi}\times{\mathbb{R}}^{n}_{x}\longrightarrow{\mathbb{R}},\qquad(\xi,x)\mapsto\langle\xi,x\rangle,$

where the bilinear form $\langle\xi,x\rangle$ is the one that corresponds to
the quadratic form $\square_{p,q}$. Let us define the Radon–Cauchy transform
[2, 5] of $f$ to be

$\hat{f}(\xi,p)=\int_{X}\frac{f(x)}{\langle\xi,x\rangle-p-{\rm
i}0}\omega_{p,q}(x,{\rm d}x),$

where

$\omega_{p,q}(x,{\rm d}x)=2{\rm d}(\square_{p,q}(x))\rfloor\big{[}{\rm
d}x^{\\{n\\}}\big{]}=(n-1)!\sum_{1\leq j\leq
n}(-1)^{(j-1)}\delta_{j}x_{j}\bigwedge_{i\neq j}{\rm d}x_{i};$

here $\delta_{j}$ are the coefficients of $(x_{j})^{2}$ in $\square_{p,q}(x)$.
It is invariant on $X$. Also

$\lim_{\varepsilon\rightarrow 0}\frac{1}{p-{\rm i}\varepsilon}=(p-{\rm
i}0)^{-1}=p^{-1}+{\rm i}\pi\delta(p).$

This definition is obtained from the usual definition of the Radon transform
by replacing $\delta(t)$, $t=\langle\xi,x\rangle-p$, with the distribution
$(t-{\rm i}0)^{-1}$. As a result, the usual Radon inversion formula,
originally valid only for $n$ odd, gets extended to any $n$. The Radon and
Cauchy–Radon transforms are easily expressed through one another. We have

$\hat{f}(\lambda\xi,\lambda p)=\lambda^{-1}\hat{f}(\xi,p),\qquad\lambda>0.$

Let $\hat{f}(\xi)=\hat{f}(\xi,1)$.

So the Cauchy–Radon transform on $X_{p,q}$ is a special case of the
Cauchy–Radon transform in ${\mathbb{R}}^{n}$. We investigate specific
properties of $\hat{f}$ if $f\in C_{0}^{\infty}(X)$ (i.e., has the support in
$X$). Let us remark that $\dim X=n-1$, but $\hat{f}$ is the result of
integration on an $n$-parametric family of sections of $X$ by the hyperplanes
in ${\mathbb{R}}^{n}$. Specifically, this can be expressed as the fact that
$\hat{f}$ is a solution of the ultrahyperbolic equation

$\left\\{\square_{p,q}\left(\frac{\partial}{\partial\xi}\right)-\frac{\partial^{2}}{\partial
p^{2}}\right\\}\hat{f}(\xi,p)=0.$

The problem of reconstructing $f$ on $X$ from $\hat{f}$ is overdetermined and
equivalent to boundary problems for these ultrahyperbolic equations. Therefore
it is natural to reconstruct $f$ on $X$ not from $\hat{f}$ for all $\xi$, $p$,
but only from some $(n-1)$-parametric subfamilies. Of course, we need to
remember that $\hat{f}$ is homogeneous.

Finally, recall the following technical lemma

######  Lemma 2.1.

${\rm d}\big{[}a(\xi),\xi,{\rm
d}\xi^{\\{n-2\\}}\big{]}=-\frac{1}{n-2}\left(\sum_{1\leq j\leq
n}\frac{\partial a_{j}(\xi)}{\partial\xi_{j}}\right)\big{[}\xi,{\rm
d}\xi^{\\{n-1\\}}\big{]}.$

The proof is a direct computation; it is simplified by the observation that it
is sufficient to consider the case where the column $a(\xi)$ has at most one
non-zero element.

##  3 Fundamental form for hyperboloids

As we mentioned above, functions $f$ on hyperboloids depend on $n-1$
variables, but their Radon transform $\hat{f}$ depends on $n$ variables.
Therefore the inversion formula cannot be unique. We will relate various such
formulas with certain $(n-1)$-dimensional subfamilies of hyperplane sections.

Our basic tool is a remarkable fundamental differential form on
$X\times{\mathbb{R}}^{n}_{\xi}$:

$\displaystyle\kappa_{x}[f]=\frac{f(u)}{(\langle\xi,(u-x)\rangle-{\rm
i}\varepsilon)^{n-1}}\omega_{p,q}(u,{\rm d}u)\wedge\big{[}x+u,\xi,{\rm
d}\xi^{\\{n-2\\}}\big{]},\qquad u\in
X,\quad\xi\in{\mathbb{R}}^{n}\backslash\\{0\\}.$

Here $f$ is a fixed function on the hyperboloid $X$, $x\in X$ is a fixed
point, $\varepsilon>0$ is a constant which we use for regularization and
eventually let $\varepsilon\to$0; $\xi$ are parameters of hyperplane sections.
Let us remark that the 1st factor in the form differs from the form in the
definition of $\hat{f}$ only by the exponent in the denominator.

######  Proposition 3.1.

The form $\kappa_{x}[f]$ is closed on $X\times{\mathbb{R}}^{n}_{\xi}$.

Indeed, in $u$, this a maximal degree form; in $\xi$, we take

$a(\xi)=\frac{u+x}{(\langle\xi,(u-x)\rangle-{\rm i}\varepsilon)^{n-1}}$

and then apply our formula for the differential of the determinant above. The
result will contain the factor

$\square_{p,q}(u)-\square_{p,q}(x)=1-1=0.$

We will reconstruct $f(x)$ by integrating this closed form $\kappa_{x}[f]$
along different cycles and then regularizing as $\varepsilon\to 0$. Let
$\gamma(x)$ be the cycle of sections passing through a fixed point $x\in X$,
homological to the sphere $S^{n-2}$. Let $\gamma_{0}(x)$ be the cycle of
sections that pass through $x$ and 0; we call $\gamma_{0}(x)$ geodesic.

######  Proposition 3.2.

For $\varepsilon=0$ we have

$\int_{X\times\gamma(x)}\kappa_{x}[f]=cf(x),\qquad c=\frac{2(2\pi{\rm
i})^{n-1}}{(n-1)!}.$

Here $\varepsilon=0$, $\gamma(x)$ is an $(n-2)$-dimensional cycle in $\xi$,
homologous to the sphere $S^{n-2}$.

For the proof it is enough to consider one point $x$ (using the invariance of
$X_{p,q}$) and the geodesic cycle $\gamma_{0}(x)$. Let $x=(1,0,\dots,0)$ and
consider $\gamma_{0}(x)$. On this cycle $\xi_{1}=0$, $\xi=(0,\eta)$. As a
result, the factor that contains the determinant is

$(1+u_{1})\big{[}\eta,{\rm d}\eta^{\\{n-2\\}}\big{]},$

and therefore the integral is the sum of two terms.

If $f(u)$ is even then the 1st term is even, but the 2nd one includes $u_{1}f$
and is odd; so the integral of the 2nd one is zero. The integral of the 1st
one is $cf(x)$ as follows from the projective Radon inversion formula [1] in
the Cauchy form (the central projection). If $f$ is odd, then the 1st term
gives zero, but the 2nd one gives $cx_{1}f(x)=cf(x)$. So the two terms in the
form work for even and odd components of the function $f$ respectively.

For the inversion of $\hat{f}$ for general cycles $\gamma(x)$ we need to
express the restriction of the form $\kappa_{x}[f]$ to the cycle through
$\hat{f}$. It follows from the last proposition that generically we can do it
using restrictions of $\hat{f}$ and its 1st derivatives (the Cauchy problem
for the ultrahyperbolic equation!). In integral geometry we are interested in
the special case where it is sufficient to know restrictions of $\hat{f}$ –
the characteristic cycles $\gamma(x)$ (Goursat problem). The description of
such cycles (also known as admissible sets) is a very interesting problem, see
[1], but we investigate here only one important class – the horospherical
cycles.

##  4 The hyperbolic space $\boldsymbol{X_{1,n-1}}$

Let us start with the case of the two-sheeted hyperboloid $X=X_{1,n-1}$, which
carries an action of the group ${\rm SO}(1,n-1)$, and we will only work with
one of its sheets: $X_{+}=\\{x_{1}>0\\}$.

The horospherical inversion formula is well known in the hyperbolic case, but
we want to illustrate in this example the method that we discuss in this
paper. I believe it explains the old observation made by Gelfand that this
inversion coincides with Radon’s inversion formula.

So we consider the hyperplane sections $L(\xi,p)$ of $X_{+}$ by the hyperbolic
spheres

$\langle\xi,x\rangle=p,\qquad\xi\neq 0.$

For $p=0$ (hyperplanes passing through 0) we have hyperbolic geodesic
hyperplanes. Hyperbolic geodesic Radon transform is projectively equivalent to
the Euclidean Radon transform [1].

The sections $L(\xi,p)$ by isotropic hyperplanes

$\square_{1,n-1}(\xi)=0,\qquad\xi\neq 0,$

are called horospheres $E(\xi,p)$. They can be interpreted as limits of
hyperbolic spheres. So such $\xi$ are points of the cone $\Xi_{1,n-1}$,
$\xi\neq 0$ (also known as the asymptotic cone) that corresponds to the
hyperboloid $X$. Here $p\neq 0$, since for $p=0$ the sections have no points.
In the case of horospheres we call $\hat{f}$ the horospherical Cauchy
transform:

${\mathcal{H}}f(\xi,p)=\int_{X}\frac{f(x)}{\langle\xi,x\rangle-p-{\rm
i}0}\omega_{1,n-1}(x,{\rm d}x),\qquad\square_{1,n-1}(\xi)=0.$

It is sufficient to consider $p=1$. We want to reconstruct $f(x)$ from
${\mathcal{H}}f$.

Let $\gamma_{1}(x)$ be the $(n-2)$-dimensional cycle of horospheres passing
through $x$. It is enough to consider a fixed point, and so let
$x=(1,0,\dots,0)$. Then on $\gamma_{1}$ we have $\xi_{1}=p$, $\xi=(p,\eta)$,
$p^{2}=\bigtriangleup(\eta)=(\eta_{1})^{2}+\cdots+(\eta_{n-1})^{2}$. Therefore

$\xi=\big{(}\sqrt{\bigtriangleup(\eta)},\eta\big{)},\qquad
p=\sqrt{\bigtriangleup(\eta)}.$

There is a natural retraction of the horospherical cycle $\gamma_{1}(x)$ on
the geodesic cycle $\gamma_{0}(x)$ through cycles $\gamma_{\rho}(x)$,
$0\leq\rho\leq 1$, of the hyperplane intersections $L(\xi,p)$ with

$\xi=\big{(}\rho\sqrt{\bigtriangleup(\eta)},\eta\big{)},\qquad
p=\rho\sqrt{\bigtriangleup(\eta)}.$

All $\gamma_{\rho}$ pass through $x$. Geometrically, we transform geodesic
hyperbolic hyperplanes through hyperbolic spheres in hyperbolic horospheres.

To obtain the horospherical inversion formula we take the cycle $\gamma_{1}$
in Proposition 3.2 and we need to express the restriction of the form
$\kappa_{x}[f]$ to this cycle in terms of the restriction of the horospherical
transform ${\mathcal{H}}$. We need to remove $u$ from the determinant
$\big{[}x+u,\xi,{\rm d}\xi^{\\{n-2\\}}\big{]}$ (generically, only this part
requires transversal derivatives of $\hat{f}$). We can do this specifically
for horospheres by using one more trick with determinants.

We want to rewrite formulas below for arbitrary $x\in X$ (not only for
$x=(1,0,\dots,0)$). So $\square(x)=1$, $\square(\xi)=0$,
$\langle\xi,x\rangle=p$. Here $p\neq 0$. If $\xi=x+\eta$,
$\langle\eta,x\rangle=0$, then $\square(\eta)=\langle\eta,\eta\rangle=p-1$.

The transformation of the form $\kappa_{x}[f]$ uses the following important
fact. If $\square(\xi)=0$, $\langle\lambda,\xi\rangle\neq 0$ then the form

$\frac{\big{[}\lambda,\xi,{\rm
d}\xi^{\\{n-2\\}}\big{]}}{\langle\lambda,\xi\rangle}$

is independent of $\lambda$. If we let for simplicity $\xi_{1}\neq 0$, then it
is enough to add to the 1st row the $j$-th row (any $j$ will do) with
coefficient $\xi_{j}/\xi_{1}$. As a result, all entries of the 1st row, except
for the 1st one, will be 0, while the 1st one will equal
$\langle\xi,\lambda\rangle/\xi_{1}$, and thus $\lambda$ disappears from the
formula. The conceptual meaning of the $\lambda$-independence is that this
form is the residue-form of

$\big{[}\xi,{\rm d}\xi^{\\{n-1\\}}\big{]}/\square(\xi)$

on the horospherical cycle $\square(\xi)=0$. A special case of this
independence gives

$\big{[}x+u,\xi,{\rm
d}\xi^{\\{n-2\\}}\big{]}=\frac{\langle\xi,(x+u)\rangle}{\langle\xi,x\rangle}\big{[}x,\xi,{\rm
d}\xi^{\\{n-2\\}}\big{]}=\left(2+\frac{\langle\xi,(u-x)\rangle}{p}\right)\big{[}x,\xi,{\rm
d}\xi^{\\{n-2\\}}\big{]};$

in the last determinant we can replace $\xi$ with $\eta$. The substitution in
$\kappa_{x}[f]$ on the horospherical cycle gives

$\displaystyle\int_{X\times\gamma_{1}(x)}f(u)\left(\frac{2}{(\langle\xi,(u-x)\rangle-{\rm
i}0)^{n-1}}+\frac{1}{p(\langle\xi,(u-x)\rangle-{\rm i}0)^{n-2}}\right)$
$\displaystyle\qquad{}\times\big{[}u,{\rm
d}u^{\\{n-1\\}}\big{]}\wedge\big{[}x,\xi,{\rm
d}\xi^{\\{n-2\\}}\big{]}=\frac{2(2\pi{\rm i})^{n-1}}{(n-1)!}f(x).$

Let us emphasize that in these transformations it was essential that we
consider horospheres ($\square(\xi)=0$). Now we can express the form $\kappa$
through the horospherical transform ${\mathcal{H}}f$. Let us define the
differential operator

${\mathcal{L}}_{p}=\frac{n-2}{p}\left(\frac{\partial}{\partial
p}\right)^{n-3}+2\left(\frac{\partial}{\partial p}\right)^{n-2}.$

######  Theorem 4.1.

One has the horospherical inversion formula

$f(x)=\frac{n-1}{2(2\pi{\rm
i})^{n-1}}\int_{\gamma_{1}(x)}{\mathcal{L}}_{p}\hat{f}(x+{\rm
i}\eta,p)|_{p=1}\big{[}x,\eta,{\rm d}\eta^{\\{n-2\\}}\big{]}.$

Often in the definition of the hyperbolic horospherical transform, a factor is
added which makes the inversion formula slightly different. For the transition
from the hyperbolic horospherical transform to the harmonic analysis on the
hyperbolic space $X_{1,n-1}$ – the spherical Fourier transform on $X$ – we
need to compose the horospherical transform with the Mellin transform on the
one-parametric dilations of the cone $\Xi_{1,n-1}$:

$\xi\to\lambda\xi,\qquad\lambda\in{\mathbb{R}}^{+}.$

##  5 The sphere $\boldsymbol{S^{n-1}=X_{n,0}}$

We use in this section $\Delta$ instead $\square_{n,0}$. Therefore on the
$(n-1)$-dimensional sphere $S^{n-1}$ we have $\Delta(x)=1$. We want to find
$S^{n-1}$-analogs of the constructions from the last section. However, there
are no real horospheres on the sphere since $\Delta(\xi)\neq 0$ if $\xi\neq
0$, and we consider complex horospheres instead [4]. In other words, we
continue to work with the real sphere and its points, but we take sections by
complex hyperplanes $\langle\zeta,z\rangle=p+{\rm i}q$, $\zeta=\xi+{\rm
i}\eta$, $\zeta\neq 0\in{\mathbb{C}}^{n}$ with complex points
$z\in{\mathbb{C}}S^{n-1}$, including the complex horospheres $E(\zeta,p+{\rm
i}q)$ where $\Delta(\zeta)=0$, $\zeta\neq 0$; the set of such $\zeta$ will be
denoted by ${\mathbb{C}}\Xi$.

We shall focus on complex horospheres (and other hyperplane sections) without
real points on $S^{n-1}$. The reason for doing so is that then the
Cauchy–Radon transform

$\hat{f}(\zeta,p+{\rm i}q)=\int_{S}\frac{f(x)}{\langle\zeta,x\rangle-p-{\rm
i}q}\omega(x,{\rm d}x)$

(where we integrate on the invariant form $\omega_{n,0}$) makes perfect sense
as there are no singularities in the denominator. In this case $\hat{f}$ is
holomorphic in the interior of their domain.

Let us investigate when complex horospheres have no real points on the sphere.
For $\zeta=\xi+{\rm i}\eta$ the condition
$\zeta\in{\mathbb{C}}\Xi(\Delta(\zeta)=0)$, $\zeta\neq 0,$ is equivalent to
the conditions

$\Delta(\xi)=\Delta(\eta),\qquad\langle\xi,\eta\rangle=0.$

On ${\mathbb{C}}\Xi$ we have $\Delta(\xi)=\Delta(\eta)>0$. So, on the
horospheres, one has $p+{\rm i}q\neq 0$, and we can always take $p+{\rm
i}q=1$.

With this normalization the set $\Xi_{+}$ of horospheres without real points
is characterized by the condition

$0<\Delta(\xi)=\Delta(\eta)<1.$

Indeed, using the action of the orthogonal group, the verification can be
reduced to $\xi=(a,0,\dots,0)$, $\eta=(0,b,0,\dots,0)$, in which case there
are no real points on the horosphere iff $0\leq|a|^{2}=|b|^{2}\leq 1$. Without
the condition $p+{\rm i}q=1$ we have $0<\Delta(\xi)<|p+{\rm i}q|^{2}$.

On the boundary $\partial\Xi_{+}$ of the domain $\Xi_{+}$ we have

$\Delta(\xi)=\Delta(\eta)=1.$

If $x\in S$ is a (real) point on the horosphere $E(\zeta)$, then
$\langle\xi,x\rangle=1$, $\langle\eta,x\rangle=0$, thus $x=\xi$, and it is the
unique real point $x$ on $S$; so

$\zeta=x+{\rm i}\eta,\qquad\Delta(\eta)=1,\qquad\langle\eta,x\rangle=0.$

Therefore $\partial\Xi_{+}$ projects on the sphere $S^{n-1}$ with fibers the
orthogonal $(n-2)$-dimensional spheres.

Similarly to the construction in the last section, let us consider the
geodesic cycle $\gamma_{0}(x)$ of hyperplanes passing through the center 0 and
$x\in S^{n-1}$. We construct a deformation of $\gamma_{0}(x)$ in the cycle
$\gamma_{1}(x)$ of complex horospheres with the unique real point $x$ as
follows. Using the invariance, it is enough to consider $x=(1,0,\dots,0)$.
Then the geodesics from $\gamma_{0}(x)$ are sections of $S$, by

$\big{\langle}\zeta^{0},u\big{\rangle}=0,\qquad\zeta^{0}=\big{(}0,\lambda,\lambda\neq
0\in{\mathbb{R}}^{n-2}\big{)}.$

For $0\leq\delta\leq 1$, let

$\zeta^{\delta}=\big{(}{\rm
i}\delta\sqrt{\Delta(\lambda}),\lambda\big{)},\qquad p^{\delta}={\rm
i}\delta\sqrt{\Delta(\lambda)},$

and $L\big{(}\zeta^{\delta},p^{\delta}\big{)}$ are the corresponding sections
by the hyperplanes. For $\delta=0$ we have the cycle $\gamma_{0}(x)$ of
geodesic sections; for $\delta=1$ we have the cycle $\gamma_{1}(x)$ of complex
horospheres, and we have the intermediate cycles $\gamma_{\delta}(x)$ for
$0<\delta<1$.

Sections from all these cycles for $0<\delta\leq 1$ have the unique real point
$u=x=(1,0,\dots,0)$. Indeed, if $u$ is a real point, then, taking the
imaginary parts of both parts of the equation, we have $u_{1}=1$, but on $S$
there is only the point $u=(1,0,\dots,0)$ with $u_{1}=1$. So, with the
exception of the point $x\in S$, the deformation of the real geodesic planes
on $S$, passing through $x$, in horospheres tangent to $S$ in $x$, lies in the
complex domain of ${\mathbb{C}}S$.

If we keep the same $\zeta^{\delta}$ and take
$p^{\delta}(\varepsilon)=p^{\delta}+{\rm i}\varepsilon$, $\varepsilon>0,$ then
the “shifted” cycles $\gamma_{\delta}(x,\varepsilon)$ will consist of sections
without real points. Correspondingly, $\gamma_{1}(x,\varepsilon)$ consists of
complex horospheres without real points, and we can consider the horospherical
Cauchy transform. On $\gamma_{1}(x)$ we define it by the regularization for
$\varepsilon\to 0$ (boundary values ${\mathcal{H}}f(x+{\rm i}\eta)$ on
$\partial\Xi_{+})$. We can now use the fundamental form and repeat all
constructions of the last section.

######  Theorem 5.1.

One has the horospherical inversion formula

$f(x)=\frac{n-1}{2(2\pi)^{n-1}}\int_{\gamma_{1}(x)}{\mathcal{L}}_{p}{\mathcal{H}}f(x+{\rm
i}\eta,p)|_{p=1}\big{[}x,\eta,{\rm d}\eta^{\\{n-2\\}}\big{]}.$

Finally, let us explain how to reproduce the classical version of the harmonic
analysis on the sphere in the language of spherical polynomials. The central
observation here is that the set $\Xi_{+}$, along with its boundary, are
invariant relative to the circle action

$\zeta\mapsto\exp({\rm i}\theta)\zeta,\qquad\zeta\in\partial\Xi_{+}.$

The composition with the horospherical transform gives the decomposition on
irreducible components and the inversion gives on the sphere $S$ the
decomposition on harmonic polynomials.

##  6 The hyperboloid $\boldsymbol{X_{2,n-2}}$

The case $p=2$ contains some important special subcases: for $q=2$ we have the
group ${\rm SL}(2;{\mathbb{R}})$. The imaginary hyperbolic plane ($p=1$,
$q=2$) serves as a model of the principal series of representations of this
group (all representations appear with multiplicity 1.) For our considerations
it is the simplest case where we need to consider both real and complex
horospheres. This forces us to combine the technology which we discussed for
the hyperbolic space and for the sphere [3].

Following our conceptual picture, we are interested in the set $\varTheta$ of
horospheres $E(\zeta,p)$ without real points on $X$, since for them the
horospherical Cauchy transform ${\mathcal{H}}(\zeta,p)$ is well defined. Here
$\zeta=\xi+{\rm i}\eta\in{\mathbb{C}}\Xi$ is nonzero and satisfies
$\square\zeta=0$. Using the homogeneity of ${\mathcal{H}}$, it is enough to
consider $p=0,1$. Of principal interest are the boundary horospheres from
$\partial\varTheta$: they have intersections with $X$ which disappear under
some small perturbations. The horospherical transform ${\mathcal{H}}$ for them
is defined by regularization (boundary values) from $\varTheta$. The set of
such horospheres is a dual object to $X$ and we use them to write the
inversion formula.

The first class of horospheres which lie in $\partial\varTheta$ is the class
$\varTheta_{R}$ of the real horospheres $E(\xi,p)$ for which $\square(\xi)=0$,
$\eta=0$, $p\in{\mathbb{R}}$. Their intersections with $X$ are paraboloids
which degenerate to the cone if $p=0$. These horospheres are the boundary for
$\varTheta$ since the horospheres $E(\xi,p+{\rm i}\varepsilon)$ have no real
points for any $\varepsilon\neq 0$.

For the next class of horospheres $\varTheta_{I}^{\pm}$, we suppose that

$\square(\xi)\neq 0,$

and this class has two connected components. There are a few degenerate
horospheres when $\square(\xi)=\square(\eta)=0$, but we do not need them for
our aims. We know that the condition $\square_{1,n-1}(\zeta)=0$ is equivalent
to

$\square(\xi)=\square(\eta),\qquad\langle\xi,\eta\rangle=0.$

With each point $x\in X$ we associate the set of those horospheres $E(\xi+{\rm
i}\eta,1)$ that intersect the hyperboloid in the unique point $x$:

$\langle x+{\rm i}\eta,x\rangle=1,\qquad\langle\eta,x\rangle=0.$

Such horospheres lie on the boundary $\partial\varTheta$, and to see this let
us consider various possibilities. Let $p>0$; then we can take $p=1$. Let

$\square(\xi)=\square(\eta)>0.$

Then, acting by the group ${\rm SO}(2,q)$, we can make
$\xi=(\lambda,0,\dots,0)$, $\lambda>0$, $\eta=(0,\pm\lambda,0,\dots,0)$. If
$x\in X$ then $x_{1}=1/\lambda$, $x_{2}=0$, and

$(x_{3})^{2}+\cdots+(x_{n})^{2}=-1+1/\lambda^{2}.$

It is impossible to have $\lambda>1$, but for $\lambda=1$ the point
$(1,0,\dots,0)$ will be the unique intersection point of the hyperboloid and
the horospheres. This exactly means that the horosphere $E(\zeta,1)$ is on the
boundary of $\varTheta$. Apparently, for $\lambda<1$ there is more than one
intersection point.

For such $\zeta$ and $p=0$ in the intersection it must be the case that
$x_{1}=x_{2}=0$, and this is impossible. So such horospheres are interior to
$\varTheta$.

If $\square(\xi)<0$ then the canonical form of such $\zeta$ is
$(0,0,\lambda,{\rm i}\lambda,0,\dots,0)$, and such horospheres have infinite
real intersections for all $p$. The case $\xi=0$, $\eta\neq 0$ can be
considered similarly.

The basic consequence of these computations is the following: The horospheres
$E(\zeta,p)$ have no real points if

$\square(\xi)=\square(\eta)>|p|^{2}>0;$

if $\square(\xi)=|p|^{2}>0$, then $x=\xi/p$ has a unique intersection point.
So passing through $x\in X$ are the horospheres $E(x+{\rm i}\eta,1)$ with

$\square(\eta)=1,\qquad\langle\eta,x\rangle=0.$

These horospheres are parameterized by the points of the $(n-2)$-dimensional,
two-sheeted hyperboloid $\\{\square_{1,n-2}(\eta)=1\\}$. Now we have enough
horospheres for the inversion of the horospherical Cauchy transform. This set
$\gamma_{1}(x)\subset\partial\varTheta$ has three connected components: one
component from the real horospheres $\gamma_{1}^{0}(x)$ and two components
from the complex horospheres $\gamma_{1}^{\pm}(x)$.

Our approach has the same structure as in the examples above. We start from
the geodesic hyperplane sections $L(\xi)$ by the hyperplanes
$\langle\xi,u\rangle=0$. We fix a point $x\in X$. It is sufficient to take
$x=(1,0,\dots,0)$. For these sections the inversion follows from the Radon
inversion formula by the projective equivalence. Let us take the cycle
$\gamma_{0}(x)$ of the geodesic sections passing through $x$. Then $\xi_{1}=0$
and we have sections

$\big{\langle}\zeta^{0},u\big{\rangle}=0,\qquad\zeta^{0}=(0,\lambda),\qquad\lambda\neq
0\in{\mathbb{R}}^{n-1}.$

For normalization we can take $\lambda$ from the unit sphere $S^{n-2}$. We
construct the deformation of the geodesic cycle $\gamma_{0}(x)$ to the
horospheric cycle $\gamma_{1}(x)$.

For $0\leq\delta\leq 1$ consider

$\zeta^{\delta}=\big{(}{\rm
i}\delta\sqrt{\square(\lambda)},\lambda\big{)},\qquad p^{\delta}={\rm
i}\delta\sqrt{\square(\lambda)}$

and the cycles $\gamma_{\delta}(x)$ of the hyperplane sections
$L\big{(}\zeta^{\delta},p^{\delta}\big{)}$ by the hyperplanes
$\big{\\{}\big{\langle}\zeta^{\delta},u\big{\rangle}=p^{\delta}\delta\big{\\}}$
that depend on $\lambda\in S^{n-2}$. For $\delta=0$ we have the geodesic cycle
$\gamma_{0}(x)$; for $\delta=1$ we have the horospherical cycle
$\gamma_{1}(x)$ that consists of the real horospheres for
$\square_{1,n-1}(\lambda)<0$ and the 2-component set of complex horospheres.
Let $\gamma_{1}^{0}(x)$, $\gamma^{\pm}_{1}(x)$ be these three connected
components of the horospherical cycle. Their joint boundary consists of
degenerated horospheres. Thus we have constructed the deformation of the
geodesic cycle in the horospheric cycle through the intermediate cycles
$\gamma^{\delta}(x)$, $0<\delta<1$ of hyperplane sections (not horospheres).

Correspondingly, in $\varTheta$ we have the two-component domain
$\varTheta^{\pm}$ of horospheres $E(\zeta,1)$ with

$\square(\xi)=\square(\eta)>1$

on whose boundaries lie $\gamma^{\pm}(x)$. The horospherical transform is
holomorphic in the domains $\varTheta^{\pm}$. Therefore the horospherical
transform has 3 components: ${\mathcal{H}}_{R}(\xi)$,
${\mathcal{H}}_{I}^{\pm}(\zeta)$. We can construct the inversion of the
horospherical transform on $\gamma_{1}(x)$ using the fundamental form. We will
discuss the details at another time.

The spherical Fourier transform also has 3 components corresponding to 3
components of the horospherical transform. The first one is connected with the
action of multiplicative real group ${\mathbb{R}}^{\times}$ on the set
$\varTheta_{R}$ of real horospheres

$\xi\mapsto\lambda\xi,$

and, as in the hyperbolic case, we take the composition of the horospherical
component ${\mathcal{H}}_{R}$ and the classical Mellin transform. It gives the
projection on the continuous principal series.

The domains $\varTheta^{\pm}_{I}$ are invariant relative to the complex
semigroup: $\zeta\mapsto\lambda\zeta$, $\lambda\in{\mathbb{C}}$,
$|\lambda|>1$. The decomposition of ${\mathcal{H}}^{\pm}$ in the Taylor series
in $\lambda$ gives projections on the holomorphic and antiholomorphic discrete
series of representations.

## References

  * [1] Gelfand I.M., Gindikin S.G., Graev M.I., Selected topics in integral geometry, Translations of Mathematical Monographs, Vol. 220, Amer. Math. Soc., Providence, RI, 2003.
  * [2] Gindikin S., Real integral geometry and complex analysis, in Integral Geometry, Radon Transforms and Complex Analysis (Venice, 1996), Lecture Notes in Math., Vol. 1684, Springer, Berlin, 1998, 70–98.
  * [3] Gindikin S., Integral geometry on ${\rm SL}(2;{\mathbb{R}})$, Math. Res. Lett. 7 (2000), 417–432.
  * [4] Gindikin S., Complex horospherical transform on real sphere, in Geometric Analysis of PDE and Several Complex Variables, Contemp. Math., Vol. 368, Amer. Math. Soc., Providence, RI, 2005, 227–232, arXiv:math.RT/0501023.
  * [5] Gindikin S., Harmonic analysis on symmetric Stein manifolds from the point of view of complex analysis, Jpn. J. Math. 1 (2006), 87–105.


# Characterization of some classes of graphs and their products as frame
graphs

F. Abdollahi  and  H. Najafi  Department of Mathematics, College of Sciences,
Shiraz University, Shiraz 7187919556, Iran<EMAIL_ADDRESS>(H. Najafi)
and<EMAIL_ADDRESS>(F. Abdollahi).

###### Abstract.

To each finite frame $\varphi$ in an inner product space $\mathcal{H}$ we
associate a simple graph $G(\varphi)$, called frame graph, with the vectors of
the frame as vertices and there is an edge between vertices $f$ and $g$
provided that $\langle f,g\rangle\neq 0$ [1]. In this paper the relation
between the order of $G(\varphi)$ and the dimension of $\mathcal{H}$ is
investigated for some well-known classes of graphs and their products.

###### Key words and phrases:

Frame Graph, Graph product, Tree, Corona product, Inner product space

###### 2010 Mathematics Subject Classification:

05C50; 42C15; 15A63

##  1\. Introduction

The study of frames, using the properties of graphs, is an exciting research
topic and hopefully will become mutually useful for both frame and graph
theory as well as in computer science. For example, in [26, 17, 4] the
relation between equiangular tight frames and graphs was observed. A one-to-
one correspondence between a subclass of equiangular tight frames and regular
two-graphs was offered in [17] and another one between real equiangular frames
of $n$ vectors and graphs of order $n$ was given in [29]. The authors of [27]
found some restrictions on the existence of real equiangular tight frames by
an equivalence between equiangular tight frames and strongly regular graphs
with certain parameters.

In [1] we defined a natural connection between frames and graphs. This
connection is made by the zero-nonzero pattern of the correlation between
different elements of the frame. More precisely, for a finite frame $\varphi$
in an inner product space $\mathcal{H}$ we associate a simple graph
$G(\varphi)$, termed the frame graph, with the elements of a frame as
vertices, two distinct vertices are adjacent if and only if the respective
vectors are non-orthogonal. A simple graph $G$ is said to be frame graph in
space $\mathcal{H}$ if there exists a frame $\varphi$ for $\mathcal{H}$ such
that $G(\varphi)=G$. In [1] we studied some basic properties of frame graphs
and identified some classes of tight frame graphs (a frame graph is a tight
frame graph if the associated frame is tight). Among other things it is shown
that complete graphs and the join of each graph with itself are tight frame
graphs, whereas non-trivial trees and cycles with at least than six vertices
are not.

This interesting definition and the corresponding observations have received
an extensive interest by many researchers, see [28, 8, 7, 12, 19] for example.
Investigating the relation between the dimension of $\mathcal{H}$ and the
graph-theoretic properties of $G$ is the main purpose of this paper. This
problem has a deep connection with a well known problem in graph theory,
namely minimum positive semidefinite rank.

The outline of the paper is as follows. In Section $2$, after fixing some
notation and definitions, we discuss the relation between the dimension of
$\mathcal{H}$ and the minimum positive semidefinite rank problem which
considers the minimum rank over all positive semidefinite Hermitian matrices
whose $ij$th entry (for $i\neq j$) is nonzero whenever $\\{i,j\\}$ is an edge
in $G$ and is zero otherwise. By this relation some well known classes of
graphs such as trees and their complements, cycles and their complements,
complete and complete bipartite graphs will be characterized as frame graphs.
In Section $3$, the relation between $dim(\mathcal{H})$ and the order of a
graph will be studied for the join of two graphs and also for the corona,
Cartesian and strong product of some well-known classes of graphs. As a result
we find the minimum positive semidefinite rank of some classes of graphs
which, as far as we know, are new results. The results are summarized in Table
1.

Result # | $G$ | Order | $mr_{+}^{\mathbb{C}}(G)$ | $mr_{+}^{\mathbb{R}}(G)$
---|---|---|---|---
[2], 3.3 | $P_{n}\boxtimes P_{m}$ | $nm$ | $(n-1)(m-1)$ | $(n-1)(m-1)$
3.7 | $T\Box K_{n}$ | $nm$ | $mn-n$ | $mn-n$
3.8 | $C_{3}\Box P_{n}$ | $3n$ | $3n-3$ | $3n-3$
3.10 | $K_{n}\Box K_{m}$ | $nm$ | $\leq n+m-1$ |  $n+m-2$ or $n+m-1$
3.13 | $T\circ T^{\prime}$ | $mm^{\prime}+m$ | $mm^{\prime}-1$ | $mm^{\prime}-1$
3.13 | $T\circ K_{n},n\geq 2$ | $mn+m$ | $2m-1$ | $2m-1$
3.13 | $K_{n}\circ T$ | $mn+n$ | $nm-n+1$ | $nm-n+1$
[2], 3.13 | $K_{n}\circ K_{m}$ | $mn+n$ | $n+1$ | $n+1$
3.13 | $C_{n}\circ T$ | $mn+n$ | $nm-2$ | $nm-2$
3.13 | $T\circ C_{n}$ | $mn+m$ | $m(n-1)-1$ | $m(n-1)-1$
[24], 3.13 | $C_{n}\circ K_{m}$ | $mn+n$ | $2n-2$ | $2n-2$
3.13 | $K_{m}\circ C_{n}$ | $mn+m$ | $m(n-2)+1$ | $m(n-2)+1$
3.13 | $C_{n}\circ C_{m}$ | $mn+n$ | $n(m-1)-2$ | $n(m-1)-2$
Table 1. Summary of minimum positive semidefinite rank results established in
this paper ($T$ and $T^{\prime}$ are trees with $|T|=m$ and
$|T^{\prime}|=m^{\prime}$).

##  2\. Definitions, Preliminaries and basic facts

The following definitions and facts are standard and can be found in any text
book about graph theory, see for example [10, 5, 30].

Recall that a graph $G=(V,E)$ consists of a set of vertices $V$ and a set of
edges $E$, where the elements of $E$ are two-element sets of vertices. The
order of a graph $G$, denoted by $|G|$, is the number of vertices. Distinct
vertices $f_{i}$ and $f_{j}$ is said to be adjacent if $\\{f_{i},f_{j}\\}$ is
an edge. The degree of each vertex is the number of vertices adjacent to it
and the minimum degree among all vertices is denoted by $\delta(G)$. Note that
our graphs are simple, i.e., multiple edges and loops do not appear in them
and all the edges are undirected. A path is a simple graph whose vertices can
be ordered so that two vertices are adjacent if and only if they are
consecutive in the list. A cycle is a graph with an equal number of vertices
and edges whose vertices can be placed around a circle so that two vertices
are adjacent if and only if they appear consecutively along the circle. A
cycle of order $n$ is denoted by $C_{n}$.

A graph $G$ is connected if each pair of vertices in $G$ belongs to a path in
$G$. A connected component of $G$ is a maximal connected subgraph of $G$. A
connected graph without a cycle is called a tree.
An independent set in a graph is a set of pairwise nonadjacent vertices. The
independence number of a graph $G$, $\alpha(G)$, is the maximal size of an
independent set of vertices. A graph $G$ is complete or a clique if
$\alpha(G)=1$. The complete graph of order $n$ is denoted by $K_{n}$. The
graph $G=(V,E)$ is called bipartite if $V$ is the union of two disjoint
(possibly empty) independent sets called partite sets of $G$. If every vertex
of the first set with $n$ elements is adjacent to every vertex of the second
set with $m$ elements, then it is called a complete bipartite graph and
denoted by $K_{n,m}$
By the complement $\overline{G}$ of a graph $G$, we mean the graph on the same
vertex set where two vertices are adjacent if and only if they are not
adjacent in $G$.
Given a graph $G=(V,E)$, the graph $H=(V^{\prime},E^{\prime})$ with
$V^{\prime}\subseteq V$ and $E^{\prime}\subseteq E$ is called a subgraph of
$G$. An induced subgraph $H$ is a subgraph in which two vertices are adjacent
if and only if they are adjacent in $G$.

Suppose that $G$ is labeled and that $G_{1},...,G_{k}$ are (labeled) subgraphs
of $G$, that is, each $G_{i},i=1,...,k$ is the result of deleting some edges
and/or vertices from $G$. We say that $G_{1},...,G_{k}$ cover $G$ if each edge
(vertex) of G is an edge (vertex) of at least one $G_{i},1\leq i\leq k$ or
$G=\bigcup_{i=1}^{k}G_{i}$. The cover $G_{1},...,G_{k}$ of $G$ is called a
clique cover of $G$ if each of $G_{1},...,G_{k}$ is a clique of $G$. The
clique cover number of G, $cc(G)$, is the minimum value of $k$ for which there
is a clique cover $G_{1},...,G_{k}$ of $G$.

A graph is said to be chordal if it has no induced cycles $C_{n}$ with $n\geq
4$. As examples trees and complete graphs are chordal.

For an $n\times n$ Hermitian matrix $A$, the graph of $A$, denoted by
$\mathcal{G}(A)$, is the graph with vertices $\\{1,2,\ldots,n\\}$ such that
two distinct vertices $i$ and $j$ are adjacent if and only if the $ij$-th
entry of $A$ is non-zero. The set of all $n\times n$ complex Hermitian
positive semidefinite matrices will be denoted by $\mathcal{H}_{n}^{+}$ and
its subset consisting of all real matrices denoted by $S_{n}^{+}$.

The real minimum positive semidefinite rank of $G$, ${\it
mr}_{+}^{\mathbb{R}}(G)$, and complex Hermitian minimum positive semidefinite
rank, ${\it mr}_{+}^{\mathbb{C}}(G)$ are defined by

$\textrm{mr}_{+}^{\mathbb{R}}(G)=\min\\{rank(B):B\in S_{n}^{+}\ and\
\mathcal{G}(B)=G\\},$

and

$\textrm{mr}_{+}^{\mathbb{C}}(G)=\min\\{rank(B):B\in\mathcal{H}_{n}^{+}\ and\
\mathcal{G}(B)=G\\}.$

If $mr_{+}^{\mathbb{R}}(G)=mr_{+}^{\mathbb{C}}(G)$ , then we denote the common
value $mr_{+}^{\mathbb{R}}(G)=mr_{+}^{\mathbb{C}}(G)$ by $mr_{+}(G)$.

Clearly ${\it mr}_{+}^{\mathbb{C}}(G)\leq{\it mr}_{+}^{\mathbb{R}}(G)$. A
graph on $16$ vertices for which these parameters are not identical was
presented in [3]. For a graph $G$ of order $n$, it is well known and
straightforward that ${\it mr}_{+}^{\mathbb{R}}(G)\leq n-1$. Other fundamental
facts, that will be of interest to us, are that ${\it mr}_{+}(G)=n-1$ if and
only if $G$ is a tree and ${\it mr}_{+}(C_{n})=n-2$[18]. For more details on
minimum positive semidefinite rank we refer the reader to [18, 6, 11, 2, 15,
3].

A finite frame for a finite dimensional Hilbert space $\mathcal{H}$ (or inner
product space) is a finite sequence $\\{f_{i}\\}_{i=1}^{n}$ in $\mathcal{H}$
such that there exist constants $0<A\leq B<\infty$ with the property that

$A\parallel f\parallel^{2}\leq\sum_{i=1}^{n}|\langle f,f_{i}\rangle|^{2}\leq
B\parallel f\parallel^{2}$

holds for all $f\in\mathcal{H}$ [9].

Given a frame $\varphi=\\{f_{i}\\}_{i=1}^{m}$ in $\mathbb{R}^{n}$ or
$\mathbb{C}^{n}$. Let $B$ be the $n\times m$ matrix whose $j$th column is
$f_{j}$. Then $B^{T}B$ ( $B^{*}B$) is a positive semidefinite martix called
the Gramian matrix of $\varphi$ and denoted by $Gram(\varphi)$($B^{*}$ is the
conjugate transpose of B). The rank of $B$, $n$, is equal to the rank of
$Gram(\varphi)$ [16, Theorem 7.2.10].

Let $\varphi$ be a finite frame for the inner product space $\mathcal{H}$. We
associate a simple graph $G({\varphi})$, called a frame graph, whose vertices
are the elements of $\varphi$ and two distinct vertices $a$ and $b$ are
adjacent if and only if $\langle a,b\rangle\neq 0$. A simple graph $G$ is
called a frame graph in the space $\mathcal{H}$ if there exists a frame
$\varphi$ for $\mathcal{H}$ such that $G(\varphi)=G$. In this paper all graphs
are non-trivial and connected, and so the associated frames do not include
zero vectors.

For a given graph $G$, we interested to find the inner product $\mathcal{H}$
so that there exists a frame $\varphi$ for $\mathcal{H}$ such that
$G({\varphi})=G$. At first, we show that this problem is deeply connected with
the well known minimum positive semidefinite rank problem. We will find the
minimum positive semidefinite rank for join of graphs and Cartesian, corona
and strong products of some well known classes of graphs and use them to
characterize these products as frame graphs.

######  Lemma 2.1.

For a graph $G$, $mr_{+}^{\mathbb{R}}(G)=k$ (respectively,
$mr_{+}^{\mathbb{C}}(G)=k$) if and only if $k$ is the minimum number such that
$G$ is a frame graph in a real (respectively, complex) inner product space of
dimension $k$.

###### Proof.

Let $A$ be a positive semidefinite real (complex) $n\times n$ matrix of rank
$k$ such that $\mathcal{G}(A)=G$. The matrix $A$ has a decomposition of the
form $A=B^{T}B$. The columns of $B$ constitute a frame $\varphi$ in a real
(complex)$k$-dimensional space such that $G(\varphi)=G$. On the other hand,
the Gramian matrix of each frame $\varphi$ in a real (complex) space
$\mathcal{H}$ describes $G(\varphi)$, or
$\mathcal{G}(Gram(\varphi))=G(\varphi)$, and its rank is $dim(\mathcal{H})$.
Hence the lowest dimension of a real (complex) space in which a frame
associated to the graph $G$ is exactly the real (complex Hermitian) minimum
positive semidefinite rank. ∎

######  Lemma 2.2.

Let $G$ be a frame graph in $\mathbb{R}^{n}$ (respectively, $\mathbb{C}^{n})$
with $m>n$ vertices. Then $G$ is a frame graph in $\mathbb{R}^{n+1}$
(respectively, $\mathbb{C}^{n+1})$.

###### Proof.

Let $\varphi=\\{f_{1},f_{2},\ldots,f_{m}\\}$ be a frame for $\mathbb{R}^{n}$
(respectively, $\mathbb{C}^{n})$ such that $G(\varphi)=G$. Since $\varphi$ is
a frame, a subset of $\varphi$ with $n$ elements spans $\mathbb{R}^{n}$
(respectively, $\mathbb{C}^{n}$). Then, without loss of generality, we may
assume that $\\{f_{1},f_{2},\ldots,f_{n}\\}$ spans $\mathbb{R}^{n}$
(respectively, $\mathbb{C}^{n}$). Clearly

$\varphi^{\prime}:=\\{(f_{1},0),(f_{2},0),\ldots,(f_{n},0),(f_{n+1},1),(f_{n+2},0),\ldots,(f_{m},0)\\},$

spans $\mathbb{R}^{n+1}$ (respectively, $\mathbb{C}^{n+1})$ and
$G(\varphi)=G(\varphi^{\prime})$. Hence $G$ is a frame graph in
$\mathbb{R}^{n+1}$ (respectively, $\mathbb{C}^{n+1})$. ∎

For a given graph $G$ on $n$ vertices, the above lemmas conclude that
$mr_{+}^{\mathbb{R}}(G)=k$ (respectively, $mr_{+}^{\mathbb{C}}(G)=k$) if and
only if $G$ is just a frame graph in the real (respectively, complex) inner
product spaces of dimension $k,k+1,...,n$. For example, $G$ is just a frame
graph in spaces of dimension $n-1$ and $n$ if and only if $G$ is a tree.
Another example is a cycle of order $n$, $C_{n}$, which is just a frame graph
in the spaces of dimension $n-2,n-1$ and $n$. Trees and cycles, as two well
known classes of graphs, are not frame graph in the spaces of lower
dimensions, whereas complete graphs are frame graphs in all possible spaces
because $mr_{+}(K_{n})=1$. Clearly complete graphs are the only connected
graphs which are frame graphs in all possible spaces. Let $G$ be a non-
complete connected graph and $\varphi$ be a frame for an inner product space
$\mathcal{H}$ such that $G(\varphi)=G$. Then the dimension of $\mathcal{H}$ is
at least two. The following example introduces two classes of connected graphs
which achieve this bound.

######  Example 2.1.

Let $G$ be a simple graph obtained from $K_{n}$ $(n\geq 3)$ by deleting an
edge and let $\\{e_{1},e_{2}\\}$ be the standard orthogonal basis of
$\mathbb{C}^{2}$ ($\mathbb{R}^{2}$). Then the frame
$\varphi=\\{e_{1}+e_{2},e_{1}-e_{2}\\}\bigcup\\{e_{1}\\}_{i=1}^{n-2}$ makes
$G$ a frame graph in $\mathbb{C}^{2}$ ($\mathbb{R}^{2}$), i.e, $mr_{+}(G)=2$.
Another graph is $H_{n}$, the ($n-2$)-regular graph on $n$ vertices. It is
known that $mr_{+}(H_{n})=2$ (see Proposition 5.2 of [6]). Both $G$ and
$H_{n}$ are frame graphs in the inner product spaces of dimension
$2,3,...,n-1$ and $n$.

Despite trees and complete graphs which are frame graphs in a minimum and
maximum number of spaces, respectively, complete bipartite graphs with the
parts of the same size are frame graphs in a medium number of possible spaces.
Indeed, since the independence number of each complete bipartite graph
$K_{m,n}(m\geq n)$ is $m$ and it has no isolated vertex, it cannot be a frame
graph in an inner product space of dimension less than $m$. Let
$\\{e_{i}\\}_{i=1}^{m}$ be the standard orthogonal basis of $\mathbb{R}^{m}$.
The set
$\\{e_{i}\\}_{i=1}^{m}\bigcup\\{e_{1}+e_{2}+\ldots+e_{i-1}+\frac{2-n}{2}e_{i}+e_{i+1}+\ldots+e_{m}\\}_{i=1}^{n}$
$(n\neq 2)$ is a frame for $\mathbb{R}^{m}$ and its frame graph is $K_{n,m}$.
Now Lemma 2.2 guaranties that $K_{m,n}$ is just a frame graph in the spaces of
dimension $m,m+1,...,n+m-1,n+m$. Proposition 2.2 of [15] shows that this
result holds for a larger class of bipartite graphs. We include it here:

######  Proposition 2.3.

Let $G$ be a bipartite graph which contains $K_{n,n}$ as an induced subgraph
and its partite sets $U$ and $V$ are of size $m$ and $n$ where $m\geq n$. Then
$G$ is just a frame graph in the inner product spaces of dimension
$m,m+1,...,m+n-1,m+n$.

##  3\. Product of graphs and frame graph

As we saw in the previous section, to characterize a graph as frame graph we
just need to find its minimum positive semidefinite rank. Some well known
classes of graphs such as trees and their complements, cycles and their
complements, complete and complete bipartite graphs have known minimum
positive semidefinite rank (see [20]), so the dimension of all the spaces
which they are frame graphs in them can be obtained by Lemma 2.2. In this
section, we try to find the minimum positive semidefinite rank of the product
of some prominent classes of graphs and use them to characterize these graphs
as frame graphs. The following definition and proposition, which can be found
in [15], provides a lower bound for $mr_{+}(G)$ and will be useful later in
this work.

Let $G=(V,E)$ be a connected graph and $S=\\{v_{1},...,v_{m}\\}$ be an ordered
set of vertices of $G$. Denote by $G_{k}$ the subgraph induced by
$v_{1},v_{2},...,v_{k}$ for all $k=1,2,...,m$. Let $H_{k}=(V_{k},E_{k})$ be
the connected component of $G_{k}$ such that $v_{k}\in V_{k}$. If for each
$k$, there exists $w_{k}\in V$ such that $w_{k}\neq v_{l}$ for $l\leq k$,
$\\{v_{k},w_{k}\\}\in E$ and $\\{w_{k},v_{l}\\}\notin E$ for all $v_{l}\in
V_{k}$ with $l\neq k$, then $S$ is called a vertex set of ordered subgraphs
(or $OS$-vertex set). The OS-number of a graph $G$, denoted by $OS(G)$, is the
maximum cardinality among all $OS$-vertex sets of $G$. For example $OS(T)=m-1$
where $T$ is a tree on $m$ vertices (see [15, Proposition 3.9]) and, clearly,
$OS(K_{n})=1$. Note that the $OS$-number is not defined for a single vertex,
$K_{1}$, and so, in this section, we assume that all graphs have more than one
vertex.

######  Proposition 3.1.

[15, Proposition 3.3 ] and [11, Observation 3.14.]. Let $G$ be a connected
graph. Then $OS(G)\leq mr_{+}^{\mathbb{C}}(G)\leq mr_{+}^{\mathbb{R}}(G)\leq
cc(G)$.

The vertex connectivity $\kappa(G)$ of a connected graph $G=(V,E)$ is the
minimum size of $S\subseteq V$ such that $G-S$ is disconnected or a single
vertex. The following result provides an upper bound for the real minimum
positive semidefinite rank.

######  Proposition 3.2.

[21, 22]. For each graph $G$ on $n$ vertices, $mr_{+}^{\mathbb{R}}(G)\leq
n-\kappa(G).$

###  3.1. Strong product

The strong product of two graphs $G_{1}=(V_{1},E_{1})$ and
$G_{2}=(V_{2},E_{2})$, denoted by $G_{1}\boxtimes G_{2}$, is the graph with
the vertex set $V_{1}\times V_{2}$ such that $(u,v)$ is adjacent to
$(u^{\prime},v^{\prime})$ if and only if (1) $u=u^{\prime}$ and
$\\{v,v^{\prime}\\}\in E_{2}$ or (2) $v=v^{\prime}$ and $\\{u,u^{\prime}\\}\in
E_{1}$ or (3) $\\{u,u^{\prime}\\}\in E_{1}$ and $\\{v,v^{\prime}\\}\in E_{2}$.

######  Theorem 3.3.

Let $G$ be the strong product of $P_{n}$ and $P_{m}$, i.e., $G=P_{n}\boxtimes
P_{n}$. Then $G$ is just a frame graph in the inner product spaces of
dimension $(n-1)(m-1),(n-1)(m-1)+1,...,mn-1,mn$.

###### Proof.

If we prove $mr_{+}(G)=(n-1)(m-1)$, then the ”lifting” argument of Lemma 2.2
completes the proof. $G$ has a clique cover of $(n-1)(m-1)$ copies of $K_{4}$,
so, by Proposition 3.1, $mr_{+}^{\mathbb{R}}(G)\leq(n-1)(m-1)$. Let
$\\{s_{1},s_{2},...,s_{n}\\}$ and $\\{t_{1},t_{2},...,t_{m}\\}$ be the vertex
sets of $P_{n}$ and $P_{m}$, respectively. The ordered set
$\bigcup_{i=1}^{n-1}\bigcup_{j=1}^{m-1}\\{v_{i,j}\\}$, where
$v_{i,j}=(s_{i},t_{j})$, with $w_{i,j}=(s_{i+1},t_{j+1})$ is an $OS$-vertex
set of length $(n-1)(m-1)$. Therefore $(n-1)(m-1)\leq OS(G)$. Now Proposition
3.1 implies $(n-1)(m-1)\leq mr_{+}^{\mathbb{C}}(G)$. ∎

###  3.2. Joins of graphs

The join $G_{1}\vee G_{2}$ of the graphs $G_{1}=(V_{1},E_{1})$ and
$G_{2}=(V_{2},E_{2})$ with disjoint vertex and edge sets is the graph with
vertex set $V_{1}\bigcup V_{2}$ and edge set $E_{1}\bigcup E_{2}$ together
with all the edges joining $V_{1}$ and $V_{2}$.

Suppose $G$ is decomposable into two graphs, $G_{1}=(V_{1},E_{1})$ and
$G_{2}=(V_{2},E_{2})$, sharing only one vertex $v$ such that if $u\in V_{1}$
and $w\in V_{2}$, then $\\{u,w\\}\in E$ only if $u=v$ or $w=v$. Then $G_{1}$
and $G_{2}$ are joined at vertex $v$ and $G$ is denoted by $G=G_{1}.G_{2}$.

Let $G$ and $H$ be two connected graphs on two or more vertices. Proposition
$2.4$ of [15] states that $mr_{+}^{\mathbb{C}}(G\vee
H)=max\\{mr_{+}^{\mathbb{C}}(G),mr_{+}^{\mathbb{C}}(H)\\}$ and by Theorem
$3.4$ of [6] we have
$mr_{+}^{\mathbb{C}}(G.H)=mr_{+}^{\mathbb{C}}(G)+mr_{+}^{\mathbb{C}}(H)$.
These, combined with Lemma 2.2, give the following theorem.

######  Theorem 3.4.

Let the graph $G$ be just a frame graph in spaces of dimension
$n^{\prime},n^{\prime}+1,..,n-1,n$ and $H$ be just a frame graph in the spaces
of dimension $m^{\prime},m^{\prime}+1,..,m-1,m$ where $n^{\prime}\geq
m^{\prime}$. The followings are hold:

  1. (i)

$G\vee H$ is just a frame graph in the spaces of dimension
$n^{\prime},n^{\prime}+1,...,m+n-1$ and $m+n$.

  2. (ii)

$G.H$ is just a frame graph in the spaces of dimension
$n^{\prime}+m^{\prime},n^{\prime}+m^{\prime}+1,...,m+n-2$ and $m+n-1$.

###  3.3. Cartesian product

The Cartesian product of two graphs $G_{1}=(V_{1},E_{1})$ and
$G_{2}=(V_{2},E_{2})$, denoted by $G_{1}\Box G_{2}$, is the graph with vertex
set $V_{1}\times V_{2}$ such that $(u,v)$ is adjacent to
$(u^{\prime},v^{\prime})$ if and only if (1)$u=u^{\prime}$ and
$\\{v,v^{\prime}\\}\in E_{2}$ or (2) $v=v^{\prime}$ and $\\{u,u^{\prime}\\}\in
E_{1}$ . The set of vertices associated with (the same) $OS$-vertex set in
each copy of $G$ or $H$ is an $OS$-vertex set for $G\Box H$. Then we have the
following lemma.

######  Lemma 3.5.

Let $G$ and $H$ be the graphs of order $n$ and $m$, respectively. Then

$\max\\{nOS(H),mOS(G)\\}\leq OS(G\Box H).$

The connectivity of the graph $G\Box H$ can be determined by knowing the
minimum degree and the connectivity of the components $G$ and $H$.

######  Proposition 3.6.

[25] Let $G$ and $H$ be the graphs on $n$ and $m$ vertices, respectively. Then
$\kappa(G\Box H)=\min\\{n\kappa(H),m\kappa(G),\delta(G)+\delta(H)\\}.$

######  Theorem 3.7.

The graph $G=T\square K_{m}$, where $T$ is a tree on $n$ vertices, is just a
frame graph in the inner product spaces of dimension
$mn-m,mn-m+1,...,mn-1,mn$.

###### Proof.

It is sufficient to show that $mr_{+}(G)=mn-m$ and use the ”lifting argument”
of Lemma 2.2.

By Lema 3.5, $mn-m\leq OS(G)$, so Proposition 3.1 implies $mn-m\leq
mr_{+}^{\mathbb{C}}(G)$. On the other hand, using Propositions 3.2 and 3.6, we
have $mr_{+}^{\mathbb{R}}(G)\leq mn-m$. Using $mr_{+}(G)\leq
mr_{+}^{\mathbb{R}}(G)$ implies that
$mr_{+}^{\mathbb{C}}(G)=mr_{+}^{\mathbb{R}}(G)=mn-m$ which completes the
proof. ∎

It is a conjecture that $mr_{+}(C_{m}\Box P_{n})=mn-\min\\{m,2n\\}$ (See
[23]). This conjecture is valid for the case $n=2$([23]). The above theorem
shows that it also holds for the case $m=3$.

######  Corollary 3.8.

$mr_{+}(C_{3}\Box P_{n})=3n-3$.

At the end of this subsection we consider the graph $K_{n}\Box K_{m}$.
Unfortunately the minimum positive semidefinite rank of this graph is not
known until now, and hence we cannot characterize it as frame graph. Another
conjecture in [23] states that $mr_{+}^{\mathbb{R}}(K_{n}\Box K_{m})=n+m-2$.
In what follows we show that $mr_{+}^{\mathbb{R}}(K_{n}\Box K_{m})$ is one of
the numbers $n+m-2$ or $n+m-1$, therefore $K_{n}\Box K_{m}$ is a frame graph
in the real spaces of dimension $n+m-1,m+n,...,nm$ and the dimension $n+m-2$
remains unsolved.

If $A$ is an $n\times n$ matrix and $B$ is an $m\times m$ matrix, then
$A\otimes B$, the Kronecker product, is the $n\times n$ block matrix whose
$(i,j)$th block is the $m\times m$ matrix $a_{ij}B$. Let $G$ and $H$ be the
graphs on $n$ and $m$ vertices, respectively, and let $A$ and $B$ be two
matrices such that $\mathcal{G}(A)=G$ and $\mathcal{G}(B)=H$. Then
$\mathcal{G}(A\otimes I_{m}+I_{n}\otimes B)=G\Box H$ (see [14]). The matrix
$A\otimes I_{m}+I_{n}\otimes B$ known as Kronecker sum and denoted by $A\oplus
B$. If $\lambda$ is an eigenvalue of $A$ and $\mu$ is an eigenvalue of $B$,
then $\lambda+\mu$ is an eigenvalue of $A\oplus B$ and any eigenvalue of
$A\oplus B$ arises as such a sum of eigenvalues of $A$ and $B$ [14]. We use
these facts to proof the next lemma.

######  Lemma 3.9.

For the graphs $G$ and $H$ on $n$ and $m$ vertices, respectively,

$mr_{+}^{\mathbb{R}}(G\Box H)\leq
mmr_{+}^{\mathbb{R}}(G)+nmr_{+}^{\mathbb{R}}(H)-mr_{+}^{\mathbb{R}}(G)mr_{+}^{\mathbb{R}}(H).$

###### Proof.

Let $A$ and $B$ be two matrices in $S_{n}^{+}$ and $S_{m}^{+}$, respectively,
such that $\mathcal{G}(A)=G$, $\mathcal{G}(B)=H$,
$rank(A)=mr_{+}^{\mathbb{R}}(G)$, and $rank(B)=mr_{+}^{\mathbb{R}}(H)$. Then
$A$ has $n-mr_{+}^{\mathbb{R}}(G)$ zero eigenvalues, $B$ has
$m-mr_{+}^{\mathbb{R}}(H)$ zero eigenvalues and all the other eigenvalues of
$A$ and $B$ are positive and non zero. Since the eigenvalues of $A\oplus B$
are the sum of the eigenvalues of $A$ and $B$, $A\oplus B$ has exactly
$mmr_{+}^{\mathbb{R}}(G)+nmr_{+}^{\mathbb{R}}(H)-mr_{+}^{\mathbb{R}}(G)mr_{+}^{\mathbb{R}}(H)$
positive non zero eigenvalues, and so $rank(A\oplus
B)=mmr_{+}^{\mathbb{R}}(G)+nmr_{+}^{\mathbb{R}}(H)-mr_{+}^{\mathbb{R}}(G)mr_{+}^{\mathbb{R}}(H)$.
The matrix $A\oplus B$ belongs to $S^{+}_{nm}$ and describes $G\Box H$, i.e,
$\mathcal{G}(A\oplus B)=G\Box H$, so $mr_{+}^{\mathbb{R}}(G\Box H)\leq
rank(A\oplus
B)=mmr_{+}^{\mathbb{R}}(G)+nmr_{+}^{\mathbb{R}}(H)-mr_{+}^{\mathbb{R}}(G)mr_{+}^{\mathbb{R}}(H).$
∎

The minimum rank of a graph $G$ (over $\mathbb{R}$) is defined to be

$\textrm{mr}(G)=\min\\{rank(A):A\in S_{n}\ and\ \mathcal{G}(A)=G\\},$

where $S_{n}$ is the set of symmetric matrices over $\mathbb{R}$. Clearly

$mr(G)\leq mr_{+}^{\mathbb{R}}(G).$

######  Theorem 3.10.

$mr_{+}^{\mathbb{R}}(K_{n}\Box K_{m})$ is either $n+m-2$ or $n+m-1$.

###### Proof.

It is known that $mr(K_{n}\Box K_{m})=m+n-2$ (see [2, Corollary 3.11]). Since
$mr(K_{n}\Box K_{m})\leq mr_{+}^{\mathbb{R}}(K_{n}\Box K_{m})$, $n+m-2\leq
mr_{+}^{\mathbb{R}}(G)$. On the other hand, by Lemma 3.9,
$mr_{+}^{\mathbb{R}}(K_{n}\Box K_{m})$ cannot be more than $n+m-1$. ∎

###  3.4. Corona product

The corona product of $G_{1}=(V_{1},E_{1})$ with $G_{2}=(V_{2},E_{2})$,
denoted by $G_{1}\circ G_{2}$, is the graph of order $|V_{1}||V_{2}|+|V_{1}|$
obtained by taking one copy of $G_{1}$ and $|V_{1}|$ copies of $G_{2}$, and
joining all the vertices in the $i$th copy of $G_{2}$ to the $i$th vertex of
$G_{1}$ [13].
The following proposition helps us to provide a short proof for the next
theorem.

######  Proposition 3.11.

[11, Observation 3.14 ] Let $G$ be a graph and $G_{1},G_{2},...,G_{n}$ be a
cover of (labeled)subgraphs of it, i.e., $G=\bigcup_{i=1}^{n}G_{i}$. Then
$mr_{+}^{\mathbb{R}}(G)\leq\sum_{i=1}^{n}mr_{+}^{\mathbb{R}}(G_{i})$.

######  Theorem 3.12.

Let $G$ be a connected graph of order $n$ with $OS(G)=mr_{+}(G)$ and $H$ be a
connected graph with $OS(H)=mr_{+}(H)$. Then $mr_{+}(G\circ
H)=n(mr_{+}(H))+mr_{+}(G)$.

###### Proof.

Let $\\{v_{1},v_{2},...,v_{n}\\}$ be the vertex set of $G$. $G\circ
H=(\bigcup_{i=1}^{n}H\vee v_{i})\bigcup G$. Therefore, by Proposition 3.11,

$mr_{+}^{\mathbb{R}}(G\circ H)\leq(\sum_{i=1}^{n}mr_{+}^{\mathbb{R}}(H\vee
v_{i}))+mr_{+}^{\mathbb{R}}(G)=n(mr_{+}(H))+mr_{+}(G).$

On the other hand, the union of $n$ distinct $OS$-vertex sets of the copies of
$H$ along with the $OS$-vertex set of a copy of $G$ in $G\circ H$ makes an
$OS$-vertex set of length $nOS(H)+OS(G)$ for $G\circ H$, and so
$nOS(H)+OS(G)\leq OS(G\circ H)$. Again by using Proposition 3.1, we have
$n(mr_{+}(H))+mr_{+}(G)\leq mr_{+}^{\mathbb{C}}(G\circ H)$. ∎

It is easy to check that $OS(C_{t})=mr_{+}(C_{t})=t-2$ and
$OS(K_{n})=mr_{+}(K_{n})=1$ and it is known that if $G$ is a connected chordal
graph, then $OS(G)=mr_{+}^{\mathbb{C}}(G)=cc(G)$ (see [15, Corollary 3.8]). If
$T$ is a tree of order $m$, then it is chordal and
$OS(T)=mr_{+}(T)=cc(T)=m-1$. Now the following corollary is a direct
consequence of Theorem 3.12.

######  Corollary 3.13.

Let $T$ and $T^{\prime}$ be trees of order $m\geq 2$ and $m^{\prime}\geq 2$,
respectively. The followings hold.

  1. (1)

$mr_{+}(T\circ T^{\prime})=mm^{\prime}-1$.

  2. (2)

$mr_{+}(T\circ K_{n})=2m-1(n\geq 2)$.

  3. (3)

$mr_{+}(K_{n}\circ T)=nm-n+1$.

  4. (4)

$mr_{+}(K_{n}\circ K_{m})=n+1$.

  5. (5)

$mr_{+}(C_{n}\circ T)=nm-2$.

  6. (6)

$mr_{+}(T\circ C_{n})=m(n-1)-1$.

  7. (7)

$mr_{+}(C_{n}\circ K_{m})=2n-2$.

  8. (8)

$mr_{+}(K_{m}\circ C_{n})=m(n-2)+1.$

  9. (9)

$mr_{+}(C_{n}\circ C_{m})=n(m-1)-2.$

As far as we know all of the results of Corollary 3.13 are new with the
exception of $4$ and $7$ which was established earlier in [2] and [24].

Note that $mr_{+}(H_{n})=OS(H_{n})=2$. Therefore the minimum positive
semidefinite rank of the corona product of $H_{n}$ with trees, cycles and
complete graphs can be calculated easily.

The following theorem is an immediate consequence of Theorem 3.12, Lemma 2.1
and Lemma 2.2.

######  Theorem 3.14.

Let $G$ and $H$ be connected graphs of order $n$ and $m$, respectively, which
are either chordal or cycle graph. If $G$ is just a frame graph in the spaces
of dimension $n^{\prime},n^{\prime}+1,...,n$ and $H$ is just a frame graph in
the spaces of dimension $m^{\prime},m^{\prime}+1,...,m$, then $G\circ H$ is
just a frame graph in the spaces of dimension
$nm^{\prime}+n^{\prime},nm^{\prime}+n^{\prime}+1,...,nm+n-1,nm+n$.

## References

  * [1] F. Abdollahi and H. Najafi, _Frame Graph_ , Linear and Multilinear Algebra, 66 (2018), 1229–1243.
  * [2] AIM Minimum Rank-Special Graphs Work Group, _Zero forcing sets and the minimum rank of graphs_ , Linear Algebras and its Applications, 428 (2008), 1628–1648.
  * [3] F. Barioli, W. Barrett, S. M. Fallat, H. T. Hall, L. Hogben, B. Shader, P. van den Driessche and H. van der Holst, _Zero forcing parameters and minimum rank problems_ , Linear Algebra and its Applications, 433 (2010), 401–411.
  * [4] B. G. Bodman and V. I. Paulsen, _Frames, graphs and erasures_ , Linear Algebra and its Applications, 404 (2005), 118–146.
  * [5] B. Bollabas, _Graph Theory, An Introductory Course_ , Springer-Verlag, New York, 1979.
  * [6] M. Booth , P. Hackney, B. Harris, C. R. Johnson, M. Lay, T. D. Lenker, L. H. Mitchell, S. K. Narayan, Amanda Pascoe and B. D. Sutton, _On the minimum semidefinite rank of simple graphs_ , Linear and Multilinear Algebra, 59 (2011), 483–506.
  * [7] T. Y. Chien and S. Waldron, _A characterisation of projective unitary equivalence of finite frames and applications_ , SIAM J. Discrete Mathematics, 30, (2016), 976–994.
  * [8] T. Y. Chien, _Equiangular lines, projective symmetries and nice error frames_ , PhD Thesis, University of Auckland, 2015.
  * [9] O. Christensen, _An introduction to frame and Riesz bases_ , Birkhauser, Boston, 2003.
  * [10] R. Diestel, _Graph Theory_ , Springer-Verlag, New York, 1997.
  * [11] S.M. Fallat and L. Hogben, _The minimum rank of symmetric matrices described by a graph: A survey_ , Linear Algebra and Its Applications, 426, (2007), 558–582.
  * [12] V. Furst and H. Grotts, _Tight Frame Graphs Arising as Line Graphs_ , The pump journal of undergraduate research, 4 (2021), 1–19.
  * [13] R. Frucht and F. Harary, _On the coronas of two graphs_ , Aequationes Math., 4 (1970), 322–325.
  * [14] C. Godsil and G. Royle, _Algebraic Graph Theory_ , Springer-Verlag, New York, 2001.
  * [15] P. Hackney, B. Harris, M. Lay, S. K. Narayan , L. H. Mitchell and A. Pascoe , _Linearly independent vertices and minimum semidefinite rank_ , Linear Algebra and its Applications, 431 (2009), 1105–1115.
  * [16] R. A. Horn and C. R. Johnson _Matrix Analysis_ , Cambridge University Press, Cambridge, 1990, corrected reprint of the 1985 original.
  * [17] R. B. Holmes and V. I Paulsen, _Optimal frames for erasures_ , Linear Algebra and its Applications, 377 (2004), 31–51.
  * [18] H. van der Holst, _Graphs whose positive semi-definite matrices have nullity at most two_ , Linear Algebra and its Applications, 375 (2003), 1–11.
  * [19] J. W. Iverson and D. G. Mixon, _Doubly transitive lines II: Almost simple symmetries_ , (2019), arXiv:1905.06859v1.
  * [20] X. Li, M. Nathanson and R. Phillips, _Minimum vector Rank and Complement Critical Graphs_ , Electronic Journal of Linear Algebra, 27 (2014), 100–123.
  * [21] L. Lov$\acute{a}$sz, M. Saks and A. Schrijver, _Orthogonal representations and connectivity of graphs_ , Linear Algebra and its Applications, 114/115 (1989), 439–454.
  * [22] L. Lov$\acute{a}$sz, M. Saks and A. Schrijver, _A correction: “Orthogonal representations and connectivity of graphs”_ , Linear Algebra and its Applications, 313 (2000), 101–105.
  * [23] T. Peters, _Positive semidefinite maximum nullity and zero forcing number_ , Electronic Journal of Linear Algebra, 23 (2012), 815–830.
  * [24] T. Peters, _Positive semidefinite maximum nullity and zero forcing number_ , PhD Thesis, Iowa State University, 2012.
  * [25] S. Spacapan, _Connectivity of Cartesian products of graphs_ , Applied Mathematics Letters, 21 (2008), 682–685.
  * [26] T. Strohmer, R.W. Heath, _Grassmannian frames with applications to coding and communication_ , Appl. Comput. Harmonic Anal., 14 (2003), 257–275.
  * [27] M.A. Sustik, J.A. Tropp, I.S. Dhillon and R.W. Heath Jr, _On the existence of equiangular tight frames_ , Linear Algebra and its Applications, 426 (2007), 619–635.
  * [28] S. F. D. Waldron, _An introduction to finite tight frames_ , Springer, 2018.
  * [29] S. F. D. Waldron, _On the construction of equiangular frames from graphs_ , Linear Algebra and its applications, 431 (2009), 2228–2242.
  * [30] D. west, _Introduction to graph theory, Second edition_ , University of Illinois, Urbana, 2001.