# Fixed point theorem for generalized Chatterjea type mappings

Ovidiu Popescu and Cristina Maria Păcurar

###### Abstract

We introduce a new type of mappings in metric space which are three-point
analogue of the well-known Chatterjea type mappings, and call them generalized
Chatterjea type mappings. It is shown that such mappings can be discontinuous
as is the case of Chatterjea type mappings and this new class includes the
class of Chatterjea type mappings. The fixed point theorem for generalized
Chatterjea type mappings is proven.

Keywords— Metric space, fixed point theorem, Chatterjea mappings

Mathematics Subject Classification— Primary 47H10; Secondary 47H09

##  1 Introduction

Recently, Petrov [15] considered a new type of mappings in metric spaces,
which can be characterized as mappings contracting perimeters of triangles,
and gave a fixed point theorem for such mappings. He proved that such mappings
are continuous, and constructed examples of mappings contracting perimeters of
triangle which are not contraction mappings.

######  Definition 1.1 (Petrov [15]).

Let $(X,d)$ be a metric space with $|X|\geq 3$. We shall say that $T:X\to X$
is a mapping contracting perimeters of triangles on $X$ if there exists
$\alpha\in[0,1)$ such that the inequality

$d(Tx,Ty)+d(Ty,Tz)+d(Tz,Tx)\leq\alpha[d(x,y)+d(y,z)+d(z,x)],$

holds for all three pairwise distinct points $x,y,x\in X$.

######  Theorem 1.1 (Petrov [15]).

Let $(X,d)$, $|X|\geq 3$ be a complete metric space and let $T:X\to X$ be a
mapping contracting perimeters of triangles on $X$. Then, $T$ has a fixed
point if and only if $T$ does not possess periodic points of prime period $2$.
The number of fixed points is at most $2$.

Moreover, Petrov and Bisht [16] introduced a three point analogue of the
Kannan type mappings [9].

######  Definition 1.2 (Petrov and Bisht [16]).

Let $(X,d)$ be a metric space with $|X|\geq 3$. We shall say that $T:X\to X$
is a generalized Kannan type mapping on $X$ if there exists
$\lambda\in[0,\frac{2}{3})$ such that the inequality

$d(Tx,Ty)+d(Ty,Tz)+d(Tz,Tx)\leq\lambda[d(x,y)+d(y,z)+d(z,x)],$

holds for all three pairwise distinct points $x,y,x\in X$.

It is shown that such mappings can be discontinuous as is the case of Kannan
type mappings, and that the two classes of mappings are independent. Also, a
fixed point theorem for generalized Kannan type mappings is proved.

######  Theorem 1.2 (Petrov and Bisht [16]).

Let $(X,d)$, $|X|\geq 3$ be a complete metric space and let the mapping
$T:X\to X$ satisfy the following two conditions:

  * (i)

$T(Tx)\neq x$ for all $x\in X$ such that $Tx\neq x$;

  * (ii)

$T$ is a generalized Kannan type mapping on $X$.

Then, $T$ has a fixed point. The number of fixed points is at most $2$.

In [3], Chatterjea proved the following result which gave the fixed point for
discontinuous mappings:

######  Theorem 1.3.

Let $(X,d)$ be a complete metric space and let $T:X\to X$ be a mapping such
that for every $x,y\in X$ the inequality

$d(Tx,Ty)\leq\lambda[d(x,Ty)+d(y,Tx)],$ (1)

holds, where $0\leq\lambda<\frac{1}{2}$. Then, $T$ has a unique fixed point.

We note that the fixed point theorems due to Banach [1], Kannan [9] and
Chatterjea [3] are independent, and that the latter two characterize the
completeness of the metric space (see Subrahmanyam [20]). The initial results
proved by Chatterjea were of great interest, and many novel directions of
research and generalizations emerged from the original result (see, for
example, the papers [2, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 17, 18, 19]).

In this paper, we give a three-point analogue of the Chatterjea type mapping.
The ordinary Chatterjea mappings form an important subclass of these novel
mappings. To emphasize the advances brought to the research field and the
comprehensiveness of the newly introduced class of mappings, examples of
generalized Chatterjea mappings, which are not Chatterjea mappings are
constructed.

##  2 Generalized Chatterjea type mappings

######  Definition 2.1.

Let $(X,d)$ be a metric space with $|X|\geq 3$. We shall say that $T:X\to X$
is a generalized Chatterjea type mapping on $X$ if there exists
$\lambda\in[0,\frac{1}{2})$ such that the inequality

$\displaystyle d(Tx,Ty)$ $\displaystyle+d(Ty,Tz)+d(Tz,Tx)\leq$ (2)
$\displaystyle\leq\lambda[d(x,Ty)+d(y,Tx)+d(y,Tz)+d(z,Tx)+d(z,Ty)+d(x,Tz)],$

holds for all three pairwise distinct points $x,y,x\in X$.

######  Remark 2.1.

Let $(X,d)$ be a metric space with $|X|\geq 3$, $T:X\to X$ be a generalized
Chatterjea type mapping on $X$ and let $x,y,z\in X$ be pairwise distinct.
Consider inequality (1) for the pairs $x,z$ and $y,z$:

  * $d(Tx,Tz)\leq\lambda[d(x,Tz)+d(z,Tx)],$ (3)

  * $d(Ty,Tz)\leq\lambda[d(y,Tz)+d(z,Ty)].$ (4)

Adding the left and the right parts of the inequalities (1), (3) and (4) we
obtain (2). Hence, we get that every Chatterjea type mapping is a generalized
Chatterjea type mapping.

######  Example 2.1.

Let $X=\\{x,y,z\\}$, $d(x,y)=d(y,z)=d(z,x)=1$ and let $T:X\to X$ be such that
$Tx=x$, $Ty=y$ and $Tz=x$.

Since $d(Tx,Ty)=1$ and $d(x,Ty)+d(y,Tx)=2,$ $T$ is not a Chatterjea type
mapping.

However,

$M(x,y,z)=d(Tx,Ty)+d(Ty,Tz)+d(Tz,Tx)=2$

and

$N(x,y,z)=d(x,Ty)+d(y,Tx)+d(y,Tz)+d(z,Tx)+d(z,Ty)+d(x,Tz)=5,$

so we have

$M(x,y,z)\leq\frac{2}{5}N(x,y,z).$

Therefore, $T$ is a generalized Chatterjea type mapping
($\lambda=\frac{2}{5}$). We note that in this case, $T$ has two fixed points.

The next theorem is the main result of the current paper which ensures that
every generalized Chatterjea type mapping that does not have periodic points
of period two, has fixed points, and the number of fixed points is at most
two.

######  Theorem 2.1.

Let $(X,d)$ be a complete metric space with $|X|\geq 3$ and let the mapping
$T:X\to X$ satisfy the following two conditions:

  * (i)

$T(Tx)\neq x$ for all $x\in X$ such that $Tx\neq x$;

  * (ii)

$T$ is a generalized Chatterjea type mapping on $X$.

Then, $T$ has a fixed point. The number of fixed points is at most two.

###### Proof.

Let $x_{0}\in X$, $x_{1}=Tx_{0}$, $x_{2}=Tx_{1}$, $\dots$, $x_{n+1}=Tx_{n}$.
Suppose that $x_{n}$ is not a fixed point of the mapping $T$ for every
$n=0,1,\dots$. Then, we have $x_{n}=Tx_{n-1}\neq x_{n-1}$ and
$x_{n+1}=T(Tx_{n-1})\neq x_{n-1}$ for every $n=1,2,\dots$. Hence, $x_{n-1}$,
$x_{n}$ and $x_{n+1}$ are pairwise distinct. Taking in (2) $x=x_{n-1}$,
$y=x_{n}$, $z=x_{n+1}$ we obtain

$\displaystyle d(Tx_{n-1},Tx_{n})$
$\displaystyle+d(Tx_{n},Tx_{n+1})+d(Tx_{n+1},Tx_{n-1})\leq$
$\displaystyle\leq\lambda[d(x_{n-1},Tx_{n})+d(x_{n},Tx_{n-1})+d(x_{n},Tx_{n+1})+$
$\displaystyle+d(x_{n+1},Tx_{n-1})+d(x_{n+1},Tx_{n})+d(x_{n-1},Tx_{n+1})],$

by where we get

$\displaystyle d(x_{n},x_{n+1})$
$\displaystyle+d(x_{n+1},x_{n+2})+d(x_{n},x_{n+2})\leq$
$\displaystyle\leq\lambda[d(x_{n-1},x_{n+1})+d(x_{n},x_{n+2})+d(x_{n},x_{n+1})+d(x_{n-1},x_{n+2})].$

Hence, we have

$\displaystyle(1-\lambda)[d(x_{n},x_{n+1})$
$\displaystyle+d(x_{n+1},x_{n+2})+d(x_{n},x_{n+2})]\leq$
$\displaystyle\leq\lambda[d(x_{n-1},x_{n+1})+d(x_{n-1},x_{n+2})].$

Using the triangle inequality

$d(x_{n-1},x_{n+2})\leq d(x_{n-1},x_{n})+d(x_{n},x_{n+1})+d(x_{n+1},x_{n+2}),$

we get

$\displaystyle(1-\lambda)[d(x_{n},x_{n+1})$
$\displaystyle+d(x_{n+1},x_{n+2})+d(x_{n},x_{n+2})]\leq$
$\displaystyle\leq\lambda[d(x_{n-1},x_{n+1})+d(x_{n-1},x_{n})+d(x_{n},x_{n+1})],$

by where

$\displaystyle d(x_{n},x_{n+1})$
$\displaystyle+d(x_{n},x_{n+2})+d(x_{n+1},x_{n+2})\leq$
$\displaystyle\leq\dfrac{\lambda}{1-\lambda}[d(x_{n-1},x_{n+1})+d(x_{n-1},x_{n})+d(x_{n},x_{n+1})].$

Further, set for every $n=0,1,\dots$

$d_{n}=d(x_{n},x_{n+1})+d(x_{n},x_{n+2})+d(x_{n+1},x_{n+2}).$

Then, we have $d_{n}\leq\alpha d_{n-1}$ for every $n=1,2,\dots$, where
$\alpha=\dfrac{\lambda}{1-\lambda}\in[0,1)$. Hence, we get

$d_{n}\leq\alpha d_{n-1}\leq\alpha^{2}d_{n-2}\leq\dots\leq\alpha^{n}d_{0}.$

Like in the proof of Theorem 2.4 from [15] we obtain that $\\{x_{n}\\}$ is a
Cauchy sequence. By completeness of $(X,d)$ we get that $\\{x_{n}\\}$ has a
limit $x^{*}\in X$. Let us prove that $Tx^{*}=x^{*}$.

Since $x_{n}$, $x_{n+1}$ and $x_{n+2}$ are pairwise distinct for every
$n=0,1,\dots$, there exists a subsequence $\\{x_{n(k)}\\}_{k\geq 0}$ such that
$x_{n(k)}$, $x_{n(k)+1}$ and $x^{*}$ are pairwise distinct for every
$k=0,1,\dots$. Taking in (2) $x=x_{n(k)}$, $y=x_{n(k)+1}$ and $z=x^{*}$, we
obtain

$\displaystyle d(Tx_{n(k)},Tx_{n(k)+1})$
$\displaystyle+d(Tx_{n(k)+1},Tx^{*})+d(Tx^{*},Tx_{n(k)})\leq$
$\displaystyle\leq\lambda[d(x_{n(k)},Tx_{n(k)+1})+d(x_{n(k)+1},Tx_{n(k)})+d(x_{n(k)+1},Tx^{*})+$
$\displaystyle+d(x^{*},Tx_{n(k)})+d(x^{*},Tx_{n(k)+1})+d(x_{n(k)},Tx^{*})].$

Hence,

$\displaystyle d(x_{n(k)+1},x_{n(k)+2})$
$\displaystyle+d(x_{n(k)+1},Tx^{*})+d(x_{n(k)+2},Tx^{*})\leq$
$\displaystyle\leq\lambda[d(x_{n(k)},x_{n(k)+2})+d(x_{n(k)+1},Tx^{*})+d(x^{*},x_{n(k)+1})+$
$\displaystyle+d(x^{*},x_{n(k)+2})+d(x_{n(k)},Tx^{*})].$

Taking the limit as $k\to\infty$ we get

$2d(x^{*},Tx^{*})\leq 2\lambda d(x^{*},Tx^{*}),$

by where $d(x^{*},Tx^{*})=0$, so $x^{*}$ is a fixed point of $T$.

Now, suppose that there exist at least three distinct fixed points $x,y$ and
$z$. Then $Tx=x$, $Ty=y$ and $Tz=z$. By (2) we have

$d(x,y)+d(y,z)+d(z,x)\leq 2\lambda[d(x,y)+d(y,z)+d(z,x)],$

which is a contradiction. ∎

######  Remark 2.2.

Suppose that under the assumption of Theorem 2.1, the mapping $T$ has a fixed
point $x^{*}$ which is a limit of some iteration sequence $x_{0}$,
$x_{1}=Tx_{0}$, $x_{2}=Tx_{1}$ $\dots$ such that $x_{n}\neq x^{*}$ for all
$n=1,2,\dots$. Then, $x^{*}$ is a unique fixed point.

Indeed, suppose that $T$ has another fixed point $x^{**}\neq x^{*}$.
Obviously, there exists $N\geq 1$ such that $x_{n}\neq x^{*}$ for all $n\geq
N$. Taking in (2) $x=x_{n}$, $y=x^{*}$ and $z=x^{**}$ we obtain

$\displaystyle d(Tx_{n},Tx^{*})$
$\displaystyle+d(Tx^{*},Tx^{**})+d(Tx^{**},Tx_{n})\leq$
$\displaystyle\leq\lambda[d(x_{n},Tx^{*})+d(x^{*},Tx_{n})+d(x^{*},Tx^{**})+$
$\displaystyle+d(x^{**},Tx_{n})+d(x^{**},Tx^{*})+d(x_{n},Tx^{**})],$

by where

