text:
\begin{document}

\author{M.I.Belishev\thanks {St. Petersburg Department of Steklov Mathematical
        Institute, St.Petersburg, Russia, e-mail: belishev@pdmi.ras.ru. Supported
        by the RFBR grant 20-01 627-A and Volks-Wagen Foundation.},\,
        T.Sh.Khabibullin\thanks {St.Petersburg State University, e-mail: timur19983@outlook.com.}
        }

\title{Data characterization in dynamical inverse problem for the 1d wave equation with  matrix potential}

\maketitle

\begin{abstract}
The dynamical system under consideration is
\begin{align*}
&
u_{tt}-u_{xx}+Vu=0,\qquad x>0,\,\,\,t>0;\\
& u|_{t=0}=u_t|_{t=0}=0,\,\,x\geqslant 0;\quad
u|_{x=0}=f,\,\,t\geqslant 0,
\end{align*}
where $V=V(x)$ is a matrix-valued function ({\it potential});
$f=f(t)$ is an $\mathbb R^N$-valued function of time ({\it
boundary control}); $u=u^f(x,t)$ is a {\it trajectory} (an
$\mathbb R^N$-valued function of $x$ and $t$). The input/output
map of the system is a {\it response operator} $R:f\mapsto
u^f_x(0,\cdot),\,\,\,t\geqslant0$.

The {\it inverse problem} is to determine $V$ from given $R$. To
characterize its data is to provide the necessary and sufficient
conditions on $R$ that ensure its solvability.

The procedure that solves this problem has long been known and the
characterization has been announced (Avdonin and Belishev, 1996).
However, the proof was not provided and, moreover, it turned out
that the formulation must be corrected. Our paper fills this gap.
\end{abstract}

\noindent{\bf Key words:}\,\,\,1d wave equation with matrix
potential, reachable sets, controllability, propagation of
singularities, characterization of inverse data.

\noindent{\bf MSC:}\,\,\,35R30, 46-XX, 47-XX.
\bigskip

\section{Introduction}

\subsubsection*{About paper}
The subject of this work is the characterization of data in the
dynamical inverse problem for the one-dimensional vector wave
equation on semi-axis with matrix potential. To characterize the
data is to provide the necessary and sufficient conditions
ensuring the solvability of the inverse problem.

The inverse problem under consideration is to recover the matrix
potential from dynamical data (the response operator); it has long
been solved (see \cite{Avd Bel 96, Avd Bel Rozhk 98}). This is one
of the first problems solved by the BC-method. The issue is
exhausted if one needs only a procedure that determines the
potential from the data. However, in the understanding of
specialists, the inverse problem is completely solved if, in
addition to the procedure, the data characterization is provided.
If the potential is self-adjoint, the solvability conditions are
well known and, in fact, are reduced to positive definiteness of
the so-called {\it connecting operator} (CO) of the dynamical
system with boundary control, the evolution of which is governed
by the Sturm-Liouville operator with the given potential
\cite{BBlag book,Blag_71,Blag2}. There was a conjecture that, in
the general (non-self-adjoint) case, solvability is ensured by the
isomorphism of a relevant analogue of CO, and, moreover, this
result was announced in \cite{Avd Bel 96}. However, the proof was
not given and, moreover, certain doubts arose about sufficiency of
this condition. In particular, it was unclear what properties of
the CO provide the {\it locality} of the potential, i.e., the
absence of nonlocal Volterra additives in it. The question
remained open and the main purpose of our paper is to fill this
gap in the theory of one-dimensional dynamical inverse problems.

\subsubsection*{Statement and results}

All spaces, classes of functions and matrices in the paper are
real. We denote $\Omega:=[0,\infty)$ and $\Omega^T:=[0,T]\subset
\Omega$.
\smallskip

\noindent$\bullet$\,\,\,The forward problem is an initial-boundary
value problem of the form
    \begin{equation}\label{forward problem}
    \begin{cases}
    u_{tt}-u_{xx}+V\,u=0, & x>0,\ 0<t<T\\
    u|_{t=0}=u_t|_{t=0}=0,& x\geqslant 0\\
    u|_{x=0}=f, & 0\leqslant t\leqslant T,\\
    \end{cases}
    \end{equation}
