Keywords: observabilité états-entrées (ISO), ISO structurelle, ISO fortement structurelle, graphes bipartites, couplages, liaisons, appariements restreints uniques, conception des observateurs, cybersécurité xxi ISO, structural ISO, strongly structural ISO, bipartite graphs, matchings, linkings, uniquely restricted matchings, observer design, cyber-security

This thesis deals with the notion of Input and State Observability (ISO) in linear network systems. One seeks graphical characterizations using the notion of structural (resp. s-structural) ISO. We first focus on linear time-invariant network systems, represented by fixed graphs, and provide characterizations for strong structural ISO. Thereafter, we turn our attention to linear time-varying network systems wherein we first narrow our attention to the particular case of fixed graphs (i.e., the structure of the graph remains fixed; the weights along the edges are allowed to vary, thereby giving rise to time-varying dynamics). We show that, under suitable assumptions on the structure of input, output and feedthrough matrices, ISO of a system is equivalent to observability of a suitably defined subsystem. Subsequently, we exploit this equivalence to obtain graphical characterizations of structural (resp. s-structural) ISO. Thereafter, for the LTV setting, we consider the more general case of time-varying graphs and furthermore make no assumptions on the structure of system matrices. We introduce two suitable descriptions of the whole collection of graphs, which are named as dynamic graph and dynamic bipartite graph. Two equivalent characterizations of structural ISO are then stated in terms of existence of a linking and a matching of suitable size in the dynamic graph and in the dynamic bipartite graph, respectively. For strongly structural ISO, we provide a sufficient condition and a necessary condition, both concerning the existence of a uniquely restricted matching of suitable size in the dynamic bipartite graph and in a subgraph of it. When there is no direct feedthrough of the input on the measurements, the two conditions can be merged to give rise to a necessary and sufficient condition. Finally, we present an unbiased recursive algorithm that simultaneously estimates states and inputs. We focus on delay-left invertible systems with intrinsic delay ≥ 1, where the input reconstruction is possible only by using outputs up to time steps later in the future. By showing an equivalence with a descriptor system, we state conditions under which the timevarying filter converges to a stationary stable filter, involving the solution of a discrete-time algebraic Riccati equation.

I would like to express my sincerest gratitude towards my advisors, Alain Kibangou and Federica Garin, for taking me on as their student, teaching me how to do research, but more importantly for your support, patience and guidance. I have benefited tremendously and learnt a great deal from our weekly interactions over the last few years. The fact that you minutely went through each and every detail of my drafts (papers, reports) and patiently provided constructive suggestions to improve the final product, is indeed very impressive. It is due to your encouragement and support that I could attend various conferences/summer schools, which, in turn, has aided my growth as a researcher. Thank you for everything! Next, I would like to thank Taha Boukhobza and Julien Hendrickx for their technical/pedagogical comments/discussions, which have helped in improving the quality of this manuscript. Thanks also to Sophie Achard, Guiseppe Notarstefano and Christian Commault for taking the time out to serve on my thesis committee. I would also like to thank Christian for his generosity with time and advice during my stay at Gipsa. I would like to thank Paolo Frasca, Maria-Laura Della Monache, Hassen Fouratti and all other members of NeCS for their camaraderie.

Prof. Henrik Sandberg invited me to give a talk at KTH, Sweden in May, 2018. It was a great learning experience for me and I thoroughly enjoyed the scientific discussions with other students and post-docs at KTH. Henrik, many thanks for this opportunity. I take this occasion to also thank Prof. Kanat Camlibel for suggesting interesting research directions during our meeting at Gipsa in September, 2018.

My sincerest thanks to Profs. Francois Meyer, Juan Restreppo and Lucy Pao at the University of Colorado, Boulder. Your invaluable advice, support and guidance has greatly benefited me over the years. In particular, a few years ago, Juan impressed upon me the upsides of attending seminars even if the topics were prima facie tangential to my areas of interest. This piece of advice has often motivated me to attend numerous talks in Gipsa and elsewhere. I am grateful to Myriam Ethienne for her help with the logistics of attending the EECI summer school; to Sonia Nogueria for efficiently arranging the travel and accommodation to various conferences, and to Martine Brossier and Fanny Soler for their help with the administrative tasks at Gipsa. Your help and kindness has made my stay here quite a pleasant one.

I have been fortunate to enjoy the friendship and company of my fellow PhD students in particular within Necs and in general within Gipsa. During my first two years here, Nicolas Espitia Hoyos was my frequent lunch partner. I greatly enjoyed discussing life, work and many other topics with him. I wish him all the best for the future. The same goes for Yashank Gupta, Miguel Davo and Andres Ladino. Andres, you are a great friend, muchas gracias for i ii everything! I would also like to thank Phong and Huong for introducing me to Vietnamese cuisine and also for their friendship in general. The Mexican crew-Raul, Juan, Jonathan, Josue-has been a regular source of amusing conversations. My little knowledge of Espaniol is due to your efforts. Many thanks to Jonathan for frequently inviting me to various parties at his place, and for making me feel welcome. Thanks also to Juan for frequently encouraging me to go running; I regret not having done so. Constantinos (Costas), it has been a real pleasure knowing you. Many thanks for educating me about Greek history and also for taking the time out to explain various concepts in mathematics. I wish you a fantastic career ahead! I thank Albin Augustin for regularly checking in on me, and for having maintained our friendship since elementary school. Also, I have tremendously benefited from the fantastic friendships formed during my years at Boulder. In particular, Sri Krishna Chaitanya Narapareddy (aka KC), for the numerous discussions we have had on life in general and food in particular; Alex Albert, for being a constant source of encouragement in all my endeavors; Yogesh Virkar, for the countless hours spent discussing the minutiae of Seinfeld; Bharat Hegde, who is my all-time favorite roommate; Abhishek Paul, Prashanth Prahladan, Sourav Srivastava and a few others.

I fondly recall my teachers in middle school and high school. In particular, I would like to thank Mrs. Sheela Mathews, who taught me through grades 7-10, for constantly encouraging me; Mrs. Treesa Sebastian, to whom I extremely thankful for giving me a solid grasp on the rules of English grammar-a skill that has greatly benefited me all through my life; Mrs. Preetha Nair, for being such a nice person. I am eternally grateful to each one of you; I remember you with great affection and apologize for not being in touch.

Philippe and Margueritte, my sincerest thanks for your friendship, the many dinner/lunch invitations and also for the oh-so-numerous interesting conversations especially the ones about the French education system. The kids, Gabriel et Laetitia, are fast growing up. It feels only like yesterday when I first met you guys on a cold December morning at Saint Luc in Ile Verte. Indeed, time flies! I wish you guys all the best for what lies ahead. Hopefully, we will continue to meet in future as well. Likewise to Paul and Marie-Liesse. I would also like to thank Madame Marie Francois, Madame Claire Baron and Madame Daniel Amblard for their kindness, pleasant conversations and lunch invitations. This journey would have been difficult without the support of my younger brother, Sachin Jose. I thank my parents, Jose Sebastian and Gracy Jose, for always being available for me; and for always being excited by my progress. I would like to conclude by thanking my wife, Nieves Crasto, for being by my side throughout this journey.

Notations

Some notations that would be used throughout this thesis are introduced here.

• R, R * and Z denote the set of real numbers, non-zero real numbers and integers respectively;

• e j;N represents the j th vector of the canonical basis of R N . Alternatively, assuming that the length is clear from context, we would denote the same as just e j ;

• I N denotes an identity matrix of size N ;

• [A] i,j denotes the entry in matrix A that corresponds to its i th row and j th column. rank(A) denotes the rank of a matrix A;

• Given two matrices A and B, let A B and A ⊗ B denote the entrywise product and Kronecker product respectively;

• A = diag(A 1 , A 2 , . . . , A N ) denotes a block diagonal matrix whose blocks along the diagonal are A 1 , A 2 , . . . , A n . In case A 1 = A 2 = . . . = A N , we get diag(A 1 , A 2 , . . . , A N ) = I N ⊗ A;

• A k } k 1 k 0 denotes a sequence of matrices A k , k = k 0 , k 0 + 1, • • • , k 1 ;
• |X | denotes cardinality of a set X ;

• a denotes the smallest integer greater than or equal to a;

• [k 0 , k 1 ] denotes the discrete interval k 0 , k 0 + 1, . . . , k 1 -1, k 1 ;

• a k 0 :k 1 denotes a (concatenated) vector

       a k 0 a k 0 +1 . . . a k 1 -1 a k 1       
• ker A and Im A denote the kernel and the range of a matrix A, and dim V denotes the dimension of a vector space V .

xi

Résumé détaillé

Contexte et Motivation de la thèse

Les résultats développés au cours de cette thèse pourraient trouver des applications dans l'analyse de la sécurité des systèmes cyber-physiques (CPS, de l'anglais Cyber-Physical Systems). Nous allons donc tout d'abord présenter ce que sont les CPS avec un focus sur les différents types d'attaques qu'ils peuvent subir.

Un CPS combine des composants de l'espace physique et du cyber-espace. Le contrôle/commande et la surveillance de tels systèmes se font en général via un système SCADA (Supervisory Control and Data Acquisition) [START_REF] Mo | Detecting integrity attacks on SCADA systems[END_REF]. La figure 3 présente une carte conceptuelle des CPS. Leur domaine d'application inclut les infrastructures critiques tels que les réseaux électriques, les réseaux de distribution d'eau et de gaz ainsi que les systèmes de santé, de contrôle aéroportuaires et autres. Actuellement ces systèmes se retrouvent dans toutes les couches socioéconomiques; d'où l'importance de veiller à ce que chaque sous-système fonctionne comme désiré. Cela implique de concevoir des systèmes en réseaux dont les propriétés de commandabilité et d'observabilité sont démontrables (voir, par exemple, [START_REF] Ji | Observability and estimation in distributed sensor networks[END_REF], [START_REF] Kibangou | Observability in connected strongly regular graphs and distance regular graphs[END_REF], [START_REF] Neave | Observability and coarse graining of consensus dynamics through the external equitable partition[END_REF], [START_REF] Parlangeli | On the reachability and observability of path and cycle graphs[END_REF])

Les CPS sont exposés à des vulnérabilités inhérentes à leur nature, contrairement aux systèmes de contrôle classiques. En effet, le recours aux réseaux de communication et aux protocoles de communication standard pour la transmission des mesures et des paquets de contrôle augmente la possibilité d'attaques externes [START_REF] Pasqualetti | Attack detection and identification in cyber-physical systems[END_REF]. Nous discuterons brièvement des différents types d'attaques externes auxquelles les CPS peuvent être soumis [START_REF] Teixeira | A secure control framework for resource-limited adversaries[END_REF][START_REF] Pasqualetti | Attack detection and identification in cyber-physical systems[END_REF]. Ces attaques peuvent être classées en trois catégories non exclusives : les attaques de confidentialité, les attaques d'intégrité et les attaques de disponibilité (voir Figure 4 [START_REF] Teixeira | A secure control framework for resource-limited adversaries[END_REF]). L'objectif des attaques de confidentialité est d'obtenir un accès non autorisé à l'information. De telles attaques nécessitent généralement au moins l'un des éléments suivants : connaissance a priori du modèle ; accès aux données de mesure et d'actionneur ; informations d'état complet. Ce type d'attaques a été étudié, par exemple, dans [START_REF] Roy | A decoupled feedback structure for covertly appropriating networked control systems[END_REF][START_REF] Pasqualetti | Cyber-physical attacks in power networks: Models, fundamental limitations and monitor design[END_REF][START_REF] Sundaram | A control-theoretic approach to disseminating values and overcoming malicious links in wireless networks[END_REF]. Les attaques de disponibilité visent à empêcher l'accès rapide aux fonctionnalités du système et aux données. C'est le cas par exemple des attaques par déni de service (DoS, de l'anglais denial of service) où l'adversaire cherche à entraver les canaux de communication (par exemple, entre le système et l'actionneur) et s'assure ainsi que les informations ne sont pas disponibles en temps voulu. Une telle entrave à la communication dans un système pourrait entraîner une instabilité dans le système, ce qui entraînerait à son tour un mauvais rendement. Les attaques DoS ont été étudiées dans [1,[START_REF] Dolk | Event-Triggered Control Systems Under Denial-of-Service Attacks[END_REF], entre autres. D'autre part, les attaques d'intégrité, également appelées attaques de tromperie, visent à mettre l'accent sur la fiabilité de l'information échangée entre les diverses composantes d'un système. Ceux-ci sont conçus de manière à atteindre les objectifs, économiques ou géopolitiques, de l'attaquant sans alerter l'opérateur du système. Par exemple, dans les réseaux électriques, l'estimation de l'état consiste à estimer des variables d'état inconnues en ayant recours à des xiii mesures de compteurs, et il existe des techniques pour manipuler les mesures de compteurs comme cela a été montré dans [START_REF] Liu | False data injection attacks against state estimation in electric power grids[END_REF]. En effet, de telles attaques peuvent avoir d'importantes ramifications économiques comme cela a été démontré lors de la panne d'électricité en Ukraine, en 2015 [START_REF] Liang | The 2015 ukraine blackout: Implications for false data injection attacks[END_REF].

Observabilité états-entrées

Les systèmes dynamiques peuvent être affectés par la présence d'entrées inconnues. Celles-ci peuvent représenter des erreurs de modélisations, des défauts, ou des attaques malveillantes [START_REF] Harish | Unbiased minimum-variance filtering for input reconstruction[END_REF]. La reconstruction des entrées inconnues fait référence à la capacité d'un système à reconstituer une séquence d'entrées inconnues jusqu'à un certain délai en utilisant les mesures de la sortie et la connaissance de l'état initial. Dans le contexte des systèmes en réseau, la

Résumé détaillé xv

Figure 2: Différents tyoes d'attaques visant les CPS [START_REF] Teixeira | A secure control framework for resource-limited adversaries[END_REF] notion de reconstruction des entrées inconnues trouve son application dans divers contextes: dans les réseaux sociaux, une fraction des agents étant des leaders et le reste étant des suiveurs, l'influence du leader sur la dynamique du suiveur peut être vue comme une entrée inconnue. L'estimation d'une telle entrée permet alors de quantifier l'influence d'un leader donné sur le réseau. Dans les CPS, l'injection de données erronées sur les signaux d'actionneur et de capteur [START_REF] Zheng | Switching and Data Injection Attacks on Stochastic Cyber-Physical Systems: Modeling, Resilient Estimation and Attack Mitigation[END_REF] peut être représentée par des entrées inconnues. Ce dernier cas est particulièrement préoccupant, car de telles attaques (éventuellement) locales sur les CPS ont des conséquences non négligeables [START_REF] Pasqualetti | Control-theoretic methods for cyberphysical security: Geometric principles for optimal cross-layer resilient control systems[END_REF] comme en témoigne les pannes sur le système de gestion des eaux usées de Marochy en Australie au début des années 2000 [START_REF] Slay | Lessons learned from the Maroochy water breach[END_REF] ainsi que les coupures de courant massives au Brésil [START_REF] Juan | The day the samba stopped[END_REF]. Ces exemples illustrent l'existence de scénarios dans lesquels il est essentiel de reconstruire non seulement le vecteur d'état d'un réseau, mais également les entrées inconnues qui l'affectent. Dans la terminologie de la théorie des systèmes, le problème de la reconstruction à la fois de l'état initial et de l'entrée inconnue, est appelé observabilité des entrées et des états (ISO). Les caractérisations algébriques de l'ISO peuvent être trouvées dans [hautus1983strong, kitanidis1987unbiased]). L'objectif principal de cette thèse est de trouver des caractérisations graphiques pour l'ISO. Tout au long de cette thèse, le terme "ISO" signifie ISO avec délai -1. Autrement dit, étant donné une séquence de sorties {y 0 , y 1 , . . . , y N }, l'objectif est de reconstruire x 0 et la séquence des entrées inconnues {u 0 , . . . , u N -1 }. La notion d'ISO revêt une importance particulière dans la conception de filtres de variance minimale non biaisés qui simultanément estiment à la fois les états et les entrées inconnus [START_REF] Hsieh | Robust two-stage Kalman filters for systems with unknown inputs[END_REF][START_REF] Gillijns | Unbiased minimum-variance input and state estimation for linear discrete-time systems[END_REF][START_REF] Zheng | A unified filter for simultaneous input and state estimation of linear discrete-time stochastic systems[END_REF]. Notez que la propriété ISO permet de reconstruire des attaques malveillanteset/ou des défauts, modélisés comme des entrées inconnues. Une application des résultats cette thèse est donc liée à la sécurité des CPS. Pour les systèmes linéaires invariant dans le temps (LTI), la commandabilité structurelle ou la notion duale d'observabilité ont été étudiés depuis les années 70 [START_REF] Lin | Structural controllability[END_REF]. La caractérisation graphique de la commandabilité s-structurelle a quant à elle été étudiée dans [START_REF] Mayeda | Strong structural controllability[END_REF]. Dans [START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF], la caractérisation graphique de l'observabilité est présentée tout en analysant les problèmes de rejet de perturbations, et de découplage entrées-sorties, etc. Les caractérisations équivalentes pour la commandabilité s-structurelle ont été fournies dans [START_REF] Christian | Strong structural controllability of linear systems revisited[END_REF]. Plus récemment, pour la commandabilité s-structurelle, [START_REF] Chapman | On strong structural controllability of networked systems: a constrained matching approach[END_REF] fournit des conditions nécessaires et suffisantes en termes de couplage uniquement restreint (pour une définition précise, voir Définition (9)) alors que [START_REF] Trefois | Zero forcing number, constrained matchings and strong structural controllability[END_REF] le fait en termes d' textit ensembles de forçage à zéro.

Contrairement à l'observabilité structurelle (et s-structurelle), la littérature sur l'ISO structurelle (et s-structurelle) est plutôt mince. Pour les systèmes de réseau LTI à temps continu,

Résumé détaillé

xvii une caractérisation graphique de l'ISO structurelle a été donnée dans [5], bien que ces conditions traduites en temps discret conduisent à une caractérisation de l'ISO structurel avec un retard inconnu -et pas nécessairement un retard de 1. Face à cet inconvénient, pour les systèmes en réseau LTI à temps discret, une caractérisation graphique pour ISO structurelle a été récemment fournie dans [START_REF] Garin | Structural Delay-1 Input-and-State Observability[END_REF], mais la question suivante demeure:

P1: Quelles sont les conditions graphiques sous lesquelles une famille de systèmes LTI possède la propriété ISO s-structurelle?

Rappelons que la configuration ci-dessus concerne les systèmes LTI, où les paramètres et la structure restent constants au fil du temps. En revanche, il est naturel de supposer que les paramètres peuvent évoluer au fil du temps alors que la structure reste fixe (LTV avec topologie fixe). Autrement dit, les paramètres libres sont autorisés à évoluer dans le temps, tandis que la structure reste fixe (la position des zéros reste inchangé). Dans un tel scénario, les conditions nécessaires et suffisantes pour l'observabilité structurelle des systèmes LTV sont données dans [START_REF] Poljak | On the generic dimension of controllable subspaces[END_REF] alors que les conditions nécessaires et suffisantes pour l'observabilité s-structurelle sont disponibles dans [START_REF] Reissig | Strong structural controllability and observability of linear time-varying systems[END_REF]. Cependant, ces conditions (c.-à-d. Celles de [START_REF] Poljak | On the generic dimension of controllable subspaces[END_REF] et de [START_REF] Reissig | Strong structural controllability and observability of linear time-varying systems[END_REF]) ne conviennent pas aux systèmes avec des entrées inconnues. Par conséquent, nous posons les questions suivantes:

P2: Quelles sont les conditions graphiques selon lesquelles une famille de systèmes LTV, représentés par des graphes fixes, possède la propriété ISO structurelle?

P3: Quelles sont les conditions graphiques selon lesquelles une famille de systèmes LTV, représentés par des graphes fixes, possède la propriété ISO s-structurelle?

Un autre inconvénient de la littérature existante est qu'elle se concentre sur les topologies invariantes dans le temps. Cependant, en réalité, on peut trouver des réseaux qui présentent un comportement variable dans le temps. Par exemple, dans les réseaux sociaux, les individus ne sont en contact que pour un intervalle de temps fini, et ces relations sont souvent intermittentes et récurrentes [START_REF] Holme | Network reachability of real-world contact sequences[END_REF], tandis que dans les réseaux de communication, transmission en rafale, perte de paquets, variation de canal paramètres etc., entraîne une communication intermittente [START_REF] Li | Consensus conditions of multi-agent systems with timevarying topologies and stochastic communication noises[END_REF] qui conduit à des changements dans la topologie de ces réseaux. La littérature dédiée à l'estimation entrée-état avec un retard d'un pas peut être divisée en deux catégories. La première considère les systèmes pour lesquels les entrées n'influencent pas directement les sorties. Un algorithme centralisé, permetant l'estimation des états au sens du minimum de variance sans biais a été proposé dans [START_REF] Gillijns | Unbiased minimum-variance input and state estimation for linear discrete-time systems[END_REF], tandis qu'une version distribuée a été proposée dans [3]. La seconde catégorie considère une influcence directe des entrées sur les sorties. Pour un retard d'un pas, un estimateur au sens du minimum de variance sans biais en considérant un effet réversible des entrées sur les sorties (matrice de rang colonne plein) a été étudié dans [START_REF] Gillijns | Unbiased minimum-variance input and state estimation for linear discrete-time systems with direct feedthrough[END_REF]. La contrainte de rang a été relaxée dans [START_REF] Zheng | A unified filter for simultaneous input and state estimation of linear discrete-time stochastic systems[END_REF].

Par ailleurs, l'effet de l'entrée inconnue sur les sorties peut ne pas être immédiat, c'est-à-dire qu'il peut y avoir un délai, pas nécessairement un pas de temps, entre l'injection d'entrée et son effet mesurable, dû à la distance entre états affectés et les capteurs. Un tel délai doit être pris en compte dans l'estimation. En cas d'absence de couplage direct entre les sorties et les entrées, dans [START_REF] Roshan A Chavan | Recursive input reconstruction with a delay[END_REF], le cas d'un délai arbitraire a été pris en compte, sous certaines hypothèses restrictives sur les matrices du système. Pour les couplages non-nuls, pour le cas plus général de > 1, [START_REF] Kirtikar | L-delay input and initial-state reconstruction for discrete-time linear systems[END_REF] et [START_REF] Zheng | Simultaneous input and state estimation with a delay[END_REF] À notre connaissance, les questions (P1-P6) sont encore ouvertes. Cette thèse a pour objectif de répondre à ces questions. Les solutions apportées sont énumérées ci-dessous.

Contributions et structure de la thèse. [START_REF] Commault | Characterization of generic properties of linear structured systems for efficient computations[END_REF], [START_REF] Chapman | On strong structural controllability of networked systems: a constrained matching approach[END_REF] , [START_REF] Chapman | On strong structural controllability of networked systems: a constrained matching approach[END_REF] et [START_REF] Trefois | Zero forcing number, constrained matchings and strong structural controllability[END_REF]). Ce chapitre répond aux questions P2 et P3. Ensuite, pour la configuration du LTV, nous considérons le cas plus général des graphes variant en temps tout en ne faisant aucune hypothèse sur la structure des matrices du système.

Introduction

Context and Motivation

The theoretical results developed during the course of this thesis could potentially find applications in security of cyber-physical systems (CPS). Hence, in the rest of this section, we shall detail CPS and thereafter provide an overview of various kinds of external attacks on CPS.

A CPS combines elements from the physical space and the cyber space, and is controlledmoved from one state to another state using a suitable input signal -and monitored -uniquely recovering the state of the systems from sensor measurements -by a supervisory control and data acquisition (SCADA) system [START_REF] Mo | Detecting integrity attacks on SCADA systems[END_REF]. A concept map of CPS is given in Figure 3. Their fields of application span from critical infrastructure domains such as power networks, water and gas distribution networks to health-care systems, flight control systems among others. Given the ubiquitous nature of their usage, it is of paramount importance to ensure that each individual subsystem functions as desired. The idea of achieving system-theoretic properties like controllability and observability in network systems has recently drawn the attention of control-theorists (see, for instance, [START_REF] Ji | Observability and estimation in distributed sensor networks[END_REF], [START_REF] Kibangou | Observability in connected strongly regular graphs and distance regular graphs[END_REF], [START_REF] Neave | Observability and coarse graining of consensus dynamics through the external equitable partition[END_REF], [START_REF] Parlangeli | On the reachability and observability of path and cycle graphs[END_REF]).

CPS are exposed to certain vulnerabilities which classical control systems are not. Indeed, the reliance of CPS on communication networks and standard communication protocols to transmit measurements and control packets increases the possibility of intentional and worstcase attacks against physical plants [START_REF] Pasqualetti | Attack detection and identification in cyber-physical systems[END_REF]. We shall briefly discuss the different kinds of external attacks that CPS can be subjected to by recalling the relevant literature from [START_REF] Teixeira | A secure control framework for resource-limited adversaries[END_REF][START_REF] Pasqualetti | Attack detection and identification in cyber-physical systems[END_REF]. Attacks can be broadly classified into three non-exclusive categories: confidentiality attacks, integrity attacks and availability attacks (see Figure 4 [82]). The objective of confidentiality attacks is to attain unauthorized access to information. Such attacks usually require at least one of the following: a priori knowledge of the model; access to measurement and actuator data; full-state information, and these have been studied in, for instance, [START_REF] Roy | A decoupled feedback structure for covertly appropriating networked control systems[END_REF][START_REF] Pasqualetti | Cyber-physical attacks in power networks: Models, fundamental limitations and monitor design[END_REF][START_REF] Sundaram | A control-theoretic approach to disseminating values and overcoming malicious links in wireless networks[END_REF]. Availability attacks seek to prevent timely access to data or system functionalities. For example, Denial of Service (DoS) attacks: the adversary seeks to hinder the communication channels (for instance, between plant and actuator) and thereby ensures that timely information is unavailable. Such hindered communication in a system could lead to instability being induced in the system, in turn leading to poor performance. DoS attacks have been studied in, among others, [1,[START_REF] Dolk | Event-Triggered Control Systems Under Denial-of-Service Attacks[END_REF].

On the other hand, integrity attacks, also referred to as deception attacks, target the trustworthiness of the information being exchanged between various components of a system. These are designed in such a manner so as to achieve the objectives-ranging from economic ones to geopolitical ones-of the attacker but without alerting the systems operator. For instance, in power grids state estimation entails estimating unknown state variables by taking recourse Figure 3: Concept map of CPS to meter measurements, and there exists techniques to manipulate meter measurements as was shown in [START_REF] Liu | False data injection attacks against state estimation in electric power grids[END_REF]. Indeed, such attacks can have significant economic ramifications as was evidenced during the Ukranian blackout, in 2015 [START_REF] Liang | The 2015 ukraine blackout: Implications for false data injection attacks[END_REF].

Input and State Observability

Dynamical systems could be affected by the presence of unknown inputs. Such unknown inputs could encompass unmodeled parts of a system, faults or malicious attacks [START_REF] Harish | Unbiased minimum-variance filtering for input reconstruction[END_REF]. Indeed, in CPS, false data injection on actuator and sensor signals [START_REF] Zheng | Switching and Data Injection Attacks on Stochastic Cyber-Physical Systems: Modeling, Resilient Estimation and Attack Mitigation[END_REF] can be represented by unknown inputs. This is of particular concern, since such (possibly) local attacks on CPS have nontrivial consequences [START_REF] Pasqualetti | Control-theoretic methods for cyberphysical security: Geometric principles for optimal cross-layer resilient control systems[END_REF] as evidenced by the failure of wastewater management systems in Marochy Australia in early 2000 [START_REF] Slay | Lessons learned from the Maroochy water breach[END_REF], multiple power blackouts in Brazil [START_REF] Juan | The day the samba stopped[END_REF], among others. These examples illustrate that there exist scenarios wherein it is essential to reconstruct not only the state vector of a network but also the unknown inputs affecting it2 . In systems theory terminology, the problem of reconstructing both the initial state and the unknown input, is referred to as input and state observability (ISO). Throughout this thesis, the term "ISO" stands for ISO with delay-1. That is, given a sequence of outputs {y 0 , y 1 , . . . , y N }, the objective is to reconstruct x 0 and the sequence of unknown inputs {u 0 , . . . , u N -1 }. The notion of ISO is of particular importance in designing unbiased minimum-variance filters that simultaneously estimate both state and unknown input [START_REF] Hsieh | Robust two-stage Kalman filters for systems with unknown inputs[END_REF][START_REF] Gillijns | Unbiased minimum-variance input and state estimation for linear discrete-time systems[END_REF][START_REF] Zheng | A unified filter for simultaneous input and state estimation of linear discrete-time stochastic systems[END_REF]. Note that the property of ISO allows one to reconstruct malicious attacks, modeled as unknown inputs 3 . The bulk of the work contained in this thesis could, under such a setting, potentially find application in security of CPS.

Need for Graphical Characterizations

It is well-known that algebraic approaches towards characterizing observability (and also controllability) involve the classic Kalman rank condition or the Popov-Belevitch-Hautus (PBH) test. Both tests require exact knowledge of entries in the matrices of interest and are computationally heavy as the dimension of the system grows, while the latter is not suitable for linear time-varying (LTV) systems. This leads to the study of observability based on the structure of the underlying network (represented by a graph) and the corresponding line of work is known as structured systems. In such systems, the system matrices have fixed zero patterns. Intuitively, one may think of presence (resp. absence) of fixed zeros as absence (resp. presence) of connections between components of a system. The positions that are not fixed to zero are referred to as free parameters. Each numerical realization of the free parameters yields a new system, and one may think of such a collection of systems as a family of systems wherein each member in this family has the same pattern of fixed zeros. Under such a setting, on the one hand, one seeks structural results i.e., results that are true for almost all choices, where "almost all" means for all choices of free parameters except for those (possibly) lying on an algebraic variety of the space of free parameters [START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF]. Since a proper algebraic variety has Lebesgue measure zero, a probabilistic interpretation is the following: assuming that the free parameters are chosen at random from a continuous distribution, a property being structural implies that each member in a given family of systems has the said property with probability one. On the other hand, there exists yet another line of work where one wants to ensure that results are true for all non-zero choice of free parameters, referred to as strongly structural (s-structural) results. Notice that, under such a setting, each and every element in a vector of free parameters should be non-zero. The key difference between structural and s-structural properties is that the former yields probabilistic results, whereas the latter provides deterministic results. A structured system can be represented by a graph, where the presence of free parameters in the system matrices are equivalent to the existence of edges on the said graph. In the sequel, a numerical choice of free parameters is to be regarded as a choice of edge weight, and hence the terms "free parameters" and "edge weights" are used interchangeably, depending on the context.

For linear time-invariant (LTI) systems, structural controllability or the dual notion of observability has been studied since [START_REF] Lin | Structural controllability[END_REF] while graph-theoretic characterizations for s-structural controllability were first provided in [START_REF] Mayeda | Strong structural controllability[END_REF]. The survey paper [START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF] revises some graph-theoretic characterizations for observability in addition to recalling similar conditions for solvability issues like disturbance rejection, input-output decoupling, and so on, while equivalent characterizations for s-structural controllability have been provided in [START_REF] Christian | Strong structural controllability of linear systems revisited[END_REF]. More recently, for s-structural controllability, [START_REF] Chapman | On strong structural controllability of networked systems: a constrained matching approach[END_REF] provides necessary and sufficient conditions in terms of uniquely restricted matching (for a precise definition, see Definition (9)) while [START_REF] Trefois | Zero forcing number, constrained matchings and strong structural controllability[END_REF] does so in terms of zero forcing sets.

In contrast to structural (and s-structural) observability, the literature on structural (and s-structural) ISO is rather thin. For continuous time LTI network systems, a graphical characterization for structural ISO was given in [5], although these conditions when translated to a discrete-time setting yields structural ISO but with some unknown delay and not necessarily delay 1. ISO, with delay-1, is particularly important in the design of unbiased minimumvariance filters that estimate both the state and the sequence of unknown inputs (see [START_REF] Gillijns | Unbiased minimum-variance input and state estimation for linear discrete-time systems[END_REF]). For discrete-time LTI network systems, a graphical characterization for structural ISO has been recently provided in [START_REF] Garin | Structural Delay-1 Input-and-State Observability[END_REF], yet the following question remains: P1: What are the graphical conditions under which a family of LTI systems has the property of s-structural ISO?

Recall that the setting above is for LTI systems, where both parameters and the structure remain constant over the time. In contrast, it is natural to assume that the parameters can evolve over the time while the structure remains fixed (LTV with fixed topology). That is, the free parameters are allowed to evolve with respect to time, while the structure remains fixed (the fixed zero positions remain unchanged). Under such a scenario, necessary and sufficient conditions for structural observability of LTV systems are given in [START_REF] Poljak | On the generic dimension of controllable subspaces[END_REF] while necessary and sufficient conditions for s-structural observability are available in [START_REF] Reissig | Strong structural controllability and observability of linear time-varying systems[END_REF]. However, under such a setting, graphical conditions for the problem of structural (resp. s-structural) ISO are as yet unavailable. This prompts us to ask the following questions: P2: What are the graphical conditions under which a family of LTV systems, represented by fixed graphs, has the property of structural ISO?

P3: What are the graphical conditions under which a family of LTV systems, represented by fixed graphs, has the property of s-structural ISO?

Yet another drawback with the extant literature is that it is focused on time-invariant topologies. However, in reality, one can find networks that exhibit time-varying behavior. For instance, in social networks, the individuals are in contact with each other only for a finite time interval, and such relationships are often intermittent and recurrent [START_REF] Holme | Network reachability of real-world contact sequences[END_REF], whereas in communication networks, bursty transmission, packet loss, variation of channel parameters etc., results in intermittent communication [START_REF] Li | Consensus conditions of multi-agent systems with timevarying topologies and stochastic communication noises[END_REF] which leads to changes in the topology of such networks. This motivates us to turn our attention to time-varying topologies. Subsequently, we ask the following questions:

P4: What are the graphical conditions under which a family of LTV systems, represented by (possibly) time-varying graphs, has the property of structural ISO?

P5: What are the graphical conditions under which a family of LTV systems, represented by (possibly) time-varying graphs, has the property of s-structural ISO?

Note that the questions raised insofar are from a characterization point of view, and they deal with noiseless settings, as is standard in the literature. ISO, it should be recalled, is a property of the system. The fact that a system is ISO tells us that we can reconstruct both state and unknown inputs. However, it does not tell us how this reconstruction can be done. Moreover, in many practical settings, the states and measurements may be corrupted due to noise. The literature for delay-1 input and state estimation can be divided into two categories. The first one considers systems for which there is no direct feedthrough between the input and output. An algorithm, which yields minimum-variance unbiased (MVU) estimates of state and unknown input, with delay 1, was given in [START_REF] Gillijns | Unbiased minimum-variance input and state estimation for linear discrete-time systems[END_REF] in a centralized way, while a distributed version was proposed in [3]. The second category considers direct feedthrough between the unknown input and the output. For delay 1, an MVU estimator with a feedthrough matrix Introduction having full column rank was studied in [START_REF] Gillijns | Unbiased minimum-variance input and state estimation for linear discrete-time systems with direct feedthrough[END_REF]. The full rank requirement was relaxed in [START_REF] Zheng | A unified filter for simultaneous input and state estimation of linear discrete-time stochastic systems[END_REF].

On the other hand, the effect of the unknown input on the outputs might not be immediate, that is, there might be a delay, not necessarily of one time step, between the input injection and its measurable effect, due to the distance between the affected states and the sensors. Such delay needs to be considered in the estimation: at time k, when output measurement y h is available for all h ≤ k, one cannot estimate input u h and state x h for all h ≤ k, but rather can estimate input for h ≤ k and state for h ≤ k + 1. For zero feedthrough, in [START_REF] Roshan A Chavan | Recursive input reconstruction with a delay[END_REF] the case of an arbitrary delay was considered, under some restrictive assumptions on the system matrices. For non-zero feedthrough, for the more general case of > 1, [START_REF] Kirtikar | L-delay input and initial-state reconstruction for discrete-time linear systems[END_REF] and [START_REF] Zheng | Simultaneous input and state estimation with a delay[END_REF] study the conditions for existence of a state and input estimator with delay , and the latter proposes an algorithm, but for the particular case of = 1. Hence, we pose the following question:

P6: For LTI systems with arbitrary feedthrough, how does one recursively estimate state and (unknown) inputs with delay-?

To the best of our knowledge, none of these questions (P1-P6) have been answered previously. Against this backdrop, we briefly highlight the main contributions of this thesis.

Contributions and structure of the thesis 1. The first main contribution of this thesis is in response to question P1 , and it is dealt with in Chapter 2. Given a LTI network system and its corresponding graph, say G, we associate a bipartite graph, say H, to it. Thereafter, we appropriately define yet another bipartite graph, say H × . We provide, in terms of existence of uniquely restricted matchings on H and H × , a necessary condition and a sufficient condition for s-structural ISO. Under suitable assumptions on the feedthrough matrix, we show that these two conditions can be combined so as to obtain a graphical characterization for s-structural ISO.

2. In Chapter 3, we deal with LTV network systems represented by fixed topology. Under suitable assumptions on the structure of the input and output matrices, first we show equivalence between ISO of a linear system and observability of a suitably defined subsystem. Second, we give a characterization of uniform N -step structural (resp. uniform N -step strongly structural) input and state observability, i.e., the conditions under which both the whole network state and the unknown input can be reconstructed for almost all (resp. all ) system matrices that share a common zero/non-zero pattern, over every time window of length N . Note that the notion of uniform N -step ISO gets rid of the dependency on a given interval, while the equivalence with structural (resp. s-structural) observability enables one to study structural (resp. s-structural) ISO using the graph techniques given in [START_REF] Commault | Characterization of generic properties of linear structured systems for efficient computations[END_REF], [START_REF] Chapman | On strong structural controllability of networked systems: a constrained matching approach[END_REF] (resp. [START_REF] Chapman | On strong structural controllability of networked systems: a constrained matching approach[END_REF], [START_REF] Trefois | Zero forcing number, constrained matchings and strong structural controllability[END_REF]). This answers questions P2 and P3.

3. The findings in Chapter 3 have certain limitations. First, some assumptions are made on the structure of input and output matrices. As a consequence of such assumptions, the problem of ISO is equivalent to an observability problem of a suitably defined subsystem. Thereafter, one takes advantage of this equivalence to study structural (resp. s-structural) ISO. However, the extension of these results accounting for arbitrary structure of input and output matrices is non-trivial, since one cannot rephrase ISO as an equivalent problem in observability. Second, these results do not extend immediately to the case wherein the topology of the network varies over an interval.

In Chapter 4, we focus on LTV network systems but with time-varying topology. Evolution of such systems can be represented by a collection of graphs {G k }. We find conditions under which the system with a pattern of fixed zeros imposed by {G k } is ISO: a) for almost all choices of edge weights in {G k } (structural ISO); and b) for all non-zero choices of edge weights in {G k } (strongly structural ISO). We introduce two suitable descriptions of the whole collection of graphs {G k } named as dynamic graph and dynamic bipartite graph. Two equivalent characterizations of structural ISO are then stated in terms of existence of a linking and a matching of suitable size in the dynamic graph and in the dynamic bipartite graph, respectively. For strongly structural ISO, we provide a sufficient condition and a necessary condition, both concerning the existence of a uniquely restricted matching of suitable size in the dynamic bipartite graph and in a subgraph of it. When there is no direct feedthrough of the input on the measurements, the two conditions can be merged to give rise to a necessary and sufficient condition. This answers questions P4 and P5.

4. In Chapter 5, we consider linear network systems with unknown inputs. We present an unbiased recursive algorithm that simultaneously estimates states and inputs. We focus on delay-left invertible systems with intrinsic delay ≥ 1, where the input reconstruction is possible only by using outputs up to time steps ahead. That is, we provide a recursive linear algorithm for estimating both states and inputs with delay-: at time k, given output measurements up to y k , an estimate of u k-and x k-+1 is obtained. This answers question P6. By showing an equivalence with a descriptor system, we state conditions under which the time-varying filter converges to a stationary stable filter, involving the solution of a discrete-time algebraic Riccati equation.

Chapter 1

Preliminaries

Introduction

In this chapter, we first recall some definitions that are used throughout this thesis. Thereafter, we provide algebraic characterizations of ISO. Given that the focus is on graphical characterizations of ISO, we familiarize ourselves with the notions of structured systems, structural properties. Since structured systems can be represented by graphs, various notions from graph-theory are frequently used in this thesis, and therefore, we shall also discuss the same.

General setup

Consider a discrete-time linear network of N nodes whose dynamics are influenced by themselves and also by a a set of P external unknown inputs, and whose measurements are taken from a set of M nodes. These nodes are referred to as state, input and output nodes, respectively, and the corresponding sets, are respectively denoted by X, U and Y . Let G W k = (X, E W k ) be the graph representing the interaction between state vertices at time instant k;

E W k = {(j, i) ∈ X × X | [A W k ] ij = 1}; A W k being the associated adjacency matrix. Let F 1 k = (U, X, E B k ), F 2 k = (X, Y, E C k ) and F 3 k = (U, Y, E D k )
be the bipartite graphs that captures the interaction between the unknown inputs and states, states and outputs, and the unknown inputs and outputs, respectively.

E B k = {(j, i) ∈ U × X | [A B k ] ij = 1}; A B k being the biadjacency matrix of F 1 k . E C k = {(j, i) ∈ X ×Y | [A C k ] ij = 1}; A C k being the biadjacency matrix of F 2 k . E D k = {(j, i) ∈ U × Y | [A D k ] ij = 1}; A D k being the biadjacency matrix of F 3 k . The graph G k = (V, E k ), where V = X ∪ U ∪ Y and E k = E W k ∪ E B k ∪ E C k ∪ E D k ,
represents the underlying system at time instant k. The dynamics of such a linear network system are given as follows:

x k+1 = W k x k + B k u k y k = C k x k + D k u k (1.1)
with state vector x k ∈ R N , unknown input vector u k ∈ R P and output vector

y k ∈ R M . The matrices W k B k , C k and D k obey the pattern of imposed zeros of A W k , A B k , A C k and A D k , respectively.
From hereon, over a given interval [k 0 , k 1 ], the system (1.1) is denoted as

W k , B k , C k , D k } k 1 k 0 .
W k = {Z 1 A W k | Z 1 ∈ R N ×N }, B k = {Z 2 A B k | Z 2 ∈ R N ×P }, C k = {Z 3 A C k | Z 3 ∈ R M ×N } and D k = {Z 4 A D k | Z 4 ∈ R M ×P }.
In a similar vein, we define