$\displaystyle d(x_{n+1},x^{*})$
$\displaystyle+d(x^{*},x^{**})+d(x_{n+1},x^{**})\leq$
$\displaystyle\leq\lambda[d(x_{n},x^{*})+d(x_{n+1},x^{*})+d(x_{n},x^{**})+d(x_{n+1},x^{**})+2d(x^{*},x^{**})].$

Taking the limit as $n\to\infty$, we get

$2d(x^{*},x^{**})\leq 4\lambda d(x^{*},x^{**}),$

so $d(x^{*},x^{**})=0$, which is a contradiction.

We present two examples of generalized Chatterjea type mappings, which are not
a Chatterjea type mappings, neither mappings contracting perimeters of
triangles, nor generalized Kannan mappings, nor Kannan mappings. These
examples highlight the contribution to the theory of fixed point theorems
brought by Theorem 2.1.

######  Example 2.2.

Let $X=\\{A,B,C,D,E\\}$ and, as in Figure 1, let

$d(A,B)=d(A,C)=d(B,C)=d(B,D)=d(C,E)=d(D,E)=d(D,F)=d(E,F)=1,$
$d(A,D)=d(A,E)=d(B,E)=d(C,D)=d(B,F)=d(C,F)=2,$

and $d(A,F)=3$.

Figure 1: A generalized Chatterjea mapping

Let $T:X\to X$ be such that $TA=TD=TE=TF=F$, $TB=D$ and $TC=E$.

We have

$M(A,B,C)=M(B,C,D)=M(B,C,E)=M(B,C,F)=3,$
$\displaystyle\;\;M(A,B,D)=M(A,B,F)=M(A,B,E)=M(A,C,D)=$
$\displaystyle=M(A,C,E)=M(A,C,F)=M(B,D,E)=M(B,D,F)=$ $\displaystyle
M(B,E,F)=M(C,D,E)=M(C,D,F)=M(C,E,F)=2,$
$M(A,D,E)=M(A,D,F)=M(A,E,F)=M(D,E,F)=0,$

and

$N(A,B,C)=12,\quad$ $N(A,B,E)=N(A,C,D)=11,$
$N(A,B,D)=N(A,B,F)=N(A,C,E)=N(A,C,F)=N(B,C,F)=10,$ $N(B,C,D)=N(B,C,E)=9,$
$N(B,D,E)=N(B,E,F)=N(C,D,E)=N(C,D,F)=7,$ $N(B,D,F)=N(C,E,F)=6.$

We note that

$M(x,y,z)\leq\dfrac{1}{3}N(x,y,z)$

for all three distinct points $x,y,z\in X$, so $T$ is a generalized Chatterjea
type mapping.

Since

$d(TB,TD)=d(D,F)=1,$

and

$d(B,TD)+d(D,TB)=d(B,F)+d(D,D)=2,$

$T$ is not a Chatterjea type mapping.

We note that $T$ has a unique fixed point. Moreover,

$d(TA,TB)+d(TA,TC)+d(TB,TC)=3$

and

$d(A,B)+d(A,C)+d(B,C)=3,$

so $T$ is not a mapping contracting perimeters of triangles.

Since

$d(TB,TC)+d(TB,TD)+d(TC,TD)=3$

and

$d(B,TB)+d(C,TC)+d(D,TD)=3,$

$T$ is not a generalized Kannan type mapping.

Also, $d(TB,TC)=1$ and $d(B,TB)+d(C,TC)=2$, so $T$ is not a Kannan mapping.

######  Example 2.3.

Let $X=\mathbb{R}$, $d(x,y)=|x-y|$ and $T:X\to X$ defined as

$Tx=\begin{cases}0,\quad x<2\\\ 1,\quad x\geq 2.\end{cases}$

If $x,y,z$ are pairwise distinct and $x<2$, $y<2$, $z<2$, then $M(x,y,z)=0$.

If $x,y,z$ are pairwise distinct and $x\geq 2$, $y\geq 2$, $z\geq 2$, then
$M(x,y,z)=0$.

For $x<y<2\leq z$, we have $M(x,y,z)=2$ and
$N(x,y,z)=|x|+|y|+|x-1|+z+|y-1|+z\geq 2z+2\geq 6$, so

$M(x,y,z)\leq\dfrac{1}{3}N(x,y,z).$

For $x<2\leq y<z$, we have $M(x,y,z)=2$ and
$N(x,y,z)=|x-1|+y+|x-1|+z+y-1+z-1\geq 2y+2z-2>6$, so

$M(x,y,z)\leq\dfrac{1}{3}N(x,y,z).$

Hence, $T$ is a generalized Chatterjea type mapping.

We note that $T$ has a unique fixed point.

Since

$M(1.9,2,2.1)=2$

and

$d(1.9,2)+d(1.9,2.1)+d(2,2.1)=0.4,$

we get that $T$ is not a mapping contracting perimeters of triangles.

Since

$M(0,1,2)=2$

and

$d(0,T0)+d(1,T1)+d(2,T2)=2,$

we obtain that $T$ is not a generalized Kannan mapping.

Also, since $d(T1,T2)=1$ and $d(1,T1)+d(2,T2)=2$, $T$ is not a Kannan mapping.

Moreover,

$d(1,T2)+d(2,T1)=2,$

so $T$ is not a Chatterjea mapping.

We note that $T$ is a discontinuous mapping.

## References

  * [1] S. Banach, Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales, Fundamenta Mathematicae 3 (1922), 133-181.
  * [2] V. Berinde, M. Păcurar, Approximating fixed points of enriched Chatterjea contractions by Krasnoselskij iterative algorithm in Banach spaces. J. Fixed Point Theory Appl. 23 (2021), 66 .
  * [3] S. K. Chatterjea, Fixed-point theorems, C.R. Acad. Bulgare Sci. 25 (1972), 727–730.
  * [4] N. Van Dung, A. Petruşel, On iterated function systems consisting of Kannan maps, Reich maps, Chatterjea type maps, and related results. J. Fixed Point Theory Appl. 19 (2017), 2271–2285.
  * [5] K. Fallahi, A. Aghanians, Fixed points for Chatterjea contractions on a metric space with a graph. International Journal of Nonlinear Analysis and Applications 7(2) (2016), 49-58.
  * [6] H. Faraji, K. Nourouzi, A generalization of Kannan and Chatterjea fixed point theorems on complete-metric spaces. Sahand Communications in Mathematical Analysis, 06(1) (2017), 77-86.
  * [7] P. Gautam, V. N. Mishra, R. Ali, S. Verma, Interpolative Chatterjea and cyclic Chatterjea contraction on quasi-partial b-metric space[J]. AIMS Mathematics, 2021, 6(2) (2021), 1727-1742.
  * [8] M. Imdad, A. Erduran, Suzuki-Type Generalization of Chatterjea Contraction Mappings on Complete Partial Metric Spaces, Journal of Operators (2013), 923843.
  * [9] R. Kannan, Some results on fixed point — II, Amer. Math. Monthly, 76 (1969), pp. 405-408.
  * [10] S. Kanwal, H. Isik, S. Waheed, Generalized fixed points for fuzzy and nonfuzzy mappings in strong b-metric spaces. J Inequal Appl 2024, 22 (2024).
  * [11] E. Karapınar, H.K. Nashine, Fixed Point Theorem for Cyclic Chatterjea Type Contractions, Journal of Applied Mathematics (2012), 165698.
  * [12] S. H. Khan, M. Abbas, M., T. Nazir, Fixed point results for generalized Chatterjea type contractive conditions in partially ordered G-metric spaces. The Scientific World Journal (2014), 341751.
  * [13] A. Mukheimer, Some Common Fixed Point Theorems in Complex Valued Metric Spaces, The Scientific World Journal (2014), 587825
  * [14] Z. Mustafa, J.R. Roshan, V. Parvaneh et al., Fixed point theorems for weakly T-Chatterjea and weakly T-Kannan contractions in b-metric spaces. J Inequal Appl 46 (2014).
  * [15] E. Petrov, Fixed point theorem for mappings contracting perimeters of triangles. J. Fixed Point Theory Appl. 25, 1–11 . (paper no. 74)
  * [16] E. Petrov, R. K. Bisht, Fixed point theorem for generalized Kannan type mappings, (2023), arXiv:2308.05419.
  * [17] O. Popescu, Fixed point theorem in metric spaces, Bulletin of the Transilvania University of Braşov III 1(50) (2008), 479–482.
  * [18] O. Popescu, G. Stan, Some Remarks on Reich and Chatterjea Type Nonexpansive Mappings. Mathematics 8 (2020), 1270.
  * [19] S. Som, A. Petruşel, H. Garai et al., Some characterizations of Reich and Chatterjea type nonexpansive mappings. J. Fixed Point Theory Appl. 21 (2019), 94.
  * [20] P. V. Subrahmanyam, Completeness and fixed points, Monatsh. Math. 80 (1975), 325–330.


# PTSC: a New Definition for Structural Controllability
under Numerical Perturbations

Yuan Zhang, Yuanqing Xia This paper is a _full_ version of a conference paper
to appear in the 40th Chinese Control Conference on July 26-28, 2021 in
Shanghai, China.. This work was supported in part by the China Postdoctoral
Innovative Talent Support Program (BX20200055), the China Postdoctoral Science
Foundation (2020M680016), the National Natural Science Foundation of China
(62003042), and the State Key Program of National Natural Science Foundation
of China (61836001). Yuan Zhang and Yuanqing Xia are with the School of
Automation, Beijing Institute of Technology, Beijing, China (email:
<EMAIL_ADDRESS>xia_yuanqing@bit.edu.cn).

###### Abstract

This paper proposes a novel notion for structural controllability under
structured numerical perturbations, namely the perturbation-tolerant
structural controllability (PTSC), on a single-input structured system whose
entries can be classified into three categories: fixed zero entries, unknown
generic entries whose values are fixed but unknown, and perturbed entries that
can take arbitrary complex values. Such a system is PTSC if, for almost all
values of the unknown generic entries in the parameter space, the
corresponding controllable system realizations can preserve controllability
under arbitrary complex-valued perturbations with their structure prescribed
by the perturbed entries. This new notion can characterize the generic
property in controllability preservation under structured numerical
perturbations. We give a necessary and sufficient condition for a single-input
system to be PTSC, whose verification has polynomial time complexity. Our
results can serve as some feasibility conditions for the conventional
_structured controllability radius_ problems from a generic view.

###### Index Terms:

Structural controllability, strong structural controllability, structured
numerical perturbations, generic property

##  I Introduction

In recent years, security has been becoming an attractive issue in the control
and estimation of cyber-physical systems, such as chemical processes, power
grids and transportation networks [1, 2, 3, 4]. The robustness of various
system properties have been investigated under internal faults (like
disconnections of links/nodes [2, 5]) or external attacks (like adversarial
sensor/actuator attacks [3]), including stability [6], stabilization [7],
controllability and observability [8, 9, 10, 11, 12]. Particularly, as a
fundamental system property, controllability/observability under structural
perturbations (such as link/node/actuator/sensor removals or deletions) has
been extensively explored on its robust performance. To name a few, [8]
considered observability preservation under sensor removals, [9] investigated
controllability preservation under simultaneous link and node failures, while
[10, 11, 12] systematically studied the involved optimization problems with
respect to link/node/actuator/sensor removals from a computational
perspective. Since controllability/observability is a generic property that
depends mainly on the system structure [13], its robustness is mainly
dominated by the robustness property of the corresponding graphs.

Note that structural perturbation is a kind of numerical perturbation that
makes the corresponding link has a zero weight. In the more general case where
the perturbed links do not necessarily result in zero weights, controllability
robustness has also been studied by computing the distance (in terms of the
$2$-norm or the Frobenius norm) from a controllable system to the set of
uncontrollable systems [14, 15, 16, 17]. Such a notion, also named
_controllability radius_ , was first proposed by [14], and then developed by
several other researchers on its efficient computations [15, 16, 17].
Recently, by restricting the perturbation matrices to a prescribed structure,
the so-called _structured controllability radius problem_ (SCRP) has also
attracted researchers’ interest, i.e., the problem of determining the smallest
(Frbenius or $2$-) norm additive perturbation with a prescribed structure for
which controllability fails to hold [18]. Towards this problem, various
numerical algorithms have been proposed [19, 20, 21]. However, due to the
nonconvexity of this problem, all these algorithms are suboptimal [20].
Moreover, since most of these algorithms adopted some relaxation and iterative
techniques and owing to the involved rounding errors, there is usually no
guarantee that the returned numerical perturbations can make the original
system uncontrollable.

On the other hand, to avoid the potential numerical issues, strong structural
controllability (SSC), a notion proposed by Mayeda and Yamada [22], could also
be used to measure the controllability robustness of a system against
numerical perturbations. In the SSC theory, the system parameters are divided
into two categories, indeterminate parameters and fixed zero parameters. A
system is SSC, if whatever values (other than zero) the indeterminate
parameters of the system may take, the system is controllable. Criteria for
SSC in the single-input case was given in [22], and then extended to the
multi-input cases in [23, 24], as well as allowing the existence of parameters
that can take arbitrary values, including zero and nonzero [25]. Note for SSC
to measure controllability robustness, the numerical perturbations should have
the same zero/nonzero structure as the original systems. While in practice,
perturbations could be imposed to only partial system components (such as a
subset of links of a network) and do not necessarily have the same structure
as the original systems.

In this paper, we propose a new definition for structural controllability
under structured numerical perturbations, namely, the perturbation-tolerant
structural controllability (PTSC). The entries for system matrices are
classified into three categories: fixed zero entries, unknown generic entries
whose values are fixed but unknown (they can be seen as randomly selected
values), and perturbed entries that can take arbitrary complex values. The
notion of PTSC is defined in the following way: a system is PTSC if, for
almost all values of the unknown generic entries in the parameter space, the
corresponding controllable system realizations can preserve controllability
under arbitrary complex-valued perturbations with structure prescribed by the
perturbed entries. The main contributions of this paper are as follows:

1) We propose a novel notion PTSC to study controllability preservation for a
single-input structured system under structured numerical perturbations. In
PTSC, the perturbation structure can be _arbitrary_ relative to the structure
of the original system. This notion provides a new view in studying the
robustness of structural controllability other than structural perturbations.