where $V\in C^1_{\rm loc}(\Omega;\mathbb M^N)$ is a (real) matrix
valued function ({\it potential}), defined on the semi-axis
$x\geqslant 0$, $T>0$ the final moment of time; $f\in
L_2(([0,T];\mathbb{R}^N)$ a {\it boundary control}; $u=u^f(x,t)$
is a solution ({\it wave}) - an $\mathbb R^N$-valued function of
variables $x$ and $t$. Due to the hyperbolicity of the problem
(\ref{forward problem}), the relation ${\rm
supp\,}u^f(\cdot,t)\subset\Omega^t$ holds for all $t$.

Let $\mathscr F^T:=L_2([0,T];\mathbb R^N)$ be the space of
controls. The waves $u^f(\cdot,t)$ are time-dependent elements of
the space $\mathscr H^T:=L_2(\Omega^T;\mathbb R^N)$. Considering
the problem  (\ref{forward problem}) as a dynamical system, we
introduce a {\it control operator} $W^T:\mathscr F^T\to\mathscr
H^T$, acting by the rule:
    \begin{equation*}
(W^Tf)(x):=u^f(x,T), \quad x\in\Omega^T\,.
    \end{equation*}

Owing to the hyperbolicity of problem (\ref{forward problem}), its
extension of the form
   \begin{equation}\label{forward problem ext}
    \begin{cases}
    u_{tt}-u_{xx}+V\,u=0, & 0<x<T,\,\, 0<t<2T-x\\
    u|_{t<x}=0\\
    u|_{x=0}=f, & 0\leqslant t\leqslant 2T\\
   \end{cases}
  \end{equation}
is a well-posed initial boundary-valued problem, with which one
associates the so-called {\it extended response operator}
 \begin{equation*}
(R^{2T}f)(t)\,:=\,u^f_x(0,t), \quad 0\leqslant t\leqslant 2T,
    \end{equation*}
acting in the space $\mathscr F^{2T}$. Like all system
(\ref{forward problem}) attributes, the operator $R^{2T}$ is
determined by the potential $V|_{\Omega^T}$ (does not depend on
the values of $V|_{x>T}$).
\smallskip

\noindent$\bullet$\,\,\,The problem
    \begin{equation}\label{forward problem flat}
    \begin{cases}
    u_{tt}-u_{xx}+V_\flat\,u=0, & x>0,\ 0<t<T\\
    u|_{t=0}=u_t|_{t=0}=0,& x\geqslant 0\\
    u_{x=0}=f, & 0\leqslant t\leqslant T\\
    \end{cases}
    \end{equation}
with the potential $V_\flat(x):=(V(x))^\flat$, where $(...)^\flat:
\mathbb M^N\to\mathbb M^N$ is the matrix transposition, is said to
be {\it dual} to problem (\ref{forward problem}). Its solution
$u=u^f_\flat(x,t)$ possesses the same properties as $u^f$; the
control operator is
  \begin{equation*}
(W^T_\flat f)(x):=u^f_\flat(x,T), \quad x\in\Omega^T\,.
  \end{equation*}

The map $C^T:\mathscr F^T\to\mathscr F^T$,
    \begin{equation*}
    C^T\,:=\,(W^T_\flat)^*W^T
    \end{equation*}
is called a {\it connecting operator}. It is expressed via the
operator $R^{2T}$ by a simple and explicit relation established in
\cite{Avd Bel 96}.
\smallskip

\noindent$\bullet$\,\,\,The inverse problem is to recover the
potential $V|_{\Omega^T}$ from the given operator $R^{2T}$. Such a
{\it local} statement was originated by A.S.Blagovestchenskii in
\cite{Blag_71}; it is relevant to the hyperbolicity of the problem
(\ref{forward problem}).

The main result of the paper is as follows. Along with problems
(\ref{forward problem}) and (\ref{forward problem flat}), we
consider a family of "shortened" problems with final moments
$t=\xi\leqslant T$, each of which has its own connecting operator
$C^\xi$, acting in the corresponding space $\mathscr F^\xi$. All
$C^\xi$ are defined by $R^{2T}$. We show that $R^{2T}$ is the
response operator of a system (\ref{forward problem}) if and only
if {\it all} operators $C^\xi$ are isomorphisms. The necessity is
known: it is established in \cite{Avd Bel 96} in course of
analysis of the forward problem. The sufficiency was announced in
the same paper, but the proof still has not been provided. Our
work fills this gap. At the same time, the mistake made in
\cite{Avd Bel 96} is corrected: the assertion that for the
solvability of the inverse problem it is enough {\it only} $C^T$
to be isomorphism, turns out to be wrong. All $C^\xi$ have to be
isomorphisms.

\section{Forward problem}

\subsubsection*{Properties of waves}
Here the known properties of the solutions to problem
(\ref{forward problem}) are listed.  They are provided or easily
extracted from the results of \cite{BBlag book,Blag2}.
 \begin{Convention}\label{Conv 1}
All time-dependent functions are extended to $t<0$ by zero.
 \end{Convention}
\smallskip

\noindent$\bullet$\,\,\,Introduce the class of smooth controls
    $$
    \mathscr M^T\,:=\,\{f\in C^2([0,T];\mathbb R^N)\,|\,\,{\rm
    supp\,}f\subset(0,T]\},
    $$
which vanish near $t=0$. For $f\in \mathscr M^T$ the problem
(\ref{forward problem}) has a unique classical solution $u^f$ and
the representation
    \begin{equation}\label{solution_of_main_problem}
    u^f(x,t)=f(t-x)+\int_x^t w(x,s)f(t-s)\,ds,\qquad x\in\Omega^T,0\leqslant t\leqslant
    T
    \end{equation}
holds with the kernel $w$ that solves the Goursat matrix problem
    \begin{equation}\label{goursat_problem}
    \begin{cases}
    w_{tt}-w_{xx}+V\,w=0, & 0<x<t<T\\
    w(0,t)=0, & 0 \leqslant t \leqslant T\\
    w(x,x)=-\frac{1}{2}\int_0^x V(s)\,ds, & x\in\Omega^T
    \end{cases}
    \end{equation}
and is $C^2$-smooth in the domain
$\{(x,t)\,|\,\,x\in\Omega^T,\,\,0\leqslant x\leqslant t\leqslant
T\}$.

For $f\in\mathscr F^T:=L_2([0,T];\mathbb R^N)$ the right-hand side
of (\ref{solution_of_main_problem}) is well defined and regarded
as a (generalized) solution to the problem (\ref{forward problem})
of the class $C([0,T];L_2(\Omega^T))$. In the subsequent, we use
the following of its properties.
\smallskip

\noindent$\bf 1.$\,\,\,The relation
 \begin{equation}\label{supp u^f}
   {\rm supp\,} u^f(\cdot,t)\,\subset \Omega^t,\qquad t\geqslant 0
    \end{equation}
holds and shows that the waves propagate in the semi-axis
$x\geqslant 0$ with the speed $1$.
\smallskip

\noindent$\bf 2.$\,\,\,For the controls $f_\tau(t):=f(t-\tau)$,
which act with the delay $\tau>0$, one has
    \begin{equation}\label{shift time}
    u^{f_\tau}(\cdot,t)\,=\,u^f(\cdot,t-\tau),\qquad t\geqslant 0
    \end{equation}
(recall the Convention \ref{Conv 1}!); as a consequence, for
smooth controls the relations
    \begin{equation}\label{diff u^f}
    u^f_t = u^{\frac{df}{dt}},\qquad u^f_{tt} =
    u^{\frac{d^2f}{dt^2}}\,\overset{\rm see\,\,(\ref{forward problem})}=u^f_{xx}-Vu^f
    \end{equation}
are valid.
\smallskip

\noindent$\bf 3.$\,\,\,As it is seen from
(\ref{solution_of_main_problem}), owing to the continuity of the
integral term, the following is valid. If the control $f$ is
piecewise continuous and has a jump at the moment
$t=T-\xi$\,\,\,($0<\xi\leqslant T$), the wave $u^f(\cdot,t)$ is
also piecewise continuous and has a jump at a point $t=\xi$, and
the equality
    \begin{equation}\label{jump}
    u^f(x,T)\bigg{|}_{x=\xi-0}^{x=\xi+0}=-f(t)\bigg{|}_{t=T-\xi-0}^{t=T-\xi+0}
    \end{equation}
holds in $\mathbb R^N$. This is a simplest geometrical optics
relation: it shows that the wave discontinuity initiated by the
jump of control propagates along the semi-axis $x\geqslant 0$ with
the unit velocity, and the `amplitude' of the discontinuity
remains constant.
\smallskip

\noindent$\bf 4.$\,\,\,All the above properties and relations are
valid for the solution $ u^f_\flat$ to the dual problem
(\ref{forward problem flat}) and the solution $ u^f$ to the
extended problem (\ref{forward problem ext}).

\subsubsection*{Dynamical system}
Here problem (\ref{forward problem}) is endowed with standard
attributes of dynamical system: spaces and operators. The system
is denoted by $\alpha^T$.
\smallskip

\noindent$\bullet$\,\,\,The space of controls is $\mathscr
F^T=L_2([0,T],\mathbb{R}^N)$ with the inner product
    $$
    (f,g)_{\mathscr F^T}\,=\,\int_0^T\langle f(t), g(t)\rangle\,dt\,,
    $$
where $\langle\cdot, \cdot\rangle$ is the standard inner product
in $\mathbb R^N$, is said to be the {\it outer space} of the
system $\alpha^T$. It contains an increasing family of subspaces
    $$
    {\mathscr F}^{T,\xi}:=\{f\in \mathscr F^T\,|\,\,{\rm supp\,}f\subset [T-\xi,T]\},\qquad
    0\leqslant \xi\leqslant T
    $$
($\mathscr F^{T,0}=\{0\},\,\mathscr F^{T,T}=\mathscr F^T$) formed
by delayed controls: $T-\xi$ is the delay, $\xi$ is the action
time.

The space $\mathscr H^T:=L_2(\Omega^T,\mathbb{R}^N)$ with inner
product
    \begin{equation*}
    (u,v)_{\mathscr H^T}:=\int_{\Omega^T} \langle u(x), v(x)\rangle\, dx
    \end{equation*}
is called the {\it inner space}, the waves $u^f(\cdot,t)$ are its
elements. It contains an increasing family of subspaces
    $$
    \mathscr H^\xi:=\{y\in \mathscr H^T\,|\,\,{\rm supp\,}y\subset
    \Omega^\xi\},\qquad 0\leqslant \xi\leqslant T
    $$
($\mathscr H^{0}=\{0\}$). By (\ref{supp u^f}), we have
$u^f(\cdot,t)\in\mathscr H^\xi$ for $0\leqslant t\leqslant \xi$.
    \smallskip

\noindent$\bullet$\,\,\, The operator $W^T:\ \mathscr F^T\to
\mathscr{H}^T$,
    \begin{equation*}
    (W^Tf)(x):=u^f(x,T),\qquad x\in\Omega^T
    \end{equation*}
is said to be the {\it control operator}. By
(\ref{solution_of_main_problem}), the representation
    \begin{equation}\label{int_control}
    (W^Tf)(x)=f(T-x)+\int_x^Tw(x,s)f(T-s)ds,\qquad
    x\in\Omega^T\,.
    \end{equation}
holds. The control operator is an isomorphism of the space
$\mathscr F^T$. Indeed, the equation $W^T f=y$ is a second kind
Volterra equation, which is solvable for any $y\in\mathscr H^T$.
Moreover, (\ref{int_control}) implies
    \begin{equation}\label{controllability}
    W^T{\mathscr F}^{T,\xi}\,=\,\mathscr H^\xi\,,\qquad 0\leqslant \xi\leqslant T\,.
    \end{equation}
The second equality in (\ref{diff u^f}) can be written as:
    \begin{equation}\label{Wd^2=LW}
    W^T\,\frac{d^2}{dt^2}\,=\,-LW^T\,,
    \end{equation}
where $L=-\frac{d^2}{dx^2}+V$ is Sturm-Liouville operator, which
governs the evolution of system $\alpha^T$.
    \smallskip

\noindent$\bullet$\,\,\,The operator $R^T:\mathscr{F}^T\to
    \mathscr{F}^T,\,\,\,{\rm Dom\,}R^T=\{f\in \mathscr{F}^T\,|\,\,
    \frac{df}{dt}\in\mathscr{F}^T,\, f(0)=0\}$,
    \begin{equation*}
    (R^Tf)(t)\,:=\,u_x^f(0,t)\,,\qquad 0\leqslant t\leqslant T
    \end{equation*}
is called the {\it response operator} of the system $\alpha^T$.
Differentiation in (\ref{solution_of_main_problem}) leads to the
representation
    \begin{equation*}
    (R^Tf)(t)=-\frac{df}{dt}(t)+\int_0^tr(t-s)f(s)ds\,,\qquad 0\leqslant t\leqslant T,
    \end{equation*}
where $r(s):=w_x(0,s)$ is a $C^1$-smooth matrix-valued function
called the {\it response function}.

Also, with the system $\alpha^T$ one associates the {\it extended
response operator} $R^{2T}:\mathscr{F}^{2T}\to
\mathscr{F}^{2T},\,\,\,{\rm Dom\,}R^{2T}=\{f\in
\mathscr{F}^{2T}\,|\,\,  \frac{df}{dt}\in\mathscr{F}^{2T},\,
f(0)=0\}$,
    \begin{equation*}
    (R^{2T}f)(t)\,:=\,u_x^f(0,t)\,,\qquad 0\leqslant t\leqslant {2T},
    \end{equation*}
where $u^f$ is a solution to the extended problem (\ref{forward
problem ext}). The representation
    \begin{equation}\label{int_reaction}
    (R^{2T}f)(t)=-f'(t)+\int_0^tr(t-s)f(s)ds\,,\qquad 0\leqslant t\leqslant {2T},
    \end{equation}
holds with the matrix-valued reply function $r$. The important
fact is that the operator $R^{2T}$ and its response function
$r|_{[0,2T]}$ are determined by the potential $V|_{\Omega^T}$ (do
not depend on its values outside $\Omega^T$).
\smallskip

\noindent$\bullet$\,\,\, The problem (\ref{forward problem flat})
describes a dynamical system, which is called dual to $\alpha^T$
and denoted by $\alpha^T_\flat$. Obviously, the dual system has
the same attributes and properties as the original one. The inner
and outer spaces of both systems are the same, the corresponding
operators $W^T_\flat,\,R^T_\flat$ and $R^{2T}_\flat$ possess the
same properties and representations. As shown in the \cite{Avd Bel
96}, the response functions are related by the equality
    \begin{equation*}
    r_\flat(t)\,=\,(r(t))^\flat\,,\qquad 0\leqslant t\leqslant
    {2T}\,.
    \end{equation*}
Note that the operator $W^T_\flat$ maps $\mathscr F^T$ onto
$\mathscr H^T$ isomorphically and
 \begin{equation}\label{controllability flat}
    W^T_\flat{\mathscr F}^{T,\xi}\,=\,\mathscr H^\xi\,,\qquad 0\leqslant \xi\leqslant T
 \end{equation}
holds. Its adjoint $(W^T_\flat)^*:\mathscr H^T\to\mathscr F^T$ is
also an isomorphism.
\smallskip

\noindent$\bullet$\,\,\, The operator $C^T:\
    \mathscr{F}^T\to\mathscr{F}^T$,
    \begin{equation}\label{connecting}
    C^T:=(W_{{\flat}}^T)^*W^T
    \end{equation}
is said to be the {\it connecting operator}. By the definition, we
have
    \begin{equation*}
    (C^Tf,g)_{\mathscr{F}^T}=(W^T f,W^T_\flat
    g)_{\mathscr H^T}=(u^f(\cdot,T),u_{{\flat}}^g(\cdot,T))_{\mathscr{H}^T}\,,
    \end{equation*}
so that operator $C^T$ connects metrics of spaces $\mathscr{F}^T$
and $\mathscr{H}^T$. As a composition of two isomorphisms, it is
an isomorphism of the outer space $\mathscr F^T$.

The key fact of the BC-method as an approach to inverse problems
is a simple and explicit relation that expresses the connecting
operator via the response operator and response function. As is
shown in the \cite{Avd Bel 96}, the representation
    \begin{equation}\label{int_connecting}
    (C^Tf)(t)=f(t)+\int_0^TC^T(t,s)f(s)\,ds\,,\qquad 0\leqslant t\leqslant {T}
    \end{equation}
with the matrix kernel
    \begin{equation*}
    C^T(t,s)=\frac{1}{2}\int_{|t-s|}^{2T-t-s}r(\eta)\,d\eta\,,\qquad 0\leqslant s,t\leqslant {T}
    \end{equation*}
holds. Thus, the connecting operator is determined by the reply
function $r|_{0\leqslant t\leqslant {2T}}$.
    \smallskip

The dual system $\alpha^T_\flat$ has connecting operator
    $$
    C^T_\flat\,:=\,(W^T)^*W^T_\flat\,=\,(C^T)^*,
    $$
for which the representation (\ref{int_connecting}) is valid,
replacing the kernel $C^T(t,s)$ by
$C^T_\flat(t,s)=[C^T(t,s)]^\flat$.

\subsubsection*{Systems $\alpha^\xi$}
Consider the family of `shortened' systems
    \begin{equation*}
    \begin{cases}
    u_{tt}-u_{xx}+V(x)u=0, & x>0,\ 0<t<\xi\\
    u|_{t=0}=u_t|_{t=0}=0,& x\geqslant 0\\
    u_{x=0}=f, & 0\leqslant t\leqslant \xi
    \end{cases}
    \end{equation*}
indexed by the parameter $0<\xi\leqslant T$. Systems $\alpha^\xi$
are equipped with their spaces $\mathscr F^\xi$ and $\mathscr
H^\xi$ and operators $W^\xi,\,R^\xi,\,R^{2\xi},\,C^\xi$. Each
$C^\xi$ is an isomorphism in $\mathscr F^\xi$, the representation
(\ref{int_connecting})
    \begin{equation}\label{int_connecting xi}
    (C^\xi f)(t)=f(t)+\int_0^\xi C^\xi(t,s)f(s)\,ds\,,\qquad 0\leqslant t\leqslant {\xi}
    \end{equation}
    with matrix kernel
    \begin{equation*}
    C^\xi(t,s)=\frac{1}{2}\int_{|t-s|}^{2\xi-t-s}r(\eta)\,d\eta\,,\qquad 0\leqslant s,t\leqslant {T}
    \end{equation*}
being valid.
\smallskip

\noindent$\bullet$\,\,\, The operators $ C^\xi $ are related to
the operator $ C^T $ as follows. Recall Convention \ref{Conv 1}
and introduce the auxiliary operators
    \begin{equation*}
    {e^{T,\xi}}: \mathscr F^\xi\to\mathscr F^T,\quad ({e^{T,\xi}} f)(t):=f(t-(T-\xi)),\qquad 0\leqslant
    t\leqslant T;
    \end{equation*}
the adjoint operators are
    \begin{equation*}
    {(e^{T,\xi})^*}: \mathscr F^T\to \mathscr F^\xi,\quad (({e^{T,\xi}})^*
    f)(t):=f(t+(T-\xi))\,,\qquad 0\leqslant t\leqslant\xi\,.
    \end{equation*}
It is easy to check that
    \begin{equation*}
    {(e^{T,\xi})^*} {e^{T,\xi}}\,=\,\mathbb I_{\mathscr F^\xi};\qquad
    {e^{T,\xi}}{(e^{T,\xi})^*}=X^{T,\xi}\,,
    \end{equation*}
where $\mathbb I_{\mathscr F^\xi}$ is the unit operator, and
$X^{T,\xi}$ is the orthogonal projector in $\mathscr F^T$ onto
${\mathscr F}^{T,\xi}$, which cuts off the $\mathbb R^N$-valued
controls to the interval $[T-\xi,T]$:
    \begin{equation}\label{cutt X}
    (X^{T,\xi}f)(t):=\begin{cases}
    0, & 0\leqslant t<T-\xi\\
    f(t), & T-\xi\leqslant t\leqslant T
    \end{cases}\,.
    \end{equation}
By the use of (\ref{int_connecting}), one easily derives
    \begin{equation}\label{C^xi via C^T}
    C^\xi\,=\,{(e^{T,\xi})^*} C^T{e^{T,\xi}}\,, \qquad 0<\xi\leqslant T\,.
    \end{equation}

\noindent$\bullet$\,\,\,As easily follows from
(\ref{int_reaction}), the relationship of the extended response
ope\-rator with the `shortened' response operators is of the form
    \begin{equation*}
    R^\xi\,=\,(e^{2T,\xi})^*R^{2T} e^{2T,\xi}\,, \qquad 0<\xi\leqslant
    2T\,.
    \end{equation*}

\section{Inverse problem}\label{Sec Inverse problem}

\subsubsection*{Statement}
As noted above, the operator $R^{2T}$ is determined by the values
of the potential $V^T$ on the segment $\Omega^T$. Hence, the
relevant statement of the inverse problem, which respects such a
locality, is as follows: {\it given $R^{2T}$ to recover
$V|_{\Omega^T}$}. Also, since to give $R^{2T}$ is to know the
response matrix-function, one needs to determine $V|_{\Omega^T}$
from the given $r|_{0\leqslant t\leqslant 2T}$.

In such a statement, the problem is solved in \cite{Avd Bel 96}
and below we briefly describe a simplified version of the
procedure for solving it. The procedure is preceded with a
description of its instruments: projectors and the so-called
amplitude formula.

\subsubsection*{Projectors}

\noindent$\bullet$\,\,\, Fix a positive $\xi\leqslant T$. In the
system $\alpha^T$, the subspace
 $$
\mathscr U^\xi:= W^T{\mathscr
F}^{T,\xi}\,=\,\{u^f(\cdot,T)\,|\,\,f\in{\mathscr
F}^{T,\xi}\}\overset{\rm see\,\,(\ref{shift
time})}=\,\{u^f(\cdot,\xi)\,|\,\,f\in{\mathscr F}^{T}\}
 $$
formed by waves, is called {\it reachable} (at the moment
$t=\xi$).

The orthogonal projector in $\mathscr H^T$ onto $\mathscr U^T$ is
said to be the {\it wave projector}. By (\ref{controllability}),
it coincides with the projector in $\mathscr H^T$ onto the
subspace $\mathscr H^\xi$, which cuts off the $\mathbb R^N$-valued
functions to $\Omega^\xi$. So, we have:
    $$
    P^\xi y\,=\,\begin{cases}
    y & \text{in}\,\,\,\Omega^\xi\\
    0  & \text{in}\,\,\,\Omega^T\setminus\Omega^\xi
    \end{cases}\,, \qquad 0\leqslant \xi\leqslant {T}\,.
    $$
\smallskip

\noindent$\bullet$\,\,\,In the space $\mathscr{F}^T$, define the
operator
 \begin{equation}\label{W cal P xi= P xi W}
    \mathcal{P}^{T,\xi}\,:=\,[W^T]^{-1}P^\xi W^T\,.
 \end{equation}
Since $W^T$ acts isomorphically, whereas
$(\mathcal{P}^{T,\xi})^2=\mathcal{P}^{T,\xi}$ obviously holds, it
is a bounded projector.  Let us describe in more detail how it
acts. Begin with a general operator lemma.
\smallskip

Let $\mathscr F$ and $\mathscr H$ be the Hilbert spaces,
$\mathscr F'\subset\mathscr F$ and $\mathscr H'\subset\mathscr H$ the (closed) subspaces;
$e:\mathscr F'\to\mathscr F$ the embedding, which satisfies $e^*e=\mathbb
I_{\mathscr F'}$ and $ee^*=X$, where $X$ projects orthogonally in $\mathscr F$
onto $\mathscr F'$. Denote $\mathscr F'_\bot:=\mathscr F\ominus\mathscr F'$ and
$\mathscr H'_\bot:=\mathscr H\ominus\mathscr H'$; let $P$ be the orthogonal projector
in $\mathscr H$ onto $\mathscr H'$.

Let $W:\mathscr F\to\mathscr H$ and $V:\mathscr F\to\mathscr H$ be isomorphisms provided
$W\mathscr F'=V\mathscr F'=\mathscr H'$. Introduce the isomorphism $C:=V^*W: \mathscr F\to\mathscr F$
and the subspace $C^{-1}\mathscr F'_\bot\subset \mathscr F$. The operator
$\mathcal P:=W^{-1}PW$ acts in $\mathscr F$.
 \begin{Lemma}\label{lemma P^{T,xi}+}
Let $C':=e^*C\,e$ act isomorphically in $\mathscr F'$. Then the
decomposition in direct sum $\mathscr F=\mathscr F'\,\dot+\,C^{-1}\mathscr F'_\bot$
holds, whereas $\cal P$ is the (skew) projector in $\mathscr F$ onto
$\mathscr F'$ in parallel to $C^{-1}\mathscr F'_\bot$. The representation
  \begin{equation}\label{repres mathcal P general}
    \mathcal{P}\,=\,e\,[C']^{-1}{e^*}\,C
 \end{equation}
holds.
 \end{Lemma}
\begin{proof}
$\bf 1.$\,\,\,The operators $W$ and $V$ act isomorphically, and we
have $W\mathscr F'=V\mathscr F'=\mathscr H'$. The latter equality
implies $V^*\mathscr H'_\bot=\mathscr F'_\bot$ and leads to
 \begin{align*}
&
\mathscr F=W^{-1}[\mathscr H'\oplus\mathscr H'_\bot]=W^{-1}\mathscr H'\,\dot+\,W^{-1}\mathscr H'_\bot=\mathscr F'\,\dot+\,C^{-1}\mathscr F'_\bot\,.
 \end{align*}

$\bf 2.$\,\,\,One has $\mathcal P^2=\mathcal P$ just by the
definition of $\mathcal P$.

If $f\in\mathscr F'$ then $W f\in\mathscr{H}'$ and, hence,
 $$
\mathcal P f=W^{-1}P W f=W^{-1} W f=f\,.
 $$

If $f\in C^{-1}\mathscr F'_\bot$ then $f=C^{-1}g$ with $g\in \mathscr F'_\bot$
and one has
 $$
\mathcal{P}f=W^{-1}P W^T C^{-1}g=W^{-1}P[V^*]^{-1}g=0
 $$
in view of $[V^*]^{-1}g\in\mathscr H'_\bot$.

Thus, $\mathcal{P}$ is an idempotent, which acts identically on
$\mathscr F'$ and annuls $C^{-1}\mathscr F'_\bot$. Therefore, it
projects in $\mathscr F$ onto $\mathscr{F}'$ in parallel to
$C^{-1}\mathscr{F}'_\bot$.
\smallskip

$\bf 3.$\,\,\,Let $Q$ be the right hand side of (\ref{repres
mathcal P general}). Then we have
 $$
Q^2=e\,[C']^{-1}{e^*}\,C\,e\,[C']^{-1}{e^*}\,C=e\,[C']^{-1}C'\,[C']^{-1}{e^*}\,C=Q\,.
 $$

If $f\in\mathscr F'$ then $X f=ee^*f=f$ and, hence,
 $$
Q f=e\,[C']^{-1}{e^*}\,Cf=e\,[C']^{-1}{e^*}\,Ce\,e^*f
=e\,[C']^{-1}C'e^*f=f\,.
 $$

If $f\in C^{-1}\mathscr F'_\bot$ then $f=C^{-1}g$ with $g\in \mathscr F'_\bot$
and one has
 $$
Qf=e\,[C']^{-1}{e^*}\,CC^{-1}g=0
 $$
in view of $e^*\mathscr F'_\bot=\{0\}$.

Thus, $Q$ is an idempotent, which acts identically on $\mathscr
F'$ and annuls $C^{-1}\mathscr F'_\bot$. Therefore, it projects in
$\mathscr F$ onto $\mathscr{F}'$ in parallel to
$C^{-1}\mathscr{F}'_\bot$ and, hence, coincides with $\mathcal P$.
\end{proof}
\smallskip

Return to the definition (\ref{W cal P xi= P xi W}). Applying the
Lemma \ref{lemma P^{T,xi}+} to $\mathscr F=\mathscr F^T$, $\mathscr F'=\mathscr
F^{T,\xi}$, $\mathscr F'_\bot=\mathscr F^{T,\xi}_\bot=\mathscr F^T\ominus\mathscr
F^{T,\xi}$, $\mathscr H=\mathscr H^T$, $\mathscr H'=\mathscr H^{\xi}$, $W=W^T$,
$V=W^T_\flat$, $\mathcal P=\mathcal P^{T,\xi}$, and referring to
(\ref{C^xi via C^T}), we arrive at the following.

 \begin{Corollary}\label{Cor P^{T,xi}}
Operator $\mathcal{P}^{T,\xi}$ is the (skew) projector in
$\mathscr F^T$ onto $\mathscr{F}^{T,\xi}$ in parallel to
$[C^T]^{-1}\mathscr{F}^{T,\xi}_{\bot}$. The representation
 \begin{equation}\label{repres mathcal P}
    \mathcal{P}^{T,\xi}\,=\,{e^{T,\xi}} [C^\xi]^{-1}{(e^{T,\xi})^*} C^T\,,\qquad
    0<\xi\leqslant T
 \end{equation}
holds.
 \end{Corollary}
\noindent$\bullet$\,\,\,Due to the complete equality of systems
$\alpha^T$ and $\alpha^T_\flat$, the operator
\begin{equation}\label{W cal P xi= P xi W flat}
    \mathcal{P}^{T,\xi}_\flat\,:=\,[W^T_\flat]^{-1}P^\xi W^T_\flat
 \end{equation}
has the same properties as $\mathcal{P}^{T,\xi}$. Namely, it is
the projector in $\mathscr F^T$ onto $\mathscr F^{T,\xi}$ in parallel of the
subspace $[(C^T)^*]^{-1}\mathscr F^{T,\xi}_\bot$, and is represented in
the form.
 \begin{equation}\label{repres mathcal P flat}
    \mathcal{P}^{T,\xi}_\flat\,=\,{e^{T,\xi}} [(C^\xi)^*]^{-1}{(e^{T,\xi})^*} (C^T)^*\,,\qquad
    0<\xi\leqslant T\,.
 \end{equation}

\subsubsection*{Amplitude formula}
For a positive $\xi\leqslant T$ and control $f\in\mathscr M^T$,
one has
    \begin{align*}
    W^T\mathcal P^{T,\xi} f\overset{\rm see\,\, (\ref{W cal P xi= P xi W})}=P^\xi W^T
    f=P^\xi u^f(\cdot,T)= \begin{cases} u^f(\cdot,T) &
    \text{in}\,\,\,\Omega^\xi\\
    0 & \text{in}\,\,\,\Omega^T\setminus\Omega^\xi
    \end{cases}\,.
    \end{align*}
The control $\mathcal P^{T,\xi} f\in{\mathscr F}^{T,\xi}$ vanishes
at $0\leqslant t<T-\xi$ and, in the generic case, has an $\mathbb
R^N$-valued `jump' at the moment $t=T-\xi$. The wave $u^{\mathcal
P^{T,\xi} f}=P^\xi   u^f(\cdot,T)\in\mathscr H^\xi$ vanishes
outside $\Omega^\xi$ and also has a jump at the point $x=\xi$. The
values (amplitudes) of these jumps are related by the equality
(\ref{jump}). Since the wave $u^f(\cdot,T)$ is continuous in
$\Omega^T$, we have the relation
    \begin{equation*}
    (\mathcal{P}^{T,\xi} f)(T-\xi+0)\,=\,(P^\xi
    u^f(\cdot,T))(\xi-0)=u^f(\xi,T)\,.
    \end{equation*}
