Structural Controllability of Linear Time-invariant Systems

arXiv:1707.08243v1 [cs.SY] 25 Jul 2017

F. Liu and A. S. Morse

Abstract—One version of the concept of structural controllability defined for single-input systems by Lin and subsequently
generalized to multi-input systems by others, states that a parameterized matrix pair (A, B) whose nonzero entries are distinct
parameters, is structurally controllable if values can be assigned
to the parameters which cause the resulting matrix pair to be
controllable. In this paper the concept of structural controllability
is broadened to allow for the possibility that a parameter may
appear in more than one location in the pair (A, B). Subject to
a certain condition on the parameterization called the “binary
assumption”, an explicit graph-theoretic characterization of such
matrix pairs is derived.
Index Terms—Linear time-invariant systems, structural controllability, graph theory.

I. I NTRODUCTION
Over the past few years there has been a resurgence of
interest in the question of structural controllability posed
by Lin in 1974 [1]. As defined by Lin, a pair of matrices
(An×n , bn×1 ) with each entry either a fixed zero or a distinct
scalar parameter is structurally controllable if there is a real
matrix pair (Ān×n , b̄n×1 ) with the same pattern of zero entries
as (A, b) which is controllable. Thus if (A, b) is structurally
controllable, then almost every real matrix pair (Ā, b̄) with
the same pattern of zero entries as (A, b) will be controllable.
Lin was able to give an explicit graph-theoretic condition for
such a matrix pair to be structurally controllable in terms
of properties of a suitably defined directed graph determined
by the given matrix pair. Lin’s result was extended to multiinput matrix pairs (An×n , Bn×m ) in linear algebra terms by
Shields and Pearson [2] and reexplained in graph theory terms
by Mayeda [3]. Generic properties and design problems of
Lin’s parameterization of the pair (A, B) were studied in
[4]–[10]. Results on structural controllability of linear timevarying systems were presented in [11]–[18]. One line of
research deals with the structural controllability of composite
systems [19]–[22]. Current interest stems from the realization
that structural controllability is a key property of interest in
swarming behavior and in the modeling and understanding
complex networks [23]–[28]. For example, identification of
driver vertices or steering vertices in biomedical networks
[29]–[31], which tend to have strong ability to influence other
vertices, may enlighten us on critical underlying relations or
mechanisms; the study of robustness of structural controllability to vertex and/or arc failures and disturbances [32]–[36]
may give us an insight in the evolution of complex social
networks and various issues of network security [37], [38].
This work was supported by National Science Foundation grant n.
1607101.00 and US Air Force grant n. FA9550-16-1-0290.
F. Liu and A. S. Morse are with the Department of Electrical Engineering,
Yale University, New Haven, CT 06511 USA (e-mail: fengjiao.liu@yale.edu;
as.morse@yale.edu).

In previous work, there was also interest in structural controllability for more general kinds of parameterizations [39]–
[41]. In particular, the notion of a “linearly parameterized”
matrix pair was introduced in [39] which allowed parameters
to appear in multiple locations in the pair (A, B). In this paper,
we address this same kind of parameterization satisfying a
certain condition called the “binary assumption” and show
by counterexample that this is the most general class of
linear parameterizations for which one can expect a graphical
characterization with unweighted graphs. Finally, the structural
controllability of this class of linear parameterizations is
characterized in strict graph-theoretic terms.
A. Linear Parameterization
Interesting as the results of Lin’s parameterization are,
they cannot address many simple but commonly encountered
modeling situations such as when A and b are of the forms


 
p p1
p
A= 1
, b= 1
(1)
0 0
p2
where at least one parameter, in this example p1 , appears
in more than one location. Recognition of this led to the
definition of a “linearly parameterized” matrix pair and to a
significant generalization of the concept of structural controllability [39]. The version of a linearly parameterized matrix
pair to which we are referring is of the form1
X
X
An×n (p) =
gk pk hk1 , Bn×m (p) =
gk pk hk2 (2)
k∈q

k∈q

q

where p ∈ IR is a vector of q > 0 algebraically independent
parameters p1 , p2 , . . . , pq , q , {1, 2, . . . , q}, and for each
k ∈ q, gk ∈ IRn , hk1 ∈ IR1×n , hk2 ∈ IR1×m . In this context,
the problem of interest is to find conditions for the existence
of a parameter vector p ∈ IRq for which (A(p), B(p)) is a
controllable matrix pair. If such values exist, the parameterized
pair (A(p), B(p)) is structurally controllable. Such pairs are
controllable for almost every value of p in the sense that the
set of values of p for which (A, B) is controllable is the
complement of an algebraic variety in IRq .
Necessary and sufficient conditions for such a matrix pair to
be structurally controllable in this more generalized sense are
developed in [39]. Like the work of Shields and Pearson [2],
these conditions are primarily matrix-algebraic. Other types
of parameterization [40], [41] have also been explored purely
algebraically. Since graphical results can reveal important
structural properties hidden in matrix representations, there is
interest in determining graphical conditions characterizing this
1 Although written differently, this linear parameterization is in fact the same
as the one considered in [39] except that in [39] there are constant matrices
A0 and B0 also appearing in the sums in (2) for A(p) and B(p) respectively.

generalized concept of structural controllability and this is the
specific problem which this paper is addressed.
Before proceeding we point out that not every matrix pair
(A, B) with parameters entering “linearly” is a linear parameterization as defined here. For example, while the matrix pair
shown in (1) is linearly parameterized, the matrix pair


 
p1 p1
0
A=
, b=
(3)
0 p1
p2
is not. It is not hard to see that a matrix pair (A, B) whose
entries depend linearly on q parameters p1 , p2 , . . . , pq will
be linearly parameterized if and only if all minors of the
partitioned matrix [A B] are multilinear functions of the q
parameters. It is clear that the matrices in (3) do not have this
property.
In the sequel it will be convenient to use the n × (n + m)
partitioned matrix [A(p) B(p)]. In view of (2), this matrix can
be expressed as
X
[A(p) B(p)] =
gk pk hk
(4)
k∈q

where hk , [hk1 hk2 ] for k ∈ q. It will be assumed for simplicity and without loss of generality that the set of matrices
{g1 h1 , g2 h2 , . . . , gq hq } is linearly independent. To justify this
assumption, suppose that the set is not linearly independent
and for purposes of illustration that gq hq is a linear combination of the remaining matrices g1 h1 , g2 h2 , . . . , g(q−1) h(q−1) .
In other words, suppose that
gq hq =

q−1
X