2) We have shown PTSC can characterize the generic property that, depending on
the structure of the original system and the perturbations, for almost all of
the controllable system realizations, either they can preserve controllability
under arbitrary complex-valued perturbations with the given structure, or
there is a perturbation with the given structure that can make the
corresponding system fail to be controllable. This is beneficial in studying
the SCRPs from a generic view.

3) We give a necessary and sufficient condition for a single-input system to
be PTSC, whose verification has polynomial time complexity. The derivation is
based on the one-edge preservation principle and a series of nontrivial
results on the roots of determinants of generic matrix pencils.

The rest is organized as follows. Section II introduces the PTSC notion and
proves the involved genericity for single-input systems. Section III presents
some preliminaries required for our further derivations. Section IV gives a
necessary and sufficient condition for a single-input system to be PTSC.
Section V discusses the application of PTSC on the SCRP. The last section
concludes this paper.

Natations: Given an integer $p\geq 0$, define ${\cal
J}_{p}\doteq\\{1,...,p\\}$. For a $p\times q$ matrix $M$, $M[{\cal
I}_{1},{\cal I}_{2}]$ denotes the submatrix of $M$ whose rows are indexed by
${\cal I}_{1}$ and columns by ${\cal I}_{2}$, ${\cal I}_{1}\subseteq{\cal
J}_{p}$, ${\cal I}_{2}\subseteq{\cal J}_{q}$. For a vector $b$, $b_{i}$
denotes the $i$th entry of $b$.

##  II The Notion of PTSC

###  II-A Structured Matrix

Before presenting the notion of PTSC, we first introduce the so-called
structured matrix. A structured matrix is a matrix whose entries are either
fixed zero (denoted by $0$) or indeterminate parameters (denoted by $*$). For
description simplicity, we may simply say the entry represented by $*$ is a
nonzero entry. Let $\\{0,*\\}^{p\times q}$ be the set of all $p\times q$
dimensional structured matrices. For $\bar{M}\in\\{0,*\\}^{p\times q}$, the
following two sets of matrices are defined:

${\bf S}_{\bar{M}}=\left\\{M\in{\mathbb{C}}^{p\times q}:M_{ij}=0\ {\text{if}}\
{\bar{M}}_{ij}=0\right\\},$ $\bar{\bf
S}_{\bar{M}}\\!=\\!\left\\{M\in{\mathbb{C}}^{p\times q}:M_{ij}=0\ {\text{if}}\
{\bar{M}}_{ij}=0,M_{ij}\neq 0\ {\text{if}}\ {\bar{M}}_{ij}=*\right\\}.$

Any $M\in{\bf S}_{\bar{M}}$ is called a realization of $\bar{M}$. For two
structured matrices $\bar{M},\bar{N}\in\\{0,*\\}^{p\times q}$, $\vee$ is the
entry-wise OR operation, i.e., $(\bar{M}\vee\bar{N})_{ij}=*$ if
$\bar{M}_{ij}=*$ or $\bar{N}_{ij}=*$; otherwise $(\bar{M}\vee\bar{N})_{ij}=0$.

A structured matrix could also be seen as a matrix whose entries are
parameterized by the free parameters of its $*$ entries, and therefore is
sometimes called a _generic matrix_ [26]. For a generic matrix $M$ and a
constant matrix $N$ with the same dimension, $M+\lambda N$ defines a generic
matrix pencil, which can be seen as a _matrix-valued polynomial of free
parameters in $M$ and the variable $\lambda$_.

###  II-B Notion of PTSC

Consider the linear time invariant (LTI) system

$\dot{x}(t)=Ax(t)+bu(t),$ (1)

where $A\in{\mathbb{C}}^{n\times n}$, $b\in{\mathbb{C}}^{n\times 1}$. It is
known that $(A,b)$ is controllable, if and only if the controllability matrix
${\cal C}(A,b)$ defined as follows has full row rank.

${\cal C}(A,b)=[b,Ab,\cdots,A^{n-1}b].$

Let ${\bar{F}}\in\\{0,*\\}^{n\times{(n+1)}}$ be a structured matrix that
specifies the structure of the perturbation (matrix) $[\Delta A,\Delta b]$,
that is, ${\bar{F}}_{ij}=0$ implies $[\Delta A,\Delta b]_{ij}=0$. In other
words, $[\Delta A,\Delta b]\in{\bf S}_{\bar{F}}$. It is emphasized that
throughout this paper, the perturbations are allowed to be _complex-valued_.
We will also call the system $(A+\Delta A,b+\Delta b)$ the perturbed system.

######  Definition 1 (PTC)

System $(A,b)$ in (1) is said to be _perturbation-tolerantly controllable_
(PTC) with respect to ${\bar{F}}$, if for all $(\Delta A,\Delta b)\in{\bf
S}_{\bar{F}}$, $(A+\Delta A,b+\Delta b)$ is controllable. If $(A,b)$ is
controllable but not PTC w.r.t. ${\bar{F}}$ (i.e., there exists a $(\Delta
A,\Delta b)\in{\bf S}_{\bar{F}}$ making $(A+\Delta A,b+\Delta b)$
uncontrollable), $(A,b)$ is said to be _perturbation-sensitively controllable_
(PSC) w.r.t. ${\bar{F}}$.

Let $\bar{A}\in\\{0,*\\}^{n\times n},\bar{b}\in\\{0,*\\}^{n\times 1}$ be the
structured matrices specifying the sparsity pattern of $A,b$, respectively.
That is, $A\in{\bf S}_{\bar{A}}$ and $b\in{\bf S}_{\bar{b}}$.

######  Definition 2 (Structural controllability)

$(\bar{A},\bar{b})$ is said to be structurally controllable, if there exists a
realization $(A,b)\in{\bf S}_{[\bar{A},\bar{b}]}$ so that $(A,b)$ is
controllable.

A property is called generic for a set of systems if, depending on the
(common) structure of parameterized systems in this set, either this property
holds for almost all of the system parameters in the corresponding parameter
space, or this property does not hold for almost all of the system parameters
[13]. It is well-known that controllability is a generic property in the sense
that, if $(\bar{A},\bar{b})$ is structurally controllable, then all
realizations of $(\bar{A},\bar{b})$ are controllable except for a set with
zero Lebesgue measure in the corresponding parameter space. For a structurally
controllable pair $(\bar{A},\bar{b})$, let ${\bf CS}(\bar{A},\bar{b})$ denote
the set of all _controllable_ complex-valued realizations of
$(\bar{A},\bar{b})$. The following proposition reveals that PTC (or PSC) is a
generic property in ${\bf CS}(\bar{A},\bar{b})$.

###### Proposition 1

With $(\bar{A},\bar{b})$ and ${\bar{F}}$ defined above, suppose that
$(\bar{A},\bar{b})$ is structurally controllable. Then, either for all
$(A,b)\in{\bf CS}(\bar{A},\bar{b})$, $(A,b)$ is PTC w.r.t. ${\bar{F}}$, or for
almost all $(A,b)\in{\bf CS}(\bar{A},\bar{b})$ except for a set with zero
Lebesgue measure in the corresponding parameter space, $(A,b)$ is PSC w.r.t.
${\bar{F}}$.

###### Proof:

Let $p_{1},...,p_{r}$ be variables that the $r$ nonzero entries of $[A,b]$
take, and $\bar{p}_{1},...,\bar{p}_{l}$ be variables that the $l$ perturbed
entries of $[\Delta A,\Delta b]$ take. Denote by $p\doteq(p_{1},...,p_{r})$
and $\bar{p}\doteq(\bar{p}_{1},...,\bar{p}_{l})$. It turns out $\det{\cal
C}(A+\Delta A,b+\Delta b)$ can be expressed as

$\det{\cal C}(A+\Delta A,b+\Delta b)=f(p)g(\bar{p})h(p,\bar{p}),$ (2)

where $f(p)$ (resp. $g(\bar{p})$) denotes the polynomial of $p$ (resp.
$\bar{p}$) with real coefficients, and $h(p,\bar{p})$ denotes the polynomial
of $p$ and $\bar{p}$ where at least one $p_{i}$ ($i\in\\{1,...,r\\}$) and one
$\bar{p}_{j}$ ($j\in\\{1,...,l\\}$) both have a term with degree no less than
one.

It can be seen that, if neither $g(\bar{p})$ nor $h(p,\bar{p})$ exists in (2),
then for all $(A,b)\in{\bf CS}(\bar{A},\bar{b})$, $(A,b)$ is PTC w.r.t.
${\bar{F}}$, as in this case, (2) is independent of $\bar{p}$. Otherwise,
suppose that there exists a $\bar{p}_{j}$, $j\in\\{1,...,l\\}$, that has a
term $\bar{p}_{j}^{k}$ with degree $k\geq 1$ in $g(\bar{p})h(p,\bar{p})$. When
$p$ and $\bar{p}\backslash\\{\bar{p}_{j}\\}$ take such values that the
coefficient of $\bar{p}_{j}^{k}$ is nonzero (Condition 1)), and meanwhile
$(A,b)$ is controllable (Condition 2)), then according to the fundamental
theorem of algebra (c.f. [27]), there exists a complex value of $\bar{p}_{j}$
making $g(\bar{p})h(p,\bar{p})=0$, thus making $\det{\cal C}(A+\Delta
A,b+\Delta b)=0$, leading to the uncontrollability of $(A+\Delta A,b+\Delta
b)$. Note that the set of values for $p$ validating Condition 1) forms a
proper algebraic variety in ${\mathbb{C}}^{r}$, which thereby has zero
Lebesgue measure in the set of values satisfying Condition 2). This proves the
proposed statements. ∎

Proposition 1 indicates that it is the structure of $(A,b)$ and ${\bar{F}}$
that domains the property of being PTC or PSC. This motivates the following
definition for structural controllability under structured numerical
perturbations:

######  Definition 3 (PTSC)

Given $\bar{A}\in\\{0,*\\}^{n\times n}$, $\bar{b}\in\\{0,*\\}^{n\times 1}$,
and a perturbation structure ${\bar{F}}\in\\{0,*\\}^{n\times(n+1)}$,
$(\bar{A},\bar{b})$ is said to be PTSC with respect to ${\bar{F}}$, if for all
$(A,b)\in{\bf CS}(\bar{A},\bar{b})$, $(A,b)$ is PTC w.r.t. ${\bar{F}}$.

If $(\bar{A},\bar{b})$ is structurally controllable but not PTSC w.r.t.
${\bar{F}}$, we will alternatively say that $(\bar{A},\bar{b})$ is
perturbation-sensitively structurally controllable (PSSC) w.r.t. ${\bar{F}}$.
From Proposition 1, PSSC of $(\bar{A},\bar{b})$ indicates that almost all
controllable realizations of $(\bar{A},\bar{b})$ are PSC w.r.t. the
perturbation structure ${\bar{F}}$.

###### Example 1

Consider a system $(A,b)$ with

$A=\left[\begin{array}[]{cccc}0&0&0&0\\\ a&0&0&0\\\ 0&c&0&0\\\ f&d&0&e\\\
\end{array}\right],b=\left[\begin{array}[]{c}h\\\ 0\\\ 0\\\ 0\\\
\end{array}\right].$

Two perturbations $[\Delta A_{i},\Delta b_{i}]$ ($i=1,2$) are given as

$\left[\begin{array}[]{ccccc}0&0&g&l&0\\\ 0&0&0&0&0\\\ 0&0&0&0&0\\\
0&0&0&0&0\\\ \end{array}\right],\left[\begin{array}[]{ccccc}0&0&0&0&0\\\
0&0&0&0&0\\\ 0&0&s&0&0\\\ 0&0&0&0&r\\\ \end{array}\right].$

It can be obtained $\det{\cal C}(A+\Delta A_{1},b+\Delta
b_{1})=a^{2}ch^{4}(fe^{2}+ade)$, which is independent of the parameters in
$[\Delta A_{1},\Delta b_{1}]$. This indicates whatever values $[\Delta
A_{1},\Delta b_{1}]$ may take, the perturbed system is always controllable (as
long as $(A,b)$ is controllable). On the other hand, $\det{\cal C}(A+\Delta
A_{2},b+\Delta b_{2})=a^{2}ch^{3}(e^{3}r-e^{2}rs+e^{2}fh-efhs+adeh-adhs)$. It
can be seen that, in case $e^{3}-se^{2}\neq 0$ (or $re^{2}+fhe+adh\neq 0$) and
$(A,b)$ is controllable, there is a value for $r$ (resp. $s$) making
$\det{\cal C}(A+\Delta A_{2},b+\Delta b_{2})=0$, leading to uncontrollability.

###### Remark 1

We remark that for multi-input systems, PTC is still a generic property, but
one should modify ‘all’ to ‘almost all’ in the last sentence of Definition 3
in defining the associated PTSC. Please see [28] for more details.

###  II-C Relations with SSC

We may also revisit PTSC from the standpoint of the _perturbed structured
system_ $[\bar{A},\bar{b}]\vee\bar{F}$. In this system, entries of system
matrices can be divided into three categories, namely, the _fixed zero
entries_ , the _unknown generic entries_ which take fixed but unknown values
(they can be seen as randomly generated values), and the _perturbed entries_
which can take arbitrarily complex values. PTSC of the perturbed structured
system requires that for almost all values of the unknown generic entries
making the original system controllable, the corresponding perturbed systems
are controllable for arbitrary values of the perturbed entries.

Recall that SSC is defined as follows.

######  Definition 4 (SSC)

$(\bar{A},\bar{b})$ is said to be SSC, if every $(A,b)\in\bar{\bf
S}_{[\bar{A},\bar{b}]}$ is controllable.

As mentioned earlier, SSC could be seen as the ability of a system to preserve
controllability under perturbations that have the same structure as the system
itself, with the constraint that the perturbed entries of the resulting system
cannot be zero. It is thus clear that the essential difference between PTSC
and SSC lies in two aspects: First, the perturbed entries can take arbitrary
values including zero in PTSC, while they must take nonzero values in SSC.
Second, in SSC, all nonzero entries can be perturbed, while in PTSC, an
arbitrary subset of entries (prescribed by the perturbation structure) can be
perturbed, and the remaining entries remain unchanged. Because of them,
neither criteria for SSC can be converted to those for PTSC, nor the converse.