Writing it in the form
    \begin{equation}\label{AF}
    (W^T f)(\xi)\,=\,(\mathcal{P}^{T,\xi} f)(T-\xi+0)\,, \qquad
    \xi\in\Omega^T,
    \end{equation}
we get the so-called {\it amplitude formula}, which is a simplest
example of the geometrical optics relations describing the
propagation of singularities in the system $\alpha^T$. Formulas of
this type play the key role in all basic versions of the BC-method
\cite{B CIRM, B EACM, B UMN}.

\subsubsection*{Recovering the potential}
Let $r|_{0\leqslant t\leqslant 2T}$ be the response
matrix-function of a dynamical system $\alpha^T$ of the form
(\ref{forward problem}). The following procedure recovers the
potential $V$ on the segment $\Omega^T$.
\smallskip

\noindent${\bf A.}$\,\,\, Given $r$ determine the operators
$C^\xi$ for all $0\leqslant\xi\leqslant T$ by the use of
representation (\ref{int_connecting xi}).
\smallskip

\noindent${\bf B.}$\,\,\,Find the projectors $\mathcal P^{T,\xi}$
for $0\leqslant\xi\leqslant T$ by (\ref{repres mathcal P}).
\smallskip

\noindent${\bf C.}$\,\,\,Determine the control operator $W^T$ by
means of the formula (\ref{AF}) and then find its kernel $w$ (see
(\ref{int_control})). Knowing the kernel, recover the potential
$V|_{\Omega^T}$ by $V(x)=-2\,\frac{dw(x,x)}{dx}$\,\, (see
(\ref{goursat_problem})).

\section{Data characterization}

To characterize the data of the inverse problem under
consideration is to provide the necessary and sufficient
conditions on a matrix-function $r$, which guarantee that it is
the response function of some system $\alpha^T$ and thereby ensure
the solvability of the inverse problem. As will be shown, these
conditions are that all operators defined (via $r$) by the
right-hand side of (\ref{int_connecting xi}) act isomorphically in
the corresponding spaces. The necessity is already established.
Indeed, if $r$ {\it is the reply function}, the right-hand side
coincides with the connecting operator $C^\xi$ of the system
$\alpha^\xi$, which is isomorphism in $\mathscr F^\xi$.
Sufficiency is more complicated and the rest of the paper is
devoted to its proof.

The proof of sufficiency is constructive. In fact, it reduces to
applying the procedure ${\bf A\!-\!C}$ to the given function $r$.
As the result, we construct some dynamical system $\alpha^T$. In
course of the construction, it is verified that the isomorphism of
all $ C^\xi $ ensures that all steps of the procedure are
realizable. At the final step, we show that the response function
of the constructed system coincides with the function $r$, with
which we has began.

We proceed to the implementation of this program, starting with an
exact statement of the main result.
    \begin{Theorem}\label{Th 1}
A matrix-function $r \in C^1([0,2T]; \mathbb M^N)$ is the response
function of a dynamical system of the form (\ref{forward problem})
if and only if for every positive $\xi\leqslant T$ the operator
$C^\xi$ defined by
        \begin{equation}\label{int_connecting xi+}
        (C^\xi f)(t)=f(t)+\int_0^\xi C^\xi(t,s)f(t-s)\,ds\,,\qquad 0\leqslant t\leqslant {\xi}
        \end{equation}
with the kernel
        \begin{equation}\label{ker_connecting}
        C^\xi(t,s)=\frac{1}{2}\int_{|t-s|}^{2\xi-t-s}r(\eta)\,d\eta\,.
        \end{equation}
is an isomorphism of the space $\mathscr F^\xi$.
    \end{Theorem}
Let us make a remark about the notation in the forthcoming proof
of sufficiency. In the above statement, the symbol $C^\xi$ does
not assume that this operator is the connecting operator of some
system $\alpha^\xi$: it is only a candidate for this role. Other
symbols $\mathcal P^{T,\xi},\,W^T,\,R^{2T}$, etc, are also used in
this way. Such a trick simplifies the notation and, on the other
hand, clarifies the meaning of the introduced objects.

\subsubsection*{Projectors}
\noindent$\bullet$\,\,\,Realizing the plan outlined above, we
introduce the relevant analogues of the objects belonging to the
system $\alpha^T$. Begin with the projectors $\mathcal P^{T,\xi}$.
However, to introduce them by (\ref{W cal P xi= P xi W}) is not
possible because, at the moment, no $W^T$ is given. Therefore,
focusing on the representation (\ref{repres mathcal P}), we {\it
define}
 \begin{equation}\label{repres mathcal P xi+}
    \mathcal{P}^{T,\xi}\,:=\,e^{T,\xi}\, [C^\xi]^{-1} (e^{T,\xi})^* C^T\,,\qquad 0<\xi\leqslant T
 \end{equation}
that is correct since all $C^\xi$ are isomorphisms by assumption
of the Theorem. Then, by perfect analogy with (\ref{repres mathcal
P xi+}), we put
 \begin{equation}\label{repres mathcal P flat+}
    \mathcal{P}^{T,\xi}_\flat\,:=\,{e^{T,\xi}} [(C^\xi)^*]^{-1}{(e^{T,\xi})^*} (C^T)^*\,,\qquad
    0<\xi\leqslant T
 \end{equation}
(compare with (\ref{W cal P xi= P xi W flat}), (\ref{repres
mathcal P flat})) that is correct since $(C^\xi)^*$ are
isomorphisms.
   \begin{Proposition}\label{Prop CP=PflatC}
Operator $\mathcal{P}^{T,\xi}$ is the projector in $\mathscr F^T$ onto
$\mathscr F^{T,\xi}$ in parallel to $[C^T]^{-1}\mathscr F^{T,\xi}_\bot$.
Operator $\mathcal P^{T,\xi}_\flat$ projects in $\mathscr F^T$ onto
$\mathscr F^{T,\xi}$ in parallel to $[(C^T)^*]^{-1}\mathscr F^{T,\xi}_\bot$. The
equalities
 \begin{equation}\label{CP=PflatC}
        C^T\mathcal{P^\xi}=(\mathcal{P^\xi}_\flat)^*C^T,\quad
\mathcal{P^\xi}(C^T)^{-1}=(C^T)^{-1}(\mathcal{P^\xi_{{\flat}}})^*\,
  \end{equation}
are valid.
   \end{Proposition}
Indeed, to verify the first and second assertions, one needs just
to repeat the arguments of the item ${\bf 3.}$ from the proof of
Lemma \ref{lemma P^{T,xi}+}. Then the equalities (\ref{CP=PflatC})
easily follow from (\ref{repres mathcal P xi+}) and (\ref{repres
mathcal P flat+}).
\smallskip

\noindent$\bullet$\,\,\,Here we derive an efficient representation
for the projectors $\mathcal{P}^{T,\xi}$ and
$\mathcal{P}^{T,\xi}_{{\flat}}$. Recall that the projector
$X^{T,\xi}$ is defined by (\ref{cutt X}).
    \begin{Lemma}\label{L repres cal P^xi integral}
For any $0<\xi\leqslant T$, the representation
        \begin{equation}\label{P_int repres}
        (\mathcal{P}^{T,\xi}
        f)(t)=(X^{T,\xi}f)(t)+\int_0^{T-\xi}m^\xi(t,s)f(s)\,ds,\qquad
        0\leqslant t\leqslant T
        \end{equation}
holds with a piecewise $C^2$-smooth kernel $m^\xi$, which obeys
$m^\xi(t,s)|_{t>T-\xi}\equiv 0$.
    \end{Lemma}
    \begin{proof}(sketch)\,\,\,
By the general Fredholm integral equation theory, the inverse to
the isomorphism $C^\xi$ is takes the form
        \begin{equation}\label{C^xi inverse}
        ((C^\xi)^{-1}f)(t)=f(t)-\int_0^\xi l^\xi(t,s) f(s)\,ds\,,\qquad
        0\leqslant t\leqslant \xi
        \end{equation}
with a matrix kernel $l^\xi$ of the same smoothness as the kernel
$C^\xi$: it is continuous in square $[0,\xi]\times[0,\xi]$ twice
continuously differentiable outside the diagonal $t=s$.

Substituting (\ref{int_connecting xi+}) (with $\xi=T$) and
(\ref{C^xi inverse}) to the right of the definition (\ref{repres
mathcal P xi+}), as a result of cumbersome calculations
(integration by parts, changing the order of integration, etc.),
we arrive at (\ref{P_int repres}). Also, the calculations provide
 \begin{equation}\label{kernel m}
            m^\xi(t,s)=X^{T,\xi}C^T(t,s)-\int_0^\xi
            l^\xi(t-(T-\xi),\eta)\,C^T(\eta+(T-\xi),s)\,d\eta\,,
 \end{equation}
where $C^T(\cdot,\cdot)$ is the kernel (\ref{ker_connecting}) for
$\xi=T$.
\end{proof}

Note in addition that the integration limits in (\ref{P_int
repres}) correspond to how the projector $\mathcal P^{T,\xi}$
acts. If $f\in{\mathscr F}^{T,\xi}$, then $f|_{0\leqslant
t\leqslant T-\xi}=0$; therefore, the integral vanishes, which
provides $\mathcal P^{T,\xi} f={X^{T,\xi}} f=f$. Also, since
$\mathcal P^{T,\xi} f|_{0\leqslant t\leqslant T-\xi}=0$ for any
$f$, the kernel $m^\xi$ must vanish identically for $t>T-\xi$.
\smallskip

By the use of (\ref{repres mathcal P flat+}), quite analogous
arguments lead to the representation
     \begin{equation*}
    (\mathcal{P}^{T,\xi}_{{\flat}}
    f)(t)=(X^{T,\xi}f)(t)+\int_0^{T-\xi}
    m^\xi_\flat(t,s)f(s)\,ds,\qquad
    0\leqslant t\leqslant T
    \end{equation*}
with kernel $m^\xi_\flat$ having the same properties as $m^\xi$.

\subsubsection*{Operators $W^T$ and $W^T_{{\flat}}$}

