The Observability Radius of Networks

arXiv:1612.06120v1 [] 19 Dec 2016

Gianluca Bianchin, Paolo Frasca, Andrea Gasparri, and Fabio Pasqualetti

Abstract—This paper studies the observability radius of network
systems, which measures the robustness of a network to perturbations
of the edges. We consider linear networks, where the dynamics are
described by a weighted adjacency matrix, and dedicated sensors are
positioned at a subset of nodes. We allow for perturbations of certain
edge weights, with the objective of preventing observability of some
modes of the network dynamics. To comply with the network setting,
our work considers perturbations with a desired sparsity structure, thus
extending the classic literature on the observability radius of linear
systems. The paper proposes two sets of results. First, we propose
an optimization framework to determine a perturbation with smallest
Frobenius norm that renders a desired mode unobservable from the
existing sensor nodes. Second, we study the expected observability radius
of networks with given structure and random edge weights. We provide
fundamental robustness bounds dependent on the connectivity properties
of the network and we analytically characterize optimal perturbations of
line and star networks, showing that line networks are inherently more
robust than star networks.

I. I NTRODUCTION
Networks are broadly used to model engineering, social, and natural systems. An important property of such systems is their robustness
to contingencies, including failure of components affecting the flow of
information, external disturbances altering individual node dynamics,
and variations in the network topology and weights. It remains an
outstanding problem to quantify how different topological features
enable robustness, and to engineer complex networks that remain
operable in the face of arbitrary, and perhaps malicious perturbations.
Observability of a network guarantees the ability to reconstruct the
state of each node from sparse measurements. While observability is
a binary notion [2], the degree of observability, akin to the degree
of controllability, can be quantified in different ways, including the
energy associated with the measurements [3], [4], the novelty of the
output signal [5], the number of necessary sensor nodes [6], [7], and
the robustness to removal of interconnection edges [8]. A quantitative
notion of observability is preferable over a binary one, as it allows to
compare different observable networks, select optimal sensor nodes,
and identify topological features favoring observability.
In this work we measure robustness of a network based on the
size of the smallest perturbation needed to prevent observability. Our
notion of robustness is motivated by the fact that observability is a
generic property [9] and network weights are rarely known without
uncertainty. For these reasons numerical tests to assess observability
may be unreliable and in fact fail to recognize unobservable systems:
instead, our measure of observability robustness can be more reliably
evaluated [10]. Among our contributions, we highlight connections
between the robustness of a network and its structure, and we
propose an algorithmic procedure to construct optimal perturbations.
Our work finds applicability in network control problems where the
network weights can be changed, in security applications where an
This material is based upon work supported in part by NSF awards
#BCS-1430279 and #ECCS-1405330. A preliminary and abbreviated version
of this work will appear in the Proceedings of the 2016 American Control Conference [1]. Gianluca Bianchin and Fabio Pasqualetti are with the
Mechanical Engineering Department, University of California at Riverside,
gianluca@engr.ucr.edu, fabiopas@engr.ucr.edu. Paolo Frasca
is with the Department of Applied Mathematics, University of Twente,
p.frasca@utwente.nl. Andrea Gasparri is with the Department of
Engineering, Roma Tre University, gasparri@dia.uniroma3.it.

attacker gains control of some network edges, and in network science
for the classification of edges and the design of robust topologies.
Related work Our study is inspired by classic works on the observability radius of dynamical systems [11], [12], [13], defined as
the norm of the smallest perturbation yielding unobservability or,
equivalently, the distance to the nearest unobservable realization.
For a linear system described by the pair (A, C), the radius of
observability has been classically defined as


∆A
,
µ(A, C) = min
∆C 2
∆A ,∆C
s.t. (A + ∆A , C + ∆C ) is unobservable.
As a known result [12], the observability radius satisfies


sI − A
µ(A, C) = min σn
,
C
s
where σn denotes the smallest singular value, and s ∈ R (s ∈ C
if complex perturbations are allowed). The optimal perturbations
∆A and ∆C are typically full matrices and, to the best of our
knowledge, all existing results and procedures are not applicable
to the case where the perturbations must satisfy a desired sparsity
constraint (e.g., see [14]). This scenario is in fact the relevant one for
network systems, where the nonzero entries of the network matrices
A and C correspond to existing network edges, and it would be
undesirable or unrealistic for a perturbation to modify the interaction
of disconnected nodes. An exception is the recent paper [8], where
structured perturbations are considered in a controllability problem,
yet the discussion is limited to the removal of edges.
We depart from the literature by requiring the perturbation to be
real, with a desired sparsity pattern, and confined to the network
matrix (∆C = 0). Our approach builds on the theory of total least
squares [15]. With respect to existing results on this topic, our work
proposes procedures tailored to networks, fundamental bounds, and
insights into the robustness of different network topologies.
Contribution The contribution of this paper is threefold. First, we
define a metric of network robustness that captures the resilience
of a network system to structural, possibly malicious, perturbations.
Our metric evaluates the distance of a network from the set of
unobservable networks with the same interconnection structure, and it
extends existing works on the observability radius of linear systems.
Second, we formulate a problem to determine optimal perturbations
(with smallest Frobenius norm) preventing observability. We show
that the problem is not convex, derive optimality conditions, and
prove that any optimal solution solves a nonlinear generalized eigenvalue problem. Additionally, we propose a numerical procedure based
on the power iteration method to determine (sub)optimal solutions.
Third, we derive a fundamental bound on the expected observability radius for networks with random weights. In particular, we present
a class of networks for which the expected observability radius
decays to zero as the network cardinality increases. Furthermore, we
characterize the robustness of line and star networks. In accordance
with recent findings on the role of symmetries for the observability
and controllability of networks [16], [17], we demonstrate that line
networks are inherently more robust than star networks to perturbations of the edge weights. This analysis shows that our measure

of robustness can in fact be used to compare different network
topologies and guide the design of robust complex systems.
Because the networks we consider are in fact systems with linear
dynamics, our results are generally applicable to linear dynamical
systems. Yet, our setup allows for perturbations with a fixed sparsity
pattern, which may arise from the organization of a network system.
Paper organization The rest of the paper is organized as follows.
Section II contains our network model, the definition of the network
observability radius, and some preliminary considerations. Section III
describes our method to compute network perturbations with smallest
Frobenius norm, our optimization algorithm, and an illustrative
example. Our bounds on the observability radius of random networks
are in Section IV. Finally, Section V concludes the paper.
II. T HE N ETWORK O BSERVABILITY R ADIUS
Consider a directed graph G := (V, E), where V := {1, . . . , n}
and E ⊆ V × V are the vertex and edge sets, respectively. Let
A = [aij ] be the weighted adjacency matrix of G, where aij ∈ R
denotes the weight associated with the edge (i, j) ∈ E (representing
flow of information from node j to node i), and aij = 0 whenever
(i, j) 6∈ E. Let ei denote the i-th canonical vector of dimension n.
Let O = {o1 , . . . , op } ⊆ V be theset of sensor nodes,
T and define the
network output matrix as CO = eo1 · · · eop . Let xi (t) ∈ R
denote the state of node i at time t, and let x : N≥0 → Rn be the
map describing the evolution over time of the network state. The
network dynamics are described by the linear discrete-time system
x(t + 1) = A x(t), and y(t) = CO x(t),