W * k = {Z 1 A W k | Z 1 ∈ R N ×N * }, B * k = {Z 2 A B k | Z 2 ∈ R N ×P * }, C * k = {Z 3 A C k | Z 3 ∈ R M ×N * } and D * k = {Z 4 A D k | Z 4 ∈ R M ×P * }. Note that the collection of sets W k , B k , C k , D k as well as W * k , B * k , C * k , D * k impose the same pattern of fixed zeros on G k . The difference between W k , B k , C k , D k and W * k , B * k , C * k , D *
k is that in case of the former the free parameters are allowed to take any1 values in R, whereas for the latter case the free parameters strictly take non-zero values.

Let us consider the following example wherein we focus on the interval [0, 1], and the system at time instants 0 and 1 are represented by graphs G 0 (see Figure 1.1) and G 1 (see Figure 1.2), respectively. Here N = 5, M = 4 and P = 2. Since the inputs do not directly affect the outputs, A D k = 0 ∀k ∈ Z + . By looking at G 0 , we obtain the following:

A W 0 =        0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0        , A B 0 =        1 0 0 0 0 0 0 1 0 0        and A C 0 =     1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0     .
Similarly, by looking at G 1 , we obtain the following:

A W 1 =        0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0        , A B 1 =        1 0 0 0 0 0 0 1 0 0        and A C 1 =     0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0     .
The matrix sets W 0 , B 0 and C 0 are the sets of matrices that obey the fixed zero pattern of A W 0 , A B 0 and A C 0 , respectively. Analogously, we define the matrix sets W 1 , B 1 and C 1 . The matrix sets W * 0 , B * 0 and C * 0 obey the fixed zero pattern of A W 0 , A B 0 and A C 0 , respectively; moreover, the free parameters take strictly non-zero values.

Consider W 0 =        0 0 0 2 0 0 0 3 0 0 4 0 0 0 0 0 1 0 0 0 0 5 0 0 0       
. Note that W 0 obeys the fixed zero positions imposed by

A W 0 , and therefore W 0 ∈ W 0 . Consider W 0 =        2 2 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0       
. Note that W 0 does not obey the fixed zero positions imposed by A W 0 , for instance

[A W 0 ] 11 = 0, while [W 0 ] 11 = 2. Hence, W 0 / ∈ W 0 . Consider W 1 =        0 0 0 0 0 0 0 2 0 0 0 0 0 3 0 4 0 0 0 3 0 0 5 0 0        . Clearly, W 1 ∈ W 1 . However, since [W 1 ] 12 = 0,
it follows that W 1 is a numerical realization where a free parameter is allowed to take zero, and therefore

W 1 / ∈ W * 1 . Figure 1.1: G 0 Figure 1.2: G 1
At various points in the sequel, we will be considering particular cases of the system given in Eq. (1.1). For instance, in chapter 2 we focus on LTI network systems. In such a setting, the system matrices are time-independent i.e., for every k

∈ Z W k = W , B k = B C k = C and D k = D.
On the other hand, in chapter 3 we focus on LTV network systems but with zero feedthrough i.e., D k = 0. Over a given interval [k 0 , k 1 ], the system (1.1) is denoted as

{W k , B k , C k , D k } k 1 k 0 .

Definitions

In this subsection, we shall recall some system-theoretic notions. Let us begin by recalling the definition of observability.

Definition 1

The system (1.1) is observable on [k 0 , k 1 ] if, assuming that the input is known, any initial state Chapter 1. Preliminaries

x k 0 is uniquely determined by the corresponding measured output sequence {y k 0 , y k 0 +1 , . . . , y k 1 }s.

It is well known that thanks to linearity the assumption that input is known can be equivalently replaced by assumption that input is zero, and that observability only depends on matrices

W k , C k , irrespective of matrices B k , D k .
It is worthwhile to notice here that Definition 1 explicitly asks that the initial state x k 0 be reconstructed, assuming that the input is known. On the other hand, the notion of strong observability asks that the initial state x k 0 be reconstructed even in the presence of an unknown input. Yet another notion that would be of interest to us is that of delay-1 left invertibility.

To this end, we recall a relevant definition from [START_REF] Sundaram | Fault-tolerant and secure control systems[END_REF].

Definition 2 (Definition 2.5 [START_REF] Sundaram | Fault-tolerant and secure control systems[END_REF])

The system W k , B k , C k , D k } k 1 k 0 is delay-1 left invertible if the unknown inputs sequence {u k 0 , u k 0 +1 , . . . , u k 1 -1 }
can be uniquely determined by the initial state x k 0 and the output sequence {y k 0 , y k 0 +1 , . . . , y k 1 }.

These two notions, namely, strong observability and left invertibility with delay 1, give rise to the definition of ISO.

Definition 3 The system W k , B k , C k , D k } k 1 k 0 is ISO on the interval [k 0 , k 1 ] if the initial condition x k 0 ∈ R N
and the unknown inputs sequence {u k 0 , u k 0 +1 , . . . , u k 1 -1 } can be uniquely determined from the measured output sequence {y k 0 , y k 0 +1 , . . . , y k 1 }.

Note that Definition 3 defines the notion of ISO with respect to an interval. This is not surprising given that we are dealing with LTV systems. Let's denote by {W, B, C, D} the linear LTI system given by (1.1) with

(W k , B k , C k , D k ) = (W, B, C, D) for all k ∈ Z.
It is well-known that LTI systems are either ISO over every sufficiently long interval or not ISO at all. Hence, for LTI systems we define ISO as follows:

Definition 4

The system W, B, C, D} is ISO if the initial condition x 0 ∈ R N and the unknown inputs sequence {u 0 , u 1 , . . . , u N -1 } can be uniquely determined from the measured output sequence {y 0 , y 1 , . . . , y N }.

Algebraic Characterizations

In this section, we first provide algebraic characterizations for delay-1 left invertibility, and thereafter for ISO. The former would be needed for studying s-structural ISO for LTI network systems (see Chapter 2), while the latter would be needed in Chapters 2, 3 and 4.

Delay-1 left-invertibility

For LTI systems, an algebraic characterization of delay-, with ∈ Z ≥0 , is given by Massey and Sain in [START_REF] Massey | Inverses of linear sequential circuits[END_REF] (see Theorem 4), while Prop. 2 in [START_REF] Garin | Structural Delay-1 Input-and-State Observability[END_REF] gives yet another algebraic characterization, albeit for the particular case of = 1. The result-which we shall recall shortly-in [START_REF] Garin | Structural Delay-1 Input-and-State Observability[END_REF] stems from the following idea: The problem of reconstructing u(0) from x(0), y(0), y( 1) is equivalent to the problem of reconstructing u(0), x(1) from x(0), y(0) and y(1), since x(0), u(0) fully determine x(1).

Proposition 1 (Prop. 2 [START_REF] Garin | Structural Delay-1 Input-and-State Observability[END_REF])

The following are equivalent:

(i) W, B, C, D} is delay-1 left invertible; (ii) rank D 0 CB D = P + rank D; (iii) rank   D 0 0 B -I 0 0 C D   = P + N + rank D.

Algebraic Characterizations of ISO

With Definitions 1 and 3 in place, we now recall a couple of algebraic characterizations for ISO. Given that in chapters 2 and 3 we seek equivalence between ISO of a system and observability of a suitably defined subsystem, it is worthwhile to recall classical algebraic characterizations for observability as well. Towards this end we introduce observability, invertibility, input and state observability matrices in the next subsection.

Kalman-like Characterization of ISO

Let Θ k 0 ,k 1 , Γ k 0 ,k 1 and Ψ k 0 ,k 1
represent the observability matrix, invertibility matrix and input and state observability (ISO) matrix, respectively, over the interval [k 0 , k 1 ]. These are defined as follows:

Θ k 0 ,k 1 =            C k 0 C k 0 +1 W k 0 C k 0 +2 W k 0 +1 W k 0 . . . C k 1 W k 1 -1 • • • W k 0            , Γ k 0 ,k 1 =        D k 0 . . . . . . 0 C k 0 +1 B k 0 D k 0 +1 . . . 0 . . . . . . . . . . . . D k 1 -1 . C k 1 W k 1 -1 • • • W k 0 +1 B k 0 . . . . C k 1 B k 1 -1 D k 1        , Ψ k 0 ,k 1 = [Θ k 0 ,k 1 Γ k 0 ,k 1 ]. (1.2)
Hence, one can immediately obtain

y k 0 :k 1 = Θ k 0 ,k 1 x k 0 + Γ k 0 ,k 1 u k 0 :k 1 -1 = Ψ k 0 ,k 1 x k 0 u k 0 :k 1 -1 .
Then based on Definition 3 and from [START_REF] Massey | Inverses of linear sequential circuits[END_REF], the following proposition is immediate:

Proposition 2 The system W k , B k , C k , D k } k 1 k 0 is ISO with delay 1 over [k 0 , k 1 ] if and only if rank(Ψ k 0 ,k 1 ) = N + (k 1 -k 0 )P + rank(D k 1 ). . Proof: Let y k 0 :k 1 and u k 0 :k 1 -1 denote
the vectors of concatenated outputs and unknown inputs over [k 0 , k 1 ], respectively. Therefore, from (1.1) and (1.2) the following can be readily

obtained y k 0 :k 1 = Θ k 0 ,k 1 x k 0 + Γ k 0 ,k 1 u k 0 :k 1 -1 = Ψ k 0 ,k 1   x k 0 u k 0 :k 1 -1 u k 1   . Based on Definition 3, it
is immediate that input and state observability requires that the vector

x k 0 u k 0 :k 1 -1
be uniquely recovered from y k 0 :k 1 . This is equivalent to asking that the first N + (k 1k 0 )P columns of Ψ k 0 ,k 1 be linearly independent amongst themselves, and also of the remaining P columns of

0 (k 1 -k 0 +1)M ×P D k 1 . Hence the system W k , B k , C k , D k } k 1 k 0 is ISO, over [k 0 , k 1 ], if and only if rank(Ψ k 0 ,k 1 ) = N + (k 1 -k 0 )P + rank(D k 1 ).

Alternative Algebraic Characterization of ISO

Notice that Prop. 2 characterizes ISO in terms of products of the system matrices. Consequently, the corresponding zero pattern is lost. Hence, in this subsection, we will focus on providing an alternative characterization that preserves the zero pattern of the system matrices. Thm. 6.4.1 in [START_REF] Murota | Matrices and matroids for systems analysis[END_REF] gives an alternative characterization of controllability. The following proposition does the same for observability.

Proposition 3 The system W k , C k } k 1 k 0 is observable over [k 0 , k 1 ] if and only if rank(Q k 0 ,k 1 ) = (k 1 -k 0 +1)N ,

Algebraic Characterizations

where

Q k 0 ,k 1 =                  C k 0 0 . . . . . . 0 0 C k 0 +1 . . . . . . 0 . . . . . . . . . . . . . . . . . . . . . . 0 . . . . . . . . . C k 1 W k 0 -I N . . . . . . 0 0 W k 0 +1 -I N . . . 0 . . . . . . . . . . . . . . . . . . . . . . 0 . . . . . . W k 1 -1 -I N                  , with Q k 0 ,k 1 ∈ R (k 1 -k 0 + 1)M + (k 1 -k 0 )N × (k 1 -k 0 + 1)N .
Proof: Notice that the problem of reconstructing x k 0 from y k 0 :k 1 is equivalent to the problem of reconstructing x k 0 , x k 0 +1 , . . . , x k 1 . To see this, consider the following argument: reconstructing

x k 0 , x k 0 +1 , . . . , x k 1 is sufficient for reconstructing x k 0 On the other hand, under the assumption that W k ∀k ∈ [k 0 , k 1 -1] is known, if x k 0 can be reconstructed, then x k 0 +1 , . . . , x k 1 can also be reconstructed.
The relationship between the states and outputs can be expressed via a system of linear equations as follows. From Eq. (1.1) and setting u(k) = 0 P , we have:

∀k ∈ [k 0 , k 1 -1], W k x k -x k+1 = 0 N and ∀k ∈ [k 0 , k 1 ] C k x k = y k .
This can be rewritten as:

Q k 0 ,k 1 x k 0 :k 1 = y k 0 :k 1 0 (k 1 -k 0 -1)N . Hence, the system W k , B k , C k , D k } k 1 k 0 is observable, over [k 0 , k 1 ]
, if and only if the above system of linear equations has a unique solution. It turns out that similar arguments can be made for ISO as well, and will be shown in Prop. 4. As a first step we define the following matrix:

J k 0 ,k 1 =   D k 0 ,k 1 -1 0 (k 1 -k 0 )M ×P 0 M ×(k 1 -k 0 )P D k 1 B k 0 ,k 1 -1 0 (k 1 -k 0 )N ×P Q k 0 ,k 1   where D k 0 ,k 1 -1 = diag (D k 0 , D k 0 +1 . . . D k 1 -1 ), B k 0 ,k 1 -1 = diag (B k 0 , B k 0 +1 . . . B k 1 -1 ), No- tice that J k 0 ,k 1 has ((k 1 -k 0 + 1)M + (k 1 -k 0 )N ) rows and (k 1 -k 0 + 1)P + (k 1 -k 0 + 1)N columns.

Proposition 4

The system

W k , B k , C k , D k } k 1 k 0 is ISO over [k 0 , k 1 ] if and only if rank(J k 0 ,k 1 ) = (k 1 -k 0 )P + (k 1 -k 0 + 1)N + rank(D k 1 ). Proof: First notice that the problem of reconstructing x k 0 and u k 0 :k 1 -1 from y k 0 :k 1 is equivalent to the problem of reconstructing x k 0 , x k 0 +1 , . . . , x k 1 and u k 0 :k 1 -1 . From (1.1), we have: ∀k ∈ [k 0 , k 1 -1], W k x k + B k u k -x k+1 = 0 N and ∀k ∈ [k 0 , k 1 ] C k x k + D k u k = y k .
Hence, both the state equation and output equation at each time instant can be expressed as a linear combination of x k 0 , x k 0 +1 , . . . , x k 1 as well as u k 0 , u k 0 +1 , . . . , u k 1 , in the following manner:

J k 0 ,k 1 u k 0 :k 1 x k 0 :k 1 = y k 0 :k 1 0 (k 1 -k 0 )N ,
Pursuant to the condition given in Definition 3, we rearrange the columns of J k 0 ,k 1 , to obtain Jk 0 ,k 1 , such that the P columns belonging to the block

  0 (k 1 -k 0 )M ×P D k 1 0 (k 1 -k 0 )N ×P   are placed at the end.
Hence, the above system of equations can be represented as

Jk 0 ,k 1   u k 0 :k 1 -1 x k 0 :k 1 u k 1   = y k 0 :k 1 0 (k 1 -k 0 )N .
Recall from Definition 3 that ISO, requires that the vector

u k 0 :k 1 -1 x k 0 :k 1 be uniquely recovered from y k 0 :k 1 0 (k 1 -k 0 )N
. This is equivalent to asking that the first

(k 1 -k 0 )P + (k 1 -k 0 + 1)N
columns of Jk 0 ,k 1 be linearly independent amongst themselves, and also of the remaining P columns of

  0 (k 1 -k 0 )M ×P D k 1 0 (k 1 -k 0 )N ×P   . Hence the system W k , B k , C k , D k } k 1 k 0 is ISO, over [k 0 , k 1 ], if and only if rank( Jk 0 ,k 1 ) = (k 1 -k 0 )P + (k 1 -k 0 + 1)N + rank(D k 1 )
. Since column permutations do not affect the rank of a matrix, rank( Jk 0 ,k 1 ) = rank(J k 0 ,k 1 ), and therefore the proof is complete.

In Chapter 3, we focus on LTV network systems with zero feedthrough. Under such a setting, the result in Prop. 4 can be written as follows:

Remark 1 The system W k , B k , C k } k 1 k 0 is ISO over [k 0 , k 1 ] if and only if rank(J k 0 ,k 1 ) = (k 1 -k 0 )P + (k 1 -k 0 + 1)N .

PBH-like tests

For the particular case of LTI systems, there exists yet another algebraic characterization of ISO, which is analogous to the famous PBH tests for observability. We start off by recalling the same, and thereafter provide the characterization for ISO. In order to state the PBH condition, we need a suitable matrix pencil. Given two matrices M 0 , M 1 of the same size, one can define the linear matrix pencil L(z) = M 0 + zM 1 ; this is a matrix-valued function of the complex variable z. The most commonly used matrix pencil is the one with M 1 = -I, i.e., L(z) = M 0 -zI, whose zeros are the eigenvalues of matrix M 0 . For the PBH test, we define the matrix pencil P (z) as

P (z) = zI -W C .
From classical results in observability we know that {W, C} is observable if and only if rank( P (z)) = N , ∀z ∈ C. In a similar vein, set u k = 0, and let us construct the matrix pencil corresponding to {W, B, C, D} as :

P (z) = zI -W B C D .
We recall the following result which is immediate from Theorem 7.17 and Corollary 8.10 in [START_REF] Harry L Trentelman | Control theory for linear systems[END_REF].

Lemma 1 {W, B, C, D} is ISO if and only if rank(P (z)) = N + P , ∀z ∈ C.
As was correctly pointed out in [START_REF] Garin | Structural Delay-1 Input-and-State Observability[END_REF], the result in Lemma 1 translates to reconstructing the initial state x 0 and the sequence of unknown inputs {u 0 , u 1 , . . . , u N -}, where ∈ Z + , from output measurements {y 0 , y 1 , . . . , y N }. Notice that is unknown, i.e., the unknown input is reconstructed with an unknown delay; not necessarily delay 1. We are interested in delay-1 unknown input reconstruction. From Thm. 7.17 in [START_REF] Harry L Trentelman | Control theory for linear systems[END_REF] and Thm. 4 in [START_REF] Massey | Inverses of linear sequential circuits[END_REF], we have the following characterization. Note that the result given in Prop. 5 generalizes the result given by Lemma 2 in [START_REF] Kibangou | Input and state observability of network systems with a single unknown input[END_REF] in that it accounts for multiple unknown inputs.

