T Boukhobza
email: taha.boukhobza@univ-lorraine.fr

F Hamelin

C Simon

A graph theoretical approach to the parameters identifiability characterization

Keywords: Parameters identifiability, structured linear systems, graph theoretical approach

This paper is devoted to the generic parameters identifiability analysis for structured linear systems with unknown inputs. The proposed method is based on a graph-theoretic approach and assumes only the knowledge of the system's structure. Necessary and sufficient conditions are expressed in graphical terms which ensure that a given set of unknown parameters characterizing the model of the system are structurally identifiable using the available measurements, assuming that the inputs and initial conditions are quite informative. Even if we are not interested in proposing identification schemes, these given conditions are necessary and sufficient to the parameter identification whatever the used algorithms to determine numerically the parameters values. Finally, note that the given conditions are quite easy to check because they are based on searching and comparing some specific paths and cycles in a digraph. This makes our approach well suited to study large scale systems.

Introduction

This paper deals with the analysis of a priori global identifiability of general structured linear dynamical systems with unknown inputs. In such systems, the matrices have a number of fixed zero entries while the rest of the entries are not numerically known. Following the definition of local identifiability by Bellman and Aström (Bellman and Ästrom 1970) and later by Chapman and Godfrey [START_REF] Chapman | Some extensions to the exhaustive-modeling approach to structural identifiability[END_REF], a model is identifiable if error-free data lead to a finite number of solutions for all the parameters in the model equations. A model is unidentifiable if at least one parameter is unidentifiable, i.e. has an infinite number of possible values. Global identifiability concerns the possibility of uniquely determining the model parameters from input-output data. There are at least two reasons for assessing this property. First, the model parameters can have a physical meaning, and it can be interesting to know whether it is possible to determine their values from experimental data. Second, numerical optimization approaches will have difficulties when trying to estimate the parameters of a non-identifiable model. A summary of existing research on structural identifiability analysis shows that in 1970s some techniques were developed from control theories for linear models [START_REF] Bellman | On structural identifiability[END_REF], especially compartmental models. A detailed review and discussion of the different ideas and terminology in the field of linear identifiability can be found in the PhD thesis of Delforge [START_REF] Delforge | Sur l'identifiabilité et l'identification des modèles linéaires[END_REF]. More recently, some methods for testing the structural identifiability of non-linear models have been developed. In [START_REF] Miao | On Identifiability of Nonlinear ODE Models and REFERENCES Applications in Viral Dynamics[END_REF], identifiability analysis methodologies are reviewed for nonlinear ODE models developed in the past couple of decades, including structural identifiability analysis, practical identifiability analysis, and sensitivity-based identifiability analysis. The main drawbacks of these methods are related to the difficulty of assessing the observability condition and the complexity to solve linear inhomogeneous partial differential equations for general non-linear dynamic systems. The more recently developed DAISY software [START_REF] Bellu | DAISY: A new software tool to test global identifiability of biological and physiological systems[END_REF]) enables its application to non-expert users. In line with this approach, the implicit function theorem based method was proposed by Xia and Moog [START_REF] Xia | Identifiability of nonlinear systems with applications to hiv/aids models[END_REF]. It is based on computing the time derivatives of the outputs to eliminate unobserved states and determining a finite number of equations consisting of known inputs/outputs and unknown parameters. These two kinds of methods can be applied to small-scale systems effectively but, when dealing with medium or large-scale systems, the calculations involved become intractable. In this context, the aim of this paper is to propose a new graph-theoretic tool to provide necessary and sufficient conditions that ensure that some desired parameters are identifiable according to the structure of the system and the location of the measurements. Our approach is well-suited to treat large scale systems because it uses classical programming techniques and is free from numerical difficulties. Moreover, the key feature of all of the results presented in this paper is that the global identifiability of structured linear dynamical systems is scrutinizing with unknown inputs. To our knowledge, it is a challenging problem that has received very little attention, the majority of recent studies mainly focus on general non-linear dynamic models without unknown inputs.

To study the identifiability of structured systems, we consider models where the fixed zeros are conserved while the non zero entries are replaced by free parameters to be determined. There is a huge amount of interesting studies in the literature using this kind of models. The latter capture most of the available structural information from physical laws. Their study requires a low computational burden, which allows us to deal with large scale systems. Because of these characteristics, we think that structured systems are particularly well suited to study the identifiability. The pioneering work of Reinschke [START_REF] Reinschke | Structural properties of linear control systems should be investigated by means of graphs[END_REF] showed that graph theoretical tools are useful techniques to analyse basic properties of structured systems. In the context of parameter identifiability, the work of [START_REF] Audoly | On the identifiability of linear compartmental systems: a revisited transfer function approach based on topological properties[END_REF]) considers a directed graph-based approach to deal with the problem of the a priori identifiability of compartmental systems from input-output experiments. The problem of determining whether or not a particular parameter, or the entire compartmental system, is structural identifiable can become extremely difficult if the number of unknown parameters and the number of compartments is large. With the objective to consider large linear compartmental systems, [START_REF] Eisenfeld | New techniques for structural identifiability for large linear and nonlinear compartmental systems[END_REF] and [START_REF] Eisenfeld | Structural identification of large systems by reduction to subsystems: VLDL triglycerides[END_REF] introduce new methods based on some digraph properties and a subsystem decomposition in such a way that a parameter is structural identifiable with respect to the large system if and only if it is structural identifiable with respect to the subsystem in which it is contained. In [START_REF] Eisenfeld | Structural identification of large systems by reduction to subsystems: VLDL triglycerides[END_REF], sufficient conditions are proposed on the digraph of the system, which guarantee that the desired decomposition can be achieved. However, none of these studies can be used to analyse generic parameter identifiability of structured linear systems with unknown inputs. It is the aim of this paper. Compared to existing works, the contribution of the presented approach lies mainly in three points : Firstly, few works deal with the identifiability of systems with unknown inputs, representing disturbances, unmodeled dynamics or faults for example. Secondly, most part of identifiability studies use algebraic or geometric approaches and so require more information than the proposed approach which needs only the knowledge of the structure of the system. Moreover, the use of graph-theoretic approach provides quite efficient and systematic analysis tool. Finally, our approach allows us to address quite easily and immediately the problem of sensors location to ensure the identifiability of a chosen set of parameters. This problem is very interesting from a conception point. The paper is organized with a Section 2 presenting the problem of the generic parameter identifiability for structured linear systems with unknown inputs. In Section 3, some classical definitions and notations in the graph-theory are given and a digraph for any structured linear system is defined. Section 4 presents some general results on the existence of redundancy equations allowing the identification of unknown parameters for systems with unknown inputs. These results allow to reduce the digraph of the system to its useful part. In Section 5, some lemmas are provided which allow us to establish the necessary and sufficient identifiability conditions in Section 6, which represent the main result of the paper. A brief conclusions is given in Section 7. T. Boukhobza, F. Hamelin and C. Simon 2 Problem statement

In this paper, we address numerically non-specified systems on the form:

Σ Λ : ẋ(t) = Ax(t) + Bu(t) y(t) = Cx(t) + Du(t) (1)
where x ∈ R n , u ∈ R q and y ∈ R p are respectively the state vector, the input vector and the output measurement vector. Without loss of generality and for the sake of homogeneity, all the inputs are assumed to be unknown. The control input signals, whose values are known, are considered to be measured i.e. a virtual output equation of the form y k ′ = u k is associated to these inputs.

A, B, C and D represent matrices which elements are either fixed to zero or assumed to be nonzero parameters noted λ i . It is assumed that the entries of all these matrices, constituting vector (λ 1 , λ 2 , . . . , λ h ) T ∈ R h , can take any value in R h or equivalently that parameters λ i are free. If all parameters λ i are numerically fixed, a so-called admissible realization of structured system (Σ Λ ) is obtained. A property is said to be true generically (van der Woude 1999) if it is true for almost all the realizations of structured system (Σ Λ ). Here, "for almost all the realizations" is to be understood [START_REF] Dion | Generic Properties and Control of Linear Structured Systems: a Survey[END_REF][START_REF] Van Der Woude | The Generic Number of Invariant Zeros of a Structured Linear System[END_REF] as "for all parameter values ((λ 1 , λ 2 , . . . , λ h ) T ∈ R h ) except for those in some proper algebraic variety in the parameter space". The proper algebraic variety for which the property is not true is the zero set of some non-trivial polynomial with real coefficients in the h system parameters λ 1 , λ 2 , . . . , λ h or equivalently it is an algebraic variety which has Lebesgue measure zero.

