# Mathematical Foundations for Efficient Structural Controllability and Observability Analysis of Complex Systems

Authors: Pedro J. Zufiria; Luis Úbeda-Medina; Carlos Herrera-Yagüe; Iker Barriales-Valbuena
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

The relationship between structural controllability and observability of complex systems is studied. Algebraic and graph theoretic tools are combined to prove the extent of some controller/observer duality results. Two types of control design problems are addressed and some fundamental theoretical results are provided. In addition new algorithms are presented to compute optimal solutions for monitoring large scale real networks.


---

## Body

## 1. Introduction

The controllability and observability analysis of dynamical systems has been an active area of research in control theory since the pioneer work of Kalman for the linear time invariant (LTI) case [1]. Since then, progress has been carried out in several directions such as the controllability/observability of a class of nonlinear systems [2–5], some types of fuzzy systems [6, 7], and the structural controllability/observability of LTI systems [8–10], aimed at robust system monitoring.The structural controllability analysis of LTI systems was initially stated by [8]. Such analysis is intended to model those system properties which only rely on the existence or not of dependencies among inputs, outputs, and state variables; the existence of a dependency is reflected in the model by some nonzero system parameter (which multiplies the corresponding coupling term) but does not depend on the specific value of such parameter. In [8] both linear algebraic and graph characterizations of structural controllability are presented, the second one by means of analyzing the associated directed graph which precisely represents the dependencies among state variables and input signals.This correspondence between some properties of system dynamics and the structure of the associated directed network has been analyzed in the context of large scale and distributed control systems [11, 12]. Conversely, the same correspondence has led to the study of complex networks from a control theoretic perspective [13]; there, the analysis of a graph has been identified with the structural controllability of an associated LTI system, where the controllability concept can be accordingly interpreted depending on the nature and meaning of the network under study. In this structural LTI system framework, some specific problems concerning the minimum number of required inputs (which corresponds to the number of required controllers or actuators) to guarantee controllability have attracted the attention of several researchers (see [10–16], where some computational solutions have been provided).The present paper deepens on the relationship between network analysis and the controllability as well as the observability properties of associated dynamical systems. First, the analysis and design of systems regarding their structural properties are formalized. Then, the potential duality between controllability and observability is analyzed in the framework of some design problems, providing new theoretical results which relate both concepts. Finally, properties of maximum matchings (MMs) and strongly connected components (SCCs) are demonstrated, which lead to new computational tools for analyzing complex networks [17–19].The paper is organized as follows. Section2 presents the main results on structural controllability of LTI systems. Two problems concerning the optimal design of the control matrix are addressed in Section 3; there, algebraic and graph theoretic tools are combined, and the corresponding computational algorithms are presented. Section 4 considers the observability problem and theoretically demonstrates several duality results which are confirmed via computational simulations. Some fundamental properties of maximum matchings and strongly connected components of the network are demonstrated in Section 5. The algorithms for computing several controllability and observability related properties in complex networks are presented in Section 6. Finally, concluding remarks are summarized in Section 8.


## 2. Structural Controllability of LTI Systems

This section presents several controllability results for LTI systems of the form(1)x˙=Ax+Bu,
where A∈ℝn×n and B∈ℝn×m are given a priori. This is the case for many engineering problems, where physical restrictions define both the relationship between state variables (matrix A) and the possible location of system actuators (matrix B).First, the classical controllability problem is stated and the need to undertake a structural analysis perspective is motivated. Secondly, some useful results on the structural analysis of matrices are demonstrated; finally, the structural controllability problem is analyzed.


### 2.1. Classical Controllability

Roughly speaking, system (1) is controllable (in the classical sense) when it is possible to lead the system state variable x(t) from any initial point x0 to any arbitrary point x1 in a finite time period.Classical control theory states that system (1) is controllable if and only if the correspondingcontrollability matrix(2)𝒞(A,B)=(B|AB|A2B⋯∣An-1B)
satisfies rank⁡(𝒞)=n (see [1]). Hence, the classical controllability problem can be formulated as a linear algebra rank condition; this implies that, in some practical cases, the problem may be ill-conditioned and too sensitive to potential parameter variations. Hence, the need of performing robust analyses not affected by modelling errors and/or uncertainties motivates the study of structural properties.


### 2.2. Structural Properties

In practice, the elements of matricesA and B may not be precisely known. This leads to the definition ofstructural properties as those which do not change with variations in the nonzero values of the elements of matrices A and B. Structural analysis considers two types of entries in the matrices, zero and nonzero entries, and addresses those properties which are preserved no matter what the exact value of the nonzero entries is, except for a set of their values with zero Lebesgue measure in the parameter space; see [8]; such properties are called generic [9]. Hence, the nonzero entries may be represented by a 1-value (defining then a binary matrix) or, alternatively, the X-symbol. This will allow for a straightforward graphical representation of the system as shown in Section 2.3.


#### 2.2.1. Algebraic Properties: Generic Rank

We introduce here the concept of a matrix generic rank (denoted byrank⁡g), which happens to play an important role in characterizing its structural properties. As mentioned earlier, the generic rank of a matrix A, say rank⁡gA, is the rank of such matrix for all values of its nonzero entries except those that lie in a set of zero measures. We now define some basic concepts aimed to characterize the generic rank of an n×m matrix A (with n≤m unless stated otherwise).Definition 1 ([see 16]).
Ann×m matrix A is of form (t) for some t, 1≤t≤n, if for some k in the range m-t<k≤m, A contains a zero submatrix of order (n+m-t-k+1)×k.Remark 2 ([see 16]).
IfA has form (t), then clearly A has form (j) for t<j≤n.The following lemma will be employed in the proof of Theorem5.Lemma 3.
Given a matrixA, let A′ be a matrix structurally equivalent to A except for a fixed zero of A which has been replaced by an arbitrary nonzero entry in A′. Then, if A is not of form (t), then A′ is not of  form (t).Proof.
From Definition1, we have that, given t, ∀k in the range m-t<k≤m, A does not contain a zero submatrix of order (n+m-t-k+1)×k. Hence, based on the way A′ has been constructed from A, matrix A′ does not contain a zero submatrix of order (n+m-t-k+1)×k either. This means that A′ is not of form (t).We can now state the following theorem which provides an alternative way to define the generic rank of a matrix.Theorem 4 (see [9], Theorem 2.2).
For anyn×m matrix A, it is rank⁡gA=t,(i)
fort=n if and only if A is not form (n),(ii)
for1≤t<n if and only if A is of  form (t+1) but not of  form (t).We end up with the following generic result, which will be useful for structural controllability analysis.Theorem 5.
Given a matrixA, let A′ be a matrix structurally equivalent to A except for a fixed zero of A which has been replaced by an arbitrary entry in A′. Then rank⁡gA′≥rank⁡gA.Proof.
Let us consider the caserank⁡gA=t=n. Then A is not of form (n); considering Lemma 3, this implies that A′ is not of form (n) which is equivalent to rank⁡gA′=t=n. Let us now consider the case rank⁡gA=t<n. Then A is of form (t+1), but not of form (t). Hence A′ is not of form (t), which implies that rank⁡gA′≥t.
(Note that, knowing thatA′ is not of form (t), then if A′ is of form (t+1), then rank⁡gA′=t; and if A′ is not of form (t+1), then rank⁡gA′≥t+1>t=rank⁡gA.)


### 2.3. The Graph Perspective

The matrix binary form suggests a straightforward alternative representation of the system as a graphG:=(V,E), where state variables appear as the nodes (or vertices belonging to set V) and the elements of A are represented by the existence of a link or edge (nonzero entries correspond to an existing link belonging to set E). Concerning matrix B, nonzero entries are reflected as links from an external input to the corresponding node (see Figure 1).Figure 1
Control configuration(A,B) and its graph representation. Squared nodes represent control inputs, yellow nodes are directly controlled, and blue nodes are controlled by other nodes in the network.Several system structural properties can be analyzed by referring to its associated graph; in the following, structural controllability is addressed and we emphasize its alternative analysis via a graph theoretic approach.


### 2.4. Structural Controllability Conditions

In [8] systems of the form (A,b) are analyzed, where column b represents the scalar input influence on the state variables. Structural controllability is analyzed via both matrix and graph theory perspectives. The system (network) is proved to be structurally controllable if and only if all nodes are accessible from the input and the network presents no dilation, which is equivalent to say that the graph is spanned by aninput cactus [8, 10].Structural controllability for multi-input systems defined by a given pair(A,B) was first addressed in [9] by analyzing two properties of matrix [A∣B]: the first one is related to accessibility and the second one (which is rank⁡g[A∣B]) relates to the absence of dilations. Fortunately, the problem can be reduced to solely computing the generic rank of the associated extended controllability matrix.Again, from a graph theory perspective, the system (network) is structurally controllable if and only if there exists a vertex disjoint union of input cacti [10] that covers all the state vertices (see, for instance, [20]).


#### 2.4.1. The Use of Maximum Matchings

In [21] the equivalence between computing the generic rank of a matrix and computing amaximum matching (MM) in G:=(V,E) over the associated bipartite graph (see [15] for details) is indicated (see Figure 2). A matching is any subset of E so that all nodes in V have neither more than one incoming edge nor more than one outgoing edge belonging to the matching. A matching is maximum if there are no other larger matchings (i.e., a matching containing a larger number of edges); note that maximum matchings (MMs) need not be unique. A matching is perfect if all nodes of the network have an incoming edge belonging to the matching (i.e., the number of links belonging to the matching equals the number of nodes in the network). Maximum matchings (MMs) will be considered in detail in the following sections, where it will be shown that the equivalence between generic rank evaluation and the determination of a MM is in accordance with the fact that a MM provides a subgraph which guarantees the absence of dilations.Figure 2
Dynamical system graph and its bipartite representation. Red links represent edges in themaximum matching. Adding control inputs to every right-unmatched node guarantees the controllability matrix to have full rank.In the next section, some control design problems (on the matrixB) are presented, where both the algebraic and the graph theoretic perspectives can still be employed to address them. Again, the computation of MMs will prove to be an efficient step towards their solution.


## 2.1. Classical Controllability

Roughly speaking, system (1) is controllable (in the classical sense) when it is possible to lead the system state variable x(t) from any initial point x0 to any arbitrary point x1 in a finite time period.Classical control theory states that system (1) is controllable if and only if the correspondingcontrollability matrix(2)𝒞(A,B)=(B|AB|A2B⋯∣An-1B)
satisfies rank⁡(𝒞)=n (see [1]). Hence, the classical controllability problem can be formulated as a linear algebra rank condition; this implies that, in some practical cases, the problem may be ill-conditioned and too sensitive to potential parameter variations. Hence, the need of performing robust analyses not affected by modelling errors and/or uncertainties motivates the study of structural properties.


## 2.2. Structural Properties

In practice, the elements of matricesA and B may not be precisely known. This leads to the definition ofstructural properties as those which do not change with variations in the nonzero values of the elements of matrices A and B. Structural analysis considers two types of entries in the matrices, zero and nonzero entries, and addresses those properties which are preserved no matter what the exact value of the nonzero entries is, except for a set of their values with zero Lebesgue measure in the parameter space; see [8]; such properties are called generic [9]. Hence, the nonzero entries may be represented by a 1-value (defining then a binary matrix) or, alternatively, the X-symbol. This will allow for a straightforward graphical representation of the system as shown in Section 2.3.


### 2.2.1. Algebraic Properties: Generic Rank