The algebraic characterizations for ISO provided insofar, namely Prop. 2, Prop. 4 and Prop. 5, are dependent on checking the rank conditions of the concerned matrices. Consequently, one requires exact knowledge of all the coefficients of the system matrices, which is not practically possible in network systems. Moreover, as the size of the network grows, computing the rank of the ISO matrix becomes non-trivial. Hence, in the sequel, we seek a (graphical) characterization that overcomes the aforesaid drawbacks.

Transition to Graphical Characterization

The focus of this section is to develop the framework for migrating to a graphical characterization of ISO, by recalling structured matrices and relevant graph terminologies useful for evaluating the different notions of ranks of structured matrices. This will aid us in seeking graphical characterizations for ISO (see results in chapters 2, 3, 4).

Structured Matrices

Recall that the ISO matrix Ψ k 0 ,k 1 contains products of the system matrices, and therefore the coefficients of Ψ k 0 ,k 1 are either fixed zeros or polynomials in the free parameters of the system matrices. Inspired from [START_REF] Murota | Matrices and matroids for systems analysis[END_REF], consider a matrix A that has fixed zero positions and all its other entries are non-zero polynomials in free parameters (say λ 1 , λ 2 , . . . , λ µ ). Let us call such a matrix as a structured matrix. Let λ = λ 1 λ 2 . . . λ µ denote the vector of free parameters in R µ . Each vector in R µ denotes a particular numerical choice of free parameters. Note that for structured matrices it is not necessarily the case that each and every entry containing a non-zero polynomial in free parameters can be independently parametrized. For instance, some of these entries might be a priori fixed to a non-zero constant; some of the entries might be algebraically dependent on other entries and, therefore, cannot be independently parametrized. It may be pertinent to look for subclasses of structured matrices wherein all entries not fixed at zero are independently parametrized and are free to take any value. We use the term pattern matrix to represent such particular instance of a structured matrix, and we define it as follows.

Definition 5

Let A be a structured matrix. A is a pattern matrix if each non-zero polynomial in A is of the form λ i with all i's being distinct.

Relevant Graph Terminology

The zero/non-zero pattern of structured matrices allows one to study structured systems by employing tools from graph theory, and hence we will briefly recall a few graph-theoretic notions. For a thorough overview of graph-theoretic vocabulary, we refer the interested reader to [START_REF] Godsil | Algebraic graph theory[END_REF].

We start off by defining the notion of output-connectedness in graphs.

Definition 6

Consider a graph G = (V, E). Let O ⊆ V be the set of output nodes. The graph G is said to be output-connected, if for every v ∈ V \ O there exists a path from v to some w such that w ∈ O. Given a graph G = (V, E) we say that two paths are vertex-disjoint if they do not have any vertex in common. Next, we define a linking on a graph

Definition 7

Let S and T be two sets of vertices of a directed graph. A collection of vertex-disjoint paths from set S to set T is called a linking from S to T .

We say that a linking saturates a vertex if the said vertex is one of the vertices along the paths in the linking. The notion of matching, which is closely related to linking, is defined as follows:

Definition 8 A matching is a collection of edges such that no two edges share a vertex. The size of a matching is the number of edges contained in it; if a matching has maximum size among all the matchings in the same graph, then it is a maximum matching. We say that a matching saturates a vertex if the said vertex is one of the vertices of the edges contained in the matching. Closely related is the concept of uniquely restricted matching (also known as constrained matching), and is given by the following definition.

Definition 9 (Definition 2.4 [START_REF] Hershkowitz | Ranks of zero patterns and sign patterns[END_REF]) Let B = {V + , V -, E} be a bipartite graph. A matching of size t is said to be uniquely restricted if it is the only matching of size t in B between {i 1 , . . . , i t } and {j 1 , . . . , j t }, where {i 1 , . . . , i t } ∈ V + and {j 1 , . . . , j t } ∈ V -.

Consider the bipartite graph B given in

Ranks of structured matrices

The rank of a structured matrix A is evaluated with respect to a choice of free parameters. However, notions like term-rank and generic rank do not depend on the choice of free parameters, and hence in the following we shall briefly discuss the same. We can associate a bipartite graph to the structured matrix A in the following manner;

B(A) = {V + , V -, E(A)} where V + is the set of all columns in A, V -is the set of all rows in A and E(A) = {(i, j) | i ∈ V + , j ∈ V -, [A] ji = 0}
is the edge set corresponding to the free parameter positions in A. With the bipartite graph B(A) in place, the definition of term-rank(A) follows.

Definition 10 ([56])

The term-rank(A) is equal to the maximum size of a matching on the bipartite graph B(A).

Consider the following structured matrix.

A 1 =   λ 1 0 0 0 λ 2 0 0 0 λ 3 
 , and let B(A 1 ) be the associated bipartite graph, given in Figure 1.9. It can be seen that there exists a matching of size 3 on B(A 1 ), which is in fact the maximum size a matching can have on B(A 1 ). Therefore, term-rank(A 1 ) = 3.

1.5. Transition to Graphical Characterization 21

3 + 2 + 1 + • • • 3 - 2 - 1 - • • • Figure 1.9: B(A 1 )
As far as the notion of generic rank of a structured matrix with polynomials in its non-zero positions is concerned, recall that the entries a ij of A are polynomials in µ free parameters. We know that any subdeterminant of A is a polynomial in the free parameters λ 1 , λ 2 , . . . , λ µ , which brings us to the following definition.

Definition 11 ([56])

The generic rank (denoted as gen-rank) of A is the maximum size of a square submatrix whose determinant is a non-zero polynomial.

It turns out that the rank(A) is the same for almost all choices of free parameters of A. This can be immediately seen by noticing that the aforementioned polynomial yields zero only when evaluated for elements in its zero set.

Let A 2 =   λ 1 0 1 0 1 1 0 2 2   .
Note that A 2 is a structured matrix, which has some of its free parameters a priori fixed to some constant value. Clearly, det(A 2 ) = 0, which implies gen-rank(A 2 ) = 3. Now, consider the following submatrix of A 2 , namely Ã2 = λ 1 0 0 1 , and note that det( Ã2 ) = λ 1 . This implies det( Ã2 ) is a non-zero polynomial and therefore, gen-rank(A 2 ) = 2.

The main results from [START_REF] Murota | Matrices and matroids for systems analysis[END_REF] that would be used in the sequel are collected in the following lemma.

Lemma 2 ([56])

Let A be a structured matrix having λ ∈ R µ as its vector of free parameters. Then the following statements are true:

(i) gen-rank(A) = max λ∈R µ rank(A),
(ii) for almost all choices of λ, rank(A) = gen-rank(A).

(iii) In general, gen-rank(A) ≤ term-rank(A). For the particular case when A is a pattern matrix, gen-rank(A) = term-rank(A)

Structural ISO

Given that we are interested in finding graphical characterizations for structural (resp. sstructural) ISO, it is worthwhile to develop a better understanding of structural ISO. This section is geared towards such an objective. First, we broadly discuss structural properties, then we show that indeed ISO is a structural property, and finally we discuss the implications of structural ISO.

What are structural properties?

In this thesis, we shall call "structural properties" as those that are true for almost all choices of free parameters or false for almost all choices of free parameters. Notice that in both cases there (possibly) exists a set of choices of free parameters for which the property fails. However, this set lies on some proper algebraic variety of the space of free parameters and therefore, has Lebesgue measure zero. For some structural properties, it turns out that once it (i.e., the property) is true for one choice of free parameters it is also true for almost all choices of free parameters (for instance, controllability and observability [START_REF] Lin | Structural controllability[END_REF][START_REF] Robert | Structural controllability of multi-input linear systems[END_REF]). Equivalently, if a property is structural, then it is either true almost everywhere or false almost everywhere.

On the other hand, if there exists a non-trivial set of choices of free parameters for which the property is true and another non-trivial set of choices of free parameters for which the property is false -as would be the case with stability-then the said property is not structural. Such a property is then said to be either false almost everywhere or true almost everywhere. From a probabilistic standpoint, it (i.e., the property) can be either true with non-trivial probability or false with non-trivial probability.

Is ISO a structural property?

It is well-known that system-theoretic properties like controllability, observability are structural properties [START_REF] Lin | Structural controllability[END_REF][START_REF] Robert | Structural controllability of multi-input linear systems[END_REF][START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF]. That is, given a fixed zero pattern of system matrices, if there exists at least one choice of free parameters for which the corresponding system is controllable (resp. observable), then for almost all choices of free parameters the corresponding system is controllable (resp. observable). In order to understand whether the same can also be said about the more general property of ISO, we introduce the following lemma.

Lemma 3

If there exists one choice of free parameters such that rank(

Ψ k 0 ,k 1 ) = N + (k 1 -k 0 )P + term-rank(D k 1 ), then gen-rank(Ψ k 0 ,k 1 ) = N + (k 1 -k 0 )P + term-rank(D k 1 ).
Proof: First notice that the entries in Ψ k 0 ,k 1 are polynomials whose coefficients are free parameters of matrices

W k k 1 k 0 , B k k 1 k 0 , C k k 1 k 0 and D k k 1 k 0 .
Suppose there exists a choice of free parameters such that rank(

Ψ k 0 ,k 1 ) = N + (k 1 -k 0 )P + term-rank(D k 1 ), then from item (i) in Lemma 2, gen-rank(Ψ k 0 ,k 1 ) ≥ N + (k 1 -k 0 )P + term-rank(D k 1 )
. Notice that, for any choice of parameters, Ψ k 0 ,k 1 can have at most N + (k 1k 0 )P + term-rank(D k 1 ) independent columns, since the rank of the block with the last P columns is rank D k 1 ≤ term-rank D k 1 . This shows that gen-rank(Ψ k 0 ,k 1 ) ≤ N + (k 1k 0 )P + term-rank(D k 1 ), which together with the previous inequality implies that gen-rank(Ψ k 0 ,k 1 ) = N + (k 1k 0 )P + term-rank(D k 1 ).

Remark 2

If the conditions in Lemma 3 are satisfied, then, over a given interval [k 0 , k 1 ], for almost all choices of free parameters in the system matrices, the corresponding numerical realization is ISO. Moreover, since D k 1 is a pattern matrix term-rank(D k 1 ) = gen-rank(D k 1 ). That is, for almost all choices of free parameters in D k 1 , the corresponding numerical realization of

D k 1 satisfies rank(D k 1 ) = term-rank(D k 1 ).
Hence, Lemma 3 implies that ISO is a structural property.

Implications of structural ISO

The understanding for structural ISO is a bit more involved than that for structural observability. Here we detail it. Let us begin by introducing the space of free parameters. Under the setting given by Eq. (1.1), for every k ∈ Z, let w k , b k , c k and d k denote the number of free parameters in W k , B k , C k and D k , respectively. Consequently, over an interval [k 0 , k 1 ], the space of free parameters is given by R α , where α =

k 1 k=k 0 (w k + b k + c k + d k ).
Moreover, since we are concerned with intervals of finite length, the space of free parameters is finite-dimensional. Also note that each choice of free parameters in R α yields a new system. The notion of structural ISO should be understood as follows: A family of systems

{W k , B k , C k , D k } being structurally ISO over [k 0 , k 1 ]
means that for almost all choices of free parameters in R α except (possibly) for those lying on a subvariety of R α , the correspond-

ing system {W k , B k , C k , D k } k 1 k 0 satisfies rank(Ψ k 0 ,k 1 ) = N + (k 1 -k 0 )P + term-rank(D k 1 ). On the other hand, a family of systems {W k , B k , C k , D k } being not structurally ISO over [k 0 , k 1 ] means that for almost all choices of free parameters in R α , the corresponding system {W k , B k , C k , D k } k 1 k 0 violates rank(Ψ k 0 ,k 1 ) = N + (k 1 -k 0 )P + term-rank(D k 1 ). However, for at most few choices of free parameters over [k 0 , k 1 ] the corresponding system {W k , B k , C k , D k } k 1 k 0 might be ISO.
Since an algebraic variety has Lebesgue measure zero, a probabilistic interpretation of the aforesaid is the following: Under the assumption that the free parameters are chosen at random from an underlying continuous distribution, a family of systems {W k , B k , C k , D k } being structurally ISO over [k 0 , k 1 ] implies that each member in this family of systems is ISO with probability 1, while a family of systems {W k , B k , C k , D k } being not structurally ISO over [k 0 , k 1 implies that each member in this family of systems is not ISO with probability 1.

Chapter 1. Preliminaries Zero feedthrough

In Chapter 3, we will be restricting our focus to the case of zero feedthrough. Note that, the notion of structural ISO, under zero feedthrough, subtly differs from what is discussed above. While the understanding in the positive sense remains unchanged, in the negative sense it should be interpreted as follows: a family of systems {W k , B k , C k } being not structurally ISO over [k 0 , k 1 ] means that for every choice of free parameters, the corresponding system

{W k , B k , C k } k 1 k 0 violates rank(Ψ k 0 ,k 1 ) = N + (k 1 -k 0 )P .
That is, in this context, the property of ISO holds almost everywhere in the space of free parameters or holds nowhere in the space of free parameters. From a probabilistic standpoint, with the same assumption on the free parameters as before, either each member in the family of systems {W k , B k , C k , D k } is ISO with probability 1 or no member in this family is ISO.

Strongly Structural ISO

Recall that structural properties ensures that the property is true with probability 1, if the free parameters are chosen from a continuous distribution. S-structural properties, on the other hand, requires that the property be true as far as the vector of free parameters is non-zero (i.e., each and every element in the vector of free parameters is strictly non-zero). Put differently, structural results are probabilistic, while s-structural results are deterministic. More pertinently, the latter gives certificates of guarantees. What informs the choice of which of these two results to pursue often depends on the consequences of a particular choice of free parameter lying on a subvariety of the space of free parameters.

Introduction

In this chapter, we focus on providing graphical characterizations of ISO for linear timeinvariant (LTI) network systems. In the first half of this chapter, we review results for structural ISO of LTI network systems given in [START_REF] Garin | Structural Delay-1 Input-and-State Observability[END_REF]. In the second half, we provide graphical characterizations for s-structural ISO.

Chapter Outline

This chapter is organized as follows. We state the problem at hand in Sect. 2.2, and provide algebraic characterizations of delay-1 left invertibility in Sect. 1.4.1. The results for structural ISO are reviewed in Sect. 2.3, while a graphical characterization for s-structural ISO are given in 2.4. The main contribution of this chapter is to provide a graphical characterization for s-structural ISO (see Thm. 3).

26

Chapter 2. Linear Time-Invariant Network Systems

Problem Formulation

We consider a particular case of the setting given in Eq. (1.1) in that we set

W k = W , B k = B, C k = C and D k = D.
This implies that the dynamics is given by the following:

x k+1 = W x k + Bu k y k = Cx k + Du k (2.1)
The the family of all systems whose dynamics obey eq. (2.1) and whose free parameters take strictly non-zero values. An illustration of the setup is given in Figure 2.1. The corresponding system equations can be written as follows:

    x 1 k+1 x 2 k+1 x 3 k+1 x 4 k+1     =     0 0 0 0 0 0 0 0 0 0 0 w 34 0 0 0 0         x 1 k x 2 k x 3 k x 4 k     +     b 11 0 0 b 22 0 0 0 0     u 1 k u 2 k   y 1 k+1 y 2 k+1 y 3 k+1   =   c 11 0 0 0 0 c 22 0 0 0 0 c 33 0       x 1 k x 2 k x 3 k x 4 k     (2.2)
In this chapter, based only on the topology of G, we seek to characterize ISO for (i) almost all system matrices as given in (2.1) with W ∈ W, B ∈ B, C ∈ C and D ∈ D;

(ii) every system matrix as given in (2.1) with

W ∈ W * , B ∈ B * , C ∈ C * and D ∈ D * .
Note that the problem stated in (i) has already been addressed in [START_REF] Garin | Structural Delay-1 Input-and-State Observability[END_REF]. Hence, we will only mention the relevant results (see Sect. 2.3). On the other hand, the problem stated in (ii) remains open and we shall address it in detail in this chapter (see Sect. 2.4).

In this chapter, we will also be dealing with the notion of unconstrained ISO, wherein we do not insist on reconstruction with one-time-step delay. That is, the unknown input sequence is reconstructed with some unknown delay.

Definition 12

The system W, B, C, D} is unconstrained ISO if there exists some ∈ Z ≥0 such that the initial condition x 0 ∈ R N and the unknown inputs sequence {u 0 , u 1 , . . . , u N -} can be uniquely determined from the measured output sequence {y 0 , y 1 , . . . , y N }.

Structural ISO

In this section we first present a formal definition of structural ISO. Thereafter, we establish a foundation for presenting our main results, and finally we conclude by recalling a graphical characterization for structural ISO. We shall now turn our focus towards a graphical characterization for structural ISO. In order to do so, we need the following constructs. Let H be a bipartite graph with left vertex set U ∪ X, right vertex set X ∪ Y , and edge set ĒW ∪ ĒB ∪ ĒC ∪ ĒD . These are defined as follows:

Definition and Some preliminary material

• U = {u 1 , . . . , u P }, X = {x 1 , x 2 , . . . , x N }; • X = {x 1 , . . . , x N }, Y = {y 1 , . . . , y M };
• for all i ∈ {1, . . . , N }, j ∈ {1, . . . , N },

(x i , x j ) ∈ ĒW if and only if [A W ] ji = 1;
• for all i ∈ {1, . . . , P }, j ∈ {1, . . . , N },

(u i , x j ) ∈ ĒB if and only if [A B ] ji = 1;
• for all i ∈ {1, . . . , N }, j ∈ {1, . . . , M },

(x i , y j ) ∈ ĒC if and only if [A C ] ji = 1;
• for all i ∈ {1, . . . , P }, j ∈ {1, . . . , M },

(u i , y j ) ∈ ĒD if and only if [A D ] ji = 1.
In words, for the bipartite graph H, the left vertex set contains the input vertices and state vertices, while the right vertex set contains output vertices and copies of the state vertices.

The edge sets ĒW (resp. ĒB , ĒC and ĒD ) represent the interaction between state vertices (resp. input vertices and state vertices, state vertices and output vertices, and input vertices and output vertices). A pictorial description of H is given in Figure 2.3.

U 0 ∪ U 1 ∪ X ∪ Y 0 ∪ Y 1 and edge set F 0 D ∪ F 1 D ∪ F B ∪ F C , with • U 0 = {u 0 1 , . . . , u 0 P }, U 1 = {u 1 1 , . . . , u 1 P }; • X = {x 1 , . . . , x N }; • Y 0 = {y 0 1 , . . . , y 0 M }, Y 1 = {y 1 1 , . . . , y 1 M }; • for all i ∈ {1, . . . , P }, j ∈ {1, . . . , M }, (u 0 i , y 0 j ) ∈ F 0 D if and only if [A D ] ji = 1 and (u 1 i , y 1 j ) ∈ F 1 D if and only if [A D ] ji = 1; • for all i ∈ {1, . . . , P }, j ∈ {1, . . . , N }, (u 0 i , x j ) ∈ F B if and only if [A B ] ji = 1; • for all i ∈ {1, . . . , N }, j ∈ {1, . . . , M }, (x i , y 1 j ) ∈ F C if and only if [A C ] ji = 1;
For a pictorial description of K, see Figure 2.5.

Structural ISO

Main Result

With the bipartite graphs H, S, directed graphs G, K in place and recalling definitions of output-connectedness (6), linking [START_REF] Alvaro | Attacks against process control systems: risk assessment, detection, and response[END_REF] and matching (8) from Chapter 1, we can now state a graphical characterization for structural ISO. (c) The directed graph K contains a linking of size

P + R from U 0 ∪ U 1 to Y 0 ∪ Y 1 ,
where R is the size of the maximum matching in S.

Indeed, the case without insisting on delay 1 has been handled in [5]. The items (a) and (b) are an equivalent rephrasing of the result therein (see Corollary 7 [5]), while item (c) ensures delay-1 left invertibility.

{u 1 --> x 1 --> y 1 ; u 2 --> x 2 --> y 2 } . This implies that V ess = {u 1 , x 1 , y 1 , u 2 , x 2 , y 2 }.
The resulting graph G1 is as shown in Figure 2.9. It can be immediately seen that G1 is output-connected. The Figure 2.10 shows the directed graph K 1 , constructed analogous to K, associated with G 1 ; highlighted in red is a linking, of size 2, from U 0 to Y 1 . Hence, the conditions given in Theorem 1 are satisfied, and thus the example given in Figure 2.1 is structurally ISO.

Chapter 2. Linear Time-Invariant Network Systems

S-structural ISO

The main objective of this section is to characterize ISO for every choice of entry in W * , B * , C * and D * . Towards this end, we first define s-structural ISO, then give a graphical characterization for the same, and finally check the conditions given in the characterization with respect to our running example.

Definition and Preliminary Materials

S-structural properties are those that hold for every non-zero choice of free parameters of the system matrices. That is, s-structural ISO (resp. s-structural unconstrained ISO) requires that every member of the family of LTI systems given by W * , B * , C * , D * LT I , be ISO (resp. unconstrained ISO). This leads us to the following definition Prior to proceeding to the main result in this section, first, we remind ourselves of the bipartite graph H (see Section 2.3.1). Thereafter, we define another bipartite graph H × , whose vertex sets are the same as in H but the edge set is E × , where E × = ĒW ∪ ĒB ∪ ĒC ∪ ĒD ∪ E new . The edge set E new is obtained by adding self-loops to all those vertices in X that previously did not have one, while the edge set E loop represents the already existing self-loops in G. For a pictorial description, see Figure 2.11. We adopt the following notation from [START_REF] Garin | Structural Delay-1 Input-and-State Observability[END_REF]. Let N be a bipartite graph whose left vertex set is

U 0 ∪ X ∪ U 1 , the right vertex set is Y 0 ∪ X ∪ Y 1 . The edge set of N is F 0 D ∪ F 1 D ∪ FB ∪ FC ∪ FI , where: • for all i ∈ {1, . . . , P }, j ∈ {1, . . . , M }, {(u 0 i , y 0 j )} ∈ F 0 D if and only if [A D ] ji = 1 and {(u 1 i , y 1 j )} ∈ F 1 D if and only if [A D ] ji = 1;
• for all i ∈ {1, . . . , P }, j ∈ {1, . . . , N }, {(u 0 i , x j )} ∈ FB if and only if [A B ] ji = 1;

• for all i ∈ {1, . . . , N }, j ∈ {1, . . . , M }, {(x i , y 1 j )} ∈ FC if and only if [A C ] ji = 1;

• FI = {(x i , x i ), i = 1, . . . , N }.
Notice that, unlike the bipartite graphs H and H × , the edges between the state vertices are only all self-loops. For a pictorial description of N , see Figure 2.12. Let Ñ be a subgraph obtained from N by removing the edge set F 1 D .

Figure 2.12: Bipartite graph N Chapter 2. Linear Time-Invariant Network Systems

Main Result

The main objective of this section is to characterize ISO (resp. unconstrained ISO) for every choice of entry in W * , B * , C * and D * . We provide a graphical characterization for s-structural unconstrained ISO, and a sufficient condition and necessary conditions for s-structural ISO. Finally, we conclude by checking these conditions with respect to a few examples.

The following result gives a graphical characterization for s-structural unconstrained ISO.

Theorem 2 W * , B * , C * , D * is s-structurally unconstrained ISO if and only if the following conditions are satisfied:

(i) there exists a uniquely restricted matching M of size N + P in the bipartite graph H, and

(ii) there exists a uniquely restricted matching M × of size N + P in the bipartite graph

H × such that M × ∩ E loop = ∅ .
Theorem 2 generalizes the result given in [START_REF] Chapman | On strong structural controllability of networked systems: a constrained matching approach[END_REF] (see Theorem 5) wherein a graphical characterization for s-structural controllability (also, for the dual problem of s-structural observability) is provided. The following remark better explains the subtleties of the condition given in item ii) of Theorem 2.

Remark 3

Let Ĥ× be a subgraph of H × obtained from H × by removing the edge set E loop . Suppose that there exists a uniquely restricted matching, say M× , of size P + N , in Ĥ× . This implies that there exists a choice of vertex sets, say q and r, such that over q and r there does not exist another matching of size P + N . Note that while M× is a uniquely restricted matching in Ĥ× , it does not necessarily imply that M× is also a uniquely restricted matching in H × , since some of the edges in E loop together with the already existing edges in Ĥ× might yield another matching over q and r.

The condition given in item ii) of Theorem 2 insists on existence of uniquely restricted matching of size P + N , not using any of the edges in E loop , in H × .

The following result gives a sufficient condition and necessary conditions for s-structural ISO. Let N be a subgraph obtained from N by removing the edge sets F 0 D and F 1 D . For the particular case of A D = 0, a graphical characterization for s-structural ISO is readily obtained from Theorem 3.

Corollary 1

If A D = 0, W * , B * , C * , D * is s-structurally ISO if and only if the following conditions are satisfied:

(i) there exists a uniquely restricted matching M of size N + P on the bipartite graph H;

(ii) there exists a uniquely restricted matching M × of size N + P on the bipartite graph H × such that M × ∩ E loop = ∅; and

(iii) there exists a uniquely restricted matching of size P + N on the bipartite graph N .

It is pertinent to think of the computational complexity involved in checking the conditions given in Theorem 3. The following remark addresses the same.

Remark 4

Note that all the conditions given in Theorem 2, Theorem 3 and Corollary 1 are questions of the following kind: In a given bipartite graph, for some given set of edges, is there a maximum matching M of a given size, only using the given edges, and which is also uniquely restricted? Corollary 4 in [START_REF] Draque Penso | Graphs in which some and every maximum matching is uniquely restricted[END_REF] provides an algorithm to answer this question in polynomial time. For the case where the given size is equal the size of all the left vertex set (namely, in the necessary condition in Theorem 2, Theorem 3 and Corollary 1), a simpler algorithm (equivalent to the one in [START_REF] Draque Penso | Graphs in which some and every maximum matching is uniquely restricted[END_REF] for this particular case) had been proposed in [START_REF] Hartung | Characterization of strong structural controllability of uncertain linear time-varying discrete-time systems[END_REF], and careful implementations have been then presented in [START_REF] Chapman | On strong structural controllability of networked systems: a constrained matching approach[END_REF] having quadratic (in the number of vertices) complexity, while a cleverer implementation of the algorithm devised by [START_REF] Weber | A linear time algorithm to verify strong structural controllability[END_REF] has a complexity which is linear in the number of vertices plus the number of edges; notice that this is in between linear and quadratic w.r.t N + P + M , depending on the sparsity of the zero pattern of the system matrices.

Example 1 (continued): Note that, over the choice of vertex sets {u 1 , u 2 , x 1 , x 2 , x 3 , x 4 } and {x 1 , x 2 , x 3 , y 1 , y 2 , y 3 }, there does not exist another matching on H 1 . This implies that the matching M 1 is uniquely restricted. The bipartite graph H ×1 , constructed analogous to H × , is given in Figure 2.13. Note that the matching M 1 is uniquely restricted on H ×1 and, since E loop = ∅, it satisfies the condition M 1 ∩ E loop = ∅. The bipartite graph N 1 , constructed analogous to N , is given in Figure 2.14.

The collection of edge sets {(u 0 1 , x 1 ), (u 0 2 , x 2 ), (x 1 , y 1 1 ), (x 2 , y 1 2 ), (x 3 , y 1 3 ), (x 4 , x 4 )}, forms a matching M N on N 1 (see Figure 2.15). Moreover, since there does not exist another matching, of size 6, over the same choice of vertex sets, M N is uniquely restricted. Thus, the conditions (1a), (1b) and (1c) given in Thm. 3 are satisfied, and therefore the example given in Figure 2.1 is s-structurally ISO. Thus, there does not exist a uniquely restricted matching of size 4 on S. That is, condition 2a given in Thm. 3 is violated, and therefore, the example given in Figure 2.17 is not s-structurally ISO. 2.33. In Figure 2.31, note that the vertex x 3 is connected only to itself via a (already existing) self-loop. This implies that there does not exist a matching M ×3 of size 4 on H ×3 such that M ×3 ∩ E loop = ∅. This further implies that there does not exist a uniquely restricted matching M ×3 on H ×3 of size 4 such that M ×3 ∩ E loop = ∅. Hence, condition 2b given in Thm. 3 is violated, and therefore, the example given in Figure 2.31 is not s-structurally ISO.