B. Graph of (A, B)
It is easy to see that the definition of structural controllability for a linearly parameterized matrix pair (A, B) coincides
with Lin’s if m = 1 and the gk and hk are restricted to be
unit vectors in IRn and IR1×(n+1) respectively. Lin defines the
graph of such a matrix pair to be a directed graph on n + 1
vertices labeled 1 to n + 1 with an arc from vertex j to vertex
i if the ijth entry in the matrix [A B] is a parameter. For the
more general linear parameterization defined by (4), a more
elaborate definition of a graph is needed not just because m
might be greater than 1, but also because some parameter pk
may appear in multiple locations in [A B].
The graph of (A, B), written G, is defined to be a directed
graph with n + m vertices labeled 1 through n + m and an arc
of color2 k from vertex j to vertex i if the ijth entry in the
matrix gk hk is nonzero, i.e., the ijth entry in the partitioned
matrix [A B] contains pk . In the sequel, (j, i)k denotes an
arc from vertex j to vertex i with color k. This graph has q
colors.
For example, Figure 1 shows the graph of


 
0 p1
0 0 0 p1
p5 0 0 0  p2 p2 


 
(5)
 0 0 p3 p3  ,  0 0 
p4 0
0 0 p4 0
where symbol k labels color k for k = 1, 2, . . . , 5.
1
4

ck gk hk

k=1

[A(p) B(p)] =

q−1
X

1

3

where the ck are real numbers. Then in view of (4),

5
1

2

4
2

3
3

gk (pk + ck pq )hk

4

2
5

k=1

6

Fig. 1: The graph of the matrix pair in (5).

Therefore if we define new parameters p̄k = pk + ck pq for
k ∈ {1, 2, . . . , q − 1}, then the right side of (4) can be written
using only the first q − 1 matrices in {g1 h1 , g2 h2 , . . . , gq hq }
as
q−1
X
gk p̄k hk
k=1

It is clear from this that the process of defining
new parameters and eliminating dependent matrices from
{g1 h1 , g2 h2 , . . . , gq hq } can be continued until one has a
linearly independent subset of matrices. This justifies our
claim and accordingly it will henceforth be assumed that
{g1 h1 , g2 h2 , . . . , gq hq } is a linearly independent set. This
implies that q ≤ n(n + m).
Since this paper deals with matrix pairs parameterized by
p exclusively, it is convenient to drop p in A(p) and B(p),
i.e., to write A and B instead of A(p) and B(p), with the
understanding that (A, B) is parameterized by p.

Note that the graph of (A, B) has three properties: (i) There
are no arcs pointing toward any of the m vertices with labels
n + 1 to n + m, since the matrix [A B] only has n rows.
(ii) There may be more than one arc from one given vertex
j to another vertex i, for the ijth entry in the matrix [A B]
may be a linear combination of more than one parameter. If
this is the case, all arcs from vertex j to vertex i will have
distinct colors. (iii) If there are two arcs of color k ∈ q, one
leaving vertex j and the other pointing toward vertex i, then
there must be an arc (j, i)k . This is because the two given arcs
imply that the jth entry in the row vector hk and the ith entry
in the column vector gk are nonzero, which means the ijth
entry in the matrix gk hk is nonzero. Any directed graph on
n+m vertices which has these properties is called a structural
controllability graph.
2 In

this paper, each color is labeled by a distinct integer.

C. Binary Assumption
This paper focuses exclusively on linear parameterizations
which satisfy a certain “binary assumption”. Specifically, the
linear parameterization defined by (4) satisfies the binary
assumption if all of the gk and hk appearing in (4) are
binary vectors, i.e., vectors of 1’s and 0’s. Similarly, a linear
parameterization satisfies the unitary assumption if all of the
gk and hk appearing in (4) are unit vectors. So any linear parameterization satisfying the unitary assumption also satisfies
the binary assumption. Lin’s parameterization is exactly the
linear parameterization satisfying the unitary assumption.
It is quite clear that when the binary assumption holds with
n and m specified, the parameterization in (4) is uniquely
determined by a structural controllability graph. Because of
this, it is possible to characterize structural controllability of a
linearly parameterized matrix pair (A, B) which satisfies the
binary assumption, solely in terms of the graph of the pair.
On the other hand, without the binary assumption, no such
graphical characterization3 is possible. The following example
illustrates this.
Note that although the matrix pairs

  

  
p1 p1 p2
0
p1 p1 p2
0
p1 p1 p2  ,  0  and p1 p1 2p2  ,  0 
0 0 0
p3
p3
0 0
0
both have the same graph, only the pair on the right is
structurally controllable. Of course the pair on the right does
not satisfy the binary assumption.
D. Problem Formulation and Organization
This paper gives the necessary and sufficient graph-theoretic
conditions for the structural controllability of a linearly parameterized matrix pair (An×n , Bn×m ) which satisfies the binary
assumption. To the best of our knowledge, this is the first
graph-theoretic result that generalizes the conditions given in
[1] and [3]. The rest of the paper is organized as follows.
The terminology and concepts used in this paper are defined
in Section II. The main result of this paper is presented in
Section III and proved in Section IV.
II. P RELIMINARIES
In order to state the main result of this paper, some
terminology and a number of graphical and algebraic concepts
are needed.
A. Terminology
Let H be a directed graph with a vertex set V. For any subset
U ⊂ V, V − U is the complement of U in V. A source vertex
in H is a vertex with no incoming arcs and a sink vertex in H
is a vertex with no outgoing arcs. An isolated vertex is both a
source vertex and a sink vertex. A directed tree is a graph in
which there is a vertex called the root and for each vertex v
3 If the binary assumption is dropped, one way to proceed is to define the
graph of (A, B) as a weighted directed graph, in which the weight of an
arc (j, i)k is the ijth entry in the matrix gk hk . The conditions on weighted
graphs for the structural controllability of all linearly parameterized matrix
pairs will be studied in a sequel of this paper.