We introduce here the concept of a matrix generic rank (denoted byrank⁡g), which happens to play an important role in characterizing its structural properties. As mentioned earlier, the generic rank of a matrix A, say rank⁡gA, is the rank of such matrix for all values of its nonzero entries except those that lie in a set of zero measures. We now define some basic concepts aimed to characterize the generic rank of an n×m matrix A (with n≤m unless stated otherwise).Definition 1 ([see 16]).
Ann×m matrix A is of form (t) for some t, 1≤t≤n, if for some k in the range m-t<k≤m, A contains a zero submatrix of order (n+m-t-k+1)×k.Remark 2 ([see 16]).
IfA has form (t), then clearly A has form (j) for t<j≤n.The following lemma will be employed in the proof of Theorem5.Lemma 3.
Given a matrixA, let A′ be a matrix structurally equivalent to A except for a fixed zero of A which has been replaced by an arbitrary nonzero entry in A′. Then, if A is not of form (t), then A′ is not of  form (t).Proof.
From Definition1, we have that, given t, ∀k in the range m-t<k≤m, A does not contain a zero submatrix of order (n+m-t-k+1)×k. Hence, based on the way A′ has been constructed from A, matrix A′ does not contain a zero submatrix of order (n+m-t-k+1)×k either. This means that A′ is not of form (t).We can now state the following theorem which provides an alternative way to define the generic rank of a matrix.Theorem 4 (see [9], Theorem 2.2).
For anyn×m matrix A, it is rank⁡gA=t,(i)
fort=n if and only if A is not form (n),(ii)
for1≤t<n if and only if A is of  form (t+1) but not of  form (t).We end up with the following generic result, which will be useful for structural controllability analysis.Theorem 5.
Given a matrixA, let A′ be a matrix structurally equivalent to A except for a fixed zero of A which has been replaced by an arbitrary entry in A′. Then rank⁡gA′≥rank⁡gA.Proof.
Let us consider the caserank⁡gA=t=n. Then A is not of form (n); considering Lemma 3, this implies that A′ is not of form (n) which is equivalent to rank⁡gA′=t=n. Let us now consider the case rank⁡gA=t<n. Then A is of form (t+1), but not of form (t). Hence A′ is not of form (t), which implies that rank⁡gA′≥t.
(Note that, knowing thatA′ is not of form (t), then if A′ is of form (t+1), then rank⁡gA′=t; and if A′ is not of form (t+1), then rank⁡gA′≥t+1>t=rank⁡gA.)


## 2.2.1. Algebraic Properties: Generic Rank

We introduce here the concept of a matrix generic rank (denoted byrank⁡g), which happens to play an important role in characterizing its structural properties. As mentioned earlier, the generic rank of a matrix A, say rank⁡gA, is the rank of such matrix for all values of its nonzero entries except those that lie in a set of zero measures. We now define some basic concepts aimed to characterize the generic rank of an n×m matrix A (with n≤m unless stated otherwise).Definition 1 ([see 16]).
Ann×m matrix A is of form (t) for some t, 1≤t≤n, if for some k in the range m-t<k≤m, A contains a zero submatrix of order (n+m-t-k+1)×k.Remark 2 ([see 16]).
IfA has form (t), then clearly A has form (j) for t<j≤n.The following lemma will be employed in the proof of Theorem5.Lemma 3.
Given a matrixA, let A′ be a matrix structurally equivalent to A except for a fixed zero of A which has been replaced by an arbitrary nonzero entry in A′. Then, if A is not of form (t), then A′ is not of  form (t).Proof.
From Definition1, we have that, given t, ∀k in the range m-t<k≤m, A does not contain a zero submatrix of order (n+m-t-k+1)×k. Hence, based on the way A′ has been constructed from A, matrix A′ does not contain a zero submatrix of order (n+m-t-k+1)×k either. This means that A′ is not of form (t).We can now state the following theorem which provides an alternative way to define the generic rank of a matrix.Theorem 4 (see [9], Theorem 2.2).
For anyn×m matrix A, it is rank⁡gA=t,(i)
fort=n if and only if A is not form (n),(ii)
for1≤t<n if and only if A is of  form (t+1) but not of  form (t).We end up with the following generic result, which will be useful for structural controllability analysis.Theorem 5.
Given a matrixA, let A′ be a matrix structurally equivalent to A except for a fixed zero of A which has been replaced by an arbitrary entry in A′. Then rank⁡gA′≥rank⁡gA.Proof.
Let us consider the caserank⁡gA=t=n. Then A is not of form (n); considering Lemma 3, this implies that A′ is not of form (n) which is equivalent to rank⁡gA′=t=n. Let us now consider the case rank⁡gA=t<n. Then A is of form (t+1), but not of form (t). Hence A′ is not of form (t), which implies that rank⁡gA′≥t.
(Note that, knowing thatA′ is not of form (t), then if A′ is of form (t+1), then rank⁡gA′=t; and if A′ is not of form (t+1), then rank⁡gA′≥t+1>t=rank⁡gA.)


## 2.3. The Graph Perspective

The matrix binary form suggests a straightforward alternative representation of the system as a graphG:=(V,E), where state variables appear as the nodes (or vertices belonging to set V) and the elements of A are represented by the existence of a link or edge (nonzero entries correspond to an existing link belonging to set E). Concerning matrix B, nonzero entries are reflected as links from an external input to the corresponding node (see Figure 1).Figure 1
Control configuration(A,B) and its graph representation. Squared nodes represent control inputs, yellow nodes are directly controlled, and blue nodes are controlled by other nodes in the network.Several system structural properties can be analyzed by referring to its associated graph; in the following, structural controllability is addressed and we emphasize its alternative analysis via a graph theoretic approach.


## 2.4. Structural Controllability Conditions

In [8] systems of the form (A,b) are analyzed, where column b represents the scalar input influence on the state variables. Structural controllability is analyzed via both matrix and graph theory perspectives. The system (network) is proved to be structurally controllable if and only if all nodes are accessible from the input and the network presents no dilation, which is equivalent to say that the graph is spanned by aninput cactus [8, 10].Structural controllability for multi-input systems defined by a given pair(A,B) was first addressed in [9] by analyzing two properties of matrix [A∣B]: the first one is related to accessibility and the second one (which is rank⁡g[A∣B]) relates to the absence of dilations. Fortunately, the problem can be reduced to solely computing the generic rank of the associated extended controllability matrix.Again, from a graph theory perspective, the system (network) is structurally controllable if and only if there exists a vertex disjoint union of input cacti [10] that covers all the state vertices (see, for instance, [20]).


### 2.4.1. The Use of Maximum Matchings

In [21] the equivalence between computing the generic rank of a matrix and computing amaximum matching (MM) in G:=(V,E) over the associated bipartite graph (see [15] for details) is indicated (see Figure 2). A matching is any subset of E so that all nodes in V have neither more than one incoming edge nor more than one outgoing edge belonging to the matching. A matching is maximum if there are no other larger matchings (i.e., a matching containing a larger number of edges); note that maximum matchings (MMs) need not be unique. A matching is perfect if all nodes of the network have an incoming edge belonging to the matching (i.e., the number of links belonging to the matching equals the number of nodes in the network). Maximum matchings (MMs) will be considered in detail in the following sections, where it will be shown that the equivalence between generic rank evaluation and the determination of a MM is in accordance with the fact that a MM provides a subgraph which guarantees the absence of dilations.Figure 2
Dynamical system graph and its bipartite representation. Red links represent edges in themaximum matching. Adding control inputs to every right-unmatched node guarantees the controllability matrix to have full rank.In the next section, some control design problems (on the matrixB) are presented, where both the algebraic and the graph theoretic perspectives can still be employed to address them. Again, the computation of MMs will prove to be an efficient step towards their solution.


## 2.4.1. The Use of Maximum Matchings

In [21] the equivalence between computing the generic rank of a matrix and computing amaximum matching (MM) in G:=(V,E) over the associated bipartite graph (see [15] for details) is indicated (see Figure 2). A matching is any subset of E so that all nodes in V have neither more than one incoming edge nor more than one outgoing edge belonging to the matching. A matching is maximum if there are no other larger matchings (i.e., a matching containing a larger number of edges); note that maximum matchings (MMs) need not be unique. A matching is perfect if all nodes of the network have an incoming edge belonging to the matching (i.e., the number of links belonging to the matching equals the number of nodes in the network). Maximum matchings (MMs) will be considered in detail in the following sections, where it will be shown that the equivalence between generic rank evaluation and the determination of a MM is in accordance with the fact that a MM provides a subgraph which guarantees the absence of dilations.Figure 2
Dynamical system graph and its bipartite representation. Red links represent edges in themaximum matching. Adding control inputs to every right-unmatched node guarantees the controllability matrix to have full rank.In the next section, some control design problems (on the matrixB) are presented, where both the algebraic and the graph theoretic perspectives can still be employed to address them. Again, the computation of MMs will prove to be an efficient step towards their solution.


## 3. Optimal Design ofB

There are practical situations in which only matrixA is known as a characterization of the system dynamics, and there is no a priori restriction about the structure of matrix B. This can be interpreted as if any state variable can be directly accessed by a control signal. Then, the selection of an appropriate matrix B can be addressed as a design goal.Different optimization criteria can be defined for the design of matrixB. In the following, we formulate two different problems aimed to minimize the control requirements. Both problems can be formulated either in the classical control context (with a specific A matrix) or in the structural analysis framework considered in this paper.


### 3.1. Minimum Number of Required Inputs

The first problem is concerned with minimizing the number of inputs or actuators, independently of the fact that such actuators may need to be connected as an input to more than one state variable.Problem 6.
FindB with a minimum number of columns (inputs or actuators) so that (A,B) is controllable.Note that, since a column ofB may have more than one nonzero entry, the number of inputs may be smaller than the number of states directly accessed by an input (i.e., the number of nonzero rows).Obviously, the solutions to this problem are not unique; and it is straightforward to prove that, given two different solutionsB1 and B2, the number of state variables directly accessed by each of them may be different.The design of an optimalB has not been an important issue in classical control theory since most of the time such matrix is given a priori (or it is restricted to access only a subset of state variables) in real engineering problems.When structural controllability is considered, the main result concerning the minimum number of required inputs is stated in the following theorem.Theorem 7.
Let us consider the LTI system(3)x˙=Ax
and let nc be the minimum number of inputs (c stands for controllers) to make it structurally controllable. Then
(4)nc=max⁡{1,n-rank⁡gA}.Proof.
As stated in [8], the system will be structurally controllable if all its variables are accessible from the inputs and the system presents no dilation. The accessibility condition requires having at least one input to the system, which implies that nc≥1. The condition of no dilation can be expressed as follows:
(5)rank⁡g(A∣B)=n,
where n is the number of state variables in the system. Since
(6)rank⁡gA≤rank⁡g(A∣B)
the structure of the system, described by A, determines the conditions imposed to B to make the system controllable.
GivenA, the problem of finding the minimum number of inputs of the system is thus reduced to finding the minimum number of column vectors forming a matrix B that satisfies (5). To comply with the accessibility condition, we may face two different cases: if rank⁡gA=n, we need B to have at least one column with some nonzero entry; if rank⁡gA<n, the already nonzero matrix B selected to satisfy the no-dilation condition may need to add extra nonfixed values to its column vectors, but either of these operations will not affect the no-dilation condition since it will never reduce rank⁡g(A∣B) as stated in Theorem 5. In other words, the range condition expressed in (5) will determine the minimum number of inputs of the system, regardless of the number of variables/vertices affected by them. This result reduces Problem 6 to the rank analysis of (5).
Therefore,B can be chosen to comply with (5) just by constructing as many independent columns as n-rank⁡gA, keeping in mind that if n-rank⁡gA=0 we need B to have one column. Hence
(7)nc=max⁡{1,min⁡rank⁡g(A∣B)=n{rank⁡gB}}=max⁡{1,n-rank⁡gA}.


#### 3.1.1. Computation ofnc: The Maximum Matching Alternative

A priori, the computation ofnc would rely on calculating the generic rank of matrix A. Hence, only the no-dilation property must be taken into account to compute nc, independently of accessibility issues. This implies that, once a matrix B satisfying the rank condition has been selected, we may only further require changing some of its zero terms to one (without altering its generic rank and nc) to cope with accessibility.Alternatively, the network theory perspective provides a way of determining the value ofnc by the calculation of MMs on the network associated bipartite graph (see [13]). Such MM, denoted by ℳ, need not be unique. Any MM provides a decomposition of the graph into paths and cycles; it can be proved that nc is the number of right-unmatched vertices of ℳ (note also that nc=|V|-|ℳ|) and such value does not depend on the specific ℳ that we may have found. Note that any MM only takes into account the no-dilation property and it does not provide information about node accessibility; equivalently, once a set of control inputs has been connected to the right-unmatched nodes, in order to complete the control configuration, we may require adding some newwires from any input(s) to the nonaccessible nodes, without altering the number of required inputs, nc (see dashed line in Figure 3).Figure 3
Adding inputs to every right-unmatched node might leave inaccessible nodes (grey in the figure). To overcome this problem, one may either add wirings (dashed line) from any existing input or include new dedicated inputs (u2).The computation of differentℳs has been analyzed in [14, 15].


### 3.2. Minimum Number of Directly Controlled States (or Dedicated Inputs)