\noindent$\bullet$\,\,\,The next definition is motivated by the
amplitude formula (\ref{AF}). Let us recall that
    $\mathscr H^T=L_2(\Omega^T;\mathbb R^N)$ and introduce the operator
    $W^T:\mathscr{F}^T\to \mathscr H^T$,
    \begin{equation}\label{W_T!}
    (W^Tf)(x):=(\mathcal{P}^{T,x} f)(T-x+0),\qquad
    x\in\Omega^T.
    \end{equation}
Note that, at the moment, it is just an operator defined (in
several steps) by the given function $r|_{[0,2T]}$. However, later
on, it will turn out to be the control operator of some system
$\alpha^T$. The construction of this system is the main storyline
of the proof of sufficiency.
\smallskip

To obtain a representation of $W^T$ it suffices to put $t=T-x+0$
in (\ref{P_int repres}) and take into account the form of the
kernel $m^\xi$ in (\ref{kernel m}). As a result of simple
calculations, one gets
    \begin{equation}\label{W_T_int}
    (W^Tf)(x)=f(T-x)+\int_x^Tw(x,s)f(T-s)\,ds,\qquad x\in\Omega^T
    \end{equation}
with $C^2$-smooth matrix kernel of the form
    \begin{align}
    \notag &  w(x,s) \,=\,C^T(T-x,T-s)\,-\\
    \label{W_T_int_ker} &  \,-\int_0^x
    l^x(0,\eta)\,C^T(\eta+(T-x),T-s)\, d\eta\,,\qquad 0\leqslant x\leqslant s\leqslant
    T\,,
    \end{align}
where $l^x$ is taken from (\ref{C^xi inverse}). Putting $x=0$ in
(\ref{W_T_int_ker}) and taking into account
$C^T(T,T)\overset{\rm see\,\,(\ref{ker_connecting})}=0$, we get
    \begin{equation*}
    w(0,s)\,=\,0,\qquad  0\leqslant s\leqslant T\,.
    \end{equation*}
It is recommended to compare (\ref{W_T_int}) with
(\ref{int_control}).
\smallskip

As it easily follows from (\ref{W_T_int}), $W^T$ is an isomorphism
from $\mathscr F^T$ on $\mathscr H^T$ and, moreover, the relation
 \begin{equation}\label{W^T FTxi=HTxi}
    W^T{\mathscr F}^{T,\xi}\,=\,\mathscr H^\xi\,,\qquad 0\leqslant \xi\leqslant T
    \end{equation}
holds. Also, by standard arguments of the theory of 2nd-order
Volterra integral equations, for $y\in\mathscr H^T$ one has
   \begin{equation}\label{W_T-1}
    ([W^T]^{-1}y)(t)=y(T-t)-\int_0^tw^{-1}(t,s)\,y(T-s)\,ds,\qquad 0\leqslant t\leqslant T
    \end{equation}
with kernel $w^{-1}$, twice continuously differentiable for $0
\leqslant s < t \leqslant T$ obeying
    \begin{equation*}
    w^{-1}(0,s)\,=\,0,\qquad  0\leqslant s\leqslant T\,.
    \end{equation*}
\smallskip

\noindent$\bullet$\,\,\,Quite analogously,  the operator
$W^T_\flat:\mathscr{F}^T\to \mathscr H^T$,
    \begin{equation*}
    (W^T_\flat)(x):=(\mathcal{P}^{T,x}_\flat f)(T-x+0),\qquad
    x\in\Omega^T.
    \end{equation*}
possesses the same properties as $W^T$. Namely, the
representation:
    \begin{equation}\label{W_T_int flat}
    (W^T_\flat)(x)=f(T-x)+\int_x^T w_\flat(x,s)f(T-s)\,ds,\qquad x\in\Omega^T
    \end{equation}
holds with a kernel $w_\flat$, which is of the same smoothness as
$w$ and obeys $ w_\flat(0,s)\,=\,0,\quad  0\leqslant s\leqslant
T$. It is an isomorphism, which provides
 \begin{equation}\label{W flat F txi=H xi}
W^T_\flat{\mathscr F}^{T,\xi}=\mathscr H^\xi,\quad 0\leqslant
\xi\leqslant T\,.
 \end{equation}
Its inverse has the form
 \begin{equation*}
    ([W^T_\flat]^{-1}y)(t)=y(T-t)-\int_0^tw^{-1}_\flat(t,s)\,y(T-s)\,ds,\qquad 0\leqslant t\leqslant T
    \end{equation*}
with a kernel $w^{-1}_\flat$ obeying $w^{-1}_\flat(0,s)=0,\quad
0\leqslant s\leqslant T$.
\smallskip

\noindent$\bullet$\,\,\, Let $Y^{\xi}$ be (orthogonal) projector
in $\mathscr H^T$ on $\mathscr H^\xi$, which cuts off $\mathbb
R^N$-valued functions onto the segment $\Omega^\xi$:
    \begin{equation*}
    Y^\xi y=
    \begin{cases}
    y, & \text{in}\,\,\Omega^\xi\\
    0,    & \text{in}\,\,\Omega^T\setminus\Omega^\xi
    \end{cases}\,\,.
    \end{equation*}
    \begin{Lemma}\label{lemma 3}
For every $0<\xi\leqslant T$ the relation
        \begin{equation}\label{plexus}
        W^T\mathcal{P^\xi}=Y^\xi W^T; \qquad
        W^T_{{\flat}}\mathcal{P^\xi}_\flat=Y^\xi W^T_{{\flat}}.
        \end{equation}
holds.
    \end{Lemma}
    \begin{proof} We use two facts:

1) since ${\mathscr F}^{T, \xi}\subset{\mathscr F}^{T, \xi'}$ for
$\xi<\xi'$, the projectors satisfy ${\mathcal P}^{T,
\xi}<{\mathcal P}^{T, \xi'}$, which implies
        $$
        \mathcal P^{T,x}\,\mathcal P^{T,\xi}\,=\,
        \begin{cases}
        \mathcal P^{T,x} & \text{for}\,\,\,x<\xi\\
        \mathcal P^{T,\xi} & \text{for}\,\,\,x>\xi
        \end{cases}\,;
        $$

2) if $f\in\mathscr F^T$, then $\mathcal P^{T,\xi} f\in{\mathscr
F}^{T,\xi}$; hence  ${\rm supp\,}\mathcal P^{T,\xi}
f\subset[T-\xi,T]$ and, therefore, $(\mathcal P^{T,\xi}
f)(T-x-0)=0$ for $x>\xi$.
        \smallskip

As a consequence, according to the definition (\ref{W_T!}), we
have
        \begin{align*}
        & \left(W^T\mathcal P^{T,\xi} f\right)(x)\,=\\
        & =\,    \begin{cases}
        (\mathcal P^{T,x} \mathcal P^{T,\xi} f)(T-x-0)=(\mathcal P^{T,x} f)(T-x-0)=\left(W^T f\right)(x), & x<\xi\\
        (\mathcal P^{T,x} \mathcal P^{T,\xi} f)(T-x-0)=(\mathcal P^{T,\xi}
        f)(T-x-0)=0,
        & x>\xi
        \end{cases}\,\,=\\
        & =\,(Y^\xi W^T f)(x)\,.
        \end{align*}

The second equality in (\ref{plexus}) is proved in the same way.
    \end{proof}
    \smallskip

\noindent$\bullet$\,\,\,Here a relation, which connects the
operators $W^T,\,W^T_\flat$ and $C^T$, is established. In its
form, it duplicates the definition (\ref{connecting}). However, at
the moment, $W^T$ and $W^T_\flat$ are just some operators
constructed via the function $r$ and we do not claim that $C^T$ is
the connecting operator of some system $\alpha^T$. This remains to
be proved.
    \begin{Lemma}\label{lemma C=WW}
        The relation
        \begin{equation}\label{C_and_W}
        C^T\,=\,(W^T_{{\flat}})^* W^T\,
        \end{equation}
        holds.
    \end{Lemma}
    \begin{proof}
        ${\bf 1.}$\,\,\,Let us denote $A:=W^T[C^T]^{-1}(W^T_\flat)^*$ and verify equality
        \begin{equation}\label{AY=YA}
        AY^\xi\,=\,Y^\xi A\,.
        \end{equation}

Multiplying the first equality in (\ref{plexus}) on the right by
$[C^T]^{-1}(W^T_\flat)^*$ we have
        \begin{equation}\label{111}
        W^T\mathcal P^\xi\,\,[C^T]^{-1}(W^T_\flat)^*=Y^\xi
        W^T\,\,[C^T]^{-1}(W^T_\flat)^*=Y^\xi A
        \,.
        \end{equation}
In the second equality (\ref{plexus}), passing to the adjoint
operators, one has
$(\mathcal{P^\xi}_\flat)^*(W^T_{{\flat}})^*=(W^T_{{\flat}})^*Y^\xi$.
Multiplying both parts on the left by $W^T[C^T]^{-1}$, we obtain:
 \begin{equation}\label{222}
        W^T[C^T]^{-1}(\mathcal{P^\xi}_\flat)^*(W^T_{{\flat}})^*=W^T[C^T]^{-1}(W^T_{{\flat}})^*Y^\xi=AY^\xi
        \,.
 \end{equation}
In this way, we get
$$
Y^\xi A\overset{(\ref{111})}=W^T\mathcal
P^\xi\,\,[C^T]^{-1}(W^T_\flat)^*\overset{(\ref{plexus})}=
W^T[C^T]^{-1}(\mathcal{P^\xi}_\flat)^*(W^T_{{\flat}})^*\overset{(\ref{222})}=AY^\xi\,.
$$
So (\ref{AY=YA}) is valid.
\smallskip

${\bf 2.}$\,\,\,Representations (\ref{C^xi inverse}) (with
$\xi=T$), (\ref{W_T_int}) and (\ref{W_T_int flat}) easily imply
that the operator $A=W^T\,\,[C^T]^{-1}(W^T_\flat)^*$ has the form
        \begin{equation*}
        A=\mathbb I+K\,,
        \end{equation*}
where $K$ is a compact integral operator in $\mathscr H^T$. The
commutation (\ref{AY=YA}) leads to $KY^\xi=Y^\xi K$ and, then, to
$K^*Y^\xi=Y^\xi K^*$. As a result, we have
 $$
K^*KY^\xi=K^*Y^\xi K=Y^\xi K^*K,
 $$
so that a {\it self-adjoint} operator $K^*K$ commutes with the
family of projectors $\{Y^\xi\}_{0\leqslant \xi\leqslant T}$. By
the well-known arguments of the spectral theory, the latter is
possible if and only if $K^*K$ is the multiplication by a bounded
positive measurable matrix-function. However, since $K^*K$ is {\it
compact}, this is possible if and only if $K^*K=\mathbb O$, which
is equivalent to $K=\mathbb O$. Thus, we arrive at $A=\mathbb I$.
\smallskip

${\bf 3.}$\,\,\, By the definition of $A$, we have
        $$
        A\,=\,W^T[C^T]^{-1}(W^T_\flat)^*\,=\,\mathbb I\,.
        $$
Since $W^T$ and $W^T_\flat$ are isomorphisms, the latter leads to
(\ref{C_and_W}).
    \end{proof}

\subsubsection*{Operator $L$}

Recall that $\mathscr M^T\subset \mathscr F^T$ is the class of
$C^2$-smooth controls vanishing near $t=0$. Also, note that the
set $\mathscr M^T\cap \mathscr F^{T,\xi}$ is dense in $\mathscr
F^{T,\xi}$ for all positive $\xi\leqslant T$.

Focusing on (\ref{Wd^2=LW}), let us define operator in $\mathscr
H^T$:
    \begin{equation}\label{def L}
    L:=-W^T\,\frac{d^2}{dt^2}\,[W^T]^{-1}\,,\quad {\rm Dom\,}
    L=W^T\mathscr M^T\,.
    \end{equation}
Using representation (\ref{W_T_int}) of $W^T$ and smoothness of
$w$, it is easy to make sure that ${\rm Dom\,} L=W^T\mathscr
M^T=\{y\in C^2(\Omega^T;\mathbb R^N)\,|\,\,{\rm
supp\,}y\subset[0,T)\}$.

The following result shows that $L$ is a Sturm-Liouville operator.
    \begin{Lemma}\label{lemma L Sturm-Liouville}
The representation
\begin{equation}\label{L Sturm-Liouv}
L\,=\,-\,\frac{d^2}{dx^2}\,+\,V(x)
\end{equation}
holds with potential $V(x):=-2\,\frac{dw(x,x)}{dx}\in
C^1(\Omega^T; \mathbb M^N)$, where $w$ is the kernel of the
integral part of $W^T$ in (\ref{W_T_int}).
    \end{Lemma}
    \begin{proof}(sketch)

\noindent{$\bf 1$.}\,\,\, At first, an auxiliary relation is
derived. To simplify the notation, we use
$\dot{(...)}=\frac{d}{dt}$.

Let controls $f,g\in\mathscr M^T$ obey $f(T)=g(T)=0$. Then the
following equality holds:
        \begin{equation}\label{aux rel}
        (C^T\ddot{g},f)_{\mathscr F^T}\,=\,(C^Tg,\ddot{f})_{\mathscr F^T}\,.
        \end{equation}
It can be verified by integration by parts, with regard to the
boundary conditions imposed of the controls and a specific form
(\ref{ker_connecting}) (with $\xi=T$) of kernel of $C^T$.
        \smallskip

\noindent{$\bf 2$.}\,\,\, Show that the operator $L$ is {\it
local}, i.e. satisfies ${\rm supp\,}Ly\subset{\rm supp\,}y$.

Let $y\in{\rm Dom\,}L$ and ${\rm supp\,}y\subset\Omega^\xi$. Then,
due to (\ref{W^T FTxi=HTxi}), for $f:=[W^T]^{-1}y$ we have
$f\in\mathscr M^T\cap{\mathscr F}^{T,\xi}$ and, consequently,
$\ddot f\in{\mathscr F}^{T,\xi}$. Referring again to (\ref{W^T
FTxi=HTxi}), we get: $Ly=-W^T\ddot f\in\mathscr H^\xi$, which
means ${\rm supp\,}Ly\subset\Omega^\xi$. Thus, $ L $ does not
extend the support of functions to the {\it right}.

Let $y\in{\rm Dom\,}L$ and ${\rm
supp\,}y\subset\overline{\Omega^T\setminus\Omega^\xi}=[T-\xi,T]$.
Then for $f:=[W^T]^{-1}y\in\mathscr M^T$ we obtain $f(T)=y(0)=0$.
Let $g\in\mathscr M^T\cap{\mathscr F}^{T,\xi}$ and $g(T)=0$. Thus,
$f$ and $g$ satisfy the conditions, which provide (\ref{aux rel}).
Then we have:
        \begin{align*}
        & -(Ly,W^T_\flat g)_{\mathscr H^T}=-(LW^Tf,W^T_\flat g)_{\mathscr H^T}=(W^T\ddot
        f,W^T_\flat g)_{\mathscr H^T}\overset{(\ref{C_and_W})}=(C^T\ddot
        f,g)_{\mathscr F^T}\overset{(\ref{aux rel})}=\\
        & = (C^Tf,\ddot g)_{\mathscr F^T}= (y,W^T_\flat\ddot
        g)_{\mathscr H^T}=0\,,
        \end{align*}