Example 4: Consider the example given in Figure 2.35. The bipartite graph N 4 is constructed analogous to N , and is shown in Figure 2.36. From Figures 2.37 and 2.38 it can be seen that there does not exist a uniquely restricted matching over the choice of vertex sets {u 0 1 , x 1 , x 2 , x 3 } and {x 1 , x 2 , x 3 , y 1 1 }. The same can be said with respect to the vertex sets {u 0 1 , x 1 , x 2 , x 3 } and {x 1 , x 2 , y 1 1 , y matching on H ×5 , M ×5 is uniquely restricted. Moreover, since

E loop = ∅, M ×5 ∩ E loop = ∅.
Next, note that term-rank(D) = 1. The bipartite graph N 5 is given in Figure 2.55, while Figure 2.56 shows a matching S, of size 6, on H 5 . Since over the choice of vertex sets {u 0 1 , x 1 , x 2 , x 3 , x 4 , u 1 1 } and {y 0 1 , x 1 , x 2 , x 3 , x 4 , y 1 1 } there does not exist another matching on N 5 , S is uniquely restricted. Thus, the conditions (1a), (1b) and (1c) given in Thm. 3 are satisfied, and therefore the example given in Figure 2.48 is s-structurally ISO. A key tool in the development of results for s-structural observability involves transforming the matrix pencils into suitable triangular forms [START_REF] Chapman | On strong structural controllability of networked systems: a constrained matching approach[END_REF] 1 . We adopt a similar trick for developing our main results .

Definition 15

A matrix H is said to be in Form IV if where × denote fixed non-zero positions, 0 denote fixed zero positions and denote positions that could be either zero or non-zero.

H =    × 0 ...
The following lemma gives a sufficient condition for s-structural unconstrained ISO in terms of transformation of matrix pencil P (z) into Form IV.

Lemma 5 W * , B * , C * , D * is s-structurally unconstrained ISO if (i) there exists permutation matrices P 1 , P 2 such that the matrix

P 1 W B C D P 2 (2.4)
is in form IV, and

(ii) there exists permutation matrices P 3 , P 4 such that the matrix

P 3 W -zI N B C D P 4 (2.5)
is in form IV, and moreover the ×-terms do not correspond to (w iiz) with w ii = 0, ∀i ∈ {1, 2, . . . , N }.

Proof: Suppose that condition (i) is satisfied. Then from Definition 15 we know that there exists a square submatrix of size N + P that has ×-terms on the main diagonal and all the upper elements (i.e., elements above the main diagonal) are zero, and therefore this submatrix has non-zero determinant. This implies that, rank(P 1 P (0)P 2 ) = N + P , and hence rank(P (0)) = N + P . Suppose that condition (ii) is satisfied. As a consequence, for the permuted matrix P 3 P (z)P 4 , we can find a square submatrix of size N + P such that, some of the terms along the main diagonal are polynomials in z and the rest are strictly non-zero terms, or all terms on the main diagonal are strictly non-zero terms. In case of the former, the determinant of the said submatrix is a polynomial in z, which evaluates to zero only if z = 0, while in case of the latter the determinant is always non-zero. Thus, if condition (ii) is true then for all z ∈ C \ {0} rank(P 3 P (z)P 4 ) = N + P , and hence rank(P (z)) = N + P . Notice that since the system is LTI, the zero/non-zero pattern does not change with time. Therefore, from conditions (i) and (ii), for every W ∈ W * , B ∈ B * , C ∈ C * and D ∈ D * , rank(P (z)) = N + P for all z. Hence, from Lemma 4, the system W * , B * , C * , D * is sstructurally unconstrained ISO.

Using the algebraic conditions given in Lemma 5, we will now seek a sufficient condition in graph-theoretic terms.

The following lemma gives another equivalent characterization of uniquely restricted matchings.

Lemma 6 (Thm 3.1 [START_REF] Charles Golumbic | Uniquely restricted matchings[END_REF]) Let B = {V + , V -, E} be a bipartite graph. A matching M is uniquely restricted if and only if there exists a reordering of vertices

V + = {v 1 , . . . , v |V + | } and V -= {w 1 , . . . , w |V -| } such that (v i , w i ) ∈ M for all 1 ≤ i ≤ |M |, and (v i , w j ) / ∈ E for 1 ≤ j < i ≤ |M |.
From Definition 15 and Lemma 6, we obtain the following remark.

Remark 5

Let H be a structured matrix, and let B(H) be the associated bipartite graph. Suppose that there exists permutation matrices P 1 and P 2 such that P 1 HP 2 is in Form IV. Then the set of edges corresponding to the ×-terms in P 1 HP 2 forms a uniquely restricted matching M on B(P 1 HP 2 ). Moreover, all other edges in B(P 1 HP 2 ) are arranged below the edges contained in M.

We can now state a sufficient condition, in graph-theoretical terms, for s-structural unconstrained ISO.

Proof of Necessity

It turns out that the conditions given in Prop. 6 are also necessary for s-structural unconstrained ISO. The following proposition shows necessity of condition (i) in Prop. 6.

Proposition 7

W * , B * , C * , D * is s-structurally unconstrained ISO only if there exists a uniquely restricted matching M of size P + N on H.

Proof: Recall that H (see Figure 2.3) is the bipartite graph associated with the structured matrix W B C D . Suppose that there does not exist a uniquely restricted matching M of size N + P on H, then from Lemma 8 it follows that there exists a non-zero choice of free parameters for which the corresponding realization, say

W 1 B 1 C 1 D 1 with W 1 ∈ W * , B 1 ∈ B * , C 1 ∈ C * and D 1 ∈ D * , such that rank W 1 B 1 C 1 D 1 = N + P .
This further implies, from Definition 14, that W * , B * , C * , D * is not s-structurally unconstrained ISO.

We now turn our attention to showing necessity of condition (ii) in Prop. 6 for s-structural unconstrained ISO. The objective is to show that, after having fixed z to some constant, say z = 1, we can find a non-zero choice of free parameters for which the corresponding matrix pencil, P (1) in this case, is rank deficient. This implies, from Lemma 4, that W * , B * , C * , D * is not s-structurally unconstrained ISO. The matrix pencil P (z) evaluated at z = 1 is the following:

W -I N B C D
. Let P (1) be a submatrix of P (1) obtained by considering all rows and r, 1 ≤ r ≤ N + P , columns of P (1), and let H× be the corresponding bipartite graph.

H× is a subgraph of H × , having r (same as the columns of P (1)) vertices in its left vertex set, the right vertex set is X ∪ Y , and the edge set is Ẽ× . Ẽ× is obtained from E × by retaining only those edges that correspond to the r vertices in the left vertex set and deleting all the remaining edges.

The following proposition shows necessity of condition (ii) given in Prop 6.

Proposition 8 W * , B * , C * , D * is s-structurally unconstrained ISO only if there exists a uniquely restricted matching M × of size P + N on H × such that M × ∩ E loop = ∅.

We prove the claim made in Prop. 8 by proving a slightly stronger result, given in Lemma 7.

Lemma 7

Let r be any integer, where 1 ≤ r ≤ N + P . For any matrix P (1) formed with r columns of P (1), if there does not exist a uniquely restricted matching M× of size r on H× that satisfies M× ∩ E loop = ∅, then there exists a non-zero choice of free parameters such that the corresponding numerical realization of P (1) satisfies rank P (1) < r.

Setting r = N + P gives the desired result. The formulation for general r admits a proof by induction as explained in the following. Proof: Notice that P (1) has fixed zeros and distinct free parameters. Moreover, depending on whether or not W has a 0 along its diagonal, each row in P (1) may have either at most one fixed -1 term or no more than one free parameter offset by -1. The base case is r = 1, where P (1) has only 1 column and H× has only 1 vertex in its left vertex set. Note that a matching of size 1 is just an edge. By Definition 8, every matching of size 1 is uniquely restricted. If there does not exist a uniquely restricted matching M× of size 1 on H× that satisfies M× ∩ E loop = ∅, it follows that every edge in H× is w ii -1 for some i ∈ {1, . . . , N }. Given that a vertex cannot have more than one self-loop, it follows that P1 has exactly one term of the type w ii -1 and the remaining terms are zero. Fixing w ii = 1 implies rank P (1) = 0.

Let us assume that the claim holds for r -1 (inductive assumption) and we prove that this implies that the claim holds for r. P (1) may or may not have a row that contains exactly 1 non-zero term, and the two cases need to be handled by separate proofs. Case a: Suppose that there exists no row in P (1) having exactly one non-zero term. A row in P (1) may have at most one -1 term; if there is a -1 it might appear either as a fixed -1 or as a w ii -1 for some i ∈ {1, . . . , N }. This implies that there are three possible kinds of rows in P (1): i) all-zero row; ii) row with either one fixed -1 term or one w ii -1 term for i ∈ {1, . . . , N } and with p ≥ 1 free parameters; iii) row with neither fixed -1 term nor w ii -1 term and with p ≥ 2 free parameters. Rows of kind i) already have sum zero. For rows of kind ii), set each of the p -1 free parameters to any arbitrary value, say α i (α i ∈ Z + ), and fix the last free parameter to 1 -p-1 i=1 α i . For rows of kind iii), fix each of the p -1 free parameters to any arbitrary positive value and fix the last free parameter to -

p-1 i=1 α i .
With this (non-zero) choice of free parameters, each row in P (1) has sum zero. This in turn implies that the columns of P (1) are linearly dependent, and hence this numerical realization of P (1) satisfies rank P (1) < r.

Case b: Suppose that there exists a row in P (1) having exactly one non-zero term. This non-zero term could be either i) w mm -1 for some m ∈ {1, 2, . . . , N }; or ii) -1 or w ij or b ij or c ij or d ij . We will show that regardless of the type of entry one can find a desired non-zero choice of free parameters. b1: Suppose that all rows in P (1) having exactly one non-zero term have the non-zero term to be of the form w mm -1 for some m ∈ {1, 2, . . . , N }. This implies that all the remaining rows in P (1) have at least two non-zero terms, and thereafter using the technique described in Case a, one can obtain a non-zero choice of free parameters for which each row sums to zero. Setting w mm = . . . = w kk = 1 implies that each of the rows with exactly one non-zero term has zero sum. Hence, one obtains a non-zero choice of free parameters in P (1) for which the corresponding numerical realization satisfies rank P (1) < r.

b2: Suppose that there exists at least one row in P (1) having exactly one non-zero term and such that this term is not of the type w mm -1, m ∈ {1, 2, . . . , N }. That is, this term has to be either -1 or a free parameter of the type w ij or b ij or c ij or d ij . Assume that this term is in position (k, ). Let P (1) :,-denote the submatrix of P (1) obtained by removing column , and note that it has r -1 columns. Let Ĥ× be the bipartite graph obtained from H× by removing the edges involving vertex j. Since by assumption there does not exist a uniquely restricted matching M× of size r in H× that satisfies M× ∩ E loop = ∅, it implies that there does not exist a uniquely restricted matching M× of size r -1 in Ĥ× that satisfies M× ∩ E loop = ∅. Indeed, if there was one, then by adding the edge corresponding to the (k, )th entry in P (1) one can construct a uniquely restricted matching M× of size r in H× that satisfies M× ∩ E loop = ∅. Since there does not exist a uniquely restricted matching of size r -1 in Ĥ× that satisfies M× ∩ E loop = ∅, by inductive assumption it follows that there exists a non-zero choice of free parameters such that the corresponding numerical realization of P (1) ;,-has rank P (1) ;,-< r -1. Now take this same numerical realization of P (1) ;,-and to that append the column together with some arbitrary value in [ P (1)] k (provided it is not a fixed -1), so as to obtain a numerical realization of P (1). This numerical realization of P (1) satisfies rank P (1) < r, and thus the proof is complete. . The necessary conditions given in Prop. 7 and Prop. 8 are combined in the following result. (i) there exists a uniquely restricted matching M of size N + P on the bipartite graph H, and

(ii) there exists a uniquely restricted matching M × of size N + P on the bipartite graph H × such that M × ∩ E loop = ∅ .

Thus, from Props. 6 and 9, the result given in Theorem 2 is proved.

Proof of Theorem 3

Theorem 2 dealt with s-structural unconstrained ISO. To prove Theorem 3, what remains to be shown is that conditions c) and f) are respectively sufficient and necessary for s-structural delay-1 left invertibility.

Let Q =   D 0 0 B -I 0 0 C D   .
Note that the bipartite graph N represents the fixed zero pattern

Introduction

In Chapter 2, we saw graphical characterizations for structural (resp. s-structural) LTI systems, where both parameters and the structure remain constant over the time. In contrast, it is natural to assume that the parameters can evolve over the time while the structure remains fixed (LTV with fixed topology). Under such a scenario, necessary and sufficient conditions for structural observability of LTV systems are given in [START_REF] Poljak | On the generic dimension of controllable subspaces[END_REF], while necessary and sufficient conditions for s-structural observability are available in [START_REF] Reissig | Strong structural controllability and observability of linear time-varying systems[END_REF]. However, these results are not applicable for LTV systems with unknown inputs.

To the best of our knowledge, for discrete-time linear structured systems, a graph-theoretic characterization for the more general ISO problem encompassing multiple unknown inputs and accounting for LTV dynamics, is missing. As such the main contributions of this chapter are threefold; under suitable assumptions on the structure of the input and output matrices, first we show equivalence between ISO of a linear system and observability of a suitably defined subsystem. Second, we give a characterization of uniform N -step structural (see Thm. 4) (resp. uniform N -step strongly structural (see Thm. 5)) input and state observability, i.e., the conditions under which both the whole network state and the unknown input can be reconstructed for almost all (resp. all ) system matrices that share a common zero/non-zero 48 Chapter 3. Linear Time-Varying Network Systems with Fixed Topology pattern, over every time window of length N . This equivalence enables one to study structural (resp. s-structural) ISO using the graph techniques given in [START_REF] Commault | Characterization of generic properties of linear structured systems for efficient computations[END_REF], [START_REF] Chapman | On strong structural controllability of networked systems: a constrained matching approach[END_REF] (resp. [START_REF] Chapman | On strong structural controllability of networked systems: a constrained matching approach[END_REF], [START_REF] Trefois | Zero forcing number, constrained matchings and strong structural controllability[END_REF]). Note that the material contained in this chapter appeared in [START_REF] Gracy | Structural and Strongly Structural Input and State Observability of Linear Network Systems[END_REF].

Chapter Outline

The organization of this chapter is as follows: We state the problem in Section 3.2. Section 3.3, under suitable assumptions on the input and output matrices, shows the equivalence between ISO and observability of an appropriate subsystem. Section 3.4 discusses structural ISO, while Section 3.5 studies the stronger notion of s-structural ISO.

Problem Statement

Consider a linear network system with N nodes, represented by a graph G = {V, E} where V is the vertex set and E = {(j, i) ∈ V×V | [A G ] i,j = 1}; A G being the adjacency matrix of G. In this network, some states can be directly measured. They define the set

O = {j 1 , j 2 , • • • , j M } ⊆ V,
M being the number of observed states. From an analysis of the network, we assume that V can also be partitioned into assailable nodes and reliable ones. We define by

A = {i 1 , i 2 , • • • , i R }
the set of the R assailable nodes that may be attacked by P external malicious agents defining the set denoted by I, the attack being modeled as a unknown input. An illustration is given in Fig. 1 where three malicious nodes, namely, x, y, z can attack the network with vertex set V through agents k, j and i. A setup of this sort can be used as an abstraction to model attacks on multiple nodes including deception attacks [START_REF] Teixeira | Networked control systems under cyber attacks with applications to power networks[END_REF], false data injection [START_REF] Liu | False data injection attacks against state estimation in electric power grids[END_REF], fault diagnosis and detection [START_REF] Patton | Fault diagnosis in dynamic systems: theory and application[END_REF], input estimation in physiological systems [START_REF] De Nicolao | Nonparametric input estimation in physiological systems: problems, methods, and case studies[END_REF]. The dynamics of the linear network system described above is given by the following equations:

x k+1 = W k x k + A B u k y k = A C x k (3.1)
with state vector x k ∈ R N , unknown input vector u k ∈ R P and output vector y k ∈ R M . The system matrices are of appropriate dimensions. The matrices A B and A C are as given in Chapter 1 (see Sect. 1.2). For the rest of this chapter, over a given interval [k 0 , k 1 ], we denote the dynamics of a LTV system as W k , A B , A C } k 1 k 0 while that of a LTI system is indicated by

W, A B , A C } k 1 k 0 .
In what follows we assume that for all k belonging to Z,

W k ∈ W or in particular W k ∈ W * , where matrix set W = {Z 1 A G | Z 1 ∈ R N ×N } and W * = {Z 1 A G | Z 1 ∈ R N ×N * }. Both {W, A B , A C } and {W * , A B , A C }
impose a fixed zero structure. The remaining coefficients (i.e., not fixed to zero positions) of the matrices are referred to as free parameters. The free parameters of matrices belonging to W can take any values while those belonging to W * strictly take non-zero values. Notice that this assumption implies that the topology of G remains fixed but the entries corresponding to the free parameters of the system matrices may vary. For the particular case of LTI systems, the said entries remain constant. We narrow our attention to the case wherein each unknown input affects exactly one node of G and each node is at most affected by a single unknown input. This leads to the following assumption:

Assumption 1 (A1)

A B = e i 1 ;N e i 2 ;N . . e i P ;N , A T C = e j 1 ;N e j 2 ;N . . e j M ;N .

In the context of network systems, it is natural to think of states as local variables that are in different physical locations, whereas unknown inputs could be isolated entities that are at best able to attack a single state. For instance, the topology of a power distribution network can be considered as the connectivity between the meters installed at the substation, feeders, transformers, and consumer mains. An attack corresponds to addition or draining of active power while the state at each node can be measured using smart meters. As a consequence of assumption A1, we rule out scenarios wherein a linear combination of multiple unknown inputs affects a single node in G. Therefore, we have R = P . On the other hand, the unknown inputs are of arbitrary nature and for the particular case in which some of the unknown inputs are the same, we would have a single unknown input affecting multiple nodes in G and as such we provide sufficient but not necessary conditions for this setup as well.

Note that the setup in this chapter a particular case of the setting given by Eq.(1.1) in that we assume that the topology of the graph is fixed, while the weights along the edges are free to vary with time. Moreover, we assume that the input and output matrices have a particular structure (the details of which are given in assumption 1), and that there is no feedthrough. The zero feedthrough assumption is motivated by the following consideration: In a cyberphysical system (CPS) setting, an attacker(s) are able to attack the states of a system, but, possibly due to resource limitations, not the outputs. In such a case, the malicious unknown inputs cannot directly affect the outputs, but only through the states.

In this chapter, we first study conditions under which it is possible to jointly estimate both the initial state and the sequence of multiple unknown inputs for an LTV system W k , A B , A C } k 1 k 0 from measurements of a subset of state vertices. Thereafter, based only on the structure of the graph G, over all sufficiently long time windows, we will characterize ISO for i) almost all choices of entries in W (see Section 3.4) and ii) every choice of entries in W * (see Section 3.5).

A stronger notion of observability is that of uniform δ-step observability which requires that a system be observable over every time window of length δ [START_REF] William S Levine | The Control Handbook[END_REF]. Analogously, we define uniform δ-step ISO as follows:

Definition 17 The system W k , A B , A C } k∈Z is uniformly δ-step ISO if ∀k 0 ∈ Z W k , A B , A C } k 0 +δ k 0 is ISO over [k 0 , k 0 + δ].

Remark 6

Notice that although uniform δ-step ISO (resp. observability) is with respect to all intervals of length δ, it turns out that it can be rephrased considering all intervals of length at least δ. For observability, this is immediate: if a system is observable over [k 0 , k 0 + δ], then it is also observable over [k 0 , k 0 + η] for all η ≥ δ. For ISO, one needs to reconstruct all inputs up to k 0 + η -1 and not only those up to k 0 + δ -1. If the system is uniformly δ-step observable, it is possible to use δ-step ISO over successive time windows of length δ to ensure that all the required inputs are indeed reconstructed.

Remark 7

It is well-known that an LTI system is either not observable or is uniformly N -step observable in which case we would simply call it as observable.

Prop. 2 enables one to exploit the structure of Ψ k 0 ,k 1 so as to find some simple necessary conditions for Ψ k 0 ,k 1 to have full column rank. The following proposition briefly summarizes them.

Proposition 10

The following conditions are necessary for the system

W k , A B , A C } k 1 k 0 to be ISO over [k 0 , k 1 ]: i) rank(Θ k 0 ,k 1 ) = N , ii) rank (A C A B ) = P , iii) M ≥ P . iv) N ≥ P .
In case N > P , then the following conditions are also necessary:

v) M > P , vi) k 1 -k 0 ≥ N -M
M -P . In case P = N then the following conditions are necessary and sufficient:

M = N , ∀k ∈ [k 0 , k 1 ] rank(A C ) = N and ∀k ∈ [k 0 , k 1 -1] rank(A B ) = N .
Proof: Item i) requires that the first N columns of Ψ k 0 ,k 1 be linearly independent. Item ii) requires that the last P columns of Ψ k 0 ,k 1 be linearly independent, while items iii) and iv) are necessary conditions for item ii). To see the necessity of items v) and vi), notice that, in order for Ψ k 0 ,k 1 to be full column rank, it is necessary that Ψ k 0 ,k 1 has at least as many rows as columns, i.e.,

M (k 1 -k 0 + 1) ≥ N + (k 1 -k 0 )P.
From the above equation, since (k 1 -k 0 +1) > 0, it follows that M ≥ P + N -P (k 1 -k 0 +1) . If N > P , this implies that M > P . Then, under M > P , item vi) immediately follows from the above equation. For the particular case of M = P = N , notice that Ψ k 0 ,k 1 is a block lower triangular matrix with each of the blocks being square. Hence, a necessary and sufficient condition for full column rank of Ψ k 0 ,k 1 is that each of the diagonal blocks have full column rank. This is equivalent to

, i) rank(A C A B ) = N ∀k ∈ [k 0 + 1, k 1 ] and ii) rank(A C ) = N . Notice that ∀k ∈ [k 0 + 1, k 1 ], rank(A C A B ) = N if and only if: i) rank(A C ) = N and ii) rank(A B ) = N .
Notice that Prop. 10 fully characterizes the ISO problem for the particular case of P = N where, under A1, the system is ISO if and only if all nodes are observed (i.e., O = V). In this chapter we restrict our attention to the non-trivial case of N > P i.e., not all the nodes are assailable. Therefore, from Prop. 10, M > P is a necessary condition for ISO. From Prop. 10 we know that the following are necessary conditions for ISO:

1. all the assailable nodes are observed i.e., {i 1 , i 2 ,.., i P } ⊂ {j 1 , j 2 , . . . , j M } and 2. all of the assailable nodes are distinct i.e., there does not exist h, k belonging to {1, 2..., P } such that i h = i k .

We also assume that all of the observed nodes are distinct i.e., there does not exist h, k belonging to {1, 2..., M } such that j h = j k . This ensures that there are no repeated or dependent rows in C. Therefore, one can relabel the nodes in G in the following manner:

i 1 = j 1 = 1, i 2 = j 2 = 2, ..., i P = j P = P .
The aforesaid relabeling allows us to rewrite A B and A C as follows:

Assumption 2 (A2)

A B = e 1;N e 2;N . . . e P ;N , A T C = e 1;N e 2;N . . . e P ;N e j P +1 ;N . . . e j M ;N .

Note that assumption 1 is a matter of choice, i.e., even if the conditions given in this assumption are to be violated it does not mean the system {W, A B , A C } is not ISO. On the other hand, under Assumption 1, if the condition given in assumption 2 is violated, then the system {W, A B , A C } is not ISO.

ISO as Observability of an Appropriate subsystem

The objective here is to decompose the system W k , A B , A C } k 1 k 0 into two subsystems and show that ISO is equivalent to observability of one of the subsystems. It is crucial to notice here that the identity of the nodes being assailable remains fixed and, according to Assumption 2, equal to {1, 2, . . . , P }. Consequently, the nodes labeled from i P +1 , . . . , i N are not assailable. This enables us to decompose the state vector in two blocks: xk denoting states that are directly affected by the unknown inputs and xk for the remaining states; a corresponding partitioning is also done for the output vector, obtaining

x k = xk xk , y k = ŷk ỹk ,
with xk ∈ R P , xk ∈ R N-P , ŷk ∈ R P , and ỹk ∈ R M-P . Moreover, thanks to Assumption 2, the input and output matrices can be rewritten as follows:

A B = I P 0 , A C = I P 0 0 ÃC .
Therefore, the system W k , A B , A C } k 1 k 0 can be decomposed into two subsystems as follows:

xk+1 = Ŵk xk + Λx k + u k ŷk = xk (3) xk+1 = Wk xk + Ωx k ỹk = ÃC xk (4)
where we use the notation

W k = Ŵk Λ k Ω k Wk .
From (3), it is clear that xk is directly observed. Hence, (3) represents a system with known state but two unknown inputs, namely, xk and u k , while (4) represents a system with unknown state but known input. Hence, we have the following proposition.

Proposition 11

Under Assumption 2, the system

W k , A B , A C } k 1 k 0 is ISO over [k 0 , k 1 ] if and only if the system Wk , ÃC } k 1 k 0 is observable over [k 0 , k 1 ].
Proof: We define the matrices Q N and QN as follows:

Q N = I p 0 , QN = 0 I N -P .
Let Π 1 and Π 2 represent row and column permutation matrices respectively, defined as follows.

For column permutations, we put at the beginning the first P columns of each occurrence of A C , obtaining

J Π 2 = R 1 0 R 3 R 2 B k 0 ,k 1 R 4 ,
where

R 1 = I k 1 -k 0 +1 ⊗ A C Q N , R 2 =     W k 0 Q N -Q N 0 N
. . . . . . W k 1 -1 Q N -Q N     , R 3 = I k 1 -k 0 +1 ⊗ A C QN , and
R 4 =     W k 0 QN -QN 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 . . . W k 1 -1 QN -QN     .
For row permutations, consider the following steps: we first arrange the (k 1k 0 + 1) row blocks corresponding to the first P rows of each occurrence of A C , then the (k 1k 0 ) row blocks corresponding to the first P rows of each occurrence of A B , and finally the remaining rows , so as to obtain

Π 1 J Π 2 =     I (k 1 -k 0 +1)P 0 0 P 1 I (k 1 -k 0 )P P 2 0 0 C P 3 0 W    ,
where

P 1 =    Ŵk 0 -I P 0 . . . . . . . . . . . . . . . 0 . . . Ŵk 1 -1 -I P    , P 2 =    Λ k 0 0 . . . . . . . . . . . . . . . . . . 0 . . . Λ k 1 -1 0    , P 3 =    Ω k 0 0 . . . . . . . . . . . . . . . . . . 0 . . . Ω k 1 -1 0    , C = I k 1 -k 0 +1 ⊗ A C , and W =        Wk 0 -I N -P . . . . . . 0 0 Wk 0 +1 -I N -P . . . 0 . . . . . . . . . . . . . . . . . . . . . . 0 . . . . . . Wk 1 -1 -I N -P        . Let J = Π 1 J Π 2 , Ĵ =   I (k 1 -k 0 )P P 2 0 C 0 W  , and
J = C W .
Notice that J is block lower triangular with the blocks over the diagonal I (k 1 -k 0 +1)P and Ĵ . This implies rank ( J ) = (k 1k 0 + 1)P + rank ( Ĵ ). Ĵ is block upper triangular with blocks over the diagonal I (k 1 -k 0 )P and J . Therefore, the following holds:

rank ( J ) = (k 1 -k 0 + 1)P + (k 1 -k 0 )P + rank ( J ). From Remark 1 we know that W k , A B , A C } k 1 k 0 is ISO over [k 0 , k 1 ] if and only if rank ( J ) = (k 1 -k 0 )P + (k 1 -k 0 + 1)N , which in turn is equivalent to rank ( J ) = (k 1 -k 0 + 1)(N -P ). From Prop. 3, the latter corresponds to observability of Wk , ÃC } k 1 k 0 over [k 0 , k 1 ].
The result in Prop. 11 can be interpreted as follows: when the subsystem { Wk , ÃC } k 1 k 0 is observable over [k 0 , k 1 ], one of the two unknown inputs in (3), namely xk , is known and hence it is possible to compute u k , since xk is directly measured. For LTI systems, alternatively, the PBH rank test may also be used to prove Prop. 11 as was shown by Prop. 4 in [START_REF] Kibangou | Input and state observability of network systems with a single unknown input[END_REF], albeit for single unknown input. The details are given in Appendix A.

Structural ISO

The main objective of this section is to characterize ISO for almost all choices of free parameters.

Definition and Implications

We denote by W, A B , A C } LTV the family of all LTV systems as given in (3.1) and having the same zero/non-zero pattern as given by W, A B and A C while W, A B , A C } LTI represents the corresponding family of all LTI systems. Note that both W, A B , A C } LTV and W, A B , A C } LTI are represented by the same graph G. In case of the former, the edge weights in G can take different values over a given interval [k 0 , k 1 ], whereas for the latter, the edge weights in G remain fixed. As mentioned previously, structured systems have fixed zero positions and free parameters. Let |E| denote the number of ones in A G . Under such a setup, the free parameters can take values in R (|E|)(k 1 -k 0 ) , where [k 0 , k 1 ] represents the time window over which the system W, A B , A C } LTV is being observed. We assume that the parameters are algebraically independent not only with respect to space, but also to time. Notice that each element in R (|E|)(k 1 -k 0 ) yields a choice of free parameters. Structural ISO then asks that there be at least one member in W, A B , A C } LTV which is observable. This leads us to the following definition.

Chapter 3. Linear Time-Varying Network Systems with Fixed Topology

Under Assumption 2, W, A B , A C } LTV is structurally ISO over [k 0 , k 1 ] if and only if W, ÃC } LTV is structurally observable over [k 0 , k 1 ].
The advantage of Prop. 12 is that it breaks down the problem of structural ISO into an equivalent problem in structural observability. However, the downside is that the conditions given in Prop. 12 are with respect to a given interval [k 0 , k 1 ]. We seek results that are not dependent on the choice of intervals. To this end, we rewrite Thm. 3 in [START_REF] Poljak | On the gap between the structural controllability of time-varying and time-invariant systems[END_REF] (also see [START_REF] Poljak | On the generic dimension of controllable subspaces[END_REF]) for observability. This rewriting yields equivalence between structural observability for LTV and LTI systems, and is given by the following proposition.

Proposition 13 (Thm. 3 in [START_REF] Poljak | On the gap between the structural controllability of time-varying and time-invariant systems[END_REF]) Under Assumption 2, over any interval [k 0 , k 1 ] of length at least N , W, ÃC } LTV is structurally observable if and only if W, ÃC } LTI is structurally observable.

Prop. 12 and Prop. 13 together break down the structural ISO problem of LTV systems into a structural observability problem of a corresponding suitably defined LTI subsystem. Thanks to [START_REF] Commault | Characterization of generic properties of linear structured systems for efficient computations[END_REF] it turns out that the structural observability of an LTI subsystem can be determined by checking certain graph-theoretical conditions. Before proceeding, we need a few constructs on G. Let G be the graph corresponding to W. Let S = {L 1 , L 2 , E S } be a bipartite graph associated with G, with L 1 = Ṽ \ Õ, L 2 = Ṽ constructed in the following manner, two vertices in L 1 and L 2 that correspond to the same element v ∈ Ṽ are denoted as u v and w v respectively, and

E S = {(u i , w j ) ∈ L 1 × L 2 | (i, j) ∈ Ẽ}.
Recalling Definitions 6 and 8 from Chapter 1, we state the following result, rephrased for observability Lemma 12 (Thm. 1 [START_REF] Chapman | On strong structural controllability of networked systems: a constrained matching approach[END_REF])

The system W, ÃC } LTI is structurally observable if and only if:

1. G is output-connected;
2. there exists a matching in S of size N -| Õ|.

As an aside, the above result previously appeared in [START_REF] Commault | Characterization of generic properties of linear structured systems for efficient computations[END_REF] and [START_REF] Commault | Observability preservation under sensor failure[END_REF]. With Lemma 12 in place, we present the first main result of the present chapter.

Theorem 4

