{'fraction_non_alphanumeric': 0.0621709472142105, 'fraction_numerical': 0.010804376688183858, 'mean_word_length': 3.579454926624738, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Fault detection and isolation for linear structured systems

This paper deals with the fault detection and isolation (FDI) problem for linear structured systems in which the system matrices are given by zero/nonzero/arbitrary pattern matrices. In this paper, we follow a geometric approach to verify solvability of the FDI problem for such systems. To do so, we first develop a necessary and sufficient condition under which the FDI problem for a given particular linear time-invariant system is solvable. Next, we establish a necessary condition for solvability of the FDI problem for linear structured systems. In addition, we develop a sufficient algebraic condition for solvability of the FDI problem in terms of a rank test on an associated pattern matrix. To illustrate that this condition is not necessary, we provide a counterexample in which the FDI problem is solvable while the condition is not satisfied. Finally, we develop a graph-theoretic condition for the full rank property of a given pattern matrix, which leads to a graph-theoretic condition for solvability of the FDI problem.


I. INTRODUCTION
This paper is concerned with the FDI problem for linear time-invariant (LTI) systems with faults. This problem has received considerable attention within the control community in the past decades and this has lead to several approaches to FDI, see, e.g., [1]- [6] and the references therein. Among these references, those closer to the results presented in the current paper are [2] and [6], in which FDI for LTI systems is performed using unknown input observers that enable socalled output separability of the fault subspaces. If such observers exist, then we say that for the given system the FDI problem is solvable.
Although conditions for solvability of the FDI problem for a given LTI system have been introduced in [2], their application relies on the exact knowledge of the dynamics of this system, meaning that precise information on the system matrices is required. However, in many scenarios, such knowledge is unavailable, and only the zero/nonzero/arbitrary structure can be acquired. This leads to the concept of linear structured system introduced in [7] which represents a family of LTI systems sharing the same structure. A large amount of literature has been devoted to analyzing system-theoretical properties for linear structured systems. For instance, strong structural controllability has been studied in [7]- [10], strong targeted controllability in [11], [12], and identifiability in [13].
Roughly speaking, in the framework of linear structured systems, the research on the FDI problem can be subdivided into two directions. The first direction aims at providing conditions under which the FDI problem is solvable for at The  least one member of a given structured system, see, e.g., [5], [14], [15]. The other direction aims at establishing conditions to guarantee that the FDI problem is solvable for all members of a given structured system, see, e.g., [6]. In the present paper, we will pursue the second research direction. For a given structured system, if the FDI problem for all systems in the structured system is solvable, then we say that the FDI problem for this structured system is solvable. To the best of our knowledge, in this direction the only existing work is [6], which has studied a special kind of linear structured system, named systems defined on graphs. The goal of the present paper is to provide conditions under which the FDI problem is solvable for a general structured system. The main contributions of this paper are the following: 1) We develop a necessary and sufficient condition under which the FDI problem is solvable for a given particular LTI system. 2) Based on the condition for a particular LTI system, we establish a necessary condition for solvability of the FDI problem for a given structured system. Next, we develop a sufficient algebraic condition. This condition is given in terms of a rank test on a pattern matrix associated with the structured system. Moreover, we provide a counterexample to show that this condition is not necessary. 3) Using the concept of colorability of a graph, we provide a graph-theoretic condition for solvability of the FDI problem for a given structured system. This paper is structured as follows. In Section II, we review concepts and preliminary results on geometric control theory and the geometric approach to the FDI problem for particular LTI systems. In addition, we introduce the concept of linear structured systems and formulate the problem studied in this paper. Section III presents a necessary and sufficient condition under which for a given particular LTI system the FDI problem is solvable. Section IV provides a necessary and a sufficient algebraic condition for solvability of the FDI problem for structured systems. Next, in Section V we establish a graph-theoretic condition for solvability of the FDI problem. Finally, section VI concludes this paper.

II. PRELIMINARIES AND PROBLEM STATEMENT
Let R and R n denote the field of real numbers and the vector space of n-dimensional real vectors, respectively. Likewise, we denote the space of n × m real matrices by R n×m . For a given matrix M ∈ R n×m , the ith column of M is denoted by M i . Moreover, I and 0 will denote identity and zero matrices of appropriate dimensions, respectively.