AH = {M : M ∈ R|V|×|V| , Mij = 0 if (i, j) 6∈ EH }.
Recall from the eigenvector observability test that the network (1) is
observable if and only if there is no right eigenvector of A that lies
in the kernel of CO , that is, CO x 6= 0 whenever x 6= 0, Ax = λx,
and λ ∈ C [18]. In this work we consider and study the following
optimization problem:
k∆k2F ,

s.t.

(A + ∆)x = λx,

(eigenvalue constraint),

kxk2 = 1,

(eigenvector constraint),

CO x = 0,

(unobservability),

∆ ∈ AH ,

(structural constraint),

III. O PTIMALITY C ONDITIONS AND A LGORITHMS FOR THE
N ETWORK O BSERVABILITY R ADIUS
In this section we consider problem (2) with fixed λ. Specifically,
we address the following minimization problem: given a constraint
graph H, the network matrix A ∈ AG , an output matrix CO , and
a desired unobservable eigenvalue λ ∈ C, determine a perturbation
∆∗ ∈ Rn×n satisfying
k∆∗ k2F =

min

x∈Cn ,∆∈Rn×n

k∆k2F ,
(A + ∆)x = λx,

s.t.

(1)

where y : N≥0 → Rp is the output of the sensor nodes O.
In this work we characterize structured network perturbations
that prevent observability from the sensor nodes. To this aim, let
H = (VH , EH ) be the constraint graph, and define the set of matrices
compatible with H as

min

For the pair (A, CO ), the network observability radius is the
solution to the optimization problem (2), which quantifies the total
edge perturbation to achieve unobservability. Different cost functions
may be of interest and are left as the subject of future research.
The minimization problem (2) can be solved by two subsequent
steps. First, we fix the eigenvalue λ, and compute an optimal
perturbation that solves the minimization problem for that λ. This
computation is the topic of the next section. Second, we search
the complex plane for the optimal λ yielding the perturbation with
minimum cost. We observe that (i) the exhaustive search of the
optimal λ is an inherent feature of this class of problems, as also
highlighted in prior work [13]; (ii) in some cases and for certain
network topologies the optimal λ can be found analytically, as we
do in Section IV for line and star networks; and (iii) in certain
applications the choice of λ is guided by the objective of the network
perturbation, such as inducing unobservability of unstable modes.

(3)

kxk2 = 1,
CO x = 0,
∆ ∈ AH .

From (3), the value k∆∗ k2F equals the observability radius of the
network A with sensor nodes O, constraint graph H, and fixed
unobservable eigenvalue λ.
A. Optimal network perturbation
We now shape minimization problem (3) to facilitate its solution.
Without affecting generality, relabel the network nodes such that the
sensor nodes set satisfy


O = {1, . . . , p}, so that CO = Ip 0 .
(4)
Accordingly,

(2)

where the minimization is carried out over the eigenvector x ∈ Cn ,
the unobservable eigenvalue λ ∈ C, and the network perturbation
∆ ∈ Rn×n . The function k · kF : Rn×n → R≥0 is the
Frobenius norm, and AH expresses the desired sparsity pattern of
the perturbation. It should be observed that (i) the minimization
problem (2) is not convex because the variables ∆ and x are
multiplied each other in the eigenvector constraint (A + ∆)x = λx,
(ii) if A ∈ AH , then the minimization problem is feasible if and
only if there exists a network matrix A + ∆ = Ã ∈ AH satisfying
the eigenvalue and eigenvector constraint, and (iii) if H = G, then
the perturbation modifies the weights of the existing edges only. We
make the following assumption:
(A1) The pair (A, CO ) is observable.
Assumption (A1) implies that the perturbation ∆ must be nonzero to
satisfy the constraints in (2).


A=

A11
A21



A12
∆11
, and ∆ =
A22
∆21


∆12
,
∆22

(5)

where A11 ∈ Rp×p , A12 ∈ Rp×n−p , A21 ∈ Rn−p×p , and
A22 ∈ Rn−p×n−p . Let V = [vij ] be the unweighted adjacency
matrix of H, where vij = 1 if (i, j) ∈ EH , and vij = 0 otherwise.
Following the partitioning of A in (5), let


V11 V12
V =
.
V21 V22
We perform the following three simplifying steps.
(1–Rewriting thePstructural
B = A + ∆, and notice
Pn constraints) Let
n
2
that k∆k2F =
(b
−
a
)
.
Then,
the minimization
ij
ij
i=1
j=1
problem (3) can equivalently be rewritten restating the constraint
∆ ∈ AH , as in the following:
k∆k2F = kB − Ak2F =

n X
n
X

−1
(bij − aij )2 vij
.

i=1 j=1

Notice that k∆k2F = ∞ whenever ∆ does not satisfy the structural
constraint, that is, when vij = 0 and bij 6= aij .

(2–Minimization with real variables) Let λ = λ< + iλ= , where i
denotes the imaginary unit. Let
 1
 1
x=
x
,
,
and
x
=
x< = <
=
x2=
x2<
denote the real and imaginary parts of the eigenvector x, with
x1< ∈ Rp , x1= ∈ Rp , x2< ∈ Rn−p , and x2= ∈ Rn−p .
Lemma 3.1: (Minimization with real eigenvector constraint) The
constraint (A + ∆)x = λx can equivalently be written as
(A + ∆ − λ< I)x< = −λ= x= ,

(6)

(A + ∆ − λ< I)x= = λ= x< .

Proof: By considering separately the real and imaginary part of
the eigenvalue constraint, we have (A + ∆)x = λ< x + iλ= x and
(A + ∆)x̄ = λ< x̄ − iλ= x̄, where x̄ denotes the complex conjugate
of x. Notice that
(A + ∆)(x + x̄) = (λ< + iλ= )x + (λ< − iλ= )x̄,
|
{z
} |
{z
}

(A + ∆)(x − x̄) = (λ< + iλ= )x − (λ< − iλ= )x̄,
|
{z
} |
{z
}
2iλ< x= +2iλ= x<

which concludes the proof.
Thus, the problem (3) can be solved over real variables only.
(3–Reduction of dimensionality) The constraint CO x = 0 and
equation (4) imply that x1< = x1= = 0. Thus, in the minimization
problem (5) we set ∆11 = 0, ∆21 = 0, and consider the minimization
variables x2< , x2= , ∆12 , and ∆22 .
These simplifications lead to the following result.
Lemma 3.2: (Equivalent minimization problem) Let