##  III Preliminaries and Terminologies

In this section, we introduce some preliminaries as well as terminologies in
graph theory and structural controllability.

###  III-A Graph Theory

If not specified, all graphs in this paper refer to directed graphs. A graph
is denoted by ${\cal G}=({\cal V},{\cal E})$, where ${\cal V}$ is the vertex
set, and ${\cal E}\subseteq{\cal V}\times{\cal V}$ is the edge set. For a
graph ${\cal G}=({\cal V},{\cal E})$ with $N$ vertices, a path from vertex
$v_{i}$ to vertex $v_{j}$ is a sequence of edges $(v_{i},v_{i+1})$,
$(v_{i+1},v_{i+2})$, $\cdots$, $(v_{j-1},v_{j})$ where each edge belongs to
$\cal E$. For a set ${\cal E}_{s}\subseteq{\cal E}$, ${\cal G}-{{\cal E}_{s}}$
denotes the graph obtained from $\cal G$ after deleting the edges in ${\cal
E}_{s}$; similarly, for ${\cal V}_{s}\subseteq{\cal V}$, ${\cal G}-{\cal
V}_{s}$ denotes the graph after deleting vertices in ${\cal V}_{s}$ and all
edges incident to vertices in ${\cal V}_{s}$. For two graphs ${\cal
G}_{i}=({\cal V},{\cal E}_{i})$, $i=1,2$, ${\cal G}_{1}\cup{\cal G}_{2}$
denotes the graph $({\cal V},{\cal E}_{1}\cup{\cal E}_{2})$.

A graph ${\cal G}=({\cal V},{\cal E})$ is said to be bipartite if its vertex
set can be divided into two disjoint parts ${\cal V}_{1}$ and ${\cal V}_{2}$
such that no edge has two ends within ${\cal V}_{1}$ or ${\cal V}_{2}$. The
bipartite graph $\cal G$ is also denoted by $({\cal V}_{1},{\cal V}_{2},{\cal
E})$. A matching of a bipartite graph is a subset of its edges among which any
two do not share a common vertex. The maximum matching is the matching with
the largest number of edges among all possible matchings. The number of edges
contained in a maximum matching of a bipartite graph $\cal G$ is denoted by
${\rm mt}({\cal G})$. For a weighted bipartite graph $\cal G$, where each edge
is assigned a non-negative weight, the weight of a matching is the sum of all
edges contained in this matching. The minimum weight maximum matching (resp.
maximum weight maximum matching) is the minimal weight (resp. maximal weight)
over all maximum matchings of ${\cal G}$.

The generic rank of a structured matrix $\bar{M}$, given by ${\rm
grank}(\bar{M})$, is the maximum rank $\bar{M}$ can achieve as the function of
its free parameters. The bipartite graph associated with a structured matrix
$\bar{M}$ is given by ${\mathcal{B}}(\bar{M})=(R,C,{\mathcal{E}})$, where the
left (resp. right) vertex set $R$ ($C$) corresponds to the row index (column
index) set of $\bar{M}$, and the edge set corresponds to the set of nonzero
entries of $\bar{M}$, i.e., ${\mathcal{E}}=\\{(i,j):i\in R,j\in
C,\bar{M}_{ij}\neq 0\\}$. It is known that, ${\rm grank}(\bar{M})$ equals the
cardinality of the maximum matching of ${\mathcal{B}}(\bar{M})$.

###  III-B DM-Decomposition

Dulmage-Mendelsohn decomposition (DM-decomposition for short) is a unique
decomposition of a bipartite graph w.r.t. maximum matchings. Let ${\cal
G}=({\cal V}^{+},{\cal V}^{-},{\cal E})$ be a bipartite graph. For ${\cal
M}\subseteq{\cal E}$, we denote by $V^{+}({\cal M})$ (resp. $V^{-}({\cal M})$)
the set of vertices in ${\cal V}^{+}$ (resp. ${\cal V}^{-}$) incident to edges
in ${\cal M}$. An edge of $\cal G$ is said to be admissible, if it is
contained in some maximum matching of $\cal G$.

######  Definition 5 (DM-decomposition,[26])

The DM-decomposition of a bipartite graph ${\cal G}=({\cal V}^{+},{\cal
V}^{-},{\cal E})$ is to decompose $\cal G$ into subgraphs ${\cal G}_{k}=({\cal
V}^{+}_{k},{\cal V}^{-}_{k},{\cal E}_{k})$ ($k=0,1,...,d,\infty$) (called DM-
components of $\cal G$) satisfying:

1) ${\cal V}^{\star}=\bigcup\nolimits_{k=0}^{\infty}{\cal V}^{\star}_{k}$,
${\cal V}^{\star}_{i}\bigcap{\cal V}^{\star}_{j}=\emptyset$ for $i\neq j$,
with $\star=+$ and $-$; ${\cal E}_{k}=\\{(v^{+},v^{-})\in{\cal
E}:v^{+}\in{\cal V}^{+}_{k},v^{-}\in{\cal V}^{-}_{k}\\}$;

2) For $1\leq k\leq d$ (consistent components): ${\rm mt}({\cal G}_{k})=|{\cal
V}_{k}^{+}|=|{\cal V}_{k}^{-}|$, and each $e\in{\cal E}_{k}$ is admissible in
${\cal G}_{k}$; for $k=0$ (horizontal tail): ${\rm mt}({\cal G}_{0})=|{\cal
V}_{0}^{-}|$, $|{\cal V}_{0}^{+}|<|{\cal V}_{0}^{-}|$ if ${\cal
V}_{0}^{+}\neq\emptyset$, and each $e\in{\cal E}_{0}$ is admissible in ${\cal
G}_{0}$; for $k=\infty$ (vertical tail): ${\rm mt}({\cal G}_{\infty})=|{\cal
V}^{+}_{\infty}|$, $|{\cal V}_{\infty}^{+}|>|{\cal V}_{\infty}^{-}|$ if ${\cal
V}_{\infty}^{-}\neq\emptyset$, and each $e\in{\cal E}_{\infty}$ is admissible
in ${\cal G}_{0}$;

3) ${\cal E}_{kl}=\emptyset$ unless $1\leq k\leq l\leq d$, and ${\cal
E}_{kl}\neq\emptyset$ only if $1\leq k\leq l\leq d$, where ${\cal
E}_{kl}=\\{e\in{\cal E}:V^{+}(\\{e\\})\in{\cal V}_{k},V^{-}(\\{e\\})\in{\cal
V}_{l}\\}$;

4) ${\cal G}$ cannot be decomposed into more components satisfying conditions
1)-3).

For an $m\times l$ matrix $M$, the DM-decomposition of ${\cal B}(M)$ into
diagraphs ${\cal G}_{k}=({\cal V}^{+}_{k},{\cal V}^{-}_{k},{\cal E}_{k})$
($k=0,1,...,d,\infty$) corresponds to that there exist two permutation
matrices $P\in{\mathbb{R}}^{m\times m}$ and $Q\in{\mathbb{R}}^{l\times l}$
satisfying

$PMQ=\left[\begin{array}[]{ccccc}M_{0}&M_{01}&\cdots&M_{0d}&M_{0\infty}\\\
0&M_{1}&\cdots&M_{1d}&M_{1\infty}\\\ 0&0&\ddots&\cdots&\cdots\\\
0&0&\cdots&M_{d}&M_{d\infty}\\\ 0&0&\cdots&0&M_{\infty}\\\
\end{array}\right],$ (3)

where the submatrix $M_{k}=M[{\cal V}^{+}_{k},{\cal V}^{-}_{k}]$ corresponds
to ${\cal G}_{k}$ ($k=0,1,...,d,\infty$). Matrix (3) is also called the DM-
decomposition of $M$.

A bipartite graph is said to be DM-irreducible if it cannot be decomposed into
more than one nonempty component in the DM-decomposition. DM-decomposition is
closely related to the irreducibility of the determinant of a generic matrix.
Recall that a multivariable polynomial $f$ is irreducible if it cannot be
factored as $f=f_{1}f_{2}$ with $f_{1},f_{2}$ being polynomials with smaller
degrees than $f$.

###### Lemma 1

[26, Theorems 2.2.24, 2.2.28] For a bipartite graph ${\cal G}(M)=({\cal
V}^{+},{\cal V}^{-},{\cal E}(M))$ associated with a generic square matrix $M$,
the following conditions are equivalent:

1) ${\cal G}(M)$ is DM-irreducible;

2) ${\rm mt}({\cal G}(M)-\\{v_{1},v_{2}\\})={\rm mt}({\cal G}(M))-1$ for any
$v_{1}\in{\cal V}^{+}$ and $v_{2}\in{\cal V}^{-}$;

3) $\det M$ is irreducible.

###  III-C Structural Controllability

Given $(\bar{A},\bar{b})$, let $\mathcal{X}$, $\mathcal{U}$ denote the sets of
state vertices and input vertices respectively, i.e.,
$\mathcal{X}=\\{x_{1},...,x_{n}\\}$, $\mathcal{U}=\\{{x_{n+1}}\\}$. Denote the
edges by
$\mathcal{E}_{\mathcal{X},\mathcal{X}}(\bar{A})=\\{(x_{i},x_{j}):\bar{A}_{ji}\neq
0\\}$,
$\mathcal{E}_{\mathcal{U},\mathcal{X}}(\bar{b})=\\{({x_{n+1}},x_{i}):\bar{b}_{i}\neq
0\\}$. Let
$\mathcal{G}(\bar{A},\bar{b})=(\mathcal{X}\cup\mathcal{U},\mathcal{E}_{\mathcal{X},\mathcal{X}}(\bar{A})\cup\mathcal{E}_{\mathcal{U},\mathcal{X}}(\bar{b}))$
be the system graph associated with $(\bar{A},\bar{b})$. A state vertex
$x\in\mathcal{X}$ is said to be input-reachable, if there exists a path from
an input vertex ${x_{n+1}}$ to $x$ in $\mathcal{G}(\bar{A},\bar{b})$.
Similarly, ${\cal G}({\bar{F}})=({\cal X}\cup{\cal U},{\cal E}_{\bar{F}})$
denotes the graph associated with the perturbation structure ${\bar{F}}$,
where ${\cal E}_{\bar{F}}=\\{(x_{i},x_{j}):{\bar{F}}_{ji}\neq 0,1\leq j\leq
n,1\leq i\leq n+1\\}$.

###### Lemma 2

[26] System $(\bar{A},\bar{b})$ in (1) is structurally controllable, if and
only if 1) every state vertex $x\in{\cal X}$ is input-reachable; 2) ${\rm
grank}([\bar{A},\bar{b}])=n$.

##  IV Necessary and Sufficient Condition

In this section, we present a necessary and sufficient condition for the PTSC
in the single-input case.

###  IV-A One-edge Preservation Principle

At first, a one-edge preservation principle is given as follows, which is
fundamental to our subsequent derivations.

######  Proposition 2 (One-edge preservation principle)

Suppose $(\bar{A},\bar{b})$ is structurally controllable. $(\bar{A},\bar{b})$
is PSSC w.r.t. $\bar{F}$, if and only if there is one edge $e\in{\cal
E}_{\bar{F}}$, such that $[\bar{A},\bar{b}]\vee\bar{F}^{\\{e\\}}$ is PSSC
w.r.t. ${\bar{F}}_{\\{e\\}}$, where $\bar{F}^{\\{e\\}}$ denotes the structured
matrix associated with the graph ${\cal G}(\bar{F})-\\{e\\}$, and
${\bar{F}}_{\\{e\\}}$ the structured matrix obtained from ${\bar{F}}$ by
preserving only the entry corresponding to $e$.

###### Proof:

Let $p\doteq(p_{1},...,p_{r})$ and $\bar{p}=(\bar{p}_{1},...,\bar{p}_{l})$ be
defined similarly in the the proof of Proposition 1. From the analysis in that
proof, $(\bar{A},\bar{b})$ is PSSC w.r.t. ${\bar{F}}$, if and only if there
exists a $\bar{p}_{j}$, $j\in\\{1,...,l\\}$, that has a degree no less than
one in $\det{\cal C}(A+\Delta A,b+\Delta b)$ (expressed in (2)), where $(A,b)$
and $(\Delta A,\Delta b)$ are realizations of $(\bar{A},\bar{b})$ and $(\Delta
A,\Delta b)$ respectively, with the corresponding parameters being $p$ and
$\bar{p}$. Let $e$ be the edge corresponding to $\bar{p}_{j}$. Suppose that
the coefficient of $\bar{p}_{j}^{k}$ is nonzero for some degree $k\geq 1$.
Since the coefficient of $\bar{p}_{j}^{k}$ is a polynomial of $p$ and
${\bar{p}}\backslash\\{\bar{p}_{j}\\}$ in $\det{\cal C}(A+\Delta A,b+\Delta
b)$, it always equals that in $\det{\cal C}(A^{\prime}+\Delta
A^{\prime},b^{\prime}+\Delta b^{\prime})$, where $(A^{\prime},b^{\prime})$ has
the system graph ${\cal G}(\bar{A},\bar{b})\cup{\cal G}({\bar{F}})-\\{e\\}$,
and $[\Delta A^{\prime},\Delta b^{\prime}]$ corresponds to the perturbation
${\bar{F}}_{\\{e\\}}$, noting that $[A+\Delta A,b+\Delta b]=[A^{\prime}+\Delta
A^{\prime},b^{\prime}+\Delta b^{\prime}]$ in the symbolic operation sense.
Upon observing this, the proposed statement follows immediately. ∎