A. Geometric control theory
Geometric control theory plays a fundamental role in this paper. Therefore, in this subsection, we will give a brief review of some basic concepts in this field. Consider the LTI systemẋ where x ∈ R n , u ∈ R m and y ∈ R p are the state, input and output, respectively, and A, B and C are matrices of Any output separable family of (C, A)-invariant subspaces is compatible [2, Lemma 2]. Moreover, if it also satisfies the condition that CS i = {0} for i = 1, 2, . . . , k, we say that the family {CS i } k i=1 is independent. For a given subspace D ⊆ R n , there exists a smallest (C, A)-invariant subspace containing D, denoted by S * . Such a minimal subspace can be computed by the following subspace algorithm (see, e.g., the conditioned invariant subspace algorithm p.111 of [16]): Denote the dimension of D by dim(D). It follows from Theorem 5.8 of [16] that there exists k n − dim D such that S k = S k+1 , and hence S * = S k .

B. The geometric approach to the FDI problem for LTI systems
In this subsection, we will review the geometric approach to the FDI problem for LTI systems. Consider the LTI systeṁ where x ∈ R n , f ∈ R q and y ∈ R p are the state, fault and output, respectively, and A, L and C are matrices of appropriate dimensions. We denote the system (3) by (A, L,C). We say that the ith fault occurs if f i = 0 (i.e., not identically equal to 0), where f i is the ith component of f . Following the approach proposed in [2], the FDI problem for (3) amounts to finding G ∈ R n×p such that the family of subspaces is independent, where V i is the smallest (A + GC)-invariant subspace containing im L i . If such G exists, then we say that the FDI problem is solvable. In what follows, we will briefly explain this approach. Suppose that we have found a G satisfying the above constraints. Consider the state observeṙ Define the innovation as r := Cx − y and error e :=x − x.
By interconnecting (3) and (4), we obtaiṅ Note that in this paper, we do not consider any stability requirement on the observer, which means that we do not require e(t) → 0, and we assume that e(0) = 0. Under this assumption, for any fault f , the resulting error trajectory e(t) lies in the reachable subspace of (A+GC, L), which is clearly For the corresponding innovation trajectory r(t) we then have If the family {CV i } q i=1 is independent, then this is a direct sum, and r(t) can be written uniquely as with r i (t) ∈ CV i for all t. The unique representation (6) can be used to determine whether the ith fault occurs. Indeed in [2] it has been shown that the FDI problem for the system (3) is solvable if and only if the family is independent, i.e., the family

C. Linear structured systems and problem formulation
Again, consider the LTI system (3). In many scenarios, the exact values of the entries in the system matrices are not known, but some entries are known to be always zero, some are nonzero, and the remaining entries are arbitrary real numbers. To describe such kind of matrices, the authors in [7] have introduced the definition of pattern matrix as follows.
A pattern matrix is a matrix with entries in the set of symbols {0, * , ?}. The set of all r × s pattern matrices is denoted by {0, * , ?} r×s . For a given r × s pattern matrix M , we define the pattern class of M as This means that for a matrix M ∈ P(M ), the entry M i j is Let A ∈ {0, * , ?} n×n , L ∈ {0, * , ?} n×q and C ∈ {0, * , ?} n×p . The family of systems (A, L,C) with A ∈ P(A ), L ∈ P(L ) and C ∈ P(C ) is called the linear structured system associated with A , L , and C . Throughout this paper, we use (A , L , C ) to represent this structured system, and we write (A, L,C) ∈ (A , L , C ) if A ∈ P(A ), L ∈ P(L ) and C ∈ P(C ). Based on these notions and notations, we define the FDI problem for (A , L , C ) to be solvable if the FDI problem is solvable for every (A, L,C) ∈ (A , L , C ). The research problem of this paper is then formally stated as follows.
Problem 1: Given (A , L , C ), find conditions under which the FDI problem is solvable for (A , L , C ).