A12 ¯
∆12
0p×n−p
Ā =
,∆ =
, M̄ =
,
A22
∆22
λ= In−p


 
(7)
0p×n−p
V12
¯
N̄ =
, V̄ =
, and B̄ = Ā + ∆.
λ< In−p
V22
The following minimization problem is equivalent to (3):
n n−p
X
X
−1
¯ ∗ k2F = min
k∆
(b̄ij − āij )2 vij
,
B̄,x2
,x2
< =

s.t.

i=1 j=1
 2 
B̄ − N̄
M̄
x<
= 0,
−M̄
B̄ − N̄ x2=
 2
x<
= 1.
x2= 2

Ã

x∗

Dx

y∗

T  

 
Ā − N̄
M̄
Sy Ty x∗<
y1
=σ
,
−M̄
Ā − N̄
y2
Ty Qy x∗=
|
{z
} | {z }
| {z } | {z }
ÃT

y∗

Dy

x∗

Sx = (I ⊗ x∗< )T D1 (I ⊗ x∗< ), Tx = (I ⊗ x∗< )T D1 (I ⊗ x∗= ), (10)
Qx = (I ⊗ x∗= )T D1 (I ⊗ x∗= ), Sy = (I ⊗ y1 )T D2 (I ⊗ y1 ),
Ty = (I ⊗ y1 )T D2 (I ⊗ y2 ), Qy = (I ⊗ y2 )T D2 (I ⊗ y2 ).
Proof: We adopt the method of Lagrange multipliers to derive
optimality conditions for the problem (8). The Lagrangian is
XX
−1
L(B̄, x2< , x2= , `1 , `2 , ρ) =
(b̄ij − āij )2 vij
i

+

`T1 ((B̄

+ ρ(1 −

− N̄ )x2< + M̄ x2= )
2
2T 2
x2T
< x< − x= x= ),

j

+ `T2 ((B̄ − N̄ )x2= − M̄ x2< )
(11)

∂L
∂bij
∂L
∂x2<
∂L
∂x2=
∂L
∂`1
∂L
∂`2
∂L
∂ρ

n

−1
+ `1i x2<j + `2i x2=j = 0,
= 0 ⇒ −2(āij − b̄ij )vij

(12)

= 0 ⇒ `T1 (B̄ − N̄ ) − `T2 M̄ − 2ρx2T
< = 0,

(13)

= 0 ⇒ `T1 M̄ + `T2 (B̄ − N̄ ) − 2ρx2T
= = 0,

(14)

= 0 ⇒ (B̄ − N̄ )x2< + M̄ x2= = 0,

(15)

= 0 ⇒ (B̄ − N̄ )x2= − M̄ x2< = 0,

(16)

2
2T 2
= 0 ⇒ x2T
< x< + x= x= = 1.

(17)

Let L1 = diag(`1 ), L2 = diag(`2 ), X< = diag(x2< ), X= =
diag(x2= ). After including the factor 2 into the multipliers, equation
(12) can be written in matrix form as
Ā − B̄ = L1 V̄ X< + L2 V̄ X= .
Analogously, equations (13) and (14) can be written as



 B̄ − N̄

 T
M̄
= 0,
− 2ρ x2T
x2T
`1 `T2
=
<
−M̄
B̄ − N̄

(8)

The minimization problem (8) belongs to the class of (structured)
total least squares problems, which arise in several estimation and
identification problems in control theory and signal processing. Our
approach is inspired by [15], with the difference that we focus
on real perturbations ∆ and complex eigenvalue λ: this constraint
leads to different optimality conditions and algorithms. Let A ⊗ B
denote the Kronecker product between the matrices A and B, and
diag(d1 , . . . , dn ) the diagonal matrix with scalar entries d1 , . . . , dn .
We now derive the optimality conditions for the problem (8).
Theorem 3.3: (Optimality conditions) Let x∗< , and x∗= be a solution to the minimization problem (8). Then,

 

 ∗ 
Ā − N̄
M̄
x<
Sx Tx y1
=σ
,
∗
−M̄
Ā − N̄ x=
Tx Qx y2
| {z } | {z }
|
{z
} | {z }


D2 = diag(v11 , . . . , vn1 , v12 , . . . , vn2 , . . . , v1n , . . . , vnn ),

where `1 ∈ R , `2 ∈ R , and ρ ∈ R are Lagrange multipliers. By
equating the partial derivatives of L to zero we obtain

and, analogously,

(A+∆)2ix=

D1 = diag(v11 , . . . , v1n , v21 , . . . , v2n , . . . , vn1 , . . . , vnn ),

n

2λ< x< −2λ= x=

(A+∆)2x<

for some σ > 0 and y ∗ ∈ R2n with ky ∗ k = 1, and where

(9)

From equation (19) we have

 T
 B̄ − N̄
`1 `T2
−M̄
|

M̄
B̄ − N̄
{z



=0 due to (15) and (16)

(18)

(19)


x2<
−2ρ = 0,
x2=
}

from which we conclude ρ = 0. By combining (15) and (18)
(respectively, (16) and (18)) we obtain

(Ā − N̄ )x2< + M̄ x2= = L1 V̄ X< + L2 V̄ X= x2< ,

(Ā − N̄ )x2= − M̄ x2< = L1 V̄ X< + L2 V̄ X= x2= .
Analogously, by combining (13) and (18), (14) and (18), we obtain

`T1 (Ā − N̄ ) − `T2 M̄ = `T1 L1 V̄ X< + L2 V̄ X= ,

`T2 (Ā − N̄ ) + `T1 M̄ = `T2 L1 V̄ X< + L2 V̄ X= .
p
Let σ = `T1 `1 + `T2 `2 and observe that σ cannot be zero. Indeed,
due to Assumption (A1), the optimal perturbation can not be zero;
thus, the first constraint in (8) must be active and the corresponding
multiplier must be nonzero. Then, we can define y1 = `1 /σ and
y2 = `2 /σ and we can verify that

L1 V̄ X< + L2 V̄ X= x2< = σ (Sx y1 + Tx y2 ) ,

L1 V̄ X< + L2 V̄ X= x2= = σ (Tx y1 + Qx y2 ) ,

and



