text:
\begin{document}

\maketitle

\vspace{-1cm}
\begin{abstract}
In this paper we show that for integers $s\geq2$, $t\geq1$,
any co-edge-regular graph which is cospectral with the $s$-clique extension of the $t\times t$-grid
is the $s$-clique extension of the $t\times t$-grid, if $t$ is large enough.
Gavrilyuk and Koolen used a weaker version of this result to show that the Grassmann graph $J_q(2D,D)$
is characterized by its intersection array as a distance-regular graph, if $D$ is large enough.
\end{abstract}
\centerline{{\bf 2010 Mathematics Subject Classification:} 05C50, 05C75, 05E30}
\begin{quote}
{\bf Keywords:}
Clique extensions; Graph eigenvalues; Interlacing; Co-edge-regular graphs; Walk-regular graphs; Spectral characterizations
\end{quote}

\section{Introduction}\label{sec1}

For undefined terminologies, see the next section. For the definitions related to distance-regular graphs, see \cite{BCN89,DaKoTa}.\\

Recall that a regular graph is co-edge-regular, if there exists a constant $\mu$ such that
any two distinct and non-adjacent vertices have exactly $\mu$ common neighbors.
Our main result in this paper is as follows:
\begin{theorem}\label{main-result}
Let $\G$ be a co-edge-regular graph with spectrum
\begin{equation*}
\{\big(s(2t+1)-1\big)^{1},(st-1)^{2t},(-1)^{(s-1)(t+1)^{2}},(-s-1)^{t^2}\},
\end{equation*}
where $s\geq2$ and $t\geq1$ are integers. If $t\geq11(s+1)^3(s+2)$, then $\G$ is the $s$-clique extension
of the $(t+1)\times(t+1)$-grid.
\end{theorem}
\vspace{0.2cm}

For $s=2$, Yang et al. \cite{YAK17} gave a similar characterization by using Hoffman graphs.
The advantage of their method is that they do not need co-edge-regularity, but their method
seems difficult to generalize to graphs with smallest eigenvalue less than $-3$.\\

In \cite{GK2018}, Gavrilyuk \& Koolen showed that any local graph, say $\Delta$,
of a distance-regular graph $\G$ with the same intersection array as a $J_q(2D,D)$ is co-edge-regular
with constant $\mu=2q$ and it has the same spectrum as the $q$-clique extension of a
$\frac{q^{D}-1}{q-1}\times \frac{q^{D}-1}{q-1}$-grid, if $D\geq4$. So our main result shows
that any local graph $\Delta$ of $\G$ is really the $q$-clique extension of a
$\frac{q^{D}-1}{q-1}\times \frac{q^{D}-1}{q-1}$-grid, if $D$ is large enough. Gavrilyuk \& Koolen \cite{GK2018}
used the $Q$-polynomial property of the distance-regular graph $\G$ to conclude that any local graph of $\G$ is the
$q$-clique extension of a $\frac{q^{D}-1}{q-1}\times \frac{q^{D}-1}{q-1}$-grid.
Using this fact, they showed that the distance-regular graph $\G$
has to be the Grassmann graph $J_q(2D,D)$, if $D$ is large enough.\\

Another motivation comes from the lecture notes \cite{Terwilliger}. In these notes, Terwilliger
shows that any local graph of a thin $Q$-polynomial distance-regular graph is co-edge-regular
and has at most five distinct eigenvalues. So it is interesting to study co-edge-regular graphs
with a few distinct eigenvalues.\\

A further motivation is as follows.
Strongly regular graphs have attracted a lot of attention, see for example
the survey papers \cite{BV84,Seidel79}. On the other hand, there are only a few papers
on regular graphs with four distinct eigenvalues, see for example \cite{vD95,vD99,VS98,HH17}.
We think that connected co-edge-regular graphs with four distinct
eigenvalues is an interesting class of graphs as they are related to association schemes with
three classes. We believe that some strong results can be obtained for this class
of graphs. For example, we believe the following conjecture is true.

\vspace{0.1cm}
\begin{conjecture}\label{conj1}
Let $\G$ be a connected co-edge-regular graph with four distinct eigenvalues. Let
$t\geq2$ be an integer and $|V(\G)|=n(\G)$. Then there exists a constant $n_{t}$ such that, if $\theta_{\min}(\G)\geq -t$
and $n(\G)\geq n_t$ both hold, then $\G$ is the $s$-clique extension of a strongly regular graph, for some $2\leq s\leq t-1$.
\end{conjecture}
\vspace{0.2cm}

Note that for any integer $s\geq2$, the $s$-clique
extension of a connected non-complete strongly regular graph is co-edge-regular and has four distinct
eigenvalues. The main result of this paper can be seen as a first step towards Conjecture \ref{conj1}.

\section{Preliminaries}

\subsection{Definitions}

Let $G$ be a simple connected graph on vertex set $V(G)$ with $n=|V(G)|$, edge set $E(G)$ and adjacency matrix $A$.
The eigenvalues of $G$ are the eigenvalues of $A$. Let $\theta_{0},\theta_1,\ldots,\theta_t$
be the distinct eigenvalues of $G$ and $m_i$ be the multiplicity of $\theta_i$ ($i=0,1,\ldots,t$).
Then the multiset $\{\theta_0^{m_0},\theta_1^{m_1},\ldots,\theta_t^{m_t}\}$ is called the \emph{spectrum} of $G$.
Two graphs are called \emph{cospectral}, if they have the same spectrum.\\

For two distinct vertices $x$ and $y$, we write $x\sim y$ (resp. $x\nsim y$)
if they are adjacent (resp. nonadjacent) to each other. For a vertex $x$ in $G$, we define
$N_{G}(x)=\{y\in V(G)\mid y\sim x\}$, and $N_{G}(x)$ is called the \emph{neighborhood} of $x$.
The graph induced by $N_{G}(x)$ is called the \emph{local graph} of $G$ with respect to $x$ and is denoted by $G(x)$.
We call $d_{x}:=|N_{G}(x)|$, the \emph{valency} of $x$.
We denote the number of common neighbors between two distinct vertices $x$ and $y$
by $\lambda_{x,y}$ (resp. $\mu_{x,y}$) if $x\sim y$  (resp. $x\nsim y$).\\

A regular graph with $n$ vertices and valency $k$ is called \emph{co-edge-regular} with parameters
$(n,k,\mu)$, if any two nonadjacent vertices have precisely $\mu=\mu(G)$ common neighbors.
Moreover, a co-edge-regular graph is called \emph{strongly regular} with parameters $(n,k,\lambda,\mu)$
if, in addition, any two adjacent vertices have precisely $\lambda=\lambda(G)$ common neighbors.
A graph $G$ is called \emph{walk-regular}, if for all $r$, the number of closed walks of length $r$
from a given vertex $x$ is independent of the choice of $x$. Since this number equals $A^{r}_{xx}$, it
is the same as saying that $A^{r}$ has constant diagonal for all $r$.\\

Recall that a \emph{clique} (or a complete graph) is a graph
in which every pair of vertices is adjacent. A $t$\emph{-clique} is a clique with $t$ vertices
and is denoted by $K_{t}$, where $t$ is a positive integer.
The $t\times t$\emph{-grid} is the Cartesian product $K_{t}\Box K_{t}$.
Note that the $t\times t$-grid is strongly regular with parameters $(t^2,2t-2,t-2,2)$.
The spectrum of the $t\times t$-grid is $\big\{(2t-2)^1,(t-2)^{2(t-1)},(-2)^{(t-1)^{2}}\big\}$.\\

The \emph{Kronecker product} $M_1\otimes M_2$ of two matrices $M_1$ and $M_2$
is obtained by replacing the $ij$-entry of $M_1$ by $(M_1)_{i,j}M_{2}$ for all $i$ and $j$.
Note that if $\tau$ and $\eta$ are eigenvalues of $M_1$ and $M_2$ respectively, then $\tau\eta$
is an eigenvalue of $M_1\otimes M_2$. We refer to \cite[Section 9.7]{GD01} for a detailed treatment on
the Kronecker product of matrices and graph eigenvalues.

\subsection{Clique extensions of the square grid graphs}\label{subsec2.3}

In this subsection, we define $s$-clique extensions of graphs and we will give some specific results for the
the $s$-clique extension of the square grid graphs.\\

For a positive integer $s$, the \emph{$s$-clique extension} of $G$ is the graph $\widetilde{G}$ obtained from
$G$ by replacing each vertex $x\in V(G)$ by a clique $\widetilde{X}$ with $s$ vertices, such that $\tilde{x}\sim\tilde{y}$
(for $\tilde{x}\in \widetilde{X},~\tilde{y}\in \widetilde{Y}$) in $\widetilde{G}$ if and only if
$x\sim y$ in $G$. If $\widetilde{G}$ is the $s$-clique extension of $G$, then $\widetilde{G}$ has adjacency matrix $J_{s}\otimes(A+I_n)-I_{sn}$,
where $J_s$ is the all-ones matrix of size $s$ and $I_n$ is the identity matrix of size $n$. In particular, if $G$ has spectrum
\begin{equation}\label{G-spectrum}
\{\theta_0^{m_0},\theta_1^{m_1},\ldots,\theta_t^{m_t}\},
\end{equation}
then it follows that the spectrum of $\widetilde{G}$ is
\begin{equation}\label{sclique-spectrum}
\big\{\big(s(\theta_0+1)-1\big)^{m_0}, \big(s(\theta_1+1)-1\big)^{m_1},\ldots,\big(s(\theta_t+1)-1\big)^{m_t},(-1)^{(s-1)(m_0+m_1+\ldots+m_t)}\big\}.
\end{equation}
\\
\vspace{-0.6cm}

In case that $G$ is a connected regular graph with valency $k$ and with adjacency matrix $A$ having exactly four distinct eigenvalues
$\{\theta_0=k,\theta_1,\theta_2,\theta_3\}$, then $A$ satisfies the following (see for example \cite{H63}):
\begin{equation}\label{eq-hoffman-poly}
A^{3}-\bigg(\sum\limits_{i=1}^{3}\theta_i\bigg)A^{2}+\bigg(\sum\limits_{1\leq i<j\leq3}\theta_i\theta_j\bigg)A-\theta_1\theta_2\theta_3I=
\frac{\prod_{i=1}^{3}(k-\theta_i)}{n}J.
\end{equation}
This implies that $G$ is walk-regular, as was also shown in \cite{vD95}.\\

