# Output null controllability for linear time-invariant structured discrete-time systems: a graph theoretic condition

Jacob van der Woude, Christian Commault, Taha Boukhobza

► To cite this version:

Jacob van der Woude, Christian Commault, Taha Boukhobza. Output null controllability for linear time-invariant structured discrete-time systems: a graph theoretic condition. European Journal of Control, 2024, 29, pp.101077. 10.1016/j.ejcon.2024.101077. hal-04644857

HAL Id: hal-04644857

https://hal.science/hal-04644857v1

Submitted on 11 Jul 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Output null controllability for linear time-invariant structured discrete-time systems: a graph theoretic condition

Jacob van der Woude, Christian Commault and Taha Boukhobza

*Abstract*—In this paper, we consider a linear time-invariant discrete-time system and study the output null controllability problem, i.e., the problem of steering the output to zero in a finite number of steps. We assume that we only know the structure of the system, i.e., the zero/nonzero location in the system matrices. Hence, we consider a structural version of the output null controllability problem. We represent the structure of the system by means of a directed graph and present a graph theoretic sufficient condition for the problem to be generically solvable. Here generically solvable means that the problem is solvable for almost all systems with the same structure. We illustrate the conditions using an example.

*Keywords*—Structured linear discrete-time systems, output null controllability, graph theoretic approach, solvability condition

## I. INTRODUCTION

In this paper, we consider a linear time-invariant discrete-time system with a state, an input, and an output. We study the problem of steering the output to zero in a finite number of steps by applying an appropriate sequence of inputs. More specifically, we address the problem from a structural point of view, meaning that we only want to use the structure of the system equations. Hence, we only assume the zero/nonzero structure of the system matrices to be known. Because of this, we can only say something about the possible generic solvability of the problem. Here, generic solvability of the problem means that it is solvable for almost all systems with the same structure, while the set of systems with the same structure for which the problem fails to be solvable forms a set of zero Lebesgue measure.

For a specific numerically specified system, an input that actually steers the output to zero in a finite number of steps, also requires the numerical values of matrix entries, i.e., for such a concrete input actually solving the problem, the structure of the system alone is not enough.

Controllability in the structural context has already been studied for quite some time. The first publication in 1974 is due to Lin [10]. Later other publications on the topic followed, see the introduction of the survey paper [7]. Originally, the results involved continuous-time systems and full state controllability. Zero state controllability for discrete-time systems

was studied in [22]. As such, that current paper can be seen as a follow-up and extension of some controllability aspects for linear continuous-time systems. A structural characterisation of output controllability was left as an open problem in [13] and, to the best of our knowledge, no graph characterisation for structural output controllability is available to date. The second difficulty is the intrinsic hardness of the problem: the minimum output controllability problem has recently been proven to be an NP-hard problem [6].

In the overview papers [7] and [17], or in the textbooks [12] and [18], an extensive motivation for the study of structured systems is given. In general, the study is motivated by the lack of precise knowledge in the description of the systems. For instance, in several applications the nonzero values in the system matrices are obtained via measurements, and thus with certain errors. Or, they appear by using physical laws that are only valid in perfect conditions, thus also with some associated errors in practical situations. In such situations, the structural approach toward the systems may be useful, yielding results that are true generically, i.e., in most practical cases. Also, sometimes certain properties of linear time-invariant systems are hard to compute, such as minimal controllability problems, see [14] and [16], whereas the structured (practical) versions are easy to solve, see [15].

A very important advantage of structured systems is the fact that they are associated in a natural way with a directed graph. This graph is important to visualize the interactions inside the system and also to characterize a lot of properties of the system. This characterization in graph terms is often very informative in terms of deep structure of the system, but also generally leads to very efficient algorithms to check the properties.

The study of controllability in complex networks/structured systems was given an enormous boost in 2011 by [11]. The paper revived interest in the subject, and many papers on various aspects of controllability have appeared since. See, for instance, [2], [15] and [21]. The paper proved that important network features can be nicely formulated in terms of structured systems properties. This considerably enlarged the range of structured systems applications. Through time also other aspects of linear structured systems have been studied, like structural properties of transfer matrices and various structural (disturbance) decoupling problems. Many of the results were inspired by the geometric and frequency domain approach toward linear system theory, like in [1], [4] and [5].

As mentioned earlier, in the current paper the focus is on

<footnote>Jacob van der Woude, DIAM, EWI, Delft University of Technology, Delft, The Netherlands; Christian Commault, Grenoble Univ, Grenoble INP, Gispsa-lab, 38400 Grenoble, France; Taha Boukhobza, University of Lorraine, CRAN, CNRS, Nancy, France; email: j.w.vanderwoude@tudelft.nl, christian.commauly@gipsa-labgrenoble-inp.fr, taha.boukhobza@univ-lorraine.fr</footnote>
discrete-time systems and on steering the output to zero in a finite number of time steps. The problem in this paper has been studied in other works, and nice geometric conditions are known, see [20] and [23]. However, the conditions in these references do not well fit within the structural framework that we adopt in this paper. Therefore, we use conditions that better fit the structural approach. Specially we will use an alternative sufficient condition. The condition will be expressed in terms of the directed graph that easily can be associated with the structured system in this paper. The sufficiency condition is then obtained using a decomposition of the graph of the system that naturally fits the problem under consideration. The main result of this paper, being a sufficient graph theoretic condition for the generic solvability of the problem, can then be obtained easily. We illustrate the condition through an example.

The outline of this paper is as follows. In Section II, we introduce the type of system studied in this paper. Also, we formulate the state and output null controllability problem and recall a necessary and sufficient condition for their solvability. The presented condition comes from the geometric approach towards linear system theory, see [23]. For completely known and numerically specified systems, the condition is elegant and also intuitive in a sense. However, the geometric nature of the condition does not fit very well within the structural approach adopted in this paper. This holds in particular for the output null controllability problem, since a structural condition for the generic solvability of the state null controllability problem can be easily given, see [22]. Therefore, in Section III, we present an alternative sufficient condition for the output null controllability problem that better suits our purposes. This paper focuses on finding a solvability condition that matches the adopted structural point of view. In Section IV, several special cases are studied that easily can be dealt with in the structural approach. The special cases will be the foundation of the main result of the paper. In Section V, the graphs of structured systems will be introduced, together with some elementary notions of graph theory. Also, a decomposition will be described that follows naturally from the problem studied in the paper. In Section VI, parts of the obtained decomposition will be related to existing results in the literature. The combination of these results yields a sufficient condition for the generic solvability of the output null controllability problem in graph terms. The condition is included in Section VI-B, and is illustrated via an example in Section VII. We end the paper with Section VIII with some conclusions and remarks. In particular, the possible necessity of the obtained sufficient condition will be discussed. Also an extension of the obtained condition will be mentioned. The appendix, in Section IX, contains the proof of a statement in a derivation of the alternative sufficient condition.