except the root there is a unique directed path from the root to
v. H has a spanning forest if it has a spanning subgraph which
is the disjoint union of directed rooted trees. Let Vroot ⊂ V be
the set of root vertices of the trees. So H has a spanning
forest rooted at the vertices in Vroot if and only if for each
vertex v ∈ V − Vroot , there is a directed path to v from one of
the root vertices. A partition π of V is a family of nonempty
subsets of V which are pairwise disjoint and whose union is
equal to V. The quotient graph of H induced by π, written
H/π, is a directed graph with one vertex for each subset of
π, and exactly one arc from vertex i to vertex j whenever H
has at least one arc from the vertices in the ith subset to the
vertices in the jth subset. H/π is the condensation of H if π
is formed by the collection of strongly connected components
of H.
B. Graphical Concepts
A multi-colored subgraph of a structural controllability
graph G is a spanning subgraph of G, which is the disjoint
union of m simple directed path graphs and any number of
simple directed cycle graphs with each arc in the union graph
of a different color. In this context one isolated vertex is a
simple directed path graph of length 0 and one vertex with a
single self-loop is a simple directed cycle graph of length 1.
Clearly, a multi-colored subgraph of G has n arcs in n distinct
colors. Figure 2 shows three multi-colored subgraphs of the
graph in Figure 1.
A multi-colored subgraph S of a structural controllability
graph G is obtained by sequentially removing arcs from G as
follows. First pick any arc (a, b)k1 in G and then remove any
other arcs with the same color k1 as well as any arcs other
than (a, b)k1 pointing toward vertex b and/or leaving vertex a.
Next, from the set of arcs which remain after these removals,
pick any arc (c, d)k2 and repeat the process until no further arc
removals are possible. If a total of n arcs are left, the graph
which remains is S. Clearly, S is not unique. In the sequel,
R(G) denotes the set of all multi-colored subgraphs of G.
The source vertices (respectively, sink vertices) of a multicolored subgraph S are the m source vertices (respectively,
sink vertices) of the simple path graphs in S. It is not hard to
see that the source vertices of every multi-colored subgraph of
G are the m vertices with labels n + 1 to n + m, since there
are no arcs pointing toward them. But the sink vertices of a
multi-colored subgraph may be any m vertices in G.
Two multi-colored subgraphs S1 , S2 ∈ R(G) are called
similar if S1 and S2 have the same m sink vertices and
the same set of n colors. Graph similarity is an equivalence
relation on R(G). The corresponding equivalence classes
induced by this relation are called similarity classes.
As an example of this concept, let G be the graph in Figure 1. Let E1 be the similarity class of multi-colored subgraphs
with sink vertices 1 and 2, and colors 1, 2, 3, 4. Figure 2a
and Figure 2b show the two multi-colored subgraphs in E1 .
Figure 2c shows a multi-colored subgraph in the similarity
class E2 with sink vertices 2 and 6, and colors 1, 3, 4, 5. In
fact, this graph is the only multi-colored subgraph of G in E2 .
Specific quotient graphs of the multi-colored subgraphs in
the same similarity class will be used to define an important

2
1

5

1

3
1

2

4

4
2

1

3

1

4

3

1

3

2

3

2

4

4

3
5

5

6

4

6

(b)

(a)

5

6

(c)
Fig. 2: Multi-colored subgraphs of the graph in Figure 1.

property of the class. Let V be the vertex set of a structural
controllability graph G. For any subset U ⊂ V, let |U| be
the number of elements in U. Let Vsource ⊂ V be the set of
m source vertices of every multi-colored subgraph of G. Let
Vsink ⊂ V be the set of m sink vertices of a given multicolored subgraph S of G. So Vsource ∩Vsink is the set of isolated
vertices in S and |Vsource − (Vsource ∩ Vsink )| = |Vsink − (Vsource ∩
Vsink )| ≤ m. The desired quotient graph of S is induced by a
“matrimonial partition”. A partition π of V is a matrimonial
partition for S if it pairs each vertex in Vsource −(Vsource ∩Vsink )
with a different vertex in Vsink − (Vsource ∩ Vsink ) and assigns
each pair to a different subset, then assigns each of the rest
vertices in V to a new subset. So there are |V| − |Vsource −
(Vsource ∩ Vsink )| subsets in π and each of them has at most
two vertices. If the pairing is not unique, π is not unique.
An observation made by comparing S and the quotient graph
S/π is that the simple cycle graphs and isolated vertices in S
remain the same in S/π, while the simple path graphs with
positive lengths in S are, roughly speaking, “welded” together
to form new simple directed cycle graphs in S/π. In the sequel,
it is assumed that the quotient graphs of all multi-colored
subgraphs in one similarity class are induced by the same
matrimonial partition.
For example, π = {{1, 5}, {2, 6}, {3}, {4}} is a matrimonial partition for the two multi-colored subgraphs in Figure 2a
and Figure 2b. The quotient graphs of the two graphs induced
by π are shown in Figure 3a and Figure 3b, respectively.
A multi-colored subgraph is odd (respectively, even) if its
quotient graph induced by a matrimonial partition has an odd
(respectively, even) number of simple directed cycle graphs.
As will be stated in Lemma 4, the choice of the matrimonial

partition does not affect the relative parity of two multi-colored
subgraphs in the same similarity class as long as their quotient
graphs are induced by the same partition, where parity is the
property of being odd or even. A similarity class of multicolored subgraphs is balanced if the numbers of odd and
even multi-colored subgraphs in the similarity class are equal.
Otherwise, it is unbalanced. This important property of a
similarity class is regardless of which matrimonial partition
is chosen.
From Figure 3, one knows that the graph in Figure 2a is
odd and the graph in Figure 2b is even, so the similarity class
E1 is balanced. The similarity class E2 is unbalanced as it only
has one multi-colored subgraph.
A “cactus graph” introduced by Lin is a directed connected
graph consisting of one “trunk” and any number of “buds”.
A trunk is a simple directed path with at least one vertex. A
bud consists of one simple directed cycle with at least one
vertex and one additional arc called the bud’s stem which is
incident to one of the cycle’s vertices. A cactus graph is then
a directed connected graph with exactly one trunk and any
non-negative number of buds with the understanding that the
stem of each bud comes out of either a vertex on the trunk
or a vertex on the cycle of another bud in the graph. In this
context a simple directed path graph is a cactus graph with
no buds. Note that the condensation of a cactus graph which
results when all cycles are condensed into vertices is a directed
rooted tree. A cactus graph has a unique vertex called the root
from which there exist directed paths to any other vertices in
the cactus graph.
Figure 4 gives an example of a cactus graph with five buds.

4

3

4
{4}

{3}

{2,6}

{4}

2
{2,6}

{1,5}

2

{3}

1

{1,5}
3

(a) The quotient graph of the graph in Figure 2a.

1

(b) The quotient graph of the graph in Figure 2b.
Fig. 3

Fig. 4: A cactus graph.

C. Algebraic Concepts
The generic rank of a linearly parameterized matrix
X
M (p) =
gk pk hk

(6)

k∈q