The second optimization problem associated with matrixB is concerned with the minimum number of states that have to be directly controlled with an input signal.Problem 8.
FindB with a minimum number of columns so that each column of B has only one nonzero entry (i.e., it represents adedicated input) and (A,B) is controllable.In this case, the number of dedicated inputsndc is exactly the same as the number of states directly accessed by an input. For example, in Figure 3, two states have to be directly accessed; hence, two dedicated inputs are required.


#### 3.2.1. Computation ofndc: Again the Maximum Matching Alternative

In [10], Problem 8 has been formalized by considering a graph theoretic perspective. In fact, ndc is equal to the minimum number of disjoint state cacti that span the network. As stated there, ndc can be indirectly computed by resorting to the relationship between graph cacti decompositions and the more easily computable maximum matchings. One must remember that a MM provides an alternative decomposition of the graph into paths and cycles. Unfortunately, the accessibility information from right-unmatched nodes to cycles is lost in a MM. Hence further analysis is required, where the relationship between the information provided by the MM and the graph strongly connected components (SCCs) becomes crucial.In [10] it is shown that the minimum number of dedicated inputs ndc is given by
(8)ndc=nc+βc-αc,
where nc again is the number of right-unmatched vertices with respect to the found maximum matching ℳ, βc is the number of nontop linked strongly connected components (SCC), and αc is the so-called maximum assignability index of the network (to be explained below).Each MMℳ found provides a set of right-unmatched nodes that are assigned an external control input. (As mentioned earlier, although the set of right-unmatched vertices may change from one MM to another, its size nc does not depend on the specific MM ℳ found.) Concerning the cycles provided by the matching, some of them may be accessible from a control input and some others may not. Since this accessibility information is not provided by the matching, further analysis is required, knowing that the nonaccessible cycles can only show up within the nontop linked SCCs, in order to determine βc-αc.LetS be the set of all SCCs and let Snt⊂S be the set of all nontop linked SCCs (|Snt|=βc). Then each specific ℳ defines a partition in Snt=Sntru(ℳ)⊔Sntrm(ℳ) (where ⊔ stands for the disjoint union of sets) so that elements of Sntru(ℳ)⊂Snt contain vertices which belong to the set of right-unmatched (ru) vertices provided by ℳ; one can interpret that the elements of Sntru(ℳ) are directly assigned an external control by ℳ so that their accessibility is guaranteed. In this context, the meaning of αc as the maximum assignability index of the network is formally stated by
(9)αc=max⁡ℳ|Sntru(ℳ)|.
On the other hand, the elements of Sntrm(ℳ)=Snt(ℳ)∖Sntru(ℳ) do not contain any of the right-unmatched vertices provided by ℳ; hence, additional dedicated input(s) (equivalent to awiring from any input(s) in the minimum number of required inputs problem) to at least one node belonging to each one of such elements will be required to complete full node accessibility [13]. If dedicated inputs were to be employed to implement such specific matching and associated wiring, the total number of inputs would be
(10)ndc(ℳ)=nc+nwc(ℳ),
where nwc(ℳ) stands for the number of additional wires required. Hence, Problem 8 can be formulated as finding a MM ℳ* which minimizes nwc(ℳ). Since the number of required wires also satisfies nwc(ℳ)=|Sntrm(ℳ)|=βc-|Sntru(ℳ)|, we have that
(11)nw*=nwc(ℳ*)=min⁡ℳnwc(ℳ)=βc-max⁡ℳ|Sntru(ℳ)|=βc-αc.
Since βc is solely determined by the network topology (being independent of the obtained ℳ), the solution of Problem 8 requires the computation of αc (by solving a maximization problem over all possible ℳs).


## 3.1. Minimum Number of Required Inputs

The first problem is concerned with minimizing the number of inputs or actuators, independently of the fact that such actuators may need to be connected as an input to more than one state variable.Problem 6.
FindB with a minimum number of columns (inputs or actuators) so that (A,B) is controllable.Note that, since a column ofB may have more than one nonzero entry, the number of inputs may be smaller than the number of states directly accessed by an input (i.e., the number of nonzero rows).Obviously, the solutions to this problem are not unique; and it is straightforward to prove that, given two different solutionsB1 and B2, the number of state variables directly accessed by each of them may be different.The design of an optimalB has not been an important issue in classical control theory since most of the time such matrix is given a priori (or it is restricted to access only a subset of state variables) in real engineering problems.When structural controllability is considered, the main result concerning the minimum number of required inputs is stated in the following theorem.Theorem 7.
Let us consider the LTI system(3)x˙=Ax
and let nc be the minimum number of inputs (c stands for controllers) to make it structurally controllable. Then
(4)nc=max⁡{1,n-rank⁡gA}.Proof.
As stated in [8], the system will be structurally controllable if all its variables are accessible from the inputs and the system presents no dilation. The accessibility condition requires having at least one input to the system, which implies that nc≥1. The condition of no dilation can be expressed as follows:
(5)rank⁡g(A∣B)=n,
where n is the number of state variables in the system. Since
(6)rank⁡gA≤rank⁡g(A∣B)
the structure of the system, described by A, determines the conditions imposed to B to make the system controllable.
GivenA, the problem of finding the minimum number of inputs of the system is thus reduced to finding the minimum number of column vectors forming a matrix B that satisfies (5). To comply with the accessibility condition, we may face two different cases: if rank⁡gA=n, we need B to have at least one column with some nonzero entry; if rank⁡gA<n, the already nonzero matrix B selected to satisfy the no-dilation condition may need to add extra nonfixed values to its column vectors, but either of these operations will not affect the no-dilation condition since it will never reduce rank⁡g(A∣B) as stated in Theorem 5. In other words, the range condition expressed in (5) will determine the minimum number of inputs of the system, regardless of the number of variables/vertices affected by them. This result reduces Problem 6 to the rank analysis of (5).
Therefore,B can be chosen to comply with (5) just by constructing as many independent columns as n-rank⁡gA, keeping in mind that if n-rank⁡gA=0 we need B to have one column. Hence
(7)nc=max⁡{1,min⁡rank⁡g(A∣B)=n{rank⁡gB}}=max⁡{1,n-rank⁡gA}.


### 3.1.1. Computation ofnc: The Maximum Matching Alternative

A priori, the computation ofnc would rely on calculating the generic rank of matrix A. Hence, only the no-dilation property must be taken into account to compute nc, independently of accessibility issues. This implies that, once a matrix B satisfying the rank condition has been selected, we may only further require changing some of its zero terms to one (without altering its generic rank and nc) to cope with accessibility.Alternatively, the network theory perspective provides a way of determining the value ofnc by the calculation of MMs on the network associated bipartite graph (see [13]). Such MM, denoted by ℳ, need not be unique. Any MM provides a decomposition of the graph into paths and cycles; it can be proved that nc is the number of right-unmatched vertices of ℳ (note also that nc=|V|-|ℳ|) and such value does not depend on the specific ℳ that we may have found. Note that any MM only takes into account the no-dilation property and it does not provide information about node accessibility; equivalently, once a set of control inputs has been connected to the right-unmatched nodes, in order to complete the control configuration, we may require adding some newwires from any input(s) to the nonaccessible nodes, without altering the number of required inputs, nc (see dashed line in Figure 3).Figure 3
Adding inputs to every right-unmatched node might leave inaccessible nodes (grey in the figure). To overcome this problem, one may either add wirings (dashed line) from any existing input or include new dedicated inputs (u2).The computation of differentℳs has been analyzed in [14, 15].


## 3.1.1. Computation ofnc: The Maximum Matching Alternative

A priori, the computation ofnc would rely on calculating the generic rank of matrix A. Hence, only the no-dilation property must be taken into account to compute nc, independently of accessibility issues. This implies that, once a matrix B satisfying the rank condition has been selected, we may only further require changing some of its zero terms to one (without altering its generic rank and nc) to cope with accessibility.Alternatively, the network theory perspective provides a way of determining the value ofnc by the calculation of MMs on the network associated bipartite graph (see [13]). Such MM, denoted by ℳ, need not be unique. Any MM provides a decomposition of the graph into paths and cycles; it can be proved that nc is the number of right-unmatched vertices of ℳ (note also that nc=|V|-|ℳ|) and such value does not depend on the specific ℳ that we may have found. Note that any MM only takes into account the no-dilation property and it does not provide information about node accessibility; equivalently, once a set of control inputs has been connected to the right-unmatched nodes, in order to complete the control configuration, we may require adding some newwires from any input(s) to the nonaccessible nodes, without altering the number of required inputs, nc (see dashed line in Figure 3).Figure 3
Adding inputs to every right-unmatched node might leave inaccessible nodes (grey in the figure). To overcome this problem, one may either add wirings (dashed line) from any existing input or include new dedicated inputs (u2).The computation of differentℳs has been analyzed in [14, 15].


## 3.2. Minimum Number of Directly Controlled States (or Dedicated Inputs)

The second optimization problem associated with matrixB is concerned with the minimum number of states that have to be directly controlled with an input signal.Problem 8.
FindB with a minimum number of columns so that each column of B has only one nonzero entry (i.e., it represents adedicated input) and (A,B) is controllable.In this case, the number of dedicated inputsndc is exactly the same as the number of states directly accessed by an input. For example, in Figure 3, two states have to be directly accessed; hence, two dedicated inputs are required.


### 3.2.1. Computation ofndc: Again the Maximum Matching Alternative

In [10], Problem 8 has been formalized by considering a graph theoretic perspective. In fact, ndc is equal to the minimum number of disjoint state cacti that span the network. As stated there, ndc can be indirectly computed by resorting to the relationship between graph cacti decompositions and the more easily computable maximum matchings. One must remember that a MM provides an alternative decomposition of the graph into paths and cycles. Unfortunately, the accessibility information from right-unmatched nodes to cycles is lost in a MM. Hence further analysis is required, where the relationship between the information provided by the MM and the graph strongly connected components (SCCs) becomes crucial.In [10] it is shown that the minimum number of dedicated inputs ndc is given by
(8)ndc=nc+βc-αc,
where nc again is the number of right-unmatched vertices with respect to the found maximum matching ℳ, βc is the number of nontop linked strongly connected components (SCC), and αc is the so-called maximum assignability index of the network (to be explained below).Each MMℳ found provides a set of right-unmatched nodes that are assigned an external control input. (As mentioned earlier, although the set of right-unmatched vertices may change from one MM to another, its size nc does not depend on the specific MM ℳ found.) Concerning the cycles provided by the matching, some of them may be accessible from a control input and some others may not. Since this accessibility information is not provided by the matching, further analysis is required, knowing that the nonaccessible cycles can only show up within the nontop linked SCCs, in order to determine βc-αc.LetS be the set of all SCCs and let Snt⊂S be the set of all nontop linked SCCs (|Snt|=βc). Then each specific ℳ defines a partition in Snt=Sntru(ℳ)⊔Sntrm(ℳ) (where ⊔ stands for the disjoint union of sets) so that elements of Sntru(ℳ)⊂Snt contain vertices which belong to the set of right-unmatched (ru) vertices provided by ℳ; one can interpret that the elements of Sntru(ℳ) are directly assigned an external control by ℳ so that their accessibility is guaranteed. In this context, the meaning of αc as the maximum assignability index of the network is formally stated by
(9)αc=max⁡ℳ|Sntru(ℳ)|.
On the other hand, the elements of Sntrm(ℳ)=Snt(ℳ)∖Sntru(ℳ) do not contain any of the right-unmatched vertices provided by ℳ; hence, additional dedicated input(s) (equivalent to awiring from any input(s) in the minimum number of required inputs problem) to at least one node belonging to each one of such elements will be required to complete full node accessibility [13]. If dedicated inputs were to be employed to implement such specific matching and associated wiring, the total number of inputs would be
(10)ndc(ℳ)=nc+nwc(ℳ),
where nwc(ℳ) stands for the number of additional wires required. Hence, Problem 8 can be formulated as finding a MM ℳ* which minimizes nwc(ℳ). Since the number of required wires also satisfies nwc(ℳ)=|Sntrm(ℳ)|=βc-|Sntru(ℳ)|, we have that
(11)nw*=nwc(ℳ*)=min⁡ℳnwc(ℳ)=βc-max⁡ℳ|Sntru(ℳ)|=βc-αc.
Since βc is solely determined by the network topology (being independent of the obtained ℳ), the solution of Problem 8 requires the computation of αc (by solving a maximization problem over all possible ℳs).