In this paper, we are interested in the generic identifiability of a subset of parameters denoted Θ = {λ i 1 , λ i 2 , . . . , λ i k θ } ⊆ {λ 1 , λ 2 , . . . , λ h } = Λ, which may represent directly or not some physical parameters of the system. The parameters to be identified are some of the entries of matrices A B, C and D. It is assumed also that all the other parameters (Λ \ Θ) are known even if the identifiability analysis does not necessitates their numerical values. Let's recall briefly the definition of the generic parameter identifiability:

Definition 2.1: The unknown parameters of subset Θ of structured system (Σ Λ ) are generically identifiable iff, for almost all realizations of (Σ Λ ), for some initial state x 0 and for input function u(t), y(t, x 0 , u(t), Θ 0 ) = y(t, x 0 , u(t), Θ 1 ) for t ≥ 0 implies Θ 0 = Θ 1 , where y(t, x 0 , u(t), Θ 0 ) (resp. y(t, x 0 , u(t), Θ 1 )) represents the output related to system Σ Λ for the initial conditions x 0 , the input u(t) and the unknown parameter values Θ = Θ 0 (resp. Θ = Θ 1 ).

In other words, the unknown parameters of subset Θ are generically identifiable, if, when the initial state and the input are quite informative, the measured trajectory allows to uniquely determine the values of all the elements of Θ. Therefore, to achieve the parameters identifiability, it is necessary and sufficient to have some algebraic and differential equations linking some outputs , which allow to uniquely determine the exact values of the parameters. Since we deal with linear systems, these equations, called redundancy equations, have obviously the form:

y (ℓ) i = s<ℓ α i,s y (s) i + y l ∈Y\{y i } n s=0 α l,s y (s) l (2)
where each α i,s can lead to an "identification" equation allowing the parameters estimation. The parameters identifiability is achieved if and only if there are sufficiently independent identification equations issued from the redundancy algebraic relations, to express all the unknown parameters.

Note that the aim of the paper is not to find these identification equations neither to propose an identification algorithm but to analyse if yes or no, according to the structure of the system, it can be written sufficiently independent and informative to ensure the unknown parameters identifiability. To establish our result, which consists on graphical necessary and sufficient conditions for the generic identifiability of the parameters belonging to Θ, we proceed with the following steps:

Step 1: a digraph is associated to the considered system. This digraph and different notations are presented in Section 3.

Step 2: the graph is reduced to its useful part for the identifiability. This is done by establishing firstly that in a certain easily computed part of the graph, it is not possible to exhibit algebraic redundancy equations allowing the identification of the parameters (Lemma 4.2), and secondly that in the remaining part there always exists an algebraic relation linking any output to the others (Lemmas 4.3 and 4.4).

Step 3: in the useful part of the graph, using the graphic characterization of the observability subspace dimension (Lemma 4.6), the notion of eligible edge is defined. Then, it is shown that a necessary condition to the parameter identifiability is that the associated edge of the considered parameter is eligible (Lemma 5.1).

Step 4: the redundancy algebraic equations are characterized by defining the pairs of paths ¶ A and of path-cycle ¶ C . Next, it is proven that all the algebraic equations use only the parameters associated to the edges covered by these pairs. According to this fact, Lemma 5.2 provides necessary and sufficient conditions to check if a parameter appears or not in a redundancy equation. Then, this result is extended to a set of k unknown parameters in Lemma 5.3.

Step 5: a new bipartite graph is defined linking the unknown parameters to the pairs of paths and cycles representing the identification equations. Using the DM-decomposition of this bipartite graph, the sufficient (Lemma 5.5) and necessary (Lemma 5.6) condition are established to the generic parameter identifiability.

Step 6: the final and main result is summarized in Proposition 6.1.

3 Graphical representation and some classical definitions

The digraph associated to

(Σ Λ ) is noted G(Σ Λ ). It is constituted by a vertex set V and an edge set E i.e. G(Σ Λ ) = (V, E).
The vertices are associated to the continuous state, the input and the output components of (Σ Λ ) and the directed edges represent links between these variables. More precisely, V = X ∪ Y ∪ U, where X = {x 1 , . . . , x n } is the set of state vertices, Y = y 1 , . . . , y p is the set of output vertices and U = u 1 , . . . , u q is the set of unknown input vertices. The edge set is

E = A-edges ∪ B-edges ∪ C-edges ∪ D-edges, with A-edges = (x j , x i ) | A(i, j) 0 , B-edges = (u j , x i ) | B(i, j) 0 , C-edges = (x j , y i ) | C(i, j) 0 , D-edges = (u j , y i ) | D(i, j) 0 .
Here, M(i, j) is the (i, j) th element of matrix M and (v 1 , v 2 ) denotes a directed edge from vertex v 1 ∈ V to vertex v 2 ∈ V. Each edge is associated to a free non-zero parameter of the system model called the weight of the edge.

Notation : The edges associated to the unknown parameters are represented in dashed lines. The set of these edges is denoted E θ and their number is k θ .

Example 3.1 To the system defined by the following matrices, it is associated the digraph depicted in Figure 1.

A =                   0 0 0 0 0 λ 1 0 λ 2 0 0 0 λ 3 λ 4 0 0 0 0 0 0 0 0 λ 5 λ 6 0 0 0 0 λ 7 0 0 0 0 0 0 0 0                   , B =                   0 0 0 0 0 λ 8                  
, C = λ 9 0 λ 10 0 0 0 0 λ 11 0 λ 12 0 0 , D = 0.For this example, the unknown parameters to be identified are Θ = {λ 1 , λ 2 , λ 7 , λ 10 }. We recall that all the other parameters Λ \ Θ are assumed to be known.

Let's now give some useful definitions and notations which are quite common in the graph-theory. Definition 1: a path is simple when every vertex occurs only once in this path. The weight of a path is the product of the weight of all the edges constituting this path.

Definition 2: a cycle is a path of the form

v s 0 → v s 1 → . . . → v s i → v s 0 , where v s 0 , v s 1 , . . . , v s i are distinct.
Definition 3: a path is a Y-topped path if its end vertex belongs to Y.

In the sequel, V 1 and V 2 represent two subsets of V. It is denoted by card(V 1 ) the cardinality of V 1 Figure 1. The digraph associated to the system of Example 3.1 and V 1 \ V 2 is the set of elements in V 1 which are not in V 2 . Definition 4: a path is a V 1 -rooted path if its begin vertex belongs to V 1 .
Definition 5: denote by pred(V 1 ) the set of all the predecessors of the vertices included in

V 1 . Definition 6: a path p = v s 0 → v s 1 → . . . → v s i is said a V 1 -V 2 path if v s 0 ∈ V 1 and v s i ∈ V 2 . Moreover, if the only vertex of p which belongs to V 1 is v s 0 and the only vertex of p which belongs to V 2 is v s i , p is called a direct V 1 -V 2 path.
Definition 7: some paths are disjoint if they have no common vertex.

ρ V 1 , V 2 is the maximal number of disjoint V 1 -V 2 paths. Moreover, a set of ρ V 1 , V 2 disjoint V 1 -V 2 paths is called maximal V 1 -V 2 linking. Definition 8: µ V 1 , V 2 denotes the minimal number of vertices of U ∪ X ∪ Y belonging to a maximal V 1 -V 2 linking. Definition 9: V ess V 1 , V 2 is the vertex subset including the vertices present in all the maximal V 1 -V 2 linkings.
Definition 10: there exists a unique vertex subset noted S o V 1 , V 2 , called minimum output separator, which is the set of begin vertices of all direct V ess V 1 , V 2 -V 2 paths. Example 3.1, continued: For the considered system, it can be seen that ρ U, Y = 1,