denoted by grk M , is the maximum rank of M that can be
achieved as p varies over IRq . It is generic in the sense that it is
achievable by any p in the complement of an algebraic variety
in IRq . Generalizing the standard notion of irreducibility, a
matrix pair (A, B) is said to be irreducible if there is no
permutation matrix Π bringing (A, B) into the form


 
A1 0
0
−1
ΠAΠ =
, ΠB =
A2 A3
B1
where A1 is an n1 × n1 block, B1 is an (n − n1 ) × m block,
1 ≤ n1 < n.
Proposition 1: [3] A matrix pair (A, B) is irreducible if and
only if the graph of (A, B) has a spanning forest rooted at the
m vertices with labels n + 1 to n + m.
Although Proposition 1 was initially developed for matrix
pairs satisfying the unitary assumption, the same proof applies
to all linearly parameterized matrix pairs without change.
Therefore a proof of Proposition 1 will not be given here.
III. M AIN R ESULT
The following classical result characterizes the structural
controllability of linearly parameterized matrix pairs satisfying
the unitary assumption.
Proposition 2: [1]–[3] Let (A, B) be a linearly parameterized matrix pair which satisfies the unitary assumption. The
following statements are equivalent.
(i) The pair (A, B) is structurally controllable.
(ii) grk [A B] = n and (A, B) is irreducible.
(iii) The graph of (A, B) has a spanning subgraph which is
a disjoint union of m cactus graphs rooted at the m vertices
with labels n + 1 to n + m, respectively.
The following theorem, which is the main result of this
paper, shows how the graphical condition in Proposition 2
changes when the unitary assumption is relaxed to the binary
assumption.

Theorem 1: Let (A, B) be a linearly parameterized matrix
pair which satisfies the binary assumption. The following
statements are equivalent.
(i) The pair (A, B) is structurally controllable.
(ii) grk [A B] = n and (A, B) is irreducible.
(iii) The graph of (A, B) has an unbalanced similarity class of
multi-colored subgraphs and has a spanning subgraph which
is a disjoint union of m cactus graphs rooted at the m vertices
with labels n + 1 to n + m, respectively.
(iv) The graph of (A, B) has an unbalanced similarity class
of multi-colored subgraphs and has a spanning forest rooted
at the m vertices with labels n + 1 to n + m.
When subject to the unitary assumption, Theorem 1 reduces
to Proposition 2. To understand why this is so, let G be
the graph of a matrix pair (A, B) which satisfies the unitary
assumption. As no two arcs of G are of the same color, G
has an unbalanced similarity class of multi-colored subgraphs
if and only if G has a multi-colored subgraph, which can be
obtained by removing the stems of all buds in the m cactus
graphs. So condition (iii) in Theorem 1 reduces to condition
(iii) in Proposition 2.
As an example of Theorem 1, the matrix pair given in (5) is
structural controllable because the graph in Figure 1 satisfies
condition (iv).
IV. A NALYSIS
This section focuses on the analysis and proof of Theorem 1,
in which condition (ii) is proved first, followed by condition
(iv) and then condition (iii).
A. Theorem 1, Condition (ii)
Apparently, if a linearly parameterized matrix pair (A, B) is
structural controllable, (A, B) is irreducible and grk [A B] =
n. We will prove the converse. To do that, some concepts and
certain result from [39] are summarized as they apply to the
proof. It is worth pointing out that the concepts and the result
in [39] do not require the binary assumption.
Suppose S = {i1 , i2 , . . . , ik } ⊂ q with i1 < i2 < · · · < ik .
Let matrices GS , HS and PS be
 
hi1
hi2 


 
GS , gi1 gi2 . . . gik , HS ,  . 
 .. 
hik
PS , diag {pi1 , pi2 , . . . , pik }
If S = ∅, GS , HS and PS are each the 0 × 0 matrix. The
complement of S in q P
is denoted by q − S. Note that the
linear parameterization i∈q gi pi hi is exactly Gq Pq Hq .
The transfer matrix of {Gq , Hq }, denoted by T , is a block
matrix defined as

hi1 gj , i, j ∈ q
Ti,j =
hi2 ,
i ∈ q, j = 0
where Ti,j is the ijth block of T , gj ∈ IRn , hi1 ∈ IR1×n
and hi2 ∈ IR1×m . The transfer graph of {Gq , Hq }, written
T, is the graph of the transfer matrix T and is defined to be a

directed graph with q + 1 vertices labeled 0, 1, . . . , q and an
arc from vertex j to vertex i whenever Ti,j is nonzero. The
following proposition is derived from Theorem 1 in [39] with
constant matrices A0 = 0 and B0 = 0. It is applicable to any
linearly parameterized matrix pair with or without the binary
assumption.
Proposition 3: [39] A linearly parameterized matrix pair
(A, B) given by (4) is structurally controllable if and only if

Lemma 2: For a linearly parameterized matrix M given by
(6),
grk M = min (rank GS + rank Hq−S )

min (rank GS + rank Hq−S ) = n

grk M ≥ rank GI HI = |I|

and the transfer graph of {Gq , Hq } has a spanning tree rooted
at vertex 0.
In addition to Proposition 3, three lemmas are needed to
prove condition (ii) in Theorem 1. More specifically, Lemma 2
and Lemma 3 draw a connection between Proposition 3 and
condition (ii). The following concepts and Lemma 1 are the
key ideas for proving Lemma 2. Among the three lemmas,
Lemma 1 and Lemma 2 hold without the binary assumption,
but Lemma 3 needs the binary assumption.
Suppose we are given two real matrices
 
h1




h2 
Gn1 ×k = g1 g2 . . . gk , Hk×n2 =  . 
 .. 
hk
Let k , {1, 2, . . . , k}. Let P , {(gi , hi ) | i ∈ k} be the set of
k pairs of vectors. For I ⊂ k, a nonempty subset {(gi , hi ) | i ∈
I} ⊂ P is jointly independent if {gi | i ∈ I} and {hi | i ∈ I}
are both linearly independent sets. That is,
rank GI = rank HI = |I|
where |I| is the cardinality of I, i.e., the number of elements in
I. Then I is called a jointly independent index set of {G, H},
{G, H}.
denoted by I
Lemma 1: For a linearly parameterized matrix M given by
(6),
max

{Gq ,Hq }

|I| = min (rank GS + rank Hq−S )
S⊂q

Proof of Lemma 1: Let M1 = {q, J1 } and M2 = {q, J2 }
be two finite matroids, where q is the ground set; J1 is the
family of the independent sets of q defined by the linear
independence relation of {gi | i ∈ q}, i.e., S1 ∈ J1 if and
only if {gi | i ∈ S1 } is a linearly independent set; J2 is the
family of the independent sets of q defined by the linear
independence relation of {hi | i ∈ q}, i.e., S2 ∈ J2 if and
only if {hi | i ∈ S2 } is a linearly independent set. Let r1
and r2 be the rank functions of M1 and M2 , respectively.
Naturally, for ∀S1 ⊂ q, r1 (S1 ) = rank GS1 , and for ∀S2 ⊂ q,
r2 (S2 ) = rank HS2 . By the matroid intersection theorem [42],
max |I| = min (r1 (S) + r2 (q − S))