σ y1T (Ā − N̄ ) − y2T M̄ = `T1 L1 V̄ X< + L2 V̄ X=
T
= σ 2 Sy x2< + Ty x2= ,



σ y2T (Ā − N̄ ) + y1T M̄ = `T2 L1 V̄ X< + L2 V̄ X=
T
= σ 2 Ty x2< + Qy x2= ,
which conclude the proof.
Note that equations (9) may admit multiple solutions, and that
every solution to (9) yields a network perturbation that satisfies the
constraints in the minimization problem (8). We now present the
following result to compute perturbations.
Corollary 3.4: (Minimum norm perturbation) Let ∆∗ be a solu¯ ∗ ], where
tion to (3). Then, ∆∗ = [0n×p ∆

¯ ∗ = −σ diag(y1 )V̄ diag(x∗< ) − diag(y2 )V̄ diag(x∗= ) ,
∆
and x∗< , x∗= , y1 , y2 , σ satisfy the equations (9). Moreover,
k∆k2F = σ 2 x∗T Dy x∗ = σx∗T ÃT y ∗ ≤ σkÃkF .
Proof: The expression for the perturbation ∆∗ comes from
Lemma 3.2 and (18), and the fact that L1 = σ diag(y1 ),
L2 = σ diag(y2 ). To show the second part notice that
k∆k2F = kA − Bk2F = kL1 V̄ X< + L2 V̄ X= k2F
XX 2 2
2 2 
y1i x<j + y2i
x=j vij
= σ2
i

j

= σ 2 x∗T Dy x∗ = σx∗T ÃT y ∗ ,
where the last equalities follow from (9). Finally, the inequality
follows from kx∗ k2 = kx∗ kF = ky ∗ k2 = ky ∗ kF = 1.
To compute a triple (σ, x∗ , y ∗ ) satisfying the condition in Theorem 3.3, observe that (9) can be written in matrix form as

 

 
0 ÃT x
Dy
0
x
= σ̄
.
(20)
y
0
Dx y
Ã
0
|
{z
} |{z}
| {z } |{z}
H

z

D

z

Lemma 3.5: (Equivalence between Theorem 3.3 and (20)) Let
(σ, x, y), with x 6= 0, solve (20). Then, σ 6= 0 and y 6= 0, and the
triple ((αβ)−1 σ, αx, βy), with α = sgn(σ)kxk−1 and β = kyk−1 ,
satisfies the conditions in Theorem 3.3.
Proof: Because x 6= 0 and Ã has full column rank due to
Assumption (A1), it follows σ 6= 0 and y 6= 0. Let Dx and Dy
be as in (9). Notice that Dαx = α2 Dx and Dβy = β 2 Dy . Notice
that (αβ)−1 σ > 0. We have
σ 2
Ãαx =
α Dx βy = ασDx y,
αβ
σ
ÃT βy =
β 2 Dy αx = βσDy x,
αβ
which concludes the proof.
Lemma 3.5 shows that a (sub)optimal network perturbation can in fact
be constructed by solving equations (20). It should be observed that,
if the matrices Sx , Tx , Qx , Sy , Ty , and Qy were constant, then (20)
would describe a generalized eigenvalue problem, thus a solution
(σ̄, z) would be a pair of generalized eigenvalue and eigenvector.
These facts will be exploited in the next section to develop a heuristic
algorithm to compute a (sub)optimal network perturbation.
Remark 1: (Smallest network perturbation with respect to the
unobservable eigenvalue) In the minimization problem (3) the size
of the perturbation ∆∗ depends on the desired eigenvalue λ, and
it may be of interest to characterize the unobservable eigenvalue

λ∗ = λ∗< + iλ∗= yielding the smallest network perturbation that prevents observability. To this aim, we equate to zero the derivatives of
the Lagrangian (11) with respect to λ< and λ= to obtain
 
 
∂L
T 0p
T 0p
= 0 ⇒ `1 2 + `2 2 = 0,
x<
x=
∂λ<
 
 
∂L
0p
0p
= 0 ⇒ `T1 2 − `T2 2 = 0.
x=
x<
∂λ=
The above conditions clarify that, for the perturbation ∆ to be of the
smallest size with respect to λ, the Lagrange multipliers `1 and `2 ,
and the vectors x2< and x2= must verify an orthogonality condition.
Remark 2: (Real unobservable eigenvalue) When the unobservable eigenvalue λ in (3) is real, the optimality conditions in Theorem 3.3 can be simplified to
(Ā − N̄ )x< = σSx y1 , and (Ā − N̄ )y1 = σSy x< .
The generalized eigenvalue equation (20) becomes
 


 
y1
Sx 0
0
ĀT − N̄ T y1
,
=σ
0 Sy x<
x<
Ā − N̄
0
and the optimality conditions with respect
 tothe unobservable eigenT 0p
value λ (see Remark 1) simplify to `1 2 = 0.

x<
B. A heuristic procedure to compute structural perturbations
In this section we propose an algorithm to find a solution to the set
of nonlinear equations (20), and thus to find a (sub)optimal solution
to the minimization problem (3). Our procedure is motivated by (20)
and Corollary 3.4, and it consists of fixing a vector z, computing
the matrix D, and approximating an eigenvector associated with the
smallest generalized eigenvalue of the pair (H, D). Because the size
of the perturbation is bounded by the generalized eigenvalue σ as in
Corollary 3.4, we adopt an iterative procedure based on the inverse
iteration method for the computation of the smallest eigenvalue of
a matrix [19]. We remark that our procedure is heuristic, because
(20) is in fact a nonlinear generalized eigenvalue problem due to the
dependency of the matrix D on the eigenvector z. To the best of our
knowledge, no complete algorithm is known for the solution of (20).
We start by characterizing certain properties of the matrices H and
D, which will be used to derive our algorithm. Let
spec(H, D) = {λ ∈ C : det(H − λD) = 0},
and recall that the pencil (H, D) is regular if the determinant
det(H − λD) does not vanish for some value of λ, see [20]. Notice
that, if (H, D) is not regular, then spec(H, D) = C.
Lemma 3.6: (Generalized eigenvalues of (H, D)) Given a vector
z ∈ R4n−2p , define the matrices H and D as in (20). Then,
(i) 0 ∈ spec(H, D);
(ii) if λ ∈ spec(H, D), then −λ ∈ spec(H, D); and
(iii) if (H, D) is regular, then spec(H, D) ⊂ R.
Proof: Statement (i) is equivalent to Ãx = 0 and ÃT y = 0, for
some vectors x and y. Because ÃT ∈ R(2n−2p)×2n with p ≥ 1, the
matrix ÃT features a nontrivial null space. Thus, the two equations
are satisfied with x = 0 and y ∈ Ker(ÃT ), and the statement follows.
To prove statement (ii) notice that, due to the block structure of
H and D, if the triple (λ, x̄, ȳ) satisfies the generalized eigenvalue
equations ÃT ȳ = λDy x̄ and Ãx̄ = λDx ȳ, so does (−λ, x̄, −ȳ).
To show statement (iii), let Rank(D) = k ≤ n, and notice that the
regularity of the pencil (H, D) implies H z̄ 6= 0 whenever Dz̄ = 0
and z̄ 6= 0. Notice that (H, D) has n − k infinite eigenvalues [20]
because H z̄ = λDz̄ = λ · 0 for every nontrivial z̄ ∈ Ker(D).

Because D is symmetric, it admits an orthonormal basis of eigenvectors. Let V1 ∈ Rn×k contain the orthonormal eigenvectors of D
associated with its nonzero eigenvalues, let ΛD be the corresponding
−1/2
diagonal matrix of the eigenvalues, and let T1 = V1 ΛD . Then,
T1T DT1 = I. Let H̃ = T1T HT1 , and notice that H̃ is symmetric. Let
T2 ∈ Rk×k be an orthonormal matrix of the eigenvectors of H̃. Let
T = T1 T2 and note that T T HT = Λ and T T DT = I, where Λ is
a diagonal matrix. To conclude, consider the generalized eigenvalue
problem H z̄ = λDz̄. Let z̄ = T z̃. Because T has full column rank
k, we have T T HT z̃ = Λz̃ = λT T DT z̃ = λz̃, from which we
conclude that (H, D) has k real eigenvalues.
Lemma 3.6 implies that the inverse iteration method is not directly
applicable to (20). In fact, the zero eigenvalue of (H, D) leads the
inverse iteration to instability, while the presence of eigenvalues of
(H, D) with equal magnitude may induce non-decaying oscillations
in the solution vector. To overcome these issues, we employ a shifting
mechanism as detailed in Algorithm 1, where the eigenvector z is
iteratively updated by solving the equation (H − µD)zk+1 = Dzk
until a convergence criteria is met. Notice that (i) the eigenvalues of
(H − µD, D) are shifted with respect to the eigenvalues of (H, D),
that is, if σ ∈ spec(H, D), then σ − µ ∈ spec(H − µD, D),1 (ii) the
pairs (H − µD, D) and (H, D) share the same eigenvectors, and
(iii) by selecting µ = ψ · min{σ ∈ spec(H, D) : σ > 0}, the pair
(H −µD, D) has nonzero eigenvalues with distinct magnitude. Thus,
Algorithm 1 estimates the eigenvector z associated with the smallest
nonzero eigenvalue σ of (H, D), and converges when z and σ also
satisfy equations (20). The parameter ψ determines a compromise
between numerical stability and convergence speed; larger values of
ψ improve the convergence speed.2

where |V| = 3, weighted adjacency matrix


a11 a12
0
A = a21 a22 a23  ,
0
a32 a33
and sensor node O = {1}. Let B = [bij ] = A + ∆∗ , where ∆∗
solves the minimization problem (3) with constraint graph H = G
and unobservable eigenvalue λ = λ< + iλ= ∈ C, λ= 6= 0. Then:
b11 = a11 ,

b21 = a21 ,

b12 = 0,

and b22 , b23 , b32 , and b33 satisfy:
b33 − b22
(b23 − a23 ) = 0,
b32
b23
(b32 − a32 ) −
(b23 − a23 ) = 0,
b32
b22 + b33 − 2λ< = 0,

(b22 − a22 ) − (b33 − a33 ) +

(21)

b22 b33 − b23 b32 − λ2< − λ2= = 0.
Proof: Let Bx = λx and notice that, because λ is unobservable,
CO x = [1 0 0]x = 0. Then, x = [x1 x2 x3 ]T , x1 = 0, b11 = a11 ,
and b21 = a21 . By contradiction, let x2 = 0. Notice that Bx = λx
implies b33 = λ, which contradicts the assumption that λ= 6= 0 and
b33 ∈ R. Thus, x2 6= 0. Because x2 6= 0, the relation Bx = λx and
x1 = 0 imply b12 = 0. Additionally, λ is an eigenvalue of


b22 b23
B2 =
.
b32 b33
The characteristic polynomial of B2 is

Algorithm 1: Heuristic solution to (20)
Input: Matrix H; max iterations maxiter ; ψ ∈ (0.5, 1).
Output: (σ, z) satisfying (20), or fail.
repeat
z ← (H − µD)−1 Dz;
φ ← kzk;
z ← z/φ;
µ = ψ · min{φ ∈ spec(H, D) : φ > 0};
update D according to (10);
i←i+1
until convergence or i > maxiter ;
return (φ + µ, z) or fail if i = maxiter ;
When convergent, Algorithm 1 finds a solution to (20) and,
consequently, the algorithm could stop at a local minimum and return
a (sub)optimal network perturbation preventing observability of a
desired eigenvalue. All information about the network matrix, the
sensor nodes, the constraint graph, and the unobservable eigenvalue is
encoded in the matrix H as in (7), (9) and (20). Although convergence
of Algorithm 1 is not guaranteed, numerical studies show that it
performs well in practice; see Sections III-C and IV.
C. Optimal perturbations and algorithm validation
In this section we validate Algorithm 1 on a small network. We
start with the following result.
Theorem 3.7: (Optimal perturbations of 3-dimensional line networks with fixed λ ∈ C) Consider a network with graph G = (V, E),
1

To see this, let σ be an eigenvalue of (H, D), that is, Hx = σDx.
Then, (H − µD)x = Hx − µDx = σDx − µDx = (σ − µ)Dx. That is
(H − µD)x = (σ − µ)Dx thus σ − µ is an eigenvalue of (H − µD, D).
2 In Algorithm 1 the range for ψ has been empirically determined during
our numerical studies.

PB2 (s) = s2 − (b22 + b33 )s + b22 b33 − b23 b32 .
For λ ∈ spec(B2 ), we must have PB2 (s) = (s − λ)(s − λ̄), where
λ̄ is the complex conjugate of λ. Thus,
PB2 (s) = (s − λ< − iλ= )(s − λ< + iλ= ) = s2 − 2λ< s + λ2< + λ2= ,
which leads to
b22 + b33 − 2λ< = 0, and b22 b33 − b23 b32 − λ2< − λ2= = 0. (22)
The Lagrange function
of the minimization problem with cost
P
P
function k∆∗ k2F = 3i=2 3j=2 (bij − aij )2 and constraints (22) is
L(b22 , b23 , b32 , b33 , p1 , p2 ) = d222 + d223 + d232 + d233
+ p1 (2λ< + b22 + b33 ) + p2 (b22 b33 − b23 b32 − (λ2< + λ2= )),
where p1 , p2 ∈ R are Lagrange multipliers, and dij = bij − aij . By
equating the partial derivatives of L to zero we obtain
∂L
∂b22
∂L
∂b33
∂L
∂b23
∂L
∂b32

= 0 ⇒ 2d22 + p1 + p2 b33 = 0,

(23)

= 0 ⇒ 2d33 + p1 + p2 b22 = 0,

(24)

= 0 ⇒ 2d23 − p2 b32 = 0,

(25)

= 0 ⇒ 2d32 − p2 b23 = 0,

(26)

together with (22). The statement follows by substituting the Lagrange multipliers p1 and p2 into (23) and (26).
To validate Algorithm 1, in Fig. 1 we compute optimal perturbations for 3-dimensional line networks based on Theorem 3.7, and
compare them with the perturbation obtained at with Algorithm 1.

Accordingly, the modified network matrix is reducible and reads as


A11
0
.
Ā =
A21 A22

1.4

1

⇤

kF

1.2

k

0.8

(i)

kF

0.6
0.4

k

0.2
0

-0.2

0

10

20

30

40

50

60

70

80

i

Fig. 1. This figure validates the effectiveness of Algorithm 1 to compute
optimal perturbations for the line network in Section III-C. The plot shows
the mean and standard deviation over 100 networks of the difference between
∆∗ , obtained via the optimality conditions (21), and ∆(i) , computed at the
i-th iteration of Algorithm 1. The unobservable eigenvalue is λ = i and the
values aij are chosen independently and uniformly distributed in [0, 1].

IV. O BSERVABILITY R ADIUS OF R ANDOM N ETWORKS : THE
C ASE OF L INE AND S TAR N ETWORKS
In this section we study the observability radius of networks with
fixed structure and random weights, when the desired unobservable
eigenvalue is an optimization parameter as in (2). First, we give a
general upper bound on the size of an optimal perturbation. Next, we
explicitly compute optimal perturbations for line and star networks,
showing that their robustness is essentially different.
We start with some necessary definitions. Given a directed graph
G = (V, E), a cut is a subset of edges Ē ⊆ E. Given two disjoint
sets of vertices S1 , S2 ⊂ V, we say that a cut Ē disconnects S2
from S1 if there exists no path from any vertex in S2 to any vertex
in S1 in the subgraph (V, E \ Ē). Two cuts E1 and E2 are disjoint
if they have no edge in common, that is, ifR E1 ∩ E2 = ∅. Finally,
∞
the Gamma function is defined as Γ(z) = 0 xz−1 e−x dx. With
this notation in place, we are in the position to prove a general
upper bound on the (expected) norm of the smallest perturbation that
prevents observability. The proof is based on the following intuition:
a perturbation that disconnects the graph prevents observability.
Theorem 4.1: (Bound on expected network observability radius)
Consider a network with graph G = (V, E), weighted adjacency
matrix A = [aij ], and sensor nodes O ⊆ V. Let the weights aij be
independent random variables uniformly distributed in the interval
[0, 1]. Define the minimal observability-preventing perturbation as
δ=
s.t.

min

λ∈C,x∈Cn ,∆∈Rn×n

k∆kF ,

(27)

(A + ∆)x = λx,
kxk2 = 1,
CO x = 0,
∆ ∈ AG .

Let Ωk (O) be a collection of disjoint cuts of cardinality k, where
each cut disconnects a non-empty subset of nodes from O. Let
ω = |Ωk (O)| be the cardinality of Ωk (O). Then,
Γ(1/k) Γ(ω + 1)
E[δ] ≤ √
.
k Γ(ω + 1 + 1/k)
Proof: Let Ē ∈ Ωk (O). Notice that, after removing the edges
Ē, the nodes are partitioned as V = V1 ∪ V2 , where V1 ∩ V2 = ∅,
O ⊆ V1 , and V2 is disconnected from V1 . Reorder the network
nodes so that V1 = {1, . . . , |V1 |} and V2 = {|V1 | + 1, . . . , |V|}.

Let x2 be an eigenvector of A22 with corresponding eigenvalue λ.
Notice that λ is an eigenvalue of Ā with eigenvector x = [0 xT2 ]T .
Since O ⊆ V1 , CO x = 0, so that the eigenvalue λ is unobservable.
From the above discussion we conclude that, for each Ē ∈ Ωk (O),
there exists a perturbation ∆ = [δij ] that is compatible with G
and ensures that one eigenvalue is unobservable. Moreover, the
perturbation ∆ is defined as δij = −aij if (i, j) ∈ Ē, and δij = 0
otherwise. We thus have


s X
2
E[δ] ≤ E  min
aij  .
Ē∈Ωk (O)

(i,j)∈Ē

Because any two elements of Ωk (O) have empty intersection and all
edge weights are independent, we have


ω

s X
s X
2
2
aij ≥ x = Pr 
aij ≥ x
Pr  min
Ē∈Ωk (O)

(i,j)∈Ē

= Pr 

(i,j)∈Ē

ω


X

a2ij

≥x

2



= 1 − Pr 

(i,j)∈Ē

ω


X

a2ij

≤x

2 

.

(i,j)∈Ē

In order to obtain a more explicit expression for this probability, we
resort to using a lower bound.
Let a denote the vector of aij with
P
(i, j) ∈ Ē. The condition (i,j)∈Ē a2ij ≤ x2 implies that a belongs to
the k-dimensional sphere of radius x (centered at the origin). In fact,
since a is sampled in [0, 1]k , it belongs to the intersection between
the sphere and the first orthant. By computing the volume of the
k-dimensional cube inscribed in the sphere, we obtain
 

√
 k
√
 (2x/ k)k
X 2
= √xk , x ≤ k,
2
k


2
≥
Pr
aij ≤ x
1,
otherwise.
(i,j)∈Ē
Since δ takes on nonnegative values only, its expectation can be
computed by integrating the survival function
Z ∞
E[δ] =
Pr (δ ≥ t) dt,
0

which leads us to obtain, by suitable changes of variables,

k !ω
Z √k
ω
√ Z 1
x
1− √
dx = k
E[δ] ≤
1 − tk dt
k
0
0
Z 1
1 −1
1 Γ(1/k)Γ(ω + 1)
1
ω k
(1 − z) z
dz = √
,
= √
k 0
k Γ(ω + 1/k + 1)
where the last equality
follows from the definition of the Beta funcR1
tion, B(x, y) = 0 tx−1 (1 − t)y−1 dt for Real(x) > 0, Real(y) > 0,
Γ(y)
and its relation with the Gamma function, B(x, y) = Γ(x)
.
Γ(x+y)
We now use Theorem 4.1 to investigate the asymptotic behavior of the
expected observability radius on sequences of networks of increasing
cardinality n. In order to emphasize the dependence on n, we shall
write E[δ(n)] from now on. As a first step, we can apply Wendel’s
inequalities [21] to find
Γ(ω + 1)
(ω + 1 + 1/k)1−1/k
1
≤
≤
.
1/k
Γ(ω + 1 + 1/k)
(ω + 1)
(ω + 1)
If in a sequence of networks ω grows to infinity and k remains
constant, then the ratio between the lower and the upper bounds goes
to one, yielding the asymptotic equivalence
Γ(1/k) Γ(ω + 1)
Γ(1/k)
1
E[δ(n)] ≤ √
∼ √
.
(ω
+
1)1/k
k Γ(ω + 1 + 1/k)
k

(a) Line network

(b) Star network

Fig. 2. Line and star networks with self-loops. Sensor nodes are marked in
black. Note that, self-loops are not shown.

This relation implies that a network becomes less robust to perturbations as the size of the network increases, with a rate determined
by k. In the rest of this section we study two network topologies
with different robustness properties. In particular, we show that line
networks achieve the bound in Theorem 4.1, proving its tightness,
whereas star networks have on average a smaller observability radius.

yielding a perturbation with minimum norm. In fact, if
ai∗ −1,i∗ = min{a12 , . . . , an−1,n }, then all eigenvalues of the
submatrix of A with rows/columns in the set {i∗ , . . . , n} are
unobservable, and thus minimizers in (27).
Both Theorems 4.1 and 4.2 are based on constructing perturbations
by disconnecting the graph. This strategy, however, suffers from
performance limitations and may not be optimal in general. The next
example shows that different kinds of perturbations, when applicable,
may yield a lower cost.
(Star network) Let G be a star network with n nodes and one sensor
node as in Fig. 2. The adjacency and output matrices read as


a11 a12 a13
···
a1n
 a21 a22
0
···
0 


.. 

..
..

,
.
.
a
0
.
A =  31

(29)
 .

.
..
 ..
0
an−1,n−1
0 
an1
0
0
0
ann


CO = 1 0 0 · · · 0 .

(Line network) Let G be a line network with n nodes and one sensor
node as in Fig. 2. The adjacency and output matrices read as


a11 a12
0
···
0
a21 a22
a23
···
0 


 .
..  ,
.
.
.
..
..
..
A =  ..

.


(28)
 0
· · · an−1,n−2 an−1,n−1 an−1,n 
0
···
0
an,n−1
ann


CO = 1 0 0 · · · 0 .

Differently from the case of line networks, star networks are not
strongly structurally observable, so that different perturbations may
result in unobservability of some modes.
Theorem 4.3: (Structured perturbation of star networks) Consider a star network with matrices as in (29), where the weights
aij are independent random variables uniformly distributed in the
interval [0, 1]. Let δ(n) be the minimal cost defined as in (27). Let

We obtain the following result.
Theorem 4.2: (Structured perturbation of line networks) Consider a line network with matrices as in (28), where the weights
aij are independent random variables uniformly distributed in the
interval [0, 1]. Let δ(n) be the minimal cost defined as in (27). Then,

Then,

1
.
n
Proof: It is known that line networks, when observed from one
of their extremes, are strongly structurally observable, that is, they
are observable for every nonzero choice of the edge weights [22].
Consequently, for the perturbed system to feature an unobservable
eigenvalue, the perturbation ∆ must be such that δi,i+1 = −ai,i+1
for some i ∈ {2, . . . , n − 1}. Thus, a minimum norm perturbation
is obtained by selecting the smallest entry ai,i+1 . Since the ai,i+1
are independent and identically distributed, δ(n) = min ai,i+1 is a
random variable with survival function Pr(δ(n) ≥ x) = (1 − x)n−1
for 0 ≤ x ≤ 1, and Pr(δ(n) ≥ x) = 0 otherwise. Thus,
Z 1
1
E[δ(n)] =
Pr(δ(n) ≥ x)dx = .
n
0
δ(n) = min{a12 , . . . , an−1,n }, and E[δ(n)] =

Theorem 4.2 characterizes the resilience of line networks to
structured perturbations. We remark that, because line networks are
strongly structurally observable, structured perturbations preventing
observability necessarily disconnect the network by zeroing some
network weights. Consistently with this remark, line networks achieve
the upper bound in Theorem 4.1, being therefore maximally robust
to structured perturbations. In fact, for O = {1} and a cut size k = 1
we have Ω1 (O) = {a12 , . . . , an−1,n } and ω = n − 1. Thus,
Γ(1)Γ(n)
(n − 1)!
1
=
= ,
E[δ(n)] ≤ √
n!
n
1Γ(n + 1)
which equals the behavior identified in Theorem 4.2. Further,
Theorem 4.2 also identifies an unobservable eigenvalue

γ=

min
i,j∈{2,...,n},i6=j

|aii − ajj |
√
.
2

δ(n) = min{a12 , a13 , . . . , a1n , γ}, and
1
1
√
≤ E[δ(n)] ≤ √
.
2 n(n − 1)
2 n(n − 2)
Proof: Partition the network matrix A in (29) as


a11 A12
,
A=
A21 A22
where A12 ∈ R1,n−1 , A21 ∈ Rn−1,1 , A22 ∈ Rn−1,n−1 . Accordingly, let x = [x1 xT2 ]T . The condition CO x = 0 implies x1 = 0.
Consequently, for the condition (A + ∆)x = λx to be satisfied,
we must have (A12 + ∆12 )x2 = 0 and (A22 + ∆22 )x2 = λx2 .
Notice that, because A22 is diagonal and ∆ ∈ AG , the condition
(A22 + ∆22 )x2 = λx2 implies that λ = aii + δii for all indices i
such that i ∈ Supp(x2 ), where Supp(x2 ) denotes the set of nonzero
entries of x2 . Because kxk = 1, |Supp(x2 )| > 0. We have two cases:
Case |Supp(x2 )| = 1: Let Supp(x) = {i}, with i ∈ {2, . . . , n}.
Then, the condition (A12 +∆12 )x2 = 0 implies δ1,i = −a1,i , and the
condition (A22 + ∆22 )x2 = λx2 is satisfied with ∆22 = 0, λ = aii ,
and x = ei , where ei is the i-th canonical vector of dimension n.
Thus, if |Supp(x2 )| = 1, then δ(n) = mini∈{2,...,n} a1,i .
Case |Supp(x2 )| > 1: Let S = Supp(x2 ). Then, δii = λ − aii .
Notice that the condition (A22 + ∆22 )x2 = λx2 is satisfied for every
x2 with support S and, particularly, for x2 ∈ Ker(A12 ). Thus, we
let ∆12 = 0. Notice that
sX
(λ − aii )2 ,
δ(n) = min
λ,S

i∈S

and that δ(n) is obtained when S = {i, j}, for some i, j ∈
{2, . . . , n}, and λ = (aii + ajj )/2.√Specifically, for the indexes
{i, j}, we have k∆kF = |aii − ajj |/ 2. Thus, if |Supp(x2 )| > 1,
then δ(n) = γ, which concludes the proof of the first statement.

V. C ONCLUSION

Star
Line

E[ (n)]

10-1

10-2

10

-3

5

10

15

20

25

n

Fig. 3. Expected values E[δ(n)] for the two network topologies in Fig. 2
as functions of the network cardinality n. Dotted lines represent upper and
lower bounds in Theorems 4.2 and 4.3. Solid lines show the mean over 100
networks of the Frobenius norm of the perturbations obtained by Algorithm 1.

In order to estimate E[δ(n)], notice that δ(n) = min{α, γ}, where
α = min{a12 , a13 , . . . , a1n }, and that α and γ are independent
random variables. Then, from [23, Chapter 6.4] we have
Pr(δ(n) ≥ x) = Pr(α ≥ x)Pr(γ ≥ x)

√
= (1 − x)n−1 (1 − (n − 2) 2x)n−1 ,

√
for x ≤ ( 2(n − 2))−1 , and Pr(δ(n) ≥ x) = 0 otherwise. Thus,
Z √ 1
√
2(n−2)
E[δ(n)] =
(1 − x)n−1 (1 − (n − 2) 2x)n−1 dx.
0

Next, for the upper bound observe that
Z √ 1
√
2(n−2)
(1 − x)n−1 (1 − (n − 2) 2x)n−1 dx
0
√

Z
≤

1
2(n−2)

√
(1 − (n − 2) 2x)n−1 dx = √

0

1
,
2n(n − 2)

and for the lower bound observe that
Z √ 1
√
2(n−2)
(1 − x)n−1 (1 − (n − 2) 2x)n−1 dx
0

Z
=

√ 1
2(n−2)

√
√
(1 − ((n − 2) 2 + 1)x + ((n − 2) 2)x2 )n−1 dx

√ 1
2(n−1)

√
(1 − (n − 1) 2x)n−1 dx = √

0

Z
≥
0

1
.
2n(n − 1)

Theorem 4.3 quantifies the resilience of star networks, and the
unobservable eigenvalues requiring minimum norm perturbations; see
the proof for a characterization of this eigenvalues.
The bounds in Theorem 4.3 are asymptotically tight and imply
1
E[δ(n)] ∼ √
, as n → ∞.
2 n2
See Fig. 3 for a numerical validation of this result. This rate of
decrease implies that star networks are structurally less robust to
perturbations than line networks. Crucially, unobservability in star
networks may be caused by two different phenomena: the deletion
of an edge disconnecting a node from the sensor node (deletion of the
smallest among the edges {a12 , a13 , . . . , a1n }), and the creation of
a dynamical symmetry with respect to the sensor node by perturbing
two diagonal elements to make them equal in weight. It turns out that,
on average, creating symmetries is “cheaper” than disconnecting the
network. The role of network symmetries in preventing observability
and controllability has been observed in several independent works;
see for instance [16], [17]. Finally, the comparison of line and star
networks shows that Algorithm 1 is a useful tool to systematically
investigate the robustness of different topologies.

In this work we extend the notion of observability radius to
network systems, thus providing a measure of the ability to maintain
observability of the network modes against structured perturbations of
the edge weights. We characterize network perturbations preventing
observability, and describe a heuristic algorithm to compute perturbations with smallest Frobenius norm. Additionally, we study the
observability radius of networks with random weights, derive a fundamental bound relating the observability radius to certain connectivity
properties, and explicitly characterize the observability radius of line
and star networks. Our results show that different network structures
exhibit inherently different robustness properties, and thus provide
guidelines for the design of robust complex networks.
R EFERENCES
[1] G. Bianchin, P. Frasca, A. Gasparri, and F. Pasqualetti, “The observability radius of network systems,” in American Control Conference, 2016
(to appear).
[2] R. E. Kalman, Y. C. Ho, and S. K. Narendra, “Controllability of linear
dynamical systems,” Contributions to Differential Equations, vol. 1,
no. 2, pp. 189–213, 1963.
[3] F. Pasqualetti, S. Zampieri, and F. Bullo, “Controllability metrics,
limitations and algorithms for complex networks,” IEEE Transactions
on Control of Network Systems, vol. 1, no. 1, pp. 40–52, 2014.
[4] F. L. Cortesi, T. H. Summers, and J. Lygeros, “Submodularity of energy
related controllability metrics,” in IEEE Conference on Decision and
Control, Los Angeles, CA, USA, Dec. 2014, pp. 2883–2888.
[5] G. Kumar, D. Menolascino, and S. Ching, “Input novelty as a control
metric for time varying linear systems,” arXiv preprint arXiv:1411.5892,
2014.
[6] A. Olshevsky, “Minimal controllability problems,” IEEE Transactions
on Control of Network Systems, vol. 1, no. 3, pp. 249–258, Sept 2014.
[7] N. Monshizadeh, S. Zhang, and M. K. Camlibel, “Zero forcing sets
and controllability of dynamical systems defined on graphs,” IEEE
Transactions on Automatic Control, vol. 59, no. 9, pp. 2562–2567, 2014.
[8] M. Fardad, A. Diwadkar, and U. Vaidya, “On optimal link removals for
controllability degradation in dynamical networks,” in IEEE Conference
on Decision and Control, Los Angeles, CA, USA, Dec. 2014, pp. 499–
504.
[9] W. M. Wonham, Linear Multivariable Control: A Geometric Approach,
3rd ed. Springer, 1985.
[10] C. Paige, “Properties of numerical algorithms related to computing
controllability,” IEEE Transactions on Automatic Control, vol. 26, no. 1,
pp. 130–138, 1981.
[11] R. Eising, “Between controllable and uncontrollable,” Systems & Control
Letters, vol. 4, no. 5, pp. 263–264, 1984.
[12] D. L. Boley and W.-S. Lu, “Measuring how far a controllable system is
from an uncontrollable one,” IEEE Transactions on Automatic Control,
vol. 31, no. 3, pp. 249–251, 1986.
[13] G. Hu and E. J. Davison, “Real controllability/stabilizability radius of
lti systems,” IEEE Transactions on Automatic Control, vol. 49, no. 2,
pp. 254–257, 2004.
[14] M. Karow and D. Kressner, “On the structured distance to uncontrollability,” Systems & Control Letters, vol. 58, no. 2, pp. 128–132, 2009.
[15] B. De Moor, “Total least squares for affinely structured matrices and the
noisy realization problem,” IEEE Transactions on Signal Processing,
vol. 42, no. 11, pp. 3104–3113, 1994.
[16] A. Chapman and M. Mesbahi, “On symmetry and controllability of
multi-agent systems,” in IEEE Conference on Decision and Control,
Los Angeles, CA, USA, Dec. 2014, pp. 625–630.
[17] F. Pasqualetti and S. Zampieri, “On the controllability of isotropic and
anisotropic networks,” in IEEE Conference on Decision and Control,
Los Angeles, CA, USA, Dec. 2014, pp. 607–612.
[18] T. Kailath, Linear Systems. Prentice-Hall, 1980.
[19] L. N. Trefethen and D. Bau III, Numerical linear algebra. SIAM, 1997.
[20] G. H. Golub and C. F. Van Loan, Matrix computations. JHU Press,
2012.
[21] J. G. Wendel, “Note on the Gamma function,” American Mathematical
Monthly, pp. 563–564, 1948.
[22] H. Mayeda and T. Yamada, “Strong structural controllability,” SIAM
Journal on Control and Optimization, vol. 17, no. 1, pp. 123–138, 1979.
[23] H. A. David and H. N. Nagaraja, Order statistics. John Wiley & Sons,
2003.