Under Assumption 2, W, A B , A C } LTV is uniformly N -step structurally ISO if and only if the following conditions are satisfied:

1. G is output-connected;
2. there exists a matching in S of size N -| Õ|.

Structural ISO 57

Proof: From Prop. 12, it can be seen that under Assumption 2, the system W, A B , A C } LTV is structurally ISO over [k 0 , k 1 ] if and only if the subsystem W, ÃC } LTV is structurally observable over [k 0 , k 1 ], while from Prop. 13 it can be seen that the subsystem W, ÃC } LTV is structurally observable over [k 0 , k 1 ] if and only if the corresponding LTI subsystem W, ÃC } LTI is structurally observable. It is well-known that LTI systems are either observable over every sufficiently long interval or not observable at all. Thus, setting δ = N in Remark 6, and from Prop. 12 and Prop. 13, it follows that under Assumption 2, the system W, A B , A C } LTV is structurally ISO over [k 0 , k 1 ] if and only if the subsystem W, ÃC } LTI is uniform N-step structural ISO. Thereafter, from Lemma 12, the proof is complete.

S-Structural ISO

The main objective of this section is to characterize ISO for every choice of entry in W * .

Definition

S-structural properties are those that hold for every non-zero choice of free parameters of the system matrices. That is, s-structural ISO (resp. observability) requires that every member of the family of LTV systems given by W * , A B , A C } LTV , be ISO (resp. observable). This leads us to the following definition.

Definition 19

Let

k 1 , k 0 ∈ Z and k 1 > k 0 , W * , A B , A C } LTV is s-structurally ISO on [k 0 , k 1 ] if for ev- ery system W k , A B , A C } k 1 k 0 with W k ∈ W * , W k , A B , A C } k 1 k 0 is ISO.
Analogous to Definition 19, one can define s-structural observability and uniform N -step sstructural observability for LTV systems. In particular, definitions for s-structural ISO, sstructural observability and uniform N -step s-structural observability can also be obtained for LTI systems.

It turns out that s-structural ISO for a family of LTV systems implies s-structural ISO for the corresponding family of LTI systems, and is given by the following remark

Remark 10

If the system {W * , A B , A C } LTV is s-structurally ISO over an interval [k 0 , k 1 ], then the corresponding LTI system {W * , A B , A C } LTI is s-structurally ISO. Indeed, if the system {W * , A B , A C } LTI is not s-structurally ISO, then from Definition 19 there exists a system

{W 1 , A B , A C } with W 1 ∈ W * such that {W 1 , A B , A C } is not ISO. Over any interval [k 0 , k 1 ], we can set W k = W 1 ∀k ∈ [k 0 , k 1 ] such that the LTV system {W k , A B , A C } k 1 k 0 is not ISO.
Consequently, from Definition 19, the system {W * , A B , A C } LTV is not s-structurally ISO over any interval.

S-Structural ISO 59

Notice that for structural ISO the implication is in the other direction (see Remark 8). The converse of Remark 10 remains open. In the rest of this section we show that, under Assumption 2, over sufficiently long intervals, the conditions given in Remark 10 are equivalent.

Uniform N -step s-structural ISO for LTV systems

The set of matrices W * is defined analogous to W. One can use Prop. 11 so as to obtain s-structural ISO results. We first focus on LTI systems. As another consequence of Prop. 11, we have the following:

Remark 11 Under Assumption 2, W * , A B , A C } LTI is uniform N -step s-structural ISO if and only if W * , ÃC } LTI is s-structurally observable.
It turns out that one can obtain similar conditions for LTV systems as well, as shall be seen in the rest of this subsection. First notice that another immediate corollary of Prop. 11 can be stated as follows

Proposition 14 Under Assumption 2, W * , A B , A C } LTV is s-structurally ISO over [k 0 , k 1 ] if and only if W * , ÃC } LTV is s-structurally observable over [k 0 , k 1 ].
Thanks to Prop. 14, we can now rephrase s-structural ISO of a family of LTV systems as an equivalent problem in s-structural observability of a suitable family of LTV systems. Against this backdrop, it is indeed relevant to see if s-structural ISO of LTV systems is equivalent to s-structural observability of a suitable family of LTI systems. The following proposition, immediate from Corollary IV.2 in [START_REF] Reissig | Strong structural controllability and observability of linear time-varying systems[END_REF], addresses equivalence between s-structural observability of a family of LTV systems and s-structural observability of the corresponding family of LTI systems.

Proposition 15

Under Assumption 2, over any interval [k 0 , k 1 ] of length at least N , W * , ÃC } LTV is sstructurally observable if and only if W * , ÃC } LTI is s-structurally observable.

Thus, from Prop. 14 and Prop. 15, it can be seen that under Assumption 2, the s-structural ISO problem for LTV systems breaks down into an equivalent problem in s-structural observability for a suitably defined LTI subsystem. This equivalence allows us to take advantage of the existing results on s-structural observability for LTI network systems, as we see in the following.

Thanks to [START_REF] Chapman | On strong structural controllability of networked systems: a constrained matching approach[END_REF], (also see [START_REF] Trefois | Zero forcing number, constrained matchings and strong structural controllability[END_REF]), it turns out that s-structural observability of an LTI system can be assessed by checking some graph-theoretical conditions. Here we would be focusing on the notion of uniquely restricted matching as in [START_REF] Chapman | On strong structural controllability of networked systems: a constrained matching approach[END_REF]. In order to proceed, a few constructs on the graph G are due. E loop ⊂ E S denote the edges of the form {u i , w i } if there exists any. Notice that E loop corresponds to self-loops in G. Let E new denote the set of newly added self-loops in G i.e., adding self-loops for those vertices i ∈ Ṽ that previously did not have one in G. Let S × = {L 1 , L 2 , E S × }, where E S × = {E S ∪ E new }, denote another bipartite graph on G. We recall that a matching is said to be uniquely restricted if there is no other matching involving the same vertex set. Equivalent characterizations of uniquely restricted matchings are discussed in [START_REF] Charles Golumbic | Uniquely restricted matchings[END_REF].

The following result is the same as Thm. 5 in [START_REF] Chapman | On strong structural controllability of networked systems: a constrained matching approach[END_REF] but rewritten for s-structural observability.

Lemma 13 (Thm. 5 [START_REF] Chapman | On strong structural controllability of networked systems: a constrained matching approach[END_REF])

The system W * , ÃC } LTI is s-structurally observable if and only if:

1. there exists a uniquely restricted matching M ⊆ E S of size N -| Õ|;

2. there exists a uniquely restricted matching

M × ⊆ E S × of size N -| Õ| such that M × ∩ E loop = ∅.
With Lemma 13 in place we present the second main result in the following theorem.

Theorem 5

Under Assumption 2, W * , A B , A C } LTV is uniformly N -step s-structurally ISO if and only if the following two conditions are satisfied:

1. there exists a uniquely restricted matching M ⊆ E S of size N -| Õ|;

2. there exists a uniquely restricted matching

M × ⊆ E S × of size N -| Õ| such that M × ∩ E loop = ∅.
Proof: From Prop. 14 and Prop. 15, it can be seen that under Assumption 2, W * , A B , A C } LTV is s-structurally ISO over any interval of length at least N if and only if W * , ÃC } LTI is s-structurally observable, while from Prop. 15, it can also be seen that W * , ÃC } LTI is sstructurally observable if and only if W * , ÃC } LTV is s-structurally observable over every interval of length at least N . Thus, Prop. 14 and Prop. 15 together with setting δ = N in Remark 6, results in the following: under A2, W * , A B , A C } LTV is s-structurally ISO if and only if the LTI subsystem W * , ÃC } LTI is uniform N -step s-structural ISO. Thereafter, from Lemma 13, the proof is complete. The conditions in Thm. 5 can be checked using the algorithm given in [START_REF] Chapman | On strong structural controllability of networked systems: a constrained matching approach[END_REF], with complexity O(| Ṽ| 2 ), or with the algorithm introduced in [START_REF] Weber | A linear time algorithm to verify strong structural controllability[END_REF], which achives a linear complexity O(| Ṽ|+| Ẽ|) by combining sophisticated data structures and sparse matrix techniques. We shall now apply the conditions given in Thm. 5 to the running example given in Figure 3.1.

Example 1 (continued): With respect to the system given in

E new = {(u a , w a ), (u b , w b ), (u c , w c )} while E loop = {(u d , w d )} Figure 3.6: A matching M × in S ×
It can be seen that M × = {(u a , w a ), (u b , w b ), (u c , w c ), (u d , w e )} (see Figure 3.6) is a matching in S × that satisfies M × ∩E loop = ∅. Notice that there exists no other matching M× ⊂ E S × saturating the same vertices as M × . Therefore, from Thm. 5, the system given in Figure 3.1 is uniformly N -step s-structurally ISO.

Now consider another example

Example 2: Consider the system given in Figure 3.7, whose corresponding subsystem is given in Figure 3.8, while a bipartite graph associated with the subsystem G1 is given in Figure 3.9. It is immediate that the subsystem G1 is output-connected. Furthermore, there also exists a matching of size N -| Õ| on the bipartite graph S 1 . Therefore from Thm. 4 the system given in Figure 3.7 is uniformly N -step structurally ISO. On the other hand, from Figures 3.10 and 3.11 it can be seen that there does not exist a uniquely restricted matching over the choice of vertex sets {u a , u b , u c } and {w a , w b , w c }. The same can be said with respect to the vertex sets {u a , u b , u c } and {w a , w b , w d } (see Figures 3.12 and 3.13), {u a , u b , u c } and {w b , w c , w d } (see Figures 3.14 and 3.15), {u a , u b , u c } and {w a , w c , w d } (see Figures 3.16 and 3.17). Thus, there does not exist a uniquely restricted matching of size N -| Õ| on the bipartite graph S 1 , and hence, from Thm. 5, the system given in Figure 3.7 is not uniformly N -step s-structurally ISO.

Introduction

Chapter 3 dealt with graphical characterizations for structural (resp. s-structural) ISO for LTV systems represented by fixed graphs. Note that the findings in Chapter 3 had certain limitations. First, the following assumptions were made on the structure of input and output matrices: each unknown input affected exactly one state; each state was affected by at most one unknown input; direct measurements of a few states were available (so-called dedicated sensors); and zero feedthrough. As a consequence of such assumptions, the problem of ISO was equivalent to an observability problem of a suitably defined subsystem. Thereafter, one took advantage of this equivalence to study structural (resp. s-structural) ISO. However, the extension of these results accounting for arbitrary structure of input and output matrices is non-trivial, since one cannot rephrase ISO as an equivalent problem in observability. Second, these results do not extend immediately to the case wherein the topology of the network varies over an interval. To the best of our knowledge, for linear network systems wherein 66 Chapter 4. Linear Network Systems with Time-Varying Topology the underlying topology varies over an interval, a characterization for structural (resp. sstructural) ISO, factoring in arbitrary time-varying input, output and feedthrough matrices, is still missing. The aim of the present chapter is to close this gap.

Our main contributions are twofold. Firstly, for the case where the topology of the network evolves over an interval, we give two graphical characterizations for structural ISO that also accounts for zero feedthrough (see Theorem 6). Secondly, under the aforesaid setting, for s-structural ISO, we provide two conditions which are sufficient (item 1 in Theorem 7) and necessary (item 2 in Theorem 7). Furthermore, under some assumptions on the feedthrough matrix, the two conditions can be combined to give a necessary and sufficient condition for s-structural ISO (see Corollary 2). The results, namely Theorem 6 and Theorem 7, are also applicable to time-invariant topologies, and hence generalize the results in [START_REF] Poljak | On the generic dimension of controllable subspaces[END_REF] (resp. [START_REF] Reissig | Strong structural controllability and observability of linear time-varying systems[END_REF]) to the case of structural (resp. s-structural) ISO, and also those in Chapter 3 by accounting for arbitrary structures of input, output and feedthrough matrices. Note that the material contained in this chapter is taken from [START_REF] Gracy | Input and State Observability of Network Systems with time-varying toplogy[END_REF].

The organization of the present chapter is as follows: We first state the problem under consideration in Section 4.2. Section 4.3 lays the groundwork for migrating to a graphical characterization. Section 4.4 gives the first main result that deals with structural ISO, while Section 4.5 introduces the second main result that concerns s-structural ISO.

Problem Formulation

In this chapter, we consider the same setup as given in Chapter 1 (see Section 1.2). We recall Equation 1.1 here for ease of readability.

x k+1 = W k x k + B k u k y k = C k x k + D k u k
We assume that the sequence of time-varying topologies is known. The setup described herein differs from the one in [START_REF] Liu | Structural controllability of switched linear systems[END_REF] in the sense that there is no switching rule governing the change in the network topology at each time instant. Furthermore, it also differs from the framework in [START_REF] Zheng | Switching and Data Injection Attacks on Stochastic Cyber-Physical Systems: Modeling, Resilient Estimation and Attack Mitigation[END_REF] in the sense that while the unknown inputs are free to attack any nodes at each time-instant, they have no influence on the evolution of the topology of the network.

We assume that, in general, for any

k 0 , k 1 ∈ Z the graphs G k 0 = (V, E k 0 ) and G k 1 = (V, E k 1 ) might be different i.e., E k 0 = E k 1 . For an illustration see Figures 4.1, 4.
2 wherein G k is periodic with periodicity 2, i.e., G k alternates between the depicted topologies with period 2.

Note that in Chapter 1 Section 1.2 we defined the family of systems

W k , B k , C k , D k } (resp. W * k , B * k , C * k , D * k }
) and studied structural (resp. s-structural) ISO with respect to subclasses of this family of systems in Chapters 2 and 3.

In this chapter, for a network system with (possibly) time-varying topologies over a given time interval, we characterize ISO for i) almost all system matrices as given in (1.1) with

W k ∈ W k , B k ∈ B k , C k ∈ C k and D k ∈ D k ,
respectively (see Section 4.4) and ii) every system matrix as given in (1.1) with

W k ∈ W * k , B k ∈ B * k , C k ∈ C * k and D k ∈ D * k ,

Prerequisites for main results

The main results contained in the present chapter are reliant on notions of dynamic graph and dynamic bipartite graph. In this section, we introduce these notions.

Dynamic Graph

Inspired by [START_REF] Murota | Matrices and matroids for systems analysis[END_REF], we introduce the notion of dynamic graph, denoted as S k 0 ,k 1 , and we show a relation between the entries in Ψ k 0 ,k 1 and the paths in S k 0 ,k 1 . The dynamic graph is constructed in the following manner: First, create (k 1k 0 + 1) copies of vertex sets X, U and Y , respectively. Label these copies as X k 0 , X k 0 +1 , . . ., X k 1 . Analogously, label the copies of U and Y . x i k , (resp. u i k and y i k ) is the vertex associated with the i th entry of the vertex sets X k (resp. U k and Y k ). Second, we assign edges and their weights as follows: There exists an edge between vertices x i k and x j k+1 if and only if (x i , x j ) ∈ E W k , and the weight on such an edge is w k (x i , x j ). Analogously, the edges between vertices u i k and x j k+1 , between x i k and y j k , and between u i k and y j k are obtained with the corresponding edge weights. For a pictorial description of the aforesaid, see Figure 4

.4. Let X = X k 0 ∪ X k 0 +1 ∪ . . . ∪ X k 1 .
Analogously, we define Ū and Ȳ . Notice that, for Ψ k 0 ,k 1 , the rows correspond to vertices in Ȳ ; while the first N columns correspond to vertices of X k 0 , and the remaining (k 1k 0 + 1)P columns correspond to vertices of Ū . In the dynamic graph S k 0 ,k 1 we define the cost of the path as the product of the weights along the edges of the path. Having defined the notion of cost, we use the following remark to address a relation between coefficients in Ψ k 0 ,k 1 and the paths, in

S k 0 ,k 1 , from X k 0 ∪ Ū to Ȳ . Remark 12 Notice that [C k+ W k+ -1 . . . W k ] ij = h 1 h 2 . . . h [C k+ ] ih [W k+ -1 ] h h -1 . . . [W k ] h 0 j ,
and hence it equals the sum of costs over all paths from x j k to y i k+ in S k 0 ,k 1 . Similarly,

Figure 4.4: Dynamic graph S k 0 ,k 1 [C k+ W k+ -1 . . . W k+1 B k ] ij = h 1 h 2 . . . h [C k+ ] ih [W k+ -1 ] h h -1 . . . [W k+1 ] h 1 h 0 [B k ] h 0 j ,
and hence it equals the sum of costs over all paths from u j k to y i k+ in S k 0 ,k 1 .

It turns out that a linking in S k 0 ,k 1 could have a subgraph which is a (suitably-defined) bipartite graph. We shall address it in the following remark, which in turn will aid the development of our main result Theorem 6.

Remark 13

Notice that, in S k 0 ,k 1 , a vertex in U k 1 may be connected only to some vertex in Y k 1 (via D k 1 ). The restriction of S k 0 ,k 1 to vertices in U k 1 leads to the bipartite graph B(D

k 1 ) = {U k 1 , Y k 1 , E(D k 1 )}.
Therefore, a linking in S k 0 ,k 1 has a subgraph that is a matching in B(D k 1 ). Hence, from Definition 10, a linking in S k 0 ,k 1 can saturate at most term-rank(D k 1 ) vertices in U k 1 .

Dynamic bipartite graph

Similar to dynamic graph S k 0 ,k 1 introduced in the previous subsection, there exists yet another equivalent graphical representation: the dynamic bipartite graph. In this subsection we shall acquaint ourselves with the same. Recall that J k 0 ,k 1 is a structured matrix with some of its free parameters set to -1. Let B(J k 0 ,k 1 ) be the bipartite graph associated with the matrix J k 0 ,k 1 . We shall refer to B(J k 0 ,k 1 ) as the dynamic bipartite graph associated with our system given by {G k }. In B(J k 0 ,k 1 ), the left vertex set is Ū ∪ X. In order to better highlight the connection between B(J k 0 ,k 1 ) and andx i k be the vertex associated with the i th entry in the vertex set X k . Note that the left vertex set corresponds to the columns of J k 0 ,k 1 , while the right vertex set corresponds to the rows of J k 0 ,k 1 . The edges in B(J k 0 ,k 1 ) obtained by looking at the matrices

S k 0 ,k 1 , it is convenient to rearrange the left vertex set as X k 0 , U k 0 , X k 0 +1 , U k 0 +1 , . . ., X k 1 , U k 1 . The right vertex set is X ∪ Ȳ . X = X k 0 +1 ∪ . . . ∪ X k 1 ,
{W k } k 1 -1 k 0 , {B k } k 1 -1 k 0 , {C k } k 1 k 0 and {D k } k 1
k 0 are in one-to-one correspondence with the edges in S k 0 ,k 1 , and are referred to as old edges. On the other hand, the edges in B(J k 0 ,k 1 ) corresponding to -I N ×N are referred to as new edges. For a pictorial description, see

Structural ISO

The main objective of this section is to characterize ISO for almost all system matrices as given in (1.1) with

W k ∈ W k , B k ∈ B k , C k ∈ C k and D k ∈ D k ,
respectively. Towards this end, we first define structural ISO and thereafter provide a graphical characterization for the same. Recall from Chapter 1 (see Sect. 1.2) that we denote by

W k , B k , C k , D k } k 1
k 0 the family of all systems whose dynamics are as given in Eq. (1.1), and for every k

∈ [k 0 , k 1 ], W k ∈ W k , B k ∈ B k , C k ∈ C k and D k ∈ D k .
With this notation in place, we define structural ISO as follows:

Definition 20 Let k 1 , k 0 ∈ Z and k 1 > k 0 . W k , B k , C k , D k } k 1 k 0 is structurally ISO, over [k 0 , k 1 ], if
for almost all choices of free parameters the corresponding system

W k , B k , C k , D k } k 1 k 0 , is ISO.

Main Result

Theorem 6

Consider the system (1.1) with the pattern of fixed zeros given by the graphs {G k }. Let S k 0 ,k 1 and B(J k 0 ,k 1 ) be the corresponding dynamic graph and dynamic bipartite graph, respectively.

The following statements are equivalent: Our main result should be understood in the following sense: if the condition is satisfied, then, over [k 0 , k 1 ], for almost all choices of free parameters except (possibly) for those lying on a subvariety of the space of free parameters, the corresponding system is ISO. On the other hand, if the condition is violated, then, over [k 0 , k 1 ], for almost all choices of free parameters, the corresponding system is not ISO. However, for at most few choices of free parameters, over [k 0 , k 1 ], the corresponding system might be ISO. We would like to point out that for the case of zero-feedthrough, if the given condition is violated, then since D k 1 = 0, from Prop. 6 in [START_REF] Gracy | Structural and Strongly Structural Input and State Observability of Linear Network Systems[END_REF], for every choice of free parameter, the corresponding system is not ISO. Theorem 6, in particular, applies to the case where the graph is fixed but the weights along the edges vary with time, as is the setting considered in Chap. 3. Consequently, it is a stronger result -in the sense of not making any assumptions on the structure of input, output and feedthrough matrices-than that given in Theorem 4.

We shall now apply the conditions given in Theorem 6 to the example given in

→ y 1 0 , x 2 0 → y 2 0 , x 3 0 → x 3 1 → y 1 1 , x 4 0 → x 4 1 → y 2 1 , u 1 0 → x 1 1 → x 1 2 → y 1 2 , u 1 1 → x 2 2 → y 2 2 .
Thus, the sufficient condition given in Theorem 6 is satisfied, and consequently the structured system represented by We first show that conditions given in item b) imply those in item a), then we prove that conditions given in item c) imply those in item b), and we conclude by showing that conditions in item a) imply those in item c).

b) =⇒ a)

With Lemma 3 in hand, the following lemma gives a sufficient condition for system (1.1) to be structurally ISO over [k 0 , k 1 ].

Lemma 14

If there exists a linking L of size N + (k 1k 0 )P + term-rank(D k 1 ), in the dynamic graph S k 0 ,k 1 , from X k 0 ∪ Ū to Ȳ , then over [k 0 , k 1 ] system (1.1) is structurally ISO.

Proof: The idea here is that it suffices to show that gen-rank(Ψ k 0 ,k 1 ) equals N + (k 1k 0 )P + term-rank(D k 1 ). We achieve the same by exhibiting one choice of free parameters for which the corresponding ISO matrix has rank equals N +(k 1 -k 0 )P +term-rank(D k 1 ), and thereafter, we make use of Lemma 3. We proceed as follows: Fix a linking L of size N + (k 1k 0 )P + term-rank(D k 1 ), in the dynamic graph S k 0 ,k 1 , from X k 0 ∪ Ū to Ȳ . Let k ∈ {k 0 , k 0 + 1, . . . , k 1 -1}. If there exists an edge in L between x j k and x i k+1 , then set [W k ] ij to 1 else set it to 0. Similarly, if there exists an edge in L between u j k and x i k+1 , then set [B k ] ij to 1 else set it to 0. If there exists an edge in L between x j k and y i k , then set [C k ] ij to 1 else set it to 0. Similarly, if there exists an edge in L between u j k and y i k , then set [D k ] ij to 1 else set it to 0. Notice that with this choice of free parameters, if a path is in the linking L, then it has cost 1; else it has cost 0. Since size of L, from X k 0 ∪ Ū to Ȳ , equals N +(k 1 -k 0 )P +term-rank(D k 1 ), it implies, from Definition 7 and Remark 13, that for every x j k 0 ∈ X k 0 , for every u j k ∈ Ū \U k 1 , and for exactly term-rank(D k 1 ) vertices in U k 1 , the linking L has a unique path saturating it; say a path from v j k ∈ X k 0 ∪ Ū to some y i k+ ∈ Ȳ ( ≥ 0). On the other hand, the linking L does not saturate (P -term-rank(D k 1 )) vertices in U k 1 , and consequently (P -term-rank(D k 1 )) columns in Ψ k 0 ,k 1 are all-zero. Thanks to Remark 12, it implies that the j th column of Ψ k 0 ,k 1 , where j ∈ {1, 2, . . . , N, N + 1, N + 2, . . . , N + (k 1k 0 )P + j}1 , has a 1 in position ( × M ) + i, and all other entries in the j th column are zero. Therefore, in Ψ k 0 ,k 1 , N +(k 1 -k 0 )P +term-rank(D k 1 ) columns have exactly one 1. Also notice, from Definition 7, that a vertex y i k ∈ Ȳ can be connected to at most one vertex v j k ∈ X k 0 ∪ Ū . Thus, with this choice of free parameters in Ψ k 0 ,k 1 , rank(Ψ k 0 ,k 1 ) = N + (k 1k 0 )P + term-rank(D k 1 ). Therefore, from Lemma 3, gen-rank(Ψ k 0 ,k 1 ) = N + (k 1k 0 )P + term-rank(D k 1 ), and hence, from Prop. 2, system (1.1) is structurally ISO over [k 0 , k 1 ].

c) =⇒ b)

The conditions given in item c) are sufficient for those given in item b), as shall be shown in the following lemma.

Lemma 15

If there exists a matching of size (k 1k 0 + 1)N + (k 1k 0 )P + term-rank(D k 1 ) on the dynamic bipartite graph B(J k 0 ,k 1 ), then there exists a linking of size N + (k 1k 0 )P + term-rank(D k 1 ) on the dynamic graph S k 0 ,k 1 , from X k 0 ∪ Ū to Ȳ .

Proof: Let M be a matching of size (k 1k 0 + 1)N + (k 1k 0 )P + term-rank(D k 1 ) on the dynamic bipartite graph B(J k 0 ,k 1 ). Notice that X ∪ Ū = (k 1k 0 + 1)N + k 1k 0 + 1)P , and at most term-rank(D k 1 ) vertices of U k 1 are saturated by M. Hence, M saturates every vertex in X ∪ Ū \ U k 1 , and exactly term-rank(D k 1 ) vertices of U k 1 . For every x j k 0 ∈ X k 0 , u j k ∈ Ū \ U k 1 , and for every u j k ∈ U k 1 saturated by M, we construct a path in the dynamic graph S k 0 ,k 1 in the following manner: Starting from x j k 0 ∈ X k 0 , we consider the edge that saturates x j k 0 in M; either it is (x j k 0 , y i k 0 ) for some y i k 0 ∈ Ȳ , and in this case (x j k 0 , y i k 0 ) gives a path of length 1 in S k 0 ,k 1 , or it is (x j k 0 , x j 1 k 0 +1 ) for some x j 1 k 0 +1 ∈ X . In the latter case, we add the edge (x j k 0 , x j 1 k 0 +1 ) to our path construction. Then, we look at vertex x j 1 k 0 +1 in B(J k 0 ,k 1 ). Now x j 1 k 0 +1 is saturated in M by some edge which cannot be any of the new edges since x j 1 k 0 +1 is already saturated via (x j k 0 , x j 1 k 0 +1 ). Consequently, x j 1 k 0 +1 is connected either to some y i k 0 +1 or to x j 2 k 0 +2 , and we can include the corresponding edge in our path construction; and the process repeats. Indeed, in case the construction does not reach any y k ∈ Ȳ for k ≤ k 1 -1, then it reaches some x j k 1 -k 0 ∈ X k 1 , and from there, it necessarily reaches some y i ∈ Y k 1 , because there is no vertex set X k 1 +1 . Analogously, paths can be constructed for every u j k ∈ Ū \ U k 1 , and for every u j k ∈ U k 1 saturated by M. By construction, since all edges in the paths correspond to some edges in M, the paths are vertex-disjoint. Hence, by Definition 7, they form a linking from X k 0 ∪ Ū to Ȳ in the dynamic graph S k 0 ,k 1 . Moreover, the linking has the correct size, i.e., N +(k 1 -k 0 )P +term-rank(D k 1 ).

An illustration of the proof technique used in Lemma 15 is as follows: B(J 0,2 ) is the dynamic bipartite graph shown in Figure 4.8. A matching M 0,2 , on B(J 0,2 ), that saturates all the vertices in X 0 ∪ U 0 ∪ X 1 ∪ U 1 ∪ X 2 is shown in Figure 4.9. Notice that in Figure 4.9 the matching M 0,2 connects vertices in X 0 ∪ Ū to Ȳ in the following manner:

x 1 0 → y 1 0 , x 2 0 → y 2 0 , x 3 0 → x 3 1 x 3 1 → y 1 1 , x 4 0 → x 4 1 x 4 1 → y 2 1 , u 1 0 → x 1 1 x 1 1 → x 2 1 x 2 1 → y 1 2 , u 1 1 → x 2 2 x 2 2 → y 2 2
. Hence, we can construct a linking of size 6, on S 0,2 , from X 0 ∪ Ū to Ȳ , as depicted in Figure 4.7.

a) =⇒ c)

With Lemma 15 in hand, the following lemma gives a necessary condition for system (1.1) to be structurally ISO over an interval. Proof: Suppose that there does not exist a matching of size (k 1k 0 + 1)N + (k 1k 0 )P + term-rank(D k 1 ) on the dynamic bipartite graph B(J k 0 ,k 1 ). This implies that term-rank(J k 0 ,k 1 ) < (k 1k 0 + 1)N + (k 1k 0 )P + term-rank(D k 1 ). Hence, from item 3) in Lemma 2, the gen-rank(J k 0 ,k 1 ) < (k 1k 0 + 1)N + (k 1k 0 )P + term-rank(D k 1 ). Moreover, for those choices of free parameters in D k 1 such that rank(D k 1 ) = term-rank(D k 1 ), this further implies As an aside, one can directly, i.e., without going through the condition given in item a), show that item b) implies item c). The proof of the same is given in Appendix B.

Lemma 16

S-Structural ISO

The main objective of this section is to characterize ISO for every system matrix as given in (1.1) with

W k ∈ W * k , B k ∈ B * k , C k ∈ C * k and D k ∈ D * k , respectively.
Towards this end, we first define s-structural ISO and thereafter provide a graphical characterization for the same.

Definition 21 Let k 1 , k 0 ∈ Z and k 1 > k 0 , W * k , B * k , C * k , D * k } k 1 k 0 is s-structurally ISO, over [k 0 , k 1 ]
, if for every non-zero choice of free parameters, the corresponding system

W k , B k , C k , D k } k 1 k 0 is ISO.
Definition 21 should be understood as follows: System (1.1) being s-structurally ISO means for every non-zero choice of free parameters in the structured system matrices, the corresponding quadruplet