It is remarkable that the one-edge preservation principle does _not_ mean the
perturbation of only one entry is enough to destroy controllability; Instead,
it means we can regard $|{\cal E}_{\bar{F}}|-1$ entries of $\bar{F}$ as
unknown generic entries (_in other words, their values can be chosen randomly;
but not fixed zero_) and find suitable values for the last entry. This
principle indicates that verifying the PTSC w.r.t. an arbitrary perturbation
structure can be reduced to an equivalent problem with a single-edge
perturbation structure. Having observed this, in the following, we will give
the conditions for the absence of zero uncontrollable modes and nonzero
uncontrollable modes, respectively, in the single-edge perturbation scenario.
Recall that an uncontrollable mode for $(A,B)$ is a $\lambda\in{\mathbb{C}}$
making ${\rm rank}([A-\lambda I,B])<n$. Then, based on Proposition 2,
conditions for PTSC with a general perturbation structure will be obtained.

###  IV-B Condition for Zero Mode

Let $\bar{H}\doteq[\bar{A},\bar{b}]$. For $j\in\\{1,...,n+1\\}$, let
$r_{j}={\rm grank}(\bar{H}[{\cal J}_{n},{\cal J}_{n+1}\backslash\\{j\\}])$.
Define sets ${\cal I}_{j}$ and ${\cal I}^{*}_{j}$ as

$\begin{array}[]{c}\begin{aligned} {\cal I}_{j}&=\left\\{{\cal
I}\subseteq{\cal J}_{n}:{\rm grank}(\bar{H}[{\cal I},{\cal
J}_{n+1}\backslash\\{j\\}])=r_{j},|{\cal I}|=r_{j}\right\\},\\\ {\cal
I}^{*}_{j}&=\left\\{{\cal J}_{n}\backslash w:w\in{\cal
I}_{j}\right\\}.\end{aligned}\end{array}$

Based on these definitions, the following proposition gives a necessary and
sufficient condition for the absence of zero uncontrollable modes in the
single-edge perturbation scenario.

###### Proposition 3

Suppose that $(\bar{A},\bar{b})$ is structurally controllable, and there is
only one nonzero entry in ${\bar{F}}$ with its position being $(i,j)$. Then,
for almost all $(A,b)\in{\bf CS}(\bar{A},\bar{b})$, there is no $(\Delta
A,\Delta b)\in{\bf S}_{{\bar{F}}}$ such that a nonzero $n$-vector $q$ exists
making $q^{\intercal}[A+\Delta A,b+\Delta b]=0$, if and only if $i\notin{\cal
I}^{*}_{j}$.

To prove Proposition 3, we need the following lemma.

###### Lemma 3

Given a matrix $H\in{\mathbb{C}}^{p\times q}$ of rank $p-1$, let
$x\in{\mathbb{C}}^{p}$ be a nonzero vector in the left null space of $H$.
Then, for any $i\in{\cal J}_{p}$, $x_{i}\neq 0$, if and only if $H[{{\cal
J}_{p}\backslash\\{i\\},{\cal J}_{q}}]$ is of full row rank.

###### Proof:

The proof is quite standard, thus omitted here. ∎

_Proof of Proposition 3:_ Sufficiency: Since $(\bar{A},\bar{b})$ is
structurally controllable, ${\rm grank}(\bar{H})=n$, which means that
$r_{j}=n$ or $n-1$. If $r_{j}=n$, then ${\cal I}^{*}_{j}=\emptyset$, which
immediately indicates that no $q(\neq 0)$ exists making
$q^{\intercal}[A+\Delta A,b+\Delta b]=0$ for almost all $(A,b)\in{\bf
CS}(\bar{A},\bar{b})$. Now suppose $r_{j}=n-1$. A vector $q(\neq 0)$ making
$q^{\intercal}[A+\Delta A,b+\Delta b]$ must lie in the left null space of
$H[{\cal J}_{n},J_{n+1}\backslash\\{j\\}]$, for almost all $H\in{\bf
S}_{\bar{H}}$. As $r_{j}=n-1$, for almost all $(A,b)\in{\bf
CS}(\bar{A},\bar{b})$, ${\cal I}^{*}_{j}$ consists of all the nonzero
positions of $q$ according to Lemma 3. As a result, if $i\notin{\cal
I}^{*}_{j}$,

$q^{\intercal}[A+\Delta A,b+\Delta b][{\cal
J}_{n},\\{j\\}]=\sum\nolimits_{k\in{\cal I}^{*}_{j}}q_{k}[A,b]_{kj}\neq 0,$

where the inequality is due to the fact that $[A,b]$ has full row rank.

Necessity: Assume that $i\in{\cal I}^{*}_{j}$. As ${\cal
I}^{*}_{j}\neq\emptyset$ and $(\bar{A},\bar{b})$ is structurally controllable,
$[A,b][{\cal J}_{n},{\cal J}_{n+1}\backslash\\{j\\}]$ has rank $n-1$ for all
$(A,b)\in{\bf CS}(\bar{A},\bar{b})$. Let $q$ be a nonzero vector in the left
null space of $[A,b][{\cal J}_{n},{\cal J}_{n+1}\backslash\\{j\\}]$. According
to Lemma 3, as $i\in{\cal I}^{*}_{j}$, we have $q_{i}\neq 0$ for almost all
$(A,b)\in{\bf CS}(\bar{A},\bar{b})$. By setting $[\Delta A,\Delta
b]_{ij}=-1/q_{i}\sum\nolimits_{k\in{\cal
I}^{*}_{j}\backslash\\{i\\}}q_{k}[A,b]_{kj}$, we get

$q^{\intercal}[A+\Delta A,b+\Delta b][{\cal
J}_{n},\\{j\\}]=\sum\nolimits_{k\in{\cal I}^{*}_{j}}q_{k}[A,b]_{kj}=0,$

which makes $q^{\intercal}[A+\Delta A,b+\Delta b]=0$. $\hfill\Box$

###### Remark 2

From the proof of Proposition 3, provided $(\bar{A},\bar{b})$ is structurally
controllable, $i\notin{\cal I}_{j}^{*}$ is equivalent to that, ${\rm
grank}(\bar{H}[{\cal J}_{n},{\cal J}_{n+1}\backslash\\{j\\}])=n$
(corresponding to $r_{j}=n$) or ${\rm grank}(\bar{H}[{\cal
J}_{n}\backslash\\{i\\},{\cal J}_{n+1}\backslash\\{j\\}])=n-2$ (corresponding
to $r_{j}=n-1$ but ${\rm grank}(\bar{H}[{\cal J}_{n}\backslash\\{i\\},{\cal
J}_{n+1}\backslash\\{j\\}])<n-1$). Moreover, since adding a column to a matrix
can increase its rank by at most one, the latter two conditions are mutually
exclusive.

###  IV-C Condition for Nonzero Mode

In the following, we present a necessary and sufficient condition for the
absence of nonzero uncontrollable modes using the DM-decomposition.

For $j\in{\cal J}_{n+1}$, let $j_{\rm c}\doteq{\cal
J}_{n+1}\backslash\\{j\\}$. Moreover, define a generic matrix pencil as
$H_{\lambda}\doteq[\bar{A}-\lambda I,\bar{b}]$, $H_{\lambda}^{j}\doteq
H_{\lambda}[{\cal J}_{n},\\{j\\}]$, and $H_{\lambda}^{{j_{\rm c}}}\doteq
H_{\lambda}[{\cal J}_{n},j_{c}]$. Here, the subscript $\lambda$ indicates a
matrix-valued function of $\lambda$. Let ${\cal B}(H_{\lambda})=({\cal
V}^{+},{\cal V}^{-},{\cal E})$ be the bipartite graph associated with
$H_{\lambda}$, where ${\cal V}^{+}=\\{x_{1},...,x_{n}\\}$, ${\cal
V}^{-}=\\{v_{1},...,v_{n+1}\\}$, and ${\cal E}=\\{(x_{i},v_{k}):{\cal
E}_{I}\cup{\cal E}_{[\bar{A},\bar{b}]}\\}$ with ${\cal
E}_{I}=\\{(x_{i},v_{i}):i=1,...,n\\}$, ${\cal
E}_{[\bar{A},\bar{b}]}=\\{(x_{i},v_{k}):[\bar{A},\bar{b}]_{ik}\neq 0\\}$. No
parallel edges are included even if ${\cal E}_{I}\cap{\cal
E}_{[\bar{A},\bar{b}]}\neq\emptyset$. An edge is called a $\lambda$-edge if it
belongs to ${\cal E}_{I}$, and a self-loop if it belongs to ${\cal
E}_{I}\cap{\cal E}_{[\bar{A},\bar{b}]}$. Note by definition, a self-loop is
also a $\lambda$-edge. Let ${\cal B}(H_{\lambda}^{{j_{\rm c}}})$ be the
bipartite graph associated with $H_{\lambda}^{{j_{\rm c}}}$, that is, ${\cal
B}(H_{\lambda}^{{j_{\rm c}}})={\cal B}(H_{\lambda})-\\{v_{j}\\}$.

###### Lemma 4

Suppose $(\bar{A},\bar{b})$ is structurally controllable. Then ${\rm mt}({\cal
B}(H_{\lambda}^{{j_{\rm c}}}))=n$ for all $j\in{\cal J}_{n+1}$.

###### Proof:

If $j=n+1$, it is obvious ${\rm mt}({\cal B}(H_{\lambda}^{{j_{\rm c}}}))=n$ as
${\cal E}_{I}$ is a matching with size $n$. Now consider $j\in\\{1,...,n\\}$.
As $(\bar{A},\bar{b})$ is structurally controllable, from Lemma 2, there is a
path from $x_{n+1}$ to $x_{j}$ in the system graph ${\cal
G}(\bar{A},\bar{b})$. Denote such a path by
$\\{(x_{n+1},x_{j_{1}}),(x_{j_{1}},x_{j_{2}}),...,(x_{j_{r-1}},x_{j_{r}})\\}$
with $\\{j_{1},...,j_{r}\\}\subseteq{\cal J}_{n}$ and $j_{r}=j$. Since each
$(x_{j_{k}},x_{j_{k+1}})$ in ${\cal G}(\bar{A},\bar{b})$ corresponds to
$(x_{j_{k+1}},v_{j_{k}})$ in ${\cal B}(H_{\lambda})$,
$\\{(x_{j_{1}},v_{n+1}),(x_{j_{2}},v_{j_{1}}),...,(x_{j_{r}},v_{j_{r-1}})\\}\cup\\{(x_{i},v_{i}):i\in{\cal
J}_{n}\backslash\\{j_{1},...,j_{r}\\}\\}$ forms a matching with size $n$ in
${\cal B}(H_{\lambda}^{{j_{\rm c}}})$. ∎

Let ${\cal G}^{j_{\rm c}}_{k}=({\cal V}^{+}_{k},{\cal V}_{k}^{-},{\cal
E}_{k})$ ($k=0,1,...,d,\infty$) be the DM-components of ${\cal
B}(H_{\lambda}^{{j_{\rm c}}})$. From Lemma 4, we know that both the horizontal
tail and the vertical one are empty. Accordingly, let $M^{j_{\rm
c}}_{\lambda}$ be the DM-decomposition of $H_{\lambda}^{{j_{\rm c}}}$ with the
corresponding permutation matrices $P$ and $Q$, i.e.,

$PH_{\lambda}^{{j_{\rm c}}}Q=\left[\begin{array}[]{ccc}M^{j_{\rm
c}}_{1}(\lambda)&\cdots&M^{j_{\rm c}}_{1d}(\lambda)\\\ 0&\ddots&\vdots\\\
0&\cdots&M^{j_{\rm c}}_{d}(\lambda)\\\ \end{array}\right]\doteq M^{j_{\rm
c}}_{\lambda}.$ (4)

Moreover, define $M_{\lambda}^{j}\doteq PH_{\lambda}^{j}$. Suppose that
$x_{i}$ is the $\bar{i}$th vertex in ${\cal V}^{+}_{i^{*}}$
($1\leq\bar{i}\leq|{\cal V}^{+}_{i^{*}}|$, $1\leq i^{*}\leq d$).

For $k\in\\{1,...,d\\}$, let $\gamma_{\min}({\cal G}_{k}^{j_{\rm c}})$ and
$\gamma_{\max}({\cal G}_{k}^{j_{\rm c}})$ be respectively the minimum number
of $\lambda$-edges and maximum number of $\lambda$-edges contained in a
matching among all maximum matchings of ${\cal G}_{k}^{j_{\rm c}}$.
Afterwards, define a boolean function $\gamma_{\rm nz}(\cdot)$ for ${\cal
G}_{k}^{j_{\rm c}}$ as

$\gamma_{\rm nz}({\cal G}_{k}^{j_{\rm
c}})=\begin{cases}1&{\begin{array}[]{c}\text{if}\ \gamma_{\max}({\cal
G}_{k}^{j_{\rm c}})-\gamma_{\min}({\cal G}_{k}^{j_{\rm c}})>0\\\ \text{or}\
{\cal G}_{k}^{j_{\rm c}}\ {\text{contains a self-loop}}\end{array}}\\\
0&\text{otherwise}.\end{cases}$ (5)

From Lemma 7 in the appendix, $\gamma_{\rm nz}({\cal G}_{k}^{j_{\rm c}})=1$
means $\det M_{k}^{j}(\lambda)$ has at least one nonzero root for $\lambda$,
while $\gamma_{\rm nz}({\cal G}_{k}^{j_{\rm c}})=0$ means the contrary. The
following lemma shows that $\gamma_{\rm nz}({\cal G}_{k}^{j_{\rm c}})$ can be
determined in polynomial time via the maximum/minimum weight maximum matching
algorithms.

###### Lemma 5

Assign the following weight function $W_{k}:{\cal E}_{k}\rightarrow\\{0,1\\}$
for ${\cal G}_{k}^{j_{\rm c}}$ as

$W_{k}(e)=\begin{cases}1&\text{if}\ e\ \text{is a}\ \lambda\text{-edge}\\\
0&\text{if}\ e\in{\cal E}_{k}\backslash{\cal E}_{I}.\end{cases}$

Then, it is true that

$\gamma_{\max}({\cal G}_{k}^{j_{\rm c}})={\text{ the maximum weight maximum
matching of}}\ {\cal G}_{k}^{j_{\rm c}},$ $\gamma_{\min}({\cal G}_{k}^{j_{\rm
c}})={\text{ the minimum weight maximum matching of}}\ {\cal G}_{k}^{j_{\rm
c}}.$