## 3.2.1. Computation ofndc: Again the Maximum Matching Alternative

In [10], Problem 8 has been formalized by considering a graph theoretic perspective. In fact, ndc is equal to the minimum number of disjoint state cacti that span the network. As stated there, ndc can be indirectly computed by resorting to the relationship between graph cacti decompositions and the more easily computable maximum matchings. One must remember that a MM provides an alternative decomposition of the graph into paths and cycles. Unfortunately, the accessibility information from right-unmatched nodes to cycles is lost in a MM. Hence further analysis is required, where the relationship between the information provided by the MM and the graph strongly connected components (SCCs) becomes crucial.In [10] it is shown that the minimum number of dedicated inputs ndc is given by
(8)ndc=nc+βc-αc,
where nc again is the number of right-unmatched vertices with respect to the found maximum matching ℳ, βc is the number of nontop linked strongly connected components (SCC), and αc is the so-called maximum assignability index of the network (to be explained below).Each MMℳ found provides a set of right-unmatched nodes that are assigned an external control input. (As mentioned earlier, although the set of right-unmatched vertices may change from one MM to another, its size nc does not depend on the specific MM ℳ found.) Concerning the cycles provided by the matching, some of them may be accessible from a control input and some others may not. Since this accessibility information is not provided by the matching, further analysis is required, knowing that the nonaccessible cycles can only show up within the nontop linked SCCs, in order to determine βc-αc.LetS be the set of all SCCs and let Snt⊂S be the set of all nontop linked SCCs (|Snt|=βc). Then each specific ℳ defines a partition in Snt=Sntru(ℳ)⊔Sntrm(ℳ) (where ⊔ stands for the disjoint union of sets) so that elements of Sntru(ℳ)⊂Snt contain vertices which belong to the set of right-unmatched (ru) vertices provided by ℳ; one can interpret that the elements of Sntru(ℳ) are directly assigned an external control by ℳ so that their accessibility is guaranteed. In this context, the meaning of αc as the maximum assignability index of the network is formally stated by
(9)αc=max⁡ℳ|Sntru(ℳ)|.
On the other hand, the elements of Sntrm(ℳ)=Snt(ℳ)∖Sntru(ℳ) do not contain any of the right-unmatched vertices provided by ℳ; hence, additional dedicated input(s) (equivalent to awiring from any input(s) in the minimum number of required inputs problem) to at least one node belonging to each one of such elements will be required to complete full node accessibility [13]. If dedicated inputs were to be employed to implement such specific matching and associated wiring, the total number of inputs would be
(10)ndc(ℳ)=nc+nwc(ℳ),
where nwc(ℳ) stands for the number of additional wires required. Hence, Problem 8 can be formulated as finding a MM ℳ* which minimizes nwc(ℳ). Since the number of required wires also satisfies nwc(ℳ)=|Sntrm(ℳ)|=βc-|Sntru(ℳ)|, we have that
(11)nw*=nwc(ℳ*)=min⁡ℳnwc(ℳ)=βc-max⁡ℳ|Sntru(ℳ)|=βc-αc.
Since βc is solely determined by the network topology (being independent of the obtained ℳ), the solution of Problem 8 requires the computation of αc (by solving a maximization problem over all possible ℳs).


## 4. Observability of LTI Systems and Duality Results

We now consider the LTI system defined by(12)x˙=Ax+Bu,y=Cx,
where again A∈ℝn×n, B∈ℝn×m, and C∈ℝp×n are given a priori. This system is said to be observable (in the classical sense) if, for any known input u, the state space initial condition x0 can be determined in finite time by measuring only the output vector y(t).It can be shown that for LTI systems matrixB does not affect the observability property, which only depends on the relationship between matrices A and C. Hence, the observability analysis can be addressed relying on a duality property (see [22] for details).In the following, we addressstructural observability and associated design issues which will provide similar results to the controllability analysis performed earlier. In addition, duality issues are considered when referring to both structural controllability and observability properties.


### 4.1. Observability and Optimal Design ofC

In the same way as for the controllability analysis, there are practical situations, where no restrictions on matrixC exist, so that it can be freely selected. Therefore one can formulate diverse problems concerning the design of optimal C matrices satisfying different minimality requirements.Such matrixC design problems can be related to the previously presented design problems for matrix B, invoking duality. In the following we demonstrate some results concerning the design of both optimal B and C matrices.


### 4.2. Minimum Number of Required Inputs and Outputs

Given the LTI system (12), we state the following result concerning Problem 6 and its dual counterpart.Theorem 9.
Consider system (12), where only matrix A is predefined (i.e., matrices B and C and the corresponding dimensions of u and y can be freely designed); let nc be the minimum number of inputs to make it structurally controllable and let no be the minimum number of outputs (o will stand for observability) to make it structurally observable. Then
(13)nc=no.(This result was empirically noted in [14].)Proof.
By invoking the duality between the observability and controllability concepts [22], the observability analysis of the system defined by matrix A can be performed by studying the controllability of the system defined by AT. Since the structural properties are grounded on the classical ones, determining the minimum number of outputs to guarantee structural observability in a system defined by A is equivalent to determining the minimum number of inputs to guarantee structural controllability of the system defined by AT.
The dual system will be structurally controllable if(14)rank⁡g(ATCT)=n.
And again, the minimum number of inputs for that new system would be
(15)no=max⁡{1,min⁡rank⁡g(AT∣CT)=n{rank⁡gCT}}=max⁡{1,n-rank⁡gAT}.
Since
(16)rank⁡gA=rank⁡gAT
we conclude that
(17)no=max⁡{1,n-rank⁡gAT}=max⁡{1,n-rank⁡gA}=nc.This proof relies only on algebraic properties ofA. An alternative proof can be constructed using graph theoretical results and the duality principle. Based on duality, the observability analysis in a given graph G:=(V,E), with adjacency matrix A, is equivalent to the controllability analysis in a graph whose adjacency matrix is AT; that is, a graph Gd:=(V,E′) with the same set of nodes V and whose links in E′ have the directions of links in E flipped. We call such a graph Gd thedual graph of G.Every MMℳ of G (considered merely as a set of links, neglecting their directions) is also a MM of Gd. Also, ℳ is composed by a disjoint union of paths and cycles, so that the number of required inputs nc is determined by the size of such paths and cycles. Since flipping the directions of links does not change the number and size of those paths and cycles, we have nc=no. The no sensors would be connected to the right-unmatched vertices determined by ℳ in Gd or equivalently to the left-unmatched vertices determined by ℳ in G.Note that this result does not imply that the number of requiredwirings should be the same, since it will depend on the accessibility of the cycles provided by ℳ, which can change from G to Gd (the directions of links do matter when determining accessibility), as illustrated in the following subsection.


### 4.3. Minimum Number of Dedicated Outputs

Given the LTI system (12), we now consider the dual counterpart of Problem 8, that is, the required dedicated outputs for guaranteeing observability.Based on duality it can be shown that the minimum number of dedicated outputs (sensors)ndo is given by
(18)ndo=no+βo-αo,
where no=nc again corresponds to the left-unmatched vertices in G provided by ℳ, βo is the size of the set Snb composed by the nonbottom linked SCCs, and αo is the maximum assignability index of the network (now also referred to as the nonbottom linked SCCs).A parallel reasoning to the one carried out for controllability can be performed for the observability analysis, where the left-unmatched vertices play the role of the previous right-unmatched ones and the nonbottom linked SCCs play the role of the previous nontop linked ones.


### 4.4. Dedicated Inputs versus Dedicated Outputs

It is obvious that, in general,βo need not be equal to βc; by the same way, αo may not be equal to αc. Accordingly, the number of required wirings nwo(ℳ) may be different from nwc(ℳ). Therefore we get the following.Remark 10.
Consider system (12) and let ndc be the minimum number of dedicated inputs to make it structurally controllable, and let ndo be the minimum number of dedicated outputs to make it structurally observable. Then ndc may or may not to be equal to ndo.For instance, ifA=[0100], then ndc=1=ndo, whereas if A=[011000001], then ndc=1≠2=ndo (see Figure 4).Figure 4
The system in the left can be controlled with only one dedicated input. However, its dual system for observability in the right needs an additional wiring to guarantee accessibility.(This result was also empirically discovered in [14].)The difference of value betweenndc and ndo suggests that the relationship between these two quantities can shed some light on a further characterization of the network properties.


## 4.1. Observability and Optimal Design ofC

In the same way as for the controllability analysis, there are practical situations, where no restrictions on matrixC exist, so that it can be freely selected. Therefore one can formulate diverse problems concerning the design of optimal C matrices satisfying different minimality requirements.Such matrixC design problems can be related to the previously presented design problems for matrix B, invoking duality. In the following we demonstrate some results concerning the design of both optimal B and C matrices.


## 4.2. Minimum Number of Required Inputs and Outputs

Given the LTI system (12), we state the following result concerning Problem 6 and its dual counterpart.Theorem 9.
Consider system (12), where only matrix A is predefined (i.e., matrices B and C and the corresponding dimensions of u and y can be freely designed); let nc be the minimum number of inputs to make it structurally controllable and let no be the minimum number of outputs (o will stand for observability) to make it structurally observable. Then
(13)nc=no.(This result was empirically noted in [14].)Proof.
By invoking the duality between the observability and controllability concepts [22], the observability analysis of the system defined by matrix A can be performed by studying the controllability of the system defined by AT. Since the structural properties are grounded on the classical ones, determining the minimum number of outputs to guarantee structural observability in a system defined by A is equivalent to determining the minimum number of inputs to guarantee structural controllability of the system defined by AT.
The dual system will be structurally controllable if(14)rank⁡g(ATCT)=n.
And again, the minimum number of inputs for that new system would be
(15)no=max⁡{1,min⁡rank⁡g(AT∣CT)=n{rank⁡gCT}}=max⁡{1,n-rank⁡gAT}.
Since
(16)rank⁡gA=rank⁡gAT
we conclude that
(17)no=max⁡{1,n-rank⁡gAT}=max⁡{1,n-rank⁡gA}=nc.This proof relies only on algebraic properties ofA. An alternative proof can be constructed using graph theoretical results and the duality principle. Based on duality, the observability analysis in a given graph G:=(V,E), with adjacency matrix A, is equivalent to the controllability analysis in a graph whose adjacency matrix is AT; that is, a graph Gd:=(V,E′) with the same set of nodes V and whose links in E′ have the directions of links in E flipped. We call such a graph Gd thedual graph of G.Every MMℳ of G (considered merely as a set of links, neglecting their directions) is also a MM of Gd. Also, ℳ is composed by a disjoint union of paths and cycles, so that the number of required inputs nc is determined by the size of such paths and cycles. Since flipping the directions of links does not change the number and size of those paths and cycles, we have nc=no. The no sensors would be connected to the right-unmatched vertices determined by ℳ in Gd or equivalently to the left-unmatched vertices determined by ℳ in G.Note that this result does not imply that the number of requiredwirings should be the same, since it will depend on the accessibility of the cycles provided by ℳ, which can change from G to Gd (the directions of links do matter when determining accessibility), as illustrated in the following subsection.


## 4.3. Minimum Number of Dedicated Outputs

Given the LTI system (12), we now consider the dual counterpart of Problem 8, that is, the required dedicated outputs for guaranteeing observability.Based on duality it can be shown that the minimum number of dedicated outputs (sensors)ndo is given by
(18)ndo=no+βo-αo,
where no=nc again corresponds to the left-unmatched vertices in G provided by ℳ, βo is the size of the set Snb composed by the nonbottom linked SCCs, and αo is the maximum assignability index of the network (now also referred to as the nonbottom linked SCCs).A parallel reasoning to the one carried out for controllability can be performed for the observability analysis, where the left-unmatched vertices play the role of the previous right-unmatched ones and the nonbottom linked SCCs play the role of the previous nontop linked ones.


## 4.4. Dedicated Inputs versus Dedicated Outputs