{W k , B k , C k , D k } satisfies rank(J k 0 ,k 1 ) = (k 1 -k 0 + 1)N + (k 1 -k 0 )P + rank(D k 1 ).

Main Result

It turns out that thanks to Definition 9 and Thm.3.9 in [START_REF] Hershkowitz | Ranks of zero patterns and sign patterns[END_REF] one can obtain a sufficient condition for s-structural ISO. In order to find a necessary condition for s-structural ISO, we restrict our attention to the following submatrix of J k 0 ,k 1 :

P k 0 ,k 1 =   D k 0 ,k 1 -1 0 M ×(k 1 -k 0 )P B k 0 ,k 1 -1 Q k 0 ,k 1  
where P k 0 ,k 1 has (k 1k 0 + 1)M + (k 1k 0 )N rows and (k 1k 0 )P + (k 1k 0 + 1)N columns, and let B(P k 0 ,k 1 ) ⊆ B(J k 0 ,k 1 ) be the dynamic bipartite graph associated with P k 0 ,k 1 . With these in place, our second main result is stated as follows:

Theorem 7

Consider the system (1.1) with the pattern of fixed zeros given by the graphs {G k }. Let B(J k 0 ,k 1 ) and B(P k 0 ,k 1 ) be as defined. System (1.1) is s-structurally ISO, over [k 0 , k 1 ],

(a) if there exists a uniquely restricted matching of size (k

1 -k 0 + 1)N + (k 1 -k 0 )P + term-rank(D k 1 ) on B(J k 0 ,k 1 ).
(b) only if there exists a uniquely restricted matching of size (k 1k 0 )P + (k 1k 0 + 1)N on B(P k 0 ,k 1 ).

Notice that there exists a gap between the sufficient condition and the necessary conditions given in Theorem 7, as the latter pertains to a submatrix, namely P k 0 ,k 1 . However, for the case when D k 1 = 0, from Theorem. 7, we can obtain a full characterization of s-structural ISO, and is given as follows.

Corollary 2

If D k 1 = 0, then system (1.1) is s-structurally ISO, over [k 0 , k 1 ], if and only if there exists a uniquely restricted matching of size (k 1k 0 )P + (k 1k 0 + 1)N on B(J k 0 ,k 1 ).

Corollary 2, in particular, applies to the case where the graph is fixed but the weights along the edges vary with time, a setup akin to the one in [START_REF] Reissig | Strong structural controllability and observability of linear time-varying systems[END_REF]. Moreover, it also accounts for any structure of input and output matrices, unlike Theorem 5 in Chapter 3.

We shall now apply the conditions given in Theorem 7 to our example shown in Figure 4.3.

Example 1 (continued): Notice that matching M 0,2 , see Figure 4.9, on B(J 0,2 ) saturates all the vertices in

X 0 ∪ U 0 ∪ X 1 ∪ U 1 ∪ X 2 .
It can also be seen that over the same choice of vertex sets, there exists another matching, namely M0,2 , as depicted in Figure 4.10. Moreover, there does not exist another choice of vertex sets of size 14 either in the left vertex set, i.e.,

X 0 ∪ U 0 ∪ X 1 ∪ U 1 ∪ X 2 , or in the right vertex set i.e., Y 0 ∪ X 1 ∪ Y 1 ∪ X 2 ∪ Y 2 .
Consequently, there does not exist a uniquely restricted matching of size 14 on B(J 0,2 ). Therefore, from item 2) in Theorem 7, we can conclude that the structured system shown in Figure 4.3 is not s-structurally ISO.

Proof of Theorem 7

We first prove sufficiency of condition given in item (a). Notice that J k 0 ,k 1 has some of the free parameters, namely the diagonal entries of each identity block, fixed to -1, while the remaining free parameters are algebraically independent. Suppose that there exists a uniquely restricted matching of size (k 1k 0 + 1)N + (k 1k 0 )P + term-rank(D k 1 ) on the dynamic bipartite graph B(J k 0 ,k 1 ), then from Lemma 8 the matrix J k 0 ,k 1 has rank equal to (k 1k 0 + 1)N + (k 1k 0 )P + term-rank(D k 1 ) for all non-zero choice of free parameters in the structured system matrices. Therefore, from Definition 21, System (1.1) is s-structurally ISO over [k 0 , k 1 ]. The proof of necessity of condition given in item (b) is more involved, and is developed in the reminder of this subsection. Let L k 0 ,k 1 be a submatrix obtained by looking at all the rows and some of the columns, say r; where 1 ≤ r ≤ (k 1k 0 )P + (k 1k 0 + 1)N , of P k 0 ,k 1 . Let B(L k 0 ,k 1 ) be the corresponding bipartite graph associated with L k 0 ,k 1 . The following lemma is crucial.

Lemma 17

Let r be any integer 1 ≤ r ≤ (k 1k 0 )P + (k 1k 0 + 1)N . For any submatrix L k 0 ,k 1 formed with r columns of P k 0 ,k 1 , if there does not exist a uniquely restricted matching of size r on B(L k 0 ,k 1 ), then there exists a choice of free parameters such that the corresponding matrix has rank less than r.

The Lemma's statement specialized to r = (k 1k 0 )P + (k 1k 0 + 1)N concerns L k 0 ,k 1 = P k 0 ,k 1 and gives the desired result: if there exists no uniquely restricted matching of size (k 1k 0 )P + (k 1k 0 + 1)N in the dynamic bipartite graph B(P k 0 ,k 1 ), then there exists a The conditions given in Theorem 7 are also applicable for s-structural ISO of LTV 4.6. On the applicability of conditions in Theorem 6 (resp. Theorem 7) for LTI network systems 81 network system with fixed graphs. Since LTI systems are subclasses of LTV systems, it follows that the sufficient condition in Theorem 7 also applies for s-structural ISO of LTI network systems. However, the necessary conditions in Theorem 7 need not necessarily apply for s-structural ISO of LTI network systems. Equivalence between s-structural ISO for LTV network systems with fixed graphs and s-structural ISO for corresponding LTI network systems remains open, unlike s-structural observability (see [START_REF] Reissig | Strong structural controllability and observability of linear time-varying systems[END_REF]).

Problem Formulation

Consider a linear time-invariant system that is subject to unknown inputs, and whose dynamics are given as follows:

x k+1 = Ax k + Bu k + w k y k = Cx k + Du k + v k (5.1)
with state vector x k ∈ R n , unknown input u k ∈ R p and output y k ∈ R m ; the matrices A, B, C, and D being of appropriate dimensions. Process noise w k and measurement noise v k are assumed to be white, zero mean, mutually uncorrelated with covariance matrices Q and R, respectively. Note that the setup here differs from that given in Eq. (1.1) in that we are no longer dealing with noiseless settings. This is so because here we do not seek to address the question whether the system has the property of ISO or not, but are interested in determining how to estimate state and unknown inputs (up to delay-).

In what follows, we introduce various notions related to the joint input and state estimation problem.

Definition 22 (Definition 2.5 [START_REF] Sundaram | Fault-tolerant and secure control systems[END_REF]) Let be a non-negative integer. The system A, B, C, D} is delay-left invertible if the unknown input u 0 is uniquely determined by the initial state x 0 and the output sequence {y 0 , y 1 , . . . , y } (in the absence of noise). The smallest for which this condition is satisfied is called the inherent delay of the system.

We define Γ ∈ R ( +1)m×( +1)p (known as delay-left-invertibility matrix) and N ∈ R ( (m+n)+m)×( (p+n)+p) as:

Γ =       D 0 . . . 0
    = E 0 F N -1 , where E = D 0 B -I n , F = 0 -C 0 -A , F = -F 0 .
By a suitable re-writing of (5.1), over consecutive time-steps, the following system of

Problem Formulation 85

equations is readily obtained:

N               u k- x k-+1 u k-+1 x k-+2 . . . u k-1 x k u k               =               y k--Cx k- -Ax k- y k-+1 0 . . . y k-1 0 y k               -               v k- w k- v k-+1 w k-+1 . . . v k-1 w k-1 v k               (5.2)
The following algebraic characterizations for delay-left invertibility can be provided in terms of Γ and N .

Proposition 16

The following statements are equivalent:

1) The system A, B, C, D} is delay-left invertible;

2) rank(Γ ) = p + rank(Γ -1 );

3) rank(N ) = p + n + rank(N -1 ).

Proof: Equivalence of items 1) and 2) is stated in [START_REF] Massey | Inverses of linear sequential circuits[END_REF] (Theorem 4). The proof of equivalence of items 1) and 3) is based on the same idea, as detailed below (see [START_REF] Garin | Structural Delay-1 Input-and-State Observability[END_REF] for the case = 1). Notice that u 0 is uniquely determined by x 0 , y 0 , y 1 , . . . , y if and only if both u 0 and x 1 are uniquely determined by x 0 , y 0 , y 1 , . . . , y , since x 1 is completely determined by u 0 and x 0 . From (5.2), setting noise to zero, the following is immediate:

E 0 F N -1               u 0 x 1 u 1 x 2 . . . u -1 x u               =               y 0 -Cx 0 -Ax 0 y 1 0 . . . y -1 0 y               . ( 5.3)
The solution for the first part u 0 , x 1 of the unknown vector is unique if and only if rank(N ) = p + n + rank(N -1 ).

Note that since delay-1 left invertbility is a particular case of delay-left invertbility, it follows that Prop. [START_REF] Corfmat | Structurally controllable and structurally canonical systems[END_REF] ensure the existence of an observer with delay 1 . In the next section, we will take noise into consideration. Assuming the system is delay-left-invertible, we will construct an unbiased linear estimator for the input and the state. Further assuming that the system is strongly detectable and satisfies a suitable reachability condition, we will use results from the analysis of descriptor systems to ensure the convergence to stationary stable error dynamics, involving the unique solution of a discrete-time algebraic Riccati equation.

Main result

Construction of a recursive filter with delay

We consider a filter structure where, at time k, we estimate u k-and x k-+1 as linear functions of the measurements y k-+1 , . . . , y k and of the previous state estimate xk-, assumed to be unbiased. Precisely, we look for an estimate of the following form:

ûk- xk-+1 = M k ỹk-, , (5.4)
where the innovation ỹk-, is defined as

ỹk-, = ȳk-, -F +1 0 I n xk- (5.5)
with ȳT k-, = y T k-, 0, y T k-+1 , 0, . . . , y T k-1 , 0, y T k .

The matrix M k will be constructed so that the estimates are unbiased with minimum error covariance, and then we will propose an approximation leading to sub-optimal covariance but simpler implementation.

For this purpose, we set the linear model linking the variables to be estimated with the available information. Introducing the notation ˜

k-, = F +1 0 I n (x k--xk-) + ¯ k-, , with
¯ T k-, = v T k-, w T k-, v T k-+1 , w T k-+1 , . . . , v T k-1 , w T k-1 , v T k , (5.2) can be re-written as E F u k- x k-+1 + 0 N -1     u k-+1 x k-+2 . . . u k-1 x k u k     = ỹk-, -˜ k-, .
(5.6)

1 A delayed observer is an observer capable to reconstruct the state despite the presence of the unknown input. In our chapter, an observer with delay reconstructs x k-+1 from outputs up to y k ; [START_REF] Sundaram | Delayed observers for linear systems with unknown inputs[END_REF] uses a different convention and denotes the same delay as -1.

Assuming that xk-is unbiased, then ˜ k-, has zero mean and covariance Σ k-= E(˜ k-, ˜ T k-, ).

Lemma 18

Assuming that xk-is unbiased, the linear estimator (5.4) is unbiased if and only if

M k E F = I and M k 0 N -1 = 0 . (5.7)
Proof: Pre-multiplying (5.6) by M k , taking expectation, and recalling that E˜ k-= 0, we obtain

M k E F u k- Ex k-+1 + M k 0 N -1     u k-+1 Ex k-+2 . . . u k-1 Ex k u k     = E(M k ỹk-, ).
Recall that M k ỹk-, = ûk- xk-+1 , and that we want this estimate to be unbiased for all input and state sequence (we do not allow M k to be state-dependent). This is true if and only if the two conditions in (5.7) are fulfilled.

When the system is delay-left invertible, it is always possible to find a matrix M k fulfilling the two conditions (5.7)2 . Such a matrix can be written as a product M k = G k H, with H 0 N -1 = 0, H having full row-rank, and a number of rows equal to n + m + dim ker N T -1 , i.e., rows of H form a basis of ker 0, N T -1 . Pre-multiplying (5.6) by H, we obtain

H E F u k- x k-+1 = H ỹk-, -H˜ k-, . (5.8)
The covariance of H˜ k-, is HΣ k-H T , which is a positive definite matrix since H has full row rank. From (5.8), by Gauss-Markov theorem, the BLUE estimate is given by

ûk- xk-+1 = P k-+1 E T , F T H T HΣ k-H T -1 H ỹk-, , (5.9)
where

P k-+1 = E T ,F T H T HΣ k-H T -1 H E F -1
(5.10) is its error covariance matrix.

Remark : The BLUE estimate (5.9)-(5.10) has an expression which involves the matrix H. However, having fixed one matrix H such that H 0 N -1 = 0, having full row-rank, and a number of rows equal to n + m + dim ker N T -1 , any other matrix H satisfying the same properties can be obtained as H = JH, for some J square and invertible matrix (a change of basis of the row space). Then, looking at (5.9)-(5.10), it is easy to see that replacing H Chapter 5. Unbiased Filtering for State and Unknown Input with Arbitrary Delay with JH gives exactly the same estimate, since J cancels out. The estimate being the same irrespective of the choice of H, we can use any construction of H; we will use the following one. We construct a matrix U 2 whose columns form an orthonormal basis of ker(N T -1 ), as follows. We consider the (full size) singular value decomposition (svd) N -1 = U SV T , and the partition U = [U 1 , U 2 ], where U 1 has r columns and

U 2 has d = ( -1)(m + n) + m -r columns, r = rank N -1 . Using U 2 , we define H = I n+m 0 0 U T 2 .
The difficulty in implementing a filter based on the BLUE estimate (5.9)-(5.10) lies in the error covariance matrix Σ k-. Below, we propose a simpler albeit suboptimal filter, where we approximate Σ k-by the block-diagonal matrix diag( Σk-, Σ ), where

Σ = diag(R, Q, • • • , R, Q, R) and Σk-= R + CP xx k-C T CP xx k-A T AP xx k-C T Q + AP xx k-A T
. This amounts at disregarding cross-correlations between xk-and y k-, . . . , y k-1 . With this approximation, together with the above construction of H, we can exploit the block-diagonal structure of these matrices, to obtain a simpler version of (5.9)-(5.10), reminiscent of a Kalman filter. Notice that

H Σk-0 0 Σ H T -1 = Σ-1 k- 0 0 (U T 2 Σ U 2 ) -1 . We define Ψ = F T U 2 (U T 2 Σ U 2 ) -1 U T 2
and Ω = Ψ F . With these definitions, and with the above-mentioned approximation for Σ k-, from (5.10) we get

P k-+1 = E T Σ-1 k-E + Ω -1
(5.11) and (5.9) becomes ûkxk-+1

= P k-+1 E T Σ-1 k-, Ψ ỹk-, .
Recalling the definition of ỹk-, (see (5.5)), one can see that

ỹT k-, = (y k--CAx k-) T , -Ax T k-, ȳT k-+1, -1 .
Hence, partitioning columns of E T Σ-1 k-in two blocks of size m and n denoted as

E T Σ-1 k-= [K (1)
k-, -K

k-], we obtain

ûk- xk-+1 = P k-+1 K (1) k-(y k--C xk-) + K (2) k-Ax k-+ Ψ ȳk-+1, -1 . (5.12)
The proposed recursive filter is summarized in the following algorithm.

Algorithm: Delay-unbiased recursive estimator for state and unknown input.

Pre-processing: Given system matrices A, B, C, D and noise covariance matrices R, Q, build:

• E = D 0 B -I n , F = 0 -C 0 -A , F = -F 0 ( -2)(m+n)+m, p+n ,
Filter iterations: for k ≥ , use xk-, P xx k-, and measurement y k-, . . . , y k to compute ûk-, xk-+1 and P xx k-+1 , as follows.

Extended measurements vector:

ȳk-+1, -1 = y T k-+1 , 0, y T k-+2 , 0, . . . , y T k-1 , 0, y T k T .
Approximate covariances and gains:

• Σk-= R + CP xx k-C T CP xx k-A T AP xx k-C T Q + AP xx k-A T , • compute Σ-1 k-, • P k-+1 = E T Σ-1 k-E + Ω -1 , • K (1)
k-= E T Σ-1 k- Im 0 , K (2)
k-= -E T Σ-1 k- 0
In .

Estimates:

ûk- xk-+1 = P k-+1 K (1) k-(y k--C xk-) + K (2) k-Ax k-+ Ψ ȳk-+1, -1 .
Approximate state error covariance:

P xx k-+1 = [0, I n ] P k-+1 0
In .

Performance analysis

In order to analyze the performance of the proposed filter, we first show its equivalence with a recursive estimator designed within the linear descriptor systems framework. We introduce the notation z

T k = u T k--1 , x T k-, ȳT k = y T k-, 0 , T k = -v T k-, w T k-
, and χ k, = U T 2 ȳk-, -1 and we refer to Sect. 5.3.1 for other notations. Delay Proposition 17

The system (5.1) can be written in the following descriptor form

Ez k+1 = F z k + ȳk + k χ k, = U T 2 F z k + U T 2 ¯ k-, -1 .
(5.13)

Proof: Similarly to (5.6), from (5.2) we obtain

E F u k- x k-+1 + 0 N -1   u k-+1 x k-+2 ... ... x k u k   = ȳk ȳk-+1, -1 - -F 0 ( -1)(m+n).(p+n) u k--1 x k- - -k ¯ k-+1, -1 .
This can be rewritten as

Ez k+1 = F z k + ȳk + k (5.14) F z k+1 + N -1   u k-+1 x k-+2 ... ... x k u k   = ȳk-+1, -1 -¯ k-+1, -1 . ( 5
F z k = U T 2 ȳk-, -1 -U T 2 ¯ k-, -1
, which gives the measurement equation.

Notice that (5.13) is a linear descriptor system, with state z k , measurements χ k, and known input ȳk . Its process noise k has covariance Σ = diag(R, Q), while the measurement noise U

T 2 ¯ k-, -1 has covariance U T 2 Σ U 2 .
By applying [START_REF] Darouach | State estimation of stochastic singular linear systems[END_REF]Thm. 3] and [START_REF] Darouach | State estimation of stochastic singular linear systems: convergence and stability[END_REF]Thm. 4] to the descriptor system (5.13), we obtain the following filter and its stability and convergence properties. We introduce the required notation and then give the result in Prop. 18 below.

Assuming rank

E U T 2 F
= n + p, let E 1 be a non-singular upper triangular matrix, of size n + p, obtained as

E 1 0 = T E U T 2 F
, with T an orthogonal matrix; this decomposition can be obtained using QR factorization. Then, use T to obtain

F 1 F 2 = T F 0 and W 1 S 1 S T 1 W 2 = T diag(Σ, U T 2 Σ U 2 )T T . Let Q 1/2 s
denote any square root of

Q s = E -1 1 W 1 -S 1 W -1 2 S T 1 E -T 1 and let F s = E -1 1 F 1 -S 1 W -1 2 F 2 .
We also introduce the following discrete-time algebraic Riccati equation (DARE)

P = F s P F T s -F s P F T 2 F 2 P F T 2 + W 2 -1 F 2 P F T s + Q s . ( 5
i) rank E U T 2 F = n + p; ii) rank zE -F U T 2 F = n + p, ∀z ∈ C s.t. |z| ≥ 1,
then there exists a recursive estimator ẑk-+1 given by

P -1 k+1 = E T (Σ + F Pk F T ) -1 E + F T U 2 (U T 2 Σ U 2 ) -1 U T 2 F , (5.17
) ẑk+1 = Pk+1 E T (Σ + F Pk F T ) -1 (F ẑk + ȳk ) + Pk+1 F T U 2 (U T 2 Σ U 2 ) -1 χ k+1, . (5.18)
Furthermore, if iii) the pair (F s , Q We will now show that the estimator obtained in Sect. 5.3.1 is equivalent to the filter in Prop. 18, and hence inherits its convergence and stability. Prop. 19 means that the algorithm described in Sect. 5.3.1 and the filter for the descriptor system (5.13) (running for k ≥ ) give exactly the same estimates, provided they are consistently initialized. Hence, they also share the same convergence properties. The two lemmas below show the relation between properties of the system (5.1) (delay-left-invertibility and strong detectability) and the conditions in Prop. 18 concerning the descriptor system (5.13).

Lemma 19

If the system is delay-left invertible, then rank E U T 2 F

= n + p.

Proof: To prove that rank

E U T 2 F
= n+p, we will prove that

E U T 2 F
w = 0 implies w = 0. The delay-left invertibility condition rank(N ) = p + n + rank(N -1 ) can be equivalently rephrased as:

rank E F = p + n and Im E F ∩ Im 0 N -1 = {0}. Notice that E U T 2 F = H E F , with H = I n+m 0 0 U T 2 . By definition of U 2 , Im(U 2 ) = ker(N T -1 ), which implies that Im(H) = ker 0, N T -1 and hence ker(H) = Im 0 N -1 . If E U T 2 F w = 0, then Hv = 0, with v = E F w. This implies v ∈ Im E F
∩ ker H, and hence v = 0. Then also w = 0, since rank

E F = n + p. Lemma 20 If rank A -zI B C D = n + p, ∀z ∈ C s.t. |z| ≥ 1, then rank zE -F U T 2 F = n + p, ∀z ∈ C s.t.
|z| ≥ 1.

Proof: Notice that [zE -F ] = zD C zB A-zI , so that rank [zE -F ] = rank A-zI zB C zD . For every z = 0, the latter is equal to rank

Numerical Example

To illustrate the performance of the proposed algorithm, simulation results are given in this section. The considered system is defined by the following matrices:

A = 1 -1/2 -1/2 -1/2 0 1/2 1 -2 0 0 0 1 0 0 -1/2 -1/2 B = 1 0 0 0 0 -1 0 0 , C = 1 -1 0 -3 0 1 0 2 0 1 -1 4 , D = 0 0 0 0 1 0 .
Since D = 0, this example cannot be treated with methods from [START_REF] Roshan A Chavan | Recursive input reconstruction with a delay[END_REF]. This system has inherent delay 2 and is strongly observable (see [START_REF] Sundaram | Delayed observers for linear systems with unknown inputs[END_REF]). Moreover, after obtaining Q s and F s , one can see that the reachability condition on the unit circle is also satisfied.

The system is affected by a square wave and a sawtooth wave, assumed to be unknown, while the initial state, x 0 = [8; 4; 6; 7], is also unknown. In addition, the process noise and the measurement noise are independent identically distributed zero-mean Gaussian processes with covariance R = Q = σ 2 I, with σ = 0.35; they are mutually uncorrelated.

The purpose of the proposed algorithm is then to estimate both the four states of the system and the two inputs with a delay = 2. It is initialized with x0 = 0 and P 0 = 10 3 I. Performance with respect to input estimation is depicted in Figure 5.2, while performance with respect to the four states is shown in Figure 5.3. These figures show that both inputs and states are very well reconstructed.

The convergence of the algorithm is illustrated in Figure 5.4, which depicts the time evolution of the trace of the sample error covariance matrix and the trace of P k (i.e., the approximate covariance matrix computed by the algorithm). After is equal to 3.846, the same as trace(P ), P being the unique strong solution of the DARE (5.16); this is consistent with the result in Thm. 8. The sample covariance is computed over 1000 runs, with same initial condition and the same noise distributions as described above. The initial sample covariance trace is small, due to all runs having a same initial condition, and then the evolution shows an almost stationary behavior, around a value near the one computed by the algorithm.

Conclusion and Perspectives

Conclusion

This thesis deals with linear discrete-time network systems that are affected by multiple unknown inputs. The objective is to reconstruct both the state vector and the sequence of unknown inputs up to delay 1, i.e., input and state observability (ISO). More precisely, given a sequence of outputs {y 0 , y 1 , . . . , y N }, we would like to reconstruct the initial state x 0 and the sequence of unknown inputs {u 0 , u 1 , . . . , u N -1 }.

We first provide algebraic characterizations, viz Kalman-like rank condition, PBH-like tests, etc., for ISO. However, such characterizations suffer from two drawbacks: a) one needs to know the exact value of the coefficients of system matrices so as to exploit them; and b) these are difficult to check as the size of the network grows. Hence, one seeks alternative characterizations.

One could use graphs to represent and study network systems, using the notion of structured systems. In such systems, the matrices of the state-space realization have fixed zero patterns. The positions that are not fixed to zero as referred to as free parameters. Each numerical realization of the free parameters yields a new system, and one may think of such a collection of systems as a family of systems wherein each member in this family has the same pattern of fixed zeros. Under such a setting, on the one hand, one seeks structural results i.e., results that are true for almost all choices, where "almost all" means for all choices of free parameters except for those (possibly) lying on an algebraic variety of the space of free parameters [START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF].

On the other hand, there exists yet another line of work where one wants to ensure that results are true for all non-zero choice of free parameters, referred to as s-structural results. In this thesis, we provide graphical characterizations for structural (resp. s-structural) ISO.

We presented our main contributions in increasing order of generality, with respect to the setup. More precisely:

1. In Chapter 2 we focused on linear time-invariant (LTI) network systems. We provided, in terms of existence of uniquely restricted matchings on suitably defined bipartite graphs, (i) a sufficient condition for s-structural ISO;

(ii) a necessary condition for s-structural ISO;

(iii) under suitable assumptions on the feedthrough matrix, a characterization for sstructural ISO.

Conclusion

time. We assumed that the input and output matrices had a particular structure. Under such assumptions, we provided (i) equivalence between ISO of a system and observability of a suitably defined subsystem;

(ii) a graphical characterization for structural ISO that relies on existence of matching on a suitably defined bipartite graph and b) output-connectedness of an appropriate graph;

(iii) graphical characterization for s-structural ISO in terms of existence of uniquely restricted matchings on suitably defined bipartite graphs.

3. In Chapter 4, we generalized even further by accounting for time-varying graphs and making no assumptions on the structure of system matrices. We provided (i) graphical characterizations for structural ISO in terms of two things: a) existence of matching on a bipartite graph; b) existence of a linking on a dynamic graph;

(ii) for s-structural ISO, in terms of existence of uniquely restricted matchings on suitably defined bipartite graphs • a sufficient condition; • a necessary condition;

• under suitable assumptions on the feedthrough matrix, a necessary and sufficient condition.

4. In Chapter 5, we presented a recursive algorithm that simultaneously estimates state and inputs in an unbiased sense.

Perspectives

The present thesis has addressed some of the open questions pertaining to ISO of structured systems. However, there are quite a few research topics, within the same focus area, that could be of interest to the community. Here we list some of them.

Equivalence between structural (resp. s-structural) ISO of LTI and LTV systems

It was shown in [START_REF] Poljak | On the gap between the structural controllability of time-varying and time-invariant systems[END_REF] (resp. [START_REF] Reissig | Strong structural controllability and observability of linear time-varying systems[END_REF]) that, under the assumption of fixed topologies but time-varying edge weights, over sufficiently long intervals, structural (resp. s-structural) controllability (and also observability) of LTV systems is equivalent to structural controllability of the corresponding family of LTI systems. This result, under suitable assumptions on the structure of input and output matrices, was generalized for the problem of structural (resp. s-structural) ISO in [START_REF] Gracy | Structural and Strongly Structural Input and State Observability of Linear Network Systems[END_REF] (see Theorem 1 (resp. Theorem 2)). However, for the more general case of time-varying topology, the equivalence between structural (resp. s-structural) ISO of LTI and LTV systems remains open.

Minimal structural ISO problem

Given a state matrix with a particular choice of numerical entries in it, the minimal controllability problem (MCP) seeks to find the input matrix with the lowest number of non-zero terms such that the resulting systems is controllable. It has been shown in [START_REF] Olshevsky | Minimal controllability problems[END_REF] that MCP is NP-hard. However, for LTI network systems, the structural variant of the MCP has polynomial-time complexity [START_REF] Commault | The single-input minimal controllability problem for structured systems[END_REF]. The authors in [START_REF] Commault | The single-input minimal controllability problem for structured systems[END_REF] addressed the following question: given a single output, what is the minimum number of states that should be connected to this output so that the resulting network system is structurally observable. Taking this idea further, [START_REF] Pequito | A framework for structural input/output and control configuration selection in large-scale systems[END_REF] sought to answer, among other things, two questions: a) given that an output is connected to exactly one state (dedicated output), what is the minimum number of outputs needed to ensure structural observability, and b) supposing that an output may be connected to multiple states, how many outputs are needed for structural observability. The problem of finding the minimum number of dedicated outputs such that the resulting LTI network system is structurally ISO has been recently studied in [START_REF] Weerakkody | Robust Structural Analysis and Design of Distributed Control Systems to Prevent Zero Dynamics Attacks[END_REF]; while the case of finding the minimum number of non-dedicated outputs for structural ISO in LTI setting remains open.

The setting in both [START_REF] Pequito | A framework for structural input/output and control configuration selection in large-scale systems[END_REF] and [START_REF] Weerakkody | Robust Structural Analysis and Design of Distributed Control Systems to Prevent Zero Dynamics Attacks[END_REF] assumes that the cost of observing each state is the same, i.e., uniform costs. However, in practice, one often encounters settings where the costs could differ depending on the choice of the state variable being measured. The question then becomes what is the minimal cost incurred so as to achieve structural observability (resp. structural ISO). Insofar structural observability in LTI set up, a solution has been provided in [START_REF] Pequito | Minimum cost input/output design for large-scale linear structural systems[END_REF] [4], while for structural ISO it is an ongoing investigation as mentioned by the authors in [START_REF] Weerakkody | Robust Structural Analysis and Design of Distributed Control Systems to Prevent Zero Dynamics Attacks[END_REF]. However, there is room for more work in this area. A couple of directions are the following: Q1: For an LTV network system represented by a fixed graph, it would be interesting to solve the minimum cost optimal sensor placement that ensures structural ISO.

Q2: Further generalizing the aforesaid, one could seek to do the same for LTV network system represented by a time-varying graphs.

