Output selection for large scale structural systems: a matroid theory approach

OUTPUT SELECTION FOR LARGE-SCALE STRUCTURAL SYSTEMS A MATROID THEORY APPROACH PEDRO MANUEL SABINO ROCHA DISSERTAÇÃO DE MESTRADO APRESENTADA À FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO EM ENGENHARIA ELECTROTÉCNICA E DE COMPUTADORES M 2014 FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO Output Selection for Large-Scale Structural Systems: a Matroid Theory Approach Pedro Manuel Sabino Rocha Mestrado Integrado em Engenharia Electrotécnica e de Computadores Supervisor: António Pedro Aguiar (Associate Professor) Co-supervisor: Paula Rocha Malonek (Full Professor) July 31, 2014 c Pedro Manuel Sabino Rocha, 2014 Abstract The question of how many outputs are needed and where to place them in order to fully observe a linear system has been a fundamental and challenging problem in control theory and applications of control systems. Structural system theory combined with graph theoretic tools has provided an efficient framework to answer this question for an equivalent class of systems, where properties are explored based on the structure of the system that corresponds to the location of zero and nonzero values. This approach deals well with applications to large-scale systems, where the systems’ dimension has to be taken into account. Within this framework, for a given structure of the state matrix of a large scale linear system, a fundamental problem is the design issue of the structure of the output matrix such that overall the system is structurally observable with the restriction that each output be dedicated, i.e., it can only measure directly a single state variable. In the present work, we propose a novel approach to solve that problem based on matroid theory. Further, we make the connection of the obtained results with graph theory and consequently provide an efficient solution to find a minimum number of dedicated outputs that ensures structural observability. Moreover, we demonstrate that if we additionally impose a performance restriction given by the systems’ generic observability index, then the problem falls in the NP-complete class. Several examples are presented that illustrate the derived results. i ii Resumo O problema relacionado com a seleção das variáveis de saída, quantas são necessárias e onde devem ser colocadas, de forma a garantir observabilidade para um dado sistema linear continua a ser um problema fundamental e desafiante em teoria de controlo, bem como em aplicações a sistemas de controlo. A teoria estrutural aliada a ferramentas de teoria de grafos tem proporcionado um enquadramento eficiente para dar uma resposta adequada a esta questão quando se considera uma classe de sistemas, em que a propriedade de observabilidade é explorada tendo em consideração apenas a estrutura do sistema, isto é, a localização de zeros e não-zeros. Esta abordagem permite lidar com aplicações para sistemas de grande-escala, onde a dimensão do sistema é um factor a ter em conta. Dentro deste contexto e para uma dada estrutura da matriz de estado de um sistema linear de grande-escala, um problema fundamental consiste em projetar a estrutura da matriz de saída de tal forma que o sistema resultante seja estruturalmente observável, com a restrição de cada variável de saída ser dedicada, isto é, cada variável de saída pode medir apenas uma variável de estado. No presente trabalho, é proposta uma nova solução baseada em teoria de matróides para o problema mencionado. De seguida, é estabelecida a conexão entre os resultados obtidos e a teoria dos grafos e, consequentemente, é proposto um algoritmo eficiente para encontrar uma configuração de tamanho mínimo de variáveis de saída dedicadas que garantem observabilidade estrutural. Uma outra contribuição é que é demonstrado que se se impuser uma restrição de performance adicional, baseada no índice genérico de observabilidade, o problema torna-se NP-completo. Vários exemplos que ilustram os resultados obtidos são apresentados. iii iv Agradecimentos Gostaria de deixar um breve e, por isso, injusto agradecimento às seguintes pessoas. Ao professor António Pedro Aguiar, que sendo a força motriz deste trabalho, não colocou nenhum entrave às minhas deambulações intelectuais. Pelo contrário, sempre as acolheu, conseguindo extraír resultados de interessantíssima aplicabilidade. À professora Paula Rocha Malonek, que sempre participou com entusiasmo, brilhantismo e dedicação nas várias actividades deste trabalho. Convidoume para o mundo da investigação, quando numa das suas aulas me entregou um livro de texto para ler em casa. Por isso, ficar-lhe-ei para sempre reconhecido. Ao aluno de doutoramento Sérgio Pequito, uma ajuda importantíssima sem a qual este trabalho não teria sido possível. Ensinou-me, com inúmeras sugestões e preciosos conselhos, a saber investigar. Ao meus dois grandes amigos Sofia Araújo e Fábio Carneiro. À primeira, pelo seu eterno zelo; tanto dá, sem nada pedir em troca. Ao segundo, por estar sempre pronto a ouvir, tornando esta tarefa bastante mais prazenteira. Finalmente, à minha família sem a qual nada disto faria sentido. À minha mãe pela sua louvável determinação; o ser mais querido com o qual tive a oportunidade de ser educado. Pedro Manuel Sabino Rocha v xii LIST OF FIGURES 3.9 A directed graph in a) and the associated condensation in b). The red circles are theSCCs. ...................................... 41 3.10 A representation of a condensation of some structural directed graph. The circles represent the strong connected components, where the green ones are non-bottom linkedSCC’s..................................... 42 4.1 A directed graph representation associated with the Set Covering Problem instance given in Example 18. ................................ 48 4.2 A structural directed graph representation D1(¯ A,¯ C)for which µG(¯ A,¯ C) = k. . . 48 4.3 A structural directed graph representation D2(¯ A,¯ C)for which µG(¯ A,¯ C) = k. . . 49 5.1 The structural directed graph representation of matrix ¯ Adescribed in (5.1). The strong connected components are represented by red dashed lines. . . . . . . . . 54 5.2 The bipartite graph representation of matrix ¯ Afrom equation (5.1). A maximal matching is depicted with red-colored edges. . . . . . . . . . . . . . . . . . . . . 54 5.3 The bipartite exchange graph for I={x1,x2,x6}. ................. 55 5.4 A set of spatially distributed wireless sensors. Each sensor belongs to a local area (represented by a dashed black circle). Some sensors can communicate (bidirectional) with each other in the same local area (blue lines). A node can transmit information to different local areas (red arrows). The objective is to choose the set of sensors allowed to change information with the central authority in order to recover the vector of initial measurements. . . . . . . . . . . . . . . . . . . . . . 57 5.5 A structural directed graph representation of the network depicted in Figure 5.4 ˙ Although not depicted, to ease the illustration, each node has a self-loop. . . . . . . . . . . 58 5.6 Condensation of the structural directed graph representation of Figure 5.5. The strong connected components are X1={x1,x2},X2={x3,x4,x5},X3={x3,x6,x7,x8,x9} and X4={x10}.................................... 59 5.7 The bipartite graph construction of STEP 3. The edges in green correspond to the connections between state variables and the associated non-bottom linked SCCs. The dashed edges belong to a weighted-maximal matching. . . . . . . . . . . . 59 5.8 The average number of minimum dedicated outputs needed to ensure structural observability for p=0.001. ............................ 61 5.9 The average number of minimum dedicated outputs needed to ensure structural observability for p=0.01. ............................. 61 5.10 The average number of minimum dedicated outputs needed to ensure structural observability for p=0.1. ............................. 62 5.11 The average number of minimum dedicated outputs needed to ensure structural observability for p=0.2. ............................. 62 5.12 The average number of minimum dedicated outputs needed to ensure structural observability for p=0.3. ............................. 63 5.13 The average number of minimum dedicated outputs needed to ensure structural observability for p=0.4. ............................. 63 5.14 The average number of minimum dedicated outputs needed to ensure structural observability for p=0.5. ............................. 64 5.15 The average number of minimum dedicated outputs needed to ensure structural observability for p=0.6. ............................. 64 5.16 The average number of minimum dedicated outputs needed to ensure structural observability for p=0.7. ............................. 65 LIST OF FIGURES xiii 5.17 The average number of minimum dedicated outputs needed to ensure structural observability for p=0.8. ............................. 65 5.18 The average number of minimum dedicated outputs needed to ensure structural observability for p=0.9. ............................. 66 xiv LIST OF FIGURES Abbreviations and Notation FDOC Feasible Dedicated Output Configuration LTI Linear Time-Invariant SCC Strong Connected Component SCP Set Covering Problem A∪BResulting set from the union of sets Aand B A∩BResulting set from the intersection of sets Aand B A\BResulting set from the difference between sets Aand B A4BResulting set from the symmetric difference between sets Aand B |A|Cardinality of set A XSet of state variables YSet of output variables SOSet of state variables where dedicated outputs are placed ¯ MStructural pattern of matrix M [¯ M]Classe of matrices that have the same dimension and structure of M InIdentity matrix of size n grank(¯ M)Generic rank of structural matrix ¯ M xv Chapter 1 Introduction Over the last few decades, mankind has been experiencing an intensive and limitless desire to build and to control ever larger and more sophisticated systems. These systems of large-scale arise naturally in a variety of fields like biology [1], traffic systems [2] and wireless networks [3] to name a few. Common to the design of these systems is the question of observability and its degree, which provides a measure of how well internal states of a system can be inferred by knowledge of its external outputs. When designing the system’s outputs, there are mainly two aspects to take into account. First, one needs to consider the cost that is associated with the output placement. Typically, we would like to use the lowest possible number of outputs to ensure observability. Secondly, consideration has to be paid to the system performance, which may depend on how fast the outputs can effectively observe the system. In this thesis, we will focus in those two problems. When dealing with large scale systems, some aspects have to be taken into account. Since the dimension of the system is large, approaches that in general lead to an increase of the complexity of analysis and design have to be avoided. For instance, the verification that a given system is observable leads to some known numerical issues [4]. Additionally, the problem of finding the minimum number of inputs needed to control a linear system and, by duality, the minimum number of outputs needed to guarantee observability, has recently been shown to be an NP-hard problem [5]. In order to cope with the aforementioned difficulties, we will rely on structural systems theory which briefly consists in explore the system properties based only on the sparsity pattern, i.e, the zero/non-zero pattern of the state space representation matrices. The study of structural systems has started with Lin [6] when he first introduced the concepts of structure and structural controllability and provided the necessary and sufficient conditions to verify structural controllability of single-input linear systems. Later on, Shields and Pearson [7] and Glover and Silverman [8] extended Lin’s results to multi-input linear systems. Since, within this theory, the only information kept is the zero/non-zero pattern, various system properties can be characterized in terms of quite simple properties of graph theory. Analysis using structural systems provides systemtheoretic guarantees that hold for almost all values of the free parameters (the non-zeros) except for a manifold of zero Lebesgue measure [9], which may be further characterized algebraically. 1 2Introduction Figure 1.1: A representation of a large-scale network. There are various entities (colored dots) that interact with each other (represented by a black line connecting the dots). Source:http://www.nas.ewi.tudelft.nl/people/Dajie/images/randomgraph.gif Furthermore, since many of the properties of the system can be translated into simple graph conditions, the computational burden is low and allows to deal with large-scale systems, specially if they are sparse. Besides structural systems analysis, research work has also been made concerning system design. Systematic approaches to structured systems based design were investigated in different application scenarios as in [10] and [11]. In this work, we study the constrained output placement problem in which the outputs are dedicated, i.e, one output can only measure a single state variable. In [12] a similar study is carried out when the authors investigate the minimal actuator placement problem that arises from the control of biological complex networks. One of the problems addressed in that work is the question of finding the minimum number of dedicated inputs needed to ensure structural controllability (equivalent, by duality, to the problem studied in this thesis). However, the results in [12] hold only for the case in which the structural directed graph representation is strongly connected. In [13], a methodology that incurs polynomial complexity in the number of state variables to find the minimum number of dedicated outputs is proposed. Those results are extended in [14] where it is considered that there exists a cost associated with placing an output to a determined state variable and where the goal is to find the minimum number of dedicated outputs for structural observability. In this thesis, we propose a novel way to solve the constrained output placement problem based on matroid theory. The concept of matroid was introduced by Whitney in 1935 to try to capture abstractly the essence of independence [15]. This abstraction embraces a diversity of combinatorial structures like graphs and zero-one matrices. Furthermore, matroid theory arises naturally in combinatorial optimization since matroids are precisely the structures for which the greedy algorithm works [16]. Within structural systems theory, the matroid abstraction was used by Murota [17] and Clark [18]. The former when dealing with state space representation matrices that may contain three types of entries, namely fixed zeros and nonzeros divided into free parameters and fixed nonzero constants. The latter when demonstrating that some problems within structural systems Introduction 3 can be posed within a matroid optimization framework. Structural systems analysis lies on both graph and matrices concepts. Due to its combinatorics nature, it seems plausible to try to apply matroid theory to solve some problems in an efficiently manner. In the present work, the constrained output placement problem is reformulated as a matroid intersection problem. Within this framework, the generalization to the case where there are costs associated with the output placement is straightforward as the generalization of the matroid intersection algorithm to the weighted matroid intersection. Within structural systems theory, some questions related with the generic observability indices remained open as noticed in [19] and [20]. Those questions are directly related with the notion of how fast the initial state vector is recovered for a given network and it has enormous importance, particularly when we would like to build systems with the ability of performing real-time monitoring. In [21], the structural counterpart of the observability indices are introduced. In [22], a new methodology is proposed for the characterization and computation of the controllability indices of structured systems. An improved upper bound of the generic observability index is given in [23] based on graph representations. However, there is a lack of methods concerning system design when it is imposed a performance restriction translated by the systems’ generic observability index. In this work, we show that the problem of finding a minimum dedicated output configuration such that the generic observability index is less than some given constant falls in the NP-complete class. Main contributions The main thesis contributions are summarized below. •We propose a novel way to solve the optimal constrained output placement problem for large-scale structural linear systems based on matroid theory. •We make the connection of the obtained results with graph theory and consequently simplify the complexity of the matroid intersection algorithm. •We show that the output placement problem with generic observability index constraint is NP-complete. •We illustrate the derived results through several examples: a 6-node network example, a wireless sensor application, and simulations with 100-node random networks. •We provide alternative proofs to some well-known results. Organization of the Dissertation The thesis is organized as follows. In chapter 2, we briefly review some fundamental concepts from linear systems theory after which some important results are introduced. We also present an algorithm to test structural observability and to compute the generic dimension of the unobservable subspace when the system is not structurally observable. 4Introduction In chapter 3, the main problem is formulated. Then, we introduce some tools and concepts from matroid theory that will be applied to the main problem. Next, we reformulate our problem as an a intersection of two matroids. Finally, a new algorithm to find a minimum dedicated output configuration that ensures structural observability is presented. In chapter 4, the constrained output placement with generic observability index is precisely formulated. After, we demonstrate that this problem is NP-complete. Finally, in chapter 5, we start by illustrating the concepts regarding matroid theory with an example. After that, the algorithm developed in chapter 3 to find a minimum-cost feasible dedicated output configuration is applied to a spatially distributed sensor network. In the last section, some simulation results are presented. Chapter 2 Structural Systems Background This chapter starts with a review of some fundamental concepts from linear systems theory taken from [24] and [25], after which some important results on structural systems theory from [19] are introduced. Only our own alternative proofs are presented. 2.1 Linear Systems In many applications, dynamical systems can be modeled by a state space representation where an intermediate state variable is introduced in the description of the relation between the input and output variables. In what follows, attention will be paid to discrete linear time-invariant systems (LTI), i.e, systems that can be represented by a discrete-time linear state space model of the form x(t+1) = Ax(t) +Bu(t), (2.1) y(t) = Cx(t)+Du(t), (2.2) where the signals u∈Rm,x∈Rn, and y∈Rpare the input, the state and the output of the system, respectively, and t∈Nis the iteration instant. The first equation expresses a relation between the input and the state and it is called the state equation, while the second one is called the output equation. Following our motivation, attention will be paid to the scenario where there are no input signals affecting the system. In that case, the matrices Band Dare identically zero, yielding the pair of equations x(t+1) = Ax(t), (2.3) y(t) = Cx(t). (2.4) Matrix Afrom (2.3) is usually referred as the state matrix whereas matrix Cfrom (2.4) is commonly referred as the output matrix. 5 12 Structural Systems Background Figure 2.1: A structural directed graph representation. The state vertices are represented in blue while the output vertices are represented in red. The blue arcs belong to EX,Xwhile the green ones belong to EX,Y. Definition 4) if it holds numerically for almost all admissible numerical realizations, i.e, if Pis the property and ¯ Ma structural matrix that satisfies P, then the set {M∈[¯ M]|Mdoes not satisfy P} has zero Lebesgue measure [9]. To give an example, the concept of generic rank is introduced next. Definition 8 (Generic Rank) Given any structural matrix ¯ M∈ {0,1}n×m, the generic rank is defined as grank(¯ M) = max M∈[¯ M] rank(M).(2.12)  Example 5 For ¯ M=   0 0 0 1 1 0 1 1 0  , it can be concluded that grank(¯ M) = 2. In fact, the admissible realization M=   000 200 0 10 0   has rank 2and it is impossible to have a higher rank because of the null pattern of the first row. All admissible realizations concerning the structure of ¯ M can be written in the form: M=   000 a b 0 c d 0  , with a, b, c and d ∈R. Thus, it is possible to conclude that the realizations that do not have rank equal to 2lie on a proper variety of R3×3defined by the condition ad =bc. Since attention had been paid only to the structure of the systems, it would be important to introduce the structural counterpart of some of the concepts presented in the previous section. One of these concepts, observability, has an intuitive generalization. 2.2 Structural Systems 13 Definition 9 (Structural Observability) The pair (¯ A,¯ C),¯ A∈ {0,1}n×n,¯ C∈ {0,1}p×n, is said to be structurally observable if and only if there exists an admissible pair (A,C), with A ∈[¯ A]and C∈[¯ C], such that (A,C)is observable. Conditions for structural observability can be stated in terms of the matrix pair (¯ A,¯ C). To formulate these conditions, the following definitions introduced by Lin [6] have to be presented. Definition 10 (Form I) The structural pair (¯ A,¯ C),with ¯ A∈ {0,1}n×nand ¯ C∈ {0,1}p×n, is said to be reducible or to be in form I if there exists a permutation1matrix P such that PT¯ AP ="¯ A11 ¯ A12 0¯ A22#and ¯ CP =h0¯ C2i,(2.13) where ¯ Ai j is an ni×njmatrix for appropriate i,j=1,2, with 0<n1≤n and n1+n2=n, where ¯ C2is an p ×n2matrix.  Definition 11 (Form II) The structural pair (¯ A,¯ C), with ¯ A∈ {0,1}n×nand ¯ C∈ {0,1}p×n, is said to be in form II if the inequality holds grank "¯ A ¯ C#!<n.(2.14)  Example 6 Consider the structural pair ¯ A=      0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 1       and ¯ C=h0 0 0 1i. Let, for instance, P be the following permutation matrix: P=      1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1       . Then, we have that PT¯ AP =      0 1 1 0 1 0 0 0 0 0 0 1 0 0 1 1       and ¯ CP =h0 0 0 1i. 1A permutation matrix is a square zero-one matrix that has exactly one non-zero entry in each row and each column and zeros elsewhere. 14 Structural Systems Background Therefore, the pair (¯ A,¯ C)can be reduced to form I. On the other hand, grank "¯ A ¯ C#!=4=n, and, therefore, the pair is not in form II. If the pair (¯ A,¯ C), after a suitable permutation, can be lead to one of the previous forms, one may conclude that that pair is not structurally observable. In fact, sufficiency also holds [6], [7] and [8]. Theorem 3 A pair (¯ A,¯ C)is structurally observable if and only if it has neither form I nor form II.  One may verify that forms I and II are purely structural forms concerning the distribution of zeros and ones of the pair (¯ A,¯ C). Thus, these forms can be translated into graph conditions. This helps to visualize the concepts regarding structural observability. Before stating the graph criteria that will allow us to infer about the presence or absence of structural observability, it will be useful to introduce some definitions. Definition 12 (Path) Let D= (V,E)be a directed graph. A path P is a sequence of vertices P=v1,...,vk, with k ≥2, such that (vi,vi+1)∈E,∀i=1,...,k−1. Vertex v1is called the root of the path, while vkis called the tip. If there exists a path between viand vj, this will be represented by vi→vj. The size of the path is defined as the number of arcs used. If there exists a path of size k between viand vj, this is written as vi k −→ vj. Definition 13 (Elementary Path) An elementary path is a path where the vertices are all distinct.  Definition 14 (Cycle) Acycle is path where all the vertices are distinct except for the first one and the last one, which coincide.  Definition 15 The pair (¯ A,¯ C)is said to be output-connected if in the associated digraph D(¯ A,¯ C) there exists a path from every xi∈Xto some yj∈Y. The previous definition is directly related with form I (Definition 10) by the following proposition. Proposition 1 The pair (¯ A,¯ C)is output-connected if and only if it is not reducible, i.e., is not in form I.  Proof If the pair (¯ A,¯ C)is not output-connected, then the set Xcan be written as the union of two disjoint sets X=X1∪X2, with X1∩X2=/0, 2.2 Structural Systems 15 (a) digraph with a contraction. (b) digraph without contractions. Figure 2.2: A directed graph with a) a contraction and b) with that contraction removed. where for every xi∈X1it is impossible to have a path for any yj∈Y,∀j=1,...,p. After an appropriate permutation, we may assume that X1={x1,...,xn1}and that X2={xn1+1,...,xn}, with n1>0. Considering the definition of X1:(xi,yj)6∈ E,∀xi∈X1,∀yj∈Y. Thus, if we write ¯ Cas ¯ C=h¯ C1¯ C2i, with ¯ C1∈ {0,1}p×n1and ¯ C2∈ {0,1}p×n2, for n2=n−n1, it must be that ¯ C1=0. At the same time: (xi,xj)6∈ E,∀xi∈X1,∀xj∈X2. Otherwise, since there is a path from any xj∈X2to some ym∈Y, there would exist a path from xi∈X1to ym(by transitivity) contradicting our assumption about X1. Thus, ¯ Acan be written as: ¯ A="¯ A11 ¯ A12 ¯ A21 ¯ A22#, where ¯ Ai j ∈ {0,1}ni×njand it must be that ¯ A21 =0. Therefore, it is possible to reduce the system to form I. If the system is in form I, then with similar considerations it is possible to conclude that there exists at least one xi∈Xsuch that there is no path between xiand yj,∀yj∈Yand, therefore, the system is not output-connected.  While the fact that the system cannot be reduced to form I means that there must exist a path from each state variable to some output variable, form II deals with the distribution of the non-zero entries in the observability matrix. In order to attain full rank, it must be possible to obtain one non-zero entry per each column in a different row of the observability matrix. This is directly related with the following definitions. Definition 16 (Target Set) Considering the digraph D= (V,E), the target set of a vertex viis defined as T(vi) = {vj∈V|(vi,vj)∈E}. The definition can be extended to a set of vertices Vi⊆Vin the following manner: T(Vi) = [ vi∈Vi T(vi).  Definition 17 (Contraction) Let D(¯ A,¯ C)be the digraph associated with the pair (¯ A,¯ C). Then, D(¯ A,¯ C)is said to have a contraction if there exists Xs⊆Xsuch that |T(Xs)|<|Xs|.(2.15) 16 Structural Systems Background Figure 2.3: A bipartite graph B= (V1,V2,E)where V1={a1,a2,a3,a4}and V2={b1,b2,b3,b4}. The edges are represented in blue and red. The red ones belong to a maximal matching.  Example 7 Figure 2.2 illustrates the contraction concept. The digraph represented on the left has a contraction since |T({x1,x2})|=|{y1}|=1. Notice, also, that grank "¯ A ¯ C#!=     0 0 0 0 1 1    =1, which is less than n =2. On the other and, if, for instance, a self-loop is added to the state vertex x1, the contraction is removed. Notice that now the cardinality of the target set is |T({x1,x2})|= |{x1,y1}|=2and grank "¯ A ¯ C#!=     1 0 0 0 1 1    =2. In order to establish the relationship between contractions and the form II from Definition 11, it will be useful to introduce some concepts regarding bipartite graphs and matching theory. Definition 18 (Bipartite Graph) Abipartite graph B= (V1,V2,E)2is an undirected graph whose vertex set can be partitioned into two disjoint sets, V1and V2, such that E ⊆ {(v1,v2)| v1∈ V1, v2∈V2}. Definition 19 (Matching) Considering a bipartite graph B= (V1,V2,E), a matching M is a subset of the edge set such that every edge in M shares no vertex with any other edge in M. A matching M is maximal if for every other matching M0, we have |M|≥|M0|. A matching M is said to cover V1(or V2) if for every v1∈V1(respectively, v2∈V2) there is an edge e ∈M such that e= (v1,v2)for some v2∈V2(respectively, for some v1∈V1).  When dealing with matchings on bipartite graphs, a pertinent question that may arise is if a given bipartite graph B= (V1,V2,E)possesses or not matching that covers V1or V2. As 2The variable Ewill be used to denote a set of arcs, i.e, oriented pairs of vertices, whereas the variable Ewill be used to note a set of edges, i.e, non-oriented pairs of vertices. 2.2 Structural Systems 17 an example, it can be seen that the bipartite graph depicted in Figure 2.3 has a matching M= {(a1,b1),(a2,b3),(a3,b2),(a4,b4)}that covers both V1={a1,a2,a3,a4}and V2={b1,b2,b3,b4}. The following theorem provides necessary and sufficient conditions to guarantee that a bipartite graph B= (V1,V2,E)possesses a matching that covers V1. Theorem 4 (Hall Marriage Theorem) Consider a bipartite graph B= (V1,V2,E)and A ⊆V1. Let J(A) = {v2∈V2|(v1,v2)∈E for some v1∈A}. Then, a matching that covers V1exists if and only if, ∀A⊆V1: |A|≤|J(A)|.(2.16)  Similar to the structural directed graph representation, one can build a bipartite graph associated with the structural pair (¯ A,¯ C). Definition 20 (Structural Bipartite Graph Representation) For a system described by (2.3)- (2.4)and whose structural counterpart is given by ¯ A∈ {0,1}n×nand ¯ C∈ {0,1}p×n, the associated structural bipartite graph representation is the bipartite graph B(¯ A,¯ C)=(X−,X+∪ Y,EX−,X+∪EX−,Y)where X−={x− 1,...,x− n},X+={x+ 1,...,x+ n}and Y={y1,...,yp}. The set of edges is the union of the following sets: EX−,X+={(x− j,x+ i)|¯ Ai j =1,∀i,j=1,...,n}, EX−,Y={(x− j,yi)|¯ Ci j =1,∀j=1,...,n,∀i=1,...,p}.  Now, we are ready to present the graph criteria equivalent to form II (Definition 11). Proposition 2 The directed graph D(¯ A,¯ C)is free of contractions if and only if the pair (¯ A,¯ C)is not in form II.  Proof In order to prove this claim, consider the bipartite graph B(¯ A,¯ C)associated with the structural pair (¯ A,¯ C)and the structural directed graph representation D(¯ A,¯ C). If the digraph D(¯ A,¯ C) is free of contractions, then ∀Xs⊆X−:|Xs|≤|T(Xs)|. Considering the bipartite graph and the Definition 16 of target set, one may write that ∀A⊆V1:|A|≤|J(A)|with J(A)defined as in Theorem 4. Thus, with Hall Marriage Theorem in mind, it is possible to conclude that there exists a matching in B(¯ A,¯ C)that covers X−. On the other hand, the existence of that matching tell us that it is possible to find one non-zero entry per column in different rows of the composite 18 Structural Systems Background Figure 2.4: A bipartite graph representation associated with the digraph represented in Figure 2.1. The edges that belong to the maxmimal matching are represented by dashed lines. matrix M="¯ A ¯ C#. To see that, notice that if (x− j,x+ i)or (x− j,yk)belong to the maximal matching, then ¯ Ai j =1 or ¯ Ck j =1, respectively. Since, by definition of that matching, the whole set X− is covered, for each column of Mit is possible to find one non-zero entry such that two different non-zero entries lie on different rows. Thus, it can be concluded that grank(M) = nand, therefore, (¯ A,¯ C)is not in form II. With analogous arguments, if (¯ A,¯ C)is not in form II, it is possible to see that B(¯ A,¯ C)has a maximal matching and, again, with Hall Marriage Theorem, one concludes that the digraph associated is contraction-free.  With the previous results, the sufficient and necessary conditions for structural observability can be stated with respect to the associated digraph. Theorem 5 Consider the pair (¯ A,¯ C)and its directed graph representation, D(¯ A,¯ C). The pair (¯ A,¯ C)is structurally observable if and only if D(¯ A,¯ C)is output connected and free of contractions.  Proof The proof follows immediately from Proposition 1, Proposition 2and Theorem 3. Example 8 Consider again the structural system whose directed graph representation is depicted in Figure 2.1. It can be seen that there is a path from every state vertex to some output vertex since (x1,y2),(x2,y2)and (x3,y1)are edges of the digraph. To check whether the system is contractionfree, one may construct its bipartite graph depicted in Figure 2.4. Since there exist a maximal matching that covers X−, the system is free of contractions. In fact, only output y2is needed to guarantee structural observability. Notice that the edges that belong to the maximal matching do not include y1and there is a path from x3to y2: x3→x2→y2. 2.2 Structural Systems 19 Structural Observability Test The direct correspondence between the necessary and sufficient conditions to guarantee structural observability and graph-theoretic conditions (see Theorem 5) makes suitable the design of an algorithm to check whether a given system is structurally observable or not. First, output-connectivity has to be verified. Second, one must conclude about the presence or absence of contractions. Definition 21 (Out-Connected Sets) Let D(¯ A,¯ C) = (X∪Y,EX,X∪EX,Y)be the directed graph associated with a structural system given by the pair (¯ A,¯ C). Then, for each output component yj∈Yand k, 1≤k≤n, the corresponding out-connected set Ok jis defined as: Ok j={xi∈X| xi p −→ yj, p ≤k}.(2.17)  It is straightforward to see that a structural system is output-connected if and only if the following equality holds: [ yj∈Y On j=X. (2.18) Furthermore, the definition of out-connected sets is suitable for a recursive computation, since for every yj∈Y, we have O1 j={xi∈X|(xi,yj)∈EX,Y},(2.19) Ok j={xi∈X|(xi,xl)∈EX,Xwith xl∈Ok−1 j}∪Ok−1 j, 1 <k≤n.(2.20) In order to test for the existence of contractions, one constructs the associated bipartite graph B(¯ A,¯ C) = (X−,X+∪Y,EX−,X+∪EX−,Y)and seeks for a matching that covers X−. This can be done efficiently with the Hopcroft-Karp algorithm that takes as input a bipartite graph and produces as output a maximum matching [26]. If that maximum matching includes all the vertices in X−={x− 1,...,x− n}, then the system is contraction-free. Otherwise, a contraction must exist. When the system is not structurally observable, the unobservable subspace and its dimension vary as function of the system parameters. However, as Hosoe demonstrated, the unobservable subspace dimension takes some constant value for all but an exceptional set of the free parameters that lie on a proper variety of zero Lebesgue measure [27]. Definition 22 (Generic Dimension the Unobservable Subspace) Given a structural pair (¯ A,¯ C), the generic dimension of the corresponding unobservable subspace, denoted by dU, is defined as dU=n−grank             ¯ C ¯ C¯ A . . . ¯ C¯ An−1             3,(2.21) 3For two structural matrices ¯ A∈ {0,1}n×mand ¯ B∈ {0,1}m×p, the product ¯ C=¯ A¯ Bis a structural matrix ¯ C∈ {0,1}n×psuch that ¯ Ci j =∨m k=1(¯ Aik ∧¯ Bk j). The operations ∨and ∧stand for the usual boolean operations or and and. 20 Structural Systems Background (a) The structural directed graph representation. (b) The bipartite representation excluding vertices x5 and x6since they do not belong to the out-reachable sets. The dashes lines represents edges that belong to a maximum matching. Figure 2.5: Example 9: in the left, a structural directed graph representation and, in the right, the bipartite graph representation constructed after STEP 2 of the Algorithm 1. where n is the size of the square matrix ¯ A.  Hosoe had proved the following theorem concerning the generic dimension of the unobservable subspace [27]. Theorem 6 Let dUbe the generic dimension of the unobservable subspace associated with the pair (¯ A,¯ C), where ¯ A has size n. Assuming that (¯ A,¯ C)is not in form I: dU=n−grank "¯ A ¯ C#!.(2.22)  If the system is in Form I (10), one has: grank             ¯ C ¯ C¯ A . . . ¯ C¯ An−1             =grank             ¯ C2 ¯ C2¯ A22 . . . ¯ C¯ An−1 22             , (2.23) which means that the problem of determining dUfor (¯ A,¯ C)reduces to the same problem for the irreducible system (¯ A22,¯ C2). With this in mind, it is possible to develop an algorithm that tests if a given system is structurally observable and, if not, returns the generic dimension of the unobservable subspace. It starts with the computation of the out-connected sets On jfor all yj∈Y. Then, it constructs the system (¯ A22,¯ C2)by eliminating the state vertices for which there is not any path to some output variable, i.e, the ones that do not belong to Syj∈YOn j. Finally, it proceeds to 2.2 Structural Systems 21 the construction of the bipartite graph of the pair (¯ A22,¯ C2)and computes a maximum matching. If the size n0of that matching equals the size nof ¯ A, the system is structurally observable. Otherwise, the generic dimension of the unobservable subspace is given by n−n0. Example 9 As an example to illustrate Algorithm 1, let us consider the structural system depicted in Figure 2.5. After the first step, the computation of the output-connected sets O6 j, for j =1,2, allow us to conclude that [ yj∈Y On j={x1,x2,x3,x4} 6=X, and, therefore, the system is not structurally observable because it can be reduced to form I. Thus, hereafter we work only with the irreducible system (¯ A22,¯ C2)formed by the state vertices x1,x2,x3 and x4, in order to compute the generic dimension of the unobservable subspace. The next step consists in verifying the size of the maximum matching in the bipartite graph constituted of the previously mentioned state variables. Figure 2.5 shows a maximum matching with three edges. Thus, the conclusion is that dUis equal to 6−3=3. 28 Output Selection for Structural Observability Figure 3.2: The construction given in proof of Theorem 8. The set Ais a maximal independent set of U1∩U2and it was augmented to create the set B, a maximal independent set of U1∪U2. Theorem 8 ([32]) Let M = (S,I)be a matroid. Then, for every U1, U2⊆S, the following holds: (i) 0≤r(U1)≤|U1|, (ii) if U1⊆U2, then r(U1)≤r(U2), (iii) r(U1)+ r(U2)≥r(U1∪U2)+r(U1∩U2).  Proof The proof of (i) and (ii) follows from the definition of rank. To prove (iii), consider the construction depicted in Figure 3.2. Let A⊆U1∩U2be a maximally independent subset ofU1∩U2. Applying successively the augmentation property to A, one can obtain the subset B⊆U1∪U2such that A⊆Band Bis a maximal independent subset of U1∪U2. From the figure, it is easy to see that |B∩U1|+|B∩U2|=|B|+|A|since the elements of Aare counted twice. Since Bis independent, so it is B∩U1and B∩U2. Further, according to (ii), r(U1)≥|B∩U1|and r(U2)≥|B∩U2|. Thus, r(U1)+r(U2)≥|B∩U1|+|B∩U2|=|B|+|A|=r(U1∪U2)+ r(U1∩U2). The third property of Theorem 8is called submodularity and plays an important role in various applications of matroids. Another important property is the association of matroids with the greedy algorithm. As the name indicates, the greedy algorithm is an algorithm that follows the heuristic of making the locally optimal choice at each step. Although this does not work to solve every optimization problem, it will be seen that matroids are exactly the structures for which the algorithm provides an optimal solution. ALGORITHM 2: Greedy algorithm for selecting the max-weight independent set of a matroid Input: A matroid M= (S,I), with S={1,2,...,n}, and a weight function w:S→R Output: An independent set I∗∈Isuch that w(I∗) = maxI∈Iw(I), where w(I) = ∑i∈Iw(i) Relabel the elements of the matroid so that w(1)≥w(2)≥. . . ≥w(n). I∗←/0. for i=1,...,ndo if I∗∪{i} ∈ Ithen I∗←I∗∪{i}. end for Return I∗. 3.2 A New Approach via Matroid Theory 29 Figure 3.3: An undirected graph whose edges were attributed a cost. The edges in red represent a maximum spanning tree. Theorem 9 ([30]) Let Ibe a nonempty collection of subsets of S closed under taking subsets. Then, the pair (S,I)is a matroid if and only if for any weight function w :S→R+, the greedy algorithm returns a set I ∈Iof maximum weight w(I). Proof To show sufficiency, let M= (S,I)be a matroid and w:S→R+a weight function. The solution of Algorithm 2will consist of a maximum weight base. Then, it suffices to show that I is always contained in a maximum weight base. Since I∗starts with the empty set, the desired property holds initially. Now, to prove the induction step, assume that I∗is contained in some maximum weight base, B, and let ybe an element in S\I∗with w(y)as large as possible. If y∈B, then I∗∪{y} ⊆ B. If y6∈ B, then there exists a base B0such that I∗∪{y} ⊆ B0and B0⊆B. Thus, there exists z∈B\I∗such that B0=B\{z}∪{y}. Since I∗∪{z} ⊆ B,I∗∪{z} ∈ Iand since w(y) was chosen maximum, w(y)≥w(z). Thus, w(B0)≥w(B)and therefore B0is a maximum weight base that contains I∗. To prove necessity, let us consider that the greedy algorithm leads to a maximum weigh independent set for any weight function w:S→R+. Condition (i) of Definition 23 is satisfied by assumption. Let us assume that condition (ii) of Definition 23 does not hold. Thus, there are I,J∈Iwith |J|>|I|such that I∪{z} 6∈ Ifor all z∈J\I. Let k=|I|and consider the following weight function: w(x) =          k+2 if x∈I, k+1 if x∈J\I, 0, otherwise. (3.6) Then, in the first kiterations, it will be I∗=I. Since, by assumption, I∪ {z} 6∈ Ifor all z∈J\I, the weight of the output w(I∗)will be k(k+2). Notice, however, that w(J) = |J|(k+1)≥(k+ 1)(k+1)>k(k+2) = w(I), contradicting our initial assumption.  Example 12 Consider the undirected graph G = (V,E)depicted in Figure 3.3 and a weighting function w :E→R+. A problem that usually arises in computer science is that of finding a maximum weighted tree, where a tree is a connected graph without cycles. Since the original graph G is connected, the problem is equivalent to that of computing the maximum weight forest. If we define S =E and I={I⊆E | such that (V,I)do not contain any cycles}, it follows from Proposition 4that M = (S,I)is a matroid. Thus, we can apply the greedy algorithm. It turns out 30 Output Selection for Structural Observability that this algorithm is equivalent to Kruskal’s algorithm to compute a maximum spanning tree for a connected weighted graph. It starts by sorting the edges by decreasing weight. Then, a edge is added if that addition do not create a cycle. It happens that some relevant problems within the scope of combinatorics can be expressed as the intersection of two matroids. Let M1= (S,I1)and M2= (S,I2)be two matroids. The intersection is the collection of sets I∈I1∩I2. However it is not generally the case that (S,I1∩ I2)is a collection of independent sets of a matroid on Eand therefore the greedy algorithm cannot be applied. In spite of this, Edmonds [28] showed that there exist efficient algorithms for the intersection of two matroids. More precisely, he showed that it is possible to find a maximumweight common independent set in two matroids in strongly polynomial time. Before describing the algorithm to compute a maximum-size common independent set in two matroids, we first describe a min-max relation that will be used to prove the optimallity of the algorithm. First, notice that given two matroids on the same ground set, M1= (S,I1)and M2= (S,I2), with rank functions r1and r2, respectively, one may write for any I∈I1∩I2and any U⊆S |I|=|I∩U|+|I∩(S\U)|≤r1(U)+r2(S\U), since, by the first axiom, I∩Uand I∩S\Uare both independent in I1and I2. If the maximum over Iand the minimum over Uis taken, it is possible to write the inequality: max I∈I1∩I2 |I|≤min U⊆S[r1(U)+r2(S\U)] . This inequality was proved first by Edmonds [28] and is known as the Matroid Intersection Theorem, stated next. Theorem 10 (Matroid Intersection) For any two matroids M1= (S,I1)and M2= (S,I2)with rank functions r1and r2respectively, the following equality holds: max I∈I1∩I2 |I|=min U⊆S[r1(U)+r2(E\U)].(3.7)  The previous theorem provides the upper limit in which we may stop the algorithm to compute a maximum-size common independent set in two matroids. However, one has to know what are the steps to follow in order to obtain the desired result. Before we present the algorithm, some technical results concerning bipartite graphs are presented. Lemma 2 ([31]) Let G = (V,E)be a bipartite graph with bipartition V =V1∪V2, V1∩V2=/0, and suppose that G has a unique matching M that includes all the vertices of V1. Then there exists an edge e = (v1,v2)∈M, v1∈V1, v2∈V2, such that: (v1,v0 2)6∈ E,∀v0 2∈V2\{v2}. 3.2 A New Approach via Matroid Theory 31  For any matroid and an independent set I, one can define a bipartite graph that expresses the changes that can occur in Iso that it remains independent as follows. Definition 28 (Bipartite Exchange Graph) Let M = (S,I)be a matroid and I ∈Ian independent set. Then, the bipartite exchange graph GM(I)is the bipartite graph with partition I and S\I such that for any y ∈I, x ∈S\I, (y,x)is an edge of GM(I)if and only if I \{y}∪{x} ∈ I.  The following lemma states that an exchange between two independent sets implies a perfect matching in the bipartite exchange graph. Lemma 3 ([31]) Let M = (S,I)be a matroid with I,J∈Iand |I|=|J|. Let GM(I)be the bipartite exchange graph associated with I. Then, GM(I)contains a perfect matching between I\J and J \I.  A very useful partial converse also holds. Lemma 4 ([31]) Let M = (S,I)be a matroid with I ∈Iand GM(I)the bipartite exchange graph. Let J ⊆S with |J|=|I|. If GM(I)contains a unique perfect matching between I \J and J\I, then J ∈I. Returning to the subject of matroid intersection, a structure similar to the bipartite exchange graph can be constructed for a pair of matroids. Definition 29 (Bipartite Exchange Digraph) Given two matroids defined over the same ground set, M1= (S,I1)and M2= (S,I2), and any I ∈I1∩I2, the exchange graph DM1,M2(I)is the directed graph with bipartition I and S \I such that for any y ∈I, x ∈S\I, (y,x)is an arc of DM1,M2(I)if and only if I \{y}∪{x} ∈ I1, (x,y)is an arc of DM1,M2(I)if and only if I \{y}∪{x} ∈ I2.  Relying on the previous definition, it would be of interest to construct directed paths along the bipartite exchange digraph that would result in augmenting the number of elements of I. To that purpose, certain vertices in S\Iare termed sources while others are the sinks. A source (respectively, sink) of DM1,M2(I)is a vertex x∈S\Isuch that I∪{x} ∈ I1(respectively, I∪{x} ∈ I2). A source-sink dipath is a directed path that begins in a source and ends in a sink and the 32 Output Selection for Structural Observability (a) Graphical representation of matroid M1.(b) Graphical representation of matroid M2. Figure 3.4: This figure represents two undirected graphs in correspondence with two graphical matroids. The edges in red belong to an independent set that belongs to both matroids. definition includes the degenerate scenario where the path contains no edges, for which the source and the sink are the same vertex. Then, the path Pwill have the vertex sequence x0,y1,x1,...,yn,xn where for all i,xi∈S\I,yi∈I, and x0is a source whereas xnis a sink. The source-sink dipath is said to be augmenting if I0=I\{y1,...,yn}∪{x0,x1,...,xn}is in I1∩I2. Notice that if V(P)is the set that contain the vertices that comprise the path P, then I0can be written as I0=I4V(P). Finally, the following lemma makes possible the task of finding an augmenting dipath. Lemma 5 ([31]) Let M1= (S,I1)and M2= (S,I2)be matroids and let I ∈I1∩I2. If P is a shortest source-sink dipath in DM1,M2(I), then it is augmenting.  Example 13 In order illustrate Lemma 5, consider the two graphical matroids depicted in Figure 3.4. The ground set is S ={a,b,c,d,e}and let M1= (S,I1)and M2= (S,I2)be the graphical matroids associated with Figure 3.4a and Figure 3.4b, respectively. Since I ={b,d}do not contain any cycle both in Figure 3.4a and Figure 3.4b, one must have that I ∈I1∩I2. With I, M1 and M2, one can construct the bipartite exchange digraph DM1,M2(I), which is represented in Figure 3.5. The set of sources is X1={x∈S\I | I ∪ {x} ∈ I1}={a}while the the of sinks is X2={x∈S\I | I ∪ {x} ∈ I2}={e}. If any path between a and e is considered, there is no guarantee that this path will correspond to an augmenting one. Indeed, take the directed path P1, whose edges are painted red and orange in Figure 3.5. Then V (P1) = {a,b,c,d,e}and I1=I4V(P1) = {a,c,e}that although independent in I1it is not in I2. On the other hand, if we take the directed path P2whose edges are painted green and orange and that corresponds to a shortest path between a and e, then, by Lemma 5, we know that P2is augmenting. In fact, V(P2) = {a,d,e}and I2=I4V(P1) = {a,b,e}, with I2∈I1∩I2and |I2|>|I|. With the previous lemma in mind, the following algorithm to compute a maximum-cardinality set that is independent in any given two matroids comes out. Theorem 11 (Correctness of the Cardinality Matroid-Intersection Algorithm) Let M1= (S,I1) and M2= (S,I2)be matroids. Then the Cardinality Matroid Intersection Algorithm (3) returns an independent set I∗∈I1∩I2such that |I∗|≥|I|,∀I∈I1∩I2. 3.2 A New Approach via Matroid Theory 33 ALGORITHM 3: Cardinality Matroid-Intersection Algorithm Input: Matroids M1= (S,I1)and M2= (S,I2) Output: An independent set I∗∈I1∩I2such that |I∗|≥|I|,∀I∈I1∩I2 1:I∗←/0. 2:Construct the set X1={x∈S\I∗|I∗∪{x} ∈ I1}. 3:Construct the set X2={x∈S\I∗|I∗∪{x} ∈ I2}. if DM1,M2(I∗)has an X1−X2path then Take the shortest such path P.I∗←I∗4V(P). Go to 2. elseReturn I∗. Proof Consider that when the algorithm stops it returns the set I. Since Istarts to be the empty set, attending to Lemma 5, it is easy to see that in the end Iis in I1∩I2. Thus, it remains to prove that Ihas indeed maximum cardinality. To that purpose, we will rely on the following construction. Let U={x∈S| there is x−ypath in DM1,M2(I), where y ∈X2}. Taking into account the definition of Uand considering that there is no directed path between X1and X2, one easily verifies that U∩X1=/0, X2⊆Uand there is no arc entering U(see Figure 3.6). First, we will show that r1(U)≤|I∩U|, where r1is the rank function associated with M1. If r1(U)>|I∩U|, then there exists x∈U\Isuch that (I∩U)∪ {x} ∈ I1. It must be that I∩ {x} 6∈ I1, since xis not in X1. Therefore, there must exist y∈I\Uwith I\ {y} ∩ {x} ∈ I1. Nevertheless, by definition of DM1,M2(I), there is an arc from yto x, contradicting the fact that no arc enters U. In a similar manner, it is possible to prove that r2(S\U)≤|S\U|. Thus |I|=|I∩U|+|I∩(S\U)|≥r1(U)+r2(S\U), and by Theorem 10 it is easy to see that Iis a maximum-cardinality independent set resulting from the intersection of the two matroids.  Notice that the algorithm has polynomial complexity provided that the time required to test if a given set Ibelongs (or not) to M1or M2is a polynomial function in the size of I. That is, for matroids M1and M2there must exist a subroutine to test whether or not a set of elements is independent. That subroutine is commonly referred as an independence oracle. Figure 3.5: A bipartite exchange digraph associated with M1,M2and Ias defined in Example 13. The vertex ais the only source whereas vertex eis the only sink. The directed path whose arcs are in green and orange represent a shortest source-sink path. 34 Output Selection for Structural Observability Figure 3.6: This figure depicts the construction of a set Uwith the conditions described in the proof of Theorem 11. Example 14 (Bipartite Matching) Let B= (V1,V2,E)be a bipartite graph. First, we note that matchings in a bipartite graph do not form a matroid because in general the second axiom is not verified. However, matchings can be regarded as an intersection of two matroids. For a given vertex x ∈V1, define σ(x)as the set of edges incident to x, i.e, σ(x) = {e∈E | there exists y ∈ V2with e = (x,y)}. Then, E can be partitioned as E =Sx∈V1σ(x). This forms a partition since all edges have precisely one endpoint in V1. Thus, we can define I1={I⊆E | |I∩σ(x)|≤1,∀x∈V1}. By Proposition 5, we know that M1= (E,I1)is a partition matroid. Notice that a set of edges is independent in M1if it has at most one edge incident to every vertex in V1. In a similar fashion, we can define I2={I⊆E | |I∩σ(x)|≤1,∀x∈V2}, and construct another matroid M2= (E,I2). Then, it can be concluded that I ∈I1∩I2if and only if I corresponds to a matching in B. Therefore, in order to compute a maximum matching, one can resort to the matroid intersection algorithm. We will consider now the weighted matroid intersection problem. Let M1= (S,I1)and M2= (S,I2)be two matroids and let w:S→R+be a weight function. Suppose that we would like to find an independent set I∈I1∩I2with maximum weight. It turns out that Algorithm 3can be generalized in a straightforward fashion to the weighted case, where the only difference is in finding the shortest source-sink directed path P. In computing P, one assigns weights to each vertex x∈DM1,M2(I)as w(x)if x∈Iand −w(x)when x6∈ I. Then, Pshould have the minimum number of arcs among all the minimum length X1−X2directed paths. The correctness of the algorithm will not be demonstrated here. It can be found in [30]. 3.3 The Solution of the Output Selection Problem In this section, the solution to the Output Selection Problem (3.4) is presented. The key idea is to formulate the problem as the intersection of two matroids, such that the necessary and sufficient conditions of Theorem 5to guarantee structural observability hold. That is, two matroids will 3.3 The Solution of the Output Selection Problem 35 be constructed over the set of the state variables: one to guarantee output-connectivity (cf. Definition 15); and another one to guarantee that the resulting structural pair is free of contractions (cf. Definition 17). Then, we will demonstrate that if dedicated outputs are assigned to the state variables in SO, with SO⊆X, then that assignment leads to structural observability if and only if the set X\SObelongs to the intersection of that two matroids. Thus, the matroid intersection algorithm can be applied to obtain a maximum-cardinality independent set I∗that lies in the intersection of the two matroids. Finally, X\I∗will correspond to a minimum feasible dedicated output configuration. Initially, attention will be devoted to the particular instance of the problem, when the cost function associated with the output placement is uniform. That is, the problem of finding the minimum number and the corresponding location of outputs to attain structural observability. The generalization to the scenario where the cost function takes different values according to the specific output follows from the generalization of Algorithm 3to the problem of finding a maximum-weight common independent set in two matroids. In the previous chapter, the necessary and sufficient conditions to guarantee structural observability were outlined in correspondence to graph criteria (see Theorem 5). Briefly, the pair (¯ A,¯ C)is structurally observable if and only if the directed graph representation D(¯ A,¯ C)is outputconnected (cf. Definition 15) and free of contractions (cf. Definition 17). With the structural matrix ¯ A∈ {0,1}n×n, one can associate the directed graph D(¯ A)=(X,EX,X), where Xis the set of the state variables and EX,X={(xj,xi)|¯ Ai j =1}describes the relations among them. Considering two sets X1and X2,X1,X2⊆X, the set X1is said to be completely connected to X2if for all xi∈X1there exists a directed path from xito some xj∈X2. This is denoted by X1CC −→ X2. Proposition 6 Let ¯ A∈ {0,1}n×nbe the structural pattern of some state matrix A and D(¯ A) = (X,EX,X)its associated directed graph. Let OC={I⊆X| I CC −→ X\I}. Then, M = (X,OC) is a matroid.  Proof The hereditary property is trivially verified. In order to prove the augmentation property, consider I,J∈OCsuch that |J|>|I|. Let xi∈J\I. Since xi∈J, there exists at least one xj∈X\J such that there is a directed path from xito xj. Now, there are two possibilities. If xj6∈ I, then we can add xito Isince xjremaining outside Iwill guarantee the path from xito xj. On the other hand, if xj∈I, then there exists another xk∈X\Isuch that xj→xkand since xi→xj, it must be by transitivity that xi→xk. Thus, I∪{xi} ∈ OCand the proposition is proved.  Definition 30 (Output-Connected Matroid) The matroid of Proposition 6will be referred as the output-connected matroid associated with the structural state matrix ¯ A.  Example 15 Consider the directed graph representation of a matrix ¯ A∈ {0,1}4×4, depicted in Figure 3.7, and whose vertex set is X={x1,x2,x3,x4,x5}. Let OC={I⊆X| I CC −→ X\I} be the collection of independent sets of the associated output-connected matroid. Notice that x2 cannot belong to any I ∈OC, because there is no state variable xi∈X, with i 6=2, such that there 36 Output Selection for Structural Observability Figure 3.7: A structural directed graph representation associated with an output-connected matroid M= (X,OC)where OC={I⊆X|ICC −→ X\I}. exists a directed path from x2to xi. Furthermore, we may write OCas OC={{x1}} ∪ {XS⊆ {x3,x4,x5}||XS|≤2}. Another necessary condition to satisfy structural observability is that the directed graph D(¯ A,¯ C) associated with the system must be free of contractions. Similar to the construction given in Definition 20, one can associate with ¯ Athe bipartite graph B(¯ A) = (X,X+,EX,X+), where X={x1,...,xn},X+={x+ 1,...,x+ n}and EX,X+={(xj,x+ i)|¯ Ai j =1}. Proposition 7 Let ¯ A∈ {0,1}n×nbe the structural pattern of some state matrix A and B(¯ A) = (X,X+,EX,X+)the associated bipartite graph. Let CFbe the collection of subsets I of Xfor which there exists a matching in B(¯ A)that covers I. Then, M = (X,CF)is a matroid.  Proof Consider that I∈CF. Then, for every subset Jof Ithere is also a matching that covers Jand therefore J∈CF. In order to prove the augmentation property, consider Theorem 7. Let I,J∈CFwith |J\I|=2 and |I\J|=1. We will apply induction on |I|to prove that there always exists xi∈J\Isuch that I∪{xi} ∈ CF. For the basis, let I\J=I={xα}. Since I∈CF, there exists an edge (xα,x+ α2)for some α2∈ {1,...,n}. Similarly, let J\I=J={xβ,xγ}. Since J∈CF, there must exist edges (xβ,x+ β2)and (xγ,x+ γ2)for appropriate β2,γ2∈ {1,...,n}with β26=γ2. Notice that α6=βand α6=γ. Considering, for instance, that β2might be equal to α2it is always possible to add the edge (xγ,x+ γ2)to the matching MIthat covered I. Therefore, I∪ {xγ} ∈ CF. On the other hand, if γ2=α2, then I∪{xβ}must belong to CF. Finally, if both β2and γ2are different from α2, then it is possible to add either {xβ}or {xγ}so that the augmented Iremains independent. For the inductive step, let |I|=kwith k>1. Then Jis comprised of k+2 elements and again we can consider that I\J={xα}, for α∈ {1,...,n}, with (xα,x+ α2)an edge of the matching that covers I. Let us take an edge (xβ,x+ β2)from the matching MJthat covers Jsuch that xβ∈J\I and x+ β26=x+ α2. Notice that such an edge must always exist since, by hypothesis, |J\I|>|I\J|. The vertex x+ β2may be covered or not by the matching of I. If x+ β2is not covered, then surely I∪{xβ} ∈ CF. On the other hand, if x+ β2is covered by MI, then there exists an edge (xi,x+ β2)∈MI with xi∈I∩J. Build the sets I0=I\ {xi}and J0=J\{xβ}and remove the vertex x+ β2from X+. Then, |I0|=k−1 and |I0\J0|=1 while |J0\I0|=2. Thus, by the induction hypothesis, there must exist xj∈J0\I0such that I0∪ {xj} ∈ CF. Notice that xjis either xior xγ, where xγis the other element of J\I. In the first case, we can add xβto I0∪{xi}=Iand we have I∪{xβ} ∈ CF. In the second case, we can simply add xito I0∪{xγ}and, therefore I∪{xγ} ∈ CF. 3.3 The Solution of the Output Selection Problem 37 Definition 31 (Contraction-free Matroid) The matroid of Proposition 7will be referred as the contraction-free matroid associated with the structural state matrix ¯ A.  According to the Output Selection Problem (3.4), an appropriate subset of state variables, SO⊆X, has to be selected in order to achieve structural observability. Remember that the output configuration is dedicated. Thus, if SO={xj1,...,xjp}then the matrix ¯ Ccan be written as ISO n where the latter is the identity matrix of order nbut only with rows j1,..., jp. Following the results from Proposition 6and Proposition 7, one can obtain the following. Theorem 12 Let ¯ A∈ {0,1}n×nbe the structural pattern of some state matrix A, X={x1,...,xn} the set of state variables and SO⊆Xa given dedicated output configuration. Additionally, let M1= (X,OC)and M2= (X,CF)be the output-connected and contraction-free matroids, respectively, associated with ¯ A. Then, the pair (¯ A,ISO n)is structurally observable if and only if X\SO∈OC∩CF.  Proof Let SO={xj1,...,xjp}be the dedicated output configuration. According to Theorem 5 the pair (¯ A,ISO n)is structurally observable if and only if the directed graph D(¯ A,ISO n)is outputconnected and free of contractions. Since outputs are placed in the state variables that belong to SO, obviously there is always a directed path between any xi∈SOand some output vertex, that is comprised of a single arc. Thus, testing for output-connectivity is restricted to the set X\SO, which has to belong to OCsuch that the pair (¯ A,ISO n)be output-connected. Regarding the contraction condition, note that as it was seen in Proposition 2, the system is free of contractions if and only if there exists a matching in the bipartite graph B(¯ A,¯ C) = (X−,X+∪Y,EX−,X+∪ EX−,Y)that covers X−. In order to maintain the previously used notation, relabel each x− i∈X− to xi. Since ¯ C=ISO n, for any xi∈SOthere is one and only one yjin Ysuch that (xi,yj)∈ EX−,Y. Thus, xican always be covered by the edge (xi,yj)and the existence of a matching that covers Xis equivalent to the existence of a matching in B(¯ A)that covers the state variables in X\SO. Therefore, X\SOmust belong to CF. Notice that, by similar arguments, if X\SO∈ OC∩CF, then we conclude that the pair (¯ A,ISO n)is at the same time output-connected and free of contractions. Therefore, by Theorem 5, the pair (¯ A,ISO n)is structurally observable.  With the previous theorem, all the feasible (in the sense that the system is structurally observable) dedicated output configurations can be written as the intersection of two matroids. Algorithm 4and Algorithm 5describe independence oracles associated with the output-connected and contraction-free matroids, respectively. At this point we are ready to solve the problem of, given the structural pattern ¯ A∈ {0,1}n×n of some state matrix A, find the minimum number of outputs and where to place them in order to achieve structural observability. The idea is to apply the matroid intersection algorithm (Algorithm 3) to M1= (X,OC)and M2= (X,OF)and the returned value will be a set I∗∈OC∩CFof 44 Output Selection for Structural Observability With the previous proposition, an efficient algorithm (see Algorithm 6) to find a maximumcardinality set that is independent in both the output-connected and contraction-free matroids can be constructed. Recall that a set I⊆Xbelongs to the collection of independent sets of the contraction-free matroid M2= (X,CF)if there exists a matching in B(¯ A) = (X,X+,EX,X+) that covers I. At the same time, we have to guarantee that Ibelongs to OCwhere OCis the collection of independent sets of the output-connected matroid, which is equivalent to say that at least one state variable per non-bottom SCC is left out of I(Proposition 8). With the previously considerations in mind, we can construct the following bipartite graph. Let B(¯ A) = (X,X+,EX,X+)be the bipartite graph associated with ¯ Aand let {X1,...,Xk}be the set of the the non-bottom SCCs resulting from the condensation of D(¯ A). For each non-bottom SCC Xi, we will introduce in Badummy variable z∗ i. Hereafter, we will consider the extended bipartite graph B∗(¯ A) = (X,X+∪Z∗,EX,X+∪EX,Z∗)where Z∗={z∗ 1,...,z∗ k}and EX,Z∗= {(xi,z∗ j)|xi∈Xi}. Additionally, we will consider the weight-function W:EX,X+∪EX,Z∗→N, where w(e) = 1 if e∈EX,X+and w(e) = n+1 if e∈EX,Z∗. In order to obtain a maximumcardinality set I∗in OC∩CF, one can compute a maximum-weight matching MWin B∗(¯ A). Let XM⊆Xbe the state variables covered by MW. To obtain I∗, we remove the state variables that are covered by an edge in EX,Z∗, i.e, I∗=XM\ {xi|(xi,z∗ j)∈MWfor some z∗ j∈Z∗}. In that manner, we always force the removal of at least one state variable per non-bottom SCC and we guarantee that the matching obtained is as maximum as possible. Algorithm 6can be easily modified in order to solve Problem 3.4, i.e., the problem of finding a minimum-cost feasible dedicated output configuration for a given cost function C:X→N+. The idea is to change the weight function in the third step. If e= (xi,x+ j)for some x+ j∈X+, then w(e) = C(xi). On the other hand, w(e) = ∑n i=1C(xi)+1 if e= (xi,z∗ j)for some z∗ j∈Z∗. Chapter 4 Output Selection Problem with Generic Observability Index Constraint In this chapter we analyze the output selection problem when we include a performance restriction given by the generic observability index. First, we will formulate the problem. Then, we will show that it is NP-complete. 4.1 Generic Observability Index: Problem Formulation Consider a network of nentities where each entity (denoted by xi) updates its data according to the linear dynamics x(t+1) = Ax(t), (4.1) where A∈Rn×nis the state matrix and x(t)∈Rnis the state vector. The goal is to design the output matrix C y(t) = Cx(t), (4.2) where y∈Rpis the output vector such that the pair (A,C)is observable. In the previous chapter, we developed a polynomial-time algorithm to solve the structural related problem (see Problem (3.4)) that consists of finding a minimum-size dedicated output configuration SO={xi1,...,xip}in order to guarantee structural observability. We could construct the pattern ¯ Cof the output matrix with ¯ C=ISO n, where ISO nis the identity matrix of size nwith rows i1,...,ip. Then, a numerical realization could be provided: A∈[¯ A]and C∈[¯ C]with (A,C) observable, where [¯ A]and [¯ C]are defined in Definition 4. Another far more difficult but more practical problem is when we also would like to impose some performance observability constraint. For example, when it is important to recover the initial state vector in the fewest iteration instant t∈Nas possible (e.g, a critical real-time network). As it was seen in Chapter 2, this constraint is directly related with the observability index µ, where µ is defined as µ(A,C) = min {k∈N|rank[O(k)] = n}, (4.3) 45 46 Output Selection Problem with Generic Observability Index Constraint where O(k)is the observability matrix at iteration instant k. Analogously, we can define the generic observability index µGas µG(¯ A,¯ C) = min {k∈N|grank[¯ O(k)] = n}, (4.4) where ¯ O(k) =       ¯ C ¯ C¯ A . . . ¯ C¯ Ak−1       (4.5) is the structural counterpart of the observability matrix at iteration instant k. Now, we can reformulate problem (3.4) that includes a performance constraint as follows. Output Selection Problem with Generic Index Constraint: Consider the system (4.1) and let X={x1,...,xn}be the set of state variables and ¯ A∈ {0,1}n×nthe structural pattern of A. The problem is to find, for a given k, with 1 ≤k≤n, the set of feasible dedicated output variables SO, with SO⊆X, that solves the following optimization problem: min I⊆{1,...,n}|SO|(4.6) s.t. µG(¯ A,ISO n)≤k where µG(¯ A,ISO n)is defined as in (4.4). Notice that for k=n(which is the same as for every k≥n) the problem is equivalent to find a minimum feasible dedicated output configuration whereas for the case k=1, the solution SOwill be the all set of state variables, X, which implies that we would have one output connected to each state. However, as we will demonstrate in the next section, problem (4.6) is NP-complete, notwithstanding the fact that some extreme cases are easy to solve. 4.2 Computational Complexity Analysis A computational problem P1is said to be polynomial-time reducible to another problem P2if there exists a procedure to transform P1into P2using a polynomial number of operations on the size of its inputs. More formally, P1polynomial reduces to P2, which we denote by P1≤PP2, if P1can be solved using a polynomial number of standard computational steps and a polynomial number of calls to an oracle that solves problem P2. In what follows we will consider for P1the set covering problem, which is a classic NPcomplete problem in combinatorics and computer science, and is described as follows. Set Covering Problem: Given a finite set U={a1,...,am}of melements (called universe) 4.2 Computational Complexity Analysis 47 and a collection S={S1,...,Sn}of nsubsets of Usuch that n [ i=1 Si=U, (4.7) the set covering problem aims to determine a set of indices I⊆ {1,...,n}that solves the following optimization problem: min |I|(4.8) s.t. [ i∈I Si=U The following result will be used in order to demontrate the NP-completeness of problem (4.6). Lemma 6 ([34]) If problem P1is NP-complete, problem P2is in NP and P1≤PP2, then P2 is NP-complete.  We will polynomial reduce the set covering problem to problem (4.6) in order to show the NP-completeness of the latter. Mainly, this suffices since problem (4.6) is in NP, given that there exists a polynomial algorithm to ascertain the satisfaction of the conditions on it. For that purpose, consider the following definitions and results. Definition 35 Consider an instance (U,S)of the set covering problem where U={a1,...,am}is the universe and S ={S1,...,Sn}is the collection of subsets of Usuch that Sn i=1Si=U. Let k = maxi|Si|and consider that k ≥2. With that instance, we define the directed graph DSCP(U,S) = (U∪S∗∪Sk,EU,U∪EU,S∗∪ES∗,Sk)given by U={a1,...,am}, S∗={S∗ 1,...,S∗ n}, Sk= n [ i=1 k−1 [ j=1 {si j}, EU,U={(ai,ai)|∀ai∈U}, EU,S∗={(ai,S∗ j)| ai∈Sj,∀ai∈U,∀Sj∈S}, ES∗,Sk={(S∗ i,si1)|∀Si∈S,∀si1∈Sk}∪{(si j,si(j+1))| i =1,...,n,j=1,...,k−2}.  Example 18 Consider the universe U={a1,a2,a3,a4}and the collection of subsets of Ugiven by S ={S1,S2,S3}where S1={a1,a2,a3}, S2={a2,a4}and S3={a3,a4}. Notice that S3 i=1Si= U. The construction given in Definition 35 is depicted in Figure 4.1. The following results establishes the relationship between the set covering problem and problem (4.6). 48 Output Selection Problem with Generic Observability Index Constraint Figure 4.1: A directed graph representation associated with the Set Covering Problem instance given in Example 18. Lemma 7 Consider an instance (U,S)of the set covering problem where U={a1,...,am}is the universe and S ={S1,...,Sn}is the collection of subsets of Usuch that Sn i=1Si=U. Let DSCP(U,S)be its associated directed graph as defined in Definition 35 and let I ={i1,...,il} be a set of indices with I ⊆ {1,...,n}. Additionally, let SO={s11,...,sn1,S∗ i1,...,S∗ il}. Then, Si∈ISi=Uif and only if µG(¯ A,ISO n)≤k, where ¯ A is the structural matrix associated with DSCP and k =maxi|Si|. Proof Consider the structural directed graph representation D1depicted in Figure 4.2. Notice that it suffices to place an output in x1to ensure that the generic observability index µGis less or equal than k. In fact, the structural pair (¯ A1,¯ C1)associated with D1is such that ¯ A1="0k−1,1Ik−1 001,k−1#, ¯ C1=h101,k−1i, where 0m,nis the m×nmatrix of zero entries and Imis the identity matrix of size m. Therefore, it is possible to see that grank             ¯ C1 ¯ C1¯ A1 . . . ¯ C1¯ Ak−1 1             =grank(Ik), and that µG(¯ A1,¯ C1) = k. Figure 4.2: A structural directed graph representation D1(¯ A,¯ C)for which µG(¯ A,¯ C) = k. 4.2 Computational Complexity Analysis 49 Figure 4.3: A structural directed graph representation D2(¯ A,¯ C)for which µG(¯ A,¯ C) = k. Consider now the structural directed graph representation D2of Figure 4.3 and consider that (¯ A2,¯ C2)is the associated structural pair such that ¯ A2=Ik, ¯ C2=h1 1 . . . 1i. Therefore, we have that grank             ¯ C2 ¯ C2¯ A2 . . . ¯ C2¯ Ak−1 2             =grank(1k,k), where 1k,kis the k×kmatrix whose entries are all equal to 1, and µG(¯ A2,¯ C2) = k. It is possible to see that any dedicated output configuration that ensures structural observability of DSCP has to be comprised of the variables s1(k−1),s2(k−1),...,sn(k−1)since those variables constitute non-bottom linked SCCs. Furthermore, the outputs placed in each of those variables are necessary and sufficient (see Figure 4.2) to ensure structural observability with generic index less than kof the directed graph whose vertex set is V1=S∗∪Skand whose arc set is E1=ES∗,Sk. By comparison with Figure 4.3, notice that to guarantee structural observability of DSCP with µGless than k, one has to start to add outputs in the variables in S∗. Furthermore, it may be easily verified that Si∈ISi=Uwith I={i1,...,il}if and only if the set of variables in S∗indexed by Iis sufficient to ensure a generic observability index less than kof the directed graph with vertex set V2=U∪S∗and arc set E2=EU,U∪EU,S∗. Since DSCP = (V1∪V2,E1∪E2), the lemma is proved.  Theorem 15 The output selection problem with generic index constraint (problem (4.6)) is NPcomplete.  Proof First, notice that problem (4.6) is in NP since for a structural pair (A,C)there exists a polynomial procedure to compute the generic observability index [22]. Therefore, it remains to show that there is a polynomial procedure that reduces the set covering problem to problem (4.6) and, by Lemma 6, the theorem is proved. 50 Output Selection Problem with Generic Observability Index Constraint For that, consider the directed graph construction given in Definition 35 (see also Algorithm 7). First, we call a procedure that solves problem (4.6) for the structural state matrix ¯ Aassociated with DSCP and let SObe a solution. We will show that from SOit is possible to construct a solution with the same number of outputs and with variables s1(k−1),...,sn(k−1)and variables in S∗. If there is a si j ∈SOwith j6=k−1, then the set SO\ {si j} ∪ {S∗ i}is certainly a solution to problem (4.6). Further, for each ai∈SO, there must exist an S∗ j6∈ SOwith (ai,SO)∈Eand with SO\ {ai} ∪ {S∗ j}a solution to problem (4.6). If this was not the case, then the number of outputs would not be minimal, which is a contradiction. Therefore, it is always possible to, given a solution SO, construct another solution S0 Owith variables si(k−1),i=1,...,n, and some variables from S∗. Then, with Lemma 7in mind, the theorem is proved.  For instance, notice that in Example 18 if we call the procedure to solve problem (4.6), SO= {s13,s23,s33,S∗ 1,a4}might be the returned value. Since (a4,S2)is an arc of the directed graph, S0 O={s13,s23,s33,S∗ 1,S∗ 2}is also a solution of problem (4.6) and, therefore, I={1,2}is a solution of the Set Covering Problem. 4.2 Computational Complexity Analysis 51 ALGORITHM 7: Reduction of the Set Covering Problem to Problem 4.6 Input: An instance of problem 4.8: an universe U={a1,...,am}and collection of subsets S={S1,...,Sn}of Uwhose union is U. Output: A set of indices I⊆ {1,...,m}that solves problem 4.8. Let kbe the size of the largest Si∈S, with i=1,...,n. Build the directed graph DSCP = (U∪S∗∪Sk,EU,U∪EU,S∗∪ES∗,Sk), where •U={a1,...,am} •S∗={S∗ 1,...,S∗ n} •Sk=Sn i=1Sk j=1si j •EU,U={(ai,ai)|∀ai∈U} •EU,S∗={(ai,S∗ j)|ai∈Sj,∀ai∈U,∀Sj∈S} •ES∗,Sk={(S∗ i,si1)|∀Si∈S,∀si1∈Sk}∪{(si j,si(j+1)|i=1,...,m,j=1,...,k−2} Call a procedure that solves problem 4.6 for DSCP and k. Let SObe the solution. I←/0 for si(k−1)∈SOdo SO←SO\{si(k−1)} end for for si j ∈SOdo SO←SO\{si j} I←I∪{i} end for for S∗ i∈SOdo SO←SO\{S∗ i} I←I∪{i} end for for ai∈SOdo Find j6∈ Isuch that (ai,S∗ j)∈EU,S∗ SO←SO\{ai} I←I∪ { j} end for Return I 52 Output Selection Problem with Generic Observability Index Constraint Chapter 5 Illustrative Examples In this chapter, we start by illustrating the concepts regarding matroid theory with an example. After that, the algorithm developed to find a minimum-cost feasible dedicated output configuration is applied to a spatially distributed sensor network. Finally, some simulation results are presented. 5.1 A 6-node Networked Example In this section, we apply the matroid intersection algorithm (Algorithm 3) in order to obtain a minimum dedicated output configuration that guarantees structural observability. Consider, for instance, the structural state matrix ¯ A=            101000 011000 000100 001011 000100 000100            , (5.1) that represents the zero/non-zero pattern of some real-valued matrix A∈Rn×n, with n=6. In Figure (5.1), we provide the structural directed graph representation D(¯ A) = (X,EX,X). When applying the matroid intersection algorithm, we have to consider the output-connected matroid M1= (X,OC)and the contraction-free matroid M2= (X,CF). Recall that a set I⊆X belongs to OCif and only if ICC −→ X\I, i.e, if for any xi∈I, there exists a directed path from xi to some xj∈X\I. On the other hand, I∈CF, if and only if there is a matching in the bipartite graph B(¯ A) = (X,X+,EX,X+)that covers I. Let us take, for instance, the set XA={x1,x2,x3,x4}of the right-covered vertices of Figure 5.2, where we can see the bipartite graph associated with ¯ Aand a maximum matching. By definition, XA∈CF. If XAalso belongs to the collection of independent sets of the output-connected matroid, then surely XAis a maximum-cardinality set in OC∩CFsince XAis covered by a maximum matching. To test that possibility, we will rely on the independence oracle for M1= (X,OC)(Algorithm 53 60 Illustrative Examples 5.3 Simulation Results of Random Networks In this section, we provide results of a set of MATLAB simulations in order to conclude about the following Q1: How does the presence/absence of zeroes in the structural pattern of some state matrix affect the minimum number of dedicated outputs to obtain structural observability? Further, how this conclusions change with the dimension of the system? Q2: Is the presence of self-loops an important requirement to reduce the number of required dedicated outputs to obtain structural observability? To that purpose, the following experiment was simulated. To each entry of ¯ A∈ {0,1}n×nthe value 1 was assigned with probability p, i.e., for each i,j=1,...,n ¯ Ai j =   1 with probability p, 0 with probability 1−p. Additionally, for each ¯ Aconstructed according to the previously manner, it was built two more structural matrices: one, with forced self-loops, i.e, with ¯ Aii =1 for i=1,...,n; and another with zero self-loops, i.e, with ¯ Ai j =0 for i=1,...,n. For each value of p, with p∈ {0.001,0.01,0.1,0,2,0.3,0.4,0.5,0.6,0.7,0.8,0.9}, the minimum number of dedicated outputs needed to ensure structural observability was computed for n=1,...,100. The simulation was realized 100 times. For small values of p(Figure 5.8 and Figure 5.9) the minimum number of dedicated outputs, nO, increases with the size of the structural state matrix, n. For pbetween 0.1 and 0.8 (Figures 5.10,5.11,5.12,5.13,5.14,5.15 and 5.16) there is a peak that corresponds to the maximum value of nOthat occurs for values of nsuccessively small until p=0.8,0.9 (Figures 5.17 and 5.18) for which that peak value is negligible. There is an abrupt decrease in nObetween p=0.001 and p=0.01 and between p=0.01 and p=0.1, and after that nOis always less than 6. Notice that for p≥0.2 and n≥10, the minimum number of dedicated outputs needed to obtain structural observability is approximately 1, regardless of the size of ¯ A. Furthermore, it can be concluded that the presence of self-loops is significant only for p=0.01 (Figure 5.9), where nOtakes as maximum approximately 45, whereas for the case with forced self-loops the maximum value of nOis approximately 35. For values of pinferior and superior than 0.01, the blue, red, and green curves almost overlap. 5.3 Simulation Results of Random Networks 61 0 10 20 30 40 50 60 70 80 90 100 0 10 20 30 40 50 60 70 80 90 100 n Avg. Number of Outputs p = 0.001 Unrestricted Forced Self−Loops Zero Self−Loops Figure 5.8: The average number of minimum dedicated outputs needed to ensure structural observability for p=0.001. 0 10 20 30 40 50 60 70 80 90 100 0 5 10 15 20 25 30 35 40 45 50 n Avg. Number of Outputs p = 0.01 Unrestricted Forced Self−Loops Zero Self−Loops Figure 5.9: The average number of minimum dedicated outputs needed to ensure structural observability for p=0.01. 62 Illustrative Examples 0 10 20 30 40 50 60 70 80 90 100 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 n Avg. Number of Outputs p = 0.1 Unrestricted Forced Self−Loops Zero Self−Loops Figure 5.10: The average number of minimum dedicated outputs needed to ensure structural observability for p=0.1. 0 10 20 30 40 50 60 70 80 90 100 1 1.2 1.4 1.6 1.8 2 2.2 2.4 2.6 2.8 n Avg. Number of Outputs p = 0.2 Unrestricted Forced Self−Loops Zero Self−Loops Figure 5.11: The average number of minimum dedicated outputs needed to ensure structural observability for p=0.2. 5.3 Simulation Results of Random Networks 63 0 10 20 30 40 50 60 70 80 90 100 1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 n Avg. Number of Outputs p = 0.3 Unrestricted Forced Self−Loops Zero Self−Loops Figure 5.12: The average number of minimum dedicated outputs needed to ensure structural observability for p=0.3. 0 10 20 30 40 50 60 70 80 90 100 1 1.05 1.1 1.15 1.2 1.25 1.3 1.35 1.4 1.45 1.5 n Avg. Number of Outputs p = 0.4 Unrestricted Forced Self−Loops Zero Self−Loops Figure 5.13: The average number of minimum dedicated outputs needed to ensure structural observability for p=0.4. 64 Illustrative Examples 0 10 20 30 40 50 60 70 80 90 100 1 1.05 1.1 1.15 1.2 1.25 1.3 1.35 1.4 n Avg. Number of Outputs p = 0.5 Unrestricted Forced Self−Loops Zero Self−Loops Figure 5.14: The average number of minimum dedicated outputs needed to ensure structural observability for p=0.5. 0 10 20 30 40 50 60 70 80 90 100 1 1.05 1.1 1.15 n Avg. Number of Outputs p = 0.6 Unrestricted Forced Self−Loops Zero Self−Loops Figure 5.15: The average number of minimum dedicated outputs needed to ensure structural observability for p=0.6. 5.3 Simulation Results of Random Networks 65 0 10 20 30 40 50 60 70 80 90 100 1 1.02 1.04 1.06 1.08 1.1 1.12 1.14 1.16 n Avg. Number of Outputs p = 0.7 Unrestricted Forced Self−Loops Zero Self−Loops Figure 5.16: The average number of minimum dedicated outputs needed to ensure structural observability for p=0.7. 0 10 20 30 40 50 60 70 80 90 100 1 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 n Avg. Number of Outputs p = 0.8 Unrestricted Forced Self−Loops Zero Self−Loops Figure 5.17: The average number of minimum dedicated outputs needed to ensure structural observability for p=0.8. 66 Illustrative Examples 0 10 20 30 40 50 60 70 80 90 100 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 n Avg. Number of Outputs p = 0.9 Unrestricted Forced Self−Loops Zero Self−Loops Figure 5.18: The average number of minimum dedicated outputs needed to ensure structural observability for p=0.9. Chapter 6 Conclusions Achievements In this thesis, we reformulated the minimum feasible dedicated output problem (3.4) within a matroid framework. We have shown that it was possible to reduce that problem to an intersection of two matroids. Next, after established the connection of the obtained results to graph-theoretic concepts, we provided a new algorithm to find a minimum feasible dedicated output configuration. These results were easily extended to the scenario where costs associated with the output allocation were considered. We have also proved that the output placement problem with generic observability index constraint (4.6) was NP-complete by a polynomial reduction of the well-known set covering problem to the first. By duality, the derived observability results can be readily extended to the structural controllability and the corresponding input (actuator) design. Future Work As part of future research, we believe that the matroid framework should be deeply studied in order to provide new results within structural systems theory. Another important future work is to try to reduce problem (4.6) to a well-known NP-complete problem that have good approximation algorithms. Thus, if the reduction is successful it would be possible to adapt such approximation algorithms to solve the original problem. Since problem (3.4) was formulated as the intersection of two matroids, perhaps problem (4.6) can be rewritten as an intersection of three matroids. It is known that the matroid intersection problem becomes NP-hard when three matroids are involved, instead of only two. 67 68 Conclusions Appendix A MATLAB implementation of some algorithms A.1 Maximum-Cardinality Matroid Intersection Algorithm 1function [ I ] = maxIntersectMatroid ( @oracle1 , @oracle2 , n ) ; 2%Inputs : 3% @oracle1 −Ind epen denc e o r a c l e o f t h e f i r s t m at ro id 4% @oracle2 −Ind ep en de ce o r a c l e o f t h e second ma tr oi d 5% n −s i z e o f t h e u n i v e s e r {1 , . . . , n } 6%Outputs : 7% I −A maximum−s i z e i n d e p e n d e n t s e t t h a t l i e s on t h e instersection of the 8% two m a t r o i d s g i v e n by i n de p e nd e n ce o r a c l e s @oracle1 and @oracle2 9 10 I = zeros (1 , n ) ; 11 12 while (1) 13 %C o n s t r u c t t h e s e t s X_1 and X_2 14 X_1 = zeros (1 , n ) ; 15 X_2 = zeros (1 , n ) ; 16 A = zeros ( n , n ) ; 17 18 for i = 1 : n 19 aux = zeros (1 , n ) ; 20 aux ( i ) = 1; 21 i f ( I ( i ) == 0) 22 X_1( i ) = oracl e 1 ( I + aux , n ) ; 69 76 REFERENCES [14] Sérgio Pequito, Soummya Kar, and A Pedro Aguiar. Minimum cost input-output and control configuration selection: A structural systems approach. In Decision and Control (CDC), 2013 IEEE 52nd Annual Conference on, pages 4895–4900. IEEE, 2013. [15] Hassler Whitney. On the abstract properties of linear dependence. American Journal of Mathematics, pages 509–533, 1935. [16] Jack Edmonds. Matroids and the greedy algorithm. Mathematical programming, 1(1):127– 136, 1971. [17] Kazuo Murota. Matrices and matroids for systems analysis, volume 20. Springer, 2000. [18] Andrew Clark, Linda Bushnell, and Radha Poovendran. On leader selection for performance and controllability in multi-agent systems. In CDC, pages 86–93, 2012. [19] Jean-Michel Dion, Christian Commault, and Jacob Van Der Woude. Generic properties and control of linear structured systems: a survey. Automatica, 39(7):1125–1144, 2003. [20] Airlie Chapman. Semi-Autonomous Networks: Effective Control of Networked Systems through Protocols, Design, and Modeling. PhD thesis, 2013. [21] H Mortazavian. On k-controllability and k-observability of linear systems. In Analysis and Optimization of Systems, pages 600–612. Springer, 1982. [22] C Sueur and G Dauphin-Tanguy. Controllability indices for structured systems. Linear algebra and its applications, 250:275–287, 1997. [23] Shreyas Sundaram and Christoforos N Hadjicostis. Structural controllability and observability of linear systems over finite fields with applications to multi-agent systems. Automatic Control, IEEE Transactions on, 58(1):60–73, 2013. [24] Chi-Tsong Chen. Linear system theory and design. Oxford University Press, Inc., 1998. [25] João P. Hespanha. Linear systems theory. Princeton university press, 2009. [26] John E. Hopcroft and Richard M. Karp. An nˆ5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 2(4):225–231, 1973. [27] Shigeyuki Hosoe. Determination of generic dimensions of controllable subspaces and its application. Automatic Control, IEEE Transactions on, 25(6):1192–1196, 1980. [28] Jack Edmonds. Matroid intersection. Annals of discrete Mathematics, 4:39–49, 1979. [29] James G Oxley. Matroid theory, volume 3. Oxford university press, 2006. [30] Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003. [31] Jon Lee. A first course in combinatorial optimization, volume 36. Cambridge University Press, 2004. [32] András Recski. Matroid theory and its applications in electric network theory and in statics. Springer, 1989. [33] Robert Tarjan. Depth-first search and linear graph algorithms. SIAM journal on computing, 1(2):146–160, 1972. REFERENCES 77 [34] Michael R Garey and David S Johnson. Computers and intractability, volume 29. wh freeman, 2002. [35] Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83–97, 1955.