V ess U, Y = {u 1 , x 6 }, S o U, Y = {x 6 }.
In order to express more easily the graphical necessary and sufficient conditions ensuring the parameters identifiability, a second kind of graphs called bipartite graphs will be used. Hereafter, some recalls are given on this kind of graphs and particularly on the so-called Dulmage-Mendelsohn decomposition. Consider any bipartite digraph noted B defined by the triplet (V + , V -, W), where V + and V -are two vertex subsets and W the set of edges linking theses two vertex subsets. Let's recall some elements related to the subdivision of such bipartite digraph into strongly connected components using the Dulmage-Mendelsohn (DM) decomposition [START_REF] Dulmage | Coverings of Bipartite Graphs[END_REF]Mendelsohn 1958, Murota 1987): A matching in bipartite graph B is an edge set M ⊆ W such that all the edges of M are disjoint (have no common vertex). A matching is maximal if it has a maximal cardinality. It can be associated to each maximal matching M a non bipartite digraph noted

B M = (V + , V -, W M ) where (v 1 , v 2 ) ∈ W M ⇔ (v 1 , v 2 ) ∈ W or (v 2 , v 1 ) ∈ M. The set of vertices in V + (resp. in V -) covered by the edges of M is denoted by ∂ + M (resp. ∂ -M). It is noted S + 0 = V + \ ∂ + M and S - 0 = V -\ ∂ -M.
In B M , two vertices v i and v j are said to be strongly connected if it exists in B M a path from v i to v j and a path from v j to v i . The relation "is strongly connected to" is an equivalence relation and its equivalence classes can be defined. Each equivalent class is called a strongly connected component [START_REF] Murota | System Analysis by Graphs and Matroids[END_REF]. Any bipartite digraph B can be decomposed uniquely into a certain number (defined here as ν + 2) of partially ordered irreducible components denoted

C i (B) = (V + i (B), V - i (B), W i (B)
), i = 0, 1, . . . , ν, ∞, using DM-decomposition described below to make the paper self-contained:

Find a maximal matching M in B,

Let V + 0 (B) = S + 0 ∪ {v ∈ V + , | ∃ a path in B M from S + 0 to v} V - 0 (B) = {v ∈ V -, | ∃ a path in B M from S + 0 to v}. W 0 (B) de f = {edges linking V + 0 (B) to V - 0 (B)}. Let V + ∞ (B) = {v ∈ V + , | ∃ a path in B M from v to S - 0 } V - ∞ (B) = S - 0 ∪ {v ∈ V -, | ∃ a path in B M from v to S - 0 }. W ∞ (B) de f = {edges linking V + ∞ (B) to V - ∞ (B)}. For i = 1, . . . , ν, let C i (B)
be the strongly connected component of the graph obtained from B M after deleting the vertices and the edges of C 0 (B) and C ∞ (B).

A partial order relation is defined on the strongly connected components, denoted " " as follows: C i (B) C j (B) ⇔ there exists a path starting from the vertices of C j (B) to the ones of

C i (B) in B M .
It is important to note that the obtained subsets V + i (B) and V - i (B) , for i = 0, 1, . . . , ν, ∞, are the same whatever the choice of the maximal matching M is [START_REF] Dulmage | Coverings of Bipartite Graphs[END_REF]Mendelsohn 1958, Murota 1987).

C 0 (B) is called the minimal inconsistent part of B and C ∞ (B) is the maximal inconsistent part of B.
The union of all the strongly components C i (B), i = 1, . . . , ν is called the consistent part of B.

Preliminaries and specific definitions

The identifiability of a set of parameters depends on the existence of some algebraic relations linking the output and their derivatives and, which are sensitive to these parameters. Therefore, it is important to characterize the existence and the number of algebraic relations linking the different output components and their derivatives. Knowing that the identifiability of the parameters depends on the existence of enough redundancy output equations sensitive to the unknown parameters, the method follows three main steps :

Step 1: A reduction of the digraph by the elimination of the part where there is no redundancy equations. This gives also a necessary identifiability condition

Step 2: A graphical characterization of the redundancy equations sensitive to the unknown parameters.

Step 3: A graphical test to know if the existing redundancy output equations allows the identifiability of all the unknown parameters. Almost all the technical aspects of method turn around the graphical characterization of the existence and the independence of output redundancy equations. And this is strongly linked to the observability subspaces dimensions and so the existence and the length of some particular paths and cycles in the digraph associated to the system. The existence of an algebraic equation linking some output components is equivalent to the fact that two generated observability subspaces are not disjoint, which can be characterized by some dimension calculations. Our aim, hereafter, is to characterize the generic dimension of the observability subspace of the system or more exactly of the part of the system where it is possible to write redundancy output equations useful for the identification. To do so, the system is first subdivided into two parts from the observability point of view: the first one is the maximal over-determined part and the second one is related to the square part and the under-determined part. The parameters identifiability can be achieved only in the over-determined part. This subdivision is provided in (van der Woude 1999) and is equivalent to the DM-decomposition when representing the system by a bipartite digraph. Definition 4.1: [START_REF] Boukhobza | State and Input Observability for Structured Linear Systems: a Graph-Theoretic Approach[END_REF] In digraph G(Σ Λ ), it can be defined:

• X 1 de f = x i | ρ U ∪ {x i }, Y > ρ U, Y ; • Y 0 de f = Y ∩ V ess U, Y ; • Y 1 de f = Y \ Y 0 ; • U 0 de f = u i | there is no edge from u i to X 1 ∪ Y 1 }; • U 1 de f = U \ U 0 ; • X s de f = S o U 0 , Y ∩ X; • X 0 de f = X \ X 1 ∪ X s .
The aim of this decomposition is to simplify the digraph of the system and to reduce it to its useful part for the identifiability study. This decomposition is also used the observability context (van der Woude 1999, [START_REF] Boukhobza | State and Input Observability for Structured Linear Systems: a Graph-Theoretic Approach[END_REF][START_REF] Boukhobza | Discrete mode observability of structured switching descriptor linear systems: A graph-theoretic approach[END_REF]. Mainly, due to the presence of unknown inputs in the systems, from the observability point of view, any system can be divided into three parts: under-determined part, exactly-determined part and over-determined part. The two first parts are here regrouped to form the subsystem (Σ 0 ). The over-determined part of the system constitutes the subsystem (Σ 1 ). The only part containing redundancy output equations leading to the identification of unknown parameters are the over-determined part. This is why, only this part is kept and the study can be reduced to (Σ 1 ) the over-determined part and the rest of the digraph is removed from the study. Moreover, if an unknown parameter appears in the under-determined part or in the exactly determined part of the system, then it won't be identifiable. More precisely, the decomposition leads to two subsystems: Subsystem (Σ 1 ) which has as input U 1 ∪X s , state X 1 and output Y 1 . This subsystem represents, from the observability point of view, the over-determined part of the system. Indeed, it is proven in [START_REF] Boukhobza | State and Input Observability for Structured Linear Systems: a Graph-Theoretic Approach[END_REF][START_REF] Van Der Woude | The Generic Number of Invariant Zeros of a Structured Linear System[END_REF]) that this part remains left invertible even if any one of its measurements is removed. This is due to the fact that, by definition, no output vertex is essential in an input-output linking and all the state vertices constituting this subsystem can reach an output vertex independently from the input-output paths. It has necessarily more outputs (measurements) than inputs.

Subsystem (Σ 0 ) which has as input U 0 , state X 0 ∪ X s and output Y 0 . This subsystem represents the square and under-determined parts of the system. In fact, if it is denote by X 0 , X s , X 1 , U 0 , U 1 , Y 0 and Y 1 the state, the unknown input and the output associated to vertex subsets X 0 , X s , X 1 , U 0 , U 1 , Y 0 and Y 1 respectively, system (Σ Λ ) can be written as given in [START_REF] Boukhobza | State and Input Observability for Structured Linear Systems: a Graph-Theoretic Approach[END_REF]):

               Ẋ0 = A 0,0 X 0 + A 0,s X s + A 0,1 X 1 + B 0,0 U 0 + B 0,1 U 1 Ẋs = A s,0 X 0 + A s,s X s + A s,1 X 1 + B s,0 U 0 + B s,1 U 1 Ẋ1 = A 1,s X s + A 1,1 X 1 + B 1,1 U 1 Y 0 = C 0,0 X 0 + C 0,s X s + C 0,1 X 1 + D 0,0 U 0 + D 0,1 U 1 Y 1 = C 1,s X s + C 1,1 X 1 + D 1,1 U 1 (3)