III. A NECESSARY AND SUFFICIENT CONDITION FOR
SOLVABILITY OF THE FDI PROBLEM FOR (A, L,C) In this section, we will establish a necessary and sufficient condition under which the FDI problem is solvable for a given LTI system (A, L,C) of the form (3). Recall that solvability of the FDI problem for (A, L,C) is equivalent to the independence of the family Here and in the sequel, we define A 0 := I. It is obvious from the Cayley-Hamilton theorem that either d i n or d i does not exist. If this d i exists, we then call it the index of (A, L i ,C).
We are now ready to state a characterization of CS * i in the following lemma.
Lemma 1: otherwise. Proof: In this proof, we will employ the recurrence relation (2) to prove the statement. Let S ℓ i be the sequence of subspaces given by We then distinguish two cases: (i) d i exists, and (ii) d i does not exist.
In case (i), we have that and By combining (7) and (8), it can be verified directly that and hence CS * i = imCA d i −1 L i . Note that (a) follows immediately from (9) and (10): To prove (b), we assume that (b) is not true, i.e.,

This implies
which contradicts (9), and hence (b) is proved. For case (ii), we have By combining (7) and (11), we obtain

It then follows from the Caley-Hamilton theorem that
Proof: The proof follows immediately from Lemma 1 and is hence omitted.