###### Proof:

Straightforward from the construction of $W_{k}$ and the definitions of the
maximum (minimum) weight maximum matching of a bipartite graph. ∎

Furthermore, define a set

${\Omega}_{j}=\\{k\in{\mathbb{N}}:1\leq k\leq i^{*},{\gamma}_{\rm nz}({\cal
G}^{j_{\rm c}}_{k})=1\\}.$ (6)

For each $k\in{\Omega}_{j}$, define a weighted bipartite graph ${\cal
G}^{j_{\rm c}}_{ki^{*}}=\left(\bar{\cal V}^{+}_{ki^{*}},\bar{\cal
V}^{-}_{ki^{*}},\bar{\cal E}_{ki^{*}},W\right)$, where $\bar{\cal
V}^{+}_{ki^{*}}={\cal V}^{+}_{k}\cup{\cal V}^{+}_{k+1}\cdots\cup{\cal
V}^{+}_{i^{*}}\backslash\\{x_{i}\\}$, $\bar{\cal V}^{-}_{ki^{*}}={\cal
V}^{-}_{k}\cup{\cal V}^{-}_{k+1}\cdots\cup{\cal V}^{-}_{i^{*}}$, $\bar{\cal
E}_{ki^{*}}=\\{(x_{i},v_{l})\in{\cal E}:x_{i}\in\bar{\cal
V}^{+}_{ki^{*}},v_{l}\in\bar{\cal V}^{-}_{ki^{*}}\\}$, and the weight
$W(e):\bar{\cal E}_{ki^{*}}\rightarrow\\{0,1\\}$

$W(e)=\begin{cases}1&\text{if}\ e\in{\cal E}_{k}\\\
0&{\text{otherwise.}}\end{cases}$

In other words, ${\cal G}_{ki^{*}}^{j_{\rm c}}$ is the subgraph of ${\cal
B}(H^{j_{\rm c}}_{\lambda})$ induced by vertices $\bar{\cal
V}_{ki^{*}}^{+}\cup\bar{\cal V}^{-}_{ki^{*}}$.

###### Proposition 4

Suppose $(\bar{A},\bar{b})$ is structurally controllable, and there is only
one nonzero entry in ${\bar{F}}$ with its position being $(i,j)$. Then, for
almost all $(A,b)\in{\bf CS}(\bar{A},\bar{b})$, there is a $(\Delta A,\Delta
b)\in{\bf S}_{{\bar{F}}}$ such that a nonzero $n$-vector $q$ exists making
$q^{\intercal}[A+\Delta A-\lambda I,b+\Delta b]=0$ for some nonzero
$\lambda\in{\mathbb{C}}$, if and only if there exists a $k\in{\Omega}_{j}$
associated with which the minimum weight maximum matching of ${\cal G}^{j_{\rm
c}}_{ki^{*}}$ defined above is less than $|{\cal V}^{+}_{k}|$.

The proof relies on a series of nontrivial results on the roots of
determinants of generic matrix pencils, which is postponed to the appendix.

###  IV-D Necessary and Sufficient Condition

We are now giving a necessary and sufficient condition for PTSC with general
perturbation structures.

###### Theorem 1

Consider a structurally controllable pair $(\bar{A},\bar{b})$ and the
perturbation structure $\bar{F}$. For each edge $e\doteq(x_{j},x_{i})\in{\cal
E}_{\bar{F}}$, let
$[\bar{A}^{e},\bar{b}^{e}]=[\bar{A},\bar{b}]\vee\bar{F}^{\\{e\\}}$, with
$\bar{F}^{\\{e\\}}$ defined in Proposition 2. Moreover, let ${\Omega}_{j}$ and
${\cal G}^{j_{\rm c}}_{ki^{*}}$ be defined in the same way as in Proposition
4, in which $(\bar{A},\bar{b})$ shall be replaced with
$(\bar{A}^{e},\bar{b}^{e})$. Then, $(\bar{A},\bar{b})$ is PTSC w.r.t.
$\bar{F}$, if and only if for each edge $e\doteq(x_{j},x_{i})\in{\cal
E}_{\bar{F}}$, it holds simultaneously:

1) ${\rm grank}(\bar{H}[{\cal J}_{n},{\cal J}_{n+1}\backslash\\{j\\}])=n$ or
${\rm grank}(\bar{H}[{\cal J}_{n}\backslash\\{i\\},{\cal
J}_{n+1}\backslash\\{j\\}])=n-2$, with $\bar{H}=[\bar{A}^{e},\bar{b}^{e}]$;

2) ${\Omega}_{j}=\emptyset$, or otherwise for each $k\in{\Omega}_{j}$, the
minimum weight maximum matching of the bipartite ${\cal G}^{j_{\rm
c}}_{ki^{*}}$ is $|{\cal V}^{+}_{k}|$.

###### Proof:

Follows immediately from Propositions 2-4. ∎

Since each step in Theorem 1 can be implemented in polynomial time, its
verification has polynomial complexity. To be specific, for each edge
$e\in{\cal E}_{\bar{F}}$, to verify Condition 1), we can invoke the Hopcroft-
Karp algorithm twice, which incurs time complexity $O(n^{0.5}|{\cal
E}_{[\bar{A},\bar{b}]}\cup{\cal E}_{\bar{F}}|)$ $\to O(n^{2.5})$. As for
Condition 2), the DM-decomposition incurs $O(n^{2.5})$, and computing the
minimum weight maximum matching of ${\cal G}_{ki^{*}}^{j_{\rm c}}$ costs
$O(n^{3})$ [29]. Since $|\Omega_{j}|\leq n$, for each $e\in{\cal
E}_{\bar{F}}$, verifying Condition 2) takes at most $O(n^{2.5}+n*n^{3})$. To
sum up, verifying Theorem 1 incurs time complexity at most $O(|{\cal
E}_{\bar{F}}|(n^{2.5}+n^{4}))$, i.e., $O(|{\cal E}_{\bar{F}}|n^{4})$. The
procedure for verifying PTSC can be summarized as follows.

Algorithm for verifying PTSC for $(\bar{A},\bar{b})$ w.r.t. $\bar{F}$:

  * 1.

Check structural controllability of $(\bar{A},\bar{b})$. If yes, continue;
otherwise, break and return false.

  * 2.

For each $e=(x_{j},x_{i})\in{\cal E}_{\bar{F}}$, construct
$(\bar{A}^{e},\bar{b}^{e})$, and implement the following steps:

    * 2.1

Check whether ${\rm grank}(\bar{H}[{\cal J}_{n},{\cal
J}_{n+1}\backslash\\{j\\}])=n$ or ${\rm grank}(\bar{H}[{\cal
J}_{n}\backslash\\{i\\},{\cal J}_{n+1}\backslash\\{j\\}])=n-2$, with
$\bar{H}=[\bar{A}^{e},\bar{b}^{e}]$. If yes, continue; otherwise, return
false.

    * 2.2

Construct $\Omega_{j}$ and ${\cal G}^{j_{\rm c}}_{ki^{*}}$ associated with
$(\bar{A}^{e},\bar{b}^{e})$.

    * 2.3

For each $k\in\Omega_{j}$, check whether the minimum weight maximum matching
of ${\cal G}^{j_{\rm c}}_{ki^{*}}$ is equal to $|{\cal V}^{+}_{k}|$. If yes,
continue; otherwise, break and return false.

  * 3.

If not break, return true.

######  Example 2 (Example 1 continuing)

Let us revisit Example 1. Consider the perturbation $[\Delta A_{2},\Delta
b_{2}]$. For edge $e=(x_{5},x_{4})$, the DM-decomposition of
$H_{\lambda}^{j_{\rm c}}$ ($j=5$) associated with $(\bar{A}^{e},\bar{b}^{e})$
and the corresponding $M_{\lambda}^{j}$ are respectively

$M_{\lambda}^{j_{\rm
c}}\\!=\\!\left[\begin{array}[]{c|c|c|c}s-\lambda&0&c&0\\\
\hline\cr&e-\lambda&d&f\\\
\cline{2-4}\cr\lx@intercol\hfil\hfil\lx@intercol\vrule\lx@intercol&-\lambda&a\\\
\cline{3-4}\cr\lx@intercol\hfil\hfil\lx@intercol\vrule\lx@intercol&-\lambda\end{array}\right],M_{\lambda}^{j}\\!=\\!\left[\\!\begin{array}[]{c}0\\\
r\\\ 0\\\ h\\\ \end{array}\\!\right].$

It can be obtained that, $i^{*}=2$, and $\Omega_{j}=\\{1,2\\}$. Since
$i^{*}\in\Omega_{j}$, according to Proposition 4, the corresponding perturbed
system can have nonzero uncontrollable modes (in fact, if
$i^{*}\in\Omega_{j}$, then the condition in Proposition 4 is automatically
satisfied). Therefore, $(\bar{A},\bar{b})$ is PSSC w.r.t.
$[\Delta\bar{A}_{2},\Delta\bar{b}_{2}]$, which is consistent with Example 1.
On the other hand, consider the perturbation $(\Delta A_{1},\Delta b_{1})$.
For the edge $e=(x_{4},x_{1})$, upon letting $j=4$, we obtain ${\cal
I}_{j}^{*}=\\{2,3,4\\}$, which means $1\notin{\cal I}_{j}^{*}$. Hence, the
condition in Proposition 3 is satisfied. Moreover, the associated
$M_{\lambda}^{j_{\rm c}}$ and $M_{\lambda}^{j}$ are respectively

$M_{\lambda}^{j_{\rm c}}=\left[\begin{array}[]{c|c|c|c}h&g&-\lambda&0\\\
\hline\cr&-\lambda&0&c\\\
\cline{2-4}\cr\lx@intercol\hfil\hfil\lx@intercol\vrule\lx@intercol&f&d\\\
\cline{3-4}\cr\lx@intercol\hfil\hfil\lx@intercol\vrule\lx@intercol&a&-\lambda\end{array}\right],M_{\lambda}^{j}=\left[\begin{array}[]{c}l\\\
0\\\ e-\lambda\\\ 0\\\ \end{array}\right],$

from which, $i^{*}=1$, and $\Omega_{j}=\emptyset$. It means Condition 2) of
Theorem 1 is satisfied. Similar analysis could be applied to the edge
$e=(x_{3},x_{1})$, and it turns out that both conditions in Theorem 1 hold.
Therefore, $(\bar{A},\bar{b})$ is PTSC w.r.t.
$[\Delta\bar{A}_{1},\Delta\bar{b}_{1}]$, which is also consistent with Example
1.

##  V Implications to SCRPs

PTC reflects the ability of a numerical system to preserve controllability
under structured perturbations. This notion is closely related to the SCRP
studied in [18, 21, 20], where the problem is formulated as searching the
smallest perturbations (in terms of the Frobenius norm or $2$-norm) with a
prescribed structure that result in an uncontrollable system.

It turns out that the SCRP is feasible, if and only if the original system is
PSC w.r.t. the corresponding perturbation structure (considering complex-
valued perturbations). Hence, before implementing any numerical algorithms on
the (single-input) SCRP, we can check whether the corresponding structured
system is PTSC w.r.t. the perturbation structure. If the answer is yes and the
original numerical system is controllable, then there cannot exist numerical
perturbations with the prescribed structure for which the perturbed system is
uncontrollable; otherwise, with probability $1$ (before looking at the exact
parameters of the original system), such a structured numerical perturbation
exists.

##  VI Conclusion

This paper proposes a novel notion of PTSC to study controllability
preservation for a structured system under structured numerical perturbations.
It is shown this notion can characterize the generic property in
controllability preservation for structured systems under structured numerical
perturbations. A necessary and sufficient condition is given for a single-
input system to be PTSC w.r.t. a prescribed perturbation structure. Readers
can refer to [28] for extensions of this work to the multi-input case.

###  -A Proof of Proposition 4

###### Lemma 6

[30, Lemma 2] Let $p_{1}(\lambda,t_{1},...,t_{r})$ and
$p_{2}(\lambda,t_{1},...,t_{r})$ be two polynomials on the variables
$\lambda,t_{1},...,t_{r}$ with real coefficients. Then, 1) For all
$(t_{1},...,t_{r})\in{\mathbb{C}}^{r}$, $p_{1}(\lambda,t_{1},...,t_{r})$ and
$p_{2}(\lambda,t_{1},...,t_{r})$ share a common zero for $\lambda$, if and
only if $p_{1}(\lambda,t_{1},...,t_{r})$ and $p_{2}(\lambda,t_{1},...,t_{r})$
share a common factor in which the leading degree for $\lambda$ is nonzero; 2)
If the above-mentioned condition is not satisfied, then for almost al
$(t_{1},...,t_{r})\in{\mathbb{C}}^{r}$ (except for a set with zero Lebsgue
measure), $p_{1}(\lambda,t_{1},...,t_{r})$ and
$p_{2}(\lambda,t_{1},...,t_{r})$ do not share a common zero for $\lambda$.

###### Lemma 7

Let $M$ be an $n\times n$ generic matrix over the variables $t_{1},...,t_{r}$,
and $E\in\\{0,1\\}^{n\times n}$, where each row, as well as each column of
$E$, has at most one entry being $1$ and the rest being $0$. Let
$P_{\lambda}\doteq M-\lambda E$ be a generic matrix pencil. Moreover, ${\cal
B}({P_{\lambda}})$ is the bipartite graph associated with $P_{\lambda}$
defined similarly to ${\cal B}(H_{\lambda})$ by replacing $I$ with $E$
(notably, self-loops are edges in ${\cal E}_{E}\cap{\cal E}_{M}$). The
following statements are true:

1) Suppose ${\cal B}({P_{\lambda}})$ contains no self-loop. Let
$\gamma_{\min}({\cal B}({P_{\lambda}}))$ and $\gamma_{\max}({\cal
B}({P_{\lambda}}))$ be respectively the minimum number of $\lambda$-edges and
maximum number of $\lambda$-edges contained in a matching among all maximum
matchings of ${\cal B}({P_{\lambda}})$. Then, the generic number of nonzero
roots of $\det(P_{\lambda})$ for $\lambda$ (counting multiplicities) equals
$\gamma_{\max}({\cal B}({P_{\lambda}}))-\gamma_{\min}({\cal
B}({P_{\lambda}}))$.