The proposed subdivision of the system into two subsystems is summarized in Figure 2. As it can be seen through equations (3), X 0 and U 0 does not intervene on the dynamics of X 1 and neither on the output Y 1 . Thus, system (Σ 1 ) can be seen as having U 1 and X s as input vectors, X 1 as state vector and Y 1 as output vector. This system is over-determined and has more outputs than inputs [START_REF] Boukhobza | State and Input Observability Recovering by Additional Sensor Implementation: a Graph-Theoretic Approach[END_REF]. System (Σ 0 ), has more inputs than outputs and is under-determined. It can be considered that this system interacts with subsystem (Σ 1 ) as U 1 and X 1 can be present in the dynamics of X 0 and X s as well in the output equation Y 0 .

1 = {x 1 , x 2 , x 3 , x 4 , x 5 }, X 0 = ∅, Y 0 = ∅, Y 1 = {y 1 , y 2 }, U 0 = {u 1 }, U 1 = ∅ and X s = {x 6 }.
Remark: When all the inputs are known, or equivalently measured, then subsystem (Σ 0 ) contains only the state vertices which are not connected to the measurements. Some important results proven in [START_REF] Boukhobza | Partial state and input observability recovering by additional sensor implementation: a Graph-Theoretic Approach[END_REF]Hamelin 2009, 2011) are summarized in the following lemmas:

Lemma 4.2: There cannot exist a relation linking only the output components of square subsystem (Σ 0 ). Proof: See Appendix A. Using this lemma result, the studied graph can be reduced to keep only its useful part i.e. only the vertices related to subsystem (Σ 1 ): U 1 ∪X s ∪X 1 ∪Y 1 and the edges linking these vertices. Note that the elimination of subsystem (Σ 0 ) does not correspond to the elimination of a subsystem, where there is no unknown parameter to identify. Indeed, if there are some parameters to identify related to some edges in (Σ 0 ), then these parameters are not identifiable and it can be concluded that the considered subset of parameters is not identifiable. Therefore, from now, only the over-determined part is considered i.e. in the sequel, our study is reduced only to the part (Σ 1 ). Example 3.1, continued: For the system of Example 3.1, the reduced useful digraph is depicted in Figure 3. Definition 4.5: Consider structured linear system (Σ Λ ) associated to digraph G(Σ Λ ). The positive number β 1 is defined as the maximal number of vertices of X 1 ∪ U 1 ∪ X s covered by a disjoint union of:

• a U 1 ∪ X s → Y 1 linking of maximal size;

• Y 1 -topped paths;

• cycles covering only the elements of X 1 .

Lemma 4.6: Consider structured linear system (Σ Λ ) represented by digraph G(Σ Λ ), the number β 1 is equal to the generic dimension of the observable subspace of the over-determined part (Σ 1 ) of the system in the extended state and input space.

Proof: This lemma has been proved in [START_REF] Boukhobza | Partial state and input observability recovering by additional sensor implementation: a Graph-Theoretic Approach[END_REF]). To achieve the parameter identifiability analysis, it is necessary to have enough independent output algebraic relations linking some outputs and their derivatives, which are sensitive to the parameters to be identified. When several output components appear in this equation, it means that for some order k i , y (k i ) i can be written as a linear combination of y (k) i , k < k i , and of other output components with their derivatives. In this case, the intersection of observability subspace generated by y i and the other components is not empty. This can be characterized by the generic dimension of such subspaces.

Definition 11: for each output y i ∈ Y 1 ,

∆ i = {x i ∈ X 1 , such that x i is covered by a direct S o U 1 ∪ X s , Y 1 \ {y i } → Y 1 \ {y i } path }
Definition 12: integer β 1, ī is the sum of :

• µ U 1 ∪ X s , S o U 1 ∪ X s , Y 1 \ {y i } • the maximal number of vertices of ∆ i ∪ S o U 1 ∪ X s , Y 1 \ {y i } covered by a disjoint union of: ⋄ a S o U 1 ∪ X s , Y 1 \ {y i } } -Y 1 \ {y i } linking of maximal size; ⋄ Y 1 \ {y i }-topped paths;
⋄ cycles covering only the elements of ∆ i . Definition 13: d(y i ) = β 1β 1, ī. β 1, ī represents the dimension of the observability subspace of subsystem (Σ 1 ) when removing the output y i [START_REF] Boukhobza | Partial state and input observability recovering by additional sensor implementation: a Graph-Theoretic Approach[END_REF]. Obviously, for all k > d(y i ), y (k) i can be written as a linear combination of y ( j) i , with j ≤ d(y i ), and other output components with their derivatives.

Definition 14: a path p is said eligible if it covers only the vertices included in U 1 ∪ X s ∪ X 1 ∪ Y 1 and if it verifies one of the following conditions:

• p is a simple U 1 ∪ X s -Y 1 path.

• p is a Y-topped path and its length is strictly greater than d(y i ), where y i is its end vertex.

• p is a cycle covering only vertices in X 1 . Definition 15: an edge is eligible if it belongs to an eligible path.

Γ c = {x i ∈ X 1 , | x i
is covered by a cycle} Definition 17: in the set of eligible Γ d -Γ d direct and simple paths, relation R 1 is defined as follows : p 1 R 1 p 2 if p 1 and p 2 are two paths having the same begin and end vertices and the same length.

Definition 18: ¶ A is the set of pairs of eligible Γ d -Γ d direct and simple paths {p 1 , p 2 } such that p 1✓ R 1 p 2 . In ¶ A , relation R p is defined as follows : {p 1 , p 2 }R p {p 3 , p 4 } if one of these two conditions holds:

•

p 1 R 1 p 3 and p 2 R 1 p 4 • p 1 R 1 p 4 and p 2 R 1 p 3 Definition 19: ¶ C is the set of pairs of paths {C 1 , p ′ 1 } such that: • C 1 is a cycle covering elements of Γ c , • p ′ 1 is a simple direct Γ c -Γ d path
Γ c = {x 2 , x 4 , x 5 }. Furthermore, it can be seen that x 6 → x 1 → y 1✓ R 1 x 6 → x 1 → x 3 → y 1 , x 6 → x 2 → y 2✓ R 1 x 6 → x 1 → x 3 → y 1 and x 6 → x 1 → y 1✓ R 1 x 6 → x 2 → y 2 . For relation R p , three equivalent classes have to be considered. The first class includes {x 6 → x 1 → y 1 , x 6 → x 1 → x 3 → y 1 }, the second one includes {x 6 → x 1 → y 1 , x 6 → x 2 → y 2 } and the last one includes {x 6 → x 2 → y 2 , x 6 → x 1 → x 3 → y 1 }. Moreover, {x 2 → x 2 , x 2 → y 2 }R c {x 4 → x 4 , x 4 → y 2 } and {x 2 → x 2 , x 2 → y 2 } ✓ R c {x 4 → x 5 → x 4 , x 4 → y 2 }.
Lemma 5.2: Let's consider structured linear system (Σ Λ ) represented by graph G(Σ Λ ). An unknown parameter corresponding to an edge e ∈ E θ belongs to a redundancy algebraic equation iff it is covered by a path belonging to a pair of ¶ A or by a cycle belonging to a pair of ¶ C .

Proof: The proof is provided in Appendix D. The following identifiability necessary conditions can be stated: Lemma 5.3: Let's consider structured linear system (Σ Λ ) represented by digraph G ( Σ Λ ). k unknown parameters corresponding respectively to k edges belonging to E θ are structurally identifiable only if they are covered by paths belonging to pairs of ¶ A or by cycles belonging to pairs of ¶ C , where all these pairs belong to k distinct equivalence classes w.r.t. relations R p and R c .