I∈J1 ∩J2

S⊂q

That is,
I

max

{Gq ,Hq }

|I| = min (rank GS + rank Hq−S )
S⊂q

Therefore, Lemma 1 is true.

Proof of Lemma 2: Let I be a jointly independent index set
of {Gq , Hq } with the maximum cardinality. Let pi = 1 if
i ∈ I and pi = 0 if i ∈
/ I. Then M = GI HI . As rank GI =
rank HI = |I|, rank GI HI = |I|. So

(7)

S⊂q

I

S⊂q

For ∀S ⊂ q, Gq Pq Hq = GS PS HS + Gq−S Pq−S Hq−S . So
rank Gq Pq Hq ≤ rank GS PS HS + rank Gq−S Pq−S Hq−S
≤ rank GS + rank Hq−S
holds for ∀p ∈ IRq and ∀S ⊂ q. It follows by varying p over
IRq on the left side of the inequality and by varying S over
the power set of q on the right side of the inequality that
grk M ≤ min (rank GS + rank Hq−S )
S⊂q

By Lemma 1, |I| = min (rank GS + rank Hq−S ). So
S⊂q

grk M = |I| = min (rank GS + rank Hq−S )
S⊂q

Therefore, Lemma 2 is true.
Corollary 1: For real matrices Gn1 ×k and Hk×n2 ,
rank GH ≤

I

max

{G,H}

|I|

Proof of Corallary 1: By Lemma 1 and Lemma 2,
grk GPk H =

I

max

{G,H}

|I|

So
rank GH = rank GIH ≤ grk GPk H
=

I

max

{G,H}

|I|

Therefore, Corallary 1 is true.
Corollary 1 gives a tighter upper bound on rank GH than
min {rank G, rank H}.
The concept of “line graph” is useful for proving Lemma 3.
The line graph of a given structural controllability graph G,
written L(G), is a directed graph that has one vertex for each
arc of G and has an arc from vertex abk1 to vertex bck2 if
G has arcs (a, b)k1 and (b, c)k2 . That is, each arc in L(G)
represents a length-two directed path in G.
Figure 5 gives an example of a structural controllability
graph and its line graph.
Lemma 3: Let (A, B) be a linearly parameterized matrix
pair given by (4), which satisfies the binary assumption. If
(A, B) is irreducible, the transfer graph of {Gq , Hq } has a
spanning tree rooted at vertex 0.
Proof of Lemma 3: For clarity, let vi denote vertex i in the
graph G of (A, B) and let wi denote vertex i in the transfer
graph T of {Gq , Hq }. Let B , {i ∈ q | hi2 6= 0}. In other
words, pi appears in B if and only if i ∈ B. By definition,
there is an arc in T from vertex w0 to vertex wi for each
i ∈ B. For i, j ∈ q, there is an arc in T from wi to wj if
Tj,i = hj1 gi 6= 0. As hj1 and gi are binary vectors, hj1 gi 6= 0

1

1

111
1

2

212

2

211

3

323

3
(a) G

(b) L(G)
Fig. 5

if and only if ∃ k ∈ n such that the kth entry of hj1 is one
and the kth entry of gi is also one. So T has an arc from wi
to wj if and only if G has an arc of color i pointing toward
vk and an arc of color j leaving vk .
b be the subgraph of T induced by vertices w1 , w2 ,
Let T
. . . , wq . Remember that the line graph L(G) has one vertex
for each arc of G. Let π be the partition of the vertices of
L(G) such that the vertices for the arcs of G in the same
color are in the same subset of the partition. Obviously, the
quotient graph L(G)/π has q vertices. For each i ∈ q, let ui
denote vertex i in L(G)/π, which corresponds to the arcs of
b are isomorphic with the
G with color i. Then L(G)/π and T
b
bijection that maps vertex ui in L(G)/π to vertex wi in T.
If (A, B) is irreducible, by Proposition 1, G has a spanning
forest rooted at the m vertices vn+1 , vn+2 , . . . , and vn+m . So
L(G) has a spanning forest rooted at the vertices for the arcs
of G leaving vn+1 , vn+2 , . . . , or vn+m . The isomorphism of
b implies that T
b has a spanning forest rooted at
L(G)/π and T
the vertices in the set {wi | i ∈ B}. Since the transfer graph T
has an arc from w0 to wi for each i ∈ B, T has a spanning
tree rooted at w0 .
Proof of Theorem 1, condition (ii): Apparently, (i) =⇒ (ii).
If (ii) is true, by Lemma 2 and Lemma 3,
min (rank GS + rank Hq−S ) = n
S⊂q

and the transfer graph of {Gq , Hq } has a spanning tree rooted
at vertex 0. By Proposition 3, (i) is true. So (i) ⇐⇒ (ii).
B. Theorem 1, Condition (iv)
Two lemmas are needed to prove condition (iv). Lemma 4
implies that the balance or unbalance of a similarity class
of multi-colored subgraphs is an intrinsic property, regardless
of which matrimonial partition is chosen. It facilitates the
understanding of Lemma 5, which directly proves the first
half of condition (iv).
For the proofs of Lemma 4 and Lemma 5, some bases
of permutation and determinant are needed. Let Sn be the
set of all permutations of the set n. Let σ ∈ Sn be one
such permutation which maps i ∈ n to σ(i) ∈ n. σ is odd
(respectively, even) if σ(1), σ(2), . . . , σ(n) can be transformed
into 1, 2, . . . , n by an odd (respectively, even) number of
two-element swaps. The signature of σ, denoted by sgn (σ),
takes value from {1, −1} such that sgn (σ) = 1 if σ is even,

and sgn (σ) = −1 if σ is odd. Each permutation in Sn can
be decomposed into the product of disjoint cycles. Let c be
the number of disjoint cycles that σ can be decomposed into,
then σ is odd (respectively, even) if n − c is odd (respectively,
even). The composition of two permutations with the same
parity (respectively, opposite parities) is an even (respectively,
odd) permutation.
One definition of the determinant of an n × n square matrix
M is
Y
X
sgn (σ)
mi,σ(i)
(8)
det M =
σ∈Sn

i∈n