With regard to Q1, thanks to the results in Chapter 3, one can breakdown the structural ISO problem for LTV systems into an equivalent problem in structural observability of a suitably defined LTI subsystem. Thereafter, by applying the results in [START_REF] Pequito | A framework for structural input/output and control configuration selection in large-scale systems[END_REF], one obtains the answer to Q1.

Given that the graphical characterizations given in Chapter 4 are dependent on the choice of intervals [k 0 , k 1 ], problem Q2 could have a (possibly) different solution for every time interval. Hence, Q2 seems less appealing.

Fixed ISO subspace

Let H, G, K and S be as given in Chapter 2. We recall the following result.

characterizations for structural (resp. s-structural) ISO, given in Chapters 2, 3, 4 are also reliant on this requirement. A more general setting is the one in which the same parameter appears at multiple positions within the system matrices; clearly, the parameters are no longer algebraically independent. Such scenarios have been considered in [START_REF] Corfmat | Structurally controllable and structurally canonical systems[END_REF], [START_REF] Jl Willems | Structural controllability and observability[END_REF] and [2], and a characterization for structural controllability, of such linearly parametrized matrix pairs 3 , has been provided. However, the result in [START_REF] Corfmat | Structurally controllable and structurally canonical systems[END_REF] is purely matrix-algebraic, while those in [START_REF] Jl Willems | Structural controllability and observability[END_REF] and [2] are also algebraic. On the other hand, under the same setting, characterizations for structural controllability in graphtheoretical terms has recently been provided in [START_REF] Liu | Structural Controllability of Linear Time-invariant Systems[END_REF]; a sufficient condition for s-structural controllability (albeit in terms of zero forcing sets) has been provided in [START_REF] Jia | A Sufficient Condition for Colored Strong Structural Controllability of Networks[END_REF] Under LTV setting with fixed graphs and dependent parameters, a graphical characterization for structural ISO can be obtained by combining the results in Chapter 3 (see Props. 12 and 13) and that in [START_REF] Liu | Structural Controllability of Linear Time-invariant Systems[END_REF]. However, the following problems remain open.

(i) under LTI setting with dependent free parameters and arbitrary input, output and feedthrough matrices, a graphical characterization for structural ISO;

(ii) for LTV setting with at least one dependent parameter, accounting for arbitrary input, output and feedthrough matrices and time-varying topology, purely algebraic characterizations and graph-theoretical characterizations for structural ISO (resp. observability).

Structural Properties over Finite Fields

Structural controllability as studied in [START_REF] Lin | Structural controllability[END_REF] [47] et al operates under the assumption that the free parameters are free to take any value over the field of real (or complex) numbers. However, there exist setups where a free parameter is allowed to take only a finite set of values, i.e., over a finite field. Characterizations of structural controllability (and observability) over finite fields have been studied in [START_REF] Sundaram | Structural controllability and observability of linear systems over finite fields with applications to multi-agent systems[END_REF]. However, to the best of our knowledge, similar characterizations for structural ISO are not yet available.

The main difficulty seems to be the following: graphical characterization for structural ISO is reliant on an algebraic characterization, namely PBH-like test (see Prop. 1 in [START_REF] Garin | Structural Delay-1 Input-and-State Observability[END_REF]). Since finite fields are not algebraically closed, i.e., not every polynomial with coefficients from a finite field will have a root in that field, PBH-like tests are not sufficient for handling linear systems over finite fields [START_REF] Sundaram | Structural controllability and observability of linear systems over finite fields with applications to multi-agent systems[END_REF].

3 Recalling the understanding provided in [START_REF] Liu | Structural Controllability of Linear Time-invariant Systems[END_REF][START_REF] Corfmat | Structurally controllable and structurally canonical systems[END_REF], a linearly parametrized matrix pair is of the following form:

AN×N (p) = k∈q g k p k h k 1 , BN×M (p) = k∈q g k p k h k 2
where p ∈ R q is a vector of q algebraically independent free parameters, p1, . . . , pq, q = {1, 2, . . . , q}. For every k ∈ q, g k ∈ R N ×1 , h k 1 ∈ R 1×N and h k 2 ∈ R 1×M 104 Conclusion

Higher-order local dynamics

Throughout this thesis, we have assumed that each node has first-order dynamics. If each node were to have higher-oder dynamics, then there are two cases to consider. Suppose that the local dynamics do not impose any constraints on the free parameters. Let q 1 (q 1 ∈ Z + ) denote the order of dynamics of each node. Let B(J k 0 ,k 1 ) be as given in Chapter 4 . Under such a setting, structural ISO over an interval [k 0 , k 1 ] is equivalent to existence of a matching of size ((k 1 -k 0 +1)N +(k 1 -k 0 )P +term-rank(D k 1 ))q 1 on a bipartite graph defined analogous to B(J k 0 ,k 1 ). Results for s-structural ISO can also be obtained along similar lines. Suppose that the local dynamics impose some constraints on the free parameters. So as to better understand the technical challenges involved in the latter, let us look at the following example: Consider a graph G = (V, E) having adjacency matrix G, where the set of nodes V = {1, 2, . . . , N } and the set of edges E ⊆ V × V such that (i, j) ∈ E if G ij = 0. Let x i (resp. v i ) denote the position (resp. velocity) of node i. The (second order) dynamics of each node is given by:

ẋi (t) = v i vi (t) = α N j=1,j =i G ij (x j (t) -x i (t)) + β N j=1,j =i G ij (v j (t) -v i (t))
where α and β, both strictly positive, are the coupling strengths. Hence, we have some free parameters that are obliged to take some fixed values. This differs from the standard literature on structured systems theory [START_REF] Lin | Structural controllability[END_REF][START_REF] Robert | Structural controllability of multi-input linear systems[END_REF][START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF]. Characterizations for structural properties (viz. controllability, observability, ISO), under such a setting, needs to factor in aforementioned constraints as well. Some preliminary results in this direction may be found in [START_REF] Partovi | Structural controllability of high order dynamic multi-agent systems[END_REF], [START_REF] Guan | Structural controllability of higher-order multi-agent systems under absolute and relative protocols[END_REF] which address the problem of structural controllability with LTI graphs. However, with respect to the more general problem of ISO, it remains open.

Design of observers for ISO with sparse unknown input

Cyber-Physical Systems, as already seen, is made up of several components spanning both the cyber-space and the physical space. The problem of designing estimators that simultaneously estimate both the state and the unknown input has been studied, among others, in [START_REF] Gillijns | Unbiased minimum-variance input and state estimation for linear discrete-time systems[END_REF][START_REF] Gillijns | Unbiased minimum-variance input and state estimation for linear discrete-time systems with direct feedthrough[END_REF]. An attacker, due to resource limitations, might choose to attack only a fraction of the assailable nodes. The unknown input, in such scenarios, would be sparse. Clearly, if the corresponding ISO matrix satisfies the full rank condition, then the linear system with sparse unknown inputs is ISO with delay-1. However, the converse is not true. That is, thanks to the assumption of sparsity on the unknown input, one can recover the state and the unknown input up to delay-1 from an appropriate sequence of outputs even if the ISO matrix has more columns than rows, i.e., there are more inputs than outputs. The assumption of sparsity on the unknown input combined with the notion of mutual coherence from compressive sensing literature enables the design of such observers [START_REF] Swart | Input and State Estimation for Linear Ystems with Sparse Unknown Input[END_REF]. An interesting line of future research, under such a setting, could be to design observers by exploiting other notions like restricted isometric property or spark, and compare the performance and computation time of such a filter against that of the filter given in [START_REF] Swart | Input and State Estimation for Linear Ystems with Sparse Unknown Input[END_REF].

Distributed Algorithms for Resilient Input and State Estimation

Resilience refers to the ability of a system to perform its task even in response to disturbances, including threats of an unexpected and malicious nature [START_REF] Craig G Rieger | Resilient control systems: Next generation design research[END_REF]. Much of the existing manuscripts are devoted to resilience of centralized systems (see, for instance, [START_REF] Liu | False data injection attacks against state estimation in electric power grids[END_REF][START_REF] Alvaro | Attacks against process control systems: risk assessment, detection, and response[END_REF][START_REF] Pasqualetti | Attack detection and identification in cyber-physical systems[END_REF][START_REF] Alvaro A Cardenas | Research Challenges for the Security of Control Systems[END_REF]).

Given the ubiquitousness of network systems and the ever-growing popularity of distributed algorithms, one could very well seek conditions under which resilience of a distributed system can be ensured. More precisely, a fully distributed setting is one in which the agents transmit their measurements to each other through a communication graph, and the objective is to to estimate the concerned parameter [START_REF] Chen | Distributed Estimation Under Sensor Attacks[END_REF]. One approach for understanding resilience of distributed computations is local filtering algorithms (algorithms in which the nodes, at each time instant, discard the most extreme values in their neighborhood). Another approach is the one wherein the objective of each node is to estimate the entire system state on the basis of limited state measurements and the information obtained from neighbors (via a consensus graph); more popularly known as distributed state estimation problem. In this context, a distributed algorithm that guarantees asymptotic reconstruction of the entire state at each node was recently given in [START_REF] Mitra | Distributed observers for LTI systems[END_REF]. However, from a security point of view, it is entirely possible that some of the nodes in a network could be corrupted as a consequence of malicious attack, and the objective then is to solve the distributed state estimation problem subject to the aforementioned constraint; more popularly referred to as resilient distributed state estimation [START_REF] Mitra | Resilient Distributed State Estimation for LTI Systems[END_REF]. Similar algorithms addressing distributed state and unknown input estimation problem are perhaps missing.

On the other hand, in the context of LTI systems but with the communication graph of the sensors monitoring the network (possibly) having time-varying topology, an algorithm addressing for distributed state estimation has been given in [START_REF] Mitra | Secure Distributed State Estimation of an LTI System over Time-Varying Networks and Analog Erasure Channels[END_REF]. The extension, under same constraints, either encompassing (or only for standalone) unknown input estimation remains a potential line for future investigation.

viii List of Figures 3 . 3 61 3. 7 62 3. 9 67 4. 2 G 67 4. 3 67 4. 4 68 4. 5 69 4. 6 4 . 8 4 . 18 M 1 0, 2 .

 336176296726736746856964841812 Bipartite graph S associated with G . . . . . . . . . . . . . . . . . . . . . . . . 57 3.4 A Matching M in S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.5 Bipartite graph S × , in solid red: S × ∩S, in dashed blue: E new = {(u a , w a ), (u b , w b ), (u c , w c )} while E loop = {(u d , w d )} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.6 A matching M × in S × . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The system G 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623.8 Subsystem G1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bipartite graph S 1 associated with G1 . . . . . . . . . . . . . . . . . . . . . . . 62 3.10 Matching M 1 on S 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.11 Matching M 2 on S 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.12 Matching M 3 on S 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.13 Matching M 4 on S 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.14 Matching M 5 on S 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.15 Matching M 6 on S 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.16 Matching M 7 on S 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.17 Matching M 8 on S 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.18 All maximum matchings on S 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.1 G 2k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2k+1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Evolution of an LTV system represented by time-varying periodic graphs with periodicity 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dynamic graph S k 0 ,k 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dynamic bipartite graph B(J k 0 ,k 1 ) . . . . . . . . . . . . . . . . . . . . . . . . . Dynamic graph S 0,2 associated with the example inFigure 4.3 . . . . . . . . . . 71 4.7 In dashed blue, a linking L 0,2 from X 0 ∪ Ū to Ȳ on the dynamic graph associated with the example in Figure 4.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 List of Figures ix Dynamic bipartite graph B(J 0,2 ). The edges in black are one-to-one correspondence with the edges in the dynamic graph in Figure 4.6, while the edges in dashed blue correspond to -I 4×4 in J 0,2 . . . . . . . . . . . . . . . . . . . . . . 4.9 M 0,2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.10 M0,2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.11 Matchings on the dynamic bipartite graph B(J 0,2 ) . . . . . . . . . . . . . . . . 4.12 G 2k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.13 G 2k+1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.14 Evolution of another LTV system represented by time-varying periodic graphs with periodicity 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.15 Dynamic graph S 1 0,2 associated with the example in Figure 4.14 . . . . . . . . . 4.16 In dashed blue, a linking L 1 0,2 from X 0 ∪ Ū to Ȳ on the dynamic graph associated with the example in Figure 4.14 . . . . . . . . . . . . . . . . . . . . . . . . . . 4.17 Dynamic bipartite graph B 1 (J 1 0,2 ). The edges in black are one-to-one correspondence with the edges in the dynamic graph in Figure 4.6, while the edges in dashed blue correspond to -I 4×4 in J 1 0,2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Timeline of delay-estimation. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Input signals estimation: True signals (blue solid lines) vs estimated signals (red dashed lines) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 State estimation: True states (blue solid lines) vs estimated states (red square lines) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 In solid red, trace of the sample covariance of the error (u T k -ûT k , x k -xT k ) T ; in dashed blue trace of the approximate covariance matrix P k , computed by the algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 The initial state changes for every iteration. In solid red, trace of the sample covariance of the error (u T k -ûT k , x k -xT k ) T ; in dashed blue trace of the approximate covariance matrix P k , computed by the algorithm. . . . . . . . . . 5.6 Plot of mean square error in the estimation. . . . . . . . . . . . . . . . . . . . .

Figure 1 :

 1 Figure 1: Carte conceptuelle des CPS.

  étudient les conditions d'existence d'un estimateur d'état et d'entrée avec un retard , et ce dernier propose un algorithme, mais pour le cas particulier de = 1. Par conséquent, nous posons la question suivante: P6: Pour les systèmes LTI avec couplage arbitraire, comment peut-on estimer récursivement l'état et les entrées (inconnues) avec un délai -?

Figure 4 :

 4 Figure 4: Various kinds of attacks in CPS[START_REF] Teixeira | A secure control framework for resource-limited adversaries[END_REF]

Proposition 5

 5 {W, B, C, D} is ISO, with delay 1, if and only if rank(CB) = P and rank(P (z)) = N + P , ∀z ∈ C.

Figure 1 . 3 : G 1 Figure 1 . 4 : G 2 G 2

 1311422 Figure 1.3: G 1 Let us consider graph G 1 given in Figure 1.3. Notice that every vertex in V \ O has a path to at least one of the vertices in O, and hence G 1 is output-connected. Now let us consider graph

Figure 1 . 5 : E 1 Figure 1 . 6 : E 2

 151162 Figure 1.5: E 1

Figure 1 . 7 .

 17 A matching M = {(u a , w a ), (u b , w b ), (u c , w c )} on B is given in Figure1.8. Note that over the choice of vertex sets {u a , u b , u c } and {w a , w b , w c }, there does not exist another matching of size 3 on B. Hence, M is a uniquely restricted matching.

Figure 1 . 7 :Figure 1 . 8 :

 1718 Figure 1.7: Bipartite graph B

Figure 2 . 1 :

 21 Figure 2.1: G 1

  Definition 13 W, B, C, D} LT I is structurally ISO, if for almost all choices of free parameters in A W , A B , A C and A D , the corresponding system W, B, C, D} is ISO.Recall, from Lemma 3, that if the condition given in Definition 13 are satisfied, then almost all members in the family of systems W, B, C, D} LT I is ISO.

Figure 2 . 2 :

 22 Figure 2.2: Pictorial Reminder of the Construction of G

Figure 2 . 3 :

 23 Figure 2.3: Bipartite graph H associated with a structured system

Figure 2 . 4 :Figure 2 . 5 :

 2425 Figure 2.4: Bipartite graph S associated with the output matrix D

Theorem 1 (

 1 Cor.1 [22]) W, B, C, D LT I is structurally ISO if and only if the following conditions hold: (a) The bipartite graph H contains a matching of size P + N ; (b) The directed graph G is output-connected;

Example 1 :

 1 Consider the example given in Figure 2.1. Here N = 4, P = 2 and M = 3. Also note that D = 0. The bipartite graph H 1 , constructed analogous to H, associated with G 1 is as given in Figure 2.6. A matching M 1 , of size 6, is given in Figure 2.7. The only maximum U --Y linking is:

Figure 2 . 6 : Bipartite graph H 1 Figure 2 . 7 : 1 Figure 2 . 8 : 1 Figure 2 . 9 :Figure 2 . 10 :

 26127128129210 Figure 2.6: Bipartite graph H 1Figure 2.7: Matching M, of size 6, on H 1 Figure 2.8: Checking condition a) in Theorem 1

Definition 14 W

 14 * , B * , C * , D * is s-structurally ISO (resp. s-structurally unconstrained ISO) if for every system W, B, C, D} with W ∈ W * , B ∈ B * , C ∈ C * , D ∈ D * ; W, B, C, D} is ISO (resp. unconstrained ISO).

Figure 2 . 11 :

 211 Figure 2.11: Bipartite graph H ×

Theorem 3 W

 3 * , B * , C * , D * is s-structurally ISO • if the following conditions are satisfied: a) there exists a uniquely restricted matching M of size N + P on the bipartite graph H; b) there exists a uniquely restricted matching M × of size N + P on the bipartite graph H × such that M × ∩ E loop = ∅; and c) there exists a uniquely restricted matching of size P + N + term-rank(D) on the bipartite graph N . • only if the following conditions are satisfied: d) there exists a uniquely restricted matching M of size N + P on the bipartite graph H; e) there exists a uniquely restricted matching M × of size N + P on the bipartite graph H × such that M × ∩ E loop = ∅; and f ) there exists a uniquely restricted matching of size P + N on the bipartite graph Ñ .

Figure 2 .Figure 2 . 1 Figure 2 .

 2212 Figure 2.13: H ×1

Figure 2 . 16 :Example 2 :

 2162 Figure 2.16: Items needed for checking condition 1c in Thm. 3.

Figure 2 . 17 : G 2 Figure 2 . 18 : 2 Figure 2 . 19 : 2 Example 3 :

 2172218221923 Figure 2.17: G 2

  and

Figure 2 .Example 5 :

 25 [START_REF] Hsieh | Robust two-stage Kalman filters for systems with unknown inputs[END_REF] is not s-structurally ISO. Consider the example given in Figure2.48. Here N = 4, M = 3 and P = 1. Also, this example differs from the examples considered insofar in that it has non-zero feedthrough. The bipartite graph H 5 is given in Figure2.49, while Figure2.50 shows a matching M, of size 5,

Figure 2 .

 2 Figure 2.20: Matching M 1 on H 2

Figure

  Figure 2.21: Matching M 2 on H 2

Figure 2 . 35 : G 4 Figure 2 . 36 :

 2354236 Figure 2.35: G 4

Figure 2 . 37 : Matching M 1 on N 4 Figure 2 . 38 : Matching M 2 on N 4 Figure 2 . 39 : Matching M 3 on N 4 Figure 2 . 40 : Matching M 4 on N 4 Figure 2 . 41 : Matching M 5 on N 4 Figure 2 . 42 : Matching M 6 on N 4 Figure 2 . 43 : Matching M 7 on N 4 Figure 2 . 44 : Matching M 8 on N 4 Figure 2 . 45 : Matching M 9 on N 4 Figure 2 . 46 : Matching M 10 on N 4 Figure 2 . 47 :

 2374238423942404241424242434244424542464247 Figure 2.37: Matching M 1 on N 4Figure 2.38: Matching M 2 on N 4 Figure 2.39: Matching M 3 on N 4Figure 2.40: Matching M 4 on N 4

Figure 2 . 48 : G 5 Figure 2 . 5 Figure 2 . 5 Figure 2 . 51 :Figure 2 .

 248525252512 Figure 2.48: G 5

Figure 2 .Figure 2 . 54 : 5 Figure 2 . 5 Figure 2 . 57 :

 2254525257 Figure 2.53: Matching M ×5 on H ×5 Figure 2.54: Checking condition 1b)

Proposition 9 W

 9 * , B * , C * , D * is s-structurally unconstrained ISO only if the following conditions are satisfied:

Figure 3 . 1 :

 31 Figure 3.1: Graph representation of a network system affected by external agents where I, O and V are the sets of attackers, observed nodes and state nodes respectively, while the set of assailable nodes is A = {i, j, k}.

Figure 3 . 2 : 1 Figure 3 . 3 :Example 1 :

 321331 Figure 3.2: The subsystem G for the system shown in Fig. 3.1

Figure 3 . 4 :

 34 Figure 3.4: A Matching M in S

Figure 3 . 1 ,

 31 first recall that M = {(u a , w b ), (u b , w c ), (u c , w d ), (u d , w e )} (see Figure3.4) is a matching in S. Furthermore,3.5. S-Structural ISO 61there exists no other matching M ⊂ E S saturating the same vertices as M, and hence, by definition M ⊂ E S is a uniquely restricted matching. The second condition is checked with respect to the bipartite graph S × given in Figure3.5.

Figure 3 . 5 :

 35 Figure 3.5: Bipartite graph S × , in solid red: S × ∩ S, in dashed blue: E new = {(u a , w a ), (u b , w b ), (u c , w c )} while E loop = {(u d , w d )}

Figure 3 . 7 :Figure 3 . 9 :

 3739 Figure 3.7: The system G 1

Figure 3 .

 3 Figure 3.10: Matching M 1 on S 1

Figure 3 . 1 Figure 3 . 1 Figure 3 . 1 Figure 3 . 1 Figure 3 . 1 Figure 3 . 1 Figure 3 . 1 Figure 3 . 18 : 1 4 Linear 70 4. 4 . 2 76 4. 5 . 1 76 4. 5 . 2 77 4. 6

 3131313131313131814704276517652776 Figure 3.11: Matching M 2 on S 1 Figure 3.12: Matching M 3 on S 1 Figure 3.13: Matching M 4 on S 1

  respectively (see Section 4.5).

Figure 4 . 1 :Figure 4 . 3 :

 4143 Figure 4.1: G 2k Figure 4.2: G 2k+1 Figure 4.3: Evolution of an LTV system represented by time-varying periodic graphs with periodicity 2.

  Figure 4.5.

Figure 4 . 5 :

 45 Figure 4.5: Dynamic bipartite graph B(J k 0 ,k 1 )

a) System ( 1 . 1 )

 11 is structurally ISO over [k 0 , k 1 ]; b) there exists a linking of size N + (k 1k 0 )P + term-rank(D k 1 ) from X k 0 ∪ Ū to Ȳ on the dynamic graph S k 0 ,k 1 ; c) there exists a matching of size (k 1 -k 0 +1)N +(k 1 -k 0 )P +term-rank(D k 1 ) on the dynamic bipartite graph B(J k 0 ,k 1 ).

Figure 4 . 3 .

 43 ExampleConsider the time-varying system shown in Figure 4.3. Here N = 4, M = 2, P = 1 and D k = 0 2×1 , for all k. We consider the interval [0 2]. The corresponding dynamic graph S 0,2 is shown in Figure 4.6.

Figure 4 .

 4 7 highlights, in dashed blue, a collection of vertex-disjoint paths, namely x 1 0

Figure 4 .

 4 3 is structurally ISO over the interval [0, 2].

Figure 4 . 6 :

 46 Figure 4.6: Dynamic graph S 0,2 associated with the example in Figure 4.3

Figure 4 . 7 :

 47 Figure 4.7: In dashed blue, a linking L 0,2 from X 0 ∪ Ū to Ȳ on the dynamic graph associated with the example in Figure 4.3

3

 3 Figure 4.7: In dashed blue, a linking L 0,2 from X 0 ∪ Ū to Ȳ on the dynamic graph associated with the example in Figure 4.3

4. 4 . 2

 42 Proof of Theorem 6

Figure 4 . 8 : 2 System ( 1 . 1 )

 48211 Figure 4.8: Dynamic bipartite graph B(J 0,2 ). The edges in black are one-to-one correspondence with the edges in the dynamic graph in Figure 4.6, while the edges in dashed blue correspond to -I 4×4 in J 0,2

Figure 4 . 9 : 2 Figure 4 . 10 :, 2 Figure 4 . 11 :

 4924102411 Figure 4.9: M 0,2 Figure 4.10: M0,2 Figure 4.11: Matchings on the dynamic bipartite graph B(J 0,2 )

Figure 4 . 15 :

 415 Figure 4.15: Dynamic graph S 1 0,2 associated with the example in Figure 4.14

Figure 4 . 16 :

 416 Figure 4.16: In dashed blue, a linking L 1 0,2 from X 0 ∪ Ū to Ȳ on the dynamic graph associated with the example in Figure 4.14

Figure 4 . 17 :

 417 Figure 4.17: Dynamic bipartite graph B 1 (J 1 0,2 ). The edges in black are oneto-one correspondence with the edges in the dynamic graph in Figure 4.6, while the edges in dashed blue correspond to -I 4×4 in J 1 0,2

Figure 4

 4 Figure 4.18: M 1 0,2

84 Chapter 5 .

 845 Unbiased Filtering for State and Unknown Input with Arbitrary Delay

Proposition 19

 19 Given xk-and P xx k-, use an arbitrary ûT k--1 to set ẑT k = ûT k--1 , xT k-, and let Pk be such that [0, I n ] Pk 0 In = P xx k-, other entries of Pk being arbitrarily chosen, provided Pk > 0. Then, the estimates and covariance matrices from (5.12)-(5.11) and those from (5.17)-(5.18) are related as follows: ûkxk-+1 = ẑk+1 and P k-+1 = Pk+1 . Proof: The proof is immediate by noting that Σk-= Σ + F P k-F T and F ẑk + ȳk = y k--C xk--Ax k- . Delay

Figure 5 . 2 :

 52 Figure 5.2: Input signals estimation: True signals (blue solid lines) vs estimated signals (red dashed lines)

Figure 5 . 3 :Figure 5 . 4 :

 5354 Figure 5.3: State estimation: True states (blue solid lines) vs estimated states (red square lines)

Figure 5 .Figure 5 . 5 :

 555 Figure 5.5: The initial state changes for every iteration. In solid red, trace of the sample covariance of the error (u T k -ûT k , x k -xT k ) T ; in dashed blue trace of the approximate covariance matrix P k , computed by the algorithm.

Figure 5 . 6 :

 56 Figure 5.6: Plot of mean square error in the estimation.

  Il est bien connu que les approches algébriques pour caractériser l'observabilité (et aussi la commandabilité) sont basées sur des calculs de rang de matrices (condition de Kalman ou test de Popov-Belevitch-Hautus (PBH)). Pour ce faire, la connaissance exacte des matrices à évaluer est requise et le coût de calcul du rang d'une matrice explose avec la dimension du système. D'autre part, le test PBH ne convient pas aux systèmes linéaires variant dans le temps (LTV). Cela conduit à l'étude de l'observabilité basée sur la structure du réseau sous-jacent (représenté par un graphe). Il s'agit donc d'étudier des systèmes dits systèmes structurés. Dans ces systèmes, les matrices sont composés de zéros et de paramètres libres. Intuitivement, on peut penser à la présence (resp. absence) de zéros comme absence (resp.

	xvi	Résumé détaillé
	Besoin de caractérisations graphiques

présence) de connexions entre composants d'un système. Les éléments non fixées à zéro sont appelées paramètres libres. Chaque choix de valeurs pour ces paramètres libres produit un nouveau système. On peut donc penser à une famille de systèmes caractérisés par une même configuration d'éléments nuls. Dans un tel contexte, d'une part, on cherche des résultats dits structurels, c'est-à-dire des résultats vrais pour presque tous les choix de paramètres libres sauf ceux (éventuellement) situés sur une variété algébrique de l'espace des paramètres libres

[START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF]

. Puisqu'une bonne variété algébrique a une mesure de Lebesgue nulle, une interprétation probabiliste est la suivante: en supposant que les paramètres libres sont choisis au hasard dans une distribution continue, une propriété structurelle implique que chaque membre dans une famille de systèmes donnée vérifie ladite propriété avec une probabilité égale à 1. D'un autre part, on peut désirer des propriétés qui soient vraies quelque soit le choix de paramètres non nuls. De tels résultats sont dits fortement structurels (s-structurels). Il est à noter que le choix de paramètres non-nuls s'applique à tout les éléments du vecteur de paramètres. La principale différence entre les propriétés structurelles et les propriétés s-structurelles est que la première donne des résultats probabilistes, tandis que la seconde fournit des résultats déterministes. Un système structuré peut être représenté par un graphe, où la présence de paramètres libres dans les matrices du système équivaut à l'existence d'arêtes sur ledit graphe. Dans la suite, un choix numérique de paramètres libres doit être considéré comme un choix de la pondération associée à une arête. Ainsi, les termes "paramètres libres" et "poids d'arête" sont utilisés indifféremment, en fonction du contexte.

  Notez que les questions soulevées jusqu'ici proviennent d'un point de vue de la caractérisation et qu'elles traitent des scénarios sans bruit, comme c'est le cas dans la littérature. Il convient de rappeler que l'ISO est une propriété du système. Le fait qu'un système soit ISO nous indique que nous pouvons reconstruire à la fois les états et les entrées inconnues. Cependant, cela ne nous dit pas comment cette reconstruction peut être faite. De plus, dans de nombreux réglages pratiques, les états et les mesures peuvent être altérés en raison du bruit.

	les questions
	suivantes:
	P4: Quelles sont les conditions graphiques pour lesquelles une famille de systèmes LTV,
	représentés par (peut-être) des graphes variables dans le temps, possède la propriété de
	ISO structurelle?

Cela nous motive à porter notre attention sur les topologies temps-variable. Par la suite, nous posons P5: Quelles sont les conditions graphiques pour lesquelles une famille de systèmes LTV, représentés par (peut-être) des graphes variables dans le temps, possède la propriété de ISO s-structurelle? xviii Résumé détaillé

  Dans le chapitre 3, nous traitons le cas des systèmes en réseau LTV représentés par une topologie fixe. Sous des hypothèses appropriées sur la structure des matrices d'entrée et de sortie, nous montrons d'abord l'équivalence entre ISO d'un système linéaire et l'observabilité d'un sous-système défini de manière appropriée. Ensuite, nous introduisons la notion d'ISO uniforme à N pas, i.e. ISO vérifiable pour tout intervalle de N mesures. Cette caractérisation graphique est réalisée tant de manière structurelle que fortement structurelle. Les résultats obtenus s'appuient sur la caractérisation structurelle et fortement structurelle de l'observabilité donnée dans

	Résumé détaillé	xix
	2.