In this paper, we will frequently use identity matrices $I$, and zero matrices $0$. However, to simplify the notations, we will not precise their dimensions, which will always follow from the context in which they appear.

## II. STATE AND OUTPUT NULL CONTROLLABILITY

We consider the following linear discrete-time system

$$x(k+1) = Ax(k) + Bu(k), \quad y(k) = Cx(k), \quad (1)$$

with $k \ge 0$, the time, and all variables and matrices as usual. More precisely, we have a state $x(k) \in \mathbb{R}^n$, an input $u(k) \in \mathbb{R}^m$, and an output $y(k) \in \mathbb{R}^p$, implying that $A \in \mathbb{R}^{n \times n}$, $B \in \mathbb{R}^{n \times m}$ and $C \in \mathbb{R}^{p \times n}$.

Considering system (1), we denote its state at time $k \ge 0$, given the initial state $x(0) = x_0$ and a control sequence $u := \{u(0), u(1), u(2), \dots\}$, by $x_u(k, x_0)$. Similarly, $y_u(k, x_0)$ denotes the output at time $k$, given the initial state $x_0$ and control sequence $u$. Note that

$$x_u(k, x_0) = A^k x_0 + \sum_{l=0}^{k-1} A^{k-1-l} Bu(l). \quad (2)$$

Likewise,

$$y_u(k, x_0) = CA^k x_0 + \sum_{l=0}^{k-1} CA^{k-1-l} Bu(l). \quad (3)$$

Considering system (1), we say that for initial state $x_0$, the state null controllability problem is solvable, if there exists a time $K \ge 0$ and a control sequence $u$ such that $x_u(k, x_0) = 0$ for all $k \ge K$. When the latter holds for any initial state $x_0$, we say that system (1) is state null controllable. We use the abbreviation SNC for ‘the state null controllability problem’, or ‘state null controllable’. Hence, we may say that SNC is solvable for initial state $x_0$, or that SNC is solvable for system (1), respectively. Or, even simpler, we may refer to it as SNC for $x_0$, or SNC for system (1), respectively.

We write $\langle A|im B \rangle$ for the controllable subspace, i.e., the column space of the well-known controllability matrix $(B, AB, \dots, A^{n-1}B)$. Recall that $\langle A|im B \rangle$ is the smallest $A$-invariant subspace that contains $im B$. For SNC, necessary and sufficient conditions for $A$ and $B$ are well known, see for instance [20], Exercise 3.19. Two of such conditions are listed in the next lemma.

**Lemma 1.** Let system (1) be given. Then

(i) SNC is solvable for initial state $x_0$ if and only if $A^n x_0 \in \langle A|im B \rangle$.

(ii) SNC is solvable if and only if $rank(A - zI, B) = n$, for all $z \ne 0$.

Now, including the output, we say that for initial state $x_0$, the output null controllable is solvable, if there exists a time $K \ge 0$ and a control sequence $u$ such that $y_u(k, x_0) = 0$ for all $k \ge K$. When the latter holds for any initial state $x_0$, we say that system (1) is output null controllable. We use the abbreviation ONC for ‘the output null controllability problem’, or ‘output null controllable’. Hence, we may say that ONC is solvable for initial state $x_0$, or that ONC is solvable for system (1), respectively. Or, even simpler, we may refer to it as ONC for $x_0$, or ONC for system (1), respectively.

We write $\mathcal{V}^*(\ker C)$ for the largest controlled invariant subspace in $\ker C$, i.e., the largest subspace $\mathcal{V}$ in $\ker C$ such that $A\mathcal{V} \subseteq \mathcal{V} + im B$. Also, for ONC, necessary and sufficient
conditions for A, B, and C can be derived, see Hautus [8] for some background.

**Lemma 2.** Let system (1) be given. Then ONC is solvable for initial state $x_0$ if and only if $A^nx_0 \in \mathcal{V}^*(\ker C) + \langle A|im B\rangle$.

**Proof.** It can be checked that the geometric condition is a discrete-time analog of the condition in [23], Theorem 4.4, when the stability region is the origin in the complex plane. □

Note that both types of null controllability are linear in the initial state. Indeed, assume that SNC is solvable for initial states $x(0) = x_a$ and $x(0) = x_b$ by applying control sequences $u_a$ and $u_b$, respectively. Then SNC is also solvable for $x(0) = \alpha_a x_a + \alpha_b x_b$ by applying control sequence $\alpha_a u_a + \alpha_b u_b$. A similar statement holds for ONC.

### III. SUFFICIENT SOLVABILITY CONDITION FOR ONC

From Lemma 2, a (geometric) sufficient condition for the solvability of ONC follows directly. However, this condition does not easily go together with the structural approach that we adopt in this paper. Therefore, to derive a condition that nicely fits the structural approach, we will use an alternative sufficient condition. To introduce this condition, we consider system (1) with initial state $x(0) = x_0$, and we assume that

$$ \text{rank}(C(zI - A)^{-1}B) = \text{rank}(C(zI - A)^{-1}(B, x_0)), \quad (4) $$

where $(B, x_0)$ is the $n \times (m+1)$ matrix obtained by concatenating the matrix $B$ with the column vector $x_0$, and the rank condition (4) holds for almost all complex $z$. Then, seen as an equation over the (field of) rational functions, the rank condition in (4) implies that the equation

$$ C(zI - A)^{-1}Bu(z) = C(zI - A)^{-1}x_0 \quad (5) $$

has a rational vector $u(z)$ as a solution. It then follows that there exist rational vectors $p(z)$ and $q(z)$ such that

$$ (zI - A)p(z) - Bq(z) = x_0 \text{ and } Cp(z) = 0. $$