IV. ALGEBRAIC CONDITIONS FOR SOLVABILITY OF THE
FDI PROBLEM FOR (A , L , C ) In this section, we will establish a necessary condition and a sufficient condition that enables the FDI problem for a given structured system (A , L , C ) to be solvable. Before presenting the results of this section, we first provide some background on operations on pattern matrices. More details can be found in [17]. Addition and multiplication within the set {0, * , ?} are defined in Table I below. Based on the operations in Table I, multiplication of pattern matrices is then defined as follows. (13) It is easily seen that MN ∈ P(M N ) for every pair of matrices M ∈ P(M ) and N ∈ P(N ). If r = s, we call M a square pattern matrix. For any given non-negative integer k, we define the kth power M k recursively by where I represents a square pattern matrix of appropriate dimensions with all diagonal entries equal to * and all offdiagonal equal to 0. In the sequel, let O denote any pattern matrix of appropriate dimensions with all entries equal to 0.
Next, consider the system (A , L , C ). Let L i represent the ith column of L for i = 1, 2, . . . , q. Let η i be a positive integer such that If η i exists, then we call it the index of (A , L i , C ). In the sequel, we will write (A, L i ,C) ∈ (A , L i , C ) if A ∈ P(A ), L i ∈ P(L i ) and C ∈ P(C ). Before continuing to explore conditions for solvability of the FDI problem for (A , L , C ), we first provide the following lemma which states the relationship between the index of (A , L i , C ) and that of (A, L i ,C) ∈ (A , L i , C ). Proof: By Definition 3, it follows that the vector CA ℓ L i ∈ P(C A ℓ L i ) for i = 0, 1, . . . and for all (A, L i ,C) ∈ (A , L i , C ). In order to prove (i), suppose that both the index η i of (A , L i , C ) and the index d i of (A, L i ,C) exist. By the definition of η i we have that C A ℓ L i = O for ℓ = 0, 1, . . . , η i − 2, and by the definition of d i it follows that CA d i −1 L i = 0. Therefore, we obtain d i η i . Next, to prove (ii), we assume that C A η i −1 L i contains at least one * entry, which implies that all the vectors in the pattern class Clearly, the vector CA η i −1 L i ∈ P(C A η i −1 L i ), and hence CA η i −1 L i = 0. By definition, the index d i of (A, L i ,C) must exist and d i η i . Recalling (i), we conclude that d i = η i . The proof of (iii) is trivial. Indeed, suppose that the index of (A , L i , C ) does not exist. It then follows that C A ℓ L i = O for ℓ = 0, 1, . . ., which implies that CA ℓ L i is equal to 0 for every (A, L i ,C) ∈ (A , L i , C ). That is, the index of (A, L i ,C) does not exist for any (A, L i ,C) ∈ (A , L i , C ). To illustrate the above lemma, we now provide an example.
Example 1: (14) Let L 1 , L 2 and L 3 denote the first, second and third column of L . For L 1 and L 2 we compute This implies that η 1 = η 2 = 1, where η i is the index of (A , L i , C ) for i = 1, 2. In addition, for L 3 we compute which implies that the index of (A , L 3 , C ) does not exists. Next, we will show that for some (A, L 1 ,C) ∈ (A , L 2 , C ) the index d 1 of (A, L 1 ,C) is larger than η 1 , for every (A, L 2 ,C) ∈ (A , L 2 , C ) its index d 2 is equal to η 2 , and for every (A, L 3 ,C) ∈ (A , L 3 , C ) its index does not exists,. Indeed, for A ∈ P(A ), L ∈ P(L ) and C ∈ P(C ) we have where c 1 , c 2 , . . . , c 7 are arbitrary nonzero real numbers, and λ 1 is an arbitrary real number. Next, we compute Thus, for all choices of c 1 , c 2 , . . . , c 7 and λ 1 we have d 2 = 1 = η 2 , while if λ 1 = 0 then d 1 = 2 > η 1 and otherwise d 1 = 1 = η 1 . In addition, it is obvious that for all choices of c 1 , c 2 , . . . , c 7 and λ 1 we have CA ℓ L 3 = 0 for ℓ = 0, 1, . . ., and hence the index of (A, L 3 ,C) does not exist. Lemma 4 immediately yields a necessary condition for solvability of the FDI problem for (A , L , C ).
Theorem 5: Consider the system (A , L , C ). Suppose that the FDI problem for (A , L , C ) is solvable. Then, the index η i of (A , L i , C ) exists for all i = 1, 2, . . . q.
Proof: Since the FDI problem for (A , L , C ) is solvable, the FDI problem is solvable for all (A, L,C) ∈ (A , L , C ). Assume that for some i ∈ {1, 2, . . ., q} the index η i of (A , L i , C ) does not exist. By statement (iii) of Lemma 4, it follows that the index d i of (A, L i ,C) does not exist for any (A, L i ,C) ∈ (A , L i , C ). It then follows from Theorem 2 that the FDI problem for (A, L,C) is not solvable for any (A, L,C) ∈ (A , L , C ). Therefore, we reach a contradiction and complete the proof.
By the above theorem, in the sequel we will assume that for all i = 1, 2, . . . q the indices η i exist. Based on this assumption, we will continue to explore sufficient conditions for solvability of the FDI problem for (A , L , C ). To do so, we first define the following pattern matrix associated with (A , L , C ): where η i is the index of (A , L i , C ). We say that R has full column rank if all the matrices in the pattern class P(R) have full column rank. We are now ready to establish a sufficient condition for solvability of the FDI problem for (A , L , C ).
Theorem 6: Consider the system (A , L , C ). Let R be the pattern matrix given by (17). The FDI problem for (A , L , C ) is solvable if R has full column rank.
Proof: Since R has full column rank, each column of R contains at least one * entry. Let (A, L,C) ∈ (A , L , C ). By (ii) of Lemma 4 it follows that d i = η i , where d i is the index of (A, L i ,C) for i = 1, 2, . . . , q. This implies that the matrix R given by (12) is in P(R), and hence R has full column rank. It then follows from Theorem 2 that the FDI problem is solvable. Since (A, L,C) is an arbitrary system in (A , L , C ), we conclude that the FDI problem for (A , L , C ) is solvable and complete the proof.
Note that the condition given in Theorem 6 is sufficient but not necessary. To show this, we provide the following counterexample.
Example 2: Consider the system (A , L , C ) with Let L 1 and L 2 be the first and second column of L . We compute and, by (17), R = * ? * * . Since 1 1 1 1 ∈ P(R), R does not have full column rank. Next, we will show that, however, the FDI problem for (A , L , C ) is solvable. Due to Theorem 2, it suffices to show that for each (A, L,C) ∈ (A , L , C ) the associated matrix R has full column rank. Clearly, every (A, L,C) ∈ (A , L , C ) has the form where c 1 , c 2 , . . . , c 6 are arbitrary nonzero real numbers. By (12), we obtain It turns out that R has full column rank. Indeed, the determinant of R is equal to −c 1 c 3 c 5 c 6 which is always nonzero. Consequently, the FDI problem for (A , L , C ) is solvable. This provides a counterexample for the necessity of the condition in Theorem 6.
V. A GRAPH-THEORETIC CONDITION FOR SOLVABILITY OF THE FDI PROBLEM So far, we have provided a sufficient condition for solvability of the FDI problem for (A , L , C ) in terms of the full column rank property of its associated matrix R. However, given such a matrix R, it is not clear how to check its full column rank property. Hence, in this section, we will provide a graph-theoretic condition under which a given pattern matrix R has full column rank. Clearly, by Theorem 6 this will immediately lead to a graph-theoretic condition for solvability of the FDI problem for (A , L , C ).
We will now first review the concept of graph associated with a given pattern matrix, and the color change rule that acts on this graph. For more details, see [7]. To visualize this, solid and dashed arrows are used to represent edges in E * and E ? , respectively. We say that M has full row rank if the matrix M has full row rank for all M ∈ P(M ). Next, we introduce a so-called color change rule which is defined as follows.
(2) If a node i has exactly one white out-neighbor j and (i, j) ∈ E * , change the color of j to black. (3) Repeat step 2 until no more nodes can be colored black. The graph G(M ) is called colorable if the nodes 1, 2, . . . , r are colored black following the procedure above. Note that the remaining nodes r + 1, r + 2, . . . , s can never be colored black since they have no incoming edges. A criterion for the full row rank property of M is then given by the following proposition. Define the transpose of R as the pattern matrix R ⊤ ∈ {0, * , ?} s×r with (R ⊤ ) i j = R ji for i = 1, 2, . . . , s and j = 1, 2, . . . , r. We then obtain the following obvious fact: Lemma 8: Consider the system (A , L , C ). Let R be the pattern matrix given by (17) and R ⊤ be its transpose. Then R has full column rank if and only if G(R ⊤ ) is colorable.
This then immediately yields the main result of this section which provides a graph-theoretic condition under which the FDI problem for (A , L , C ) is solvable.
Theorem 9: Consider the system (A , L , C ). Suppose that the indices η i exists for i = 1, 2, . . . , q. Let R be the pattern matrix given by (17). Then, the FDI problem for Proof: The proof follows immediately from Theorem 6 and Lemma 8.
To conclude this section, we will provide an example. By multiplying the pattern matrices, we obtain that where L i is the ith column of L . By (17), it follows that the associated matrix R and its transpose R ⊤ are given by As depicted in Fig. 1 G(R ⊤ ) is colorable. Indeed, initially let all nodes in G(R ⊤ ) be colored white as shown in Fig.  1(a). Node 1 then colors itself black as depicted in Fig. 1(b), and finally node 3 colors 2 to black as in Fig. 1(c). Therefore, by Theorem 9, the FDI problem for (A , L , C ) is solvable.

VI. CONCLUSION
In this paper, we have studied the FDI problem for linear structured systems. We have established a necessary and sufficient condition for solvability of the FDI problem for a given particular LTI system. Based on this, we have established a necessary condition under which the FDI problem for structured systems is solvable. Moreover, we have developed a sufficient condition for solvability of the FDI problem in terms of a rank test on a pattern matrix associated with the structured system. Next, we have provided a counterexample to show that this condition is not necessary. Finally, we have developed a graph-theoretic condition for solvability of the FDI problem using the concept of colorability of a graph. This paper has only established a necessary condition and sufficient conditions for solvability of the FDI problem for structured systems. Finding necessary and sufficient conditions for solvability of the FDI problem is still an open problem. In addition, as we have mentioned in section II-B, this paper does not consider the stability of the unknown input observers. Therefore, another possible future research direction is to establish conditions under which stable unknown input observers exist for linear structured systems. Furthermore, investigating solvability of FDI for structured systems with constraints, such as allowing dependencies on some nonzero and arbitrary entries [18]- [20], is also a possibility for future research.