Proof: The proof is provided in Appendix E. It is defined now the bipartite digraph linking the parameters to the paths which allows to write the identifiability equations: Definition 5.4: Considering edge subset E θ , which corresponds to the unknown parameters and a union of pairs

F = {p 1,1 , p 1,2 }, {p 2,1 , p 2,2 }, . . . , {p k,1 , p k,2 }, {c 1 , p ′ 1 }, {c 2 , p ′ 2 }, . . . , {c ℓ , p ′ ℓ }
, a bipartite digraph B I (F ) called "identifiability bipartite digraph related to F "can be defined , such that:

B I (F ) = (V + , V -, W), where V + = Θ, V -= F and W = (λ j , {p i,1 , p i,2 }), if the edge associated to λ j is covered by a path p j,1 or p j,2 of a pair {p j,1 , p j,2 } ∈ [{p i,1 , p i,2 }] R p ∪ (e j , {c i , p ′ i }), if the edge associated to λ j is covered by a cycle c j of a pair {c j , p ′ j } ∈ [{c i , p ′ i }] R c .
The two following lemmas establish the necessary and sufficient identifiability conditions using the bipartite graph defined above.

Lemma 5.5: Let's consider a union of pairs F ⊆ ¶ A ∪ ¶ C , where all the pairs belong to distinct equivalence classes w.r.t. relations R p and R c . If all the parameters associated to elements of E θ are covered in B I (F ) by an exactly determined DM-component of cardinality equal to one, then they are structurally identifiable, assuming that all the other parameters of the model are known.

Proof: The Proof is provided in Appendix F. Lemma 5.6: All the parameters associated to E θ are structurally identifiable, assuming that all the other parameters of the model are known, only if there exists a union of pairs F ⊆ ¶ A ∪ ¶ C belonging to distinct equivalence classes w.r.t. relations R p and R c , such that each element of E θ is covered in B I (F ) by an exactly determined DM-component of cardinality equal to one.

Proof: The Proof is provided in Appendix G.

6 Main result : parameter identifiability characterisation Using the previous definitions and results, it can enounced now the main result of the paper characterizing exactly the parameters identifiability: Proposition 6.1: Let's consider structured linear system (Σ Λ ) represented by graph G ( Σ Λ ). The unknown parameters corresponding to the edge subset E θ are structurally identifiable, assuming that all the other parameters of the model are known, iff there exists a family

F = {p 1,1 , p 1,2 }, {p 2,1 , p 2,2 }, . . . , {p k,1 , p k,2 }, {c 1 , p ′ 1 }, {c 2 , p ′ 2 }, . . . , {c ℓ , p ′ ℓ } of pairs included in ¶ A ∪ ¶ C such that:
-All the edges of E θ are covered by paths p i, j , i = 1, . . . , k, j = 1, 2 or by cycles c r , r = 1, . . . , ℓ, -All the pairs {p i,1 , p i,2 }, i = 1, . . . , k, belong to distinct equivalent classes w.r.t. R p , -All the pairs {c r , p ′ r }, r = 1, . . . , ℓ, belong to distinct equivalent classes w.r.t. R c , -All the D-M components of the identifiability bipartite digraph associated to F are in the exactly determined part and each of them contains exactly one element of Θ (the vertex set associated to the unknown parameters).

Proof: Sufficiency: According to lemma 5.5, the existence of family F satisfying conditions of Proposition 6.1, which are similar to the conditions of Lemma 5.5, and covering all the edges corresponding to unknown parameters, is sufficient to establish the identifiability of all the unknown parameters. Necessity: The necessity is immediate according to Lemma 5.6. △ Example 3.1, continued: For the system of Example 3.1, four parameters have to be identified {λ 1 , λ 2 , λ 7 , λ 10 }. Let's take the following notations for the paths and cycles:

p 1 = x 6 → x 2 → y 2 , p 2 = x 6 → x 1 → x 3 → y 1 , p 3 = x 6 → x 1 → y 1 , c 1 = x 2 → x 2 , c 2 = x 4 → x 5 → x 4 , p ′ 1 = x 2 → y 2 and p ′ 2 = x 4 → y 2 . All the elements of family F = {p 1 , p 3 }, {p 2 , p 3 }, {c 1 , p ′ 1 }, {c 2 , p ′ 2 }
belong to distinct equivalent classes w.r.t. R p and R c . Moreover, each of the unknown parameters is covered by at least one path p 1 or p 2 or one cycle c 1 or c 2 . Figure 5 depicts identifiability bipartite digraph associated to F . It can be seen that all the DM-components contain only one element because edge (λ 1 , {p 2 , p 3 }) does not belong to any maximal matching in this bipartite digraph. Therefore, the four parameters are generically identifiable. Indeed, when writing the redundancy algebraic equation linking y 1 and their derivatives to y 2 , when the equation is normalized in order to obtain the coefficient multiplying y (6) 2 equal to one, it can be seen that the coefficient multiplying y (6) 1 depends on known parameters and λ 1 that allows to identify λ 1 ; the coefficient multiplying y (5) 1 depends on known parameters, λ 1 and λ 10 that allows to identify λ 10 ; the coefficient multiplying y (5) 2 depends on known parameters, λ 2 and λ 10 that allows to identify λ 2 ; finally, the coefficient multiplying y (4) 2 depends on λ 2 , λ 7 and λ 10 that allows to identify λ 7 . Note that, if λ 9 was unknown, λ 1 and λ 10 won't be identifiable since they would belong to the same DM-component. In this case, to recover the identifiability of these parameters, a measure has to be added on x 6 , x 1 or x 3 .

Conclusion

In this paper, a graph-theoretic tool is proposed to analyse generic parameter identifiability for structured linear systems with unknown inputs. More precisely, new necessary and sufficient conditions are provided that ensure that the redundancy equations generated by the output measurements allow the parameter identifiability. Obviously, in this structural study, the different constraints on the inputs and initial conditions are not considered. It is just assumed that they are sufficiently informative and can take any desired values which allow the practical identification of the parameters. Our approach uses classical programming techniques and is free from numerical difficulties. This makes our proposed method well-suited to treat large scale systems. In future works, the graph-theoretic approach can be used when the proposed identifiability conditions are not satisfied, to determine the location of additional sensors in order to recover them. relation (D5) by e j , it comes:

Ci A k e j = s<d(y i ) α i,s Ci A s + l|y l ∈ Ỹ n 1 s=0 α l,s Cl Ãs e j (D6)
where each non-zero component of Cl Ãs is associated to the paths arriving to y l ∈ Ỹ of length s + 1. Since all the {x j }-Ỹ ∪ {y i } paths starting from x j cover by definition S o {x j }, Ỹ ∪ {y i } denoted in the sequel x r , then there exist k r and k ′ such that k r + k ′ = k and Ci Ãk e j = Ci Ãk r ∆ r Ãk ′ e j where ∆ r is a diagonal matrix having only one non-zero element ∆ r (r, r) = 1. The same reasoning can be done for each term Cl Ãs e j and so there exist s r and s ′ such that s r + s ′ = s and Cl Ãs e j = Cl Ãs r ∆ r Ãs ′ e j . The fact that e belongs to a S o v P , Ỹ ∪ {y i } -Ỹ ∪ {y i } path means that edge e appears in only some of S o v P , Ỹ ∪ {y i } -Ỹ ∪ {y i } paths. Thus, some terms Ci Ãk r and Cl Ãs r , but not all of them, contain the nonzero parameter λ e corresponding to edge e. Denoting by C r = e T r , where e r is the r th Euclidean vector, we have that Ci Ãk e j = Ci Ãk r ∆ r Ãk ′ e j = α ′ i,k C r Ãk ′ e j and Cl Ãs e j = Cl Ãs r ∆ r Ãs ′ e j = α ′ l,s C r Ãs ′ e j , where

α ′ l,s de f = ( Cl Ãs r ∆ r )(C r C T r ) -1 = Cl Ãs r ∆ r .
Thus, after substitution of the previous terms in relation (D6), it comes:

α ′ i,k C r A k ′ e j = s r ≤s<d(y i ) α ′ i,s α i,s C r A s-s r + l | y l ∈ Ỹ n 1 s=s r α ′ l,s α l,s C r Ãs-s r e j (D7)
where some, but not all coefficients α ′ i,k , α ′ i,s and α ′ l,s depend on λ e . This weight cannot be factorized and simplified because all the coefficients do not depend on it (some S o v P , Ỹ ∪ {y i } -Ỹ ∪ {y i } paths do not contain edge e). Therefore, (D7) is valid only if some of the coefficients α ′ i,k , α i,s and α l,s depend also on the weight λ e of e. Thus, by means of equation (D4) containing coefficients α i,s and α l,s , an output algebraic relation depending on λ e is obtained. Necessity: Firstly, when edge e is not covered by an eligible cycle or by a U 1 ∪ X s -Y 1 path, it has been shown in Lemma 5.1 that it is not possible to obtain an output algebraic relation achieving the parameter identifiability from the characteristic equation of any matrix à in (D1) whatever Y u is. Moreover, when e is not covered by an eligible cycle or by a U 1 ∪ X s -Y 1 path, for any possible choice of Y u , ϕ y (Y u , Ẏu , . . . , Y (ν) u ) and ϕ x (Y u , Ẏu , . . . , Y (ν) u ) do not depend on the specific parameter associated to e. Furthermore, any output relation can be put on the form of (D4) for some integer k, output component y i and a set of output components Ỹ, which does not include y i and are disjoint from Y u . Thus, the only way to have an identification of unknown parameter λ e is that there exists at least one coefficient α i,s or α l,s of (D4) depending on λ e . Without loss of generality, it can be assumed that Ỹ is minimal and so that in the output algebraic relations all the components of Ỹ appear. If it is not the case, they are removed from Ỹ. Relation (D4) implies that the observable subspace obtained using outputs {y i } ∪ Y u and the one generated by Ỹ ∪ Y u have non zero intersection. Defining k i as the difference between the dimension of the observability subspace when considering as outputs Ỹ ∪ {y i } ∪ Y u and the dimension of the observability subspace considering as outputs Ỹ ∪ Y u ). Obviously, k i ≥ d(y i , relation (D4) cannot be satisfied for some k ≤ k i -1. Thus, in output algebraic relation (D4), k ≥ k i . Furthermore, as Ỹ is minimal, it is not possible to express y (k i ) i using only a part of Ỹ. To guarantee identifiability of λ e , there must exist at least one y i -topped path p, of length greater or equal to k i + 1 and so of length strictly greater than d(y i ), associated to this relation which covers λ e . Let's denote by x j the begin vertex of p (it cannot be a U 1 ∪ X s -Y 1 path when the Lemma is not satisfied) and e j the j th Euclidean vector. When e is not covered by an eligible U 1 ∪ X s -Y 1 path, in Equation (D4), υ(Y u , Ẏu , . . . , Y (n) u ) does not depend on λ e . Then, (D4) can be rewritten as relation (D6) i.e.

Ci A k e j = s<d(y i ) α i,s Ci A s + y l ∈ Ỹ n 1 s=0 α l,s Cl Ãs e j (D8)
where Cl Ãs is associated to y l -topped paths and y l ∈ Ỹ is of length s + 1. All the {x j }-Ỹ ∪ {y i } paths cover

x r = S o x j , Ỹ ∪ {y i } . So, if e is not covered by a path belonging to a pair of ¶ A or by a cycle belonging to a pair of ¶ C , then it is neither covered by a cycle, nor by a U 1 ∪ X s -Y 1 path nor by a S o {v p }, Y 1 -y i path. Then, the paths starting from x r to Y do not contain e. Thus, all the redundancy equations can be written similarly to (D7):

α ′ C r A k ′ e j = s r ≤s<d(y i ) α ′ i,s α i,s C r A s-s r + l | y l ∈ Ỹ n 1 s=s r α ′ l,s α l,s C r Ãs-s r e j (D9)
where α ′ and α ′ l,s do not depend on λ e . Equation (D9) implies that there exists an output algebraic relation with the use of only virtual output C r x in addition to Y u . This relation can be due to the characteristic equation of matrix A, which includes only the terms related to cycles in the digraph. When e does not belong to an eligible cycle, also all α ′ and α ′ l,s do not depend on λ e and it is also the case for coefficients α i,s and α l,s in equation (D4). So, all the existing relations of the form (D4) do not contain λ e . The same reasoning can be done for all Y u ⊆ Y 1 s.t. ρ U 1 ∪ X s , Y u = card(U 1 ∪ X s ) and so λ e cannot be identified. △ Appendix E: Proof of Lemma 4.6

According to Lemma 5.2, k unknown parameters corresponding respectively to k edges belonging to E θ are structurally identifiable only if they are all covered by paths belonging to pairs of ¶ A or by a cycle belonging to a pair of ¶ C . Therefore, to prove Lemma 5.3, it has to be shown that two parameters are structurally identifiable only if the associated edges are covered by two paths, parts of elements of ¶ A ∪ ¶ C belonging to distinct equivalence classes w.r.t. relations R p and R c . Assume that it is not the case i.e. there are two parameters λ r 1 and λ r 2 associated to two edges e 1 and e 2 , which are covered by two elements of ¶ A ∪ ¶ C belonging to the same equivalence classes w.r.t. relations R p or R c . There are four possibilities to this fact: e 1 and e 2 are covered by elements of ¶ A belonging to the same equivalent class w.r.t. relation R p and these two edges can be covered by the same Γ d -Γ d direct path or equivalently by the same Γ d -Y path. Let's denote x j the begin and y i the end vertices of this Γ d -Y path. In this case, redundancy equation (D4) where y i intervenes can also be written on the form (D6) where the only term depending on λ r 1 and λ r 2 is Ci A k e j . However, since e 1 and e 2 are covered by the same path, then Cl Ãs depends on the product λ r 1 λ r 2 . Thus, the redundancy equation may allow the identifiability of the product λ r 1 λ r 2 but not of λ r 1 and λ r 2 separately.

e 1 and e 2 are covered by elements of ¶ A belonging to the same equivalent class w.r.t. relation R p and these two edges can be covered by two different Γ d -Γ d direct paths having the same begin and end vertices or equivalently by two different Γ d -Y paths having the same begin and end vertices. Let's denote x j the begin and y i the end vertices of this Γ d -Y path. In this case, redundancy equation (D4) where y i intervenes can also be written on the form (D6) where the only term on the form Cl Ãs depending on λ r 1 and λ r 2 is Ci A k e j because e 1 and e 2 are covered by two paths of same length. More precisely, Cl Ãs depends on a combination of λ r 1 and λ r 2 . Thus, the redundancy equation may allow the identifiability of this combination but not of λ r 1 and λ r 2 separately.

e 1 and e 2 are covered by elements of ¶ C belonging to the same equivalent class w.r.t. relation R c and these two edges can be covered by the same cycle noted C. In this case, the redundancy algebraic equation, where λ r 1 and λ r 2 appear, is issued from the polynomial characteristic of matrix à (D1). From [START_REF] Reinschke | Multivariable Control. A Graph Theoretic Approach[END_REF]) (Theorem 21.1), the characteristic equation of matrix à has the form Ãn 1 + . . . + a k Ãk + . . . + a 1 à + a 0 Ã0 = 0, where n 1 = card(X 1 ), coefficients a k = c i ,| c i is a loop covering k vertices (-1) n k weight(c i ) and From Lemma 5.2, only edges covered by eligible Γ d -rooted paths or eligible cycles can lead to redundancy equations. Thus, a parameter which is associated to an edge not covered by such paths is not identifiable. Moreover, from Lemma 5.3, the k θ unknown parameters are identifiable only if they are covered by k θ paths and cycles belonging respectively to pairs of ¶ A and to pairs of ¶ C and where all these pairs belong to k θ distinct equivalence classes w.r.t. relations R p and R c . This implies that the parameters are identifiable only if there exists a maximal matching of size k θ in B I (F ), where F denotes such union of k θ pairs, and then there is no under-determined or over-determined DM-component in this bipartite digraph.