Indeed, with $u(z)$ as a solution to equation (5), take $q(z) = -u(z)$ and $p(z) = (zI - A)^{-1}(x_0 + Bq(z))$.

Next, note that $Cp(z) = 0$ implies that $Cp(z)$ can be seen as a polynomial expression that happens to be the zero polynomial. Hence, we obtain that there exist rational vectors $p(z)$ and $q(z)$ such that

$$ (zI - A)p(z) - Bq(z) = x_0 \text{ and } Cp(z) \text{ is polynomial.} $$

Using methods of Schumacher [19], see also Hautus [8], it can be proved that the latter implies that (see also a proof in the appendix)

$$ x_0 \in \mathcal{V}^*(\ker C) + \langle A|im B \rangle. $$

Note that the subspace $\mathcal{V}^*(\ker C) + \langle A|im B \rangle$ is A-invariant. Indeed, by the properties mentioned in Section II, it follows that $A(\mathcal{V}^*(\ker C) + \langle A|im B \rangle) \subseteq \mathcal{V}^*(\ker C) + \text{im } B + \langle A|im B \rangle \subseteq \mathcal{V}^*(\ker C) + \langle A|im B \rangle$. Hence, it follows immediately that

$$ A^nx_0 \in \mathcal{V}^*(\ker C) + \langle A|im B \rangle. \quad (6) $$

By Lemma 2, the latter implies the existence of a control sequence $u = \{u(k)|k \ge 0\}$ for $x(0) = x_0$, such that $y_u(k, x_0) = 0$ for all $k \ge K$ for some appropriate $K \ge 0$. So, we have obtained the following sufficient condition.

**Lemma 3.** Consider system (1) with the initial state $x_0$. If rank condition (4) is satisfied, then ONC is solvable for $x_0$.

**Proof.** If condition (4) is satisfied, condition (6) follows from the above, implying by Lemma 2 that ONC is solvable for $x_0$. □

Hence, the rank condition in (4) provides a sufficient condition for solving ONC for a specific initial condition. Rank conditions like (4), with $x_0$ replaced by a known matrix, are useful in the structural approach that we follow in this paper, because they can be implemented in an elegant way.

### IV. THE SOLVABILITY OF ONC IN SPECIAL CASES

Before treating the general case, we first look at some special cases in which the solvability of ONC can be treated more easily, and that may be useful for the general case.

1) Consider the linear discrete time system given by (1).

**Proposition 1.** Assume that SNC for system (1) is solvable, then ONC is solvable for system (1).

**Proof.** If for initial state $x_0$, there is a control sequence $u$ and an integer $K \ge 0$ such that $x_u(k, x_0) = 0$ for all $k \ge K$, then also $y_u(k, x_0) = Cx_u(k, x_0) = 0$ for all $k \ge K$. Hence, SNC implies ONC. □

2) Assume that the state $x(k)$, and the matrices $A, B$ and $C$ in (1) are partitioned as

$$ x(k) = \begin{pmatrix} x_1(k) \\ x_2(k) \end{pmatrix}, \quad A = \begin{pmatrix} A_{11} & A_{12} \\ 0 & A_{22} \end{pmatrix}, \quad (7) $$

$$ B = \begin{pmatrix} B_1 \\ 0 \end{pmatrix}, \quad C = \begin{pmatrix} C_1 & C_2 \end{pmatrix}, \quad (8) $$

with $x_1(k) \in \mathbb{R}^{n_1}, x_2(k) \in \mathbb{R}^{n_2}, A_{11} \in \mathbb{R}^{n_1 \times n_1}, A_{12} \in \mathbb{R}^{n_1 \times n_2}, A_{22} \in \mathbb{R}^{n_2 \times n_2}$, where $n_1 + n_2 = n$, $B_1 \in \mathbb{R}^{n_1 \times m}$, $C_1 \in \mathbb{R}^{p \times n_1}$ and $C_2 \in \mathbb{R}^{p \times n_2}$.

**Proposition 2.** Let the partitioning as in (7) and (8) be given, and assume that $A_{22}$ is nilpotent, then ONC is solvable for system (1) if and only if ONC is solvable for the subsystem described by

$$ x_1(k+1) = A_{11}x_1(k) + B_1u(k), \quad y(k) = C_1x_1(k). \quad (9) $$

**Proof.** The solvability of ONC for system (9) follows from the solvability of ONC for (1), partitioned as in (7) and (8), starting from $x(0) = (x_1^\top(0), 0^\top)^\top$, where $^\top$ denotes transpose, and $0^\top$ denotes a zero row vector of suitable dimension. Conversely, for any $x(0) = (x_1^\top(0), x_2^\top(0))^\top$, and any finite length control sequence $\{u(k)|n_2 > k \ge 0\}$, it follows by the nilpotency of matrix $A_{22}$, that $x(n_2) = (x_1^\top(n_2), 0^\top)^\top$, i.e., the second component of $x(k)$ goes to zero automatically, and stays there. Next, extending the starting control sequence with a control sequence $\{u(k)|k \ge n_2\}$ such that ONC is solved for system (9) starting from $x_1(n_2)$
at $k = n_2$, it follows directly that ONC is solved for system (1), starting from the original initial state $x(0) = (x_1^\top(0), x_2^\top(0))^\top$, by application of the control sequence $\mathbf{u} = \{u(k)|k \ge 0\}$. $\square$

3) Next assume that SNC is solvable for the subsystem (9), and therefore, by Proposition 1, also ONC is solvable for any matrix $C_1$. Then the following equivalence holds.

**Proposition 3.** Let the partitioning as in (7) and (8) be given, and assume that $\mathrm{rank}(A_{11} - zI, B_1) = n_1$, for all $z \neq 0$, then ONC is solvable for system (1) if and only if ONC is solvable for system (1) for all $x(0) = (0^\top, x_2^\top(0))^\top$.

**Proof.** Indeed, since $\mathrm{rank}(A_{11} - zI, B_1) = n_1$, for $z \neq 0$, it follows that ONC is solvable for system (1) for all $x(0) = (x_1^\top(0), 0^\top)^\top$. Because of the linearity in the initial state, it then follows that ONC is solvable for system (1) for all $x(0) = (x_1^\top(0), x_2^\top(0))^\top$ if and only if ONC is solvable for system (1) for all $x(0) = (0^\top, x_2^\top(0))^\top$. $\square$