because $\ddot g\in{\mathscr F}^{T,\xi}$, and therefore
$W^T_\flat\ddot g\in\mathscr H^\xi$, whereas $y\in\mathscr
H^T\ominus\mathscr H^\xi$ by assumption on its support. In the
meantime, the set $\{g\in{\mathscr F}^{T,\xi}\,|\,\,g(T)=0\}$ is
dense in ${\mathscr F}^{T,\xi}$. Owing to (\ref{W flat F txi=H
xi}), the images $W^T_\flat g$ constitute a dense set in $\mathscr
H^\xi$. Therefore, the established equality $(Ly,W^T_\flat
g)_{\mathscr H^T}=0$ implies $Ly\in\mathscr H^T\ominus\mathscr
H^\xi$. The latter is equivalent to ${\rm
supp\,}Ly\subset\overline{\Omega^T\setminus\Omega^\xi}$. As a
result, $L$ does not extend the support of functions  to the {\it
left}.

So, $L$ does not extend the support of functions, i.e., acts
locally.
\smallskip

\noindent{$\bf 3$.}\,\,\,Let us show that (\ref{L Sturm-Liouv})
does hold. By (\ref{W_T_int}), for $f\in\mathscr M^T$ one easily
derives
        \begin{align}
\notag  & (W^Tf)''(x)-(W^T\ddot
        f)(x)=\\
\notag  & =V(x)f(T-x)+\int_x^T\left[w_{xx}(x,s)-w_{ss}(x,s)\right]f(T-s)\,ds=\\
\label{calculus}        & =
        V(x)(W^Tf)(x)+\int_x^T\left[w_{xx}(x,s)-w_{ss}(x,s)-V(x)w(x,s)\right]f(T-s)\,ds
        \end{align}
where $(...)'=\frac{d}{dx}$ and $V:=-2\,\frac{dw(x,x)}{dx}$. Note
that all operations, which are applied in course of the derivation
(differentiation of integrals, integration by parts, etc) are
justified owing to $C^2$-smoothness of the kernels of the
integrals under consideration. Next, substituting $f=[W^T]^{-1}y$
and using (\ref{W_T-1}), the derived relation is transformed to
        \begin{equation}\label{L local}
        (Ly)(x)=-y''(x)+V(x)y(x)+\int_x^Tk(x,s)y(s)\,ds,\qquad
        x\in\Omega^T
        \end{equation}
with a continuous kernel $k$.
\smallskip

\noindent{$\bf 4$.}\,\,\,We omit a simple proof of the following
fact: an operator of the form (\ref{L local}) is {\it local} if
and only if the integral summand is absent. Thus, we arrive at
(\ref{L Sturm-Liouv}).
  \end{proof}

\subsubsection*{Operator $L_\flat$}

\noindent$\bullet$\,\,\,By the use of the same scheme, it is
established that the operator
    \begin{equation*}
    L_\flat:=-W^T_\flat\,\frac{d^2}{dt^2}\,[W^T_\flat]^{-1}\,,\quad
    {\rm Dom\,} L_\flat=W^T_\flat\mathscr M^T
    \end{equation*}
is of the form
    \begin{equation*}
    L_\flat\,=\,-\,\frac{d^2}{dx^2}\,+\,V_\flat(x)
    \end{equation*}
with potential $V_\flat(x):=-2\,\frac{dw_\flat(x,x)}{dx}\in
C^1(\Omega^T; \mathbb M^N)$, where $w_\flat$ is the kernel of the
integral part of $W^T_\flat$ in (\ref{W_T_int flat}).
    \smallskip

    \noindent$\bullet$\,\,\,
Let us show that operators $L$ and $L_\flat$ are adjoint by
d'Alembert, i.e., for $y,v\in C^\infty_0(\Omega^T;\mathbb R^N)$
the equality
    \begin{equation*}
    (Ly,v)_{\mathscr H^T}\,=\,(y,L_\flat v)_{\mathscr H^T}\,.
    \end{equation*}
is valid. Indeed, by the choice of $y$ and $v$, the controls
$f=[W^T]^{-1}y$ and $g=[W^T_\flat]^{-1}v$ vanish at $t=0$ and obey
$f(0)=g(0)=0$. Hence, we have:
    \begin{align*}
    & (Ly,v)_{\mathscr H^T}=(W^T\ddot f,W^T_\flat g)_{\mathscr H^T}=(C^T\ddot
    f,g)_{\mathscr F^T}\overset{(\ref{aux rel})}
    = (C^Tf,\ddot g)_{\mathscr F^T}=\\
    & =(W^T f,W^T_\flat \ddot g)_{\mathscr H^T}=(y,L_\flat v)_{\mathscr H^T}\,.
    \end{align*}
As a consequence, one easily concludes that the potentials are
connected by the equality
    \begin{equation*}
    V_\flat(x)=V^\flat(x),\qquad x\in\Omega^T\,.
    \end{equation*}

\subsubsection*{Completion of the proof of Theorem \ref{Th 1}}

The operator (\ref{L Sturm-Liouv}) determines a dynamical system
$\alpha^T$ of the form
    \begin{equation}\label{forward problem+}
    \begin{cases}
    u_{tt}+Lu=0, & x>0,\ 0<t<T\\
    u|_{t=0}=u_t|_{t=0}=0,& x\geqslant 0\\
    u_{x=0}=f, & 0\leqslant t\leqslant T.\\
    \end{cases}
    \end{equation}
As is seen from (\ref{def L}), the operator $W^T$ is the control
operator of this system.

Quite analogously, system $\alpha^T_\flat$ of the form
    \begin{equation*}
    \begin{cases}
    u_{tt}+L_\flat u=0, & x>0,\ 0<t<T\\
    u|_{t=0}=u_t|_{t=0}=0,& x\geqslant 0\\
    u_{x=0}=f, & 0\leqslant t\leqslant T\\
    \end{cases}
    \end{equation*}
is controlled by the operator $W^T_\flat$.
\smallskip

As it follows from (\ref{C_and_W}), the connecting operator of the
system (\ref{forward problem+}) defined by (\ref{connecting}) {\it
coincides} with the operator $C^T$ introduced by
(\ref{int_connecting xi+}) (for $\xi=T$). Therefore, the integral
parts of these operators also coincide. The latter obviously
implies that the response matrix-function of the system
(\ref{forward problem+}) is identical to the function
$r|_{0\leqslant t\leqslant 2T}$, with which our considerations
have started.

Thus, $r|_{0\leqslant t\leqslant 2T}$ is the response function of
a dynamical system of the form (\ref{forward problem}). {\it The
sufficiency of the conditions of Theorem \ref{Th 1} is proved.}

\subsubsection*{Comments}

\noindent$\bullet$\,\,\, The deep connection between inverse
problems and the problem of triangular factorization of operators
is well known. It can be also traced in this work.