Assume that there exists in such bipartite digraph a DM-component of cardinality strictly greater than one. In this case, at least two redundancy algebraic equations depend at least on two unknown parameters. Let's denote these two parameters λ r 1 and λ r 2 . An equation issued from an element of ¶ A or ¶ C depending on these two parameters means that an identifiability equation depends on the product λ r 1 λ r 2 or on one of ratios λ r 1 λ r 2 or λ r 2 λ r 1 (which are equivalent). Then, three cases have to be considered for these equations:

1. The two equations depend on the product λ r 1 λ r 2 . In this case, neither λ r 1 nor λ r 2 are identifiable.

2. The same conclusion is drawn when the two equations depend on the ratios λ r 1 λ r 2 or λ r 2 λ r 1 .

3. One equation depends on the product λ r 1 λ r 2 and the other on the ratio λ r 1 λ r 2 . In this case, the parameters are identifiable. However, the first equation means that edges e 1 and e 2 associated respectively to λ r 1 and λ r 2 belong to cycle part c 1 of an element of ¶ C and the second implies that these two edges belong to two direct paths p 1 and p 2 constituting the elements of ¶ A . In this case, there exists necessarily a vertex v 1 in Γ d covered by cycle c 1 such that a pair (p ′ 1 , p ′ 2 ) ∈ ¶ A covers only λ r 1 if e 1 is after e 2 in c 1 or λ r 2 if e 2 is after e 1 in c 1 . Thus, in F , pair (p 1 , p 2 ) can be substitued by (p ′ 1 , p ′ 2 ) and we obtain in the bipartite digraph associated to this disjoint union that e 1 and e 2 belong to two distinct DM-components. The same reasoning can be done for all the DM-components containing more than one element. Thus, if the parameters are identifiable then there always exists a union of pairs F ⊆ ¶ A ∪ ¶ C , where all the pairs belong to distinct equivalence classes w.r.t. relations R p and R c , such that elements of E θ are each covered in B I (F ) by an exactly determined DM-component of cardinality equal to one and the lemma follows. △

Figure 2 .

 2 Figure 2. System subdivision for parameters identifiability

Figure 3 .

 3 Figure 3. The reduced useful digraph for Example 1

  Example 3.1, continued: For the system of Example 1 reduced to its over-determined part, β 1 ({y 1 , y 2 }) = 6 and as β 1, ī = β 1, ī = 2, then d({y 1 }) = d({y 2 }) = 4. The eligible paths are then all the {u 1 }-Y simple paths and all the cycles covering x 1 , x 2 , x 3 , x 4 and x 5 . The eligible edges of the system of Example 3.1 are depicted in Figure 4.

Figure 4 .

 4 Figure 4. Eligible edges for Example 1

Figure 5 .

 5 Figure 5. Identifiability bipartite digraph associated to F for Example 1

  , and • C 1 and p ′ 1 have the same begin vertex. In ¶ C , relation R c is defined as follows : {C 1 , p ′ 1 }R c {C 2 , p ′ 2 } if C 1 and C 2 have the same length and p ′ For this example, Γ d = {x 6 } and

	and p ′ 2 have the same end-vertex.	1
	Example 3.1, continued:

A loop is a collection of disjoint cycles

Appendix A: Proof of Lemma 4.2

Using results shown in (van der Woude 1999) (Theorem 5.1) concerning the case of square systems, the generic number of invariant zeros of the pencil matrix of system (Σ 0 ) is equal to card(X 0 ) + card(X s ) + card(U 0 )µ U 0 , X s ∪ Y 0ρ U 0 , X s ∪ Y 0 + card(X s ) . Thus, the dimension of the strongly observable subspace and so the number of possible independent observation equations is equal to µ U 0 , X s ∪ Y 0ρ U 0 , X s ∪ Y 0 . Moreover, the cardinality of U 0 ∪ X 0 representing the unknown variables for this system, is at least equal to µ U 0 , X s ∪ Y 0ρ U 0 , X s ∪ Y 0 because all the linkings between U 0 and X s ∪ Y 0 cover the vertices of U 0 ∪ X 0 . Since, (Σ 0 ) cannot partitioned in smaller independent rectangular and square subsystems, in the best case, the number of independent observation equations is equal to the number of unknown variables. Thus, unknown variables cannot be eliminated from any equations to obtain a relation linking only Y 0 and X s and their derivatives. △

Appendix B: Proof of Lemma 4.4 y i V ess U 1 ∪ X s , Y 1 implies that there exists necessarily a subset Y u ⊂ Y 1 \ {y i } such that ρ U 1 ∪ X s , Y u = card(U 1 ∪ X s ). Using the previous lemma, there exist a function ϕ and an integer ν ≥ 0 such that, X T s , U T

Substituting this in subsystem (Σ 1 ), we have:

Consider then that the characteristic equation of matrix à has the form Ãn 1 +. . .+a k Ãk +. . .+a 1 Ã+a 0 Ã0 = 0, where n 1 = card(X 1 ). Multiplying this equation by Ci where Ci is the line of matrix C related to output y i in (B1), an equation of the following form is obtained:

Since y i is an output of (Σ 1 ), at least a term Ci Ãk of the latter equation is not zero and depends on y i . Then, (B2) leads to an output algebraic equation where some derivatives of y i intervene. △

Appendix C: Proof of Lemma 5.1

Every algebraic redundancy equation consists in expressing the k th derivative of an output component y i according to the other output components and/or the lower y i derivatives. So, it is of the form y (k) i =

October 28, 2013 12:24

l . If all the coefficients α l,s with l i are equal to zero, this implies that the considered redundancy equation is necessarily issued form the polynomial characteristic of matrix A. In this case, according to the results proved in [START_REF] Murota | System Analysis by Graphs and Matroids[END_REF], coefficients α i,s are all issued from the cycles constituting the graph. If at least one of the coefficients α l,s , l i is non zero, this implies that, for all ℓ ≥ k, y ℓ i can be expressed using the k -1 first derivatives of y i and the other output derivatives. In this case, from the observability subspaces dimensions, we have equivalently d(y i ) ≤ k. This implies that the only paths which traduce the k th derivative of y i with k ≥ d(y i ) can be associated to a redundancy equation. As y (k) i is represented by y i -topped paths of length k, y (k) i is not sensitive to the coefficients representing the weight of the paths which are not U ∪ X s -rooted paths and are shorter than d(y i ). Thus, when an edge is not eligible, its associated parameter cannot belong to a redundancy equation and then is not identifiable. △

Appendix D: Proof of Lemma 5.2

Let's denote by e ∈ E θ the edge associated to the unknown parameter denoted λ e . Sufficiency: First case: If e is covered by a cycle belonging to a pair of ¶ C then it is also covered by a cycle C in (Σ 1 ). Let's denote by x i the begin vertex of e. Since this vertex belongs to X 1 (Y), there exist a x i → y j path, where

From Lemma 4.3, there exist a matrix G, a function ϕ and an integer ν ≥ 0 such that

Substituting this in subsystem (Σ 1 ) and using notations of (B1), we obtain:

Since the elements of G are represented by the edges belonging to Y u -topped paths, they are independent from the elements of à associated to cycle C. Thus, the digraph representation of (D1) contains also C. Therefore, from [START_REF] Reinschke | Multivariable Control. A Graph Theoretic Approach[END_REF]) (Theorem 21.1), the characteristic equation of matrix à has the form Ãn 1 + . . .

where k is the length of C and a n 1 -k depends on the product of the weights of the edges constituting C and so, on the specific entry λ e of matrix A according to the fact that edge e belongs to C. Thus,

where C j is the line of matrix C related to output y j in (D1) i.e. y j = C j X 1 + ϕ y, j (Y u , Ẏu , . . . , Y (ν) u ). On the one hand, since x i belongs to a cycle and as there exists a x i -y j path, if ℓ > 0 denotes the length of this path then, ∀k ≥ ℓ -1, C j Ãk 0. Furthermore, since ℓ

). Thus, (D2) leads to an equation of the form:

where υ is a function depending on functions ϕ y and ϕ x . Therefore, as a n 1 -k depends on λ e , the latter intervenes in the redundancy algebraic equation (D2). Second case: If e is covered by a Γ d -Γ d path belonging to a pair of ¶ A , and as all these paths are eligible, two possibilities have to be considered: 1) e is covered by a U 1 ∪ X s -Y 1 path or 2) e is covered by a y i -topped path, which length is strictly greater than d(y i ). In the first case, we denote by v i the vertex of U 1 ∪ X s from which there is a direct

) without using edges and vertices of p. From Lemma 4.3, there exist a matrix G, a function ϕ and an integer ν ≤ n 1 such that the dynamics equation of subsystem (Σ 1 ) is in the form of (D1). Since the elements of G are represented by edges belonging to Y u -topped paths, they are independent from the elements of Ã. From the characteristic equation of matrix Ã, an equation as (D2) can be written where also C j is the line of matrix C related to output y j in (D1) i.e. y j = C j X 1 + ϕ y, j (Y u , Ẏu , . . . , Y (ν) u ). Using equations of (D1), we have

Since there exists a path of length ℓ from v i to y j containing an edge e, C j Ãℓ-1 is not zero, for all k ≥ ℓ, and depends on the element λ e of A. Moreover, ϕ (k-ℓ)

x (Y u , Ẏu , . . . , Y u (ν) ) is not zero for all k ≥ ℓ, because there exists a path between v i and an element of Y u , as by definition of

) is not zero for all k ≥ ℓ and depends on λ e . In particular, this implies that term C j Ãn 1 in relation (D2) is not zero and depends on λ e . Thus, substituting term C j Ãk X 1 by y

x (Y u , Ẏu , . . . , Y u (ν) ) depends on λ e . The second possibility is when e is covered by a y i -topped path which length is strictly greater than d(y i ). As e is also covered by a Γ d -y i path, this implies that there exists a y i -topped path p of length strictly greater than d(y i ) which covers e and such that x ℓ belongs to a direct S o {v P }, Y 1 -y i path, where v P = x j is the begin vertex of the eligible path p. y i belongs to Y 1 implies that there exists a vertex subset

. From Lemma 4.3, this implies that there exist a matrix G, a function ϕ and an integer ν ≤ n 1 such that the dynamics equation of subsystem (Σ 1 ) can be put under the form of (D1). Moreover, by definition of d(y i ), the dimension of the observability subspace is equal to d(y i ) plus the dimension of the observability subspace without y i . This means that the (d(y i )) th derivative of y i can be expressed using the other output components and the lower derivatives of y i . Thus, ∀k ≥ d(y i ), there exists a minimal subset Ỹ ⊆ Y 1 \ (Y u ∪ {y i }) such that y (k) i is a linear combination of the first derivatives of y (s) i , with s = 0, . . . , k -1 and all the possible derivatives (until the dimension of the under-determined part) of components y l of Ỹ. Thus, there exist some constant real parameters denoted α i,s and α l,s and a function υ such that:

where n 1 = card(X 1 ). Using the system equations described in (D1), it can be deduced that for each s and l, y

), where Ci (resp. Cl ) is the row of C corresponding to output y i (resp. y l ). Substituting the latter equalities in (D4), all functions of Y u and its derivatives can be simplified as they are independent from the considered elements of X 1 and (D4) can be written as:

Since subset Ỹ is minimal i.e. ∀y j ∈ Ỹ, the difference of dimensions the observability subspaces when considering respectively Y u ∪ Ỹ ∪ {y i } \ {y j } and Y u ∪ Ỹ \ {y j } as output components is strictly greater than k i , then in relation (D5), all the components of Ỹ intervene. Let's denote by e j the j th Euclidean vector. As this relation is valid whatever state vector X 1 is, it can be removed and by post-multiplying n k is the number of loops 1 covering k vertices. Here, since e 1 and e 2 are covered by the same cycle, in all the coefficients a k where appear λ r 1 and λ r 2 , the weights of the loops depend on the product λ r 1 λ r 2 . Thus, multiplying the characteristic equation by C i , an algebraic redundancy equation as (D2) is obtained, which makes possible the identifiability of the product λ r 1 λ r 2 but not of λ r 1 and λ r 2 separately.

e 1 and e 2 are covered by elements of ¶ C belonging to the same equivalent class w.r.t. relation R c and these two edges can be covered by different cycles of the same length and connected to the same vertex of Γ d . Here also, the redundancy algebraic equation, where λ r 1 and λ r 2 appear, is issued from the polynomial characteristic of matrix à of system (D1). But all the coefficients of such polynomial depend on the products of the weight of different cycles or on the sum of the weights of cycles having the same length. Therefore, multiplying the characteristic equation by C i , an algebraic redundancy equation as (D2) is obtained, where it is not possible to distinguish the value of λ r 1 and the value of λ r 2 . Thus these two values are not identifiable even if their sum and their product are known. Consequently, if two parameters λ r 1 and λ r 2 are not identifiable when they associated to two edges e 1 and e 2 covered by two elements of ¶ A ∪ ¶ C belonging to the same equivalence classes w.r.t. relations R p or R c and the lemma follows. △

Appendix F: Proof of Lemma 5.5

If all the DM-component cardinalities are equal to one in B I (F ) and if each element of F can be associated to an equation making possible the identification of its linked parameters in B I (F ), then using the DM-decomposition properties, these equations constitute a triangular system. In this case, all the parameters are obviously structurally identifiable. Consequently, to establish the lemma, it has to be proven that each element of F can be associated to an equation making possible the identification of its linked parameters in B I (F ).

Consider first that for an element {c 1 , p ′ 1 } ∈ ¶ C , c 1 covers a set of parameters λ r 1 , . . . , λ r k . Since this cycle is connected to an element of Γ d by p ′ 1 and since all the vertices of Γ d are linked to at least one output vertex, then the considered cycle is linked to at least one output vertex. Let's denote by y i one of these outputs. The redundancy algebraic equations, where λ r 1 ,. . . , λ r k appear, are issued from the polynomial characteristic of matrix à (D1). From [START_REF] Reinschke | Multivariable Control. A Graph Theoretic Approach[END_REF] This equation can be multiplied by C i to obtain redundancy algebraic equation of the form (D2). One identification equation can be written for each coefficient a k of this redundancy algebraic equation. From this equation, for each length of cycle and so for each equivalent class w.r.t. relation R c , an identifiability equation can be deduced. Therefore, the obtained equation (noted Eq c 1 ) related to {c 1 , p ′ 1 } has then as unknown variables the sum of products of weights of all the cycles belonging to the pairs included in the same equivalent class than {c 1 , p ′ 1 } w.r.t. relation R c . Consider now the case where an element {p i,1 , p i,2 } ∈ ¶ A , c 1 covers a set of parameters λ r 1 , . . . , λ r k in B I (F ). This element corresponds to Γ d -Γ d paths, and so, as all the elements of Γ d are linked to vertices of Y 1 , this element corresponds also to Γ d -Y 1 paths having distinct end vertices. Let's denote y i 1 and y i 2 the output end vertices of these paths and ℓ 1 , ℓ 2 the length of these paths. It has been shown, in Lemma 5.2, that these paths can be associated to a redundancy algebraic equation on the form of Equation (D4) when terms α i 1 ,k 1 y (k 1 ) i 1 and α i 2 ,k 2 y (k 2 ) i 2 appear, with k 1 ≥ ℓ 1 and k 2 ≥ ℓ 2 . From this equation, containing K parameters, it can be deduced K identification equations for each coefficient. Using the same arguments than in the proof of Lemma 5.2, coefficients α i 1 ,k 1 and α i 2 ,k 2 are respectively sensitive (inversely proportional) to the sum of the weights of all the paths belonging to the pairs included in the same equivalent class than {p i,1 , p i,2 } w.r.t. relation R p . Therefore, the obtained equation (noted Eq p 1 ) related to {p i,1 , p i,2 } has then as unknown variables the sum of products of weights of all the cycles belonging to the pairs included in