4) Now assume that the state $x(k)$, and the matrices $A, B$ and $C$ in (1) are partitioned as

$$x(k) = \begin{pmatrix} x_1(k) \\ x_2(k) \\ x_3(k) \end{pmatrix}, A = \begin{pmatrix} A_{11} & A_{12} & A_{13} \\ 0 & A_{22} & A_{23} \\ 0 & 0 & A_{33} \end{pmatrix}, \quad (10)$$

and

$$B = \begin{pmatrix} B_1 \\ 0 \\ 0 \end{pmatrix}, C = \begin{pmatrix} C_1 & C_2 & C_3 \end{pmatrix}, \quad (11)$$

with $x_1(k) \in \mathbb{R}^{n_1}$, $x_2(k) \in \mathbb{R}^{n_2}$, $x_3(k) \in \mathbb{R}^{n_3}$, $A_{11} \in \mathbb{R}^{n_1 \times n_1}$, $A_{12} \in \mathbb{R}^{n_1 \times n_2}$, $A_{13} \in \mathbb{R}^{n_1 \times n_3}$, $A_{22} \in \mathbb{R}^{n_2 \times n_2}$, $A_{23} \in \mathbb{R}^{n_2 \times n_3}$, $A_{33} \in \mathbb{R}^{n_3 \times n_3}$, where $n_1 + n_2 + n_3 = n$, $B_1 \in \mathbb{R}^{n_1 \times m}$, $C_1 \in \mathbb{R}^{p \times n_1}$, $C_2 \in \mathbb{R}^{p \times n_2}$ and $C_3 \in \mathbb{R}^{p \times n_3}$.

The following equivalence is now immediate.

**Proposition 4.** Let the partitioning in (10) and (11) be given, and assume that $\mathrm{rank}(A_{11} - zI, B_1) = n_1$, for all $z \neq 0$, and matrix $A_{33}$ is nilpotent. It then follows that ONC is solvable for system (1) if and only if ONC is solvable for the following subsystem of (1) given by

$$\tilde{x}(k+1) = \tilde{A}\tilde{x}(k) + \tilde{B}u(k), \quad y(k) = \tilde{C}\tilde{x}(k),$$

with

$$\tilde{x}(k) = \begin{pmatrix} x_1(k) \\ x_2(k) \end{pmatrix}, \tilde{A} = \begin{pmatrix} A_{11} & A_{12} \\ 0 & A_{22} \end{pmatrix}, \\ \tilde{B} = \begin{pmatrix} B_1 \\ 0 \end{pmatrix}, \tilde{C} = \begin{pmatrix} C_1 & C_2 \end{pmatrix},$$

for any initial state $\tilde{x}(0) = (0^\top, x_2^\top(0))^\top$, with $x_2(0) \in \mathbb{R}^{n_2}$ arbitrary.

**Proof.** A proof can be obtained by combining the results of the Propositions 2 and 3. $\square$

Hence, because of the two assumptions, for the solvability of ONC for system (1), with a partitioning as in (10) and (11), we can ignore $x_3(k)$, and need only to focus

on the evolution of $x_1(k)$ and $x_2(k)$, for $x_1(0) = 0$ and $x_2(0)$ is arbitrary.

5) Finally, continue with the partitioned system and the assumptions as before, and add a rank condition.

**Lemma 4.** Let the partitioning in (10) and (11) be given, and assume that $\mathrm{rank}(A_{11} - zI, B_1) = n_1$, for all $z \neq 0$, and matrix $A_{33}$ is nilpotent. Next, also assume that

$$\mathrm{rank} (C(zI - A)^{-1}B) = \mathrm{rank} (C(zI - A)^{-1}(B, G)), \quad (12)$$

$$\text{with } G^\top = \begin{pmatrix} 0 & I & 0 \end{pmatrix}, \quad (13)$$

where the matrix $I$ in (13) denotes the $n_2 \times n_2$ identity matrix, and the zeros denote zero matrices of suitable dimensions.

Then, for any initial condition $x_0$ of the form $x_0 = (0^\top, x_2(0)^\top, 0^\top)^\top$, with $x_2(0) \in \mathbb{R}^{n_2}$ the ONC is solvable.

**Proof.** By the sufficient condition in Lemma 3, it follows that for all initial conditions $x_0 = (0^\top, x_2(0)^\top, 0^\top)^\top$, with $x_2(0) \in \mathbb{R}^{n_2}$ arbitrary, there exists a control sequence $\mathbf{u} = \{u(k)|k \ge 0\}$ such that $y_\mathbf{u}(k, x_0) = 0$ for all $k \ge K$ for some appropriate $K \ge 0$, i.e., a control sequence $\mathbf{u}$ that solves ONC for the above $x_0$. $\square$

Hence, for the partitioned system description as in (10) and (11), the rank assumption (12), and the other two assumptions ($\mathrm{rank}(A_{11} - zI, B_1) = n_1$ for all $z \neq 0$, and $A_{33}$ nilpotent) are sufficient for solving ONC.

Based on the last case, the following sufficient condition can now be given.

**Proposition 5.** Consider system (1), partitioned as in (10) and (11). Then ONC is solvable for the system if

1) $\mathrm{rank}(A_{11} - zI, B_1) = n_1$, for all $z \neq 0$,

2) rank condition (12) is satisfied

3) $A_{33}$ is nilpotent.

**Proof.** The next observations follow from the various cases. Condition 3 implies that $x_3(k)$, and therefore $C_3x_3(k)$, goes to zero automatically. Condition 2 implies that there is a control that steers $C_2x_2(k)$ to zero, and condition 1 says the same for $x_1(k)$, and therefore for $C_1x_1(k)$. By linearity, it then follows that ONC is solvable for any $x_0$. $\square$

It turns out that the partitioning, as in (10) and (11), and the checking of the above conditions, can be implemented and performed elegantly for structured systems. Hence, for structured systems, the above yields a sufficient condition for the solvability of ONC in a structural sense.

## V. STRUCTURED SYSTEMS

### A. Graph representation