where mi,j is the ijth entry of M .
If Mn×n is linearly parameterized as given by (6), the graph
of M , written GM , is a directed graph with n vertices labeled
1 to n and an arc (j, i)k if the ijth entry in M contains pk . So
GM is exactly the subgraph induced in the graph of the pair
(M, 0) by the n vertices with labels 1 to n. With the binary
assumption, each entry of M is either zero, one parameter or
the sum of distinct parameters. After the products of entries
in (8) are expanded, each term in det M is a signed product
of n parameters. As no two of the n parameters in a term
are taken from the same row or the same column of M , each
term in det M corresponds to a spanning subgraph of GM with
n arcs, which is a disjoint union of finite number of simple
directed cycle graphs. The following proposition is derived
from Theorem 2 in [43] and will be used to prove Lemma 4.
Proposition 4: [43] Let M be an n × n linearly parameterized matrix satisfying the binary assumption, whose graph is
denoted by GM . The sign of a term in det M is positive if
n − c is even, and is negative if n − c is odd, where c is the
number of simple directed cycle graphs in the corresponding
spanning subgraph of GM .
For an n×n linearly parameterized matrix M which satisfies
the binary assumption, a term in det M is valid if it contains
n distinct parameters. Since det M is a multilinear function of
p1 , p2 , . . . , pq , only valid terms appear in the final expression
of det M . That is,
X
Y
det M =
aC
pk
(9)
C⊂q
|C|=n

k∈C