2) If ${\cal B}({P_{\lambda}})$ is DM-reducible, then $\det(P_{\lambda})$
generically has nonzero roots for $\lambda$ whenever ${\cal B}({P_{\lambda}})$
contains a self-loop.

3) Suppose that ${\cal B}({P_{\lambda}})$ is DM-reducible. Let ${\cal T}_{i}$
be the subset of variables of $t_{1},...,t_{r}$ that appear in the $i$th
column of $M$. Then, for each $i\in\\{1,...,n\\}$, every nonzero root of
$\det(P_{\lambda})$ (if exists) cannot be independent of ${\cal T}_{i}$.

###### Proof:

We first prove an useful observation, that every maximum matching of ${\cal
B}({P_{\lambda}})$ corresponds to a nonzero term (monomial) in
$\det(P_{\lambda})$ that cannot be zeroed out by other terms, which is
fundamental to the following proofs. For this purpose, consider a term
$\lambda^{r_{1}}t_{l_{1}}t_{l_{2}}\cdots t_{l_{r_{2}}}$ associated with a
maximum matching of ${\cal B}({P_{\lambda}})$, where $r_{1}+r_{2}=n$ and
$\\{l_{1},...,l_{r_{2}}\\}\subseteq\\{1,...,r\\}$. The only case to zero out
$\lambda^{r_{1}}t_{l_{1}}t_{l_{2}}\cdots t_{l_{r_{2}}}$ in $\det(P_{\lambda})$
is that there exists a term being $\lambda^{r_{1}}t_{l_{1}}t_{l_{2}}\cdots
t_{l_{r_{2}}}$ associated with another maximum matching of ${\cal
B}({P_{\lambda}})$. Now suppose that $R$ (resp. $C$) is the set of row indices
(resp. column indices) of $t_{l_{1}},...,t_{l_{r_{2}}}$ in $M$, recalling that
each $t_{i}$ ($i=1,...,r$) appears only once. Then, $\lambda^{r_{1}}$ must
correspond to $r_{1}$ ‘1’ entries in $E[{\cal J}_{n}\backslash R,{\cal
J}_{n}\backslash C]$. However, as each row and each column has at most one
‘$1$’ in $E$, the aforementioned configuration for ‘$1$’ entries is unique, a
contraction to the existence of two different maximum matchings associated
with $\lambda^{r_{1}}t_{l_{1}}t_{l_{2}}\cdots t_{l_{r_{2}}}$.

We now prove 1). Suppose $\det(P_{\lambda})$ can be factored as
$\lambda^{l}f(\lambda,t_{1},...,t_{r})$, where $l\in{\mathbb{N}}$ and
$f(\lambda,t_{1},...,t_{r})$ is a polynomial of $\lambda,t_{1},...,t_{r}$ that
does not contain factors in the form of $\lambda^{\bar{l}}$ for any
$\bar{l}\geq 1$. Because of the above observation, every term associated with
a maximum matching of ${\cal B}({P_{\lambda}})$ must contain the factor
$\lambda^{l}$. Therefore, the number $l$ of zero roots of $\det(P_{\lambda})$
equals $\gamma_{\min}({\cal B}({P_{\lambda}}))$. In addition, the maximum
degree of $\lambda$ in $\lambda^{l}f(\lambda,t_{1},...,t_{r})$ appears in a
term associated with a maximum matching containing the maximum number of
$\lambda$-edges, which is exactly $\gamma_{\max}({\cal B}({P_{\lambda}}))$.
The conclusion in 1) then follows immediately from the fundamental theorem of
algebra.

Next, we prove 2). Consider a self-loop with the entry being $t_{l}-\lambda$
($1\leq l\leq r$). As ${\cal B}({P_{\lambda}})$ is DM-reducible, every nonzero
entry must be contained in $\det(P_{\lambda})$ by Definition 5, which means
$t_{l}-\lambda$ is contained in some term $(t_{l}-\lambda)f$ of
$\det(P_{\lambda})$, where $f$ denotes a polynomial over variables
$\\{t_{1},...,t_{r}\\}\backslash\\{t_{l}\\}$ and $\lambda$. This term can be
written as the sum of two terms $t_{l}f$ and $t_{l}\lambda f$, which indicates
$\det(P_{\lambda})$ contains at least two monomials whose degrees for
$\lambda$ differ from each other. Then, following the similar reasoning to the
proof of 1), $\det(P_{\lambda})$ contains at least one nonzero root.

We are now proving 3). Suppose such a nonzero root exists that is independent
of ${\cal T}_{i}$ for some $i\in\\{1,...,n\\}$, and denote it by $z$. Let
${\cal T}[{\cal I}_{1},{\cal I}_{2}]$ be the set of variables in
$t_{1},...,t_{r}$ that appear in $M[{\cal I}_{1},{\cal I}_{2}]$ for ${\cal
I}_{1},{\cal I}_{2}\subseteq{\cal J}_{n}$, and let $R({\cal T}_{s})$ (resp.
$C({\cal T}_{s})$) be the set of row (resp. column) indices of variables
${\cal T}_{s}\subseteq\\{t_{1},...,t_{r}\\}$. Suppose
$[P_{\lambda}]_{k_{0},i}=\lambda$ for some $k_{0}\in{\cal J}_{n}\backslash
R({\cal T}_{i})$ ($k_{0}$ can be empty). Upon letting all $t_{k}\in{\cal
T}_{i}$ be zero, we obtain ($P_{z}=M-zE$)

${\small\begin{array}[]{c}\begin{aligned}
&\det(P_{z})=\sum\nolimits_{j=1}^{n}(-1)^{i+j}[P_{z}]_{ji}\det(P_{z}[{\cal
J}_{n}\backslash\\{j\\},{\cal J}_{n}\backslash\\{i\\}])\\\
&=z\cdot\det(P_{z}[{\cal J}_{n}\backslash\\{k_{0}\\},{\cal
J}_{n}\backslash\\{i\\}])=0,\end{aligned}\end{array}}$

which indicates

$\det(P_{z}[{\cal J}_{n}\backslash\\{k_{0}\\},{\cal
J}_{n}\backslash\\{i\\}])=0,$ (7)

as $z\neq 0$. Since $(P_{\lambda}[{\cal J}_{n}\backslash\\{k_{0}\\},{\cal
J}_{n}\backslash\\{i\\}])$ has full generic rank from Lemma 1, it concludes
that $z$ depends solely on the variables ${\cal T}[{\cal
J}_{n}\backslash\\{k_{0}\\},{\cal J}_{n}\backslash\\{i\\}]$. Similarly,
because of (7), for each $t_{k}\in{\cal T}_{i}$, fixing all $t_{j}\in{\cal
T}_{i}\backslash\\{t_{k}\\}$ to be zero yields

$\det(P_{z}[{\cal J}_{n}\backslash R(\\{t_{k}\\}),{\cal
J}_{n}\backslash\\{i\\}])=0,$

which indicates that $z$ depends on the variables ${\cal T}[{\cal
J}_{n}\backslash R(\\{t_{k}\\}),{\cal J}_{n}\backslash\\{i\\}]$, being
independent of the remaining variables. Taking the intersection of ${\cal
T}[{\cal J}_{n}\backslash\\{j\\},{\cal J}_{n}\backslash\\{i\\}]$ over all
$j\in R({\cal T}_{i})\cup\\{k_{0}\\}$, we obtain ${\cal T}[\Theta,{\cal
J}_{n}\backslash\\{i\\}]$, where $\Theta\doteq{\cal J}_{n}\backslash(R({\cal
T}_{i})\cup\\{k_{0}\\})$. That is, $z$ depends on variables ${\cal
T}[\Theta,{\cal J}_{n}\backslash\\{i\\}]$, and makes $P_{\lambda}[\Theta,{\cal
J}_{n}\backslash\\{i\\}]$ row rank deficient. However, for each pair $(j,l)$,
$j\\!\in\\!{\cal J}_{n}\backslash\\{i\\}$, $l\in R({\cal T}_{i})$, it holds

$\begin{array}[]{c}\begin{aligned} &{\rm grank}(P_{\lambda}[\Theta,{\cal
J}_{n}\backslash\\{i,j\\}])\\\
&\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny(a)}}}}{{\geq}}}{\rm
grank}((M\\!-\\!\lambda E)[{\cal J}_{n}\backslash\\{l\\},{\cal
J}_{n}\backslash\\{j\\}])\\!-\\!(|R({\cal T}_{i})\cup\\{k_{0}\\}|\\!-1\\!)\\\
&\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny(b)}}}}{{=}}}n-|R({\cal
T}_{i})\cup\\{k_{0}\\}|=|\Theta|,\end{aligned}\end{array}$

where (a) is due to that $P_{\lambda}[\Theta,{\cal J}_{n}\backslash\\{i,j\\}]$
is obtained by deleting $|R({\cal T}_{i})\cup\\{k_{0}\\}|\\!-1\\!$ rows from
$P_{\lambda}[{\cal J}_{n}\backslash\\{l\\},{\cal J}_{n}\backslash\\{j\\}]$,
and (b) comes from ${\rm grank}(P_{\lambda}[{\cal
J}_{n}\backslash\\{l\\},{\cal J}_{n}\backslash\\{j\\}])=n-1$ by 2) of Lemma 1.
That is, after deleting any column from $P_{\lambda}[\Theta,{\cal
J}_{n}\backslash\\{i\\}]$, the resulting matrix remains of full row generic
rank, which induces at least one nonzero polynomial equation constraint on $z$
and ${\cal T}[\Theta,{\cal J}_{n}\backslash\\{i,j\\}]$. This indicates $z$
depends on ${\cal T}[\Theta,{\cal J}_{n}\backslash\\{i,j\\}]$, or
equivalently, being independent of ${\cal T}[\Theta,\\{j\\}]$, for each
$j\in{\cal J}_{n}\backslash\\{i\\}$. It finally concludes that $z$ is
independent of the variables ${\cal T}[\Theta,{\cal J}_{n}\backslash\\{i\\}]$,
causing a contraction. Therefore, the assumed $z$ cannot exist. ∎

###### Lemma 8

Let $M^{j_{\rm c}}_{\lambda}$ and ${\Omega_{j}}$ be defined in (4) and (6).
For each $k\in{\Omega_{j}}$, let $\tilde{M}^{j_{\rm
c}}_{ki^{*}}(\lambda)\doteq M_{\lambda}^{j_{\rm c}}[\bar{\cal
V}^{+}_{ki^{*}},\bar{\cal V}^{-}_{ki^{*}}]$, i.e.,

$\tilde{M}^{j_{\rm
c}}_{ki^{*}}(\lambda)\\!=\\!\left[\\!\begin{array}[]{ccc}M_{k}^{j_{\rm
c}}(\lambda)&\cdots&M_{ki^{*}}^{j_{\rm c}}(\lambda)\\\ 0&\ddots&\vdots\\\
0&0&M^{j_{\rm c}}_{i^{*}}(\lambda)[{\cal J}_{|{\cal
V}^{+}_{i^{*}}|}\backslash\\{\bar{i}\\},{\cal J}_{|{\cal
V}^{+}_{i^{*}}|}]\end{array}\\!\right].$

Then, $\tilde{M}^{j_{\rm c}}_{ki^{*}}(\lambda)$ generically has full row rank
when $\lambda\in\\{z\in{\mathbb{C}}\backslash\\{0\\}:\det M_{k}^{j_{\rm
c}}(z)=0\\}$, if and only if the minimum weight maximum matching of the
bipartite ${\cal G}^{j_{\rm c}}_{ki^{*}}$ is less than $|{\cal V}^{+}_{k}|$.

###### Proof:

Sufficiency: Let $n_{1}=|{\cal V}^{+}_{k}\cup{\cal V}^{+}_{k+1}\cdots\cup{\cal
V}^{+}_{i^{*}}|$. By Lemma 1, ${\rm mt}({\cal
G}^{j_{c}}_{i^{*}}-\\{x_{i}\\})=|{\cal V}^{+}_{i^{*}}|-1$. Consequently,
${\cal G}^{j_{\rm c}}_{ki^{*}}$ has a maximum matching with size $n_{1}-1$
from its structure. Suppose that ${\cal G}^{j_{\rm c}}_{ki^{*}}$ has a maximum
matching with weight less than $|{\cal V}^{+}_{k}|$. Then, ${\cal
B}(\tilde{M}^{j_{\rm c}}_{ki^{*}}(\lambda)[{\cal J}_{n_{1}-1},{\cal
J}_{n_{1}}\backslash\\{\bar{k}\\}])$ for some $\bar{k}\in\\{1,...,|{\cal
V}^{-}_{k}|\\}$ must have a matching with size $n_{1}-1$. Indeed, if this is
not true, then any maximum matching of ${\cal G}^{j_{\rm c}}_{ki^{*}}$ must
matches ${\cal V}^{-}_{k}$, which certainly leads to a weight equaling $|{\cal
V}^{+}_{k}|$, noting that each edge not incident to ${\cal V}^{-}_{k}$ has a
zero weight. Furthermore, due to the DM-irreducibility of ${\cal G}^{j_{\rm
c}}_{k}$, from Lemma 7, any nonzero root of $\det M_{k}^{j_{\rm c}}(\lambda)$
cannot be independent of the variables in the $\bar{k}$th column of
$M_{k}^{j_{\rm c}}(\lambda)$.111Note the case where $|{\cal V}^{+}_{k}|=1$ and
$M_{k}^{j_{\rm c}}(\lambda)=\lambda$ has been excluded by the nonzero root
assumption. Therefore, $\det M_{k}^{j_{\rm c}}(\lambda)$ and
$\det\tilde{M}^{j_{\rm c}}_{ki^{*}}(\lambda)[{\cal J}_{n_{1}-1},{\cal
J}_{n_{1}}\backslash\\{\bar{k}\\}]$ generically do not share a common nonzero
root, since the latter determinant cannot contain the variables in the
$\bar{k}$th column of $M_{k}^{j_{\rm c}}(\lambda)$ (except for $\lambda$).
That is, $\det\tilde{M}^{j_{\rm c}}_{ki^{*}}(\lambda)[{\cal J}_{n_{1}-1},{\cal
J}_{n_{1}}\backslash\\{\bar{k}\\}]$ is generically nonzero for
$\lambda\in\\{z\in{\mathbb{C}}\backslash\\{0\\}:\det M_{k}^{j_{\rm
c}}(z)=0\\}$, leading to the full row rank of $\tilde{M}^{j_{\rm
c}}_{ki^{*}}(\lambda)$.