We assume now that system (1) is structured, i.e., we assume that $A, B$, and $C$ in (1) are so-called structured matrices, containing free nonzeros and fixed zeros. Let the graph representing the structure of the system be given by $G = (\mathcal{V}, \mathcal{E})$, with node set $\mathcal{V}$ and edge set $\mathcal{E}$. The node set can be written as $\mathcal{V} = \mathcal{X} \cup \mathcal{U} \cup \mathcal{Y}$, with $\mathcal{X} = \{x_1, \dots, x_n\}$
the set of state nodes, $\mathcal{U} = \{u_1, \dots, u_m\}$ the set of input nodes, and $\mathcal{Y} = \{y_1, \dots, y_p\}$ the set of output nodes. The edge set is given by $\mathcal{E} = \{(x_j, x_i)|a_{ij} \neq 0\} \cup \{(u_j, x_i)|b_{ij} \neq 0\} \cup \{(x_j, y_i)|c_{ij} \neq 0\}$, where, for example, $(x_j, x_i)$ denotes an edge from node $x_j$ to node $x_i$, and $a_{ij} \neq 0$ indicates that the $(i, j)$ element of $\mathcal{A}$ is a free nonzero, and similarly for the other edges and nonzero elements.

Given graph $G = (\mathcal{V}, \mathcal{E})$, we say there is a path from node $\tilde{v} \in \mathcal{V}$ to node $\hat{v} \in \mathcal{V}$, if there exist mutually distinct nodes $v_0, v_1, \dots, v_l \in \mathcal{V}$, with $v_0 = \tilde{v}, v_l = \hat{v}$ and $(v_{i-1}, v_i) \in \mathcal{E}$, for $i = 1, 2, \dots, l$. The path then has length $l$, and is said to go from node $\tilde{v}(=v_0)$, also called begin node, to node $\hat{v}(=v_l)$, also called end node, and the path is said to consist of the nodes $v_0, v_1, \dots, v_l$. A cycle is a path with at least one edge, of which the begin node and end node coincide. A path consisting of a single node with no edge to itself, has length 0. Hence, the length of a cycle is always positive.

Given subsets $\tilde{\mathcal{V}}, \hat{\mathcal{V}} \subseteq \mathcal{V}$, we say that $\mathcal{V}$ is reachable from $\tilde{\mathcal{V}}$, if there is a path from a node $\tilde{v} \in \tilde{\mathcal{V}}$ to a node $\hat{v} \in \hat{\mathcal{V}}$. We say that a collection of paths from $\tilde{\mathcal{V}}$ to $\hat{\mathcal{V}}$ is disjoint when they mutually have no nodes in common. The size of such a disjoint collection is the number of paths it consists of.

## B. Graph decomposition

We focus now on the graph $G = (\mathcal{V}, \mathcal{E})$ of the structured system (1) and introduce the following decomposition.

* We let $\mathcal{V}_1$ be the set of nodes of $\mathcal{V}$ that are reachable from $\mathcal{U}$, i.e., that can be reached from a node in $\mathcal{U}$ using a path, possibly of zero length. We write $\mathcal{V}_1 = \mathcal{X}_1 \cup \mathcal{U}_1 \cup \mathcal{Y}_1$, where $\mathcal{U}_1 = \mathcal{U}$ (obviously), $\mathcal{X}_1$ denotes the set of state nodes that are reachable from $\mathcal{U}$, and $\mathcal{Y}_1$ denotes the set of output nodes that are reachable from $\mathcal{U}$.

* Next, consider the complementary set $\mathcal{V} \setminus \mathcal{V}_1 = \{v \in \mathcal{V}|v \notin \mathcal{V}_1\}$. Focusing on the subgraph of $G$ with node set $\mathcal{V} \setminus \mathcal{V}_1$, we let $\mathcal{V}_2 \subseteq \mathcal{V} \setminus \mathcal{V}_1$ denote all nodes that are reachable from a cycle in $\mathcal{V} \setminus \mathcal{V}_1$, i.e., all nodes in $\mathcal{V} \setminus \mathcal{V}_1$ that can be reached using a path from a node in a cycle with nodes in $\mathcal{V} \setminus \mathcal{V}_1$. The cycle has a positive length, the path may be possibly of zero length.
Let $\mathcal{V}_3$ be all remaining nodes in $\mathcal{V} \setminus \mathcal{V}_1$. Hence, $\mathcal{V}_3 = (\mathcal{V} \setminus \mathcal{V}_1) \setminus \mathcal{V}_2$.

* We note that nodes in $\mathcal{V} \setminus \mathcal{V}_1$ can not be reached from $\mathcal{U}$, but may be reachable from nodes, and even cycles, in $\mathcal{V} \setminus \mathcal{V}_1$ itself. Further, note that all nodes contained in cycles in $\mathcal{V} \setminus \mathcal{V}_1$ are elements of $\mathcal{V}_2$. Hence, the nodes in $\mathcal{V}_3$ are not contained in any cycle (in $\mathcal{V} \setminus \mathcal{V}_1$). However, the nodes in $\mathcal{V}_3$ may be reached using a path, but such a path cannot start in a cycle.

* We write $\mathcal{V} = \mathcal{V}_1 \cup \mathcal{V}_2 \cup \mathcal{V}_3$, and in particular $\mathcal{X} = \mathcal{X}_1 \cup \mathcal{X}_2 \cup \mathcal{X}_3$, $\mathcal{U} = \mathcal{U}_1$, $\mathcal{Y} = \mathcal{Y}_1 \cup \mathcal{Y}_2$, where $\mathcal{X}_1, \mathcal{U}_1, \mathcal{Y}_1$ are as above, $\mathcal{X}_2$ denotes the set of state nodes in $\mathcal{V} \setminus \mathcal{V}_1$ reachable from a cycle in $\mathcal{V} \setminus \mathcal{V}_1$, $\mathcal{X}_3 = \mathcal{X} \setminus (\mathcal{X}_1 \cup \mathcal{X}_2)$ and $\mathcal{Y}_2 = \mathcal{Y} \setminus \mathcal{Y}_1$. Also, observe that $\mathcal{V} \setminus \mathcal{V}_1 = \mathcal{V}_2 \cup \mathcal{V}_3$. The matrices $A, B$, and $C$ can be partitioned as

$$A = \begin{pmatrix} A_{11} & A_{12} & A_{13} \\ A_{21} & A_{22} & A_{23} \\ A_{31} & A_{32} & A_{33} \end{pmatrix}, B = \begin{pmatrix} B_1 \\ B_2 \\ B_3 \end{pmatrix},$$