It is obvious that, in general,βo need not be equal to βc; by the same way, αo may not be equal to αc. Accordingly, the number of required wirings nwo(ℳ) may be different from nwc(ℳ). Therefore we get the following.Remark 10.
Consider system (12) and let ndc be the minimum number of dedicated inputs to make it structurally controllable, and let ndo be the minimum number of dedicated outputs to make it structurally observable. Then ndc may or may not to be equal to ndo.For instance, ifA=[0100], then ndc=1=ndo, whereas if A=[011000001], then ndc=1≠2=ndo (see Figure 4).Figure 4
The system in the left can be controlled with only one dedicated input. However, its dual system for observability in the right needs an additional wiring to guarantee accessibility.(This result was also empirically discovered in [14].)The difference of value betweenndc and ndo suggests that the relationship between these two quantities can shed some light on a further characterization of the network properties.


## 5. Properties of Maximum Matchings and Strongly Connected Components

In this section some fundamental results are presented for addressing the practical solution of the two problems presented in Section3. In order to simplify the exposition, the controllability problem will be considered to illustrate the results. Note that the whole reasoning applies also to the observability analysis, which is performed by merely applying the same reasoning to the dual network.As mentioned earlier,nc can be obtained via the computation of a MM. We will see that MMs are also crucial for the computation of ndc together with the properties of the SCCs. In the following some fundamental results concerning the properties of MMs and the network SCCs are presented.


### 5.1. Properties of Maximum Matchings