Necessity: If $k=i^{*}$, the necessity is obvious. Consider $k<i^{*}$. Suppose
the minimum weight maximum matching of ${\cal G}^{j_{\rm c}}_{ki^{*}}$ equals
$|{\cal V}^{+}_{k}|$. Then, based on the above analysis, any maximum matching
of ${\cal G}^{j_{\rm c}}_{ki^{*}}$ must match ${\cal V}^{-}_{k}$, which leads
to a zero determinant of ${\tilde{M}}^{j_{\rm c}}_{ki^{*}}(\lambda)$, due to
the block-triangular structure of ${\tilde{M}}^{j_{\rm c}}_{ki^{*}}(\lambda)$
and the fact that $\det M_{k}^{j_{\rm c}}(\lambda)=0$, contradicting the full
row rank of ${\tilde{M}}^{j_{\rm c}}_{ki^{*}}(\lambda)$. ∎

Proof of Proposition 4: In the following, suppose vertex $x_{i}$ corresponds
to the $\hat{i}$th row of $M^{j_{\rm c}}_{\lambda}$ after the permutation by
$P$, i.e.
$[M_{\lambda}^{j}]_{\hat{i}}=[PH_{\lambda}^{j}]_{\hat{i}}=[H_{\lambda}^{j}]_{i}$.
Recall the involved $H_{\lambda},M^{j_{c}}_{\lambda}$ and their submatrices
are treated as generic matrix pencils.

Sufficiency: From Lemma 7, we know that for each $k\in\Omega_{j}$, there
exists a nonzero $\lambda$ making $\det M_{k}^{j_{\rm c}}(\lambda)=0$. To
distinguish such value from the variable $\lambda$, we denote it by $z$ (i.e.,
$z\neq 0$ and $\det M_{k}^{j_{\rm c}}(z)=0$). From Lemma 6, it generically
holds that $\det M_{l}^{j}(z)\neq 0$ for all
$l\in\\{1,...,b\\}\backslash\\{k\\}$, as $\det M_{k}^{j_{\rm c}}(\lambda)$ and
$\det M_{l}^{j}(\lambda)$ do not share any common factor except the factor
$\lambda$. Due to the block-triangular structure of $M^{j_{\rm c}}_{z}$
(obtained by replacing $\lambda$ with $z$ in $M^{j_{\rm c}}_{\lambda}$), it
can be seen readily that if $\tilde{M}^{j_{\rm c}}_{ki^{*}}(z)$ defined in
Lemma 8 generically has full row rank, then $M^{j_{\rm c}}_{z}[{\cal
J}_{n}\backslash\\{\hat{i}\\},{\cal J}_{n}]$ will do. The former condition has
been proven in Lemma 8.

Note also that $M^{j_{\rm c}}_{z}$ generically has rank $n-1$ as otherwise
$[\bar{A}-zI,\bar{b}]$ generically has rank less than $n$, contradicting the
structural controllability of $(\bar{A},\bar{b})$. Therefore, from Lemma 3,
letting ${\hat{q}}$ be a nonzero vector in the left null space of $M^{j_{\rm
c}}_{z}$, we have ${\hat{q}}_{\hat{i}}\neq 0$. For almost all $(A,b)\in{\bf
CS}(\bar{A},\bar{b})$, by letting $[\Delta A,\Delta
b]_{ij}=-1/{\hat{q}}_{\hat{i}}\sum\nolimits_{l=1}^{n}{\hat{q}}_{l}(P[A-zI,b])_{lj},$
we get

$\begin{array}[]{c}\begin{aligned} &{\hat{q}}^{\intercal}P([A-zI,b]+[\Delta
A,\Delta b])[{\cal J}_{n},\\{j\\}]\\\ &={\hat{q}}_{\hat{i}}(P[\Delta A,\Delta
b])_{\hat{i},j}+\sum\nolimits_{l=1}^{n}{\hat{q}}_{l}(P[A-zI,b])_{lj}\\\
&=0,\end{aligned}\end{array}$

where the second equality is due to $(P[\Delta A,\Delta
b])_{\hat{i},j}=[\Delta A,\Delta b]_{ij}$. Upon defining
$q^{\intercal}\doteq{\hat{q}}^{\intercal}P$, we have

$q^{\intercal}([A-zI,b]+[\Delta A,\Delta b])=0,$

which comes from the fact $q^{\intercal}H_{z}^{j_{\rm c}}Q=0$ and $Q$ is
invertible.

Necessity: For the existence of $q$ making the condition in Proposition 4
satisfied, it is necessary $H_{\lambda}^{j_{\rm c}}$ should be of rank
deficient at some nonzero value for $\lambda$ (generically). Denote such a
value by $z$ for the sake of distinguishing it from the variable $\lambda$.
Since DM-decomposition does not alter the rank, $M_{z}^{j_{\rm c}}$ should be
of row rank deficient too. From the block-triangular structure of
$M_{z}^{j_{\rm c}}$ (see (4)), there must exist some $k\in\\{1,...,b\\}$, such
that $M^{j_{\rm c}}_{k}(z)$ is singular generically. From Lemma 7, such an
integer $k$ must correspond to a ${\cal G}_{k}^{j_{\rm c}}$ satisfying
${\gamma}_{\rm nz}({\cal G}_{k}^{j_{\rm c}})=1$. We consider two cases: i)
$k>i^{*}$, and ii) $k\leq i^{*}$.

In case i), since $k>i^{*}$, from the upper block-triangular structure of
$M_{z}^{j_{\rm c}}$, it is clear that $M_{z}^{j_{\rm c}}[{\cal
J}_{n}\backslash\\{\hat{i}\\},{\cal J}_{n}]$ is of row rank deficient when
$\det M^{j_{\rm c}}_{k}(z)=0$. Note that ${\rm grank}(M_{z}^{j_{\rm c}})\geq
n-1$ as otherwise ${\rm grank}(H_{z})<n$, which is contradictory to the
structural controllability of $(\bar{A},\bar{b})$. Consequently,
$M_{z}^{j_{\rm c}}$ has a left null space with dimension one. Denote by
$\hat{q}$ the vector spanning that space. From Lemma 3,
${\hat{q}}_{\hat{i}}=0$. As a result, for any $[\Delta A,\Delta b]\in{\bf
S}_{[{\Delta\bar{A}},{\Delta\bar{b}}]}$,

$\hat{q}^{\intercal}\big{\\{}M^{j}_{z}+(P[\Delta A,\Delta b])[{\cal
J}_{n},\\{j\\}]\big{\\}}\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny(a)}}}}{{=}}}\hat{q}^{\intercal}M^{j}_{z}\neq
0,$

where (a) results from $(P[\Delta A,\Delta b])_{\hat{i}j}=[\Delta A,\Delta
b]_{ij}$, and the inequality from $\hat{q}^{\intercal}[M^{j_{\rm
c}}_{z},M^{j}_{z}]\neq 0$, as otherwise $\hat{q}^{\intercal}PH_{z}=0$ meaning
that $z$ will be an uncontrollable mode (noting that
$\hat{q}^{\intercal}[M^{j_{\rm
c}}_{z},M^{j}_{z}]=\hat{q}^{\intercal}PH_{z}Q=0$, and $Q$ is invertible).
Consequently, case i) cannot lead to the required results.

Therefore, $k$ must fall into case ii). Now suppose that the minimum weight
maximum matching of ${\cal G}_{ki^{*}}^{j_{\rm c}}$ is equal to $|{\cal
V}_{k}^{+}|$. Then, from Lemma 8 and by the block-triangular structure of
$M_{z}^{j_{\rm c}}$, we obtain that $M_{z}^{j_{\rm c}}[{\cal
J}_{n}\backslash\\{\hat{i}\\},{\cal J}_{n}]$ is generically of row rank
deficient. Following the similar reasoning to case i), it turns out that the
requirement in Proposition 4 cannot be satisfied. This proves the necessity.
$\hfill\square$

## References

  * [1] Anthony D Wood and John A Stankovic.  Denial of service in sensor networks.  Computer, 35(10):54–62, 2002.
  * [2] Sergey V Buldyrev, Parshani Roni, Paul Gerald, Stanley H Eugene, and Havlin Shlomo.  Catastrophic cascade of failures in interdependent networks.  Nature, 464(7291):1025–8, 2009.
  * [3] Hamza Fawzi, Paulo Tabuada, and Suhas Diggavi.  Secure estimation and control for cyber-physical systems under adversarial attacks.  IEEE Transactions on Automatic Control, 59(6):1454–1467, 2014.
  * [4] Aritra Mitra and Shreyas Sundaram.  Byzantine-resilient distributed observers for lti systems.  Automatica, 108:108487, 2019.
  * [5] Yuan Zhang, Yuanqing Xia, Jinhui Zhang, and Jun Shang.  Generic detectability and isolability of topology failures in networked linear systems.  IEEE Transactions on Control of Network Systems, 2020.
  * [6] Pasqualetti Fabio, Chiara Favaretto, Shiyu Zhao, and Sandro Zampieri.  Fragility and controllability tradeoff in complex networks.  In American Control Conference, pages 216–227. IEEE, 2018.
  * [7] Claudio De Persis and Pietro Tesi.  Input-to-state stabilizing control under denial-of-service.  IEEE Transactions on Automatic Control, 60(11):2930–2944, 2015\.
  * [8] Christian Commault, Jean-Michel Dion, and Do Hieu Trinh.  Observability preservation under sensor failure.  IEEE Transactions on Automatic Control, 53(6):1554–1559, 2008.
  * [9] Mohammad Amin Rahimian and Amir G. Aghdam.  Structural controllability of multi-agent networks: Robustness against simultaneous failures.  Automatica, 49(11):3149–3157, 2013.
  * [10] Yuan Zhang and Tong Zhou.  Minimal structural perturbations for controllability of a networked system: Complexities and approximations.  International Journal of Robust and Nonlinear Control, 29(12):4191–4208, 2019.
  * [11] Yuan Zhang and Tong Zhou.  On the edge insertion/deletion and controllability distance of linear structural systems.  In 56th Annual Conference on Decision and Control, pages 2300–2305. IEEE, 2017.
  * [12] Yuan Zhang, Yuanqing Xia, and Kun Liu.  Observability robustness under sensor failures: A computational perspective.  arXiv preprint arXiv:1812.07745, 2018.
  * [13] J M Dion, C Commault, and J Van DerWoude.  Generic properties and control of linear structured systems: a survey.  Automatica, 39:1125–1144, 2003.
  * [14] R Eising.  Between controllable and uncontrollable.  Systems & Control Letters, 48(5):263–264, 1984.
  * [15] Mark Wicks and Raymond DeCarlo.  Computing the distance to an uncontrollable system.  IEEE Transactions on Automatic Control, 36(1):39–49, 1991.
  * [16] Guangdi Hu and E. J Davison.  Real controllability/stabilizability radius of lti systems.  IEEE Transactions on Automatic Control, 49(2):254–257, 2004.
  * [17] M. Gu, E. Mengi, Overton, Xia M. L., and J. J. Zhu.  Computing the distance to an uncontrollable system.  SIAM Journal on Matrix Analysis and Applications, 28(2):477–502, 2006.
  * [18] Michael Karow and Daniel Kressner.  On the structured distance to uncontrollability.  Systems & Control Letters, 58(2):128–132, 2009.
  * [19] Swanand R Khare, Harish K Pillai, and Madhu N Belur.  Computing the radius of controllability for state space systems.  Systems & control letters, 61(2):327–333, 2012.
  * [20] Scott C Johnson, Mark Wicks, Miloš Žefran, and Raymond A DeCarlo.  The structured distance to the nearest system without property P.  IEEE Transactions on Automatic Control, 63(9):2960–2975, 2018.
  * [21] Gianluca Bianchin, Paolo Frasca, Andrea Gasparri, and Fabio Pasqualetti.  The observability radius of networks.  IEEE transactions on Automatic Control, 62(6):3006–3013, 2016.
  * [22] Hirokazu Mayeda and Takashi Yamada.  Strong structural controllability.  SIAM Journal on Control and Optimization, 17(1):123–138, 1979.
  * [23] Christopher Bowden, William Holderbaum, and Victor M Becerra.  Strong structural controllability and the multilink inverted pendulum.  IEEE transactions on automatic control, 57(11):2891–2896, 2012\.
  * [24] Nima Monshizadeh, Shuo Zhang, and M Kanat Camlibel.  Zero forcing sets and controllability of dynamical systems defined on graphs.  IEEE Transactions on Automatic Control, 59(9):2562–2567, 2014.
  * [25] Jiajia Jia, Henk J van Waarde, Harry L Trentelman, and M Kanat Camlibel.  A unifying framework for strong structural controllability.  IEEE Transactions on Automatic Control, 66(1):391–398, 2020.
  * [26] K Murota.  Matrices and Matroids for Systems Analysis.  Springer Science Business Media, 2009.
  * [27] David Steven Dummit and Richard M Foote.  Abstract algebra, volume 3.  Wiley Hoboken, 2004.
  * [28] Yuan Zhang, Yuanqing Xia, Gang Wang, and Jinhui Zhang.  Perturbation-tolerant structural controllability for linear systems.  arXiv preprint arXiv:2105.00968, 2021.
  * [29] D. B. West.  Introduction to Graph Theory.  Prentice hall, 2001.
  * [30] K S Lu and J N Wei.  Rational function matrices and structural controllability and observability.  IET Control Theory and Applications, 138(4):388–394, 1991.