$$C = \begin{pmatrix} C_{11} & C_{12} & C_{13} \\ C_{21} & C_{22} & C_{23} \end{pmatrix},$$

with the submatrices of suitable dimensions. Note that some of the subsets $\mathcal{V}_1, \mathcal{V}_2, \mathcal{V}_3$ may be empty, in which case the corresponding submatrices are void, i.e., consisting of zero rows and/or columns.

* As a consequence of the definition of $\mathcal{V}_1$, it follows that the submatrices $A_{21}, A_{31}, B_2$ and $B_3$, when existing, must be zero matrices. Indeed, a nonzero entry in $B_2$ or $B_3$ would mean that there are nodes in $\mathcal{V} \setminus \mathcal{V}_1$ that can be reached from $\mathcal{U}$ directly by an edge starting in $\mathcal{U}$. Similarly, a nonzero entry in $A_{21}$ or $A_{31}$ would mean that there are nodes in $\mathcal{V} \setminus \mathcal{V}_1$ that can be reached from $\mathcal{U}$ via a path that passes through $\mathcal{V}_1$. Both are impossible by the definition of $\mathcal{V}_1$.

As a consequence of the definition of the sets $\mathcal{V}_2, \mathcal{V}_3 \subseteq \mathcal{V} \setminus \mathcal{V}_1$, it follows that the submatrix $A_{32}$, when existing, must be a zero matrix. Indeed, a nonzero entry in $A_{32}$ would mean that there are nodes in $\mathcal{V}_3$ that are connected to nodes from $\mathcal{V}_2$, and therefore are connected to a cycle in $\mathcal{V} \setminus \mathcal{V}_1$. Consequently, such a node in $\mathcal{V}_3$ should belong to $\mathcal{V}_2$, which is impossible by the definition of $\mathcal{V}_3$. Finally, by definition all edges from $\mathcal{V}_1$ to $\mathcal{Y}$ have the end node in $\mathcal{Y}_1$. Therefore, $C_{21}$, when existing, must be a zero matrix.

* As a result of these observations, it follows that the matrices $A, B$ and $C$ can be partitioned in more detail as

$$A = \begin{pmatrix} A_{11} & A_{12} & A_{13} \\ 0 & A_{22} & A_{23} \\ 0 & 0 & A_{33} \end{pmatrix}, B = \begin{pmatrix} B_1 \\ 0 \\ 0 \end{pmatrix}, \\ C = \begin{pmatrix} C_{11} & C_{12} & C_{13} \\ 0 & C_{22} & C_{23} \end{pmatrix},$$

where some of the submatrices may be void because corresponding node sets that are empty.

# VI. EXISTING RESULTS AND MAIN RESULT

## A. Incorporating existing results

The following results can be found in literature. Start from the decomposition derived in the previous section.

* Recall that all state nodes in $\mathcal{X}_1$ can be reached from $\mathcal{U}$. The latter can equivalently be expressed by saying that the pair $(A_{11}, B_1)$ is irreducible, cf. [7]. By Theorem 2 of Hosoe and Matsumoto, see [9], this implies that the generic rank of $(A_{11} - zI, B_1) = n_1$, for all $z \neq 0$, or, by Lemma 1, that SNC is structurally solvable for the structured system given by the pair $(A_{11}, B_1)$.

* The structural version of the rank condition (12) is satisfied if and only if in graph $G$ the maximal number of disjoint paths from $\mathcal{U}$ to $\mathcal{Y}$ equals the maximal number of disjoint paths from $\mathcal{U} \cup \mathcal{X}_2$ to $\mathcal{Y}$. For details, see the survey paper [7].

* Recall that, by construction, there are no cycles in $\mathcal{V}_3$. Therefore, the restriction of graph $G$ to the nodes in $\mathcal{X}_3$ does not contain any cycle. The latter implies that any numerical realisation of matrix $A_{33}$ is structurally
nilpotent. Indeed, in Theorem 4 of [22], it is shown that $det(sI - A_{33}) = s^{n_3}$ if and only if the graph of $A_{33}$ contains no cycles.

## B. Main result

The previous results can be summarised in the following theorem containing sufficient conditions for the structural solvability of ONC. It is the main result of this paper.

**Theorem 1.** Consider the structured system (1), and let its graph G be decomposed as described in Subsection V-B. Then ONC is generically solvable when the maximal number of disjoint paths from $\mathcal{U}$ to $\mathcal{Y}$ is equal to the maximal number of disjoint paths from $\mathcal{U} \cup \mathcal{X}_2$ to $\mathcal{Y}$.

**Proof.** The condition on the equal maximal number of disjoint paths from $\mathcal{U}$ to $\mathcal{Y}$, and from $\mathcal{U} \cup \mathcal{X}_2$ to $\mathcal{Y}$, implies by Theorem 6 in [7] that the rank condition (12) generically holds. Then condition 2 of Proposition 5 is generically satisfied. Conditions 1 and 3 are generically satisfied by how the partitioning in Subsection V-B is obtained. Hence, in the context of the present theorem, the conditions of Proposition 5 are generically satisfied, and consequently, ONC is generically solvable. □

The graph decomposition in Subsection V-B starts with finding nodes that can be reached from the inputs. The reachable set can be simply obtained by a breadth first algorithm which complexity is linear in the number of edges in the system graph. Note that the first and third bullet in Subsection VI-A are satisfied automatically by the decomposition. The second bullet of Subsection VI-A, i.e., the condition in Theorem 1, can be checked by using ideas based on maximal size linkings, i.e., sets of disjoint paths of maximal size. See Theorem 2 in Section 3.2 of [3] for more details. The computational aspects of the computations can be worked out using bipartite graphs and maximal matchings. See Section 4, and Lemma 4 in Section 5, of [3] for more details.

To summarize, the conditions of Theorem 1 can be checked using well-known and very efficient (polynomial) algorithms from combinatorial optimization.

## VII. EXAMPLE

In this section, the main result, i.e., Theorem 1, of this paper is illustrated by means of an example.

Consider the structured system (1) given by the structured matrices

$$A = \begin{pmatrix} 0 & * & 0 & * & 0 & * \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & * & 0 \\ 0 & * & 0 & 0 & 0 & 0 \\ * & 0 & 0 & 0 & * & * \\ 0 & 0 & 0 & * & 0 & * \end{pmatrix}, \quad B = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ * \\ 0 \end{pmatrix}, \\ C = \begin{pmatrix} * & * & 0 & 0 & 0 & * \\ * & * & * & 0 & 0 & 0 \end{pmatrix},$$