where aC ∈ [−n! , n! ] is the integer coefficient of the product
of the n distinct parameters labeled by elements of C.
Let G be the graph of a linearly parameterized matrix pair
(A, B) which satisfies the binary assumption. By replacing any
m columns, such as columns t1 , t2 , . . . , tm , of the partitioned
matrix [A B] with 0, we get another n × (n + m) matrix
b is then
b B].
b The graph of the pair (A,
b B),
b denoted by G,
[A
a spanning subgraph of G which results when all the arcs
leaving vertices t1 , t2 , . . . , or tm are removed from G. Let
M be the n × n subarray obtained by deleting columns t1 , t2 ,
. . . , tm of [A B]. Each valid term in det M has n distinct
parameters and no two of them are taken from the same row
b B].
b So each valid term in det M
or the same column of [A
b with n arcs in n
corresponds to a spanning subgraph of G
distinct colors and with no two arcs pointing toward the same
vertex or leaving the same vertex, which is a multi-colored
subgraph of G with sink vertices t1 , t2 , . . . , tm . Therefore,

each valid term in the determinant of an n × n subarray of
[A B] corresponds to a multi-colored subgraph of G. Valid
terms which are in the determinant of the same subarray and
which contain the same n distinct parameters correspond to
multi-colored subgraphs of G in the same similarity class.
Lemma 4: Let G be the graph of a linearly parameterized
matrix pair (A, B) which satisfies the binary assumption. The
relative parity of two multi-colored subgraphs of G in the
same similarity class remains unchanged regardless of which
matrimonial partition induces their quotient graphs.
Proof of Lemma 4: Suppose G has a similarity class E of
multi-colored subgraphs with sink vertices t1 , t2 , . . . , tm . Let
L , {1, 2, . . . , n + m} − {t1 , t2 , . . . , tm }
Note that |L| = n. Let M be the n × n subarray obtained by
deleting columns t1 , t2 , . . . , tm of [A B]. Let
f0 : n → L
be the bijection such that for each i ∈ n, the ith column of
M is taken from the f0 (i)th column of [A B]. Let π be the
matrimonial partition that induces the quotient graphs of all
multi-colored subgraphs in E. For each i ∈ L ∩ {n + 1, n +
2, . . . , n+m}, vertex i is a source vertex but not a sink vertex.
So vertex i shares a subset of π with a sink vertex, denoted
by vertex tiπ . Let
fπ : L → n
be the bijection such that fπ (i) = tiπ if i ∈ L ∩ {n + 1, n +
2, . . . , n + m} and fπ (i) = i if i ∈ L ∩ n.
Rearrange columns of M to get another n × n matrix
M such that for each i ∈ n, the ith column of M is the
fπ (f0 (i))th column of M . Let z1 be a valid term in det M ,
which corresponds to a multi-colored subgraph S1 in E. Let
σ1 ∈ Sn be the permutation associated with term z1 . That is,
each parameter in z1 is taken from a location in the ith row
and the σ1 (i)th column of M for some i ∈ n. So the sign of
z1 is sgn (σ1 ). Term z1 naturally pairs with a valid term in
det M , denoted by z̄1 . To be precise, if a parameter in z1 is
taken from the location in the ith row and the σ1 (i)th column
of M , z̄1 has the same parameter taken from the location in the
ith row and the fπ (f0 (σ1 (i)))th column of M . Let σ̄1 ∈ Sn
be the permutation associated with term z̄1 . So σ̄1 = fπ f0 σ1
and the sign of z̄1 is sgn (σ̄1 ). As fπ f0 ∈ Sn ,
sgn (σ̄1 ) = sgn (fπ f0 ) sgn (σ1 )
Let c1 be the number of simple directed cycle graphs in
the quotient graph S1 /π. Let Q1 be the subgraph of S1 /π
obtained by removing all the isolated vertices, if any, from
S1 /π. So Q1 is the disjoint union of c1 simple directed cycle
graphs. It can be checked that Q1 has n vertices and n arcs in
n distinct colors. In fact, Q1 is exactly the spanning subgraph
of GM that term z̄1 in det M corresponds to. By Proposition 4,
sgn (σ̄1 ) = 1 if n − c1 is even, and sgn (σ̄1 ) = −1 if n − c1
is odd. It means that c1 is even if sgn (σ̄1 ) = (−1)n , and c1
is odd if sgn (σ̄1 ) = −(−1)n . So S1 is even if
sgn (fπ f0 ) sgn (σ1 ) = (−1)n

and S1 is odd if
sgn (fπ f0 ) sgn (σ1 ) = −(−1)n
Let z2 be another valid term in det M , which corresponds
to a multi-colored subgraph S2 in E. Let σ2 ∈ Sn be the
permutation associated with term z2 . So the sign of z2 is
sgn (σ2 ). Similarly, S2 is even if
sgn (fπ f0 ) sgn (σ2 ) = (−1)n
and S2 is odd if
sgn (fπ f0 ) sgn (σ2 ) = −(−1)n
Therefore, the relative parity of S1 and S2 in E only depends
on the relative sign of z1 and z2 . If the two valid terms have the
same sign, their corresponding multi-colored subgraphs have
the same parity, and vice versa.
Lemma 5: For a linearly parameterized matrix pair (A, B)
which satisfies the binary assumption,
grk [A B] = n
if and only if the graph of (A, B) has an unbalanced similarity
class of multi-colored subgraphs.
Proof of Lemma 5: When the binary assumption holds,
grk [A B] = n if and only if there exists an n × n subarray of
[A B], written M , such that grk M = n. By (9), grk M = n
if and only if ∃ C ⊂ q, |C| = n such that aC 6= 0. As each valid
term in det M is a signed product of n distinct parameters,
a
QC 6= 0 if and only if the number of positive valid
Q terms
k∈C pk and the number of negative valid terms −
k∈C pk
are
not
equal.
By
the
proof
of
Lemma
4,
a
positive
valid
term
Q
Q
k∈C pk and a negative valid term −
k∈C pk correspond to
two multi-colored subgraphs with opposite parities in the same
similarity class. So aC 6= 0 if and only if the similarity class is
unbalanced. Therefore, grk [A B] = n if and only if the graph
of (A, B) has an unbalanced similarity class of multi-colored
subgraphs.
Proof of Theorem 1, condition (iv): By Lemma 5 and
Proposition 1, (ii) ⇐⇒ (iv).
C. Theorem 1, Condition (iii)
The following lemma makes the proof of condition (iii)
fairly straightforward.
Lemma 6: Let G be a directed graph on n + m vertices.
Then G has a spanning subgraph which is a disjoint union
of m cactus graphs rooted at m distinct vertices if and only
if G has two spanning subgraphs: One is a spanning forest
rooted at the same m vertices; The other is a disjoint union
of m simple directed path graphs and a non-negative number
of simple directed cycle graphs, where the source vertices are
the m root vertices of the cactus graphs.
Note that Lemma 6 has no requirement on the color of arcs.
Proof of Lemma 6: The necessity is obvious. Let us prove
the sufficiency. Let U be a spanning subgraph of G, which
is the disjoint union of m simple directed path graphs and c
simple directed cycle graphs. If c = 0, U is already a disjoint
union of m cactus graphs with no buds. Now assume c > 0.

Let V be the vertex set of G. Let V0 ⊂ V be the set of
vertices in the m simple path graphs of U. Let Vroot ⊂ V0
be the set of source vertices of the m simple path graphs in
U. For each i ∈ c , {1, 2, . . . , c}, let Vi ⊂ V be the set of
vertices in the ith simple cycle graph of U. So
V=

c
[

Vi

i=0

and
Vi ∩ Vj = ∅, i 6= j, i, j ∈ {0, 1, . . . , c}
Since G has a spanning forest rooted at the m vertices in
Vroot , there exists an arc in G from a vertex in V0 to a vertex
in Vi1 for some i1 ∈ c. Otherwise, there is no directed path
to the vertices in V − V0 from one of the root vertices. Let
V01 , V0 ∪ Vi1 . Similarly, there exists another arc in G from
a vertex in V01 to a vertex in Vi2 for some i2 ∈ c − {i1 },
otherwise there is no directed path to the vertices in V − V01
from one of the root vertices. The process continues until one
finds c arcs in G that connect V0 , V1 , . . . , Vc . The addition
of the c arcs to U renders a disjoint union of m cactus graphs
rooted at the m vertices in Vroot .
Proof of Theorem 1, condition (iii): Obviously, (iii) =⇒ (iv).
If the graph G of (A, B) has an unbalanced similarity class
of multi-colored subgraphs, G has at least one multi-colored
subgraph. So a spanning subgraph of G is the disjoint union
of m simple directed path graphs and a non-negative number
of simple directed cycle graphs, where the source vertices are
the m vertices with labels n + 1 to n + m. By Lemma 6, (iv)
=⇒ (iii). Therefore, (iii) ⇐⇒ (iv).
V. C ONCLUSION
This paper extends the graph-theoretic conditions for structural controllability to the class of linearly parameterized
matrix pairs satisfying the binary assumption. As a byproduct
of the analysis, Corollary 1 presents a tighter upper bound
on the rank of matrix product than the minimum rank of the
matrices in the product. If one wants to further extend the
graph-theoretic conditions to all linearly parameterized matrix
pairs, weighted graphs of matrix pairs must be introduced.
To accommodate this, some graphical concepts will have
to be modified accordingly, such as quotient graph, multicolored subgraph, balanced or unbalanced similarity class
of multi-colored subgraphs, and line graph. Some future
research problems are: (1) to find the minimum number of
input required for the structural controllability of a given
linearly parameterized matrix An×n ; (2) to study the structural
controllability of linearly parameterized linear time-varying
systems; (3) to eventually generalize the definition and the
corresponding characterizations of structural controllability to
nonlinear systems for which there is a good understanding of
controllability.
R EFERENCES
[1] C.-T. Lin, “Structural controllability,” IEEE Trans. Automat. Contr.,
vol. 19, no. 3, pp. 201–208, 1974.
[2] R. W. Shields and J. B. Pearson, “Structural controllability of multi-input
linear systems,” Rice University ECE Technical Report, no. TR7502,
1975.

[3] H. Mayeda, “On structural controllability theorem,” IEEE Trans. Automat. Contr., vol. 26, no. 3, pp. 795–798, 1981.
[4] C.-T. Lin, “System structure and minimal structure controllability,” IEEE
Trans. Automat. Contr., vol. 22, no. 5, pp. 855–862, 1977.
[5] S. Hosoe, “Determination of generic dimensions of controllable subspaces and its application,” IEEE Trans. Automat. Contr., vol. 25, no. 6,
pp. 1192–1196, 1980.
[6] J.-M. Dion, C. Commault, and J. Van Der Woude, “Generic properties
and control of linear structured systems: a survey,” Automatica, vol. 39,
no. 7, pp. 1125–1144, 2003.
[7] S. Maza, C. Simon, and T. Boukhobza, “Impact of the actuator failures
on the structural controllability of linear systems: a graph theoretical
approach,” IET Control Theory & Applications, vol. 6, no. 3, pp. 412–
419, 2012.
[8] P. J. Zufiria, L. Úbeda-Medina, C. Herrera-Yagüe, and I. BarrialesValbuena, “Mathematical foundations for efficient structural controllability and observability analysis of complex systems,” Mathematical
Problems in Engineering, vol. 2014, 2014.
[9] A. Olshevsky, “Minimum input selection for structural controllability,”
in Proc. Amer. Control Conf., Chicago, IL, USA, 2015, pp. 2218–2223.
[10] S. Pequito, S. Kar, and A. P. Aguiar, “A framework for structural
input/output and control configuration selection in large-scale systems,”
IEEE Trans. Automat. Contr., vol. 61, no. 2, pp. 303–318, 2016.
[11] S. Poljak, “On the gap between the structural controllability of timevarying and time-invariant systems,” IEEE Trans. Automat. Contr.,
vol. 37, no. 12, pp. 1961–1965, 1992.
[12] C. Hartung, G. Reißig, and F. Svaricek, “Necessary conditions for
structural and strong structural controllability of linear time-varying
systems,” in Proc. 12th Eur. Control Conf., Zurich, Switzerland, 2013,
pp. 17–19.
[13] X. Liu, H. Lin, and B. M. Chen, “Structural controllability of switched
linear systems,” Automatica, vol. 49, no. 12, pp. 3531–3537, 2013.
[14] Y. Pan and X. Li, “Structural controllability and controlling centrality
of temporal networks,” PloS One, vol. 9, no. 4, p. e94998, 2014.
[15] M. Pósfai and P. Hövel, “Structural controllability of temporal networks,” New J. Physics, vol. 16, no. 12, p. 123055, 2014.
[16] M. I. Garcı́a Planas and M. D. Magret, “Structural controllability and
observability of switched linear systems,” in Proc. 20th Int. Conf.
Applied Mathematics, Budapest, Hungary, 2015, pp. 15–21.
[17] B. Hou, X. Li, and G. Chen, “Structural controllability of temporally
switching networks,” IEEE Trans. Circuits Syst. I, vol. 63, no. 10, pp.
1771–1781, 2016.
[18] S. Pequito and G. J. Pappas, “Structural minimum controllability problem for switched linear continuous-time systems,” Automatica, vol. 78,
pp. 216–222, 2017.
[19] C. Rech and R. Perret, “About structural controllability of interconnected
dynamical systems,” Automatica, vol. 27, no. 5, pp. 877–881, 1991.
[20] K. Li, Y. Xi, and Z. Zhang, “G-cactus and new results on structural
controllability of composite systems,” Int. J. Syst. Sci., vol. 27, no. 12,
pp. 1313–1326, 1996.
[21] L. Blackhall and D. J. Hill, “On the structural controllability of networks
of linear systems,” IFAC Proceedings Volumes, vol. 43, no. 19, pp. 245–
250, 2010.
[22] J. F. Carvalho, S. Pequito, A. P. Aguiar, S. Kar, and K. H. Johansson,
“Composability and controllability of structural linear time-invariant
systems: distributed verification,” Automatica, vol. 78, pp. 123–134,
2017.
[23] Y.-Y. Liu, J.-J. Slotine, and A.-L. Barabási, “Controllability of complex
networks,” Nature, vol. 473, no. 7346, pp. 167–173, 2011.
[24] N. J. Cowan, E. J. Chastain, D. A. Vilhena, J. S. Freudenberg, and C. T.
Bergstrom, “Nodal dynamics, not degree distributions, determine the
structural controllability of complex networks,” PloS One, vol. 7, no. 6,
p. e38398, 2012.
[25] J. C. Nacher and T. Akutsu, “Structural controllability of unidirectional
bipartite networks,” Scientific Reports, vol. 3, 2013.
[26] X. Zhang, T. Lv, X. Yang, and B. Zhang, “Structural controllability of
complex networks based on preferential matching,” PloS One, vol. 9,
no. 11, p. e112039, 2014.
[27] H. Yin and S. Zhang, “Minimum structural controllability problems of
complex networks,” Physica A: Statistical Mechanics and its Applications, vol. 443, pp. 467–476, 2016.
[28] S. Sun, Y. Ma, Y. Wu, L. Wang, and C. Xia, “Towards structural
controllability of local-world networks,” Physics Lett. A, vol. 380, no. 22,
pp. 1912–1917, 2016.
[29] X. Liu and L. Pan, “Detection of driver metabolites in the human liver
metabolic network using structural controllability analysis,” BMC Syst.
Biology, vol. 8, no. 1, p. 1, 2014.

[30] X. Liu and L. Pan, “Identifying driver nodes in the human signaling
network using structural controllability analysis,” IEEE/ACM Trans.
Comput. Biol. Bioinformatics, vol. 12, no. 2, pp. 467–472, 2015.
[31] L. Wu, M. Li, J. Wang, and F.-X. Wu, “Minimum steering node set of
complex networks and its applications to biomolecular networks,” IET
Systems Biology, vol. 10, no. 3, pp. 116–123, 2016.
[32] C. Rech, “Robustness of interconnected systems to structural disturbances in structural controllability and observability,” Int. J. Control,
vol. 51, no. 1, pp. 205–217, 1990.
[33] M. A. Rahimian and A. G. Aghdam, “Structural controllability of multiagent networks: robustness against simultaneous failures,” Automatica,
vol. 49, no. 11, pp. 3149–3157, 2013.
[34] B. Wang, L. Gao, Y. Gao, and Y. Deng, “Maintain the structural controllability under malicious attacks on directed networks,” Europhysics
Lett., vol. 101, no. 5, p. 58003, 2013.
[35] M. A. Rahimian and A. G. Aghdam, “Structural controllability of multiagent networks: importance of individual links,” in Proc. Amer. Control
Conf., Washington, DC, USA, 2013, pp. 6871–6876.
[36] S. A. Mengiste, A. Aertsen, and A. Kumar, “Effect of edge pruning
on structural controllability and observability of complex networks,”
Scientific Reports, vol. 5, 2015.
[37] F. Pasqualetti, F. Dörfler, and F. Bullo, “Control-theoretic methods
for cyberphysical security: geometric principles for optimal cross-layer
resilient control systems,” IEEE Control Syst., vol. 35, no. 1, pp. 110–
127, 2015.
[38] S. Weerakkody, X. Liu, S. H. Son, and B. Sinopoli, “A graph-theoretic
characterization of perfect attackability for secure design of distributed
control systems,” IEEE Trans. Control Netw. Syst., vol. 4, no. 1, pp.
60–70, 2017.
[39] J. Corfmat and A. S. Morse, “Structurally controllable and structurally
canonical systems,” IEEE Trans. Automat. Contr., vol. 21, no. 1, pp.
129–131, 1976.
[40] J. L. Willems, “Structural controllability and observability,” Syst. &
Control Lett., vol. 8, no. 1, pp. 5–12, 1986.
[41] B. D. O. Anderson and H.-m. Hong, “Structural controllability and
matrix nets,” Int. J. Control, vol. 35, no. 3, pp. 397–416, 1982.
[42] K. Murota, Matrices and Matroids for Systems Analysis.
Berlin,
Germany: Springer-Verlag, 2010.
[43] C. Coates, “Flow-graph solutions of linear algebraic equations,” IEEE
Trans. Circuit Theory, vol. 6, no. 2, pp. 170–187, 1959.