We begin by stating some properties which characterize the structure of the set of possible MMs; precisely, the construction of a MM from another one by only performing few changes is addressed, which will lead to characterize similarities between different MMs. In order to make the notation easy, the MM, as subgraph ofG:=(V,E), will be defined with ℳ representing their set of links.Given a MMℳ so that one of its right-unmatched nodes in Vru(ℳ) has an incoming link in E, the following results address the possibility of constructing a new MM ℳ′ whose Vru(ℳ′) is obtained by justswapping such node of Vru(ℳ) by another node in Vrm(ℳ).Lemma 11.
Letℳ be a MM and let Vru(ℳ) be the set of right-unmatched nodes of ℳ. Let v1∈Vru(ℳ) be such that there exists a link (v2,v1)∈E (going from some node v2 to v1). Then, there exist a node v3 and a MM ℳ′ such that ℳ′=ℳ⊔{(v2,v1)}∖{(v2,v3)} implying that Vru(ℳ′)=Vru(ℳ)∖{v1}⊔{v3}.Proof.
Let us consider the subgraphG1:=(V,E1) with E1=ℳ⊔{(v2,v1)}. Obviously, E1 must contain some (v2,v3), a second outgoing link from v2 (if not, E1 would become a matching with more links than ℳ, leading to a contradiction with the maximality of ℳ). By removing such link we obtain a new subgraph with the same number of links as ℳ and satisfying again the no-dilation condition (i.e., a new MM), ℳ′=E1⊔(v2,v1)=ℳ⊔(v2,v1)∖(v2,v3) which satisfies Vru(ℳ′)=Vru(ℳ)∖{v1}⊔{v3}.Remark 12.
Note that ifv1∈Vru(ℳ) and there exists ℳ′′ such that v1∉Vru(ℳ′′), then Lemma 11 does apply, implying the existence of ℳ′, where v1 has beenswapped in Vru(ℳ) by another single node to form Vru(ℳ′).Lemma 13.
Letℳ be a MM and let Vrm(ℳ) be the set of right-matched nodes of ℳ. Let v1∈Vrm(ℳ) be such that there exists ℳ′′ with v1∈Vru(ℳ′′). Then, there exist a node vj∈Vru(ℳ)∩Vrm(ℳ′′) and a MM ℳ′ such that Vru(ℳ′)=Vru(ℳ)∖{vj}⊔{v1}.Proof.
Let us consider(v2,v1)∈ℳ, the link right-matching node v1. Note that (v2,v1)∉ℳ′′ since v1∈Vru(ℳ′′). Let us now consider v3≠v1 such that (v2,v3)∈ℳ′′. Note that ℳ′′ must contain such a link; otherwise, ℳ′′⊔{(v2,v1)} would be a valid matching, contradicting ℳ′′ being maximum. If we construct E1=ℳ∖{(v2,v1)}⊔{(v2,v3)}, then we face two possibilities.(1)
Ifv3∈Vru(ℳ), then E1=ℳ′ would be the matching we are looking for such that Vru(ℳ′)=Vru(ℳ)∖{v3}⊔{v1}.(2)
Ifv3∉Vru(ℳ), then E1 would have two incoming links to v3. Let v4 be such that (v4,v3)∈ℳ (note that v4≠v2 since v3≠v1 and (v2,v1)∈ℳ). Let also v5≠v1, v3, such that (v4,v5)∈ℳ′′ (note that such link must exist; otherwise, ℳ′′⊔{(v4,v3),(v2,v1)}∖{(v2,v3)}=ℳ′′⊔(ℳ∖E1) would be a valid matching, leading to a contradiction). We construct E2=E1∖{(v4,v3)}⊔{(v4,v5)}, where again we can have two possibilities: if v5∈Vru(ℳ), then we are done with E2=ℳ′ and Vru(ℳ′)=Vru(ℳ)∖{v5}⊔{v1}. Otherwise, we could apply the same reasoning recursively until some node vj≠v1,v3,v5,… is encountered such that vj∈Vru(ℳ)∩Vrm(ℳ′′) allowing itsswapping with v1.Lemma 14.
Letℳ be a MM and let Vrm(ℳ) be the set of right-matched nodes of ℳ. Let {v1,…,vk}∈Vrm(ℳ) be such that there exists ℳ′′ with v1,…,vk∈Vru(ℳ′′). Then, there exists a set of nodes {v1′,…,vk′}⊂Vru(ℳ∩Vrm(ℳ′′) and a MM ℳ′ such that Vru(ℳ′)=Vru(ℳ)∖{v1′,…,vk′}⊔{v1,…,vk}.Proof.
From the previous Lemma13, we can construct a MM ℳ1 such that Vru(ℳ1)=Vru(ℳ)∖{v1′}⊔{v1} for some v1′∈Vrm(ℳ′′). Applying again the same reasoning of Lemma 13, we can construct a new MM ℳ2 such that Vru(ℳ2)=Vru(ℳ)∖{v1′,v2′}⊔{v1,v2}, where again v2′∈Vrm(ℳ′′) which guarantees that v2′∉{v1,…,vk}. The procedure can be applied repeatedly for each vj to obtain a new ℳj such that Vru(ℳj)=Vru(ℳ)∖{v1′,…vj′}⊔{v1,…,vj} with vj′∈Vrm(ℳ′′) which guarantees that vj′∉{v1,…vk}. When j=k, the desired result holds.These lemmas will allow for an efficient search of appropriate MMs.


### 5.2. Properties of the Elements ofSnt

We now address some properties ofSnt, the set of nontop linked SCCs, from the point of view of their relationship with the different MMs which can be defined in the network.For everyGi∈Snt, let Vi represent the set of its vertices or nodes. For any MM ℳ, let Vi(ℳ)⊆Vi be the set of nodes of Gi having an outgoing link in ℳ. Then we can define Vib(ℳ) and Vio(ℳ) to be a partition of Vi into two subsets: nodes whose outgoing links in ℳ are between nodes of Gi and those whose outgoing links leave Gi, respectively, so that |Vi(ℳ)|=|Vib(ℳ)|+|Vio(ℳ)|≤|Vi|. Note that Viru(ℳ), the set of right-unmatched nodes of Gi for ℳ, satisfies |Viru(ℳ)|=|Vi|-|Vib(ℳ)| (hence |Vio(ℳ)|≤|Viru(ℳ)|).IfViru(ℳ)=∅, all nodes of Gi are right-matched for ℳ and we define Gi∈Sntrm(ℳ). We can then define the following subset of Snt:
(19)Sntrm={Gi∈Snt∣∃ℳ,Gi∈Sntrm(ℳ)}.
We will see that the elements of Sntrm accept a perfect matching; hence, they may end up being inaccessible from any input in a given MM, requiring an additional dedicated input. Therefore, further analysis of this type of subgraphs is required.The following theorem analyzes the existence and similarity among different MMs when focused on the elements ofSntrm.Theorem 15.
IfGi∈Sntrm (equivalently, Gi accepts a perfect matching), then (1)
|Vi(ℳ)|=|Vib(ℳ)|+|Vio(ℳ)|=|Vi| (equivalently, |Vio(ℳ)|=|Viru(ℳ)|) for all ℳ;(2)
given anyℳ, it is possible to construct an alternative ℳ′ so that Vio(ℳ′) is any arbitrary subset of Vio(ℳ) (|Vio(ℳ')| taking the corresponding arbitrary value between 0 and |Vio(ℳ)|) and ℳ′ is the same as ℳ for links not outgoing from nodes of Gi.(In particular, one can construct such a ℳ′ so that Vio(ℳ′)=∅, meaning that Gi∈Sntrm(ℳ′)).Proof.
(1) Let us first consider the existingℳ such that Gi∈Sntrm(ℳ). Then every node of Gi must have an input link belonging to ℳ, necessarily coming from another node of Gi. Therefore, |Vi(ℳ)|=|Vi| so that ℳ defines a perfect matching in Gi; note also that |Vi(ℳ)|=|Vib(ℳ)|, so that all links outgoing from Gi do not belong to ℳ (|Vio(ℳ)|=0). The same can be said for any other ℳ satisfying Gi∈Sntrm(ℳ).
Let nowℳ be an alternative MM so that Gi∉Sntrm(ℳ) (i.e.,1≤|Viru(ℳ)|≤|Vi|). We will show now that |Vio(ℳ)|=|Viru(ℳ)|.
Note that|Vi(ℳ)|=|Vib(ℳ)|+|Vio(ℳ)|=|Vi|-|Viru(ℳ)|+|Vio(ℳ)|. On one hand, if |Vio(ℳ)|<|Viru(ℳ)|, we would have |Vi(ℳ)|<|Vi| and could define ℳ' with the (known existing) perfect matching in Gi so that |Vib(ℳ′)|=|Vi| and |Vio(ℳ′)|=0 which would allow ℳ′ to preserve the same links as ℳ in the rest of the network; this would imply |ℳ′|>|ℳ| leading to a contradiction. On the other hand, if |Vio(ℳ)|>|Viru(ℳ)|, we would have |Vi(ℳ)|>|Vi| leading also to a contradiction.
Therefore|Vio(ℳ)|=|Viru(ℳ)| and |Vi(ℳ)|=|Vi|.
(2) Letℳ be any MM; note that, from 1, |Vi(ℳ)|=|Vi|. We begin by constructing ℳ′ such that |Vio(ℳ′)|=0, in two parts. On one hand, ℳ′ would contain the (known existing) perfect matching in Gi so that |Vi(ℳ′)|=|Vib(ℳ′)|=|Vi|. Since |Vio(ℳ′)|=0, this would allow completing ℳ′ by keeping the same links as ℳ in the rest of the network (satisfying |ℳ′|=|ℳ|).
We can now constructℳ′′ so that Vio(ℳ′′) is any arbitrary subset of Vio(ℳ). Since Vio(ℳ′′)⊂Vib(ℳ′) for each of its nodes, we can remove the (known existing) outgoing link in ℳ′ and restore the corresponding link in ℳ. This again would allow completing ℳ′′ by keeping the same links as ℳ and ℳ′ in the rest of the network.
Finally, note the true equivalence in the theorem statement: for anyGi∈Snt, we have that Gi∈Sntrm if and only if Gi accepts a perfect match. If Gi∈Sntrm(ℳ), we have already seen that ℳ defines a perfect matching in Gi. Alternatively, consider that Gi accepts a perfect match. As shown above, given any ℳ, either Gi∉Sntrm(ℳ) or we can construct ℳ′ such that Gi∈Sntrm(ℳ′).We now formulate a result illustrating the existence of MMs which can make or not, one by one, the elements ofSnt to be right-unmatched.Corollary 16.
LetG1, G2∈Sntrm(ℳ) for some ℳ.(1)
If there existℳ1 and ℳ2 satisfying Sntru(ℳ1)⊇Sntru(ℳ)∪{G1} and Sntru(ℳ2)⊇Sntru(ℳ)∪{G2}, then there may not exist ℳ3 satisfying Sntru(ℳ3)⊇Sntru(ℳ)∪{G1,G2}.(2)
The other way around, if there existsℳ3 satisfying Sntru(ℳ3)⊇Sntru(ℳ)∪{G1,G2}, then there must exist ℳ1 and ℳ2 satisfying Sntru(ℳ1)=Sntru(ℳ3)∖{G2} and Sntru(ℳ2)=Sntru(ℳ3)∖{G1}.Proof.
(1) The first part of the corollary is obvious due to the interdependence of the outgoing links in the elements ofSntrm(ℳ). For instance, let us consider
(20)A=[0100010100000000010100010]
whose graphical representation can be found in Figure 5. There exists ℳ such that G1 is the subgraph gathering nodes {1,2}, and G2 gathers {4,5}. There exist ℳ1 and ℳ2 satisfying Sntru(ℳ1)=Sntru(ℳ)∪{G1} and Sntru(ℳ2)=Sntru(ℳ)∪{G2}, but no ℳ3 satisfying Sntru(ℳ3)=Sntru(ℳ)∪{G1,G2}.
(2) Givenℳ3, such that Sntru(ℳ3)⊇Sntru(ℳ)∪{G1,G2}, then, by Theorem 15, we can construct a new MM (let us call it ℳ1) such that G2∈Sntrm(ℳ1), ℳ1 being the same as ℳ3 for links not outgoing from nodes of G2 (this includes all links involving nodes of G1, since there cannot be links from nodes of G2 to nodes of G1). Therefore Sntru(ℳ1)=Sntru(ℳ3)∖{G2}.
The same reasoning can be applied to justify the existence ofℳ2.Figure 5
G
1 and G2 are interdependent because they cannot both belong to Sntru(ℳ) for any ℳ.We now consider the optimality with respect tondc: a MM ℳ* is optimal if ndc(ℳ*)≤ndc(ℳ) for any other ℳ. The following result provides information about the existence of optimal solutions in a standard form.Corollary 17.
LetGi∈Sntrm; then there exists an optimal ℳ* such that |Viru(ℳ*)|=|Vio(ℳ*)|≤1.Proof.
Let us considerℳ* being optimal and |Viru(ℳ*)|=|Vio(ℳ*)|>1. By Theorem 15, we can construct a new MM (let us call it ℳ*′) such that |Viru(ℳ*′)|=|Vio(ℳ*′)|=1, ℳ*′ being the same as ℳ* for links not outgoing from nodes of Gi. Note that neither ℳ* nor ℳ*′ require a wiring on Gi, and the required wirings in the rest of the network remain unchanged. Hence, invoking (10), we have ndc(ℳ*)=ndc(ℳ*′).Remark 18.
LetGi∈Sntrm and let ℳ* be optimal with |Viru(ℳ*)|=|Vio(ℳ*)|≥1. Let ℳ′ be such that |Viru(ℳ′)|=|Vio(ℳ′)|=0, ℳ′ being the same as ℳ* for links not outgoing from nodes of Gi. Then ℳ′ is not optimal since a new wiring is required and ndc(ℳ′)=ndc(ℳ*)+1.
Nevertheless, there may exist another optimalℳ*′ such that |Viru(ℳ*′)|=|Vio(ℳ*′)|=0, but ℳ*′ should be necessarilydifferent from ℳ* for links not outgoing from nodes of Gi.


### 5.3. Compatibility

We are now ready to state the final results which will determine the steps of the algorithms for searching optimal solutionsℳ*.Definition 19.
LetGi∈Sntrm. We say that Gi istop-assignable if and only if there exists a MM ℳ such that |Vio(ℳ)|=1.Note that we only need to consider top-assignable elements ofGi∈Sntrm in the search for an optimum ℳ*.Definition 20.
LetG1,…,Gk∈Sntrm be top-assignable. We say that {G1,…,Gk} arecompatible if and only if there exists a MM ℳ such that G1,…,Gk∈Sntru(ℳ).By Theorem15 it is equivalent to guarantee that there exists a ℳ′′ such that |Vio(ℳ′′)|=1, i=1,…,k. Note that all unitary sets of the form {Gi} with Gi assignable are also compatible; the definition provides new insights when being particularized for pairs {G1,G2} (i.e., pairwise compatibility implicitly addressed in Corollary 16).We say that{G1,…,Gk} areincompatible if they are not compatible.The following lemma proves a fundamental property of compatibility and incompatibility.Lemma 21.
LetI={1,…,|Sntrm|} so that Sntrm={Gi:i∈I}. Let I1,I2 be two different nonempty subsets of I, such that 𝒢1={Gi:i∈I1} and 𝒢2={Gi:i∈I2} are subsets of Sntrm so that all elements of 𝒢1 are compatible among them and all elements of 𝒢2 are also compatible among them. Let us consider |I1|=k≤l=|I2| without loss of generality. Then, there exists 𝒢3={Gi:i∈I3} compatible such that |I2|≤|I3| and I1⊆I3⊆I1∪I2 (equivalently, 𝒢1⊆𝒢3⊆𝒢1∪𝒢2).Proof.
From the hypotheses, there must exist the following MMs:(i)
ℳ such that |Vio(ℳ)|=0,i∈I1∪I2 (since 𝒢1,𝒢1⊂Sntrm);(ii)
ℳ1 such that |Vio(ℳ1)|=1,i∈I1 (since 𝒢1 is compatible);(iii)
ℳ2 such that |Vio(ℳ2)|=1,i∈I2 (since 𝒢2 is compatible).
Let us consider the subgraphG1,2=G-∪i∈I1∪I2Gi, where all nodes of Gi∈ℳ1∪ℳ2 are removed from G together with the links outgoing from them. Note that ℳ restricted to each Gi,i=I1∪I2 defines a perfect submatching ℳGi on it. Hence, ℳ restricted to G1,2 defines a maximum submatching ℳG12 on it; otherwise, a matching larger than ℳ could be constructed on the whole graph by adding to the new larger submatching the subgraphs Gi,i∈I1∪I2 with their corresponding perfect submatchings.
Let us consider nowℳ1,G1,2 and ℳ2,G1,2, the corresponding submatchings of ℳ1 and ℳ2 on G1,2, respectively. By Theorem 15, all these submatchings are maximum in G1,2 having all size |ℳ|-∑i∈I1∪I2‍|Vi(ℳ)|. By construction ℳ1,G1,2 has k right-unmatched nodes (let us call them vi,i∈I1) each one being the destination of the corresponding link outgoing Gi∈𝒢1; by the same way ℳ2,G1,2 has l right-unmatched nodes (let us call them vi,i∈I2) destination of the links outgoing Gi∈𝒢2 in ℳ2. Let I12=I1-I2; then for all vii∈I12, we have vi∈Vru(ℳ1)∩Vrm(ℳ2), i∈I12, and we can apply Lemma 14 to I12 obtaining I12′ (which satisfies I12′∩I1=∅) and ℳ3 such that Vru(ℳ3)=Vru(ℳ2)∖{vi:i∈I12′}⊔{vi:i∈I12}. Then, we have that, for I3=I2∖I12′∪I12, I1⊂I3 and |I3|≥|I2|. Completing such submatching with the corresponding submatchings, ℳ1,Gi,i∈I1, ℳ2,Gi,i∈I3-I1, and ℳGi,i∈I12′, we would complete the required MM to end the proof.The following corollaries prove some relationships when the sets are modified element by element; they also show that pairwise incompatibility, besides being symmetric, is also a transitive property.Corollary 22.
LetG1,…,Gk,Gk+1∈Sntrm be top-assignable, so that {G1,…,Gk} are compatible and {G1,…,Gk,Gk+1} are incompatible. Then, there exists 1≤j≤k such that {G1,…,Gj-1,Gj+1,…,Gk+1} are compatible.Proof.
Calling𝒢1={G1,…,Gk} and 𝒢2={Gk+1} we only need to apply Lemma 21.Corollary 23.
LetG1,G2,G3∈Sntrm be top-assignable, so that G3 is incompatible with both G1 and G2, respectively. Then G1 and G2 are incompatible.Proof.
Keeping the assumptions, we will considerG1 and G2 to be compatible; then, applying Lemma 21, we know that either {G1,G3} or {G1,G3} must be compatible, which leads to a contradiction.Corollary 24.
LetG1,G2∈Sntrm be top-assignable and incompatible. If G1 is compatible with G3, then G2 is also compatible with G3.Proof.
If we considerG2 and G3 incompatible, the first assumption and the transitivity property would imply G1 and G3 being incompatible, which contradicts the second assumption.Finally, Lemma21 allows for a useful characterization of the set of possible optimal matchings.Theorem 25.
Let𝒢={G1,…,Gk}⊂Sntrm be top-assignable and compatible. Then ∃ℳ* such that |Viru(ℳ*)|=1, for i=1,…,k (i.e., 𝒢⊂Sntru(ℳ*)).Proof.
Let us consider∃ℳ*′ optimal, so that Sntru(ℳ*′)={G1′,…,Gl′}=𝒢′, where obviously k≤l (otherwise ℳ such that 𝒢={G1,…,Gk}⊂Sntru(ℳ) would provide a larger set of right-unmatched components contradicting the optimality of ℳ*′). Then applying Lemma 21, we can construct a new compatible set 𝒢′′={G1′′,G2′′,…,Gl′′} satisfying 𝒢⊂𝒢′′ and |𝒢′′|≥|𝒢′|. Since ℳ′ is optimum, then |𝒢′′|=|𝒢′| and MM ℳ′′ is also optimum, satisfying the theorem statement.


## 5.1. Properties of Maximum Matchings

We begin by stating some properties which characterize the structure of the set of possible MMs; precisely, the construction of a MM from another one by only performing few changes is addressed, which will lead to characterize similarities between different MMs. In order to make the notation easy, the MM, as subgraph ofG:=(V,E), will be defined with ℳ representing their set of links.Given a MMℳ so that one of its right-unmatched nodes in Vru(ℳ) has an incoming link in E, the following results address the possibility of constructing a new MM ℳ′ whose Vru(ℳ′) is obtained by justswapping such node of Vru(ℳ) by another node in Vrm(ℳ).Lemma 11.
Letℳ be a MM and let Vru(ℳ) be the set of right-unmatched nodes of ℳ. Let v1∈Vru(ℳ) be such that there exists a link (v2,v1)∈E (going from some node v2 to v1). Then, there exist a node v3 and a MM ℳ′ such that ℳ′=ℳ⊔{(v2,v1)}∖{(v2,v3)} implying that Vru(ℳ′)=Vru(ℳ)∖{v1}⊔{v3}.Proof.
Let us consider the subgraphG1:=(V,E1) with E1=ℳ⊔{(v2,v1)}. Obviously, E1 must contain some (v2,v3), a second outgoing link from v2 (if not, E1 would become a matching with more links than ℳ, leading to a contradiction with the maximality of ℳ). By removing such link we obtain a new subgraph with the same number of links as ℳ and satisfying again the no-dilation condition (i.e., a new MM), ℳ′=E1⊔(v2,v1)=ℳ⊔(v2,v1)∖(v2,v3) which satisfies Vru(ℳ′)=Vru(ℳ)∖{v1}⊔{v3}.Remark 12.
Note that ifv1∈Vru(ℳ) and there exists ℳ′′ such that v1∉Vru(ℳ′′), then Lemma 11 does apply, implying the existence of ℳ′, where v1 has beenswapped in Vru(ℳ) by another single node to form Vru(ℳ′).Lemma 13.
Letℳ be a MM and let Vrm(ℳ) be the set of right-matched nodes of ℳ. Let v1∈Vrm(ℳ) be such that there exists ℳ′′ with v1∈Vru(ℳ′′). Then, there exist a node vj∈Vru(ℳ)∩Vrm(ℳ′′) and a MM ℳ′ such that Vru(ℳ′)=Vru(ℳ)∖{vj}⊔{v1}.Proof.
Let us consider(v2,v1)∈ℳ, the link right-matching node v1. Note that (v2,v1)∉ℳ′′ since v1∈Vru(ℳ′′). Let us now consider v3≠v1 such that (v2,v3)∈ℳ′′. Note that ℳ′′ must contain such a link; otherwise, ℳ′′⊔{(v2,v1)} would be a valid matching, contradicting ℳ′′ being maximum. If we construct E1=ℳ∖{(v2,v1)}⊔{(v2,v3)}, then we face two possibilities.(1)
Ifv3∈Vru(ℳ), then E1=ℳ′ would be the matching we are looking for such that Vru(ℳ′)=Vru(ℳ)∖{v3}⊔{v1}.(2)
Ifv3∉Vru(ℳ), then E1 would have two incoming links to v3. Let v4 be such that (v4,v3)∈ℳ (note that v4≠v2 since v3≠v1 and (v2,v1)∈ℳ). Let also v5≠v1, v3, such that (v4,v5)∈ℳ′′ (note that such link must exist; otherwise, ℳ′′⊔{(v4,v3),(v2,v1)}∖{(v2,v3)}=ℳ′′⊔(ℳ∖E1) would be a valid matching, leading to a contradiction). We construct E2=E1∖{(v4,v3)}⊔{(v4,v5)}, where again we can have two possibilities: if v5∈Vru(ℳ), then we are done with E2=ℳ′ and Vru(ℳ′)=Vru(ℳ)∖{v5}⊔{v1}. Otherwise, we could apply the same reasoning recursively until some node vj≠v1,v3,v5,… is encountered such that vj∈Vru(ℳ)∩Vrm(ℳ′′) allowing itsswapping with v1.Lemma 14.
Letℳ be a MM and let Vrm(ℳ) be the set of right-matched nodes of ℳ. Let {v1,…,vk}∈Vrm(ℳ) be such that there exists ℳ′′ with v1,…,vk∈Vru(ℳ′′). Then, there exists a set of nodes {v1′,…,vk′}⊂Vru(ℳ∩Vrm(ℳ′′) and a MM ℳ′ such that Vru(ℳ′)=Vru(ℳ)∖{v1′,…,vk′}⊔{v1,…,vk}.Proof.
From the previous Lemma13, we can construct a MM ℳ1 such that Vru(ℳ1)=Vru(ℳ)∖{v1′}⊔{v1} for some v1′∈Vrm(ℳ′′). Applying again the same reasoning of Lemma 13, we can construct a new MM ℳ2 such that Vru(ℳ2)=Vru(ℳ)∖{v1′,v2′}⊔{v1,v2}, where again v2′∈Vrm(ℳ′′) which guarantees that v2′∉{v1,…,vk}. The procedure can be applied repeatedly for each vj to obtain a new ℳj such that Vru(ℳj)=Vru(ℳ)∖{v1′,…vj′}⊔{v1,…,vj} with vj′∈Vrm(ℳ′′) which guarantees that vj′∉{v1,…vk}. When j=k, the desired result holds.These lemmas will allow for an efficient search of appropriate MMs.


## 5.2. Properties of the Elements ofSnt

We now address some properties ofSnt, the set of nontop linked SCCs, from the point of view of their relationship with the different MMs which can be defined in the network.For everyGi∈Snt, let Vi represent the set of its vertices or nodes. For any MM ℳ, let Vi(ℳ)⊆Vi be the set of nodes of Gi having an outgoing link in ℳ. Then we can define Vib(ℳ) and Vio(ℳ) to be a partition of Vi into two subsets: nodes whose outgoing links in ℳ are between nodes of Gi and those whose outgoing links leave Gi, respectively, so that |Vi(ℳ)|=|Vib(ℳ)|+|Vio(ℳ)|≤|Vi|. Note that Viru(ℳ), the set of right-unmatched nodes of Gi for ℳ, satisfies |Viru(ℳ)|=|Vi|-|Vib(ℳ)| (hence |Vio(ℳ)|≤|Viru(ℳ)|).IfViru(ℳ)=∅, all nodes of Gi are right-matched for ℳ and we define Gi∈Sntrm(ℳ). We can then define the following subset of Snt:
(19)Sntrm={Gi∈Snt∣∃ℳ,Gi∈Sntrm(ℳ)}.
We will see that the elements of Sntrm accept a perfect matching; hence, they may end up being inaccessible from any input in a given MM, requiring an additional dedicated input. Therefore, further analysis of this type of subgraphs is required.The following theorem analyzes the existence and similarity among different MMs when focused on the elements ofSntrm.Theorem 15.
IfGi∈Sntrm (equivalently, Gi accepts a perfect matching), then (1)
|Vi(ℳ)|=|Vib(ℳ)|+|Vio(ℳ)|=|Vi| (equivalently, |Vio(ℳ)|=|Viru(ℳ)|) for all ℳ;(2)
given anyℳ, it is possible to construct an alternative ℳ′ so that Vio(ℳ′) is any arbitrary subset of Vio(ℳ) (|Vio(ℳ')| taking the corresponding arbitrary value between 0 and |Vio(ℳ)|) and ℳ′ is the same as ℳ for links not outgoing from nodes of Gi.(In particular, one can construct such a ℳ′ so that Vio(ℳ′)=∅, meaning that Gi∈Sntrm(ℳ′)).Proof.
(1) Let us first consider the existingℳ such that Gi∈Sntrm(ℳ). Then every node of Gi must have an input link belonging to ℳ, necessarily coming from another node of Gi. Therefore, |Vi(ℳ)|=|Vi| so that ℳ defines a perfect matching in Gi; note also that |Vi(ℳ)|=|Vib(ℳ)|, so that all links outgoing from Gi do not belong to ℳ (|Vio(ℳ)|=0). The same can be said for any other ℳ satisfying Gi∈Sntrm(ℳ).
Let nowℳ be an alternative MM so that Gi∉Sntrm(ℳ) (i.e.,1≤|Viru(ℳ)|≤|Vi|). We will show now that |Vio(ℳ)|=|Viru(ℳ)|.
Note that|Vi(ℳ)|=|Vib(ℳ)|+|Vio(ℳ)|=|Vi|-|Viru(ℳ)|+|Vio(ℳ)|. On one hand, if |Vio(ℳ)|<|Viru(ℳ)|, we would have |Vi(ℳ)|<|Vi| and could define ℳ' with the (known existing) perfect matching in Gi so that |Vib(ℳ′)|=|Vi| and |Vio(ℳ′)|=0 which would allow ℳ′ to preserve the same links as ℳ in the rest of the network; this would imply |ℳ′|>|ℳ| leading to a contradiction. On the other hand, if |Vio(ℳ)|>|Viru(ℳ)|, we would have |Vi(ℳ)|>|Vi| leading also to a contradiction.
Therefore|Vio(ℳ)|=|Viru(ℳ)| and |Vi(ℳ)|=|Vi|.
(2) Letℳ be any MM; note that, from 1, |Vi(ℳ)|=|Vi|. We begin by constructing ℳ′ such that |Vio(ℳ′)|=0, in two parts. On one hand, ℳ′ would contain the (known existing) perfect matching in Gi so that |Vi(ℳ′)|=|Vib(ℳ′)|=|Vi|. Since |Vio(ℳ′)|=0, this would allow completing ℳ′ by keeping the same links as ℳ in the rest of the network (satisfying |ℳ′|=|ℳ|).
We can now constructℳ′′ so that Vio(ℳ′′) is any arbitrary subset of Vio(ℳ). Since Vio(ℳ′′)⊂Vib(ℳ′) for each of its nodes, we can remove the (known existing) outgoing link in ℳ′ and restore the corresponding link in ℳ. This again would allow completing ℳ′′ by keeping the same links as ℳ and ℳ′ in the rest of the network.
Finally, note the true equivalence in the theorem statement: for anyGi∈Snt, we have that Gi∈Sntrm if and only if Gi accepts a perfect match. If Gi∈Sntrm(ℳ), we have already seen that ℳ defines a perfect matching in Gi. Alternatively, consider that Gi accepts a perfect match. As shown above, given any ℳ, either Gi∉Sntrm(ℳ) or we can construct ℳ′ such that Gi∈Sntrm(ℳ′).We now formulate a result illustrating the existence of MMs which can make or not, one by one, the elements ofSnt to be right-unmatched.Corollary 16.
LetG1, G2∈Sntrm(ℳ) for some ℳ.(1)
If there existℳ1 and ℳ2 satisfying Sntru(ℳ1)⊇Sntru(ℳ)∪{G1} and Sntru(ℳ2)⊇Sntru(ℳ)∪{G2}, then there may not exist ℳ3 satisfying Sntru(ℳ3)⊇Sntru(ℳ)∪{G1,G2}.(2)
The other way around, if there existsℳ3 satisfying Sntru(ℳ3)⊇Sntru(ℳ)∪{G1,G2}, then there must exist ℳ1 and ℳ2 satisfying Sntru(ℳ1)=Sntru(ℳ3)∖{G2} and Sntru(ℳ2)=Sntru(ℳ3)∖{G1}.Proof.
(1) The first part of the corollary is obvious due to the interdependence of the outgoing links in the elements ofSntrm(ℳ). For instance, let us consider
(20)A=[0100010100000000010100010]
whose graphical representation can be found in Figure 5. There exists ℳ such that G1 is the subgraph gathering nodes {1,2}, and G2 gathers {4,5}. There exist ℳ1 and ℳ2 satisfying Sntru(ℳ1)=Sntru(ℳ)∪{G1} and Sntru(ℳ2)=Sntru(ℳ)∪{G2}, but no ℳ3 satisfying Sntru(ℳ3)=Sntru(ℳ)∪{G1,G2}.
(2) Givenℳ3, such that Sntru(ℳ3)⊇Sntru(ℳ)∪{G1,G2}, then, by Theorem 15, we can construct a new MM (let us call it ℳ1) such that G2∈Sntrm(ℳ1), ℳ1 being the same as ℳ3 for links not outgoing from nodes of G2 (this includes all links involving nodes of G1, since there cannot be links from nodes of G2 to nodes of G1). Therefore Sntru(ℳ1)=Sntru(ℳ3)∖{G2}.
The same reasoning can be applied to justify the existence ofℳ2.Figure 5
G
1 and G2 are interdependent because they cannot both belong to Sntru(ℳ) for any ℳ.We now consider the optimality with respect tondc: a MM ℳ* is optimal if ndc(ℳ*)≤ndc(ℳ) for any other ℳ. The following result provides information about the existence of optimal solutions in a standard form.Corollary 17.
LetGi∈Sntrm; then there exists an optimal ℳ* such that |Viru(ℳ*)|=|Vio(ℳ*)|≤1.Proof.
Let us considerℳ* being optimal and |Viru(ℳ*)|=|Vio(ℳ*)|>1. By Theorem 15, we can construct a new MM (let us call it ℳ*′) such that |Viru(ℳ*′)|=|Vio(ℳ*′)|=1, ℳ*′ being the same as ℳ* for links not outgoing from nodes of Gi. Note that neither ℳ* nor ℳ*′ require a wiring on Gi, and the required wirings in the rest of the network remain unchanged. Hence, invoking (10), we have ndc(ℳ*)=ndc(ℳ*′).Remark 18.
LetGi∈Sntrm and let ℳ* be optimal with |Viru(ℳ*)|=|Vio(ℳ*)|≥1. Let ℳ′ be such that |Viru(ℳ′)|=|Vio(ℳ′)|=0, ℳ′ being the same as ℳ* for links not outgoing from nodes of Gi. Then ℳ′ is not optimal since a new wiring is required and ndc(ℳ′)=ndc(ℳ*)+1.
Nevertheless, there may exist another optimalℳ*′ such that |Viru(ℳ*′)|=|Vio(ℳ*′)|=0, but ℳ*′ should be necessarilydifferent from ℳ* for links not outgoing from nodes of Gi.


## 5.3. Compatibility

We are now ready to state the final results which will determine the steps of the algorithms for searching optimal solutionsℳ*.Definition 19.
LetGi∈Sntrm. We say that Gi istop-assignable if and only if there exists a MM ℳ such that |Vio(ℳ)|=1.Note that we only need to consider top-assignable elements ofGi∈Sntrm in the search for an optimum ℳ*.Definition 20.
LetG1,…,Gk∈Sntrm be top-assignable. We say that {G1,…,Gk} arecompatible if and only if there exists a MM ℳ such that G1,…,Gk∈Sntru(ℳ).By Theorem15 it is equivalent to guarantee that there exists a ℳ′′ such that |Vio(ℳ′′)|=1, i=1,…,k. Note that all unitary sets of the form {Gi} with Gi assignable are also compatible; the definition provides new insights when being particularized for pairs {G1,G2} (i.e., pairwise compatibility implicitly addressed in Corollary 16).We say that{G1,…,Gk} areincompatible if they are not compatible.The following lemma proves a fundamental property of compatibility and incompatibility.Lemma 21.
LetI={1,…,|Sntrm|} so that Sntrm={Gi:i∈I}. Let I1,I2 be two different nonempty subsets of I, such that 𝒢1={Gi:i∈I1} and 𝒢2={Gi:i∈I2} are subsets of Sntrm so that all elements of 𝒢1 are compatible among them and all elements of 𝒢2 are also compatible among them. Let us consider |I1|=k≤l=|I2| without loss of generality. Then, there exists 𝒢3={Gi:i∈I3} compatible such that |I2|≤|I3| and I1⊆I3⊆I1∪I2 (equivalently, 𝒢1⊆𝒢3⊆𝒢1∪𝒢2).Proof.
From the hypotheses, there must exist the following MMs:(i)
ℳ such that |Vio(ℳ)|=0,i∈I1∪I2 (since 𝒢1,𝒢1⊂Sntrm);(ii)
ℳ1 such that |Vio(ℳ1)|=1,i∈I1 (since 𝒢1 is compatible);(iii)
ℳ2 such that |Vio(ℳ2)|=1,i∈I2 (since 𝒢2 is compatible).
Let us consider the subgraphG1,2=G-∪i∈I1∪I2Gi, where all nodes of Gi∈ℳ1∪ℳ2 are removed from G together with the links outgoing from them. Note that ℳ restricted to each Gi,i=I1∪I2 defines a perfect submatching ℳGi on it. Hence, ℳ restricted to G1,2 defines a maximum submatching ℳG12 on it; otherwise, a matching larger than ℳ could be constructed on the whole graph by adding to the new larger submatching the subgraphs Gi,i∈I1∪I2 with their corresponding perfect submatchings.
Let us consider nowℳ1,G1,2 and ℳ2,G1,2, the corresponding submatchings of ℳ1 and ℳ2 on G1,2, respectively. By Theorem 15, all these submatchings are maximum in G1,2 having all size |ℳ|-∑i∈I1∪I2‍|Vi(ℳ)|. By construction ℳ1,G1,2 has k right-unmatched nodes (let us call them vi,i∈I1) each one being the destination of the corresponding link outgoing Gi∈𝒢1; by the same way ℳ2,G1,2 has l right-unmatched nodes (let us call them vi,i∈I2) destination of the links outgoing Gi∈𝒢2 in ℳ2. Let I12=I1-I2; then for all vii∈I12, we have vi∈Vru(ℳ1)∩Vrm(ℳ2), i∈I12, and we can apply Lemma 14 to I12 obtaining I12′ (which satisfies I12′∩I1=∅) and ℳ3 such that Vru(ℳ3)=Vru(ℳ2)∖{vi:i∈I12′}⊔{vi:i∈I12}. Then, we have that, for I3=I2∖I12′∪I12, I1⊂I3 and |I3|≥|I2|. Completing such submatching with the corresponding submatchings, ℳ1,Gi,i∈I1, ℳ2,Gi,i∈I3-I1, and ℳGi,i∈I12′, we would complete the required MM to end the proof.The following corollaries prove some relationships when the sets are modified element by element; they also show that pairwise incompatibility, besides being symmetric, is also a transitive property.Corollary 22.
LetG1,…,Gk,Gk+1∈Sntrm be top-assignable, so that {G1,…,Gk} are compatible and {G1,…,Gk,Gk+1} are incompatible. Then, there exists 1≤j≤k such that {G1,…,Gj-1,Gj+1,…,Gk+1} are compatible.Proof.
Calling𝒢1={G1,…,Gk} and 𝒢2={Gk+1} we only need to apply Lemma 21.Corollary 23.
LetG1,G2,G3∈Sntrm be top-assignable, so that G3 is incompatible with both G1 and G2, respectively. Then G1 and G2 are incompatible.Proof.
Keeping the assumptions, we will considerG1 and G2 to be compatible; then, applying Lemma 21, we know that either {G1,G3} or {G1,G3} must be compatible, which leads to a contradiction.Corollary 24.
LetG1,G2∈Sntrm be top-assignable and incompatible. If G1 is compatible with G3, then G2 is also compatible with G3.Proof.
If we considerG2 and G3 incompatible, the first assumption and the transitivity property would imply G1 and G3 being incompatible, which contradicts the second assumption.Finally, Lemma21 allows for a useful characterization of the set of possible optimal matchings.Theorem 25.
Let𝒢={G1,…,Gk}⊂Sntrm be top-assignable and compatible. Then ∃ℳ* such that |Viru(ℳ*)|=1, for i=1,…,k (i.e., 𝒢⊂Sntru(ℳ*)).Proof.
Let us consider∃ℳ*′ optimal, so that Sntru(ℳ*′)={G1′,…,Gl′}=𝒢′, where obviously k≤l (otherwise ℳ such that 𝒢={G1,…,Gk}⊂Sntru(ℳ) would provide a larger set of right-unmatched components contradicting the optimality of ℳ*′). Then applying Lemma 21, we can construct a new compatible set 𝒢′′={G1′′,G2′′,…,Gl′′} satisfying 𝒢⊂𝒢′′ and |𝒢′′|≥|𝒢′|. Since ℳ′ is optimum, then |𝒢′′|=|𝒢′| and MM ℳ′′ is also optimum, satisfying the theorem statement.


## 6. A New Algorithm for Computingndc

The proposed algorithm for locating an optimalℳ* is as follows.(1)
DetermineSnt.(2)
Determine all elements ofSnt accepting a perfect matching; for each Gi∈Snt, we remove the links outgoing Gi and compute a maximum submatching in Gi. If such matching is perfect, then Gi accepts a perfect matching.LetSntrm={G1,…,Gk}⊂Snt be the elements of Snt accepting a perfect matching. We call G′=G-G1-⋯-Gk the subgraph, where G1,…,Gk are removed from G together with the links outgoing from them.(3)
For all elements ofSntrm, determine the set of top-assignable elements Sntrm/ta={G1,…,Gm}; for doing so, we apply procedure P1.If a givenGi happens to be assignable, then a maximum submatching ℳi,G′ is already available which might also give additional information about assignability of other Gj's as well as compatibility among them.(4)
ConstructS={G1,…,Gl} as the maximum set of assignable and compatible elements provided by the previous step (the index being reordered without loss of generality). Note that if some assignable element has been found, S will contain at least one element. If no Gi is assignable, then S=∅, implying that we are done since all elements of Sntrm require a dedicated input.(5)
Fori=l+1,…,m, check compatibility of S′=S∪{Gi} (applying procedure P2). If S′ is compatible, then S=S′.(6)
αc=|Snt|-|Sntrm|+|S|.(7)
By (8) and keeping in mind |Snt|=βc, ndc is directly obtained as
(21)ndc=nc+|Snt|-αc.The basic procedures are as follows.(P1)
GivenGi∈Sntrm, this procedure determines if it is top-assignable. We first compute a maximum submatching in G′, called ℳG′; |ℳG′| is to be employed as a reference of the attainable MM size (note that |VG′ru(ℳG′)|=|VGru(ℳG)|, where ℳG refers to the whole network, and it is obtained by adding to ℳG′ the perfect submatchings corresponding to each Gi). Then, for all Gi, we check the existence of a maximum submatching in G′ having one right-unmatched node belonging to the set of destination nodes of links outgoing Gi (i.e., for each destination node, the links entering it are removed and the existence of a MM in such new graph is checked. Note that one may need to check for all the destination nodes associated with Gi). If such maximum submatching is found, we define Gi to be assignable. If Gi is top-assignable, this procedure will provide at least one maximum submatching ℳi,G′ associated with one of such destination nodes.(P2)
GivenS and Gl+1∈Snt top-assignable, determine if they are compatible. For doing so, we only need to consider the existence of a maximum submatching in G′ which has one right-unmatched node belonging to each set of destination nodes of links outgoing each Gi,i=1,…,l and one right-unmatched node (different from the previous one) belonging to the set of destination nodes of links outgoing Gl+1. Note that one may need to check for all the possible pairings of different destination nodes associated with S and Gl+1, respectively. If S and Gl+1 are compatible, this procedure will provide at least one maximum submatching ℳ1,2,…,l+1 associated with a pair of such nodes.The search of such maximum submatchingℳ1,2,…,l+1 can be (sometimes) simplified by using available maximum submatchings ℳ1,2,…,l and ℳGl+1 from P1 and following the procedure proposed in Lemma 13.


### 6.1. Suboptimal Solutions

Finding the control configuration with the minimum number of dedicated inputs might be computationally expensive for large networks; hence the consideration of a suboptimal solution can be useful. Considering the expression proposed in [10],
(22)ndc=nc+|Snt|-αc,
a suboptimal solution could be proposed, requiring nc+|Snt| dedicated inputs. This upper bound can be computed by determining the nontop linked SCCs of G(V,E) and performing a MM search on the network. Since the MM search dominates the complexity of the algorithm, computing such suboptimal solution takes O(VE) time.Analogously, given the definition ofαc in step (10) of the algorithm proposed on Section 6, the minimum number of required inputs can also be expressed as
(23)ndc=nc+|Sntrm|-|S|.Note that a new smaller upper bound tondc can also be derived from this expression by just computing nc and |Sntrm|. While the latter is already available at step (2) of the algorithm, nc can be obtained by just performing a MM search on G′.This suboptimal solution computes the MMs of subgraphsG′ and Sntrm={G1,…,Gk}⊂Snt that define a partition on G(V,E). Since the time complexity of a MM search is superlinear, finding a MM for each of the subgraphs is faster than computing a MM of the whole network. This means that this latter upper bound is not only closer to the optimal solution but also less computationally expensive.


## 6.1. Suboptimal Solutions

Finding the control configuration with the minimum number of dedicated inputs might be computationally expensive for large networks; hence the consideration of a suboptimal solution can be useful. Considering the expression proposed in [10],
(22)ndc=nc+|Snt|-αc,
a suboptimal solution could be proposed, requiring nc+|Snt| dedicated inputs. This upper bound can be computed by determining the nontop linked SCCs of G(V,E) and performing a MM search on the network. Since the MM search dominates the complexity of the algorithm, computing such suboptimal solution takes O(VE) time.Analogously, given the definition ofαc in step (10) of the algorithm proposed on Section 6, the minimum number of required inputs can also be expressed as
(23)ndc=nc+|Sntrm|-|S|.Note that a new smaller upper bound tondc can also be derived from this expression by just computing nc and |Sntrm|. While the latter is already available at step (2) of the algorithm, nc can be obtained by just performing a MM search on G′.This suboptimal solution computes the MMs of subgraphsG′ and Sntrm={G1,…,Gk}⊂Snt that define a partition on G(V,E). Since the time complexity of a MM search is superlinear, finding a MM for each of the subgraphs is faster than computing a MM of the whole network. This means that this latter upper bound is not only closer to the optimal solution but also less computationally expensive.


## 7. A Comparative Example

The following example illustrates the behavior of the new proposed algorithm. If we consider the network in Figure6, the application of a simple MM-based algorithm plus direct wiring keeping track of accessibility (see [15] for details) may provide (depending on the obtained MM) a different number of required dedicated input signals, ranging from four (corresponding to a solution with two unmatched nodes and only two wirings, in the most favourable case) to eight (two unmatched nodes plus six wirings, in the worst case). If we combine the MM-based algorithm with another one which also determines the SCCs for an ordered accessibility track (see [16]), we may obtain (again depending on the obtained MM) solutions ranging from four dedicated inputs (corresponding to an optimal solution) to six (two unmatched nodes plus four wirings, in the worst case).Figure 6
The result of applying the proposed algorithm for minimizing the number of dedicated inputs.The new proposed algorithm always leads to an optimal solution by first determiningSntrm={G1,G2,G3,G4}; then, applying procedure P1, it finds that G1 is not assignable whereas G2,G3,G4 are assignable. Finally, applying procedure P2, it determines that G2,G3,G4 are pairwise compatible but 𝒢={G2,G3,G4} is not compatible. These results lead to selecting (among others) the optimal MM ℳ* shown in the figure such that 𝒢1={G2,G3}⊂Sntru(ℳ*). (Note that nodes 3 and 4 are controlled since they constitute a cycle which is accessible from either u1 or u2.)


## 8. Concluding Remarks

Structural controllability and observability of complex directed networks have been analyzed by combining algebraic and graph theoretic tools. Two different design problems have been addressed and the extent of some controller/observer duality results has been demonstrated. In addition, some results concerning the structure of optimal solutions and their relationship with respect to MM have also been proved; these results have led to new algorithms to efficiently compute optimal and suboptimal solutions for monitoring large scale real networks.



---

*Source: 676313-2014-05-04.xml*