where the 0's denote fixed zeros and the *'s are free nonzeros. The entries $\times$ will be treated below as a fixed zero 0 or as a free nonzero $\times$. The graph G of the system is given in Figure

1. In the graph below the special nature of the entries $\times$ (either a free nonzero or a fixed zero) is indicated by the dotted edge.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Graph of example.</figcaption></figure>

From graph G, the decomposition in Subsection V-B easily follows. Indeed, it is straightforward to see that the set of input-connected vertices is $V_1 = \{u, x_3, x_5, y_2\}$ and then $V \setminus V_1 = \{x_1, x_2, x_4, x_6, y_1\}$. If any of the entries $\times$ is a free nonzero, then the set of vertices reachable by a path from a cycle is $V_2 = \{x_1, x_6, y_1\}$ and then $V_3 = \{x_2, x_4\}$, else $V_2 = \{x_1, x_6\}$ and $V_3 = \{x_2, x_4, y_1\}$. In both cases, it follows that $X_1 = \{x_3, x_5\}$, $U_1 = \{u\}$, $Y_1 = \{y_2\}$, $X_2 = \{x_1, x_6\}$, $X_3 = \{x_2, x_4\}$, and $Y_2 = \{y_1\}$.

Based on the sets $X_1, X_2, X_3, Y_1$, and $Y_2$, the state and output component can be relabelled as follows: $\hat{x}_1 = x_3, \hat{x}_2 = x_5, \hat{x}_3 = x_1, \hat{x}_4 = x_6, \hat{x}_5 = x_2, \hat{x}_6 = x_4$, and $\hat{y}_1 = y_2, \hat{y}_2 = y_1$. Note that $u$ needs no relabelling here.

Then, the associated matrices $\hat{A}, \hat{B}$ and $\hat{C}$ can be obtained easily and can be partitioned as described in Subsection V-B:

$$\hat{A} = \begin{pmatrix} 0 & * & 0 & 0 & 0 & 0 \\ 0 & * & * & * & 0 & 0 \\ 0 & 0 & 0 & * & * & * \\ 0 & 0 & 0 & * & 0 & * \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & * & 0 \end{pmatrix}, \quad \hat{B} = \begin{pmatrix} 0 \\ * \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}, \\ \hat{C} = \begin{pmatrix} * & 0 & * & 0 & * & 0 \\ 0 & 0 & * & * & 0 & 0 \end{pmatrix}.$$

The main result of this paper (i.e., Theorem 1) is that ONC is structurally solvable for the structured system given by A, B, and C (and by $\hat{A}, \hat{B}$, and $\hat{C}$), if both entries $\times$ are fixed zeros, i.e., if there are no edges from $x_1$ to $y_1$ and from $x_6$ to $y_1$. Indeed, when $\times = 0$ for both entries, the maximal number of disjoint paths from $\mathcal{U}$ to $\mathcal{Y}$ is one and is equal to the maximal number of disjoint paths from $\mathcal{U} \cup \mathcal{X}_2$ to $\mathcal{Y}$.

If one of the two entries $\times$ is unequal to 0, i.e., $\times \neq 0$, then the maximal number of disjoint paths from $\mathcal{U} \cup \mathcal{X}_2$ to $\mathcal{Y}$ is equal to two. Indeed, then generically $y_1(k) \neq 0$ for all $k \ge 0$, no matter what control sequence $\{u(k)|k \ge 0\}$ is applied.

The above conclusions can be verified numerically by selecting the nonzero entries in A, B, and C randomly, yielding a numerical realisation of the matrices. Next, $A^n, V^*(\ker C)$, and $\langle A|\mathrm{im} B \rangle$ can be computed and Lemma 2 can be checked
numerically. Also, the condition can be checked formally by computing $A_{\lambda}^n$, $\mathcal{V}^*(\ker C_{\lambda})$ and $\langle A_{\lambda}|\mathrm{im} B_{\lambda} \rangle$, given the matrices $A_{\lambda}, B_{\lambda}$, and $C_{\lambda}$ parametrised by the vector $\lambda$, and checking the condition in Lemma 2.

## VIII. CONCLUSION AND DISCUSSION

### A. Summary

In this paper, we studied the output null controllability problem for a structured linear discrete-time system and studied the generic solvability of the problem. The latter means that the problem is solvable for almost all systems with the same structure. For this, we only needed the zero/nonzero structure of the system matrices. We represented the structure of the system by means of a directed graph and presented a graph theoretic sufficient condition for the generic solvability of the problem.

### B. Necessity of condition of Theorem 1

The obtained sufficient condition in Theorem 1 is illustrated through an example. In the example, the condition also appeared to be necessary. This phenomenon has shown up in all examples studied thus far. However, the actual necessity of the condition could not be proved yet. The (believed) necessity of the condition of Theorem 1 is a topic for future research.

### C. Extension

A possible extension of Theorem 1 might be that the set $\mathcal{X}_2$ is restricted to the set of nodes in $\mathcal{X}_2$ that are contained in a cycle in $\mathcal{X}_2$. For the example, this would mean that only node $x_4$ in $\mathcal{X}_2$ has to be taken into consideration in the application of Theorem 1. A proof of such an extension would require a more detailed investigation of the graph decomposition and all related aspects. To avoid the paper from getting too technical, this possible extension and its proof are omitted.

## REFERENCES

[1] R. Bru, L. Caccetta, and V.G. Rumchev. Monomial subdigraphs of reachable and controllable positive discrete-event systems. *Int. J. Appl. Math. Comput. Sci.*, 15(1):159–166, 2005.

[2] C. Commault and J. M. Dion. Input addition and leader selection for the controllability of graph-based systems. *Automatica*, 49(11):3322–3328, 2013.

[3] C. Commault, J. M. Dion, and J. van der Woude. Characterization of generic properties of linear structured systems for efficient computations. *Kybernetika*, 38(5):503–520, 2002.

[4] C. Commault, J. van der Woude, and T. Boukhobza. On the fixed controllable subspace in linear structured systems. *Systems & Control Letters*, 102:42–47, 2017.