Recall the definitions. Let a monotone family ({\it nest}) of
subspaces $\mathfrak f=\{\mathscr F^\xi\}_{0\leqslant \xi\leqslant
T}:$ $\mathscr F^\xi\subset\mathscr F^{\xi'}$ for $\xi<\xi'$ be
given in a Hilbert space $\mathscr F$. An operator $Z$ is called
{\it triangular} with respect to this nest if $Z\mathscr
F^\xi\subset\mathscr F^\xi$, i.e. all the subspaces $\mathscr
F^\xi$ are invariant with respect to $Z$. We say that operators
$Z$ and $Z_\flat$, which are triangular with respect to $\mathfrak
f$, provide {\it triangular factorization} of an operator $C$ if
$C=Z_\flat^*Z$ holds.

In our paper, in the space $\mathscr F^T$, there is the nest of
the subspaces $\mathfrak f=\{{\mathscr F}^{T,\xi}\}_{0\leqslant
\xi\leqslant T}$. Let us introduce an isometry
    $$
I^T: \mathscr H^T\to\mathscr F^T, \quad (I^Ty)(t):=y(T-t), \qquad
0\leqslant t\leqslant T
    $$
and note that $(I^T)^*I^T=\mathbb I_{\mathscr F^T}$. Following
from (\ref{controllability}) and (\ref{controllability flat}),
operators $Z^T:=I^TW^T$ and $Z^T_\flat:=I^TW^T_\flat$ are
triangular with respect to $\mathfrak f$. According to
(\ref{connecting}), we have:
   \begin{equation}\label{C^T factor}
C^T=(W^T_\flat)^*W^T=(I^TW^T_\flat)^*I^TW^T\,=\,(Z^T_\flat)^*Z^T\,.
   \end{equation}
Consequently, the pair $Z^T,\,Z^T_\flat$ provides  triangular
factorization of the connecting operator of the system $\alpha^T$
with respect to the nest of subspaces, formed by delayed controls.

Thus, solving the inverse problem by the procedure ${\bf
A.}\!-\!{\bf C.}$ described in the end of the section \ref{Sec
Inverse problem}, we solve the triangular factorization problem
for the operator $C^T$ by (\ref{C^T factor}). These problems are
{\it equivalent}.

The general factorization problem for operators of the form
$\mathbb I+\text{compact}$\, is solved in \cite{GohbKrein}: see
Theorem 2.1, which provides the necessary and sufficient
conditions for its solvability. The conditions on the family of
operators $C^\xi$ adopted in our Theorem \ref{Th 1}, are quite
adequate to the mentioned classical ones.

Let us return to the question raised in the Introduction: why does
the operator $L$ given by (\ref{def L}) turn out to be {\it
local}? The explanation is in a very specific form of the kernel
of operator $C^T$: see (\ref{ker_connecting}). Such a specifics is
used, in particular, in the calculations (\ref{aux rel}) and
(\ref{calculus}).
\smallskip

\noindent$\bullet$\,\,\, A substantial difference, which
distinguishes the problem with a non-self-adjoint potential $V$
from the problem with $V^*=V$, is as follows. In the second case,
the connecting operator $C^T=(W^T)^*W^T$ is {\it positive
definite} and, hence, all the shortened operators $C^\xi$ turn out
to be such. Therefore, for characterization it suffices to require
only $C^T$ to be isomorphism: this implies isomorphism of all
$C^\xi$. In the general case, isomorphism of $C^T$ does not ensure
isomorphism of $C^\xi$. This is the mistake made in the statement
of the conditions of Theorem 3.2 in \cite{Avd Bel 96}.

There is a case when the isomorphism of all $C^\xi$ certainly
takes place. If $T>0$ is small, then the integral parts of the
operators $C^\xi$ have a small norm and all $C^\xi$ turn out to be
isomorphisms. With this reservation, the statement of Theorem 3.2
becomes true.
\smallskip

\noindent$\bullet$\,\,\,The scheme, which provides the data
characterization in this work, is traditional for the BC-method.
Its core is, first, to elaborate an efficient procedure, which
{\it solves} the inverse problem and, then, to provide the
conditions, which ensure its realizability. In one-dimensional
problems such a scheme works quite successfully: see \cite{B Pest,
BMikh Dirac IP}. There are certain results on the multidimensional
case but the list of the characteristic conditions turns out to be
rather long \cite{BV Rendiconti}.


TITLE: What are the rules for equals signs with big-O and little-o?
QUESTION [57 upvotes]: This question is about asymptotic notation in general. For simplicity I will use examples about big-O notation for function growth as $n\to\infty$ (seen in algorithmic complexity), but the issues that arise are the same for things like $\Omega$ and $\Theta$ growth as $n\to\infty$, or for little-o as $x\to 0$ (often seen in analysis), or any other combination.
The interaction between big-O notation and equals signs can be confusing. We write things like
$$\tag{1} 3n^2+4 = O(n^2)$$
$$\tag{2} 5n^2+7n = O(n^2)$$
But we're not allowed to conclude from these two statements that $3n^2+4=5n^2+7n$. Thus it seems that transitivity of equality fails when big-O is involved. Also, we never write things such as $$\tag{3} O(n^2)=3n^2+4,$$
so apparently commutativity is also at risk.
Many textbooks point this out and declare, with varying degrees of indignation, that notations such as $(1)$ and $(2)$ constitute an "abuse of notation" that students are just going to have to get used to. Very well, but then what are the rules that govern this abuse? Mathematicians seem to be able to communicate using it, so it can't be completely random.
One simple way out is to define that the notation $O(n^2)$ properly denotes the set of functions that grow at most quadratically, and that equations like $(1)$ are just conventional abbreviations for
$$\tag{4} (n\mapsto 3n^2+4)\in O(n^2)$$
Some authors even insist that writing $(1)$ is plain wrong, and that $(4)$ is the only correct way to express the estimate.
However, other authors blithely write things like
$$\tag{5} 5 + O(n) + O(n^2)\log(O(n^3)) = O(n^2\log n)$$
which does not seem to be easily interpretable in terms of sets of functions.
The question: How can we assign meaning to such statements in a principled way such that $(1)$, $(2)$ and $(4)$ are true but $(3)$ is not?

REPLY [33 votes]: My take on this notation agrees with David Speyer's comment. As Henning's answer notes, our answers are just different ways to look at the same thing. Often I resort to rules similar to his as the operative definition, but I find the my approach easier to motivate.
We proceed in two steps: (a.) understanding an expression involving asymptotic notation, and (b.) understanding the use of the equals sign in this notation.

Rule for Interpreting Expressions. Every (well-formed) expression involving standard functions and operations (e..g, ${ +, \times, -, \div, \exp, \log }$) and asymptotic notations $\{ O, o, \Omega, \omega, \Theta\}$ corresponds to a set of functions. [For simplicity, we will restrict ourselves to only the $O$ notation.] This set is built recursively exactly as one would expect:
$$
\begin{align*}
E_1 \circ E_2 &:= \{ f(n) \circ g(n) \quad : \quad f(n) \in E_1, g(n) = E_2 \}, \quad \circ \in \{ +, \times, -, \div \}; \\
\Psi (E) &:= \{ \Psi(f(n)) \quad : \quad f(n) \in E \}, \quad \Psi \in \{ \exp, \log \}. \\
\end{align*}
$$
This interpretation of expressions is perfectly natural; it's analogous to the Minkowski sum of two sets, extended for more general operations. We can even enrich this with a slightly more involved rule for $O$:

$$
O(E) := \bigcup_{f(n) \in E} O(f(n)).
$$

These rules are not complete; one needs to append the appropriate base cases when $E$, $E_1$ and $E_2$ are single functions rather than a set of functions. The most interesting base case is the expression $O(f(n))$ which is defined exactly as in the post. As a final point, we can agree to identity a single function $f(n)$ with the set $\{ f(n) \}$; this turns out to be very convenient in practice.
For example, an expression of the form  $5 + O(n) + O(n^2)\log(O(n^3))$ stands for the set
$$
\{  5 + f(n) + g(n) \log h(n) \ : \ f(n) \in O(n), \quad g(n) \in O(n^2), \quad h(n) \in O(n^3)  \}.
$$
Similarly we can interpret the expression like $O(2^{n^2 + O(n)})$ by applying the $O(\cdot)$ rule twice.

Rules for Interpreting the Equals sign. When one asserts that $E_1 = E_2$ where $E_1$ and $E_2$ are sets represented by expressions like the above, one should always interpret it to mean that $E_1 \subseteq E_2$. E.g., $$5 + O(n) + O(n^2)\log(O(n^3)) \ \color{Red}{=} \ O(n^2\log n)$$ is really a shorthand for $$5 + O(n) + O(n^2)\log(O(n^3)) \ \color{Red}{\subseteq} \ O(n^2\log n) .$$
In addition, there is the case $f(n) = E$; e.g., $n = O(n^2)$. In this case, we can identity the function $f(n)$ with the set $\{ f(n) \}$ and apply the above interpretation. This tells us that $f(n) = E$ is the same as saying $f(n) \in E$ (because $f(n) \in E \iff \lbrace f(n) \rbrace \subseteq E$).
This is arguably unnatural since this clashes starkly with the standard interpretation of the equals sign as (set) equality. In fact, this is an inherent difficulty since we would expect any reasonable definition of equality to be symmetric:
$$
E_1 = E_2 \quad \stackrel{\color{Red}{(??)}}{\implies} \quad E_2 = E_1.
$$
However, as we all know, this is seldom true with the asymptotic notation. Thus the only way out seems to be to override the intuitive notion of equality in favor of a less natural one.  [At this stage, it is worth pointing out that Henning's rules also resorts to redefining the equals sign suitably.]

A sample of properties. Many commonly used rules for manipulating asymptotic notation follow directly from the above interpretation. As a case study, I consider some of the properties already studied by Henning in his answer:

"Local scope" or Change of meaning. For example, In $O(n) + O(n) = O(n)$, you can substitute distinct functions $f(n)$, $g(n)$ and $h(n)$. The definition of "$+$" in the set-of-functions interpretation is clearly based on this idea.
The asymptotic notation is not symmetric. E.g., $O(n) = O(n^2)$ whereas $n^2 \stackrel{\color{Red}{?}}{=} O(n)$ is false. This is for the same reason that set inclusion is not.
However it is transitive; i.e., if $E_1 = E_2$ and $E_2 = E_3$, then $E_1 = E_3$. This simply follows from the transitivity of set inclusion.

Final words. One main complaint against the asymptotic notation seems to be that it is usually not symmetric as is implied by the equals sign. This is legitimate, but in this case, the real issue is with the abuse of equals sign, rather than the functions-as-sets idea. In fact, as far as I remember, I am yet to come across a single use of the asymptotic notation that is technically wrong even after one mentally replaces the equals sign with either $\in$ or $\subseteq$ as appropriate.


TITLE: How is Hausdorff Distance sensitive to position?
QUESTION [2 upvotes]: I am working on my final year M.Tech. project. It involves using Hausdorff Distance to compare images. In the process of understanding it, I stumbled upon this  website  which states that Hausdorff Distance is sensitive to position. I have refered several papers and articles but unable to understand how this is possible. Can someone please explain it to me or atleast point me towards a link that will help me to understand this.
Thank you

REPLY [2 votes]: Compare figures 1 and 2. They depict two triangles such that the shortest distance between them is the same. However, qualitatively, the two triangles in figure 2 appear closer than the two triangles in figure 1. This is what the website calls the insensitivity of the shortest distance metric to position (the way the shapes are posed in the ambient space).
Now look at figures 4 and 5. Figure 4 depicts the same triangles as in figure 1, and figure 5 depicts the same triangles as in figure 2. Now, what is computed is the Hausdorff distance instead of the shortest distance. It is now seen that the Hausdorff distance between the triangles in figure 4 is larger than for those in figure 5. Thus, it is seen that the Hausdorff distance captures the initial intuition that the triangles in figure 5 are indeed closer.
This property, that the Hausdorff distance considers the position (again, the way the shapes are posed in the ambience), is what the website calls the sensitivity of the Hausdorff distance to position.
I'm not sure this terminology is very illuminating. I would say something along the lines of "the Hausdorff distance is sensitive to the global positioning of the two sets, and not just to the local distances".
A more straightforward example would be in $\mathbb R$. Consider $A=[0,1]$ and $B=[2,3]$. The shortest distance metric between $A$ and $B$ is $1$. The Hausdorff distance between $A$ and $B$ is 2. Now, consider $B'=[2,100]$. The shortest distance between $A$ and $B'$ did not change, it's still $1$. But the Hausdorff distance is between $A$ and $B'$ is now $99$. The shortest distance metric is blind to the global relative positioning of the two shapes, but the Hausdorff distance picks it up.


TITLE: Linear programming without use Gauss-Jordan row operations
QUESTION [0 upvotes]: I want some help for the following LP:
$$\begin{align}
\mbox{maximize} \quad& 24 x_1 + 22 x_2 + 45 x_3 \\
\mbox{subject to} \quad& 2x_1+x_2+3x_3 \leq 42 \\
& 2x_1 + x_2 + 2x_3 \leq 40 \\
& x_1 + \tfrac{1}{2}x_2 + x_3 \leq 45 \\
& x_1, x_2, x_3, x_4 \geq 0 \\
\end{align}$$
The above problem has to be solved by inspection without use the Gauss-Jordan rows operations.

REPLY [0 votes]: Note that

$x_4$ can be thrown away.
The third constraint multiplied by two $2x_1 + x_2 + 2x_3 \le 90$ is redudant due to the second constraint $2x_1 + x_2 + 2x_3 \le 40$.

So the original LP is actually
\begin{align}
\max \quad& 24 x_1 + 22 x_2 + 45 x_3 \\
\mbox{s.t.} \quad& 2x_1+x_2+3x_3 \leq 42 \tag{#}\label{OP}\\
& 2x_1 + x_2 + 2x_3 \leq 40 \\
& x_1, x_2, x_3 \geq 0 \\
\end{align}
By adding slack variables $s_1,s_2$ to the LP, we have
\begin{align}
\max z= \quad& 24 x_1 + 22 x_2 + 45 x_3 \tag{$\star$}\label{z1} \\
\text{s.t.} \quad& 2x_1+x_2+3x_3+s_1 = 42 \tag{1}\label{c11} \\
& 2x_1 + x_2 + 2x_3+s_2 = 40 \tag{2}\label{c12} \\
& x_1, x_2, x_3, s_1, s_2 \geq 0 \tag{FC}\label{fc}
\end{align}
Since the question asks us to solve this LP by inspection, we start from the most obvious feasible solution to \eqref{c11} and \eqref{c12}: $(x_1,x_2,x_3)=(0,0,0)$.
We can regard $z$ in \eqref{z1} as a linear function of $x_1,x_2$ and $x_3$ "around the origin $(0,0,0)$".  (More rigourously, $z$ is a linear function from $\Bbb R^3$ to $\Bbb R$ restricted to a neighbourhood around the origin.)  This is because we can make $s_i$ the subject of constraint $(\rm i)$.
\begin{align}
\max z= \quad& 24 x_1 + 22 x_2 + 45 x_3 \tag{$\star$} \\
\text{s.t.} \quad& s_1 = 42 - (2x_1+x_2+3x_3) \tag{1'}\label{f11} \\
& s_2 = 40 - (2x_1 + x_2 + 2x_3) \tag{2'}\label{f12} \\
& x_1, x_2, x_3, s_1, s_2 \geq 0 \tag{FC}
\end{align}
When $x_i$'s change, we can adjust $s_j$'s according to \eqref{f11} and \eqref{f12} so that \eqref{c11} and \eqref{c12} are satisfied as long as $x_i$'s aren't too large.
From \eqref{z1}, it's natural to consider increasing $x_3$ so as to increase $z$.  \eqref{c11} and \eqref{c12} impliy $x_3 \le 42/3 = 14$ and $x_3 \le 40 /2 = 20$ respectively, so $x_3 \le 14$.  Check that $(x_1,x_2,x_3) = (0,0,14)$ verifies \eqref{OP}.
To look at the behavior of the function $z$ "around (0,0,14)", we make $x_3$ a variable depending on $x_1,x_2$ and $s_1$.
Make $x_3$ the subject of \eqref{c11}, and substitute it into $\eqref{z1}$. The objective function then becomes
\begin{align}
z =& 24x_1+22x_2+45(14-\frac23x_1-\frac13x_3-\frac13s_1) \\
=& 630 - 6x_1 + 7x_2 -15s_1 \tag{$\star'$} \label{z2}
\end{align}
By a similar reasoning, we can regard $z$ in \eqref{z2} as an affine function of $x_1,x_2$ and $s_1$.  Since it has a positive coefficient (7) of $x_2$, by increasing $x_2$.  So, we keep $x_2$ and $x_3$, and try to see how they depend on $x_1,s_1$ and $s_2$
$\eqref{c11}-\eqref{c12}: x_3 + s_1 - s_2 = 2$ so $$x_3 = 2 - s_1 + s_2.\tag{3}\label{x3}$$  Substitute \eqref{x3} into \eqref{c12}.
\begin{align}
2x_1 + x_2 + 2(2 - s_1 + s_2) + s_2 &= 40 \\
x_2 &= 36 - 2x_1 + 2s_1 - 3s_2 \tag{4}\label{x2}
\end{align}
Substitute the above equation into \eqref{z2}.
\begin{align}
z =& 630 - 6x_1 + 7x_2 -15s_1 \\
=& 630 - 6x_1 + 7(36 - 2x_1 + 2s_1 - 3s_2) - 15s_1 \\
=& 630 - 6x_1 + 252 - 14x_1 + 14s_1 - 21s_2 - 15s_1 \\
=& 882 - 20x_1 - s_1 - 21s_2 \tag{$\diamondsuit$}\label{z3} \\
\le& 882 \quad \text{due to \eqref{fc}}
\end{align}
We finally arrive at an expression for the objective function $z$ which contains no positive coefficients.  We set $x_1, s_1$ and $s_2$ to zero, and find the corresponding values of $x_2$ and $x_3$.
\begin{align}
x_3 \stackrel{\eqref{x3}}=& 2 \\
x_2 \stackrel{\eqref{x2}}=& 36
\end{align}
Hence, the optimal solution is $(x_1,x_2,x_3) = (0,36,2)$ and maximal value is 882.


TITLE: Determinant: Effect on changing entry in a matrix on Cofactor Expansion [GStrang 5.2.22]
QUESTION [0 upvotes]: I can't discern why $N_n = S_n - S_{n - 1}$ from the answer (I define these below).
I computed: $S_1 = 3, S_2 = 8$.
By cofactor expansion along the $3$rd column (WLOG, I could've picked row):
$S_3 = 1\cdot(-1)^{2 + 3} \begin{vmatrix}
    3 & 1 \\
    0 & 1 \\
    \end{vmatrix} + 3\cdot(-1)^{3 + 3}\begin{vmatrix}
    3 & 1 \\
    1 & 3 \\
    \end{vmatrix} = 21.$
Let $N$ be the $S_i$ with the change of the $(1, 1)$ entry to $2$.
Then $N_1 = |\color{#009900}{2}|, N_2 = 5 = S_2 - S_1.$
By cofactor expansion along the $3$rd column,
$N_3 = 1\cdot(-1)^{2 + 3} \begin{vmatrix}
    \color{#009900}{2} & 1 \\
    0 & 1 \\
    \end{vmatrix} + 3\cdot(-1)^{3 + 3}\begin{vmatrix}
    \color{#009900}{2} & 1 \\
    1 & 3 \\
    \end{vmatrix} = 13 = S_3 - S_2.$

REPLY [0 votes]: Consider $S_n$. Cofactor expand along the first row and notice that the $(1,1)$ cofactor is precisely $S_{n-1}$. That means we can write
$$S_n = 3S_{n-1} + \text{remaining terms}$$
where "remaining terms" are the other terms of the expansion (which do not really matter to us). Changing the $3$ to a $2$ will not affect the remaining terms of the expansion, so we get
$$\color{green}{N_n = 2S_{n-1} + \text{remaining terms (Same as those in $S_n$)}}$$
Now substitute $N_n$ into $S_n$:
$$S_n = S_{n-1} + \color{green}{2S_{n-1} + \text{remaining terms}}
\\ =  S_{n-1} + \color{green}{N_n}$$
The net effect of the change is to subtract $S_{n-1}$ from $S_n$. Therefore
$$N_n = S_n - S_{n-1}$$


TITLE: Are all embeddings of $D^n$ into $R^n$ ambiently homeomorphic?
QUESTION [0 upvotes]: To make the question more precise: let $i, j : D^n \to R^n$ be topological embeddings. Does there exist a topological automorphism $h : R^n \to R^n$ such that $h \circ i = j$?

REPLY [4 votes]: Yes if $n=1$ (easy).
Yes if $n=2$ (not easy: this follows from the Jordan–Schönflies theorem)
No if $n\ge 3$. The classical counterexample is the Alexander horned sphere. When filled in, it is homeomorphic to closed $3$-ball. However, the exterior is not simply connected and therefore is not homeomorphic to the exterior of the standard $3$-ball.


text:
\begin{document}

\def\Z{{\mathcal Z}}
\def\V{{\mathcal V}}
\def\F{{\mathcal F}}
\def\I{{\mathcal I}}
\def\U{{\mathcal U}}
\def\Iz{{\mathcal I_0}}
\def\H{{\mathcal H}}
\def\G{{\mathcal G}}
\def\Gp{{\mathcal {G'}}}
\def\Hp{{\mathcal {H'}}}
\def\R{{\mathcal R}}
\def\E{{\mathcal E}}

\def\Paths{{\mathcal P}}

\def\variety{Y}
\def\genvariety{\Z^{m,n}_{r,k}}
\def\basevar{\Z^{m,n}_2}

\def\LT{LT(J)}
\def\SC{\Delta_{\LT}}

\def\A{{\mathbf {A}}}

\def\del#1#2#3#4{\delta_{[#1,#2][#3,#4]}}
\def\eps#1#2#3#4{\epsilon_{[#1,#2][#3,#4]}}
\def\pho#1#2#3#4#5#6{\rho_{[#1,#2,#3][#4,#5,#6]}}
\def\lam#1#2#3#4#5#6{\lambda_{[#1,#2,#3][#4,#5,#6]}}
\def\sigh#1#2#3#4#5#6{\psi_{[#1,#2,#3][#4,#5,#6]}}

\def\mp{\marginpar}

\hfill To appear in \textit{Journal of Pure and Applied Algebra} \\

\title[Complex Associated to Jet Scheme of Determinantal Variety]{Initial Complex Associated to a Jet Scheme of a Determinantal Variety}
\author{Boyan Jonov}
\address{Dept. of Mathematics\\California State University
Northridge\\Northridge CA 91330\\U.S.A.\\Current address: Dept of Mathematics\\University of California Santa Barbara\\Santa Barbara CA 93106} \email{boyan@math.ucsb.edu}

\subjclass[2000]{Primary 13F55}

\keywords{Determinantal variety, Jet scheme, Stanley-Reisner complex,
Cohen-Macaulay}

\begin{abstract}
We show in this paper that the principal component of the first order jet scheme over
the classical determinantal variety of $m\times n$ matrices of rank at most
$1$ is arithmetically Cohen-Macaulay, by showing that an associated Stanley-Reisner simplicial complex is shellable.
\end{abstract}

\maketitle

\section{Introduction} \label{SecnIntro}

Let $F$ be an algebraically closed field and $\A_F^{k}$ the affine
space of dimension $k$ over $F$. By a \textsl{variety} in
$\A_F^{k}$ we will mean the zero set of a collection of
polynomials over $F$ in $k$ variables; in particular, our
varieties are not assumed irreducible. In \cite{KoSe1} and \cite{KoSe2}, Ko\v{s}ir
and Sethuraman had studied jet schemes over classical determinantal varieties, and
had described their components in a large number of cases. In particular, they had
shown  that the variety of first-order jets, or loosely the ``algebraic tangent
bundle,'' over the determinantal variety of $m\times n$ matrices ($m \le n$) of rank
at most
$1$ has two components when $m \ge 3$.  One component is simply the affine space
$\A_F^{mn}$ supported over the origin.  The other component, which is much more
interesting, is the closure of the set of
tangents at the nonsingular points of the base determinantal variety.  We denote
this component by $Y$, and refer to it as the \textsl{principal component.} (When
$m=2$, the variety of first-order jets is irreducible, and coincides with the
principal component $Y$.) The goal of this paper is to show that $Y$ is
arithmetically Cohen-Macaulay, i.e., its coordinate ring is Cohen-Macaulay.

Consider the truncated polynomial ring
$F[t]/(t^2)$, and let $X(t)=(f_{i,j}(t))_{i,j}$ be the generic $m\times n$ ($m \le n$)
matrix over this ring; thus, the $(i,j)$  entry of $X(t)$ is of the
form $ f_{i,j}(t) = x_{i,j} + y_{i,j} t $, where $1\le i \le m$, $1 \le j
\le n$, and $ x_{i,j}, y_{i,j}$ are variables.
Let $I$ be the ideal of $R = F[x_{i,j}, y_{i,j}]$, $1 \leq i \leq m, 1 \leq
j \leq n$, generated by the coefficients of powers of $t$ in each $2
\times 2$ minor of the generic matrix $X(t)$. Then the variety of first-order jets
over the $m\times n$ matrices ($m \le n$) of rank at most
$1$ is precisely the zero set of $I$.  Let $J$ be the ideal of the principal
component $Y$.  In \cite{KoSe2}, Ko\v{s}ir and Sethuraman showed that $I$ is
radical, and further, determined a Groebner basis for both $I$ and $J$ for the
graded reverse
lexicographical order using the following scheme: $ y_{1,1} >
y_{1,2}> \dots> y_{1,n} > y_{2,1} > \dots >y_{2,n}>\dots> y_{m,n}>
x_{1,1} > x_{1,2} > \dots> x_{1,n} > x_{2,1} > \dots >x_{2,n}>\dots>
x_{m,n} $ (see \cite[Theorem 2.4]{KoSe2},  \cite[Proposition 3.3]{KoSe2}, and also
\cite[Remark 2.2]{KoSe2}).

 It follows easily from the description in \cite[Theorem 2.4]{KoSe2} of the Groebner
basis $G$ of $J$ that the leading term ideal of $J$, $\LT := \langle lm(g); g\in G
\rangle$, is generated by the following family of monomials:

\begin{Proposition} \label{CorGBI0}
(Generators of $\LT$) The following families of monomials generate
$\LT$:  $A =\{x_{i,l}x_{j,k}\ |\ 1 \le i < j\le m,\ 1\le k < l\le
n\}$, $B = \{ x_{i,k}y_{j,l}\ |\ 1\le i < j \le m,\ 1\le k < l \le
n\}$, $C = \{x_{k,p}y_{j,q}y_{i,r}\ |\ 1 \le i < j \le k \le m,\ 1
\le p < q < r \le n\}$, $D = \{x_{i,r}y_{j,q}y_{k,p}\ |\ 1 \le i < j
< k \le m,\ 1 \le p < q \le r \le n\}$, and $E =
\{y_{i,r}y_{j,q}y_{k,p}\ |\ 1 \le i < j < k \le m,\ 1 \le p < q < r
\le n\}$.
\end{Proposition}

Since $\LT$ is generated by squarefree monomials

we can
construct the Stanley-Reisner complex $\SC$ of $\LT$: this is the
simplicial complex on vertices $\{x_{i,j},y_{i,j}\ |\ 1 \le i \le
m, 1 \le j \le n\}$ whose corresponding Stanley-Reisner ideal (see
\cite[Chap. 1]{MiSt} or \cite[Chap. 5]{BrHe}) is $\LT$.  The simplicial complex is
defined by the relation
 $x_{i_1,j_1}

\dots x_{i_k, j_k}
\dots x_{i_s, j_s}y_{i^{'}_1, j^{'}_1}

\dots y_{i^{'}_l, j^{'}_l}
\dots y_{i^{'}_t, j^{'}_t}$, $\ 1 \le i_k, i^{'}_l \le m, 1 \le j_k, j^{'}_l \le n$,
is a face of $\SC$ if, as a monomial, it does not belong to $\LT$.

We will enumerate all the facets of $\SC$ and we will describe an explicit ordering
of the facets which will show that $\SC$ is a shellable simplicial complex. By
standard results, shellability of $\SC$ allows us to conclude the following main
result of the paper (a result that has been independently obtained by Smith and Weyman  in \cite{SW} as well, using their geometric technique for computing syzygies):

\begin{Theorem} \label{Cohen-Macaulay}
The coordinate ring of $Y$, i.e., $R/J$, is Cohen-Macaulay.
\end{Theorem}

We wish to thank Professor Aldo Conca for some very valuable discussions
during the writing of the paper. We also wish to thank Professor Toma\v{z} Ko\v{s}ir  for being generous with his time and his encouragement. This paper constitutes our M.S. thesis
at California State University Northridge, and we wish to thank
Professor B.A. Sethuraman for suggesting this problem and for his
constant encouragement.

\section{Describing the Facets of $\SC$} \label{SecnElementsSC}

\begin{figure}[h]
\includegraphics[scale=0.35]{family2.pdf}
\caption{ \label{family2}}
\end{figure}

It would be helpful in what follows to visualize the structure of
the monomials in the families $A$, $B$, $C$, $D$, and $E$ as described in Proposition \ref{CorGBI0}. For this, see Figure \ref{family2}. In this paper, we will visualize a monomial as being positioned in a matrix, where each variable of the monomial is
located in the matrix's entry corresponding to the index of the
variable.

In this section, we will enumerate all facets of $\SC$.  First, some
notation: we will denote a facet $F$ of the simplicial complex $\SC$
by $F=F_{x}F_{y}$, where $F_{x}$ is a string composed of vertices
$x_{i,j}$'s and $F_{y}$ is a string composed of vertices
$y_{i,j}$'s.  We will view each of $F_x$ and $F_y$ as both strings of vertices
or monomials, depending on the context. Note that $F_{x}F_{y} \in
\SC$ if, as a monomial, $F_{x}F_{y}$ does not belong in the ideal
$\LT$ if and only if $F_{x}F_{y}$ is not divisible by the generators of $\LT$ (see Proposition \ref{CorGBI0}).

We will start by showing a relation between the facets
of $\SC$ and those of the corresponding simplicial complexes
arising from classical determinantal varieties.   We refer to the
excellent survey paper of Bruns and Conca \cite{BrCo}. In this
paper,  the authors consider the facets of $\Delta_t$: the
Stanley-Reisner complex attached to the ideal $LT(I_t)$, which is
generated by the leading terms of the $t\times t$ minors of the
generic $m\times n$ matrix $(w_{i,j})$. The order they use is one
in which the leading term of a minor is the main diagonal, and it
is known that the leading terms of the $t\times t$ minors generate
the ideal of leading terms of $I_t$.

 The key result for us is \cite[Prop.
6.4]{BrCo}, where they enumerate the facets of $\Delta_t$. This is
a purely combinatorial result that enumerates the maximal subsets
of $V = \{ w_{i,j}: i \leq m, j \leq n \}$ that intersect any
$t$-subset of $V$ arising from the diagonal of some $t\times t$
submatrix of $(w_{i,j})$ in at most $t-1$ places, and can be
applied by symmetry to enumerate the maximal subsets of $V$ that
intersect any $t$-subset of $V$ arising from the antidiagonal of
some $t\times t$ submatrix of $(w_{i,j})$ in at most $t-1$ places.
We quote this result as:
\begin{Proposition} \label{Prop_classical_facets}(\cite[Prop.
6.4]{BrCo}).  Let $I_t$ be the ideal of $F[\{w_{i,j}\}]$ generated
the $t\times t$ minors of the generic $m\times n$ matrix
$(w_{i,j})$.  Write $LT(I_t)$ for the ideal generated by the lead
terms of the $t\times t$ minors  with respect to the graded
reverse lexicographical order $w_{1,1} > w_{1,2} > \dots> w_{1,n}
> w_{2,1} > \dots
>w_{2,n}>\dots> w_{m,n}$.  Write $\Delta_t$ for the Stanley-Reisner
complex of $LT(I_t)$.  Then the facets of $\Delta_t$ correspond to
all families of non-intersecting paths from
$w_{1,1},w_{2,1},\dots,w_{t-1,1}$ to $w_{m,n},w_ {m,n-1},\dots w_{m,n-t+2}$.
\end{Proposition}
Here, a path from $w_{a,b}$ to $w_{c,d}$, given $a\le c$ and $b\le d$,
is a sequence of vertices starting at $w_{a,b}$ and ending
at $w_{c,d}$ where each vertex in the sequence is either one step to
the right or one step down from the previous vertex.  A
non-intersecting path of the kind described in the last line of the
proposition above is a union of paths from $w_{i,1}$ to $w_{m,n-i+1}$
whose pairwise intersection is empty.  (It is known that for
the graded reverse lexicographic order as well, the leading terms
of the $t\times t$ minors generate the ideal of leading terms of
$I_t$.)

We observe that the monomials in $A$ correspond to the generators
of $LT(I_2)$  and the monomials in $E$ correspond to the
generators of $LT(I_3)$ (with the order specified in Proposition \ref{Prop_classical_facets}). So, for a facet facet $F=F_{x}F_{y}$ of $\SC$,  we have that $F_x$ is not in $LT(I_2)$ and $F_y$ is not in $LT(I_3)$. Therefore, by Proposition \ref{Prop_classical_facets}, we can state the following lemma:

\begin{Lemma} \label{lemma_Fx and Fy subsets of classical case}
$F_x$ is a subset of a path from $x_{1,1}$ to $x_{m,n}$ and $F_y$
is a subset of a pair of non-intersecting paths from $y_{1,1}$,
$y_{2,1}$  to $y_{m,n}$, $y_{m,n-1}$
\end{Lemma}

We will continue by showing that for each facet $F=F_{x}F_{y}$ of $\SC$,
$F_{x}$ is a non-empty string that contains at least two $x$-vertices. It is straightforward to see that $x_{m,n}F$  can not be divisible by any of the generators of  $\LT$. Hence, maximality of $F$ implies that $x_{m,n}$ is already in $F$. The next lemma shows that, in addition to $x_{m,n}$, $F$ must contain another $x$-vertex.

\begin{Lemma} \label{other x's present}
Let $F$ be a facet of the simplicial complex $\SC$. Then $F$ must contain at least two $x$-vertices, one of which is $x_{m,n}$ .
\end{Lemma}

\begin{proof}
We already know that $F$ must have $x_{m,n}$. Suppose that it is the only $x$-vertex that $F$ has. Consider then $x_{m-1,n}F$. We can easily check then that $x_{m-1,n}F$ is not divisible by any of the monomials in $A$, $B$, $C$, $D$, or $E$ . So, $x_{m-1,n}F \in \SC$ and maximality of $F$ implies that $x_{m-1,n}$ must already be in $F$, a contradiction to the assumption that the only $x$-vertex that $F$ contains is $x_{m,n}$.
\end{proof}

\noindent\textsl{Notation:} Let $F=F_{x}F_{y}$ be any facet and recall that, by Lemma \ref{lemma_Fx and Fy subsets of classical case}, $F_x$ is a subset of a path from $x_{1,1}$ to $x_{m,n}$. Thus, for any two $x$-vertices in $F_x$, one is always to the north, west, or north-west of the other. Let  $\mu(F)$ denote the $x$-vertex that is furthest to north and furthest to the west of all other $x$-vertices in $F_x$.  Thus, $\mu(F) = x_{i,j}$ implies that $i \le c$ and $j\le d$ for all $x_{c,d}$ in $F_x$ (see Figure \ref{facet}). Notice that $\mu(F) \neq x_{m,n}$ (Lemma \ref{other x's present}).

The next lemma deals with the $F_y$ part of a facet $F$ and, in particular, the lemma lists some of the $y$-vertices that must be present in a given facet.

\begin{Lemma} \label{y's present}
Let $F=F_{x}F_{y}$ be a facet of the simplicial complex $\SC$ with $\mu(F) = x_{i,j}$. Then $F$ must contain $y_{i,n}$ and $y_{m,j}$.
\end{Lemma}

\begin{proof}

To prove that $F$ contains $y_{i,n}$, it suffices to show that $y_{i,n}F$ is not divisible by a monomial in $A$, $B$, $C$, $D$, or $E$. Maximality of $F$  would then imply that $y_{i,n}$ must be in $F$.

Obviously, $y_{i,n}F$ can not be divisible by a monomial in $A$.
Also, $y_{i,n}F$ can not be divisible by a monomial in $B$ because otherwise it is easy to see that $y_{i,n}$ would have to be to the south-east of $\mu(F) = x_{i,j}$ - a contradiction. If $y_{i,n}F$ were divisible by a monomial in $D$, then another straightforward verification shows that $y_{i,n}$ must in a row below $\mu(F) = x_{i,j}$, which is impossible.

Suppose that $y_{i,n}F$ is divisible by a monomial in $C$. Then,
there must be some $x_{c,d}$ and $y_{s,t}$ in $F$ such that
$x_{c,d}y_{s,t}y_{i,n}$ is in $C$ (recall Figure \ref{family2}). But then the only possible location of $y_{s,t}$ is to the south-east of $x_{i,j}$. However, $x_{i,j}y_{s,t}$ is in $B$ and in $F$ - a contradiction.

Finally, suppose that $y_{i,n}F$ is divisible by a monomial in
$E$. Then there must be some $y_{a,b}$ and $y_{c,d}$ in $F$ such
that $y_{i,n}y_{a,b}y_{c,d}$ is in $E$ (recall Figure \ref{family2}).
In particular, it must be the case that, say, $y_{c,d}$ is to the
south-west of $y_{a,b}$ which, in turn, is to the south-west of
$y_{i,n}$. But then either $x_{i,j}y_{a,b}$ is in $B$ or $x_{i,j}y_{c,d}y_{a,b}$ is in $D$ - a contradiction in both cases.

So, $y_{i,n}F$ is not divisible by a monomial in $A$, $B$, $C$,
$D$, or $E$ which implies, as argued above, that $F$ must contain
$y_{i,n}$. We can similarly show that $F$ must contain $y_{m,j}$
as well.
\end{proof}

Now we are ready to describe the structure of all facets of $\SC$.
The following notation will be useful in the next theorem: for a
given facet $F=F_{x}F_{y}$ with $\mu(F) = x_{i,j}$, consider the
following partition of the $y$-vertices based on the index
$(i,j)$: $R_1 = \{y_{s,t} \ | \ s \leq i, j < t \}$, $R_2 =
\{y_{s,t} \ | \ s \leq i, t \leq j \}$, $R_3 = \{y_{s,t} \ | \ i <
s, t \leq j\}$, $R_4 = \{y_{s,t} \ | \ i < s, j < t\}$ (see Figure
\ref{regions1}) .

\begin{figure}[h]
\includegraphics[scale=0.15]{regions1.pdf}
\caption{ \label{regions1}}
\end{figure}

\begin{Theorem} \label{facets}
Let $F=F_{x}F_{y}$ be a facet of the simplicial complex $\SC$ with $\mu(F) = x_{i,j}$.
Then $F_{x}$ is a path from $x_{i,j}$ to  $x_{m,n}$ and
$F_{y}$ is a family of non-intersecting paths from $y_{1,1}$, $y_{2,1}$ to $y_{i,n}$, $y_{m,j}$.
\end{Theorem}

\begin{proof}

We will first show that $F=F_{x}F_{y}$ as described in the theorem is indeed a valid facet of $\SC$. Then we will argue that any facet of $\SC$ must have that form.

Let $F=F_{x}F_{y}$ with $F_{x}$  a path from $x_{i,j}$ to  $x_{m,n}$ and $F_{y}$  a family of non-intersecting paths from $y_{1,1}$, $y_{2,1}$ to $y_{i,n}$, $y_{m,j}$ be given (see Figure \ref{facet}). We will first show that $F$ is a facet of $\SC$ , i.e. $F$ is not divisible by monomials in $A$, $B$, $C$, $D$, or $E$ and $F$ is maximal with respect to inclusion.

\begin{figure}[h]
\includegraphics[scale=0.30]{facet.pdf}
\caption{ \label{facet}}
\end{figure}

Obviously, $F$ is not divisible by monomials in $A$ and $E$. To see that $F$ is not divisible by monomials in $B$, $C$, and $D$, it is enough to notice that F doesn't contain a $y$-variable in $R_4$ or variables of the form $y_{c,d}$ and $y_{e,f}$ such that one is to the south-west of the other and both are entirely in $R_1$ or $R_3$.

Next, we will show that $F=F_{x}F_{y}$ is maximal with respect to inclusion by arguing that any vertex attached to $F$ would make the resulting monomial divisible by some monomial in $A$, $B$, $C$, $D$, or $E$ (i.e. that resulting monomial can not be a face in $\SC$). Recall that by Lemma \ref{lemma_Fx and Fy subsets of classical case} $F_x$ is a subset of a path from $x_{1,1}$ to $x_{m,n}$. So, if we attach a vertex $x_{a,b}$ to $F_x$, it has to be to the north, west or north-west of $x_{i,j}$. But notice that in this case either $x_{a,b}y_{m,j}$ or $x_{a,b}y_{i,n}$, or both, would be a monomial in $B$ when $i \neq m $, $j \neq n$ (in the cases $i=m$ or $j=n$, $x_{a,b}$ can also produce monomials in $C$ and $D$). So, no $x$-vertex can be attached to $F$. Recall also that $F_y$ is a subset of a pair non-intersecting paths from $y_{1,1}$, $y_{2,1}$  to $y_{m,n}$, $y_{m,n-1}$ (Lemma \ref{lemma_Fx and Fy subsets of classical case}). So, if we attach a vertex $y_{c,d}$ to $F_y$, then $y_{c,d}$ must be in one of those two non-intersecting paths. If $i \neq m$, $j \neq n$ (see Figure \ref{threecases}), then $y_{c,d}$ must be  in $R_4$, but then $x_{i,j}y_{c,d}$ would be in $B$. If $i = m$, then $y_{c,d}$ must be  in $R_1$ and in row $m$. But then $x_{i,j}y_{c,d}$ and some $y$-variable that is in the upper path of $F_y$ and in $R_1$ would produce a monomial in $C$. Finally, if $j = n$, then $y_{c,d}$ must be  in $R_3$ and in column $n$. But then $x_{i,j}y_{c,d}$ and some $y$-variable that is in the lower path of $F_y$ and in $R_3$ would produce a monomial in $D$. So, no $y$-vertex can be attached to $F$ either. Thus, $F$ is maximal.

\begin{figure}[h]
\includegraphics[scale=0.30]{threecases.pdf}
\caption{ \label{threecases}}
\end{figure}

Finally, we will show that any facet $f=f_{x}f_{y}$ of $\SC$ with $\mu(f) = x_{i,j}$ must be of the form described in the theorem. Since $f_x$ is a subset of  a path from $x_{1,1}$ to $x_{m,n}$ (by Lemma \ref{lemma_Fx and Fy subsets of classical case}), and since $\mu(f) = x_{i,j}$, then it follows that $f_x$ must actually be a subset of a path from $x_{i,j}$ to $x_{m,n}$.

Next, again by Lemma \ref{lemma_Fx and Fy subsets of classical case}, $f_y$ must be a subset of a pair of non-intersecting paths from $y_{1,1}$, $y_{2,1}$  to $y_{m,n}$, $y_{m,n-1}$. By Lemma \ref{y's present}, it follows that $f_y$ must also contain $y_{i,n}$ and $y_{m,j}$.

Now, if $i \neq m$, $j \neq n$ (see Figure  \ref{threecases}), $f_y$ can not contain $y$-vertices in $R_4$, because $x_{i,j}$ and any vertex in that region is a monomial in $B$. So, $f_y$ must be a subset of a family of two non-intersecting paths from $y_{1,1}$, $y_{2,1}$ to $y_{i,n}$, $y_{m,j}$. Next, suppose $i = m$ (see Figure \ref{threecases}). Since $f_y$ is a subset of a pair of non-intersecting paths from $y_{1,1}$, $y_{2,1}$  to $y_{m,n}$, $y_{m,n-1}$, it is straightforward to verify, using maximality of $f$, that $f_y$ must contain the $y$-variable of the upper $y$-path that is furthest to north-west in $R_1$, call it $y_{e,f}$. Also, notice that there should be no $y$-vertices in $f_y \cap R_1$ such that one is to the south-west of the other (otherwise $x_{m,j}$ and those two $y$-vertices would produce a monomial in $C$). Therefore, $f_y \cap R_1$ must actually be a subset of a facet in $\Delta_2$ on vertex set $R_1$, i.e. $f_y \cap R_1$ must be a subset of some path in $R_1$ starting in
  $y_{e,f}$ and ending at $y_{m,n}$ (recall Proposition \ref{Prop_classical_facets}). So, $f_y$ must be a subset of a family of two non-intersecting paths from $y_{1,1}$, $y_{2,1}$ to $y_{i,n}$, $y_{m,j}$, $i=m$. Finally, we conclude the same result for the case $j=n$ (see Figure \ref{threecases}) using similar arguments from the case $i=m$.

Finally, notice that $f=f_xf_y$  is actually a subset of a some facet $F$ as described in the theorem. Maximality of $f$ implies that it actually has to be one of those facets $F$.

\end{proof}

Knowing the structure of a facet $F = F_xF_y$ of the simplicial complex $\SC$, we can easily count the number of vertices that $F$ is composed of, so we can determine $\dim F = |F|-1$. In particular, we see that the dimension of any facet $F$ is $2(m+n)-3$. Notice that the dimension of $F$ depends only on the constants $m$ and $n$. Thus, we can conclude that all facets of the simplicial complex $\SC$ have the same dimension, i.e. $\SC$ is a pure simplicial complex of dimension $2(m+n)-3$.

\begin{Corollary}
The dimension of $R/J$ is $2(m+n)-2$.
\end{Corollary}

Theorem \ref{facets} also allows to determine the total number of facets in $\SC$. Thus, we can determine the multiplicity of $R/J$ as well.

\begin{Corollary}
The multiplicity  of $R/J$ is given by

\begin{eqnarray}
 \sum \limits_{(i,j), (i,j) \neq (m,n)}   \binom{m+n-i-j}{m-i}     det \left(
\begin{array}{cc}
  \binom{i+n-2}{i-1}   &  \binom{m+j-2}{m-1} \\
  \binom{i+n-3}{i-2}   &  \binom{m+j-3}{m-2} \\
\end{array}
\right)
\end{eqnarray}

\end{Corollary}

\begin{proof}
The number of paths from $x_{i,j}$ to $x_{m,n}$ is $\binom{m+n-i-j}{m-i}$, while the number of non-intersecting paths from $y_{1,1}$, $y_{2,1}$  to $y_{i,n}$, $y_{m,j}$ is given by (see \cite[\S 2.2]{Krat2})
\begin{eqnarray}
det \left(
\begin{array}{cc}
  \binom{i+n-2}{i-1}   &  \binom{m+j-2}{m-1} \\
  \binom{i+n-3}{i-2}   &  \binom{m+j-3}{m-2} \\
\end{array}
\right) \nonumber
\end{eqnarray}

\end{proof}

\begin{Remark}
 Professor Sudhir Ghorpade (\cite{Ghor}) has shown that the expression for the multiplicity of $R/J$ above simplifies to ${{n+m-2}
\choose{m-1}}^2$ .
\end{Remark}

\section{Shellability of $\SC$} \label{SecnShellability}

The main goal of this section is to prove that our simplicial complex $\SC$ is shellable. Recall the following definition of shellability:

 \begin{Definition} \label{shellability_def}
 A simplicial complex $\Delta$ is \emph{shellable} if it is pure and if its facets can be given a total order, say $F_1$,$F_2$, $\dots$, $F_e$, so that the following condition holds: for all $i$ and $j$ with $1 \leq j < i \leq e$ there exists $v \in F_i \setminus F_j$ and an index $k$, $1 \leq k < i$, such that $F_i \setminus F_k = \{v\}$. A total order of the facets satisfying this condition is called \emph{shelling} of $\Delta$.
 \end{Definition}

 \begin{Theorem} \label{shellability_thm}
The simplicial complex $\SC$ is shellable.
 \end{Theorem}

 \begin{proof}
 Note that at the end of the previous section we have argued that $\SC$ is pure. We will proceed by first giving a partial order to the facets of $\SC$. Let $P=P_xP_y$ and $Q=Q_xQ_y$ be two facets of $\SC$. If $\mu(P)$ is in a row below $\mu(Q)$, we set $P<Q$ (see Figure \ref{partialorder}). If $\mu(P)$ and $\mu(Q)$ are in the same row, but $\mu(P)$ is to the right of $\mu(Q)$, we set $P<Q$ (see Figure \ref{partialorder}). If $\mu(P)=\mu(Q)$ but $P_x$ is to the right of $Q_x$ as one goes from $\mu(P)$ to $x_{m,n}$, then $P<Q$ (see Figure \ref{partialorder}). If $P_x = Q_x$ and the upper $y$-path of $P_y$ goes to the right of the upper $y$-path of $Q_y$, we set $P<Q$. Finally, if $P_x = Q_x$, the upper $y$-path of $P_y$ is the same as the upper $y$-path of $Q_y$ and the lower $y$-path of $P_y$ goes to the right of the lower $y$-path of $Q_y$, we set $P<Q$. Now we arbitrarily extend this partial order on the facets of $\SC$ to a total order.

\begin{figure}[h]
\includegraphics[scale=0.30]{partialorder.pdf}
\caption{ \label{partialorder}}
\end{figure}

 Now we will prove that the selected total order is indeed a shelling of $\SC$. Let $P=P_xP_y$ and $Q=Q_xQ_y$ be two facets of $\SC$ such that $P<Q$. Our goal is to find $v \in Q \setminus P$ and a facet $R < Q$ such that $Q \setminus R = \{v\}$.   Suppose that $\mu(P) \neq \mu(Q)$. Notice $P$ can not contain $\mu(Q) = x_{i,j}$ (otherwise $P<Q$ is contradicted). Take $v = x_{i,j}$. Take $R=R_xR_y$ to be the following: $R_x =  Q_x \setminus x_{i,j}$ and $R_y = Q_yy_{m,j+1}$ if $\mu(R) = x_{i,j+1}$ or $R_y = Q_yy_{i+1,n}$ if $\mu(R) = x_{i+1,j}$. In the special case $\mu(Q) = x_{m-1,n}$,  take $R_x = x_{m,n-1}x_{m,n}$, $R_y = Q_y$.

Next, suppose that $\mu(P) = \mu(Q)$, but $P_x \neq Q_x$. Then, there must be a right turn $H = x_{a,b}$ in $Q_x$ that is not in $P_x$ or else $Q_x$ would be to the right of $P_x$, contradicting $P<Q$. So, in this case take $v = H=x_{a,b}$ and $R=R_xR_y$ where $R_x = Q_x$ with $H=x_{a,b}$ replaced by $x_{a+1,b-1}$ and $R_y=Q_y$.

Next, suppose that $P_x = Q_x$ and the upper $y$-paths of the two facets are different. Notice that the upper path of $Q_y$ can not be strictly on the right of the upper path of $P_y$ (otherwise $P<Q$ is contradicted). So, there must be a right turn $H = y_{c,d}$ of the upper path of $Q_y$ strictly on the left of the upper path of $P_y$. Thus, $H = y_{c,d}$ can not be in $P_y$. So, take $v = y_{c,d}$. If $y_{c+1,d-1}$ is not in the lower path of $Q_y$, let $R=R_xR_y$ be the following facet: $R_x = Q_x$ and $R_y = Q_y$ with $y_{c,d}$ replaced by $y_{c+1,d-1}$. If $y_{c+1,d-1}$ is in the lower path of $Q_y$ (see Figure \ref{doublecascade}), then notice that $y_{c+1,d-1}$ must be a right turn as well. Then take $R=R_xR_y$ to be the following facet: $R_x = Q_x$ and $R_y$ is obtained from $Q_y$ be removing $y_{c,d}$ and by adding $y_{c+2,d-2}$.

\begin{figure}[h]
\includegraphics[scale=0.20]{doublecascade.pdf}
\caption{ \label{doublecascade}}
\end{figure}

Finally, suppose that $P_x = Q_x$, the upper $y$-paths of the two facets are the same, but the lower $y$-paths are different. Similarly as in the previous paragraph, we see that there must be a right turn $H = y_{e,f}$ of the lower path of $Q_y$ strictly on the left of the lower path of $P_y$. Notice that $H = y_{e,f}$ can not be in the upper path of $P_y$ because it is the same as the upper path of $Q_y$. So, take $v = y_{e,f}$. Let $R=R_xR_y$ be the facet: $R_x = Q_x$ and $R_y = Q_y$ with $y_{e,f}$ replaced by $y_{e+1,f-1}$.

 \end{proof}

We are now in position to prove Theorem \ref{Cohen-Macaulay}, the main result of the paper:

\begin{proof}[Proof of Theorem \ref{Cohen-Macaulay}]
By standard
results, the ring $R/J$ is Cohen-Macaulay if the ring $R/\LT$ is
Cohen-Macaulay (see \cite[Corollary 8.31]{MiSt}.  By construction,
$R/\LT$ is precisely the Stanley-Reisner ring associated to $\SC$,
and since $\SC$ is shellable, $R/\LT$ will necessarily be
Cohen-Macaulay (see \cite[Theorem 5.1.13]{BrHe}).
\end{proof}

config: arxiv


TITLE: Diagonalization of elements of the symplectic algebra.
QUESTION [1 upvotes]: Let $A$ a symmetric positive definite real matrix of dimension $2n\times 2n$ and $J$ the standard symplectic matrix, with block representation
  \begin{gather}
J=
\begin{pmatrix}
0 & -I \\ I & 0
\end{pmatrix}
\end{gather}
  with $I$ diagonal matrix of order $n \times n$. Consider the product $U=JA$, then there exists a basis that diagonalizes $U$ and have only imaginary eigenvalues.

How can I prove that?

REPLY [3 votes]: It's simply because $JA$ is similar to $A^{1/2}JA^{1/2}$, which is skew-Hermitian.