text:
\begin{document}

\begin{frontmatter}

\title{State Estimation for a Class of Linear  Systems with Quadratic Output\thanksref{footnoteinfo}}

\thanks[footnoteinfo]{This research work is supported in part by NSERC-DG RGPIN-2020-04759, the SSF COIN project, the Swedish Research Council (VR), the Wallenberg AI, Autonomous Systems and Software Program
(WASP),  and the Knut och Alice Wallenberg foundation (KAW).}

\author[First]{Dionysios Theodosis}
\author[Second]{Soulaimane Berkane}
\author[Third]{Dimos V. Dimarogonas}

\address[First]{Dynamic Systems and Simulation Laboratory, School of Production Engineering and Management,
Technical University of Crete, Greece (e-mail: dtheodosis@dssl.tuc.gr).}
\address[Second]{D\'epartement   d'informatique   et   d'ing\'enierie, Universit\'e   du   Qu\'ebec   en   Outaouis,   Gatineau, Qu\'ebec,   Canada (e-mail: soulaimane.berkane@uqo.ca )}
\address[Third]{Division of Decision and Control Systems, School of Electrical Engineering and Computer Science, KTH Royal Institute of Technology, Sweden (e-mail: dimos@kth.se)}

\begin{abstract}
This paper deals with the problem of state estimation for  a class of linear time-invariant systems with quadratic output measurements. An immersion-type approach is presented that transforms the system into a state-affine system by adding a finite number of states to the original system. Under suitable persistence of excitation conditions on the input and its higher derivatives, global state estimation is exhibited by means of a Kalman-type observer. A numerical example is provided to illustrate the applicability of the proposed observer design for the problem of position and velocity estimation for a vehicle navigating in the $n-$dimensional Euclidean space using a single position range measurement.
\end{abstract}

\begin{keyword}
Observers, observability, state estimation, linear system, quadratic output.
\end{keyword}
\end{frontmatter}

\section{Introduction}

The aim of an observer is to provide an estimation of the running value of the system's internal
state using the input and output measurements. For linear systems, the observer synthesis is guaranteed through the observability property, namely, the determination of the initial state vector of the system from knowledge of the input and the corresponding output over an interval of time.  While observability is independent of the input for linear systems, this is not in general true for nonlinear systems and one needs to consider inputs that distinguish the states, namely,  inputs which generate different outputs, see \cite{HK77}.

Typically, the study of the observability of a nonlinear system is a local problem and can be characterized by the usual observability rank condition \cite{HK77}. However, this condition is not enough for the design of an observer since it tightly depends on the input. For such cases the design will be restricted to some appropriate classes of inputs, namely, regular or persistently exciting inputs, see for instance  \cite{B07}, \cite{BBH96}, \cite{BCC88}, \cite{GK01} and references therein. A well-known technique to design observers for nonlinear systems is the {\it immersion} approach where a nonlinear system is transformed into a state-affine system whose  dimension may be greater than the dimension of the initial system. Such methodologies have a long history. For instance,   \cite{FK83} presented a necessary and sufficient condition based on the observation space of the system. Another approach was considered in \cite{BS04} and \cite{J03} where the immersion was based on the solutions of a partial differential equation.  Another immersion-based technique was presented in \cite{BT07} for a wide class of (rank-observable) nonlinear
systems based on a high-gain design.

In this paper we consider systems with linear dynamics and   quadratic output measurements of the form \begin{align*}
&\dot{x}=Ax+Bu,\\
&y=\frac{1}{2}x^{\top}Cx,
\end{align*}
which is indeed a particular class of nonlinear systems. However, by restricting our attention to this class, our goal is to derive explicit conditions on the input $u$ that guarantee the design of an observer that is able to instantaneously estimate the state $x$ from the input and the (scalar) output measurement. First, through successive differentiation of the output, we extend the state of the system by a finite number of states which results in a new state-affine system with linear output.
Then, we exploit the structure of the new extended system to derive suitable Persistence of Excitation (PE) conditions for the input and its derivatives that establish uniform observability for the new system. Consequently, the design of an observer for the obtained (uniformly observable) system follows directly from well known Kalman-like estimators, \cite{BBH96}, \cite{B07}, \cite{HS17} or other suitable observers. Since we consider an extended system, the estimate of the state of the original system can be obtained without any online inversion of a diffeomorphism. Finally, the framework presented in this paper generalizes and includes as a special case other state augmentation techniques presented in \cite{BSO11},   \cite{PI17}, \cite{HS17}, which mainly dealt with single and double integrator systems.  It should be noted that due to the nonlinear output of the considered class of systems it is also possible to apply other techniques as in  \cite{CDG93}, \cite{GK01},  \cite{GHO92} which for suitable inputs exploit a local change of coordinates to transform the system into a canonical form or by applying Lyapunov techniques as in \cite{T90}. {However, in contrast to these nonlinear techniques, our proposed approach has the advantage of employing a linear Kalman-type observer which guarantees global convergence while we also characterize explicitly the class of inputs (through the PE conditions) that guarantee the uniform observability property necessary for the exponential convergence of the estimator.} Finally, certain algebraic conditions for the observability of such systems was also proposed in \cite{D71}  without characterizing the admissible inputs. It should also be noted that the control of systems with quadratic outputs was considered in \cite{Monte17}.

\section{Preliminaries}\label{sec:prel}

\subsection{Notations} Throughout this paper we adopt the following notation. $\mathbb{N}$ and $\mathbb{R}$ denote, respectively, the sets of natural and real numbers.
For a given vector or matrix $(\cdot)\in{\mathbb R}^{n}$, $(\cdot)^{\top}$ denotes its transpose.
We denote by $I_{n}$ the $n\times n$ identity matrix. A matrix $A\in\Rat{n\times n}$ is called nilpotent if there exists an integer $\kappa\leq n$ such that $A^{\kappa}=0$.  By $0$ we denote each of the following: the scalar zero, the zero vector or the zero matrix. Depending on the context, the notation will be clear unless otherwise specified.  For $n\times n$ symmetric matrices $W$ and $Q$, the notation $W>0$ ($W\ge0$) is used if $W$ is positive definite (semi-definite) and $W>Q$ ($W\ge Q$) if $W-Q>0$ ($W-Q\ge 0$). With $\det(A)$ we denote the determinant of a square matrix  $A$. The Lie derivative of the real-valued scalar function $h$ along the vector field $f$ is denoted by $L_fh(x):=(dh(x)/dx)f(x)$ and the iterated derivatives  are defined as  $L^i_fh(x)=L_fL^{i-1}_fh(x)$, $L^0_fh(x)=h(x)$.

\subsection{Observability and Observers for LTV systems}

We first recall some well-known definitions and results for the observability of an LTV system.  Consider a linear time-varying system
\begin{subequations}\label{sys:LTV}
    \begin{align}
        \dot{x}=&A(t)x+B(t)u\label{sys:LTV:dynamics}\\
        y=& C(t)x\label{sys:LTV:out}
    \end{align}
\end{subequations}
where $x\in\Rat{n}$ is the state, $u\in\Rat{p}$ is the input, and $y\in\Rat{m}$ is the output of the system. $A(t), B(t), C(t)$ are matrix-valued functions of appropriate dimensions. We assume that these functions are continuous and bounded on $[0, +\infty)$.
\begin{dfn}\label{dfn:1}
The LTV system \eqref{sys:LTV} is called observable on $[t_0,T]$ if any initial state $x(t_0)=x_0$ is uniquely determined by the input $u(t)$ and the output $y(t)$ for $t\in[t_0,T]$.  $\triangleleft$
\end{dfn}

\begin{thm}\label{thm:1} [\cite{Rugh96}]
System \eqref{sys:LTV} is observable on $[t_0,T]$ if and only if the matrix:
$$W(t_0,T):=\int_{t_0}^{T}\Phi^{\top}(s,t)C^{\top}(s)C(s)\Phi(s,t)ds$$ is invertible, where
$\Phi(t,s)$ is the transition matrix defined by $\frac{d}{dt}\Phi(t,s)=A(t)\Phi(t,s)$, $\Phi(t,t)=I_n$. The matrix $W$ is called the Observability Gramian of \eqref{sys:LTV}.  $\triangleleft$
\end{thm}

Define the observability matrix
\begin{equation*}
\mathcal{R}(t):=\left(\begin{matrix}
N_0(t)\\N_1(t)\\\vdots\\N_{n-1}(t)
\end{matrix}\right)
\end{equation*}
with $N_0(t)=C(t)$, $N_{i}(t)=N_{i-1}(t)A(t)+\dot{N}_{i-1}(t)$, $i=1,\ldots,n-1$.
\begin{thm}\label{thm:2} [\cite{Rugh96}, \cite{SM67}]
The system \eqref{sys:LTV} is  observable if   $\rank \mathcal{R}(\bar{t})=n$, for some $\bar{t}\in [t_0,T]$.  $\triangleleft$
\end{thm}
The characterization of observability for time-varying systems is ``tied'' to finite time intervals, see \cite{BPP10}, \cite{Rugh96}, \cite{SM67}, and, \cite{W65} for different observability concepts and definitions.  For the state estimation problem a stronger property is required:
\begin{dfn}\label{dfn:2} [\cite{B07}]
System \eqref{sys:LTV} or the pair $(A(t),C(t))$ is uniformly observable if there exist $\delta>0$, $\mu>0$ such that
\begin{equation}\label{obs:gramian}
\forall t\ge0\qquad W(t,t+\delta)\ge \mu I_n >0.  \triangleleft
\end{equation}
\end{dfn}

\begin{lemma}\label{lemma:Sca}
[\cite{Sc13}] Assume that there exists a positive integer $K$ such that the $k-$th derivative of $A$ (respectively $C$) is well defined and bounded up to $k=K$ (respectively up to $k=K+1$). If there exists a  matrix-valued function $\mathcal{O}(\cdot)$ of dimension $(\ell\times n)$, $\ell\ge1$, composed of row vectors of $N_1,\ldots,N_K$ such that for some strictly positive numbers $\bar{\delta},\bar{\mu}$ and $\forall t\ge0$
\begin{equation}\label{Sca}
 \int_t^{t+\bar{\delta}} \det( \mathcal{O}^{\top}(s)\mathcal{O}(s))ds\ge \bar{\mu}>0
\end{equation}
then system \eqref{sys:LTV} is uniformly observable. $\triangleleft$
\end{lemma}

A  Kalman-like observer for a uniformly observable LTV system \eqref{sys:LTV} is given in the following theorem:
\begin{thm}\label{Theorem:K:obs} [\cite{B07}]
If \eqref{sys:LTV} is uniformly  observable then there exists an observer of the form
$$\dot{\hat{x}}=A(t)\hat{x}+B(t)u+K(t)(y-C(t)\hat{x})$$
where
\begin{align*}
K(t)=&M(t)C^{\top}(t)W^{-1}\\
\dot{M}(t)=&A(t)M(t)+M(t)A^{\top}(t)\\&-M(t)C^{\top}(t)W^{-1}C(t)M(t) +V+\theta M(t)\\
M(0)=&M_0=M_0^{\top}>0,\,\,W=W^{\top}>0
\end{align*}
with $\theta>2||A(t)||$ for all $t\ge0$, or $V=V^{\top}>0$.  $\triangleleft$
\end{thm}

The boundedness assumption on $A(\cdot)$ and the uniform observability ensure that the solution $M(t)$ remains bounded for all times and the error $e:=\hat{x}-x$ between the state of the observer and the actual state decays exponentially to zero with the rate of convergence tuned by $\theta$ or $V$. For $\theta=0$ we obtain the usual Kalman observer; more details can be found in \cite{B07}.

\section{Problem formulation}
Consider the dynamical system
\begin{subequations}\label{sys:LTI}
    \begin{align}
        \dot{x}=&Ax+Bu\label{sys:LTI:dynamics}\\
        y=&\frac{1}{2}x^{\top}Cx \label{sys:LTI:out:q}
    \end{align}
\end{subequations}
where $x\in\mathbb{R}^n$ is the state, $u\in\Rat{p}$ is the input and $y\in\Rat{}$ is a scalar output. The constant matrices  $A\in\Rat{n\times n}$ and $B\in\Rat{n\times p}$ are arbitrary and, without loss of generality, the constant matrix $C\in\Rat{n\times n}$ is assumed symmetric. System \eqref{sys:LTI} is a linear time-invariant system with a single quadratic output and, thus, it is a special class of nonlinear systems. In contrast to classic linear systems, it is known that the observability of nonlinear systems depends usually on the input and is characterized locally. For instance, for the trivial system  $\dot{x}=0$, $y=x^2$, it is not possible to {\it distinguish} the initial conditions $x_0$ and $-x_0$ using only the output measurement. For certain nonzero input $u$, however, it is possible to distinguish all states of $\dot{x}=u$. Observability of nonlinear systems can be discussed using the notion of observation space where the observability rank condition can be used to study the so-called local weak observability around a given point, see \cite{HK77}, \cite{NS90}.

Notice that for zero inputs, the observation space is spanned by elements of the form $L_{f_0}^ih(x)$ with  $f_0(x)=Ax$ and $h(x)=\frac{1}{2}x^{\top}Cx$. In particular we have
\begin{align}
	L_{f_0}h(x)=&x^{\top}CAx=\frac{1}{2}x^{\top}(CA+A^{\top}C)x:=\frac{1}{2}x^{\top}C_1x\nonumber\\
	L^2_{f_0}h(x)=&x^{\top}C_1Ax=\frac{1}{2}x^{\top}(C_1A+A^{\top}C_1)x:=\frac{1}{2}x^{\top}C_2x\nonumber\\
	&\vdots\nonumber\\
	L^i_{f_0}h(x)=&\frac{1}{2}x^{\top}C_{i}x,\quad i\in\mathbb{N}\label{Lie:der}
\end{align}
where the matrices $C_i$ are defined recursively as follows
\begin{align}
    &\left\{\begin{array}{l}
      C_0= C, \\
        C_{i+1}= C_iA+A^{\top}C_i.\\
    \end{array}\right. \label{Ci}
\end{align}
Note that the matrix $C_i$, can be explicitly calculated using the following formula:
\begin{align}
    C_{i}=&\sum_{r=0}^i\binom{i}{r}{A^\top}^rCA^{i-r}\label{Ci:formula}
\end{align}
The proof of \eqref{Ci:formula} follows by simple induction; for completeness the proof can be found in the appendix.

In the subsequent sections, we will exploit the terms $L^{i}_{f_0}h(x)$   to augment the system \eqref{sys:LTI} with the additional states in order to bring the system in a new suitable form where an observer can be designed. Then, we will derive sufficient conditions for the admissible inputs that render the new extended time-varying system uniformly observable in the sense of Definition \ref{dfn:2}. To this end we start by our main assumption:

\begin{ass}\label{assumption:Cm}
  There exists $m\in\mathbb{N}$ with $C_{m}=0$.
\end{ass}
Assumption \ref{assumption:Cm} is the only restriction we impose on the class of systems considered. The motivation behind this assumption is to facilitate the augmentation of the system by a finite number of states. Roughly speaking, this assumption is equivalent to the fact that there exists $m\in\mathbb{N}$ such that the $m-$th derivative $y^{(m)}$ of the output is zero under zero input or, equivalently,  $y^{(m)}$ is a polynomial function of time when $u=0$.  Note that for $u=0$, the solution of the linear time-invariant system is given by
\begin{align}
    x(t)=\exp(At)x(0),
\end{align}
which implies that
\begin{align}
   y(t)=\frac{1}{2}x(0)^\top\exp(At)^{\top} C\exp(At)x(0).
\end{align}
For instance, it is clear that the output will be polynomial if the Taylor series defining the exponential matrix $\exp(At)$ is finite, i.e., when $A$ is nilpotent. This can also be seen  from \eqref{Ci:formula}, when $A^{k}=0$ then $C_{m}=0$ with $m=2k-1$. Also, when $A$ is skew-symmetric ($A=-A^{\top}$) and the matrices $A$, $C$ commute ($CA=AC$), one has $C_1=A^TC+CA=-CA+AC=0$, hence $m=1$ satisfies the assumption. The navigation example we provide in the simulation section also satisfies this assumption since the state matrix is nilpotent.
\section{State augmentation}
In this section, we proceed with the transformation of system  \eqref{sys:LTI} to an equivalent time-varying system when Assumption \ref{assumption:Cm} holds. We extend the state of the system   with $m$  additional states \begin{equation}\label{zi:state}
	z_i:=\frac{1}{2}x^{\top}C_ix  ,\,\,\,i=0,1,\cdots,(m-1).
\end{equation}
Then, since $C_{m}=0$, we have
\begin{align}\nonumber
\dot{z}_i=&\frac{1}{2}x^{\top}(A^{\top}C_i+C_iA)x+u^{\top}B^{\top}C_ix\\
=&z_{i+1}+ u^{\top}B^{\top}C_ix,\quad i=0,\ldots,(m-2),
\label{eq:dzi1}
\end{align}
and
\begin{equation}\label{eq:dzi2}
\dot{z}_{m-1}=u^{\top}B^{\top}C_{m-1}x,
\end{equation}
where the last equation holds due to Assumption \ref{assumption:Cm}.
Therefore, by defining the extended state as
\begin{equation}\label{ext:state:1}
z:=\left[\begin{matrix}
z_0&z_1& \cdots&z_{m-1}&x
\end{matrix}\right]^{\top}\in\mathbb{R}^{m+n}
\end{equation}
and in view of \eqref{sys:LTI} and \eqref{eq:dzi1}-\eqref{eq:dzi2}, the dynamics of the new variable $z$ are given by the following LTV system
\begin{subequations}\label{sys:noC:ext}
\begin{align}
\dot{z}=&\mathcal{A}(u)z+\mathcal{B}u\label{sys:noC:ext:s},\\
y=&\mathcal{C}z \label{sys:noC:ext:out},
\end{align}
\end{subequations}
where the matrices $\mathcal{A}(u)\in\mathbb{R}^{(m+n)\times(m+n)}$, $\mathcal{B}\in\mathbb{R}^{(m+n)\times p}$ and $\mathcal{C}\in\mathbb{R}^{1\times(m+n)}$ are given by
\begin{align}
\mathcal{A}(u):=&\left[\begin{matrix}
0&1&0&\cdots&0&u^{\top}B^{\top}C_0\\
0&0&1&\cdots&0&u^{\top}B^{\top}C_1\\
\vdots&\vdots&\vdots&\vdots&\vdots\\
0&0&0&\cdots&1&u^{\top}B^{\top}C_{m-2}\\
0&0&0&\cdots&0 &u^{\top}B^{\top}C_{m-1}\\
0_{n\times 1}&0_{n\times 1}&0_{n\times 1}&0_{n\times 1}&0_{n\times 1}&A
\end{matrix}\right]\label{matrix:Au:ext}\\
\mathcal{B}:=&\left[\begin{matrix}
0_{m\times p}\\B
\end{matrix}\right] \label{matrix:B:ext}\\
\mathcal{C}:=&\left[\begin{matrix}  \begin{matrix}
1&0&0&\cdots&0
\end{matrix}
&0_{1\times n}\end{matrix}\right]\label{matrix:Cu:ext}.
\end{align}
Notice that the new augmented system \eqref{sys:noC:ext:s} is a state affine system, \cite{BBH96}, which can also be considered as a LTV system for some fixed input function $u(t)$. We adopt the state-affine definition to emphasize the dependence on the input $u(\cdot)$ even if $u$ appears linearly in $\mathcal{A}$.
For state affine systems several Kalman-type observer designs have appeared in the literature, see for instance   \cite{BCC88}, \cite{B07}, \cite{BBH96}. Typically, the main property required to  use a Kalman-type observer is that of uniform observability. Therefore, to estimate the state of the extended system, it suffices to study the observability of the pair $(\mathcal{A}(u),\mathcal{C})$, see Section \ref{section:observability}.

\section{Uniform observability analysis}\label{section:observability}
In this section, we derive different sufficient conditions for the admissible inputs $u(\cdot)$ that render the system \eqref{sys:noC:ext} uniformly observable. Before we proceed, the following necessary condition is provided, which allows the input $u$ to directly affect the extended system and its observability properties.
\begin{prop}\label{prop:consistency}
If $u(t)\equiv 0$ for all times or $B^{\top}C_r=0$ for all $r\in\mathbb{N}$, then the pair $(\mathcal{A}(u),\mathcal{C})$ is not uniformly observable.
\end{prop}

\begin{pf}
Notice that for the cases $u\equiv0$ or $B^{\top}C_r=0$ for all $r\in\mathbb{N}$, the matrix $\mathcal{A}(u(t))=\mathcal{A}$ is constant. In that case, the pair $(\mathcal{A},\mathcal{C})$ in \eqref{matrix:Au:ext}, \eqref{matrix:Cu:ext} is not Kalman observable since the observability rank condition gives $\rank(\mathcal{C}^\top, \mathcal{A}^\top\mathcal{C}^\top,\cdots,\mathcal{A}^{{m+n-1}^\top}\mathcal{C}^\top)=m$. To prove this claim rewrite $\mathcal{A}$ in the following block structure
\begin{equation*}
\mathcal{A} =\begin{bmatrix}
S_m&0\\0&A
\end{bmatrix}
\end{equation*}
where $S_m\in\Rat{m\times m}$ is the standard shift matrix
\begin{align}\label{mat:shift}
S_m= \begin{bmatrix}
0&1&0&\ldots &0\\
0&0&1&\ldots &0\\
\vdots&\vdots&\vdots&\ddots &0\\
0&0&0&\ldots &1\\
0&\undermat{m-1}{0&0&\ldots &0}
\end{bmatrix}\\ \nonumber
\end{align}
Notice now that due to the triangular block structure we also have that
$$\mathcal{A}^j=\begin{bmatrix}
S_m^j&0\\0&A^j
\end{bmatrix}$$
Then, it follows by direct calculations that $\mathcal{C}\mathcal{A}=(0,1,0,\ldots,0)$, $\mathcal{C}\mathcal{A}^2=(0,0,1,\ldots,0)$, $\ldots,   \mathcal{C}\mathcal{A}^{m-1}=(0,0, \ldots,1,0)$ and hence $\rank(\mathcal{C}^\top, \mathcal{A}^\top\mathcal{C}^\top,\cdots,\mathcal{A}^{{m-1}^\top}\mathcal{C}^\top)=m$. Since $S_m$ is a shift matrix we also have that $S_m^m=0$. The latter in conjunction with \eqref{matrix:Cu:ext} implies that $\mathcal{C}\mathcal{A}^m=0$ and $\mathcal{C}\mathcal{A}^j=0$ for $j=m+1,\ldots,m+n-1$ which proves that the system is not rank observable.
\end{pf}

The state-transition matrix associated with \eqref{sys:noC:ext} is defined by \begin{equation}\label{mat:trans}
    \frac{d}{dt}\Phi(t,\tau)=\mathcal{A}(u(t))\Phi(t,\tau), \quad \Phi(\tau,\tau)=I_{m+n}.
\end{equation}
In general, calculating the transition matrix $\Phi(t,\tau)$ and verifying that the inequality $W(t,t+\delta)\ge \mu I$  holds is a tedious task, especially in our case where the state matrix $\mathcal{A}(u(t))$ depends on the input. However, we can exploit the block structure of \eqref{matrix:Au:ext} and simplify its representation. More specifically, rewrite $\mathcal{A}(u)$ in the following form
\begin{equation}\label{mat:Au:small}
\mathcal{A}(u(t))=\begin{bmatrix}
S_m&U(t)\\0&A
\end{bmatrix}
\end{equation}
where $S_m\in\Rat{m\times m}$ is  given by \eqref{mat:shift}
and $U:\RgeO\to\Rat{m\times n}$ is given by
\begin{equation}\label{mat:U}
U(t)=\begin{bmatrix}
u^{\top}(t)B^{\top}C_0\\
u^{\top}(t)B^{\top}C_1\\
\vdots\\
u^{\top}(t)B^{\top}C_{m-2}\\
u^{\top}(t)B^{\top}C_{m-1}\\
\end{bmatrix}.
\end{equation}
Notice that due to the structure of $\mathcal{A}(u(t))$ in \eqref{mat:Au:small} it follows from \eqref{mat:trans}, that the transition matrix has the following form:
\begin{equation}\label{transition:mat}
    \Phi(t,\tau)=\begin{bmatrix}
\Phi_{11}(t,\tau)&\Phi_{12}(t,\tau)\\
0&\Phi_{22}(t,\tau)
\end{bmatrix}
\end{equation}
with
\begin{align}
&\frac{d}{dt}\Phi_{11}(t,\tau)=S_m\Phi_{11}(t,\tau), \quad\Phi_{11}(\tau,\tau)=I_{m},\label{Phi:11:de}\\
&\frac{d}{dt}\Phi_{22}(t,\tau)=A\Phi_{22}(t,\tau), \quad \Phi_{22}(\tau,\tau)=I_{n},\label{Phi:22:de}
	\end{align}
and $\Phi_{12}(t,\tau)$ satisfying
\begin{equation}\label{Phi:12:de}
    \frac{d}{dt}\Phi_{12}(t,\tau)=S_m\Phi_{12}(t,\tau)+U(t)\Phi_{22}(t,\tau),\quad \Phi_{12}(\tau,\tau)=0.
\end{equation}
Since $S_m$ and $A$ are constant matrices, we have that
\begin{subequations}
	\begin{align}
	\Phi_{11}(t,\tau)=&\exp\{S_m(t-\tau)\},\label{Phi:11}\\
	\quad\Phi_{22}(t,\tau)=&\exp\{A(t-\tau)\}, \label{Phi:22}
	\end{align}
whereas $\Phi_{12}(\cdot,\cdot)$ has the following form
\begin{equation}\label{Phi:12}
\Phi_{12}(t,\tau)=\int_{\tau}^t\Phi_{11}(t,s)U(s)\Phi_{22}(s,\tau)ds.
\end{equation}
\end{subequations}
Indeed, $\Phi_{12}(\tau,\tau)=0$ and from \eqref{Phi:11:de} and the Leibniz integral rule we also have
\begin{align*}
    \frac{d}{dt}\Phi_{12}(t,\tau)=&\Phi_{11}(t,t)U(t)\Phi_{22}(t,\tau)\\&+\int_{\tau}^{t}\frac{d}{dt}\Phi_{11}(t,s)U(s)\Phi_{22}(s,\tau)ds\\
    =&S_m\int_{\tau}^{t}\Phi_{11}(t,s)U(s)\Phi_{22}(s,\tau)ds\\&+U(t)\Phi_{22}(t,\tau)\\
    =&S_m\Phi_{12}(t,\tau)+U(t)\Phi_{22}(t,\tau),
\end{align*}
so that \eqref{Phi:12:de} follows as well.
By defining $\mathcal{C}=(\mathcal{C}_m,0_{1\times n})$, with $\mathcal{C}_m=(1,0_{1\times m-1})$ and taking into account the observability condition in Definition \ref{dfn:2} and \eqref{matrix:Cu:ext}, we have that the Observability Gramian of the extended system \eqref{sys:noC:ext} is given by
	\begin{align}
	&W(t,t+\delta)=\nonumber\\
	&\int_t^{t+\delta}\begin{bmatrix}
	\Phi_{11}(s,t)^{\top}\\
	\Phi_{12}(s,t)^{\top}
	\end{bmatrix}
	\mathcal{C}_m^{\top}\mathcal{C}_m
	\begin{bmatrix}
	\Phi_{11}(s,t)&\Phi_{12}(s,t)
	\end{bmatrix}ds.
\label{obs:Gramian:ext}
	\end{align}
Notice that the Observability Gramian is expressed in terms of the matrices $S_m$, $A$ and $U(t)$ through the definitions of $\Phi_{11}(t,\tau)$, $\Phi_{22}(t,\tau)$ and $\Phi_{12}(t,\tau)$ above and does not require the derivatives of $u$ neither the evaluation of the usual Peano-Baker series, see \cite{Rugh96}. According to Theorem \ref{Theorem:K:obs}, to  design an observer for the time-varying system \eqref{sys:noC:ext}, we require   uniform observability, which guarantees the exponential convergence of the observer. Therefore, according to Definition \ref{dfn:2} it suffices to consider inputs $u$ for which the Observability Gramian \eqref{obs:Gramian:ext} of the extended system satisfies inequality \eqref{obs:gramian}, i.e., persistently exciting inputs, see \cite{B07}. The transition matrices $\Phi_{11}$ and $\Phi_{22}$ can be easily  computed from \eqref{Phi:11} and \eqref{Phi:22} since $S_m$ and $A$ are constant, however, verifying that the Observability Gramian in \eqref{obs:Gramian:ext}  satisfies inequality \eqref{obs:gramian} is  non-trivial.

Typically, to design a Kalman-type observer and guarantee its exponential convergence it is required that the control input $u(t)$ is bounded for all $t\ge0$ which also implies that $\mathcal{A}(u(t))$ is bounded, see Theorem \ref{Theorem:K:obs}. To derive more explicit uniform observability conditions, we further assume in this work that the higher derivatives of the inputs are bounded.
\begin{ass}\label{As:bounded:input}
	The input $u(t)$ is bounded and there exists  $\kappa\ge m$ such that the  derivatives $\dot{u}(t)$, $\ddot{u}(t),\cdots,  \overset{(\kappa)}{u}(t)$, are also bounded for all $t\ge0$.
\end{ass}

{The next result is based on Lemma \ref{lemma:Sca} and gives a sufficient Persistence of Excitation (PE) condition for the uniform observability of the extended system by exploiting row vectors of the observability matrix at the expense of sufficiently smooth input $u(\cdot)$ with bounded derivatives.}
\begin{prop}\label{PE:cond:2}
	Let $r_0=0$ and
		\begin{equation}\label{fun:r:2}
		r_{i+1}(t)=r_i(t)A+\dot{r}_i(t)+u^{\top}(t)B^{\top}C_{i},\,\,i=0,1,\ldots.
		\end{equation}
	and assume also that there exist positive constants $\delta$, $\mu$, $\kappa$ such that for all $t\ge0$ Assumption \ref{As:bounded:input} holds and the following condition is satisfied:
	\begin{align}
	\int_t^{t+\delta}\det\left(\sum_{i=m}^{\kappa}r_{i}^{\top}(s) r_{i}(s)\right)ds\ge\mu.	\label{uni:obs:2}
	\end{align}
	Then, the system \eqref{sys:noC:ext} is uniformly observable.
\end{prop}

\begin{pf}
	To show that \eqref{uni:obs:2} implies uniform observability of the system \eqref{sys:noC:ext}, we will exploit Lemma \ref{lemma:Sca}. Hence, as in the statement of Lemma \ref{lemma:Sca} we define the row vectors
	\begin{align}
    &N_0(t):=\mathcal{C}\nonumber\\
	&N_{i}(t):=N_{i-1}(t)\mathcal{A}(u(t))+\dot{N}_{i-1}(t),\,\,i=1,\ldots,\label{Ni}
	\end{align}
	In view of \eqref{matrix:Au:ext}-\eqref{matrix:Cu:ext} we obtain
	\begin{align*}
	N_0(t)=&\left[\begin{matrix}1&0&0&\cdots&0&0_{1\times n}\end{matrix}\right]\\
	N_1(t)=&\left[\begin{matrix}0&1&0&\cdots&0&r_1(t)\end{matrix}\right]\\
	\vdots&\\
	N_{m-1}(t)=&\left[\begin{matrix}0&0&0&\cdots&1&  r_{m-1}(t)\end{matrix}\right] \\
	N_{\kappa}(t)=&\left[\begin{matrix}0&0&0&\cdots&0&  r_{\kappa}(t)\end{matrix}\right],\,\,\,\kappa\ge m
	\end{align*}
	where  $r_i(\cdot)$, $i=1,\ldots,\kappa$ is a sequence of $1\times n$ vectors defined by \eqref{fun:r:2}.
	Now, consider the matrix $\mathcal{O}(t)=\left[\begin{matrix}
	N_0(t)^\top&N_1(t)^\top&\ldots&N_{\kappa}(t)^\top\end{matrix}\right]^{\top}$
	from which we obtain the $(m+n)\times(m+n)$ matrix
	\begin{align*}
	& \mathcal{O}(t)^{\top}\mathcal{O}(t)= \\
	&\left[
	\begin{matrix}
	1&0&0&\cdots&0 &0_{1\times n}\\
	0&1&0&\cdots&0 &r_1(t)\\
	0&0&1&\cdots&0 &r_2(t)\\
	\vdots&\vdots&\vdots&\cdots& \vdots&\vdots\\
	0&0&0&\cdots&1&r_{m-1}(t)\\
	0_{n\times 1}&r_1^{\top}(t)&r_2^{\top}(t)&\cdots &r_{m-1}^{\top}(t) &\sum_{i=1}^{\kappa}r_i^{\top}(t)r_i(t)
	\end{matrix}
	\right]
	\end{align*}
	By taking into account Assumption \ref{As:bounded:input}, it follows that $\mathcal{A}(u(\cdot))$ and its $\kappa$- derivatives are bounded and thus all assumptions of Lemma \ref{lemma:Sca} hold. Hence, to show the uniform observability of the system it suffices to show that \eqref{Sca} holds. Notice that for the matrix $\mathcal{O}(\cdot)^{\top}\mathcal{O}(\cdot)$ above we have by the Schur complement and its determinant  that
	\begin{align*}
	\det(\mathcal{O}^{\top}(t)\mathcal{O}(t))=& \det\left(\sum_{i=1}^{\kappa}r_i^{\top}(t)r_i(t)-\sum_{i=1}^{m-1}r_i^{\top}(t)r_i(t)\right)\\
	&=\det\left(\sum_{i=m}^{\kappa}r_i^{\top}(t)r_i(t)\right)
	\end{align*}
	Therefore, it follows that if condition \eqref{uni:obs:2} holds then also \eqref{Sca} is satisfied and from Lemma \ref{lemma:Sca} we conclude that the system \eqref{sys:noC:ext} is  uniformly observable. \qed
\end{pf}

{Notice that condition \eqref{uni:obs:2} requires a sufficiently smooth and bounded input as there is no restriction on how large the constant $\kappa$ may be. In particular, $\kappa$ must be at least greater or equal to $m+1$ since $\det(r_m^\top(s) r_m(s))=0$.  In the following material, we will derive PE conditions that require less number of derivatives. The first proposition below provides a PE condition for the admissible inputs and their derivatives and is equivalent to the uniform observability of the pair $(A,r_m(t))$, where $r_m(\cdot)$ is defined in \eqref{fun:r:2}.}
\begin{prop}\label{PE:cond:3}
	Suppose that Assumption \ref{assumption:Cm} holds and in addition Assumption \ref{As:bounded:input} is satisfied with $\kappa=m$. Then, the system \eqref{sys:noC:ext} is uniformly observable if there exist positive constants $\bar{\delta}$ and $\bar{\mu}$ such that for all $t\ge0$ we have
		\begin{align}
		\int_t^{t+\bar{\delta}}\Phi_{22}^{\top}(s,t)r_m^{\top}(s) r_m(s)\Phi_{22}(s,t)ds\ge\bar{\mu} I_n.	\label{uni:obs:3}
		\end{align}
\end{prop}

\begin{pf}
To show that the system \eqref{sys:noC:ext} is uniformly observable, it suffices to show that there exist $\delta$, $\mu>0$ such that \eqref{obs:gramian} holds, i.e., $W(t,t+\delta)>\mu I_{m+n}$, for all $t\ge0$ with $W(t,t+\delta)$ given by \eqref{obs:Gramian:ext}.
We proceed by contradiction. Suppose that for every $\mu>0$ and $\delta>0$ there exists $t\ge0$ with $W(t,t+\delta)<\mu I_{m+n}$. Consider a sequence $\{\mu_p\}_{p\in\mathbb{N}}$ that converges to zero  with $\mu_p>0$ and $\delta=\bar{\delta}>0$, with $\bar{\delta}$ satisfying the PE condition \eqref{uni:obs:3}.  Then, there exists a sequence of times $\{t_p\}_{p\in\mathbb{N}}$ and a sequence $\{\hat{d}_p\}_{p\in\mathbb{N}}$ with $\hat{d}_p\in D=\{d\in\mathbb{R}^{m+n}:||{d}||=1\}$ such that, for all $p\in\mathbb{N}$, $\hat{d}_p^\top W(t_p,t_p+\bar{\delta})\hat{d}_p<\mu_p$. Next, consider a sub-sequence of $\{\hat{d}_p\}_{p\in\mathbb{N}}$ which converges to some $d\in D$, since $D$ is compact. Let
$d=(d_1^{\top},d_2^{\top})^{\top}\in\Rat{m+n}$ with $d_1=(d_{11},d_{12},\ldots,d_{1m})^{\top}\in\Rat{m}$, $d_2=(d_{21},d_{22},\ldots,d_{1n})^{\top}\in\Rat{n}$ and $||d||=1$, then it follows from the previous assumption, \eqref{transition:mat}, and \eqref{obs:Gramian:ext} that
\begin{align}
    \lim_{p\to+\infty}\int_{t_p}^{t_p+\bar{\delta}}\|\mathcal{C}\Phi(s,t_p)d\|^2ds=0
\end{align}
or, by a change of variables,
\begin{align}
    \lim_{p\to+\infty}\int_{0}^{\bar{\delta}}\|f_p(s)\|^2ds=0
    \end{align}
where we define
\begin{align*}
    f_p(t)&=\mathcal{C}\Phi(t+t_p,t_p)d\\
          &=\mathcal{C}_m\Phi_{11}(t+t_p,t_p)d_1+\mathcal{C}_m\Phi_{12}(t+t_p,t_p)d_2,
\end{align*}
with $\Phi_{11}(\cdot,\cdot)$ and  $\Phi_{12}(\cdot,\cdot)$ satisfying \eqref{Phi:11} and \eqref{Phi:12}, respectively.
From \eqref{Phi:11:de}-\eqref{Phi:12:de}, the successive time-derivatives of $f_p(t)$ are given as follows (argument for $(t+t_p,t_p)$ in $\Phi_{ij}$ is omitted):
\begin{align*}
    f_p^{(1)}(t)&=\mathcal{C}_mS_m\Phi_{11}d_1+\mathcal{C}_mS_m\Phi_{12}d_2+r_1\Phi_{22}d_2\\
    f_p^{(2)}(t)&=\mathcal{C}_mS_m^2\Phi_{11}d_1+\mathcal{C}_mS_m^2\Phi_{12}d_2+r_2\Phi_{22}d_2\\
    &\vdots \\
    f_p^{(m)}(t)&=\mathcal{C}_mS_m^m\Phi_{11}d_1+\mathcal{C}_mS_m^m\Phi_{12}d_2+r_m\Phi_{22}d_2\quad\\
    &=r_m\Phi_{22}d_2\qquad (S_m^m=0)
\end{align*}
with $r_i$ defined by \eqref{fun:r:2}.
Now, using the result of Lemma A.1 in \cite{Sc13}, we deduce that
\begin{align}\label{eq:int-fk}
    \lim_{p\to+\infty}\int_{0}^{\bar{\delta}}\|f_p^{(k)}(s)\|^2ds=0,\quad k=0,\cdots, m
    \end{align}
or, in particular for $k=m$,
\begin{align}
    \lim_{p\to+\infty}\int_{t_p}^{t_p+\bar{\delta}}\|r_m(s)\Phi_{22}(s,t_p)d_2\|^2ds=0.
\end{align}
However thanks to the PE condition \eqref{uni:obs:3}, this cannot hold except with $d_2=0$. This implies that the derivatives above have the form:
\begin{align}
    f_p^{(k)}(t)=\mathcal{C}_mS_m^k\Phi_{11}(t+t_p,t_p)d_1,\quad k=0,\cdots,m.\label{f:k:der}
\end{align}
On the other hand, notice that thanks to the special structure of the matrix $S_m$, the state transition matrix $\Phi_{11}(t,\tau)$ can be written as
\begin{align*}
    \Phi_{11}(t,\tau)&=\exp(S_m(t-\tau))\\
    &=\begin{bmatrix}
    1&(t-\tau)&\frac{(t-\tau)^2}{2!}&\cdots&\frac{(t-\tau)^{m-1}}{(m-1)!}\\
    0&1&(t-\tau)&\cdots&\frac{(t-\tau)^{m-2}}{(m-2)!}\\
    \vdots&\vdots&\ddots&\vdots&\vdots\\
    0&0&0&\cdots&1\\
    \end{bmatrix}.
\end{align*}
Also, since $S_m$ is a shift matrix, we have
\begin{align*}
    \mathcal{C}_mS_m&=[0\; 1\; 0\cdots0\; 0]\\
    \mathcal{C}_mS_m^2&=[0\; 0 \;1\cdots0\; 0]\\
      &\vdots\\
       \mathcal{C}_mS_m^{m-1}&=[0\; 0\;\ldots\;0 \;1].
\end{align*}
By taking into account \eqref{f:k:der}, the last equation $\mathcal{C}_mS_m^{m-1}=[0,0,\ldots,0,1]$ implies that $f_p^{(m-1)}(s)=d_{1,m}$ which in turn leads in view of \eqref{eq:int-fk} to $\lim_{p\to\infty}\int_{0}^{\bar{\delta}} |f_p^{(m-1)}(s)|^2ds=\lim_{p\to\infty}\allowbreak\int_0^{\bar{\delta}} d_{1,m}^2ds=0$ and $d_{1,m}=0$. Since $d_{1,m}=0$, we have in view of \eqref{f:k:der} and $\mathcal{C}_mS_m^{m-2}=[0,0,\ldots,1,0]$  that $f^{(m-2)}=(t-\tau)d_{1,m}+d_{1,m-1}=d_{1,m-1}$. This leads in view of \eqref{eq:int-fk} to  $\lim_{p\to\infty}\int_0^{\bar{\delta}}\allowbreak |f_p^{(m-2)}(s)|^2ds=\lim_{p\to\infty}\allowbreak \int_{0}^{\bar{\delta}}d_{1,m-1}^2ds=0$ and hence $d_{1,m-1}=0$. Using recursively the same argument for each $k=m-2,m-3,\ldots,1,0$ and by exploiting \eqref{f:k:der} we have that $d_1=0$ and thus $d=0$ which is a contradiction since $||d||=1$. \qed
\end{pf}

{Notice that the PE condition in \eqref{uni:obs:3} is equivalent to the uniform observability of the pair $(A,r_m(t))$ since the matrix in \eqref{uni:obs:3} corresponds to the observability Gramian of this pair (recall that $\Phi_{22}$ is the state transition matrix of $A$). The next PE condition guarantees the uniform observability of system \eqref{sys:noC:ext} without requiring the computation of the Gramian matrix for the pair $(A,r_m(t))$ but under the additional assumption that the matrix $A$ has real eigenvalues.}
\begin{prop}\label{PE:cond:4}
When $A$ has real eigenvalues, a sufficient condition for \eqref{uni:obs:3} to hold is the following
\begin{align}\label{uni:obs:4}
		\int_t^{t+\bar{\delta}}r_m^{\top}(s) r_m(s)ds\ge\bar{\mu} I_n.
\end{align}
for some $\bar{\delta},\bar{\mu}>0$.
\end{prop}
\begin{pf}
The proof follows directly from Lemma 2.7 in \cite{HS17}  by noticing that the pair $(A,I_n)$ is Kalman observable. \qed
\end{pf}

Notice that each $r_i(\cdot)$ in \eqref{fun:r:2}, can be written as a summation of higher order derivatives of the input $u$. More specifically, it can shown by induction that
\begin{align}
    r_m=\sum_{i=0}^{m-1}u^{(i)^\top}\Gamma_{i+1,m}
\end{align}
such that
\begin{align}
    \Gamma_{i+1,k+1}=\Gamma_{i+1,k}A+\Gamma_{i,k},\quad i=0,\cdots,k
\end{align}
and $\Gamma_{0,k}=B^\top C_k$ and $\Gamma_{k+1,k}=0$.  It follows that
\begin{align}\label{eq:rm:Gamma}
    r_m^\top=\begin{bmatrix}
    \Gamma_{1,m}\\
    \Gamma_{2,m}\\
    \vdots\\
    \Gamma_{m,m}
    \end{bmatrix}^\top\begin{bmatrix}
    u\\
    \dot u\\
    \vdots\\
    u^{(m-1)}
    \end{bmatrix}=:\Gamma^\top\bar U
\end{align}

\begin{prop}
Assume that $A$ has real eigenvalues and the pair $(A,\Gamma)$ is Kalman observable. Then, a sufficient condition for \eqref{uni:obs:3} to hold is the following
\begin{align}
		\int_t^{t+\delta}\bar U(s)\bar U(s)^\top ds\ge\mu I_{pm}.\label{PE:Ubar}
\end{align}
then \eqref{uni:obs:4} holds.
\end{prop}
\begin{pf}
The proof follows directly from Lemma 2.7 in \cite{HS17} in view of \eqref{uni:obs:3} and \eqref{eq:rm:Gamma}. \qed
\end{pf}
The advantage of the above PE condition is that the vector $\bar U(t)$ is directly expressed as a function of the input and its higher derivatives. However, the drawback compared to \eqref{uni:obs:4} is that we might check a PE condition on a vector with higher dimension when $pm\geq n$. Finally, notice that conditions \eqref{uni:obs:3},  \eqref{uni:obs:4}, and \eqref{PE:Ubar} require in general less number of derivatives compared to \eqref{uni:obs:2}.

{Now that we established different conditions for the uniform observability of the extended system \eqref{sys:noC:ext} it is possible to estimate its state and consequently the state of the original system with the desing of a Kalman estimator as in Theorem \ref{Theorem:K:obs} with $\theta=0$.  Note that the structure of the augmented system allows to apply other observer designs presented for instance in \cite{BBH96}, \cite{BCC88}, \cite{KJ11}, \cite{TK19}. In fact, one of the advantages of the observer design methodology adopted in this paper is that the global state estimation can be achieved by a simple linear Kalman type observer as in Theorem \ref{Theorem:K:obs} as shown in the simulation examples of the next section.}

 \section{Numerical Example}
 The following example illustrates the state extension as well as the observability conditions presented in the previous section. We consider a vehicle navigating in $\mathbb{R}^n$ using a single position range measurement positioned at $0\in\Rat{n}$. The dynamics of the vehicle can be written as
 \begin{align}
     &\dot x_1=x_2\\
     &\dot x_2=u\\
     &y=\frac{1}{2}\|x_1\|^2
 \end{align}
 where $x_1\in\mathbb{R}^n$ represents the position of the vehicle, $x_2\in\mathbb{R}^n$ is its linear velocity, and $u$ is the corresponding inertial acceleration. The output $y$ represents the (half squared) position range to the origin. The vehicle's dynamics are written as in \eqref{sys:LTI} with $x=(x_1^\top,x_2^\top)^{\top}\in\Rat{2n}$ and
\begin{align*}
&A=\left[\begin{matrix}
0&I_n\\
0&0\end{matrix}\right],\qquad
B=\left[\begin{matrix}
0\\
I_n\end{matrix}\right],\qquad C=\left[\begin{matrix}
I_n&0\\
0&0\end{matrix}\right]
\end{align*}
 It is easy to verify that $A^2=0$ and that $C_{m}=0$ with $m=3$, i.e., $C_3=0$. Indeed, according to \eqref{Ci} we have
\begin{equation*}
\begin{array}{lll}
C_1=\left[\begin{matrix}
 0 & I_n  \\
 I_n & 0
\end{matrix}\right],&
C_2=\left[\begin{matrix}
 0 & 0  \\
 0 & 2I_n
\end{matrix}\right],& C_3=0.
\end{array}
\end{equation*}

 Then, from \eqref{matrix:Au:ext}, we obtain the extended matrix
\begin{align*}
\mathcal{A}(u):=
\begin{bmatrix}
0&1&0&u^{\top}B^{\top}C_0\\
0&0&1&u^{\top}B^{\top}C_1\\
0&0&0&u^{\top}B^{\top}C_{2}\\
0&0&0&A
\end{bmatrix}.
\end{align*}
According to \eqref{fun:r:2} we can calculate $r_1(t)=0$, $r_2(t)=[u^\top(t),0]$, and $r_{3}(t)=[\dot{u}^{\top}(t),3u^{\top}(t)]$. Since, the matrix $A$ has real eigenvalues, a sufficient condition for the uniform observability of the extended system follows from Proposition \ref{PE:cond:4}:
$$\int_t^{t+\delta}\begin{bmatrix}
\dot{u}(s)\dot{u}^\top(s)&3\dot{u}(s)u^\top(s)\\
3{u}(s)\dot{u}^\top(s)&9u(s)u^\top(s)
\end{bmatrix}\ge \mu I_{2n},$$
which is a PE condition on the acceleration and the jerk of the vehicle.
 \begin{figure}[t!]
\centering
\includegraphics[scale=0.6]{conf_traj}
\caption{Real and estimated trajectory of the vehicle.}
\label{fig:traj}
\end{figure}
\begin{figure}[t!]
\centering
\includegraphics[scale=0.768]{conf_x1}
\includegraphics[scale=0.768]{conf_x2}
\caption{Estimation errors for the position $x_1$ and velocity $x_2$.}
\label{fig:error}
\end{figure}
For simulation, we consider that the vehicle moves along the 3D trajectory $x_1(t)=(20 \cos (t)-20,10 \sin (2t)+20,-4 \cos (4 t))$ which is rich enough to satisfy the PE condition.  We perform the state estimation of the augmented state through a Kalman type observer given in Theorem \ref{Theorem:K:obs} with  $S_0=100I_{6}$, $V=0.0001I_6$, and $W=I_6$. In Figure \ref{fig:traj} the red trajectory generated by the observer of the system converges to the actual trajectory in blue. Figure \ref{fig:error} shows that the position and velocity estimation errors converge to zero.

 \section{Conclusion}
We proposed an immersion-type technique that transforms a class of linear systems with quadratic output to a new system with linear output  by adding a finite number of states to the original system. The class of linear systems considered is characterized by polynomial outputs under zero inputs, which encompasses for example nilpotent systems. Moreover, we derived persistence of excitation conditions for the admissible inputs that establish the uniform observability of the new system. The PE conditions are explicit and can be checked easily for a given input function. In future work we will address the problem of state estimation with multiple quadratic outputs and extend the current approach to systems for which $C_m\neq0$ for all $m\in\mathbb{N}$.

\cite{*}
\bibliography{ifacconf}

\appendix
\section{Proof of Binomial Expression \eqref{Ci:formula}.}

The proof of \eqref{Ci:formula} follows by induction. More specifically, for $i=1$, \eqref{Ci:formula} obviously holds. Suppose that for some $m\in\mathbb{N}$, $C_m=\sum_{r=0}^{m}\binom{m}{r}A^{\top^r}CA^{m-r}$. Then we have
	\begin{align*}
	C_{m+1}=&C_mA+A^{\top}C_m=\sum_{r=0}^{m}\binom{m}{r}A^{\top^r}CA^{m+1-r}\\&+\sum_{r=0}^{m}\binom{m}{r}A^{\top^{r+1}}CA^{m-r}\\
	=&A^{\top^{m+1}}C+\sum_{r=0}^{m-1}\binom{m}{r}A^{\top^{r+1}}CA^{m-r}\\&+\sum_{r=0}^{m}\binom{m}{r}A^{\top^r}CA^{m+1-r}\\
	=&CA^{m+1}+A^{\top^{m+1}}C+\sum_{r=1}^{m}\binom{m}{r-1}A^{\top^r}CA^{m+1-r}\\&+\sum_{r=1}^{m}\binom{m}{r}A^{\top^r}CA^{m+1 -r}\\
	=&CA^{m+1}+A^{\top^{m+1}}C+\sum_{r=1}^{m}\binom{m+1}{r}A^{\top^r}CA^{m+1-r} \\
	=&\sum_{r=0}^{m+1}\binom{m+1}{r}A^{\top^r}CA^{m+1-r}
	\end{align*}
	where in the last equality we have taken into account Pascal's identity $\binom{n}{k}+\binom{n}{k-1}=\binom{n+1}{k}$.

\end{document}

config: arxiv


TITLE: Proving statements , that require Zorn's lemma , for countable case directly by well-ordering principle of natural numbers
QUESTION [1 upvotes]: We know that for countable sets , the existence of a choice function is a consequence of the well-ordering principle ; and it is also known that the results like "every vector space has a maximal linearly independent set " , " every proper ideal in a ring with identity is contained in some maximal ideal " , " intersection of all prime ideals is a subset of the set of all nilpotent elements " etc. depends on Zorn's lemma which is equivalent to axiom of choice ; so my question is can we give proofs of these above statements when the corresponding Vector-spaces  or Rings are countable , using well ordering principle directly ?   Demonstration of at-least one of the proofs for countable case in such a way ( if possible ) would be really helpful , thanks in advance .

REPLY [2 votes]: The answer, is generally yes. The idea is that we enumerate the countable set, then proceed one by one to collect the maximal subset.
For example. If $V$ is a countable vector space, then it has a basis.
Enumerate $V\setminus\{0\}=\{v_n\mid n\in\Bbb N \}$ and define by recursion the sets $B_k$.
$B_0=\{v_0\}$ and if $B_n$ was defined, then $B_{n+1}$ is $B_n$ added $v_k$ where $k$ is the least index of a vector not in the span of $B_n$, if it exists; if not such vector exists then just $B_{n+1}=B_n$.
Now define $B=\bigcup B_n$, and we claim that it is a basis for $V$. To see that, simply prove by induction that any linear dependence would contradict the construction (meaning we chose a vector that was in the span of the previous ones), and similarly if $v$ is any vector then at some point we could create it from some $B_n$.


TITLE: Difference between stochastic process and chaotic system
QUESTION [4 upvotes]: Can anyone please point out some difference and similarity between stochastic system  and chaotic system?

REPLY [4 votes]: I think this is an excellent question that maybe doesn't have
a clear-cut answer. Here is my personal attempt.
Technically speaking, I suppose a 'stochastic process' can be
almost any collection of random variables (usually indexed by time).
But the stochastic processes of most interest are those in which some
sort of 'glue' holds these random variables together so that the
long run behavior (as time passes) can be described in some meaningful manner.
IID. As suggested by @Michael a sequence of iid random variables
would be considered a stochastic process. Even though no one
observation in the sequence helps predict others, there are
some interesting rules of behavior described the the Law of Large
Numbers and the Central Limit Theorem (under reasonable conditions).
Markov. Markov processes have a sort of one-step dependence, that may or
may not wear off as time passes. Consider process with only
two states 0 and 1. (a) If the process simply alternates between
0 and 1 at each step in time, starting at state 1 at step 1,
then it is always in state 1 at every odd-numbered step.
Technically Markovian, but not very interesting. (b) If the
process moves from its current state to the other with probability
1/3 at each step, then the influence of its starting state
soon wears away. All we can say is that in the limit it will spend
half of the steps in 0 and half in 1. (c) A process that starts
in state 0 and moves to state 1 when the first 6 appears on
a repeatedly rolled die, then it will take an average of six
steps to get to state 1 and then stay there forever.
"Chaotic." I think the terminology 'chaotic' is reserved for processes
in which it is essentially impossible to describe the long
run behavior in any meaningful way knowing the initial state
(and even knowing some of the rules of movement among states).
Traditionally and most simply, coin tossing is often considered 'chaotic' in the sense
that there is no predicting whether the coin will show H or T.
One might try to take into account the speed and spin with
which it is tossed, but very small differences in speed and spin
can determine H or T in a way that is not generally considered predictable.
We do suppose that a fair coin will land H or T and that it will
show each result half of the time. But relative to the simplicity
of the probability model, coin tossing has a 'chaotic' feel because it does
not seem possible to predict beyond the obvious.
Closer to the main sense of a 'chaotic' process may be weather
and its unpredictability. Specific forecasts about rain are
usually futile more than three or four days in advance. There
are too many tiny factors that can affect whether a storm will
develop, stay coherent, or fade away to make a reasonable
forecast. Even a forecast of 'scattered showers' for tomorrow in my area
tells me essentially nothing about whether I get rain in my garden tomorrow.
Definitions? I'm sure there are texts on stochastic processes that pretend to
give a narrower definition than mine, and that there are books
on chaos theory that will try to do the same for that field.
However, I do not know of any generally satisfactory definitions that
make a really clear cut distinction. I'm posting this hoping that
someone comes closer to 'mathematics' than to 'intuition' in
making the distinction.


TITLE: Find $\lim_{x\to 0}\frac{x}{\sin x - x}$
QUESTION [2 upvotes]: Find limit:
$$\lim_{x\to 0}\frac{x}{\sin x - x} = ???$$
Any help would be thoroughly appreciated.

REPLY [0 votes]: If you're allowed to use l’Hôpital's theorem, you have
$$
\lim_{x\to0}\frac{x}{\sin x-x}=\lim_{x\to0}\frac{1}{\cos x-1}
$$
Since $\cos x-1<0$ for $-\pi/2<x<\pi/2$, $x\ne0$, we know that the denominator is negative in a (punctured) neighborhood of $0$. Thus
$$
\lim_{x\to0}\frac{x}{\sin x-x}=\lim_{x\to0}\frac{1}{\cos x-1}=-\infty
$$


TITLE: Show $L^M=L^{\langle M\rangle}$
QUESTION [0 upvotes]: Let $L/K$ be a field extension and $M\subset\text{Aut}_K(L)$ a subset. Then for $\langle M\rangle\subset\text{Aut}_K(L)$ $$L^M=L^{\langle M\rangle}.$$
I need hints, I don't know how to start here.

REPLY [1 votes]: Hint: Note that $L^{\langle M\rangle} \subseteq L^{M}$; if $l \in L$ is fixed by all the automorphisms in $\langle M\rangle$, then it is fixed by all the automorphisms in $M \subseteq \langle M\rangle$.
For the other inclusion, let $l \in L^M$. For any $\phi \in \langle M\rangle$, $\phi = \theta_1\circ\theta_2\circ\dots\circ\theta_n$ where $\theta_i \in M$ or $\theta_i^{-1} \in M$.


text:
\section{Path-Connected Set in Subspace}
Tags: Path-Connected Spaces

\begin{theorem}
Let $T = \struct {S, \tau}$ be a [[Definition:Topological Space|topological space]].
Let $A \subseteq B \subseteq S$.
Let $T_B = \struct {B, \tau_B}$ be the [[Definition:Topological Space|topological space]] where $\tau_B$ is the [[Definition:Subspace Topology|subspace topology]] on $B$.
Then
:$A$ is [[Definition:Path-Connected (Topology)|path-connected]] in $T_B$ {{iff}} $A$ is [[Definition:Path-Connected (Topology)|path-connected]] in $T$.
\end{theorem}

\begin{proof}
Let $\tau_A$ be the [[Definition:Subspace Topology|subspace topology]] on $A$ induced by $\tau$.
Let $\tau'_A$ be the [[Definition:Subspace Topology|subspace topology]] on $A$ induced by $\tau_B$.
By the definition of a [[Definition:Path-Connected Set (Topology)|path-connected set]], $A$ is [[Definition:Path-Connected Set (Topology)|path-connected]] in $T$ {{iff}} every two points in $A$ are [[Definition:Path-Connected Points|path-connected]] in $\struct {A, \tau_A}$.
Similarly, $A$ is [[Definition:Path-Connected Set (Topology)|path-connected]] in $T_B$ {{iff}} every two points in $A$ are [[Definition:Path-Connected Points|path-connected]] in $\struct {A, \tau'_A}$.
From [[Subspace of Subspace is Subspace]], we have $\tau_A = \tau'_A$.
Hence every two points in $A$ are [[Definition:Path-Connected Points|path-connected]] in $\struct {A, \tau_A}$ {{iff}} every two points in $A$ are [[Definition:Path-Connected Points|path-connected]] in $\struct {A, \tau'_A}$.
{{qed}}
[[Category:Path-Connected Spaces]]
fjn398nft5bqigl7msccdtvfw6sjie6
\end{proof}

config: wiki


TITLE: Noncommutativity and Quantum Fluctuations
QUESTION [2 upvotes]: I have been reading a book called Quantum Phase Transitions in Transverse Field Spin Models:
From Statistical Physics to Quantum Information. Part I on this book gives an introduction to Quantum Phase Transitions (QPTs). Chapter 1 in Part I states that:

"The presence of non-commuting terms in the Hamiltonian produces a superposition
between various states. In QPTs, it is the quantum fluctuations (due to non-commuting terms in the Hamiltonian)
which are responsible for taking the system from one phase to another." (Section 1.3: page 14)

From this I understood that the claim is : non-commuting terms in the Hamiltonian leads to quantum fluctuations. To understand why non-commuting terms lead to phase transitions, I read the part of the introductory section on Transverse Ising Models, which starts from page 17. This model describes a d dimensional hypercube lattice containing N spins, either up or down. The Hamiltonian is given by equation 1.8 in the book:

$\hat{H} = -\sum_{\langle ij\rangle} J_{ij} \sigma_i^x \sigma_j^x - h\sum_i \sigma^z_i$

Here we see that that $\sigma^a_i$ is the $a^{th}$ Pauli Spin matrix at the lattice site $i$. The text also claims:

" In this
section, we assume that Jij = Jx ≥ 0, i.e., a ferromagnetic (FM) interaction between the
nearest-neighbor spins. which simplifies the Hamiltonian to the form:
$\hat{H} = -\sum_{\langle ij\rangle} J \sigma_i^z \sigma_j^z - h\sum_i \sigma^x_i$"

(Side Comment: I am not sure why the Hamiltonian in (Eq. 1.8) would transform this way; I do not see why the sum over nearest neighbors started with x Pauli matrices and ended with z Pauli matrices, but I went with the textbook). Now comes the following statement:

"The operator $\sigma_i^x$
acting on the eigenstate of $\sigma_i^z$ with eigenvalue +1 (up state)
changes it to the down state with eigenvalue −1. The non-commuting transverse field
term, therefore, introduces quantum fluctuations in the model causing a QPT" (pg 17)

I understand the first sentence completely. However, I am not sure what the second statement means. Is the noncommutative transverse field term the sum $h\sum_i \sigma^x_i$? If it is, is it noncommutative because the commutator of the first and second terms of the Hamiltonian is nonzero via the Pauli spin matrix commutator rule? Also, why does this non-commutativity lead to quantum fluctuations? For the last part, please kindly provide a conceptual and mathematical explanation.

REPLY [0 votes]: I'd like to complete catalogue_number's answer by elaborating on the meaning of

In QPTs, it is the quantum fluctuations (due to non-commuting terms in the Hamiltonian) which are responsible for taking the system from one phase to another.

Immediately before that, the authors state that

Each term of the Hamiltonian, when
dominant, corresponds to a specific ground state and determines a phase in the phase diagram. The presence of non-commuting terms in the Hamiltonian produces a superposition between various states.

Consider the Ising Hamiltonian
$$H = -J \sum_{<ij>}\sigma^z_i\sigma^z_j - h \sum_i \sigma^x_i$$
and its limiting case $h \to 0$
$$H_0 = -J \sum_{<ij>}\sigma^z_i\sigma^z_j.$$
Referring to the first sentence of the second quote, this can also be thought as the limiting case in which $h \neq 0$ but $J >> h$.
Denoting $\{ |\uparrow \rangle ,|\downarrow\rangle \}$ the eigenbasis of $\sigma^z$ the ground state of $H_0$ is doubly degenerate
$$\begin{align}
&|\uparrow \uparrow \dots \uparrow\rangle\\
&|\downarrow \downarrow \dots \downarrow\rangle
\end{align}$$
with energy $-NJ$, where $N$ is the number of sites on the chain and periodic boundary conditions are assumed.
Both states being eigenstates of $H_0$, when measuring the energy in any one of them the probability of getting the value $E_0 = -NJ$ is $P(-NJ) = 1$. In other words, there are no statistical fluctuations in the value of the energy.
If we turn on the magnetic field, the Hamiltonian of the system is now $H$ which is not diagonal in the $H_0$ basis (i.e. the $\sigma^z$ basis), and therefore will have a different ground state. Notice that this is a direct consequence of the non-commutativity of $H_0$ and $H_1 = H - H_0$: if the two terms commuted, $H$ and $H_0$ would share the same eigenbasis, just with different eigenvalues.
If we wait for the system to equilibrate (i.e. either we turn on $h$ very slowly or we wait until it is in the new ground state of $H$) and measure again $H_0$, we will have a probability distribution over its spectrum for the value that we will measure (i.e. no value will turn out with probability 1) and hence there will be non-zero statistical fluctuations.
At zero temperature there are no thermal fluctuations, and it is the study of how the quantum fluctuations just described change with $h$ that characterize quantum phase transitions.


text:
\begin{document}

\title{ Hyperbolic model for Helmholtz equation with impedance boundary conditions}

\author{Ramaz Botchorishvili}
\address{Faculty of Exact and Natural Sciences, Ivane  Javakhishvili Tbilisi State University, Tbilisi, Georgia}
\email[Corresponding author]{ramaz.botchorishvili@tsu.ge (Corresponding author)}

\author{Tamar Janelidze}
\address{Faculty of Exact and Natural Sciences, Ivane  Javakhishvili Tbilisi State University, Tbilisi, Georgia;
         Institute of Energy and Climate research 8: Troposphere, Research Center J\"ulich, J\"ulich, Germany }
\email{t.janelidze@fz-juelich.de}

\keywords{Helmholtz equation , first order hyperbolic system approach , well balanced property}

\subjclass[2010]{65L10, 65M06}

\date{\today}

\begin{abstract}
		Solution of Helmholtz equation with impedance boundary condition on finite interval is equivalently reformulated as
		steady state of initial boundary value problem for first order hyperbolic system of partial differential equations.
		Particularly interesting property of the proposed hyperbolic model is that steady state is achieved in finite time.
		For large wavenumber the numerically challenging task for Helmholtz equation is achieving high accuracy with small number of nodal points. We successfully solved this problem by means of using  well balanced scheme approach.
		Numerical tests demonstrate excellent computational potential of the proposed method: high accuracy is achieved for large wavenumber with small number of nodal points in space and time.
\end{abstract}

\maketitle

\section{Introduction}
We consider Helmholtz equation on finite interval with impedance boundary consitions
\begin{equation}\label{eq:Helmholz}
	\frac{d^2 u}{d x^2}+k^2 u=f, ~ 0<x<1,
\end{equation}
\begin{equation}\label{eq:ImpedanceCondition}
u'(0) + iku(0)=g_0, ~~~ u'(1) - iku(1)=g_1,
\end{equation}
\begin{equation}\label{eq:complexFunctions}
u(x)= u_R(x) + iu_I(x),   f(x)= f_R(x) + if_I(x),  g_0= g_{0R} + ig_{0I},  g_0= g_{1R} + ig_{1I},
\end{equation}
where  $i$ is unit imaginary number, $i^2=-1$, $k, g_{RI}, g_{1I}$ are real numbers, $k>0$, $f_R(x), f_I(x)$ are sufficiently smooth real
valued functions that ensure the functions $u_R(x), u_I(x)$ are sufficiently smooth.

Main numerical challenge associated with Helmholtz equation is finding such spatial discretization that ensure that obtained linear
system can be solved efficiently by iterative methods. If $\Delta x$ is discretization step and wavenumber is small then $k \Delta x = const$
is a good choice for determining suitable mesh ~ \cite{ihlenburg1995finite}. If wavenumber is large then for dealing with the so
called pollution effect $k^{\gamma} \Delta x $ small is needed with  $\gamma >1$ resulting in very fine mesh and  very large system of
linear algebraic equations ~\cite{ihlenburg1995finite}. Solving this linear system by iterative methods is a difficult task,
see ~\cite{ernst2012difficult} for detailed exposition on the subject.

Here we propose new method that is motivated by first order system approach ~\cite{nishikawa2007first} introduced initially for
diffusion equation and by well balanced schemes for hyperbolic conservation laws with source terms pioneered in
 ~\cite{bermudez1994upwind, greenberg1996well}. The strategy set by first order system approach is to solve an equivalent
first-order hyperbolic system instead of the second-order diffusion equation thus achieving stable computation with time step $O(\Delta x)$
that is typical for hyperbolic equations instead of time step $O((\Delta x)^2)$ that is typical for parabolic equations. The srtategy set
by  the well-balanced property of numerical schemes is  preservation of discrete equilibrium states that results in high accuracy with
small number of nodal points. In our approach we offer suitable combination of these approaches resulting in highly efficient numerical method.

The rest of the paper is organized as follows: hyperbolic model is developed in section \ref{sec:hypmodel}; numerical scheme is developed in section \ref{sec:numerical};
it is investigated theoretically and numerically in sections \ref{sec:numerical} and \ref{sec:numtests}.

\section{Hyperbolic model}
\label{sec:hypmodel}
Following the strategy set by first order system approach ~\cite{nishikawa2007first} the goal is finding  first order hyperbolic system of
partial differential equations that at steady states is equivalent to Helmholtz equation (\ref{eq:Helmholz}).
We consider the following linear hyperbolic system

\begin{equation}\label{eq:HypSystemQ}
\frac{\partial \vec{Q}}{\partial t}+A\frac{\partial\vec{Q}}{\partial x}=B\vec{Q}+\vec{F}, ~t>0,
\end{equation}
where $\vec{Q}=(Q_1(t,x), Q_2(t,x), Q_3(t,x), Q_4(t,x))^T$ is unknown real valued vector function, \\ $\vec{F}=(F_1(x), F_2(x), F_3(x), F_4(x))^T$
is real valued vector function, $A,B \in \mathbb{R}^{4\times4}$.

The system (\ref{eq:HypSystemQ}) is equipped with initial and boundary conditions

\begin{equation}\label{eq:InitConditionQ}
\vec{Q}(0,x)=\vec{Q}_0(x), ~~0<x<1,
\end{equation}

\begin{equation}\label{eq:BoundCondition,Q}
B_0\vec{Q}(t,0)=\vec{G}_0, ~~B_1\vec{Q}(t,1)=\vec{G}_1, ~~t \geq 0,
\end{equation}
where $\vec{Q}_0(x)$ is sufficiently smooth, $B_0,B_1 \in \mathbb{R}^{4\times4}$, $\vec{G}_0,\vec{G}_1 \in \mathbb{R}^{4}$. We set

\begin{equation}\label{eq:lambda<0,>0}
\lambda_1,\lambda_2 >0, \lambda_3,\lambda_4 <0,
\end{equation}
\begin{equation}\label{eq:G0,G1}
\vec{G}_0=(g_{0R},g_{0I},0,0)^T, ~~	\vec{G}_1=(0,0,g_{1R},g_{1I})^T,
\end{equation}

\begin{equation}\label{eq:B_0,B_1}
B_0 =
\begin{pmatrix}
k    &  0    &  1   &  0     \\
0    &  k    &  0   &  1     \\
0    &  0    &  0   &  0  \\
0    &  0    &  0   &  0  \\
\end{pmatrix}
,
B_1 =
\begin{pmatrix}
0    &  0    &  0   &  0  \\
0    &  0    &  0   &  0  \\
0    &  k    &  1   &  0     \\
-k   &  0    &  0   &  1     \\
\end{pmatrix}
,
\end{equation}
\begin{equation}\label{eq:RHS,F}
\vec{F}= \frac{1}{2}
\begin{pmatrix}
[f_I (\lambda_2-\lambda_4)+f_R (\lambda_1-\lambda_3)] \frac{1}{k} \\
[f_I ({\lambda}_2-{\lambda}_4)+f_R ({\lambda}_3-{\lambda}_1)] \frac{1}{k} \\
f_I (\lambda_4 -\lambda_2)+f_R (\lambda_1+\lambda_3) \\
f_I (\lambda_2+\lambda_4)+f_R (\lambda_1-\lambda_3)
\end{pmatrix}
,
\end{equation}
\begin{equation}\label{eq:LHS,A}
A = \frac{1}{2}
\begin{pmatrix}
\lambda_1+\lambda_4    &  \lambda_2-\lambda_3    & (\lambda_1-\lambda_3)\frac{1}{k}  &  (\lambda_2-\lambda_4)\frac{1}{k} \\
\lambda_4-\lambda_1    &  \lambda_2+\lambda_3    & (\lambda_3-\lambda_1)\frac{1}{k}  &  (\lambda_2-\lambda_4)\frac{1}{k} \\
(\lambda_1-\lambda_4)k &  (\lambda_3-\lambda_2)k & \lambda_1+\lambda_3            &  \lambda_4-\lambda_2  \\
(\lambda_1-\lambda_4)k &  (\lambda_2-\lambda_3)k & \lambda_1-\lambda_3            &  \lambda_4+\lambda_2  \\
\end{pmatrix}
,
\end{equation}
\begin{equation}\label{eq:RHS,B}
B = \frac{1}{2}
\begin{pmatrix}
(\lambda_3-\lambda_1)k    &  (\lambda_4-\lambda_2)k    &  \lambda_1+\lambda_4   &  \lambda_2-\lambda_3     \\
(\lambda_1-\lambda_3)k    &  (\lambda_4-\lambda_2)k    & \lambda_4-\lambda_1    &  \lambda_2+\lambda_3     \\
-(\lambda_1+\lambda_3)k^2 &  (\lambda_2-\lambda_4)k^2  & (\lambda_1-\lambda_4)k &  (\lambda_2-\lambda_3)k  \\
(\lambda_3-\lambda_1)k^2  &  -(\lambda_2+\lambda_4)k^2 & (\lambda_1-\lambda_4)k &  (\lambda_2-\lambda_3)k  \\
\end{pmatrix}
.
\end{equation}
\begin{theorem}[Steady state equivalence]\label{Th:equivalence}
	Helmholtz equation with impedance boundary conditions (\ref{eq:Helmholz}),(\ref{eq:ImpedanceCondition}) is equivalent to initial
	boundary value problem for hyperbolic system (\ref{eq:HypSystemQ})-(\ref{eq:RHS,B}) at steady states in the following sense:
\begin{equation}\label{eq:U=Q}
	u_R(x)=Q_1(t,x), ~u_I(x)=Q_2(t,x),~\frac{du_R(x)}{dx}=Q_3(t,x), ~\frac{du_I(x)}{dx}=Q_4(t,x), ~t \geq 0.
\end{equation}
\end{theorem}
\begin{proof} Helmholtz equation (\ref{eq:Helmholz}) equivalently writes as the following first order system of equations:
\begin{equation}\label{eq:Helmholtz,q}
	\frac{d\vec{q}}{dx}=B_q \vec{q}+\vec{F_q},
\end{equation}
\begin{equation}\label{eq:v,q}
v_R=\frac{du_R}{dx}, ~~	v_I=\frac{du_I}{dx}, ~~ \vec{q}=(u_R,u_I,v_R,v_I)^T
\end{equation}
\begin{equation}\label{eq:B_q,F_q}
B_q= \begin{pmatrix}
	0    &  0   & 1 & 0 \\
	0    &  0   & 0 & 1 \\
	-k^2 &  0   & 0 & 0 \\
	0    & -k^2 & 0 & 0\\
	\end{pmatrix}
, ~~~~ \vec{F_q} =
	\begin{pmatrix}
	0   \\
	0   \\
	f_R \\
	f_I \\
	\end{pmatrix}
	.
\end{equation}

From the system (\ref{eq:Helmholtz,q})-(\ref{eq:B_q,F_q}) one can easily recover Helmholtz equation (\ref{eq:Helmholz}) by means of using first and second equations of (\ref{eq:Helmholtz,q}) in the third and fourth equations.

Using the above notations boundary condition (\ref{eq:ImpedanceCondition}) equivalently writes:
\begin{equation}\label{eq:BoundCondition,q}
B_0\vec{q}(0)=\vec{G}_0, ~~B_1\vec{q}(1)=\vec{G}_1.
\end{equation}

At steady states ${\partial Q_i(t,x) / \partial t} =0, ~i=1,2,3,4$ and hyperbolic system (\ref{eq:HypSystemQ}) is reduced to the following system of equations:
\begin{equation}\label{eq:Helmholtz,ODE,Q,1}
A\frac{\partial\vec{Q}}{\partial x}=B\vec{Q}+\vec{F}.
\end{equation}

Inverse of $A$ exist, since $det(A)=\lambda_1 \lambda_2 \lambda_3 \lambda_4$ and $det(A) \neq 0$ because of (\ref{eq:lambda<0,>0}).
Multiplying (\ref{eq:Helmholtz,ODE,Q,1}) on $A^{-1}$ from the left yields:
\begin{equation}\label{eq:Helmholtz,ODE,Q,2}
\frac{\partial \vec{Q}}{\partial x}=B_q \vec{Q}+\vec{F_q}.
\end{equation}

At steady states $\vec{Q}$ does not depend on variable $t$  and it depends on variable $x$ only. Therefore (\ref{eq:Helmholtz,q}) and (\ref{eq:Helmholtz,ODE,Q,2})
are in fact the same equations when ${\partial Q_i(t,x) / \partial t} =0, ~i=1,2,3,4$ and (\ref{eq:U=Q}) is also valid. For the same reasons boundary conditions
(\ref{eq:BoundCondition,q}) and (\ref{eq:BoundCondition,Q}) are equivalent when $\vec{Q}$ does not depend on variable $t$.

Thus we have shown that Helmholtz equation with impedance boundary conditions  (\ref{eq:Helmholz}),(\ref{eq:ImpedanceCondition})  and hyperbolic system of partial differential equations with initial and boundary conditions (\ref{eq:HypSystemQ})-(\ref{eq:RHS,B}) are equivalent to the same problem when ${\partial Q_i(t,x) / \partial t} =0, ~i=1,2,3,4$ that concludes the proof.
\end{proof}

\begin{theorem}[Stationary solution of hyperbolic model]\label{Th:Stationary}
	Smooth solution of the problem (\ref{eq:HypSystemQ})-(\ref{eq:RHS,B}) obtained with arbitrary initial value $\vec{Q}_0(x)$ reaches steady state in
	finite time if $\lambda_1=\lambda_2$ and $\lambda_3=\lambda_4$.
\end{theorem}
\begin{proof} Hyperbolic model (\ref{eq:HypSystemQ})-(\ref{eq:RHS,B}) equivalently writes:
\begin{equation}\label{eq:HypSystem,r}
     \frac{\partial \vec{r}}{\partial t}+\Lambda\frac{\partial\vec{r}}{\partial x}=B_r\vec{r}+\vec{F}_r, ~t>0,
\end{equation}
\begin{equation}\label{eq:InitCondition,r}
     \vec{r}(0,x)=\vec{r}_0(x), ~~0<x<1,
\end{equation}
\begin{equation}\label{eq:BoundCondition,r}
  r_1(t,0)=g_{0R}, ~r_2(t,0)=g_{0I}, ~r_3(t,1)=g_{1R}, ~r_4(t,1)=g_{1I},  ~t \geq 0,
\end{equation}
where $\vec{r}$ is Riemann invariant,
\begin{equation}\label{eq:r,Lambda}
	\vec{r}=L\vec{Q}, ~~L=B_0+B_1, ~~\Lambda=diag\{\lambda_1, \lambda_2, \lambda_3,\lambda_4 \},
\end{equation}
\begin{equation}\label{eq:B_r,F_r}
B_q= k \begin{pmatrix}
0            &  -\lambda_1   & \lambda_1  & \lambda_1 \\
\lambda_2    &           0   & -\lambda_2 & \lambda_2 \\
0            &           0   &          0 & \lambda_3 \\
0            &           0   & -\lambda_4 &         0\\
\end{pmatrix}
, ~~~~ \vec{F_r} =
\begin{pmatrix}
\lambda_1 f_R \\
\lambda_2 f_I \\
\lambda_3 f_R \\
\lambda_4 f_I \\
\end{pmatrix}
.
\end{equation}

Riemann invariant $\vec{r}$ is smooth function, $\Lambda, B_r, \vec{F}_r$ do not depend on the variable $t$. Therefore for $\vec{r}~'\equiv {\partial r / \partial t}$
from (\ref{eq:HypSystem,r})-(\ref{eq:B_r,F_r}) we obtain the following problem:
\begin{equation}\label{eq:HypSystem,r'}
\frac{\partial \vec{r}~'}{\partial t}+\Lambda\frac{\partial\vec{r}~'}{\partial x}=B_r\vec{r}~',
\end{equation}
\begin{equation}\label{eq:InitCondition,r'}
\vec{r}~'(0,x)=\vec{r}~'_0(x), ~~0<x<1,
\end{equation}
\begin{equation}\label{eq:BoundCondition,r'}
r'_1(t,0)=0, ~r'_2(t,0)=0, ~r'_3(t,1)=0, ~r'_4(t,1)=0,  ~t \geq 0.
\end{equation}

 Third and fourth equations of (\ref{eq:HypSystem,r'}) are multiplied by $r'_3$ and $r'_4$ respectively. Summing obtained equations yields:
\begin{equation}\label{eq:r3'^2+r4'^2}
	\frac{\partial [(r'_3)^2+(r'_4)^2] }{\partial t}+\lambda_3\frac{\partial[(r'_3)^2+(r'_4)^2]}{\partial x}=0.
\end{equation}

From (\ref{eq:r3'^2+r4'^2}) and (\ref{eq:BoundCondition,r'}) we obtain $(r'_3)^2+(r'_4)^2=0$ when $t>1/|\lambda_3|$. Analogically for $(r'_1)^2+(r'_2)^2$ we obtain the following equation:
\begin{equation}\label{eq:r1'^2+r2'^2}
	\frac{\partial [(r'_1)^2+(r'_2)^2] }{\partial t}+\lambda_1\frac{\partial[(r'_1)^2+(r'_2)^2]}{\partial x}=
	2\lambda_1(r'_3+r'_4)r'_1-2\lambda_2(r'_3-r'_4)r'_2.
\end{equation}

From (\ref{eq:r1'^2+r2'^2}), (\ref{eq:BoundCondition,r'}) and from $r'_3=r'_4=0$ when $t>1/|\lambda_3|$ we obtain $(r'_1)^2+(r'_2)^2=0$ when $t>1/|\lambda_3|+1/\lambda_1$.
Thus ${{\partial r_i} / {\partial t}} =0, i=1,2,3,4$, when $t>1/|\lambda_3|+1/\lambda_1$, i.e. steady state is reached in finite time.
\end{proof}

\section{Numerical scheme}
\label{sec:numerical}
Following ~\cite{botchorishvili2003equilibrium} we consider numerical scheme

\begin{equation}\label{ns:sc,r}
	\frac{\vec{r}_j^{~n+1}-\vec{r}_j^{~n}}{\Delta t}+\Lambda^+\frac{\vec{r}_j^{~n}-\vec{r}_{j-1,+}^{~n}}{\Delta x}
	+\Lambda^-\frac{\vec{r}_{j+1,-}^{~n}-\vec{r}_{j}^{~n}}{\Delta x}=0,
\end{equation}

\begin{equation}\label{ns:InitialCondition,r}
\vec{r}_j^{~0}=\vec{r}(0,x_j), ~x_j=j\Delta x, ~j=0,1,..,N_x, ~\Delta x=1/N_x,
\end{equation}
\begin{equation}\label{ns:BoundaryCondition,r}
r_{1,0}^{n}=g_{0R}, ~ r_{2,0}^{n}=g_{0I}, ~r_{3,N_x}^{n}=g_{1R}, ~r_{4,N_x}^{n}=g_{1I},
\end{equation}

\begin{equation}\label{ns:r+}
	\vec{r}_{j-1,+}^{~n}=e^{B_r\Delta x}\vec{r}_{j-1}^{~n}+
	e^{B_r\Delta x} \int_{x_{j-1}}^{x_j} e^{-B_r(\xi-x_{j-1})}\vec{F}_r(\xi)d\xi,
\end{equation}

\begin{equation}\label{ns:r-}
\vec{r}_{j+1,-}^{~n}=e^{-B_r\Delta x}\vec{r}_{j+1}^{~n}+
e^{-B_r\Delta x} \int_{x_{j+1}}^{x_j} e^{-B_r(\xi-x_{j+1})}\vec{F}_r(\xi)d\xi,
\end{equation}

\begin{equation}\label{ns:Lambda+,Lambda-}
\Lambda^+=diag \{\lambda_1,\lambda_2,0,0\},~\Lambda^-=diag \{0,0,\lambda_3,\lambda_4 \},
\end{equation}
\begin{equation*}
t_n=n\Delta t, ~n=0,1,..,N_t, ~\Delta t=T/N_t, ~T>0, N_t,N_x \in \mathbb{N}.
\end{equation*}

\begin{theorem}[Properties of the scheme]
	Numerical scheme (\ref{ns:sc,r})-(\ref{ns:Lambda+,Lambda-}) maintains discrete steady states of (\ref{eq:HypSystem,r})-(\ref{eq:BoundCondition,r}),
	the scheme is stable under CFL condition $max\{\lambda_1,\lambda_2,|\lambda_3|,|\lambda_4|\}\Delta t/\Delta x <1$ and it is consistent with
	(\ref{eq:HypSystem,r})-(\ref{eq:BoundCondition,r}) in the sense of local truncation error.
\end{theorem}

\begin{proof}
	 Equations (\ref{eq:Helmholtz,q}),(\ref{eq:Helmholtz,ODE,Q,2}) are valid at steady states of  (\ref{eq:HypSystem,r})-(\ref{eq:BoundCondition,r}).
	 Having discrete steady states given at $t_n$ means that $L\vec{q}(x)$ is projected on mesh, i.e. $\vec{r}_j^{~n}=L\vec{q}(x_j)$. At $x_j$ solution
	 of (\ref{eq:Helmholtz,q}) with initial condition $\vec{q}(x_{j-1})=L^{-1}\vec{r}_{j-1}^{~n}$ coincides with  $L^{-1}\vec{r}_{j-1,+}^{~n}$
	 when $\vec{r}_{j-1,+}^{~n}$ is defined by (\ref{ns:r+}). Therefore $\vec{r}_{j}^{~n}-\vec{r}_{j-1,+}^{~n}=0$ at discrete steady states.
	 Analogically from (\ref{eq:Helmholtz,q}) and (\ref{ns:r-}) we obtain $\vec{r}_{j+1,-}^{~n}-\vec{r}_{j}^{~n}=0$ is valid at discrete steady
	 states of (\ref{eq:HypSystem,r})-(\ref{eq:BoundCondition,r}) and thus the scheme  (\ref{ns:sc,r})-(\ref{ns:Lambda+,Lambda-}) is reduced
	 to $\vec{r}_{j}^{~n+1}-\vec{r}_{j}^{~n}=0$,  i.e. discrete steady states are maintained.

	Using Taylor's series expansion in (\ref{ns:r+}),(\ref{ns:r-}) yields the following equivalent formulas:

\begin{equation}\label{ns:r+,dx}
	\vec{r}_{j-1,+}^{~n}=\vec{r}_{j-1}^{~n}+(B_r\vec{r}_{j-1}^{~n} + \vec{F}_r(x_j))\Delta x + 0((\Delta x)^2),
\end{equation}
\begin{equation}\label{ns:r-,dx}
	\vec{r}_{j+1,-}^{~n}=\vec{r}_{j+1}^{~n}-(B_r\vec{r}_{j+1}^{~n} + \vec{F}_r(x_j))\Delta x + 0((\Delta x)^2).
\end{equation}

	On account of (\ref{ns:r+,dx}) and (\ref{ns:r-,dx}) the scheme (\ref{ns:sc,r}) equivalently writes

\begin{equation}\label{ns:sc,r+rhs}
	\frac{\vec{r}_j^{~n+1}-\vec{r}_j^{~n}}{\Delta t}+\Lambda^+\frac{\vec{r}_j^{~n}-\vec{r}_{j-1}^{~n}}{\Delta x}
	+\Lambda^-\frac{\vec{r}_{j+1}^{~n}-\vec{r}_{j}^{~n}}{\Delta x}=
	\Lambda^+B_r\vec{r}_{j-1}^{~n}+\Lambda^-B_r\vec{r}_{j+1}^{~n}+\vec{F}_{r,j} +O(\Delta x).
\end{equation}

From (\ref{ns:sc,r+rhs}) obtaining stability and consistency is straightforward when using standard techniques for studying numerical schemes for first order hyperbolic partial differential equations.
\end{proof}

\section{Numerical tests}\label{sec:numtests}

In the first numerical test considered here $\Delta x$ is kept constant and wavenumber $k$ gradually increases from $10$ to $10^{5}$.
In the second numerical test $k\Delta x$  is kept constant and $\Delta x$ decreases from $10^{-1}$ to $10^{-5}$. We define exact solution of the
problem (\ref{eq:Helmholz}),(\ref{eq:ImpedanceCondition}) by $u(x)=sin(kx)+i2cos(kx)$ that implies $f(x)=0$ in (\ref{eq:Helmholz}).
Therefore $\vec{F}_{r}=0$ and integral vanishes in (\ref{ns:r+}), (\ref{ns:r-}). Matrix exponentials present in these formulas are precomputed
for $k\Delta x =1$. Then for $k\Delta x =m, ~m \in \mathbb{N}$, computation of matrix exponential is reduced to the multiplication of precomputed matrices.
In hyperbolic model we set $\lambda_1=\lambda_2=1$ and $\lambda_3=\lambda_4=-1$ that according to Theorem ~\ref{Th:Stationary}
means that steady state is reached at $T=2$. This effect is also observed numerically in our tests.
In the tables ~\ref{tab:error,q,k} and ~\ref{tab:error,q,dx} the norms $\|\vec{e}\|_{1,2}=max \{ \|e_1\|,\|e_2\| \} $, $\|\vec{e}\|_{3,4}=max \{ \|e_3\|,\|e_4\| \} $
are used for measuring the errors in numerical approximation of the function $u$ and in its derivatives respectively. Numerical results show excellent
computational potential of the developed numerical scheme. In particular the table ~\ref{tab:error,q,k} shows that for wavenumber $k=10^5$  relative
error  $\approx 10^{-3}$ can be obtained with just $11$ nodal points in space and $20$ time steps. Mesh refinement, see table \ref{tab:error,q,dx},
decreases the error further granting high accuracy when $k\Delta x =1$.

\bibliography{hyperbolic_model_for_helmholtz_equation_with_impedance_boundary_conditions}

\begin{table}[h!]
	\centering
	\caption{ Error $\vec{e}=\vec{q}_{exact}-\vec{q}_{numeric}$, $\Delta x=0.1$, $N_x=10$, $N_t=20$.}
	\begin{adjustbox}{width=1\linewidth}
		\begin{tabular}{c c c c c c}
			\hline
			 k       & Error,$\vec{e}$     &  $l_{2,rel}$   & $l_{\infty,rel}$ & $l_{2,abs}$ & $l_{\infty,abs}$ \\
			\hline
			 10      & $\|\vec{e}\|_{1,2}$  & 3.3035777e-07 & 3.817435e-07  & 1.7788994e-06 & 7.63487e-07  \\
			         & $\|\vec{e}\|_{3,4}$  & 3.4928838e-07 & 4.0443439e-07 & 1.7811752e-05 & 8.0026099e-06 \\
			\hline
			 $10^2$  & $\|\vec{e}\|_{1,2}$  & 3.1886394e-06 & 3.602908e-06  & 1.6753317e-05  & 7.205816e-06 \\
			         & $\|\vec{e}\|_{3,4}$  & 3.411358e-06  & 3.9042842e-06 & 1.7855065e-03  & 7.7608476e-04 \\
			\hline
			 $10^3$  & $\|\vec{e}\|_{1,2}$  & 3.9453715e-05 & 4.2069045e-05 & 2.0419553e-04 & 8.413809e-05 \\
			         & $\|\vec{e}\|_{3,4}$  & 3.427245e-05  & 3.8295731e-05 & 1.8204272e+01 & 7.657276e-02   \\
                        \hline
                         $10^4$  & $\|\vec{e}\|_{1,2}$  & 3.2833097e-04 & 3.7296399e-04 & 1.7728889e-03 & 7.4592799e-04 \\
			         & $\|\vec{e}\|_{3,4}$  & 3.5056249e-04 & 4.0213891e-04 & 1.7821279e+01 & 8.0254302 \\
                        \hline
                         $10^5$  & $\|\vec{e}\|_{1,2}$  & 2.8128045e-03 & 3.1224907e-03 & 1.5103248e-02 & 6.2449814e-03  \\
			         & $\|\vec{e}\|_{3,4}$  & 3.434853e-03  & 3.441699e-03  & 1.757117e+03  & 6.882298e+02 \\
                        \hline
		\end{tabular}
	\end{adjustbox}
	\label{tab:error,q,k}
\end{table}

\begin{table}[h!]
	\centering
	\caption{ Error $\vec{e}=\vec{q}_{exact}-\vec{q}_{numeric}$, $k\Delta x=1$, $T=2$.}
	\begin{adjustbox}{width=1\linewidth}
		\begin{tabular}{c c c c c c}
			\hline
			$\Delta x$ & Error,$\vec{e}$ &  $l_{2,rel}$   & $l_{\infty,rel}$ & $l_{2,abs}$ & $l_{\infty,abs}$ \\
			\hline
			$10^{-1}$  & $\|\vec{e}\|_{1,2}$  & 3.9453715e-05 & 4.2069045e-05 & 2.0419553e-04 & 8.413809e-05 \\
			           & $\|\vec{e}\|_{3,4}$  & 3.427245e-05  & 3.8295731e-05 & 1.8204272e-01 & 7.657276e-02 \\
			\hline
			$10^{-2}$  & $\|\vec{e}\|_{1,2}$  & 3.3700138e-06 & 4.3448308e-06 & 5.3714493e-05 & 8.6896615e-06 \\
			           & $\|\vec{e}\|_{3,4}$  & 3.4083229e-06 & 4.2919226e-06 & 5.3992586e-02 & 8.5817495e-03 \\
			\hline
			$10^{-3}$  & $\|\vec{e}\|_{1,2}$  & 3.3997232e-07 & 4.3876751e-07 & 1.7010247e-05 & 8.7753501e-07 \\
			           & $\|\vec{e}\|_{3,4}$  & 3.4011019e-07 & 4.4119365e-07 & 1.7010874e-02 & 8.8237889e-04 \\
                        \hline
                        $10^{-4}$  & $\|\vec{e}\|_{1,2}$  & 3.3956751e-07 & 4.4190141e-07 & 5.3694783e-05 & 8.8380282e-07 \\
			           & $\|\vec{e}\|_{3,4}$  & 3.3959106e-07 & 4.4202167e-07 & 5.3694984e-01 & 8.8403766e-03 \\
                        \hline
                        $10^{-5}$  & $\|\vec{e}\|_{1,2}$  & 3.3491766e-07 & 4.4119696e-07 & 1.6746016e-04 & 8.8239392e-07 \\
			           & $\|\vec{e}\|_{3,4}$  & 3.3491975e-07 & 4.4119442e-07 & 1.6746022e+01 & 8.8238885e-02 \\
                        \hline
		\end{tabular}
	\end{adjustbox}
	\label{tab:error,q,dx}
\end{table}

\end{document}


TITLE: Covering of a $2\times 3$ rectangle using smaller rectangles
QUESTION [3 upvotes]: We have a $2 \times 3$ rectangle, that we wish to cover using $1 \times 2$ rectangles and $1 \times 1$ squares.  How many possible ways are there to do so?

Using $0$ and $3$ rectangles, it appears that there are only $2$ possible combinations. Using $1$ rectangle, we can get $7$ solutions. Determining the number of solutions when two rectangles are used appears to be the tricky part.

REPLY [3 votes]: With $0$ rectangles there is one way, as you say. However, with $3$ rectangles, there are $3$ ways, not $1$. With $1$ rectangle, there are $7$ ways, as you say.
For $2$ rectangles, they can either both extend in the shorter direction, in $3$ ways, or both in the longer direction, in $4$ ways, or one in each direction, in $4$ ways.
The total is $1+3+7+3+4+4=22$.
[Edit in response to comment:]
Let's say the $2\times3$ rectangle has $2$ rows and $3$ columns. For $2$ rectangles, if they both extend along the columns, they occupy one column each, leaving one column for the squares, and there are $3$ choices for that column. If they both extend along the rows, they have to be in different rows, and each has two possible positions in its row, which makes $2\cdot2=4$ options. If they extend in different directions, one occupies a column, and this can't be the central column, so there are $2$ choices for the column, and in each case there are $2$ choices which row to put the other one in, for another $2\cdot2=4$ options.


TITLE: Reference Request: Grouplike Algebras over the little $n$-cubes operad are $n$-fold loop spaces
QUESTION [8 upvotes]: In Geometry of the iterated loop space, Peter May proved his famous recognition theorem, which is, in a simple form, stated on page 3 as the following.

There exist $\Sigma$-free operads $\mathcal{C}_n$, $1\le n\le \infty$, such that every n-fold loop space is a $\mathcal{C}_n$-space and every connected $\mathcal{C}_n$-space has the weak homotopy type of an $n$-fold loop space.

For $\mathcal{C}_n$ the explicit example constructed in Peter May's book is the operad of little $n$-cubes.
However, there is a stronger version of the recognition theorem for grouplike $\mathcal{C}_n$-spaces spread all over the literature (e.g. at the nLab).
Although I'm absolutely not an expert in this field, I believe it should not be hard to prove the stronger form with the help of the techniques developed in May's book as soon as one dwelled on. (Is this the case? Is there a reason May did not state and prove the stronger version?)
Is there a reference for the stronger version that one can use if one does not want to expect the readers to be capable extending May's proof? I don't want to expect any knowledge of higher category theory, so Lurie's text on $E_k$-algebra does not fulfill my needs.

REPLY [10 votes]: May gave a proof in the case $n = \infty$ in this followup paper to "Geometry of iterated loop spaces," which relies on knowing that a certain map (from a free algebra on $X$ to the free infinite loop space on $X$) is a group-completion map. On page 67 he asserted "I am reasonably certain that $\alpha_n: \mathcal C_n X \to \Omega^n \Sigma^n X$ is a group completion [...] but a rigorous calculation of $H_* \mathcal C_n X$ is not yet available." I believe that the lack of this calculation is the reason why the nonconnected case was not addressed.
The calculation happened in of Cohen-Lada-May's "The homology of iterated loop spaces." The group completion theorem is in part III, section 3, corollary 3.3 (page 226).