[5] C. Commault, J. van der Woude, and P. Frasca. Functional target controllability of networks: structural properties and efficient algorithms. *IEEE Trans. Network Science and Engineering*, 7(3):1521–1530, 2020.

[6] E. Czeizler, K.C. Wu, C. Gratie, K. Kanhaiya, and I. Petre. Structural target controllability of linear networks. *IEEE/ACM Trans. Comp. Biol and Bioinformatics*, 15(4):1217–1228, 2018.

[7] J. M. Dion, C. Commault, and J. van der Woude. Generic properties and control of linear structured systems: a survey. *Automatica*, 39(7):1125–1144, 2003.

[8] M.L.J. Hautus. (a,b)-invariant subspaces and stabilizability spaces: some properties and applications. Technical report, (Memorandum COSOR; Vol. 7917). Technische Hogeschool Eindhoven, 1979.

[9] S. Hosoe and K. Matsumoto. On the irreducibility condition in the structural controllability theorem. *IEEE Trans. Automat. Control*, AC-24:963–966, 1979.

[10] C. T. Lin. Structural controllability. *IEEE Trans. Automat. Control*, 19(3):201–208, 1974.

[11] Y. Y. Liu, J. J. Slotine, and A. L. Barabasi. Controllability of complex networks. *Nature*, 473:167–173, 2011.

[12] K. Murota. Systems Analysis by Graphs and Matroids, volume 3 of Algorithms and Combinatorics. Springer-Verlag New-York, Inc., 1987.

[13] K. Murota and S. Poljak. Note on a graph-theoretic criterion for structural output controllability. *IEEE Trans. Automat. Control*, 35(8):939–942, 1990.

[14] A. Olshevsky. Minimal controllability problems. *IEEE Trans. on Control of Network Systems*, 1(3):249–258, 2014.

[15] S. Pequito, S. Kar, and A.P. Aguiar. A framework for structural input/output and control configuration selection in large-scale systems. *IEEE Trans. Automatic Control*, 61(2):303–318, 2016.

[16] S. Pequito, G. Ramos, S. Kar, and A.P. Aguiar. The robust minimal controllability problem. *Automatica*, 82:261–268, 2017.

[17] G. Ramos, A.P. Aguiar, and S. Pequito. An overview of structural systems theory. *Automatica*, 140, 2022.

[18] K.J. Reinschke. Multivariable control: a graph-theoretic approach. Springer Verlag, 1988.

[19] J.M. Schumacher. Algebraic characterizations of almost invariance. *International Journal of Control*, 38(1):107–124, 1983.

[20] H.L. Trentelman, A.A. Stoorvogel, and M.L.J. Hautus. Control theory for linear systems. Springer, 2001.

[21] J. van der Woude, T. Boukhobza, and C. Commault. On structural behavioural controllability of linear discrete time systems with delays. *Systems & Control Letters*, 119:31–38, 2018.

[22] J.W. van der Woude. Zero controllability in discrete-time structured systems. In *16th European Control Conference, ECC 2018*, pages 1851–1856, Limassol, Cyprus, 2018.

[23] W.M. Wonham. Linear Multivariable Control: a geometric approach. Springer, 1985.

## IX. APPENDIX

Following the method in [19], write $p(z)$ and $q(z)$ in their Laurent series as follows

$$p(z) = \sum_{k>-\ell} p_k z^{-k} \quad \text{and} \quad q(z) = \sum_{k\ge -\ell} q_k z^{-k}$$

for some nonnegative integer $\ell$, i.e.,

$$p(z) = p_{1-\ell}z^{\ell-1} + \cdots + p_{-1}z + p_0 + p_1z^{-1} + p_2z^{-2} + \cdots,$$

$$q(z) = q_{-\ell}z^{\ell} + q_{1-\ell}z^{\ell-1} + \cdots + q_{-1}z + q_0 + q_1z^{-1} + q_2z^{-2} + \cdots.$$

Then, by comparing powers of $z^{-k}$ for $k \ge -\ell$, it follows from

$$x_0 = (zI - A)p(z) - Bq(z) \quad \text{and} \quad Cp(z) \text{ is polynomial,}$$

that

$$0 = p_{1-\ell} - Bq_{-\ell}$$

$$0 = p_{k+1} - Ap_k - Bq_k \quad \text{for } -\ell < k < 0$$

$$x_0 = p_1 - Ap_0 - Bq_0$$

$$0 = p_{k+1} - Ap_k - Bq_k \quad \text{for } k \ge 1$$

and

$$0 = Cp_k \quad \text{for } k \ge 1$$

Hence, for $k \ge 1$, it follows that

$$p_{k+1} = Ap_k + Bq_k \quad \text{and} \quad Cp_k = 0.$$

Introducing $\tilde{p}(s) = \sum_{k \ge 1} p_k z^{-k}$ and $\tilde{q}(s) = \sum_{k \ge 1} q_k z^{-k}$, it follows that

$$p_1 = (zI - A)\tilde{p}(z) - B\tilde{q}(z) \quad \text{and} \quad C\tilde{p}(z) = 0,$$

which implies that $p_1 \in \mathcal{V}^*(\ker C)$, see [8].
Further,

$$ 
\begin{aligned}
x_0 &= p_1 - Ap_0 - Bq_0 \\
0 &= p_{k+1} - Ap_k - Bq_k \quad \text{for all } -\ell \le k < 0
\end{aligned}
$$

with $p_{-\ell} = 0$. In particular,

$$ 
\begin{aligned}
x_0 &= p_1 - Ap_0 - Bq_0 \\
0 &= p_0 - Ap_{-1} - Bq_{-1} \\
\vdots &= \vdots \\
0 &= p_{2-\ell} - Ap_{1-\ell} - Bq_{1-\ell} \\
0 &= p_{1-\ell} - Bq_{-\ell}
\end{aligned}
$$

Multiplying the obtained equations by $I, A, \dots, A^{\ell-1}$ and $A^{\ell}$, respectively, and adding them together, it follows that

$$ x_0 = p_1 - Bq_0 - ABq_{-1} - \dots - A^{\ell}Bq_{-\ell}. $$

Hence, it follows that $x_0 - p_1 \in \langle A | \operatorname{im} B \rangle$. With $p_1 \in \mathcal{V}^*(\ker C)$, it consequently follows that $x_0 \in \mathcal{V}^*(\ker C) + \langle A | \operatorname{im} B \rangle$.