Now we assume that $\G$ is a cospectral graph with the $s$-clique extension of $(t+1)\times(t+1)$-grid, where $s\geq2$ is an integer.
Then by (\ref{G-spectrum}) and (\ref{sclique-spectrum}), the graph $\G$ has spectrum
\begin{equation}\label{sclique-grid-spectrum}
\big\{\theta_{0}^{m_0},\theta_{1}^{m_1},\theta_{2}^{m_2},\theta_{3}^{m_3}\big\}=
\big\{\big(s(2t+1)-1\big)^{1},(st-1)^{2t},(-1)^{(s-1)(t+1)^{2}},(-s-1)^{t^2}\big\}.
\end{equation}
Using (\ref{eq-hoffman-poly}) we obtain
\begin{equation*}
A^{3}+(3+s-st)A^{2}+(3+2s-s^2t-2st)A+(1+s-s^2t-st)I=2s^2(2t+1)J.
\end{equation*}
Thus, we have
\begin{equation}\label{walk-regularity}
A^{3}_{(x,y)}=\left\{
  \begin{array}{ll}
    2s^2t^2+4s^2t-6st+s^2-3s+2, & \hbox{\textrm{if}~$x=y$;} \\
    5s^2t+2st+2s^2-2s-3-(3+s-st)\lambda_{x,y}, & \hbox{\textrm{if}~$x\sim y$;} \\
    4s^2t+2s^2-(3+s-st)\mu_{x,y}, & \hbox{\textrm{if}~$x\nsim y$.}
  \end{array}
\right.
\end{equation}
\\

Applying the Hoffman bound \cite[Lemma 9.6.2]{GD01} to the complement of $\G$, we obtain:
\begin{lemma}\label{lem2}
Let $\G$ be a graph that is cospectral with the $s$-clique extension of the $(t+1)\times(t+1)$-grid, where $s\geq2$, $t\geq1$ are integers.
For any clique $C$ of $\G$, say with order $c$, we have $c\leq st+s$.
If equality holds, then every vertex $x\in V(\G)-V(C)$ has exactly $s$ neighbors in $C$.
\end{lemma}

\section{Lines in $\G$}\label{sec3}

At the end of Subsection \ref{subsec2.3}, we assumed that $\G$ is a graph cospectral with the $s$-clique extension of the $(t+1)\times(t+1)$-grid, where $s \geq 2$ and $t \geq 1$ are integers.
This implies that $\G$ is walk-regular.
For this section and the next three sections, we assume that $\G$ is co-edge-regular as well, i.e. there exists
exactly $\mu$ number of common neighbors between any two nonadjacent vertices of $\G$.
Note that, from the spectrum of the $s$-clique extension of the $(t+1)\times (t+1)$-grid, we obtain that $\mu=2s$.\\

Let $\G(\infty)$ be the local graph of $\G$ at vertex $\infty$. Assume that the vertices of $\G(\infty)$ have valencies
$d_1,\ldots,d_k$, where $k=s(2t+1)-1$. Then, as $\G$ is walk-regular and co-edge-regular, we obtain that
the number of walks of length two inside $\G(\infty)$ is same as in the local graph of the $s$-clique extension of
the $(t+1)\times(t+1)$-grid. Using (\ref{walk-regularity}), this implies that the sum of valencies and
the sum of square of valencies of vertices in $\G(\infty)$ are constant, and are given by the following equations, where $\varepsilon$ is the number of edges inside $\G(\infty)$.
\begin{equation}\label{local-valencies-sum}
2\varepsilon =\sum\limits_{i=1}^{k}d_i= 2st(st+2s-3)+s^{2}-3s+2,
\end{equation}
\begin{equation}\label{local-valencies-square-sum}
\sum\limits_{i=1}^{k}(d_i)^{2}= 2st(s^2t^2+4s^2t-6st+3s^2-10s+8)+s^3-5s^2+8s-4.
\end{equation}
By (\ref{local-valencies-sum}) and (\ref{local-valencies-square-sum}), we obtain the following equation.
\begin{equation}\label{primal-eqn}
\sum\limits_{i=1}^{k}\big(d_i-(st+s-2)\big)^{2}=s^2t^2(s-1).
\end{equation}
It turns out that (\ref{primal-eqn}) is of crucial importance in proving our main result.\\

It is straightforward to show the following lemma. We will use it later.
\begin{lemma}\label{integers-lemma}
Let $a,~b,~p$ and $q$ be some integers satisfying $0\leq q\leq p\leq a$ and $b\leq a$. If $p+q=a+b$, then $p^2+q^2\leq a^2+b^2$.
\end{lemma}

We call a maximal clique a line, if it contains at least
$\frac{3}{4}s(t+2)$ vertices. The following result shows the existence of lines in $\G$.
\begin{proposition}\label{prop1}
Let $\G$ be a co-edge-regular graph, that is cospectral with the $s$-clique extension of the $(t+1)\times(t+1)$-grid, where $s \geq 2$ and $t \geq 1$ are integers.
If $t\geq 11(s+1)^3(s+2)$, then any vertex in $\G$ lies on exactly two lines.
\end{proposition}
\begin{proof}
Note that $\G$ is regular with valency $k=s(2t+1)-1$, and co-edge-regular with constant $\mu=2s$.
Let $\infty$ be a vertex of $\G$ and $\G(\infty)$ be its local graph. As before let $\varepsilon$ be the number of edges inside $\G(\infty)$.
We first obtain a lower bound on $\varepsilon$.
By (\ref{local-valencies-sum}) we obtain
\begin{equation}\label{ineq-bounds}
2\varepsilon \geq 2s^2t^2,
\end{equation}as $s \geq 2$.
Now we derive an upper bound on $\varepsilon$.
Let $P$
be a coclique with maximum order in $\G(\infty)$ with vertex set $\{x_1,x_2,\ldots,x_p\}$.
Then by the interlacing theorem \cite[Theorem 9.5.1]{GD01}, we have $p\leq (s+1)^{2}$, as $\theta_{\min}=-s-1$,
where $\theta_{\min}$ is the smallest eigenvalue of $\G$.
We define
\begin{center}
$B:=\{y\sim\infty\mid$ $y$ has at least two neighbors in $P\}$.
\end{center}
Let $b$ be the cardinality of $B$. Then
\begin{equation}\label{b-eqn}
b\leq (2s-1){p\choose 2}\leq sp(p-1)\leq s^{2}(s+1)^{2}(s+2),
\end{equation}
as $\mu=2s$. We also define the sets $A_i$ such that
\begin{center}
$A_i:=\{y\sim\infty\mid$ $y$ has only $x_i$ as its neighbor in $P\}\cup\{x_{i}\}$,
\end{center}
where $a_i:=|A_i|$. Note that, if $\mathcal{A}:=\bigcup\limits_{i}A_i$, then $\mathcal{A}\bigcup B=V\big(\G(\infty)\big)$.
Note further that any two vertices in $A_i$ are adjacent, because $P$ is maximum.
Thus, for every $i$, $A_i$ is a clique in $\G(\infty)$.
\\

Now, inside $\mathcal{A}$, we have at most $\frac{1}{2}\big(\sum\limits_{i}a_i(a_{i}-1)+(p-1)(2s-1)\sum\limits_{i}a_i\big)$ edges,
inside $B$, we have at most $\frac{1}{2}b(b-1)$ edges and between $\mathcal{A}$ and $B$, we have at most $b(k-b)$ edges.
Then, by counting these number of edges in $\G(\infty)$, we obtain
\begin{eqnarray}\label{epsilon}
\nonumber 2\varepsilon&\leq&\sum\limits_{i}a_i(a_{i}-1)+b(b-1)+2(k-b)b+(p-1)(2s-1)\sum\limits_{i}a_{i}\\
\nonumber &\leq&\sum\limits_{i}a_i(a_{i}-1)+2(k-1)b+(p-1)(2s-1)\sum\limits_{i}a_{i}\\
\nonumber &\leq&\sum\limits_{i}a_i(a_{i}-1)+2(k-1)s^{2}(s+1)^{2}(s+2)+k(s^2+2s)(2s-1)~~~~~~~~~~~~\big(\textrm{as}~~\sum\limits_{i}a_{i}\leq k\big)\\
\nonumber &\leq&\sum\limits_{i}a_i(a_{i}-1)+4s^{3}(s+1)^{2}(s+2)(t+1)+4s^2(s+1)^2(t+1)~~~\big(\textrm{as}~~k=s(2t+1)-1\leq2s(t+1)\big)\\
&\leq&\sum\limits_{i}a_i(a_{i}-1)+4s^2(s+1)^3(s+2)(t+1).
\end{eqnarray}
Without loss of generality, we may assume that $a_1\geq a_2\geq\ldots\geq a_p\geq1$. By Lemma \ref{lem2},
we have $a_1< s(t+1)$. Assume that $\G$ has at most one line through $\infty$. Then
$a_1<s(t+1)$, $a_2\leq \frac{3}{4}s(t+2)$ and $\sum\limits_{i}a_{i}\leq k < 2s(t+1).$ Using Lemma \ref{integers-lemma}, we obtain
\begin{equation}\label{upper-bound-ai}
\sum\limits_{i}a_i(a_{i}-1)< \sum\limits_{i}a_i^2< \big(s(t+1)\big)^2+\bigg(\frac{3}{4}s(t+2)\bigg)^2+\bigg(\frac{1}{4}s(t+2)\bigg)^2 <\frac{13}{8}\big(s(t+2)\big)^2 .
\end{equation}
Combining (\ref{ineq-bounds}), (\ref{epsilon}) and (\ref{upper-bound-ai}), we obtain
\begin{equation}\label{new}
2s^2t^2 \leq 2 \varepsilon \leq \frac{13}{8}\big(s(t+2)\big)^2 +4s^2(s+1)^3(s+2)(t+1).
\end{equation}
As $$t \geq11(s+1)^3(s+2)> 600, \ \ \ \ (s \geq 2)$$
we find $t+2<\frac{201}{200}t$. Putting this in (\ref{new}), we obtain a contradiction.\\

\noindent Thus, if $t\geq11(s+1)^3(s+2)$, we obtain that every vertex
in $\G$ lies on at least two lines. Let $C_1$ and $C_2$ be these two lines and $m:=| V(C_1)\bigcap V(C_2)|$. Since $\G$
is co-edge-regular with $\mu=2s$, we obtain that $m\leq 2s$. As $3\times \frac{3}{4}s(t+2)-6s > 2s(t+1) > k$, we find that every vertex
in $\G$ lies on at most two lines. This shows the proposition.
\end{proof}

Now we prove the following property for lines through a vertex.
\begin{lemma}\label{l+m=s-1}
Let $\G$ be a co-edge-regular graph, that is cospectral with the $s$-clique extension of the $(t+1)\times(t+1)$-grid,
where $s \geq 2$ and $t \geq 1$ are integers.
Let $\infty$ be a vertex of $\G$. Let $C_1$ and $C_2$ be the two lines through $\infty$. Let $\ell:=|\{y\mid y\notin V(C_1)\bigcup V(C_2) \}|$
and $m:=| V(C_1)\bigcap V(C_2)|$. If $t\geq11(s+1)^3(s+2)$, then $\ell+m=s$, and both $C_1$ and $C_2$ have at least $s(t-1)+1$ vertices and at most
$s(t+1)$ vertices.
\end{lemma}
\begin{proof}
Let $\G(\infty)$ be the local graph corresponding to vertex $\infty$ of $\G$, with vertex set $\{ x_1, x_2, \ldots , x_k\}$. For $1\leq i\leq k$, let $d_{i}$ be the valency of vertex in $\G(\infty)$.
Without loss of generality, we may assume that $\{ x_1, x_2, \ldots, x_{\ell}\}$ are the vertices in $\G$ which do not lie in either $C_1$ or $C_2$.
Note that for $x_i\notin V(C_1)\bigcup V(C_2)$, we have $d_{i}\leq (6s-3)+\frac{1}{2}s(t+1)$. This, in turn,  implies, using
(\ref{primal-eqn})

\begin{eqnarray}\label{Eqz2}
\nonumber s^{2}t^{2}(s-1) =\sum\limits_{i=1}^{k}\big(d_{i}-(st+s-2)\big)^2&\geq&\sum\limits_{y\notin V(C_1)\bigcup V(C_2)}\big(d_{y}-(st+s-2)\big)^2\\
\nonumber&\geq&\ell\bigg(\frac{1}{2}s(t+1)-6s\bigg)^2\\
&=&\ell\bigg(\frac{1}{4}\big(s(t-11)\big)^2\bigg).
\end{eqnarray}
Hence we find that
\begin{equation}\label{claimh1}
\ell\leq 5s,
\end{equation}
as $t\geq11(s+1)^{3}(s+2)>100$.\\

By (\ref{claimh1}), it follows that
\begin{eqnarray}\label{jack1}
\nonumber s(t+1)\geq|V(C_j)|&\geq& 1+ k - s(t+1)-  \ell \\
\nonumber &\geq& 2s(t+1) -s(t+1) - 5 s\\
&=&st-5s
\end{eqnarray}
for $j=1,2$.

Now we are going to refine the estimates for the number $\varepsilon$  of edges in $\G(\infty)$. This will give the following claim.

\begin{claim}\label{claim2}
$\ell+m=s$.
\end{claim}
\noindent{\bf Proof of Claim \ref{claim2}.}
Let $X:=V(C_1)\bigcap V(C_2)-\{\infty\}$, $Y:=V(C_1)\triangle V(C_2)$, and $Z:=\G(\infty)-V(C_1)\bigcup V(C_2)$. For $u \in X \bigcup Y \bigcup Z$, we will write $d_u$ for the valency of $u$ inside $\G(\infty)$. So we need to estimate $|X| + |Z| = \ell + m -1$.

\noindent For $x\in X$, we have
\begin{equation*}\label{sakka2}
2s(t+1)-5s\leq d_{x}\leq k-1=s(2t+1)-2.
\end{equation*}
\noindent Now, for $y\in Y$, (\ref{jack1}) and $\mu = 2s$ give us
\begin{equation*}\label{sakka4}
     st - 5s -1 \leq   d_y \leq s(t+1) -2 + 2s-1.
\end{equation*}
\noindent Moreover, for $z \in Z$, we have
\begin{equation*}\label{sakka1}
d_{z}\leq 2s-1+2s-1+\ell-1\leq 9s-2.
\end{equation*}
\noindent So, for $u\in X\bigcup Z$, we have
\begin{equation*}\label{sakka3}
st-8s\leq d_{u}-st- s+2 \leq st +1,
\end{equation*}
and for $y \in Y$ we have
\begin{equation*}\label{sakka}
|d_y - st-s +2| \leq 6s.
\end{equation*}

\noindent By using the above expressions and (\ref{primal-eqn}), we obtain
\begin{eqnarray}\label{sakka5}
\nonumber (\ell+m-1)\big(st-8s\big)^2 &\leq& \sum\limits_{v \in X \cup Z}\big(d_{v}-(st+s-2)\big)^{2}\\
\nonumber &\leq & \sum\limits_{v\sim \infty}\big(d_{v}-(st+s-2)\big)^{2}=s^2t^2(s-1)\\
&\leq &(\ell+m-1)(st+s)^2+2st(6s)^2.
\end{eqnarray}
By simplifying (\ref{sakka5}), we obtain
\begin{equation}\label{sakka6}
\frac{t^2(s-1)-72st}{(t+1)^2}\leq\ell+m-1\leq\frac{s^2t^2(s-1)}{\big(s(t-8)\big)^2}.
\end{equation}
If $t\geq11(s+1)^3(s+2)> 200$, then (\ref{sakka6}) implies that
\begin{equation*}
s-2<\ell+m-1 <s.
\end{equation*}
This shows that $\ell+m=s$.
\qed
\\

As, by Proposition \ref{prop1} we have that every vertex lies in two lines, we obtain using Claim \ref{claim2} that
for a line $C$ in $\G$ with order $c$, we have $s(t-1)+1\leq c\leq s(t+1)$, if $t\geq11(s+1)^3(s+2)$.
This shows the lemma.
\end{proof}

As a consequence of Lemma \ref{l+m=s-1}, we show the following result.
\begin{lemma}\label{c1+c2=2m+2st}
Let $\G$ be a co-edge-regular graph, that is cospectral with the $s$-clique extension of the $(t+1)\times(t+1)$-grid, where $s\geq2$ and $t\geq1$ are integers.
Let $C_1$ and $C_2$ be two lines with respective order $c_1$ and $c_2$. Assume that $C_1$ and $C_2$ intersect in exactly
$m$ vertices, where $m\geq1$. If $t\geq11(s+1)^3(s+2)$, then $c_{1}+c_{2}=2st+2m$.
\end{lemma}
\begin{proof}
Let $x\in V(C_1)\bigcap V(C_2)$. Let $\ell=|\G(x)-V(C_1)-V(C_2)|$. Then we have
\begin{equation*}
(c_1-m)+(c_2-m)+m-1+\ell=k=s(2t+1)-1.
\end{equation*}
If $t\geq11(s+1)^3(s+2)$, then, by Lemma \ref{l+m=s-1},  we have $\ell+m=s$. Hence we obtain
\begin{equation*}
c_{1}+c_{2}=2st+2m.
\end{equation*}
\end{proof}

\section{The order of lines}\label{sec4}

In this section we will show the following lemma on the order of lines.
\begin{lemma}\label{sum-of-cliques-pairs} Let $s \geq 2$ and $t \geq 1$ be integers.
Let $\G$ be a co-edge-regular graph, that is cospectral with the $s$-clique extension of the $(t+1)\times(t+1)$-grid.
 Let $q_{i}$ be the number of lines of order $s(t-1)+i$ in $\G$ where $i=1,\ldots,2s$ and $\delta = \sum\limits_{i=1}^{2s} q_i$ be the number of lines in $\Gamma$.
Assume $t\geq11(s+1)^3(s+2)$. Then
\begin{equation}\label{main-eqn}
\sum\limits_{i=1}^{2s}\big(s(t-1)+i\big)q_{i}=2s(t+1)^{2}
\end{equation} holds, and the number $\delta$ satisfies
\begin{equation}\label{total-cliques-ineq}
2t+2\leq\delta\leq2t+6,
\end{equation}
where $\delta=2t+2$ implies that $q_{i}=0$ for all $i<2s$ and $q_{2s}=2t+2$.\\

\noindent Let $\alpha := \delta - 2t -2$. Then $\alpha \in \{0, 1, 2, 3, 4\}$ and
\begin{equation}\label{eqz3}
\sum\limits_{i=1}^{2s}(2s-i)q_i =\alpha s(t+1)
\end{equation}
holds.
\end{lemma}
\begin{proof}
Assume $t\geq11(s+1)^3(s+2)$.
By Lemma \ref{l+m=s-1}, any vertex lies on exactly two lines and each line has
at least $st-s+1$ and at most $st+s$ vertices.
\noindent Now consider the set
\begin{equation*}
W=\{(x,C)\mid x\in V(C),~\mathrm{where}~C~\mathrm{is~a~line}\}.
\end{equation*}
Then, by double counting the cardinality of the set $W$, we obtain (\ref{main-eqn}).\\

\noindent By (\ref{main-eqn}), we obtain that
\begin{equation*}
\delta=\sum\limits_{i=1}^{2s}q_i<\sum\limits_{i=1}^{2s}\frac{s(t-1)+i}{s(t-1)}q_{i}=\frac{2(t+1)^2}{t-1}=2(t+3)+\frac{8}{t-1}.
\end{equation*}
Thus, if $t\geq10$, then we obtain
\begin{equation*}
\delta\leq2t+6.
\end{equation*}
In a similar fashion, we obtain
\begin{equation*}
\delta\geq\sum\limits_{i=1}^{2s}\frac{s(t-1)+i}{s(t+1)}q_{i}=2(t+1).
\end{equation*}
This shows that  $\delta\geq2t+2$  and $\delta=2t+2$
implies that all lines have order $st+s$.\\

Let $\alpha:=\delta-2t-2$. Then $\alpha\in\{0,1,2,3,4\}$. From (\ref{main-eqn}), we find
\begin{equation*}
\sum\limits_{i=1}^{2s}(2s-i)q_i =\sum\limits_{i=1}^{2s} s(t+1)q_{i} -\sum\limits_{i=1}^{2s}\big(s(t-1)+i\big)q_{i} =\big(\delta-2(t+1)\big)s(t+1) = \alpha s(t+1).
\end{equation*}
This shows (\ref{eqz3}).
This completes the proof.
\end{proof}

\section{The neighborhood of a line}
In this section we will show the following proposition.
\begin{proposition}\label{propneigh}
Let $\G$ be a graph that is cospectral with the $s$-clique extension of the $(t+1)\times(t+1)$-grid, where $s \geq 2$ and $t \geq 1$ are integers.
If  $t\geq11(s+1)^3(s+2)$, then $\G$ contains exactly $2t+2$ lines.
\end{proposition}
\begin{proof}
In Lemma \ref{sum-of-cliques-pairs}, we have seen that the number $\delta$ of lines satisfies $2t+2 \leq \delta \leq 2t +6$.
Now we will assume that $\delta \geq 2t+3$, in order to obtain a contradiction.  We will show this contradiction in a number of claims.
In order to obtain this contradiction, we will look at the neighborhood of a line in $\G$.\\

Note that the condition $t\geq11(s+1)^3(s+2)$ implies $t \geq 5s \geq 10$, which we will use several times below.
As before, let $q_{i}$ be the number of lines of order $s(t-1)+i$ in $\G$, where $i=1,\ldots,2s$.
Let $h$ be minimal such that $q_{h}\neq0$. Fix a line $C$ with exactly $s(t-1)+h$ vertices.
Let $q'_i:=q'_{i}(C)$ be the number of lines $C'$ with $s(t-1)+i$ vertices that intersect $C$
in at least one vertex. Let $\tau$ be the number of lines that intersect $C$ in at least one vertex. Note that by Lemma \ref{c1+c2=2m+2st}, we obtain that
\begin{equation}\label{primal1}
|V(C)\bigcap V(C')|=\frac{h+i-2s}{2}.
\end{equation}
This means that $q'_i =0 $ if $i < \max\{ h, 2s+2 - h\}$.
We first give the following claim concerning the numbers $\tau$, $q_{i}$ and $q'_{i}$ ($i=h,\ldots,2s$).
\begin{claim}\label{claim1}
The following hold:
\begin{itemize}
   \item[\emph{(i)}] $q'_i =0 $ if $i < \max\{h, 2s+2 - h\}$,
   \item[\emph{(ii)}] $q'_{i}\leq q_{i}$ if $i>h$,
  \item[\emph{(iii)}] $q'_{i}\leq q_{i}-1$ if $i=h$,
  \item[\emph{(iv)}] $\tau=\sum\limits_{i=h}^{2s}q'_{i}\leq\bigg(\sum\limits_{i=h}^{2s}q_{i}\bigg)-1\leq2t+5$,
  \item[\emph{(v)}] $\sum\limits_{i=\max\{h, 2s+2 - h\}}^{2s}q'_{i}\bigg(\frac{h+i-2s}{2}\bigg)=s(t-1)+h$.
\end{itemize}
\end{claim}
\noindent{\bf Proof of Claim \ref{claim1}}.
(i)-(iii) follow easily from the definitions of $q'_i$, $h$ and  $(\ref{primal1})$.
(iv) follows immediately from (i)-(iii).
To show (v), recall that every vertex of $\G$ lies in exactly two lines so this, in particular,
holds for the vertices of $C$. By using (\ref{primal1}) and (i), we obtain (v).
\qed
\\

Next we show that $h\geq s$.
\begin{claim}\label{myclaim0}
$h\geq s$.
\end{claim}
\noindent{\bf Proof of Claim \ref{myclaim0}.}
By Claim \ref{claim1}(ii), (iii) and (v), we have
\begin{eqnarray*}
s(t-1)+h&=&\sum\limits_{i=\max\{h, 2s+2 - h\}}^{2s}q'_{i}\bigg(\frac{h+i-2s}{2}\bigg)\\
&\leq&\sum\limits_{i=h}^{2s}q'_{i}\bigg(\frac{h}{2}\bigg)\\
&<&\sum\limits_{i=h}^{2s}q_{i}\bigg(\frac{h}{2}\bigg)=\frac{h}{2}\delta.\end{eqnarray*}
By $\delta\leq2t+6$, we obtain
\begin{equation}\label{myeqn0}
(t+2)h = (2t+4)\frac{h}{2}\geq s(t-1).
\end{equation}
Since we have $t\geq5s \geq 10$, (\ref{myeqn0}) implies that $h>s-\frac{1}{2}$. This shows the claim.
\qed
\\

Note that Claim \ref{myclaim0} shows that $\frac{h+i-2s}{2} \geq 0$ for all $i \geq h$. Using this, we show that $h \geq \frac{3}{2}s$.
\begin{claim}\label{myclaim1}
$h\geq \lceil\frac{3}{2}s\rceil$.
\end{claim}
\noindent{\bf Proof of Claim \ref{myclaim1}.}
By Claim \ref{claim1} we have
\begin{equation}\label{myeqn1}
\sum\limits_{i=h}^{2s}q_{i}\bigg(\frac{h+i-2s}{2}\bigg)\geq\sum\limits_{i=h}^{2s}q'_{i}\bigg(\frac{h+i-2s}{2}\bigg)=\sum\limits_{i=\max\{h, 2s+2 - h\}}^{2s}q'_{i}\bigg(\frac{h+i-2s}{2}\bigg)=s(t-1)+h.
\end{equation}
Adding twice (\ref{myeqn1}) to (\ref{eqz3}), we obtain
\begin{equation*}
h\delta=h\sum\limits_{i=h}^{2s}q_{i}\geq 2s(t-1)+2h+\alpha s(t+1).
\end{equation*}
As $2t+3 \leq \delta\leq2t+6$, we have
\begin{equation}\label{myeqn3}
h(2t+4)\geq 2s(t-1)+\alpha s(t+1)\geq3st-s.
\end{equation}
This implies that
\begin{equation*}
h\geq \frac{3st-s}{2t+4}=s\bigg(\frac{3t-1}{2t+4}\bigg).
\end{equation*}
Since $t\geq5s\geq 10$, we obtain that $h\geq \lceil\frac{3}{2}s\rceil$.
This shows the claim.
\qed
\\

The following claim gives an upper bound on $h$.
\begin{claim}\label{myclaim2}
$h\leq\lfloor\frac{3}{2}s\rfloor$.
\end{claim}
\noindent{\bf Proof of Claim \ref{myclaim2}.}
As $ \alpha \geq 1$ and  $\delta\leq2t+6$,   we obtain, by (\ref{eqz3}), the following
\begin{equation*}
(2s-h)(2t+6)\geq(2s-h)\sum\limits_{i=h}^{2s}q_{i}\geq s(t+1).
\end{equation*}
This implies that
\begin{equation*}
2s-h\geq\frac{s(t+1)}{2t+6}=\frac{1}{2}s-\frac{2s}{2t+6}.
\end{equation*}
Since $t\geq5s$, it follows that $h\leq\lfloor\frac{3}{2}s\rfloor$.
This shows the claim.
\qed
\\

Claims \ref{myclaim0}, \ref{myclaim1} and \ref{myclaim2} imply the following claim.
\begin{claim}\label{myclaim3}
$h=\frac{3}{2}s$, $\alpha=1$ and $\delta = 2t+3$.
\end{claim}
\noindent{\bf Proof of Claim \ref{myclaim3}.}
By Claims \ref{myclaim1} and \ref{myclaim2}, we obtain $h=\frac{3}{2}s$.
As $h=\frac{3}{2}s$, (\ref{myeqn3}) becomes
\begin{equation*}
\frac{3}{2}s(2t+4)\geq2s(t-1)+\alpha s(t+1).
\end{equation*}
Now, by $ t \geq  5s \geq 10$, we obtain  $\alpha<2$, which implies $\alpha=1$.
This also shows that $\delta = 2t+3.$ This shows the claim.
\qed
\\

Next we show that all lines have order $st + \frac{s}{2}$ and the number $\tau$ of lines that intersect $C$ is equal to  $2t+1$.
\begin{claim}\label{myclaim4}
We have  $\tau = 2t+1$.
\end{claim}
\noindent{\bf Proof of Claim \ref{myclaim4}.}
By Claim \ref{myclaim3} we have $h = \frac{3}{2} s$ and $\delta = 2t+3$. As $\alpha =1$, Eq.  (\ref{eqz3}) gives us
\begin{equation}\label{myeqn5}
\sum\limits_{i=h}^{2s}q_{i}(2s-i)= s(t+1).
\end{equation}
Inserting $h=\frac{3}{2}s$ in Claim \ref{claim1} (v), we obtain
\begin{eqnarray}\label{myeqn6}
\nonumber \sum\limits_{i=h}^{2s}q'_{i}(h-s) &\leq& \sum\limits_{i=h}^{2s}q'_{i}\bigg(\frac{h+i-2s}{2}\bigg)\\
\nonumber &=& s(t-1)+\frac{3}{2}s,\\
&=& s\big(t+\frac{1}{2}\big)
\end{eqnarray}

\noindent
As $\tau=\sum\limits_{i=h}^{2s}q'_{i}$ and $h = \frac{3}{2}s$, we find
\begin{equation}\label{jack}
\frac{1}{2}\tau s= \tau(h-s) \geq s\big(t+\frac{1}{2}\big),
\end{equation}
which implies that
\begin{equation}\label{myeqn7}
\tau\leq2t+1,
\end{equation}
holds.

On the other side, by Claim \ref{claim1} (v) and $h = \frac{3}{2} s$, we have
\begin{equation}\label{myeqn8}
\sum\limits_{i=h}^{2s}q_{i}\bigg(\frac{h+i-2s}{2}\bigg)\geq\sum\limits_{i=h}^{2s}q'_{i}\bigg(\frac{h+i-2s}{2}\bigg)+(\delta-\tau)(h-s)= s\big(t+\frac{1}{2}\big)+(\delta-\tau)\frac{1}{2}s.
\end{equation}
By adding twice (\ref{myeqn8}) to (\ref{myeqn5}), we obtain
\begin{equation}\label{myeqn9}
h\delta=h\sum\limits_{i=h}^{2s}q_{i}\geq2s\big(t+\frac{1}{2}\big)+s(t+1)+(\delta-\tau)s,
\end{equation}
which implies
\begin{equation}\label{myeqn10}
2t+1 - \tau = \delta-\tau\leq\frac{5}{2},
\end{equation}
as $\delta = 2t+3$.
Combining (\ref{myeqn10}) and (\ref{myeqn7}), we find
\begin{equation*}
\tau=2t+1.
\end{equation*}
This shows the claim.
\qed
\\

\noindent As we have equality in (\ref{myeqn7}), and consequently,  in (\ref{jack}) and in (\ref{myeqn6}), we obtain
\begin{equation*}
q'_{i}=0,~(i>h)~~\textrm{and}~~q'_{h}=2t+1.
\end{equation*}

In order to finish the proof of the proposition, we construct a graph $\G'$ whose vertices are the lines in $\G$ where
two lines are adjacent if they intersect in at least one vertex in $\G$.
Let $C'$ be the line that does not intersect $C$. As every vertex of $\G$ lies in two lines
this implies that $C'$ has a common neighbor $C''$ with $C$ in $\G'$. Now replacing $C$
by $C''$, we see that $C'$ has also $s(t-1)+h$ vertices. This means all lines of $\G$ have exactly $s(t-1)+h$ vertices. Hence $\G'$ is a $(2t+1)$-regular graph on $2t+3$ vertices and this  is clearly not possible.
So we obtain a contradiction and this finishes the proof of the proposition.
\end{proof}

\section{Proof of the main result}

In this section we show our main result, namely Theorem \ref{main-result}.\\

\noindent{\bf Proof of Theorem \ref{main-result}.}
Assume $t\geq11(s+1)^3(s+2)$. By Propositions \ref{prop1} and \ref{propneigh} and Lemma \ref{sum-of-cliques-pairs}, we find that there are exactly $2t+2$ lines, each of order $s(t+1)$, and
every vertex $x$ in $\G$ lies on exactly two lines.
Moreover, by Lemma \ref{c1+c2=2m+2st}, the two lines through any vertex $x$ have exactly $s$ vertices in common, and every neighbor of $x$ lies in one of the two lines through $x$.
Now, consider the following equivalence relation
$\mathcal{R}$ on the vertex set $V(\G)$:
\begin{center}
$x\mathcal{R}x'$ if and only if $\{x\}\cup N_{\G}(x)=\{x'\}\cup N_{\G}(x')$, where $x,x'\in V(\G)$.
\end{center}

Every equivalence class under $\mathcal{R}$ contains $s$ vertices and it is the intersection of two lines.
Let us define the graph $\widehat{\G}$ whose vertices are the equivalent classes and two classes, say $S_1$ and $S_2$, are adjacent in $\widehat{\G}$
if and only if any vertex in $S_1$ is adjacent to any vertex in $S_2$. Then $\widehat{\G}$ is a regular graph with valency $2t$,
and $\G$ is the $s$-clique extension of $\widehat{\G}$. Note that the spectrum of $\widehat{\G}$ is equal to
\begin{equation*}
\{(2t)^{1},(t-1)^{2t},(-2)^{t^{2}}\},
\end{equation*}
by the relation of the spectra of $\G$ and $\widehat{\G}$, see
(\ref{G-spectrum}) and (\ref{sclique-spectrum}).
Since $\widehat{\G}$ is a connected regular graph with valency $2t$, and since it has exactly three
distinct eigenvalues, it follows that $\widehat{\G}$ is a strongly regular graph with parameters $\big((t+1)^{2},2t,t-1,2\big)$.\\

From \cite{S59}, it follows that a graph with these parameters is the $(t+1)\times(t+1)$-grid or $t=3$ and the graph is the Shrikhande graph.
But the Shrikhande graph is not possible as $\widehat{\G}$ has cliques of order $t+1$. This completes the proof.
\qed

\section*{Acknowledgements}
Sakander Hayat is supported by a CAS-TWAS president's fellowship at USTC China.
Jack Koolen is supported by the National Natural Science Foundation of China (Nos. 11471009 and 11671376).


TITLE: How can the momentum-position Uncertainty Principle not violate conservation of energy?
QUESTION [1 upvotes]: As far as I understand, the primary reason why an electron doesn't fall into a nucleus is that, when it gets close, it has a sufficiently high probability of having a lot of momentum to get back to its original position. This high probability, in my understanding, arises because the electron is confined to only a small amount of space around the nucleus, and hence, by Heisenberg's Uncertainty Principle,the uncertainty in its momentum is high, which in turn increases the probability of the momentum being large.
In such cases, where the electron "bounces off" or "phases through" the nucleus, the momentum would always have a non-zero magnitude, and hence the kinetic energy would always be non-zero. This way, energy would be gained with each new "bounce". Additionally, the electrons would be constantly accelerating, radiating away light of all frequencies.
Is my premise incorrect, or is it the implication? And in what way is it incorrect?

REPLY [1 votes]: Don't take this the wrong way, but it's pretty much incorrect start to finish because it applies classical reasoning to quantum mechanical systems.  Sometimes semi-classical reasoning can help give us a bit of intuition, but this is not one of those times.
The real answer to this question is simply that electrons are not little balls orbiting a nucleus like planets around the sun.  Electrons bound to an atom do not have well-defined momenta, nor do they have well-defined positions, and the spreads in the possible results of position and momentum measurements obey the uncertainty principle.
Additionally, the conservation of energy takes on a somewhat different character in quantum mechanics because quantum mechanical particles do not generically have well-defined energies either.  It's true that for certain systems (i.e. those which can be described by Hamiltonian operators with no explicit time-dependence) the expectation value of the energy is conserved as the state evolves, but this doesn't correspond to the actual energy of the system at any point in time.


TITLE: Positive semi-definiteness of a matrix whose diagonal elements slightly differ from the sum of the absolute values of other elements in the row
QUESTION [2 upvotes]: I have a matrix which has the following form:
$$
A=
\begin{bmatrix}
a+b-\varepsilon_1 & -a & -b \\
-a & a+c-\varepsilon_2 & -c \\
-b & -c & b+c-\varepsilon_3
\end{bmatrix}
$$
where a, b, c, $\varepsilon_1$, $\varepsilon_2$ and $\varepsilon_3$ are all positive real numbers.
In other words, diagonal elements differ from the sum of the absolute values of other elements in the row (or column since the matrix is symmetric) by some epsilons ($\varepsilon_1$, $\varepsilon_2$, $\varepsilon_3$). If all the epsilons are zero, then according to Gershgorin circle theorem, my matrix is positive semidefinite. However, if epsilons are not zero but small positive values instead, can my matrix still be positive semidefinite. How can I determine a bound for epsilons with respect to other elements of the matrix? I gave 3x3 matrix as an example, but my question is more general. The matrix can be extended a higher dimensional one.

REPLY [1 votes]: As usual, user 1551 is right. A better question would be: if $A$ is symmetric $\geq 0$ , how to choose $\Delta$ symmetric $\geq 0$ in order to obtain $A-\Delta\geq 0$ ?
A sufficient condition is $\sup(spectrum(\Delta))\leq \inf(spectrum(A))$.


TITLE: A question about the smash product
QUESTION [2 upvotes]: Let $K$ be an algebraically closed field and $H$ a finite dimensional semisimple-cosemisimple Hopf $K$-algebra, and let $A$ be a finite dimensional $H$-module algebra and $H^{\ast}= Hom_{K}(H, K)$.
Is $A$ a direct summand of $A \# H \# H^\ast$ as $A$-bimodules?

REPLY [0 votes]: $\text{A#H#H*}$ is isomorphic to $M_n(A)$.
You may check Moss E.Sweedler's textbook: "Hopf algebras" to find the proof


TITLE: Non linear transformation of uniform distribution
QUESTION [0 upvotes]: Let $U$ be uniformly distributed over $[0,1]$. Let $X:=3+U^{1/3}$. What is the cdf and pdf of $X$?
My approach:
The constant factor results in a shift of $3$ to the right, resulting in $\mathbf{P}(3+U^{1/3} \leq b)$ in $[0,1]$ is equal to $\mathbf{P}(U^{1/3} \leq b)$ in $[3,4]$ is equal to  $\mathbf{P}(U \leq b^3)$ in $[3,4]$. From here on I just need to compute the cdf and derive the pdf. Am I on the right track? Please show me the last step(s).

REPLY [2 votes]: Cdf of $U$ is
$$
F_U(t)=\begin{cases}0, & t < 0 \cr t, & 0\leq t <1 \cr 1, & t\geq 1\end{cases}
$$
Therefore
$$
F_X(b)=\mathbb P(3+U^{1/3}<b)=\mathbb P(U^{1/3}<b-3) = \mathbb P(U<(b-3)^3) = F_U((b-3)^3)
$$
$$
=\begin{cases}0,&(b-3)^3 < 0,\cr (b-3)^3, & 0\leq (b-3)^3 < 1, \cr 1, & (b-3)^3 \geq 1.\end{cases} = \begin{cases}0,& b < 3,\cr (b-3)^3, & 3 \leq b < 4, \cr 1, & b \geq 4.\end{cases}
$$
From here you can derive pdf by differentiating cdf.


text:
\begin{document}

\maketitle
\thispagestyle{empty}
\pagestyle{empty}

\begin{abstract}
This paper presents the design of a diagnosis system for the detection, identification and reconstruction of faults in pipelines. The design of such diagnosis system is based on redundant relations and  nonlinear observers, taking into account faults in sensors, damages in pumps, and unknown extractions. The proposed algorithm is developed based on a model described by nonlinear equations of the fluid behavior in a pipeline, considering the principles of conservation of mass and momentum. In order to distinguish among different types of faults and to reconstruct their behavior, the diagnosis system operates in stages. The first stage called \emph{detection \& fault isolation} aims to isolate a fault symptom with a set of redundant relations deduced from the analysis of the model in nominal conditions and assuming measurements of the standard variables at the extremes of the pipeline. In the second stage named \emph{fault reconstruction}, nonlinear observation algorithms estimate the temporal evolution of the isolated fault. The complete diagnosis system is validated through a series of experiments in a hydraulic pilot pipeline of 200 [$m$].
\end{abstract}

\section{Introduction}
The principal purpose of a monitoring automatic system in real time is to locate, as quickly as possible, the presence of faults with the minimal instrumentation and cost. Different physical principles and tools have been considered to design automated systems of aqueducts, pipelines, pumping systems, etc. \cite{stoianov2007}. Usually in pipeline networks, the anomalies to locate in real time are: faults in valves and pumps, leaks in the pipeline body, obstructions, air bubbles, cracks, corrosion, etc. If the pipelines are underground or underwater, in addition to the inability to suspend the process operation, the fault diagnosis becomes an arduous task. Therefore, the diagnosis should be realized considering the dynamical phenomena associated with the fluid. For the detection and location of leaks in pipelines, various models of the static behavior of the fluid have been used \cite{billman:87}. Recently, these models have been successfully extended to the case of pipelines with nonuniform topographic profiles \cite{Gonzalez2013}. Despite their simplicity, the main disadvantage of using these models is that they can not be used when the fluid does not operate around static conditions. For distribution networks, leak detection analysis using time-frequency signals as wavelets have been reported \cite{Al-Shidhani2003}, as well as advanced genetic algorithms \cite{Fuentes2011}. For the automatic monitoring of pipelines is mandatory the continuous improvement of issues related to the hardware and software.
Sensors should be faster and more accurate, and the localization algorithms must be able to discern among a great number of fault scenarios, \emph{i.e.}, the monitoring systems should include fault alarms for sensors and pump systems to become intelligent monitoring systems for pipeline networks \cite{Verde2011}. This fact has motivated the development of this work where the main contribution is a diagnosis system, which considers faults in measuring instruments, damages in pumps and pipeline leaks. The system uses an algorithm with the ability to distinguish among different faults in real time by means of five residuals with faults signatures for each event, and a bank of high gain observers to reconstruct the evolution of the identified fault.

This paper is organized as follows: Section 2 exposes the fluid model in nominal and fault conditions used for the design of the fault diagnosis system; Section 3 contains the overall description of the proposed diagnosis system for five diverse faults. Finally, Sections 4 and 5 show the experimental validation of the proposed approach and some conclusions about it.

\section{Dynamical Model of the fluid}
Assuming convective changes in velocity to be negligible, constant liquid density and constant pipe cross-sectional area, the
momentum and continuity equations governing the dynamics of the
fluid in a horizontal pipeline can be expressed as \cite{Chaudry1979}.
\begin{align}\label{WH}
\nonumber\frac{\partial Q(z,t)}{\partial t}&+a_1\frac{\partial H(z,t)}{\partial z}+\mu Q(z,t)|Q(z,t)|=0\\
\frac{\partial H(z,t)}{\partial t}&+a_2\frac{\partial Q(z,t)}{\partial z}=0
\end{align}
where $(z,t) \in (0,L)\times(0,\infty)$ are the time [$s$] and space
[$m$] coordinates respectively, $L$ is the length of the pipe,
$H(z,t)$ is the pressure head [$m$] and $Q(z,t)$ is the flow rate [$m^3/s$].
The physical parameters of the pipeline are $$a_1=gA_r, \displaystyle a_2=\frac{b^2}{gA_r}, \mu=\displaystyle\frac{\mathfrak{f}}{2\phi A_r},$$
where $b$ is the wave speed in the fluid [$m/s$],
$g$ is the gravitational acceleration [$m/s^2$], $A_r$ is the
cross-sectional area of the pipe [$m^2$], $\phi$ is the inside diameter
of the pipe [$m$], and $\mathfrak{f}$ is the Darcy-Weichbach friction factor.

The presence of a leak in a given position $z_{f_i}$
must be handled as a boundary condition for the system (\ref{WH}) with a flow loss:
\begin{equation}\label{leakstep}
Q_{f_i}(t)=\sigma_{i}\sqrt{H_{f_i}(z_{f_i},t)}
\end{equation}
where $\sigma_{i}=\sqrt{2g}A_{f_i}C_{f_i}>0$, $A_{f_i}$ is the sectional area of the
leak, $C_{f_i}$ the discharge coefficient and $H_{f_i}$ is the pressure at the leak position $z_{f_i}$.

\subsection{Nonlinear finite model}
To obtain a model of finite dimension from the set of equations (\ref{WH}) is necessary to define their boundary and initial conditions. The boundary conditions express the temporal profiles of $Q(z,t)$ and $H(z,t)$ in the spatial coordinates $z=0$ and $z=L$. Apart from, the initial conditions express the spatial profiles of $Q(z,t)$ and $H(z,t)$ at the instant $(t=0)$ and they are denoted here as: $H(z,0)={{H}^{0}}(z)$, $Q(z,0)={{Q}^{0}}(z)$. As boundary conditions,
the following Dirichlet conditions can be used:
\begin{itemize}
\item Upstream pressure head: $H(0,t)={{H}_{in}(t)}$
\item Downstream pressure head: $H(L,t)={{H}_{out}(t)}$
\item Upstream flow rate: $Q\left( 0,t \right)={{Q}_{in}(t)}$
\item Downstream pressure head: $Q\left( L,t \right)={{Q}_{out}(t)}$
\end{itemize}
System (\ref{WH}) with included leaks can be discretized using the Finite Difference Method in $n_{s}$ sections as follows \cite{Chaudry1979}:
\begin{equation}\label{Q-modelDifHH}
\dot{Q}_i=\frac{a_1}{\Delta z_i}(H_i-H_{i+1})-\mu Q_i|Q_i|;
\end{equation}
\begin{equation}\label{H-modelDifHH}
\dot{H}_{i+1}=\frac{a_2}{\Delta z_{i}}(Q_{i}-Q_{i+1}-\sigma_{i}\sqrt{H_{i+1}});
\end{equation}
with $i=1,\ldots,n_{s}$.

\section{Diagnosis system for a set of faults in a pipeline}
A Fault Detection and Isolation (FDI) procedure involve three tasks \cite{pattonBook:00}: (\emph{i}) Fault detection: to take a binary decision on the status of the system according to the nominal operating conditions. (\emph{ii}) Fault isolation: to determine the type of fault from a symptom. (\emph{iii}) Fault identification: to estimate the size and type of fault, including its temporal evolution.
For the three tasks in this work the generic representation of concentrated parameters
\begin{eqnarray}\label{system}
\dot x(t)&=&f(x(t),u(t),\theta(t))\\
\nonumber y&=&h(x(t))
\end{eqnarray}
is assumed, where $x(t)\in\mathbb{R}^n$ are the states associated to the flows and pressures of the fluid along the pipeline, $u(t)\in\mathbb{R}^m$ are the exogenous inputs or control signals, $y(t)\in\mathbb{R}^p$ represents known variables of the fluid and $\theta(t)\in\mathbb{R}^{n_{\theta}}$
represents the physical parameters of the pipeline.\\

By means of the data of the process and model (\ref{system}) the detection task consists to generate a residual $r(t)$ with the following property \cite{gertler:91}:
\begin{equation}\label{residuo}
r(t)=\left\{\begin{array}{cc}
0&\mbox{normal \;condition} \\
\neq0&\mbox{abnormal\;condition}
\end{array}\right.
\end{equation}

In particular for the residual generation task, let consider the analytical model of the fluid (\ref{Q-modelDifHH})-(\ref{H-modelDifHH}), as well as the available measurements of flows and pressures at the ends of the pipeline ($H_1=H_{in}$, $H_{n+1}=H_{out}$, $Q_1=Q_{in}$ and $Q_n=Q_{out}$). For the design of the robust fault diagnosis the following fault scenarios are considered:
\begin{itemize}
\item E1: Fault in the upstream flow rate sensor, $\delta Q_{in}$.
\item E2: Fault in the downstream flow rate sensor $\delta Q_{out}$.
\item E3: Fault in the pumping system corresponding to an actuator fault $\delta H_{in}$.
\item E4: Abnormal condition in the downstream storage system associated with additive faults $\delta H_{out}$ in the model.
\item E5: Leak in the pipeline with unknown position and outflow $Q_{f_i}$.
\end{itemize}

Thus, the diagnosis system presented here is composed of two tasks, the \emph{detection \& isolation} step followed by a specific \emph{reconstruction} stage (which is activated according to the isolated fault).
The first one counts on five analytical redundancy relations to detect and isolate the faults with a different signature for each scenario. This stage simplifies the reconstruction of the faults by a set of independent nonlinear observers of dimension lower than the global model with each fault.

\subsection{Fault detection and isolation system}
To obtain residuals that fulfill the property (\ref{residuo}) for the fault scenarios (E1-E5), the model (\ref{Q-modelDifHH})-(\ref{H-modelDifHH}) is considered. Since there is not a solution to the design of residuals sensitive only to one fault scenario and robust to the rest, residual patterns assuming diverse subsets of faults and disturbances must be generated.\\

The simplest and basic residual is based on the mass balance and is generated from the difference between the flow rates
\begin{equation}\label{R1}
r_1=Q_{in}-Q_{out}
\end{equation}
which is zero when there is not an unknown fluid extraction or the sensors of the variables $Q_{in}$ and $Q_{out}$ operates in normal conditions and becomes nonzero when there are leaks in the system or any flow rate measurement is erroneous, \emph{i.e.} $r_1$ deviates from zero for the scenarios E1, E2 and E5 and remain around zero for E2 and E4.\\

Considering that a pipeline of length $L$ operates in steady state, from (\ref{Q-modelDifHH})-(\ref{H-modelDifHH}), the analytical redundant relation
\begin{equation}\label{R2}
r_2=-\mu {{Q}_{in}}\left| {{Q}_{in}} \right|+\frac{{{a}_{1}}}{L}({{H}_{in}}-{{H}_{out}})
\end{equation}
is zero in normal conditions and becomes nonzero for four fault scenarios: E1, E3, E4 and E5. Since (\ref{R2}) does not depend on the measurement of the variable $Q_{out}$, this relation is robust to the fault in the measurement of the downstream flow. By symmetry of the model with respect to the flows the relation
\begin{equation}\label{R3}
r_3=-\mu Q_{out}\left\vert Q_{out}\right\vert +\frac{a_1}{L}(H_{in}-H_{out})
\end{equation}
is zero when the pipeline is free of leaks, and the pumping system, pressure data and downstream flow are correct. On the contrary, the residual deviates from zero when there is a leak or scenarios E2, E3 and E4 occur. Since $r_3$ is independent from $Q_{in}$, this is only insensible to the upstream flow rate.

With these three residuals (\ref{R1}-,\ref{R3}), the following Fault Signature Matrix (FSM) is obtained
\begin{equation}\label{MatrizFirma3}
\begin{array}{c|ccccc}
     &E1&E2&E3&E4&E5\\
     \hline
  r_1 &   \bullet   &  \bullet     &             &             &  \bullet \\
  r_2 &   \bullet   &              &  \bullet    &  \bullet    &  \bullet  \\
  r_3 &             &  \bullet     &  \bullet    &  \bullet    &  \bullet \\
\end{array}
\end{equation}
where $\bullet$ means a residual different from zero for the abnormality indicated at the top of each column. Thus, only the presence of leaks and faults in the flowmeters can be isolated assuming the presence of a unique fault scenario. Faults in the pumping system or pressure sensors ($\delta H_{in}$ and $\delta H_{out}$) can be detected with (\ref{R2}) and (\ref{R3}) but not isolate, because both residuals $r_2$ and $r_3$ are sensitive to both faults.

Thus, discretizing the model (\ref{Q-modelDifHH})-(\ref{H-modelDifHH}) with $\sigma_{i}=0$ for two sections of the same size, one gets
\begin{eqnarray*}
{{{\dot{Q}}}_{in}}&=&\mu {{Q}_{in}}|{{Q}_{in}}|+\frac{{{a}_{1}}}{0.5L}\left( {{H}_{in}}-{{H}_{m}} \right) \\
{{{\dot{H}}}_{m}}&=&\frac{{{a}_{2}}}{0.5L}\left( {{Q}_{in}}-{{Q}_{out}}\right)\\
{{{\dot{Q}}}_{out}}&=&\mu {{Q}_{out}}|{{Q}_{2}}|+\frac{{{a}_{1}}}{0.5L}\left( {{H}_{m}}-{{H}_{out}} \right)
\end{eqnarray*}
and eliminating the unknown pressure at the middle of the line ${{H}_{m}}$, the following analytical relation is obtained
\begin{equation}\label{R4}
r_4=\overset{\cdot }{\mathop{{{Q}_{in}}}}\,+\mu {{Q}_{in}}\left|{{Q}_{in}}\right|+\alpha_1\int{({{Q}_{in}}-{{Q}_{out}})}dt-{\alpha_2{H}_{in}}
\end{equation}
with $\alpha_1=\frac{a_{1}a_{2}}{0.25L}$ and $\alpha_2=\frac{{a}_{1}}{0.5L}$. This relation is zero if there are deviations in the downstream pressure head
$H_{out}$ and then allows to isolate faults in the actuator and pressure sensors. It is to note that the implementation of the residual require to estimate on-line the initial condition of the integral or to generate the residual as a second order differential equation. By symmetry of the structure, the following analytical relation is obtained
\begin{equation}\label{R5}
r_5=\overset{\cdot }{\mathop{{{Q}_{out}}}}\,+\mu {{Q}_{out}}\left| {{Q}_{out}} \right|-\alpha_1\int{({{Q}_{in}}-{{Q}_{out}})}dt+ \alpha_2{{H}_{out}}
\end{equation}
which does not depend on the upstream pressure head $H_{in}$. By adding the new residuals to the FSM (\ref{MatrizFirma3}), this becomes
\begin{equation}\label{firmas}
\begin{array}{c|ccccc}
     &E1&E2& E3&E4&E5\\
\hline
  r_1 &\bullet    &  \bullet     &             &              &  \bullet \\
  r_2 &\bullet    &              &  \bullet    &  \bullet     &  \bullet  \\
  r_3 &           &  \bullet     &  \bullet    &  \bullet     &  \bullet  \\
  r_4 &   \bullet &   \bullet    &  \bullet    &              &  \bullet  \\
  r_5 &  \bullet  &  \bullet     &             &  \bullet     &  \bullet \\
\end{array}
\end{equation}
From this matrix, one can observe that a different pattern of the residuals exists for each scenario, such that all faults are isolable.

\subsection{Fault reconstruction}
The second stage of the diagnosis system is the reconstruction of the five concerned faults. To design this stage, specific models of the form (\ref{system}) with the corresponding fault are considered, where the parameters $\theta$ associated to the faults are additional states according to the extended vector
\begin{equation}\label{VectoAumentado}
x_{e}(t)\to \left[\begin{matrix}
   x(t) \\ \theta (t)
\end{matrix}\right]
\end{equation}
and they can be estimated via nonlinear observers. In this work, high gain observers are designed for the aim.
The start point of the algorithm design consists on transforming the finite model (\ref{Q-modelDifHH})-(\ref{H-modelDifHH}),
into the form
\[f(x(t),u(t),\theta(t))=F(x_{e}(t),u(t))+Gy(t),\]
to obtain the following system
\begin{equation}\label{SistemaExtendido}
\dot x_{e}(t)=F(x_{e}(t),u(t))+G(y(t))
\end{equation}
where the input vector is given by $u(t)={{[{{u}_{1}}(t),{{u}_{2}}(t)]}^{T}}={{[{{H}_{in}(t)},{{H}_{out}(t)}]}^{T}},$
composed by the pressure heads at the ends of the pipeline. In case of constant pressure heads, $u(t)=u_0$ is assumed.
For the design of the high gain observers, the flow rates at the ends of the pipeline are considered to be measurable, \emph{i.e.}:
 \begin{equation}\label{Salidas}
y=h(x_{e})=\left[\begin{array}{cc}Q_{in}&Q_{out}\end{array}\right]^T
\end{equation}

It is to remark that both measurements are not required in all the reconstruction cases. Thus, the used measurements are defined for each fault scenario.

\subsubsection{Reconstruction of a leak}
The aim of this task is the reconstruction of the leak position and its coefficient. For the conception of the observer, the model (\ref{Q-modelDifHH})-(\ref{H-modelDifHH})
must be fixed (at least) with $n_s=2$ to represent two sections with different flow rates: the flow before the leak point, and the flow rate after it. Therefore, the following equations set is proposed:
\begin{align}\label{Finito2secciones}
\nonumber{{{\dot{Q}}}_{in}}&=\mu {{Q}_{in}}|{{Q}_{in}}|+\frac{{{a}_{1}}}{\Delta {{z}_{1}}}\left( {{H}_{in}}-{{H}_{f}} \right)\\
{{{\dot{H}}}_{f}}&=\frac{{{a}_{2}}}{\Delta {{z}_{1}}}\left( {{Q}_{in}}-{{Q}_{out}}-{{\sigma }_{f}}\sqrt{{{H}_{f}}} \right)\\
\nonumber{{{\dot{Q}}}_{out}}&=\mu {{Q}_{out}}|{{Q}_{out}}|+\frac{{{a}_{1}}}{\Delta {{z}_{2}}}\left( {{H}_{f}}-{{H}_{out}}\right)
\end{align}
where the leak position is associated with the size of the first section $\Delta {{z}_{1}}\in [0,L]$, whereas the second section has a size of $\Delta z_{2}=L-\Delta z_{1}$.

To complete the model for parameter estimation purposes, the state vector of system (\ref{Finito2secciones}), $x=\left[\begin{array}{ccc}Q_{in}&H_{f}&Q_{out}\end{array}\right]^T$, must be extended
with two adittional states corresponding to the parameters associated (position and leak coefficient) to the unknown extraction
$$\theta(t)=\left[\begin{array}{cc}\Delta {{z}_{1}}&{{\sigma }_{f}}\end{array}\right]^T$$
setting up the augmeted vector (\ref{VectoAumentado}). Taking into account that the parameters are constant, their derivatives are equalised to zero, thus
\begin{align}
\nonumber\dot{\Delta}{{z}_{1}}&=0\\
\nonumber{{{\dot{\sigma}}}_{{{f}_{1}}}}&=0
\end{align}

Following the procedure design of a high gain observer (described in \cite{Gauthier1992,Gauthier2001,Besanccon2007a}) for the system with the state vector
$$x_e=[\begin{matrix}   {{Q}_{e}} & {{H}_{f}} & {{Q}_{s}} & \Delta {{z}_{1}} & {{\sigma }_{f}}\end{matrix}]^T$$
the following state observer is obtained:
\begin{align}\label{ObservadorFuga}
\left[
\begin{array}{c}
\dot{\hat Q}_{in}\\
\dot{\hat H}_f\\
\dot{\hat Q}_{out}\\
\dot{\hat\Delta}z_1\\
\dot{\hat \sigma}_{f_1}\\
\end{array}
\right]
&=\left[ \begin{matrix}
   \mu {{{\hat{Q}}}_{in}}|{{{\hat{Q}}}_{in}}|+\displaystyle\frac{{{a}_{1}}}{{{{\hat{\Delta}}}z_{1}}}\left( H_{in}^{{}}-{{{\hat{H}}}_{f}} \right)  \\
   0  \\
   \mu {{{\hat{Q}}}_{out}}|{{{\hat{Q}}}_{out}}|+\displaystyle\frac{{{a}_{1}}}{L-{{{\hat{\Delta}}}z_{1}}}\left( {{{\hat{H}}}_{f}}-H_{out}^{{}} \right)  \\
   \displaystyle\frac{{{a}_{2}}}{{{{\hat{\Delta}}}z_{1}}}\left( {{{\hat{Q}}}_{in}}-{{{\hat{Q}}}_{out}}-{{{\hat{\sigma}}}_{f_1}}\sqrt{{{{\hat{H}}}_{f}}} \right)  \\
   0  \\
\end{matrix} \right]\\
\nonumber&-K(.)\left[ \begin{matrix}
   {{{\hat{Q}}}_{in}}-Q_{in}\\
   {{{\hat{Q}}}_{out}}-Q_{out}\\
\end{matrix} \right]
\end{align}
with a convergence gain expressed as:
\begin{align}
\nonumber K&=\left[ \begin{matrix}
   2\lambda  & 0  \\
   -\displaystyle\frac{{{\lambda }^{2}}{{{\hat{\Delta}}}z_{1}}^{2}}{{{a}_{1}}}{{H}_{f}} & 0  \\
   0 & 3\lambda   \\
   0 & \displaystyle\frac{3{{\lambda }^{2}}\left( L-{{{\hat{\Delta}}}z_{1}} \right)}{{{a}_{1}}}  \\
   0 & \gamma\\
\end{matrix} \right]\\
\nonumber\gamma&= -\displaystyle\frac{3\lambda }{\sqrt{{{{\hat{H}}}_{f}}}}-\displaystyle\frac{3{{\lambda }^{2}}{{{\hat{\sigma}}}_{f_1}}\left( L-{{{\hat{\Delta}}}z_{1}} \right)}{2{{a}_{1}}{{{\hat{H}}}_{f}}}-\displaystyle\frac{{{\lambda }^{3}}{{{\hat{\Delta}}}z_{1}}\left( L-{{{\hat{\Delta}}}z_{1}} \right)}{{{a}_{1}}{{a}_{2}}\sqrt{{{{\hat{H}}}_{f}}}}
\end{align}

This observer was originally presented in \cite{Torres2012} and by means of, the parameters linked to the leak can be reconstructed with the estimation of $\theta$. This observer was conceived considering the output vector
(\ref{Salidas}), \emph{i.e.}, the flow rate measurements at both ends of the pipeline.

\subsubsection{Reconstruction of faults in flow sensors}
In the scenario of faults in the flow sensors, the faults are assumed to be additive offsets, therefore the fault models are given in the following way:
\begin{gather}
{{\tilde{Q}}_{in}}={{Q}_{in}}+\delta {{Q}_{in}},\;{{\tilde{Q}}_{out}}={{Q}_{in}}+\delta {{Q}_{out}}
\end{gather}
Substituting these models in (\ref{Q-modelDifHH})-(\ref{H-modelDifHH}),
the following extended models are obtained:\\
 (\emph{i}) Fault in the upstream flow sensor:
\begin{align*}
{{{\dot{Q}}}_{in}}&=\mu {{\left( {{Q}_{in}}-\delta {{Q}_{in}} \right)}}|Q_{in}-\delta Q_{in}|+\frac{{{a}_{1}}}{L}\left( {{H}_{in}}-{{H}_{out}} \right)\\
\dot\delta {{Q}_{in}}&=0
\end{align*}
with $x_{e}=[\begin{matrix} Q_{in}&  \delta{Q}_{in}\end{matrix}]$, and\\
(\emph{ii}) Fault in the downstream flow sensor:
\begin{align*}
{{{\dot{Q}}}_{out}}&=\mu {{\left( {{Q}_{out}}-\delta {{Q}_{out}} \right)}|Q_{out}-\delta Q_{out}|}+\frac{{{a}_{1}}}{L}\left( {{H}_{in}}-{{H}_{out}}\right)\\
\dot\delta {{Q}_{out}}&=0
\end{align*}
with $x_{e}=[\begin{matrix} Q_{out} & \delta{Q}_{out} \end{matrix}]$.\\

In both models the equations of the unknown states ${\delta }{{Q}_{in}}=0$ and ${\delta }{{Q}_{out}}=0$
represent offsets of the flow sensors. The choice of a finite model with a unique section is justified since along the pipeline the flow is the same in steady state in absence of extractions. Following the procedure design of high gain observers \cite{Gauthier1981,Gauthier1992}, the estimation algorithm for the case of a
fault in the upstream flowmeter is reduced to
\begin{align}\label{ObservadorCaudalimetro}
\nonumber\left[
\begin{matrix}
\dot{\hat Q}_{in}\\
\dot{\hat \delta}Q_{in}\\
\end{matrix}
\right]&=\left[ \begin{matrix}
   \mu(\hat Q_{in}-\hat\delta Q_{in})|\hat Q_{in}-\hat\delta Q_{in}|+\frac{{{a}_{1}}}{L}\left( H_{in}^{{}}-{{H}_{out}} \right)  \\
   0  \\
\end{matrix} \right]\\
&\begin{matrix}-K\left[ {{{\hat{Q}}}_{in}}-Q_{in} \right]\end{matrix}
\end{align}
with the gain
\begin{align*}
K&=\left[\begin{matrix}
2\lambda\\
\displaystyle\frac{-\lambda^2}{\gamma}+2\lambda\\
\end{matrix}\right]\\
\gamma&=\mu|\hat Q_{in}-\hat\delta Q_{in}|+\mu Q_{in}\texttt{sign}(\hat Q_{in}-\hat\delta Q_{in})\\
&-\mu\hat\delta Q_{in}\texttt{sign}(\hat Q_{in}-\hat\delta Q_{in})
\end{align*}
In this case, the observer uses only the flow rate measurement at the upstream, \emph{i.e}, $y=h(x_{e})=Q_{in}$.
Finally, assuming $(\hat Q_{in}-\hat\delta Q_{in})>0$, the gain is reduced to:
\begin{gather}
K=\left[ \begin{matrix}
2\lambda   \\
\displaystyle\frac{{-{\lambda }^{2}}}{2\mu ({{{\hat{Q}}}_{in}}-{{{\hat{\delta}}}Q_{in}})}+2\lambda   \\
\end{matrix} \right]
\end{gather}
A similar observer can be designed for the reconstruction of the downstream flow sensor.
\subsubsection{Reconstruction of faults in pressure systems}
In case of faults in the pumping or storage systems at the end of the pipeline, the fault models to be considered are:
\begin{gather}
{{{\tilde{H}}}_{in}}={{H}_{in}}+\delta {{H}_{in}},\;{{{\tilde{H}}}_{out}}={{H}_{out}}+\delta {{H}_{out}}
\end{gather}
To conceive the reconstruction observer, a finite model with at least two spatial sections is required.
Therefore, for the upstream case, the considered model is
\begin{align}\label{PressureObserver1}
\nonumber{{{\dot{Q}}}_{in}}&=\mu Q_{in}|Q_{in}|+\frac{{{a}_{1}}}{\Delta {{z}_{1}}}\left( {{H}_{in}}-\delta {{H}_{in}}-{{H}_{f}} \right) \\
{{{\dot{H}}}_{f}}&=\frac{{{a}_{2}}}{\Delta {{z}_{1}}}\left( {{Q}_{in}}-{{Q}_{out}} \right) \\
\nonumber{{{\dot{Q}}}_{out}}&=\mu Q_{out}|Q_{out}|+\frac{{{a}_{1}}}{\Delta {{z}_{2}}}\left( {{H}_{f}}-{{H}_{out}} \right) \\
\nonumber\dot{\delta }{{H}_{in}}&=0
\end{align}
By symmetry, for a fault at the downstream, the observer design is based on the following model
\begin{align}\label{PressureObserver2}
\nonumber{{{\dot{Q}}}_{in}}&=\mu Q_{in}|Q_{in}|+\frac{{{a}_{1}}}{\Delta {{z}_{1}}}\left( {{H}_{in}}-{{H}_{f}} \right) \\
{{{\dot{H}}}_{f}}&=\frac{{{a}_{2}}}{\Delta {{z}_{1}}}\left( {{Q}_{in}}-{{Q}_{out}} \right) \\
\nonumber{{{\dot{Q}}}_{out}}&=\mu Q_{out}|Q_{out}|+\frac{{{a}_{1}}}{\Delta {{z}_{2}}}\left( {{H}_{f}}-{{H}_{out}}+\delta {{H}_{out}} \right) \\
\nonumber\dot{\delta }{{H}_{out}}&=0
\end{align}

In the case of a fault in the upstream pressure system (pumping system), the high gain observer according \cite{Gauthier1992} for this fault scenario (\ref{PressureObserver1}) is given by
\begin{align}\label{ObservadorActuador}
\nonumber\left[
\begin{array}{c}
\dot{\hat Q}_{in}\\
\dot{\hat H}_f\\
\dot{\hat Q}_{out}\\
\dot{\hat\delta}H_{in}\\
\end{array}
\right]=&\left[ \begin{matrix}
   \mu \hat{Q}_{in}|\hat Q_{in}|+\displaystyle\frac{{{a}_{1}}}{\Delta {{z}_{1}}}\left( H_{in}^{{}}-{{{\hat{H}}}_{f}}-{{\delta}H_{in}} \right)  \\
   \displaystyle\frac{{{a}_{2}}}{{{{\hat{\Delta}}}z_{1}}}\left( {{{\hat{Q}}}_{in}}-{{{\hat{Q}}}_{out}} \right)  \\
   \mu \hat{Q}_{out}|\hat Q_{out}|+\displaystyle\frac{{{a}_{1}}}{\Delta {{z}_{2}}}\left( {{{\hat{H}}}_{f}}-H_{out}^{{}} \right)  \\
   0  \\
\end{matrix} \right]\\
-&K\left[ \begin{matrix}
   {{{\hat{Q}}}_{in}}-Q_{in}^{{}}  \\
   {{{\hat{Q}}}_{out}}-Q_{out}^{{}}  \\
\end{matrix} \right]
\end{align}
which have been conceived considering as measurement outputs, the flows ant the extremities, \emph{i.e.}, using Eq. (\ref{Salidas}).
Assuming  $\hat Q_{in}>0$, the reduced gain is expressed as follows:
\small
\begin{gather}
K=\left[ \begin{matrix}
   2\lambda  & 0  \\
   0 & \displaystyle\frac{\Delta {{z}_{2}}{{\lambda }^{2}}}{{{a}_{1}}}-\displaystyle\frac{4\mu {{{\hat{Q}}}_{out}}\Delta {{z}_{2}}\lambda }{{{a}_{1}}}  \\
   0 & 2\lambda   \\
   -\displaystyle\frac{\Delta {{z}_{1}}{{\lambda }^{2}}}{{{a}_{1}}}+\displaystyle\frac{4\mu {{{\hat{Q}}}_{in}}\Delta {{z}_{1}}\lambda }{{{a}_{1}}} & -\displaystyle\frac{\Delta {{z}_{2}}{{\lambda }^{2}}}{{{a}_{1}}}+\displaystyle\frac{4\mu {{{\hat{Q}}}_{out}}\Delta {{z}_{2}}\lambda }{{{a}_{1}}}  \\
\end{matrix} \right]
\end{gather}
\normalsize
Similar observer can be designed for $\delta H_{out}$ using Eq. (\ref{PressureObserver2}).
\section{Experimental Results}
\begin{figure}[tpb]
\centering
\resizebox*{8.5cm}{!}{\includegraphics{Signals.eps}}
\caption{Measured signals of flow rates and pressures at the ends of the pipeline with an extraction at $t=100$ [$s$]}\label{Signals}
\end{figure}
The hydraulic pilot pipeline counts on six valves (V1, V2, V3, V4, V5, V6)
used to emulate leaks at 11.535 $[m]$, 49.825 $[m]$, 80.355 $[m]$ 118.365 $[m]$, 148.925 $[m]$, 186.945 $[m]$, respectively from the upstream. The physical parameters values of this pipeline are $b=1497$ $[m/s]$, $\phi=0.1047$ $[m]$, $L=200.16$ $[m]$, $\mathfrak{f}=2.785\times10^{-2}$. With the purpose to evaluate the performance of the fault diagnosis system for pipelines, several experiments were realized provoking a extraction (leak emulation) and altering the recorded measurements supplied by the flow and pressure sensors. The leak emulation was originated opening the valve V4 at $100$ $[s]$.
The effect of the leak can be observed in the behavior of the flows plotted in Fig. \ref{Signals}, clearly
these are deviated from the operation point. In the same figure, the measurement signals corresponding to the pressure heads at the end points are also plotted.
For the validation of the system robustness, experiments are carry out considering the following three scenarios:
\begin{itemize}
\item E5: Reconstruction of a leak with a position $\Delta z_1=118.365$ $[m]$ via the algorithm given by the non linear observer (\ref{ObservadorFuga}) and full described in \cite{Torres2012}.
\item E1: Reconstruction of the offset $\delta{Q}_{in}=11.11-22.22\%$ in the upstream flowmeter with the algorithm (\ref{ObservadorCaudalimetro}).
\item E3: Reconstruction of the fault $\delta{H}_{in}=20\%$ in the sensor of the pumping system with algorithm (\ref{ObservadorActuador}).
\end{itemize}
\subsection{Fault detection and isolation}
The evolution of the set of residuals (\ref{R1}, \ref{R2}, \ref{R3}, \ref{R4} and \ref{R5}) for scenarios E1, E3 and E5 are shown in Fig. \ref{Residuals}. One can see that the signature for each scenario corresponds with the FSM given by (\ref{firmas}), both the magnitude of each residual is disperse with respect to faults. A normalized procedure for the residual is suggested considering maximum physical parameters of the faults. It is to remark that to detect leaks $r_1$ is the standard residual; however the loss volume involved in the integral term of residuals $r_4$ or $r_5$, seems to be more appropriated from sensitivity point of view.
\begin{figure*}[t]

\begin{tabular}{ccc}
\hspace{2cm}Scenario 1\hspace{2cm} &\hspace{2cm}Scenario 3 \hspace{2cm} & \hspace{2cm}Scenario 5 \hspace{2cm}\\
\end{tabular}
\includegraphics[scale=.4]{Ese1editada-A.eps}
\includegraphics[scale=.4]{Ese3editada-A.eps}
\includegraphics[scale=.4]{Ese5editada-A.eps}
\caption{Residual evolutions for fault scenarios E1, E3 and E5}\label{Residuals}
\end{figure*}
\subsection{Fault reconstruction}
In accordance to the fault nature, once a fault has been detected and isolated, the reconstruction of the fault along the time is determined using a corresponding estimation algorithm. Following, some experimental results concerning the reconstruction performed by the observers
are presented.
\subsubsection{Reconstruction of a leak}
The observer given in (\ref{ObservadorFuga}) was initialized at $t=160$ $[s]$, once the leak has been isolated from the residuals behavior. In Fig. \ref{Posicion1}, the estimation of the leak position is presented for different values of $\lambda$. The estimated values are approximated to the real value of the leak position with a decreasing and increasing of noise depending on the choice of $\lambda$.
\begin{figure}[htb]
\begin{center}
\resizebox*{8.5cm}{!}{\includegraphics{Posicion1.eps}}
\end{center}
\caption{Position estimation}\label{Posicion1}
\end{figure}
\subsubsection{Reconstruction of faults in flow sensors}
In order to evaluate the observer for the reconstruction of a fault in the upstream flowmeter (\ref{ObservadorCaudalimetro}),
a signal has be added to the upstream measurement.
During the experiment shown in Fig. \ref{Signals}, the observer was initialized at $t=0$ $[s]$, \emph{i.e.}, when there is not a leak.
The initial conditions of the observer were chosen with different values with respect to the real initial conditions
in the pilot pipeline and it was tuned with $\lambda=2$.
The estimations results are exposed in Fig. \ref{offset} (top).
\begin{figure}[htb]
\begin{center}
\begin{tabular}{c}
\resizebox*{8.5cm}{!}{\includegraphics{offset.eps}}\\
\resizebox*{8.5cm}{!}{\includegraphics{offsetPresion.eps}}
\end{tabular}
\end{center}
\caption{(top) Estimation of the offset in the upstream flowmeter , (bottom) Estimation of a damage in the pumping system}\label{offset}
\end{figure}
\subsubsection{Reconstruction of faults in pressure sensors}
For the evaluation of the observer which estimates faults in the pumping system (\ref{ObservadorActuador}),
a constant signal with a value of 1.6$\times 10^{-3}$ $[m]$ was added to the upstream pressure measurement.
The observer was launched during the absence of extractions. The initial conditions of the observer were chosen different to the pipeline conditions and
was tuned with $\lambda =1$. In Fig. \ref{offset} (bottom), the good estimation can be appreciated.
\section{Conclusions}
In this work, a robust algorithm was presented to diagnose faults in pipelines.
The originality of such system is its ability to detect, isolate and reconstruct different types of faults in pipelines,
principal contribution of this paper. The main characteristic of this monitoring system is its two-stages composition with specific tasks. In the first step the aim is to distinguish among five fault scenarios including a possible leak. This task is performed by the use of redundant relations obtained from the fluid transport model of the pipeline. In the second stage, the task is the reconstruction of the temporal evolution of the fault, once this has been previously identified. The evaluation results of the diagnosis system with experimental data were satisfactory, making it feasible for implementation in industrial pipelines.

config: arxiv


TITLE: Why isn't $0+a=a$ something we derive?
QUESTION [0 upvotes]: In the usual natural number definition of addition $0+a=a$ is taken as true by definition. This feels like it should be something we derive from $0+0=0$, instead? As in, let's define addition this way:
$0+0=0$
$a+S(b)=S(a+b)$
Then prove the result:
Claim: $0+a=a$
Base case: $0+0=0$ by definition.
Inductive step: Suppose $0+a=a$. We must show that $0+S(a)=S(a)$. By definition of addition, $0+S(a)=S(0+a)$ then by inductive hypothesis equals $S(a)$ and we are done.
In other words we can derive the result rather than assume it true, so why do we skip this step usually?

REPLY [0 votes]: As in, let's define addition this way:
  $$0+0=0$$
  $$a+S(b)=S(a+b)$$

When you attempt to define a function like addition, a good start is to consider it as a general function.  Even granting a domain of natural numbers and that the successor is +1, you have:
$$f(0, 0) = 0$$
$$f(a, b+1) = f(a, b) + 1$$
Try to think of another function with that property.  One that comes to my mind is $f(x, y) = y$.