1. La première contribution principale de cette thèse est en réponse à la question P1, et elle est traitée dans le chapitre 2. Étant donné un système en réseau LTI et son graphe correspondant, disons G, on associe un graphe bipartite, disons H. Par la suite, nous définissons un autre graphe bipartite, disons H × . Nous fournissons, en termes d'existence de couplages uniquement restreints sur H et H × , une condition nécessaire et une condition suffisante pour ISO s-structurelle. Sous des hypothèses appropriées sur la matrice de couplage entrée-sortie, nous montrons que ces deux conditions peuvent être combinées pour obtenir une caractérisation graphique de ISO s-structurelle.

  3. Les conclusions du chapitre 3 ont certaines limitations. Tout d'abord, certaines hypothèses sont formulées sur la structure des matrices d'entrée et de sortie. En conséquence de telles hypothèses, le problème de l'ISO est équivalent à un problème d'observabilité Cette thèse traite de la notion d'observabilité états-entrées (ISO) dans les systèmes de réseaux linéaires. On cherche des caractérisations graphiques en utilisant la notion de structure (resp. s-structural) ISO. Tout d'abord nous nous concentrons sur les systèmes de réseaux linéaires invariant en temps, représentés par des graphes fixes et fournissons des caractérisations pour structure ISO fortes. Par la suite, nous nous intéressons aux systèmes de réseaux linéaires variant en temps, dans lesquels nous nous concentrons d'abord sur le cas particulier des graphes fixes (la structure du graphe reste fixe mais les poids sur les arêtes peuvent varier à la dynamique qui varie dans le temps). Nous montrons que, sous des hy-

	Thesis Abstract
	Publications
	Résumé -
	Journaux

d'un sous-système convenablement défini. Par la suite, on profite de cette équivalence pour étudier l'ISO structurelle et fortement structurelle. Cependant, l'extension de ces résultats en tenant compte de la structure arbitraire des matrices d'entrée et de sortie n'est pas triviale, car on ne peut pas reformuler l'ISO comme un problème équivalent d'observabilité. Deuxièmement, ces résultats ne s'étendent pas immédiatement au cas où la topologie du réseau varie sur un intervalle. Dans le chapitre 4, nous nous concentrons sur les systèmes en réseau LTV mais avec une topologie variant dans le temps. L'évolution de tels systèmes peut être représentée par une collection de graphes {G k }. Nous trouvons des conditions dans lesquelles le système avec une configuration de zéros fixes imposés par {G k } est ISO: a) pour presque tous les choix de pondérations d'arêtes dans {G k } (ISO structurelle); et b) pour tous les choix non nuls de pondérations d'arêtes dans {G k } (ISO fortement structurel). Nous introduisons deux descriptions appropriées de la collection entière de graphes {G k } , appelés graphe dynamique et graphe bipartite dynamique. Deux caractérisations équivalentes de l'ISO structurelle sont ensuite présentées en termes d'existence d'un chemin et d'un couplage de taille appropriée dans le graphique dynamique et dans le graphe bipartite dynamique, respectivement. Dans le cas fortement structurel, nous fournissons une condition suffisante et une condition nécessaire, à la fois concernant l'existence d'un couplage restreint de taille appropriée dans le graphe bipartite dynamique et dans un sous-graphe de celui-ci. Lorsqu'il n'y a pas de couplage direct de l'entrée sur la sortie, les deux conditions peuvent être fusionnées pour donner lieu à une condition nécessaire et suffisante. Cela répond aux questions P4 et P5. 4. Dans le chapitre 5, nous considérons les systèmes en réseaux linéaires avec des entrées inconnues. Nous présentons un algorithme récursif sans biais qui estime simultanément les états et les entrées. Nous nous concentrons sur les systèmes inversibles de délai -left avec un retard intrinsèque ≥ 1, où la reconstruction de l'entrée est possible uniquement en utilisant des sorties allant jusqu'à pas de temps en amont. Autrement dit, nous fournissons un algorithme linéaire récursif pour estimer les simultanément les états et les entrées avec un retard -. Cela répond à la question P6. En montrant une équivalence avec un système singulier, nous énonçons des conditions dans lesquelles le filtre variant dans le temps converge vers un filtre stable stationnaire, impliquant la solution d'une xx Résumé détaillé équation algébrique discrète de Riccati. pothèses appropriées sur la structure des matrices de commande, d'observation et d'action, l'ISO d'un système équivaut à l'observabilité d'un sous-système défini de manière appropriée. Par la suite, nous exploitons cette équivalence pour obtenir des caractérisations graphiques de l'ISO structurelle (resp. S-structurelles).

  The coefficients in A W k , A B k , A C k and A D k that are not a priori fixed to zero are referred to as free parameters. Let W k , B k , C k and D k denote, at time instant k, the set of all matrices that have the same structure of fixed zeros as A W k , A B k , A C k and A D k , respectively. These sets are defined as follows:

	10	Chapter 1. Preliminaries

  system matrices W B, C and D obey the pattern of imposed zeros of A W , A B , A C and A D , respectively, where A W , A B , A C and A D are particular instances of the matrices A W k , A B k , A C k and A D k , (defined in Chapter 1; see Sect. 1.2), respectively. We denote by W, B, C, D LT I the family of all systems whose dynamics obey eq. (2.1) and whose zero/non-zero positions are as given by the respective matrices in eq. (2.1). Let G =

{V, E} be the graph associated with the system W, B, C, D LT I where

V = (X ∪ U ∪ Y ) is the vertex set and E = E W ∪ E B ∪ E C ∪ E D .

The edge sets E W , E B , E C and E D are defined analogous to the edge sets E W k , E B k , E C k and E D k , respectively; but with the constraint that they do not change with time. We denote by W * , B * , C * , D * LT I

  bipartite graphs H 2 and H ×2 are as given in Figures 2.18 and 2.19, respectively. From Figures 2.20 and 2.21 it can be seen that there does not exist a uniquely restricted matching over the choice of vertex sets {u, x 1 , x 2 , x 3 } and {x 1 , x 2 , x 3 , y 1 }. The same can be said with respect to the vertex sets {u, x 1 , x 2 , x 3 } and {x 1 , x 2 , x 3 , y 2 } (see Figures 2.22 and 2.23); {u, x 1 , x 2 , x 3 } and {x 1 , x 2 , x 3 , y 2 } (see Figures 2.24 and 2.25); {u, x 1 , x 2 , x 3 } and {x 1 , x 3 , y 1 , y 2 } (see Figures 2.26 and 2.27) and {u, x 1 , x 2 , x 3 } and {x 2 , x 3 , y 1 , y 2 } (see Figures 2.28 and 2.29).

  1 2 } (see Figures 2.39 and 2.40); {u 0 1 , x 1 , x 2 , x 3 } and {x 1 , x 3 , y 1 1 , y 1 2 } (see Figures 2.41 and 2.42); {u 0 1 , x 1 , x 2 , x 3 } and {x 1 , x 2 , x 3 , y 1 2 } (see Figures 2.43 and 2.44) and {u 0 1 , x 1 , x 2 , x 3 } and {x 2 , x 3 , y 1 1 , y 1 2 } (see Figures 2.45 and 2.46). Thus, there does not exist a uniquely restricted matching of size 4 on N 4 . That is, condition 2c given in Thm. 3 is violated, and therefore, the example given in

  2.21: Matching M 2 on H 2 Figure 2.30: All maximum matchings on H 2 Figure 2.32: H 3 Figure 2.33: H ×3 Figure 2.34: Bipartite graphs associated with G 3 on H 5 . Note that over the choice of vertex sets {u 1 , x 1 , x 2 , x 3 , x 4 } and {x 1 , x 2 , x 3 , x 4 , y 3 } there does not exist another matching on H 5 , and therefore M is a uniquely restricted matching. Next, note that since G 5 does not have any self-loops, E loop = ∅. The bipartite graph H ×5 is given in Figure 2.52, while Figure 2.53 shows a matching M

			Figure 2.22: Matching	Figure 2.23: Matching
			M 3 on H 2	M 4 on H 2
	Figure 2.24: Matching	Figure 2.25: Matching	Figure 2.26: Matching	Figure 2.27: Matching
	M 5 on H 2	M 6 on H 2	M 7 on H 2	M 8 on H 2
		Figure 2.28: Matching	Figure 2.29: Matching
		M 9 on H 2	M 10 on H 2
		Figure 2.31: G 3

×5 , of size 5, on H 5 . Since over the choice of vertex sets {u 1 , x 1 , x 2 , x 3 , x 4 } and {x 1 , x 2 , x 3 , y 2 , y 3 } there does not exist another

  implies Prop. 1 (seeChapter 2). DelayIn the noise-free case, it was shown in[START_REF] Sundaram | Delayed observers for linear systems with unknown inputs[END_REF] that delay-left invertibility and strong detectability, i.e., rank A -zI B C D = n + p, ∀z ∈ C s.t. |z| ≥ 1, are necessary and sufficient to

  .16) With this notation in place, we have the following result.

	Proposition 18
	([18] Thm. 3 and [17] Thm. 4). If

  then the DARE (5.16) has a unique solution P , Pk converges exponentially fast to P , and the corresponding steady-state filter is stable.

	1/2

s ) has no unreachable mode on the unit circle, i.e., rank [ zI-Fs Q 1/2 s ] = p + n, ∀z ∈ C s.t. |z| = 1,

  Propositions 18 and 19 and Lemmas 19 and 20, together, give the following result.

	Theorem 8
	If the system is
	i) delay-left-invertible,
	ii) strongly detectable, and
	iii) the pair (F s , Q 1/2 s ) has no unreachable mode on the unit circle,

A-zI B C D , and hence is n + p for all |z| ≥ 1. As a consequence, rank zE -F U T 2

F = n + p, ∀z ∈ C s.t. |z| ≥ 1.

then, for the filter described in Section 5.3.1, the matrix P k converges exponentially fast to the unique solution P of the DARE (5.16), and the corresponding steady-state filter is stable.

Nous introduisons deux descriptions appropriées de la collection complète de graphes, nommés graphes dynamiques et graphes dynamiques bipartites. Deux caractérisations équivalentes de l'ISO structurelle sont ensuite présentées en termes d'existence d'une liaison et d'une correspondance de taille appropriée, respectivement, dans le graphe dynamique et dans le graphe dynamique bipartite. Pour les ISO fortement structurelles, nous fournissons une condition suffisante et une condition nécessaire, concernant à la fois à l'existence d'une correspondance restreinte de taille appropriée dans le graphe dynamique bipartite et dans un sous-graphe de celle-ci. Lorsqu'il n'y a pas d'action directe de la commande sur les mesures, les deux conditions peuvent être fusionnées pour donner lieu à une condition nécessaire et suffisante. Enfin, nous présentons un algorithme récursif sans biais qui estime simultanément les états et les commandes. Nous nous concentrons sur les systèmes à retard-inversibles avec retard intrinsèque > 1, où la reconstruction de la commande est possible uniquement en utilisant des sorties allant jusqu'à un nombre de temps plus tard. En montrant une équivalence avec un système de descripteurs, nous présentons des conditions dans lesquelles le filtre variant en temps converge vers un filtre stationnaire stable, impliquant la solution d'une équation algébrique à temps discret de Riccati.

The ability of a system to reconstruct a sequence of unknown inputs up to some delay using the given sequence of output measurements and knowledge of the initial state is referred to as unknown input reconstruction

 3 It should be noted that not every unknown input affecting a system is malicious in nature.

Note that, since the free parameters are allowed to take any values in R it implies that, in particular, they can take zero. Therefore, there exists Z1 (resp. Z2, Z3 and Z4) that contain more zeros than the fixed zeros in AW k (resp. AB k , AC k and AD k ). However, such choices of Z1 (resp. Z2, Z3 and Z4) lie on a proper variety of the space of free parameters of AW k (resp. AB k , AC k and AD k ).

To see what the terms "form I, form II and form III" mean, we refer the interested reader to[START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF][START_REF] Chapman | On strong structural controllability of networked systems: a constrained matching approach[END_REF].

Recall that the vertices in U k are indexed as 1,

2, . . . , P , for every k ∈ [k0, k1].

This means that also in the case D = 0 we consider a larger family of systems than[START_REF] Roshan A Chavan | Recursive input reconstruction with a delay[END_REF], where the proposed filter was unbiased only under further assumptions.

In Chapter 3, we turned our attention to linear time-varying (LTV) network systems wherein the underlying graph remains fixed and the weights along the edges vary with

Acknowledgments

First, I would like to thank my Lord Jesus Christ!

Publications

Journal Papers of Q, since the left vertex set corresponds to columns while the right vertex set corresponds to rows of Q, it follows that the edges correspond to the positions that are not fixed to zero. Exploiting the algebraic characterization of delay-1 left-invertibility given in Prop. 1, we define the following.

Definition 16

W * , B * , C * , D * is s-structurally delay-1 left invertible if for every B ∈ B * , C ∈ C * and D ∈ D * , the system {W, B, C, D} is delay-1 left-invertible, i.e., rank(Q) = P +N +rank(D).

Proof of Sufficiency

We recall a result from [START_REF] Hershkowitz | Ranks of zero patterns and sign patterns[END_REF] that will be of interest to us in the sequel: Lemma 8 (Thm.3.9 [START_REF] Hershkowitz | Ranks of zero patterns and sign patterns[END_REF]) Let A be an m × n pattern matrix and B(A) be a bipartite graph obtained from A, and let r be a nonnegative integer. Then the following are equivalent:

(i) rank(A) equals r for every non-zero choice of free parameters.

(ii) In B(A) there exists no matching of size greater than r, and there exists at least one uniquely restricted matching of size r in B(A).

The following lemma gives a sufficient condition for s-structural delay-1 left-invertibility.

Lemma 9 W * , B * , C * , D * is s-structurally delay-1 left invertible if there exists a uniquely restricted matching of size P + N + term-rank(D) in N .

Proof: Note that Q has fixed zero positions, algebraically independent free parameters, and some positions fixed to -1. Let Q be the pattern matrix obtained by replacing the fixed -1 terms with free parameters that are distinct among themselves and also among the free parameters of Q. This implies that Q is a particular instance of Q. Let N ( Q) be the bipartite graph associated with Q, and note that N ( Q) = N (a pictorial description of N is, as was mentioned previously, given in Figure 2.12) Suppose that there exists a uniquely restricted matching of size P + N + term-rank(D) on N . Hence, there exists a uniquely restricted matching of size P + N + term-rank(D) on N ( Q). Then from Lemma 8 for every non-zero choice of free parameters in Q, the corresponding realization has rank equals P + N + term-rank(D). This remains true even when some of the free parameters in Q are fixed to -1 to obtain Q. Hence, for every B ∈ B * , C ∈ C * and D ∈ D * , the corresponding realization of Q has rank equals P + N + term-rank(D). This further implies from Definition 16 that W * , B * , C * , D * is s-structurally delay 1 left invertible.

Thus, from proof of Prop. 6 and Lemma 9, the proof of sufficiency is completed.

Proof of Necessity

Recalling the construction of the bipartite graph Ñ , we now provide a necessary condition for s-structural delay-1 left invertibility.

Lemma 10 W * , B * , C * , D * is s-structurally delay 1 left invertible only if there exists a uniquely restricted matching of size P + N in Ñ .

Proof: Let Q be a submatrix obtained by looking at r, 1 ≤ r ≤ P + N , columns and all rows of Q. Let N ( Q) be the associated bipartite graph. We prove the claim made in Lemma 10 by proving a slightly stronger result, given in Lemma 11.

Lemma 11

Let 1 ≤ r ≤ P +N . For any submatrix Q formed with r columns of Q and all rows of Q, if there does not exist a uniquely restricted matching of size r in N ( Q), then there exists a non-zero choice of free parameters such that the corresponding realization of Q has rank Q < r.

The proof of Lemma 11 is along similar lines as that of Lemma 7, and is hence skipped. Setting r = P + N and by noting that for r = P + N the bipartite graph N ( Q)is indeed the bipartite graph Ñ , it follows, from Lemma 11, that there exists a non-zero choice of free parameters for which the corresponding realization of Q has rank Q < N + P . This further implies from Definition 16 that W * , B * , C * , D * is not s-structurally delay 1 left invertible. This completes the proof of Lemma 10. Thus, from proof of Prop. 9 and Lemma 10, the proof of necessity is completed.

Analogously, one can define structural observability and uniform N -step structural observability for LTV systems. In particular, definitions for structural ISO, structural observability and uniform N -step structural observability can also be obtained for LTI systems where the space of free parameters is R |E| and the same free parameters are repeated at each time instant.

, thereby exhibiting a choice of entries for which {W, A B , A C } LTV is ISO. Consequently, from Definition 18, the system {W,

However, the converse of Remark 8 is open. In the rest of this section we show that, under Assumption 2, the conditions given in Remark 8 are equivalent.

Uniform N -step structural ISO for LTV systems

From Proposition 11, we can study ISO by studying observability of a suitable sub-system. Here we apply this technique to the family of systems {W, A B , A C } LTV , defining a suitable family of subsystems. We define the set of matrices W as W = { QT N W QN | W ∈ W}. Let W, ÃC } LTV represent the family of all LTV systems as given in (4) but without the known input xk . We denote by W, ÃC } LTI the counterpart LTI subsystem (i.e., whose matrices have the same zero/non-zero pattern as given by W). As a consequence of Prop. 11, for LTI systems we have the following remark:

It turns out that corresponding to Remark 9, conditions for structural results can also be obtained for LTV systems, as shall be evidenced in the rest of this subsection. An immediate corollary of Prop. 11 is the following Proposition 12 non-zero choice of free parameters such that the corresponding numerical realization of P k 0 ,k 1 has rank P k 0 ,k 1 < (k 1k 0 )P + (k 1k 0 + 1)N ; this further implies that there is a non-zero choice of parameters for which rank

, and hence the system is not s-structurally ISO over

The formulation for general r is introduced because it allows a proof by induction on r, as follows.

Proof of Lemma 17:

The proof is by induction, quite similar to that of Theorem 3.4 in [START_REF] Hershkowitz | Ranks of zero patterns and sign patterns[END_REF], but adapted to the fact that J k 0 ,k 1 , has fixed zero, non-zero and -1 positions, respectively. We proceed as follows: Notice that in P k 0 ,k 1 some of the free parameters are fixed to -1. Also, the free parameters that are not a priori fixed to -1 are algebraically independent. For r = 1 every matching of size r is uniquely restricted. Consequently, if there does not exist a uniquely restricted matching for r = 1, then there does not exist either a matching of size r = 1 on B(L k 0 ,k 1 ). This implies that L k 0 ,k 1 is an all-zero column, and hence, rank(L k 0 ,k 1 ) equals zero. Assume that the claim holds for r -1 (inductive assumption). We will prove that this implies the claim holds for r columns of P k 0 ,k 1 . Matrix L k 0 ,k 1 might or might not have a row with exactly one non-zero element, and the two cases require a different proof. Case a: Suppose that there exists a row i 1 in L k 0 ,k 1 that has exactly one non-zero term in the (i i ,j 1 ) position. Let L k 0 ,k 1 (:, j 1 ) denote the matrix L k 0 ,k 1 with all the rows, and all but the j th 1 column, and let B(L k 0 ,k 1 (:, j 1 )) denote the corresponding bipartite graph. B(L k 0 ,k 1 (:, j 1 )) does not have a uniquely restricted matching of size r -1, since if it has a uniquely restricted matching of size r -1, then such a matching together with the edge corresponding to the i th 1 row and j th 1 column, forms a uniquely restricted matching of size r on B(L k 0 ,k 1 ). From inductive assumption, there exists a choice of free parameters, of L k 0 ,k 1 (:, j 1 ), such that the corresponding matrix, say L 1 k 0 ,k 1 (:, j 1 ), has rank less than r -1. Consequently, there exists a choice of free parameters, in L k 0 ,k 1 , such that the corresponding matrix, namely L 1 k 0 ,k 1 , has rank(L 1 k 0 ,k 1 ) < r. Case b: Suppose that there does not exist a row in L k 0 ,k 1 that has exactly one non-zero term. Under such a setting, a choice of free parameters for which the corresponding matrix does not have full column rank can be easily found without using the inductive assumption nor the assumption about the non existence of uniquely restricted matching. Notice that thanks to the positions of -1's in P k 0 ,k 1 , it is not possible for any row in L k 0 ,k 1 to have more than 1 fixed -1 term. Hence, there can be only three kinds of row: i) an all-zero row; ii) a row with exactly one -1 and with p ≥ 1 free parameters; iii) a row with no -1 and with p ≥ 2 free parameters. Rows of kind i) already have zero row-sum. For rows of kind ii), one can assign non-zero values to the free parameters such that, in the resulting matrix, say L k 0 ,k 1 , for every row i, the total row sum is zero, i.e., r j=1 L k 0 ,k 1 (i, j) = 0. This can be accomplished in the following manner: Suppose that in a given row there are p (p > 1) free parameters, for all but one free parameter assign -1, then fix the last parameter to p. For rows of kind iii), fix p -1 parameters to -1 and then fix the last parameter to p -1. With this non-zero choice of parameters, the sum of elements along each row of L k 0 ,k 1 is 0, which means that the sum of all columns of L k 0 ,k 1 is a zero vector and hence the columns are not linearly independent, so 4.6. On the applicability of conditions in Theorem 6 (resp. Theorem 7) for LTI network systems 79 that this numerical realization of L k 0 ,k 1 has rank L k 0 ,k 1 < r. Thus, the proof of Lemma 17 is complete.

Example

Consider the time-varying system shown in

Thus, the sufficient condition given in Theorem 6 is satisfied, and consequently the structured system represented by Figure 4.14 is structurally ISO over the interval [0, 2]. The dynamic bipartite graph, B 1 (J 1 0,2 ), associated with the system in Figure 4.14 is shown in Figure 4.17. Figure 4.18 shows a matching M 1 0,2 of size 14 on B 1 (J 1 0,2 ). Moreover, over the same choice of vertex sets i.e., {x 1 0 , x 2 0 , x 3 0 , x 4 0 , u

2 , y 1 2 , y 2 2 } there does not exist another matching. Therefore, M 1 0,2 is a uniquely restricted matching of size 14 on B 1 (J 1 0,2 ). Hence, from item 1) Theorem 7, we can conclude that the system given in 4.6 On the applicability of conditions in Theorem 6 (resp. Theorem 7) for LTI network systems

For LTI network systems, a graphical characterization for structural ISO (resp. s-structural ISO) is given in Chapter 2 (see Theorem 1 and Theorem 2) of this thesis. The questions that arise, then, are the following:

(i) Given that LTI systems are subclasses of all LTV systems, are the conditions given in Theorem 6 applicable for LTI network systems? To the best of our knowledge, equivalence between structural ISO for LTI network systems and structural ISO for LTV network systems with fixed graphs, remains open, unlike structural observability (see [START_REF] Poljak | On the generic dimension of controllable subspaces[END_REF][START_REF] Poljak | On the gap between the structural controllability of time-varying and time-invariant systems[END_REF]). While proving the following "structural ISO Chapter 5

Unbiased Filtering for State and Unknown Input with Arbitrary Delay

Introduction

In the present chapter, for systems with arbitrary direct feedthrough, we provide a recursive linear algorithm for estimating both states and inputs with delay : at time k, given output measurements up to y k , an estimate of u k-and x k-+1 is obtained (see Figure 5.1).

The chapter is organized as follows. In Section 5.2 we state the problem being studied in this chapter and summarize the preliminary material needed for developing the results, while we present our main result in Section 5.3. Section 5.4 deals with an appropriately chosen numerical example. The material contained in this chapter has appeared in [START_REF] Garin | Unbiased Filtering for State and Unknown Input with Delay[END_REF].

, where R appears times, Compute:

Conclusion

Proposition 20 (Corollary 1 [START_REF] Garin | Structural Delay-1 Input-and-State Observability[END_REF]) {W, B, C, D} is structurally ISO with delay-1 if and only if (i) The bipartite graph H contains a matching of size P + N ;

(ii) The directed graph G is output-connected;

(iii) The directed graph K contains a linking of size

where R is the size of the maximum matching on S.

Insofar, we have sought a binary response to the question "Is a given family of systems structurally observable (resp. ISO)?". If the conditions given in Prop. 20 are satisfied, then one obtains a positive answer to the aforementioned question; meaning that the whole state space (resp. space spanned by the state vectors and the sequence of unknown input vectors) is observable (resp. ISO). While one obtains a negative answer to the same question if the conditions are violated, it is worth asking to what extent is {W, B, C, D} ISO if these conditions are not satisfied. Clearly, conditions in Prop. 20 being violated implies that gen-rank(Ψ) < N + (N -1)P . This further implies at least one of the following: a) gen-rank(Θ) < N ; b) gen-rank(Γ) < (N -1)P ; c) for almost all choices of free parameters, range spaces of Θ and Γ have non-trivial intersection. Recall that the gen-rank(Ψ) gives the generic dimension of the ISO subspace. That is, for almost all choices of free parameters, the corresponding ISO subspace has dimension equals gen-rank(Ψ). However, as was correctly pointed out in [START_REF] Commault | On the fixed controllable subspace in linear structured systems[END_REF], the generic dimension gives a number that is same for almost all choices of free parameters. This does not mean that the observability (resp. ISO) subspace remains fixed. It is quite possible that different choices of free parameters could lead to different subspaces. Then, the notion of fixed observable (resp. ISO) subspace refers to the observable (resp. ISO) subspace that is present for almost all choices of free parameters. For LTI network systems, characterizations for the fixed observable subspace have been given in [START_REF] Commault | On the fixed controllable subspace in linear structured systems[END_REF]. More generally, for LTI network systems, when the conditions given in Prop. 20 are violated, graphical characterizations of fixed ISO subspace are missing. In trying to address this problem, it may be essential to treat the cases a), b) and c) (discussed in the preceding paragraph) separately. For LTV network systems with time-varying topologies, under the assumption that the conditions given in Theorem 6 (see Chapter 4) are violated, characterizations of both fixed observable subspace and fixed ISO subspaces could be lines of future investigation. The authors in [START_REF] Christian | Determination of the dimensions of strong structural controllable subspaces[END_REF] provided a lower bound for the dimension of the controllable subspace of structured linear systems, while also determining an upper bound on the number of uncontrollable eigenvalues at zero frequency. However, similar results for strong structural ISO seem to be lacking.

Introduction of dependent parameters

The notion of structural controllability as introduced by Lin in [START_REF] Lin | Structural controllability[END_REF] requires that the positions that are not a priori fixed to zero be algebraically independent. Recall that all the graphical Appendix for Chapter 3

Main Result for LTI case: Another approach

In this section, we show that for a given system the ISO problem can be reformulated as an equivalent problem in observability of an appropriately defined subsystem. We use PBH-like tests to show this equivalence. Note that a similar result is given by Lemma 2 in [START_REF] Kibangou | Input and state observability of network systems with a single unknown input[END_REF], but restricted to the case of single unknown input. Here we account for multiple unknown inputs.

Let S K 1 ,...K M ;N denote a selection matrix which is defined as follows:

We can therefore define the matrices W = S T i 1 ...i P ;N W S i 1 ...i P ;N and ÃC = S T i 1 ...i P ;M A C S i 1 ...i P ;N . These are obtained by removing from W (resp. A C ) the first P rows and the first P columns. W ∈ R (N-P) × (N-P) and ÃC ∈ R (M-P) × (N-P) . The following proposition characterizes ISO in terms of observability of a suitable subsystem:

Proposition 21

Under assumption 2, the system {W, A B , A C } is ISO if and only if the subsystem { W , ÃC } is observable.

Proof: First notice that assumption 2 implies that rank(A

Since we assume that N > P , it follows from Prop. 10 that M > P , which in turn implies that rank(J) = P .

We define the following permutation matrices π 1 and π 2 .

Under assumption 2, and from (I) and (II), we obtain rank(Γ z ) = rank( φz )+rank(JA C A B )+ P = rank( φz ) + 2P . From Prop. 5, we know that the system {W, A B , A C } is ISO if and only if rank(Γ z ) = N + P , which is equivalent to rank( φz ) = N -P . This in turn is equivalent to the observability of the subsystem { W , ÃC }.

Appendix for Chapter 4

Theorem 6: proof for b) =⇒ c)

Lemma 21

If there exists a linking of size N + (k 1k 0 )P + term-rank(D k 1 ) on the dynamic graph S k 0 ,k 1 , from X k 0 ∪ Ū to Ȳ , then there exists a matching of size (k

those vertices in X ∪ Ū \ U k 1 that are not saturated by L) and { X ∪ Ū \ U k 1 } L (those vertices in X ∪ Ū \U k 1 that are saturated by L). Note that since L saturates all the vertices in X k 0 ∪ Ū \U k 1 , it follows that { X ∪ Ū \U k 1 } N L = { X \X k 0 } N L . For every vertex in { X \X k 0 } N L , one can look at the edges of the form (X i k 0 +p ,X i k 0 +p ) (via identity blocks), where p ∈ {1, 2, . . . , k 1k 0 }. All such edges can be added to a matching, say M * . Given that there exists a linking L, of size N , from X k 0 ∪ Ū to Ȳ , on the dynamic graph S k 0 ,k 1 , it implies (i) every vertex X i k 0 is connected either to some vertex in Y j k 0 , in which case the edge from X i k 0 to Y j k 0 is included in a matching M * , on B(J k 0 ,k 1 ); or is connected to some vertex in X q k 0 +1 . The vertex X q k 0 +1 may be connected either to some vertex in Y j k 0 +1 , in which case we include the edge from X i k 0 to X q k 0 +1 , and the edge from X q k 0 +1 to Y j k 0 +1 in M * ; or it is connected to a vertex X q k 0 +2 . In case of the latter, the process continues analogously. Indeed, from Definition 7, the edges corresponding to every vertex covered by the linking L can be added to the matching M * .

(ii) every vertex U i k 0 +p is connected either to some vertex in X j k 0 +p+1 , in which case we include the edge from U i k 0 +p to X j k 0 +p+1 to M * ; or to some vertex in Y j k 0 +p , in which case the edge from U i k 0 +p to Y j k 0 +p is included to M * . Note that for p = (k 1k 0 ), the only possible edges are of the form U i k 1 to Y j k 1 , and, thanks to L, there are exactly term-rank(D k 1 ) such edges; all of which are added to M * .

Appendix B. Appendix for Chapter 4

Therefore, there exists a matching on the bipartite graph B(J k 0 ,k 1 ), and moreover it has the correct size, i.e., (k 1k 0 + 1)N + (k 1k 0 )P + term-rank(D k 1 ).